Исследование (m, k)- методов с L-устойчивыми промежуточными схемами для решения жестких систем

Тип работы:
Диссертация
Предмет:
Вычислительная техника
Страниц:
150


Узнать стоимость новой

Детальная информация о работе

Выдержка из работы

Во многих приложениях, таких как химическая кинетика, радиоэлектроника и других, возникает необходимость численного решения задачи Коши для жестких систем обыкновенных дифференциальных уравнений.

Стремление ко все более точному описанию физических процессов приводит к постоянному росту размерности и жесткости соответствующей системы дифференциальных уравнений и предъявляет все возрастающие требования к методам интегрирования. Применение многошаговых схем в некоторых случаях нежелательно из-за эффекта & quot-срезания экстремумов& quot-. Реализация неявных методов Рунге-Кутты сложна и приводит к итерационному процессу для нахождения стадий. В работах [1]-[4] предложен способ интегрирования обыкновенных дифференциальных уравнений, основанный на локальном многочленном приближении, где также используется итерационный процесс. Применение явных методов типа Рунге-Кутты приводит к обременительному ограничению на размер шага интегрирования ввиду ограниченного размера области устойчивости. Построение явных методов с расширенными и согласованными областями устойчивости [5, 6] не способно полностью решить проблему.

При решении задачи Коши для жестких систем обыкновенных дифференциальных уравнений широкое распространение получили методы типа Розенброка [7]. Данные численные формулы получены из полуявных методов типа Рунге-Кутты [8, 9], в которых при решении нелинейной системы алгебраических уравнений используется одна итерация метода Ньютона (см., например, [10]). В результате при вычислении каждой стадии вместо нелинейной системы алгебраических уравнений нужно решать линейную систему, а требуемая точность вычислений достигается за счет подходящего выбора величины шага интегрирования. Для снижения вычислительных затрат при решении линейной системы обычно используют LU -разложение. Другие способы решения линейных систем можно найти в работах [11]-[21].

Максимальный порядок точности методов типа Розенброка не превышает (к + 1), где число к задает количество вычислений правой части системы дифференциальных уравнений на шаге. Несмотря на более сложную (по сравнению с явными методами) реализацию и необходимость вычисления и обращения матрицы Якоби, методы Розенброка обладают неограниченной областью устойчивости, их применение позволяет снять ограничения по устойчивости на размер шага интегрирования.

При решении жестких систем важную роль играет также численная устойчивость. Эффективность метода определяется в большей степени свойствами устойчивости, чем точности, поэтому методы решения жестких систем должны быть как минимум Л-устойчивыми. В настоящее время в основном используют L -устойчивые схемы, что позволяет еще больше снизить вычислительные затраты.

Проблеме устойчивости численных методов на нелинейных задачах посвящена монография [22], построение численных схем для интегрирования жестких систем и способы контроля точности описываются в работах [10, 23]. Возможности применения явных методов для жестких систем, включая контроль устойчивости, описаны в монографии [5]. В этих работах имеется обширный библиографический список по соответствующей тематике, поэтому в дальнейшем приводятся ссылки только на непосредственно используемые источники.

При большой размерности решаемой задачи основные вычислительные затраты методов Розенброка приходятся на обращение матрицы Якоби, что заставляет искать способы сокращения числа обращений данной матрицы. Один из таких способов — так называемое замораживание матрицы Якоби, то есть использование одной и той же матрицы Якоби на нескольких шагах интегрирования. Если алгоритм интегрирования не обладает такой возможностью, это означает ограничение на размерность решаемых задач. При этом возможности численного вычисления матрицы Якоби и ее замораживания должны быть учтены уже на стадии математического описания алгоритма, в противном случае заявленная точность метода не будет выполнена.

Известно, что при замораживании матрицы Якоби в методах Розенброка максимальный порядок точности не превышает двух [24].

В [25] предложен класс (т, к) -методов, в которых вычисление стадий не связывается с обязательным вычислением правой части системы дифференциальных уравнений. Применение данных методов позволяет построить численные схемы с более лучшими, чем у методов Розенброка, свойствами точности и устойчивости. В рамках (ш, к) -методов значительно упрощается проблема замораживания матрицы Якоби и ее численного вычисления.

В настоящее время на базе (га, к) -методов с замораживанием матрицы Якоби удалось построить алгоритмы интегрирования до четвертого порядка порядка точности [26]. Показано, что максимальный порядок точности (га, к) -методов равен (к + 2) в случае аналитического вычисления матрицы Якоби и (& + 1) при ее замораживании. Здесь к — количество вычислений правой части на шаг интегрирования. Построены (т, к) -схемы максимального порядка точности, обладающие свойством L -устойчивости.

При построение методов интегрирования жестких систем необходимо учитывать, что классический порядок точности метода, основанный на сравнении разложений приближенного и точного решений в ряды Тейлора, в случае жестких систем оказывается завышенным по сравнению с фактическим. На это явление впервые было указано в работе [27], а затем в [28] было введено понятие В -сходимости, способное предоставить оценку глобальной ошибки метода, не зависящую от жесткости решаемой задачи. Как показано в [10, с. 267], методы Розенброка не могут быть В -сходящимися.

Наряду с В-сходимостью было введено понятие BSI -устойчивости [29], которое играет существенную роль для В-сходимости и связано с поведением внутренних схем. В [22, с. 194] установлено, что однократно неявные методы Рунге-Кутты, к которым относятся и методы Розенброка, BSI -устойчивы при некотором ограничении на шаг интегрирования. Данное ограничение можно обойти, потребовав L -устойчивость промежуточных численных формул.

Поскольку о возможности построения В -сходящихся и BSI -устойчивых (ш, к) -методов на сегодняшний день ничего не известно, можно надеяться, что (т, к) -схема, обладающая L -устойчивыми внутренними схемами, будет обладать лучшими свойствами сходимости на жестких системах. Однако во многих современных алгоритмах промежуточные численные формулы не обладают свойством L -устойчивости. В результате эффективность алгоритма интегрирования и точность расчетов понижаются.

Следует заметить, что свойства В -сходимости и BSI -устойчивости зависят от класса решаемых задач, и проверка этих условий для достаточно общих классов задач трудоемка, в то время как во многих случаях применение L -устойчивых схем с L -устойчивыми внутренними схемами, построенных на основе классического порядка точности, вполне себя оправдывает.

На практике известно, что при невысокой требуемой точности вычислений выгоднее применять схемы низкого порядка точности, в то время как схемы высокого порядка оказываются эффективнее при более высокой требуемой точности. Более того, в одной и той же задаче встречаются участки, которые эффективней решать разными методами. Все это привело к созданию методов переменного порядка точности, которые способны самостоятельно решить вопрос о применении на данном участке той или иной схемы. На настоящий момент методы переменного порядка на основе (ш, к) -методов отсутствуют.

В данной работе предлагается повысить эффективность (га, к) -методов путем построения L -устойчивых схем, обладающих внутренней L -устойчивостью. Решается вопрос о построении таких схем, имеющих максимальный порядок точности, и предлагается способ построения методов переменного порядка на базе (то, к) -методов. Построена пара (то, к) -методов третьего и четвертого порядка, в которых для нахождения стадий используется одна и та же матрица. Использование пар подобных методов в алгоритмах переменного порядка и шага может упростить задачу замораживания матрицы Якоби в данных алгоритмах.

В главе 1 приведены основные определения, описаны (то, к) -методы и некоторые способы контроля точности- сформулирован алгоритм интегрирования переменного шага- доказаны утверждения о максимальном порядке точности (то, к) -методов при к = 1,2,3 как в случае аналитического вычисления матрицы Якоби, так и в случае ее замораживания.

В главе 2 построены L -устойчивые (то, к) -алгоритмы второго, третьего, четвертого и пятого порядка точности, обладающие внутренней L -устойчивостью. Построены методы максимального порядка точности, обладающие L -устойчивыми промежуточными схемами. Приведены результаты расчетов, подтверждающие повышение эффективности методов с внутренней L-устойчивостью.

В главе 3 построены L -устойчивые алгоритмы второго и третьего порядка с L -устойчивыми внутренними схемами. Предлагаемые алгоритмы обладают возможностью замораживания матрицы Якоби и ее численного вычисления. Приведены результаты расчетов, подтверждающие эффективность замораживания матрицы Якоби в построенных алгоритмах.

В главе 4 сконструирован алгоритм переменного порядка и шага на основе методов второго и третьего порядка. Построена пара (га, к) -методов третьего и четвертого порядка, в которых используется одна и та же матрица Dn, приведены результаты расчетов.

Основные результаты диссертации опубликованы в работах [30]-[41].

Заключение

В работе построены эффективные методы интегрирования жестких систем, обладающие свойством L -устойчивости основной и промежуточных схем. Получены следующие новые результаты

• Доказаны теоремы о максимальном порядке точности (ш, к) -методов при к = 1,2,3 с замораживанием и без замораживания матрицы Якоби, а также с возможностью ее численной аппроксимации. Показано, что методы максимального порядка могут обладать свойством внутренней L -устойчивости.

• На основе (ш, к) -методов с аналитическим вычислением матрицы Якоби построены алгоритмы второго, третьего, четвертого и пятого порядков точности, обладающие свойством внутренней L -устойчивости.

• На основе (т, к) -методов с замораживанием матрицы Якоби и ее численной аппроксимацией построены алгоритмы второго и третьего порядков точности, обладающие свойством внутренней L -устойчивости.

• На десяти тестовых примерах из области химической кинетики показано почти полуторократное повышение эффективности методов за счет L -устойчивости промежуточных численных схем.

• Исследована возможность построения методов переменного порядка и шага на основе (ш, к) -методов. Проведены численные расчеты, подтверждающие повышение эффективности алгоритмов интегрирования за счет внутренней L -устойчивости.

ПоказатьСвернуть

Содержание

Глава

Исследование (то, к) -методов

1. Основные определения.

2. (то, к) -методы.

3. Максимальный порядок точности (то, к) -методов с аналитическим вычислением матрицы Якоби

4. Максимальный порядок точности (то, к) -методов с замораживанием матрицы Якоби.

5. Построение неравенства для контроля точности вычислений

6. Алгоритмы интегрирования.

Глава

Алгоритмы интегрирования с аналитическим вычислением матрицы Якоби

1. (2,1)-метод второго порядка точности.

2. (2,2)-метод второго порядка с внутренней L -усточивостыо

3. (3,2)-метод третьего порядка с внутренней L -устойчивостью

4. (4,2)-метод третьего порядка с внутренней L- устойчивостью

5. (5,2)-метод четвертого порядка с внутренней L -устойчивостью

6. (6,3)-метод пятого порядка.

7. (6,3)-метод пятого порядка с внутренней L -устойчивостью

8. Анализ результатов расчетов.

Глава

Алгоритмы с замораживанием матрицы Якоби

1. (2,2)-метод второго порядка

2. (3,2)-метод третьего порядка.

3. Анализ результатов расчетов.

Глава

Алгоритмы переменного порядка

1. Метод переменного порядка с переключением по оценке локальной ошибки

2. (т, к) -методы с одной матрицей для нахождения стадий

3. Анализ результатов расчетов.

Список литературы

1. Залеткин, С.Ф. О построении многочленных приближений при численном решении обыкновенных дифференциальных уравнений /С.Ф. Залеткин, Татевян С. К., Сорокин Н. А. // Вычислительные методы и программирование. -т.2. -2001. -С. 56−64. (http: //num-meth. srcc. msu. su)

2. Залеткин, С. Ф. Формула численного интегрирования Маркова и ее применение в ортогональных разложениях /С.Ф. Залеткин, Татевян С. К., Сорокин Н. А. // Вычислительные методы и программирование. -Т.2. -2001. -С. 131−158. (http: //num-meth. srcc. msu. su)

3. Залеткин, С. Ф. Численное интегрирование обыкновенных дифференциальных уравнений с использованием рядов Чебышева /С.Ф. Залеткин, Татевян С. К., Сорокин Н. А. // Вычислительные методы и программирование. -т.З. -2002. -С. 52−81. (http: //num-meth. srcc. msu. su)

4. Новиков, Е. А. Явные методы для жестких систем. /Е. А. Новиков. Новосибирск: Наука.- 1997 .- 195 с.

5. Новиков, Е. А. Явные методы второго порядка с согласованными областями устойчивости/ Е. А. Новиков, JL Н. Контарева// Вычислительные технологии, 2001.- т. 6.- JYH.- С. 40−50.

6. Rosenbrock, Н.Н. Some general implicit processes for the numerical solution of differential equations /Н. H. Rosenbrock// Computer, № 5,1963. p. 329−330.

7. Butcher, J. C. Implicit Runge-Kutta Processes /J. C. Butcher// Math. Сотр. 1964. -18.- С. 50−64.

8. N0rsett, S. P. Semi-Explicit Runge-Kutta Methods//S. P. N0rsett. -Tech. Rept. -Math and Cornp. -№ 6/74. -1974. -Univ. of Trondheim.

9. Хайрер, Э. Решение обыкновенных дифференциальных уравнений. Жесткие и дифференциально-алгебраические задачи // Э. Хайрер, Ваннер: Пер. с англ. М.: Мир. 1999. 685с.

10. Axelsson, О. A general incomplete block-factorization method/O. Axelsson //Linear Alg. Appl., 74 P. 179−190, 1986.

11. Axelsson, O. Iterative Solution Methods/O. Axelsson// Cambridge University Press.- New York.- 1994.

12. Bank, R. E. An analysis of the composite step biconjugate gradient method/ R. E. Bank, T. F. Chan// Numer. Math. 66: P. 295−319.- 1993.

13. Brezinski, C. Projection Methods for Systems of Equations/ C. Brezinski//North-Holland.- Amsterdam.- 1997.

14. Dongarra, J. J. Numerical Linear Algebra for High-Performance Computers/J. J. Dongarra, I. S. Dulf, D. C. Sorensen, H. A. van der Vorst// SIAM.- Philadelphia, PA.- 1998.

15. Elman, H. С. A stability analysis of incomplete LU factorizations/H. C. Elman// Math. Сотр.- 47. -P. 191−217.- 1986.

16. Hackbusch, W. Iterative Solution of Large Linear Systems of Equations/ W. Hackbusch// Springer Verlag.- New York.- 1994.

17. Hestenes, M. R. Methods of conjugate gradients for solving linear systems/ M. R. Hestenes, E. L. Stiefel//J. Res. Nat. Bur. Stand., Section В.- 49. -P. 409−436. -1952.

18. Lanczos, C. Solution of systems of linear equations by minimized iterations/ C. Lanczos//J. Res. Nat. Bur. Stand. -49. -P. 33−53.- 1952.

19. Meurant, G. Computer solution of large linear systems/ G. Meurant//North-Holland.- Amsterdam.- 1999.

20. Greenbaum, A. Iterative Methods for Solving Linear Systems/ A. Greenbaum//SIAM.- Philadelpha, PA. -1997.

21. Деккер, К. Устойчивость методов Руиге-Кутты для жестких нелинейных дифференциальных уравнений/К. Деккер, Я. Вервер. -М: Мир. -1988. -332с.

22. Холл, ДЖ. Современные численные методы решения обыкновенных дифференциальных уравнений / ДЖ. Холл, ДЖ. УАТТ // М.: Мир, 1979. 312с.

23. Новиков, Е. А. Замораживание матрицы Якоби в методах типа Розенброка второго порядка точности. /Е. А. Новиков, В. А. Новиков, J1. А. Юматова//ЖВМ и МФ. -1987. -Т. 27. -№ 3. -С. 385−390.

24. Новиков, Е. А. Одношаговые безитерационные методы решения жестких систем. /Е. А. Новиков, Ю. А. Шитов, Ю. И. Шокин // ДАН СССР .- 1988 .- 301.- № 6.- С. 1310 1314.

25. Новиков, Е. А. Исследование (М, К)-методов решения жестких систем с тремя вычислениями правой части //Е А. Новиков, М. И. Голушко. Препринт № 5: Красноярск, ВЦ СО РАН. -1992 .- 45 с.

26. Prothero, A. On the Stability and Accuracy of One-Step Methods for Solving Stiff Systems of Ordinary Differential Equations/A. Prothero, A. Robinson//Math, of Coput. -vol. 28. -1974. -P. 145−162.

27. Frank, R. The Concept of Б-convergence /R. Frank, J. Schneid, C. W. Ueberhuber//SIAM J. Numer. Anal.- vol. 18. -1981. -P. 753−780.

28. Frank, R. Stability Properties of Implicit Runge-Kutta Methods/R. Frank, J. Schneid, C. W. Ueberhuber//Bericht Nr 52/82. -Institut fur Numerische Mathematik, TU-Wien. -1982.

29. Двинский, А. Л. Об одном алгоритме интегрирования жестких систем ОДУ / A. JI. Двинский // Информатика и информационные технологии.- Красноярск, 1999 .- С. 83−84.

30. Двинский, A. J1. (т, 2)-методы решния жестких систем ОДУ / A. JT. Двинский // Информатика и информационные технологии.- Красноярск, 2000.- С. 77−78.

31. Двинский, A. JI. Исследование (3,2) -метода решения жестких систем / A. JI. Двинский // Наука. Тезисы. Инновации. Региональная научная конференция студентов, аспирантов, молодых ученых. Тезисы докладов.- Новосибирск, 2001 .- ч. 1 С. 57−58.

32. Двинский, A. JI. (4,2)-метод решения жестких систем ОДУ с L-устойчивой внутренней схемой / A. JI. Двинский //Информатика и информационные технологии.- Красноярск, 2001.- С. 53−62.

33. Двинский, А. Л. (4,2) — метод третьего порядка для решения жестких систем / A. J1. Двинский, Е. А. Новиков// труды международной конференции RDAMM-2001, Вычислительные технологии, 2001.- т. 6.- ч. 2.- С. 470−474.

34. Двинский, A. JI. (4,2)-алгоритм интегрирования жестких систем ОДУ / A. JI. Двинский// Материалы XXXIV научной студенческой конференции.- Красноярск, 2001.- С. 53−59.

35. Dvinskiy, A.L. (4, 2)-Method of Order 3 for Solving Stiff Systems /А. L. Dvinskiy, E. A. Novikov//AMSE, Advances A.- vol. 40.- № 3. -2003.- P. 61−70.

36. Двинский, A. JI. Замораживание матрицы Якоби в (3,2) -методе решения жестких систем / A. JI. Двинский, Е. А. Новиков// Вычислительные технологии. 2003. т. 8. Региональный вестник Востока. 2003. — № 3. — (Совм. выпуск. — ч. 2.) — С. 272−278.

37. Двинский, A. JI. Алгоритм интегрирования переменного порядка и шага для решения жестких систем / A. JI. Двинский, Е. А. Новиков// Вестник КГТУ. -выпуск ЗЗ. -Красноярск, 2004.- С. 79−87.

38. Двинский, АЛ. L-устойчивая (6,3)-схема пятого порядка точности для решения жестких систем /АЛ. Двинский, Е. А. Новиков // Вычислительные технологии. -т.9.- Вестник КазНУ.- № 3(42).- 2004. С. 228−234.

39. Новиков, Е. А. М, 3-метод третьего порядка для жестких неавтономных систем ОДУ/ Е. А. Новиков, М. И. Голушко// Вычислительные технологии, 1998.- т. 3.- № 3.- С. 48−54.

40. Новиков, Е. А. Одношаговые безитерационные методы решения жестких систем /Е. А. Новиков.- Новосибирск: ВЦ СО РАН, дисс. д.ф.м.н. .- 1991.- 327с.

41. Новиков, Е. А. Построение (т, к)-методов решения линейных систем обыкновенных дифференциальных уравнений/ Е. А. Новиков// Вычислительные технологии, сборник научных трудов ИВТ СО РАН: Новосибирск .- 1993.- т. 2. -№ 7.- С. 140−155.

42. Richardson, L. F. The Deferred Approach to the Limit/L. F. Richardson// Phil. Trans. A. 1927.- vol. 226. -P. 299−349.

43. Richardson, L. F. The Approximate Arithmetical Solution by Finite Differences od Physical Problems Including Differential Equations, with an Application to the Stresses in a Masonry Dam/L. F. Richardson//Phil. Trans. A. 1910.- vol. 210. -P. 307−357.

44. Cescino, F. Numerical Solution of Initial Value Problems /F. Cescino, J. Kuntzman//Prentice-Hall, Englewood Cliffs, A, New Jersey, 1966.

45. Fehlberg, E. Low-Order Classical Runge-Kutta Formulas with Step Size Control and their Application to Some Heat Transfer Problems/E. Feglberg//NASA Technical Report 315. -1969.

46. England, R. Error Estimates for Runge-Kutta Type Solutions to Systems of Ordinary Differential Equations/ R. England//The Computer J. .- 1969. -vol. 12. -P. 166−170.

47. Sarafyan, D. Error Estimation for Runge-Kutta Methods through Pseudo-Iterative Formulas/D. Sarafyan//Techn. Rep. No. l4. -1966. -Lousiana State Univ. -New Orleans.

48. Dormand, J. R. A Family of Embedded Runge-Kutta Formulae/J. R. Dormand, P. J. Prince//J. Сотр. Appl. Math. .- vol.6. -1980. -P. 19−26.

49. Хайрер, Э. Решение обыкновенных дифференциальных уравнений, нежесткие задачи // Э. Хайрер, Г. Ваннер, С. Нёрсетт: Пер. с англ. М.: Мир. 1990. 512с.

50. Shampine, L. F. The Art of Writing a Runge- Kutta Code/ L. F. Shampine, H. A. Watts//II, Appl. Math. Comput., 1979, vol. 5, P. 93−121.

51. Gear, C. W. The Automatic Integration of Stiff Ordinary Differential Equations/C. W. Gear//Inform. Proc. -1969. -P. 187−193.

52. Byrne, G. D. Stiff ODE Solvers: a Review of Current and Coming Attractions/G. D. Byrne, A. C. Hindmarsh//J. Сотр. Phys. -1986.- № 70. -P. l-62.

53. Артемьев, С. С. Алгоритм переменного порядка и шага для численного решения жестких систем обыкновенных дифференциальных уравнений /С. С. Артемьев, Г. В. Демидов//ДАН СССР. -1978. -Т. 238,№ 3. -С. 517−520.

54. Демидович, Б. П. Численные методы анализа/Б.П. Демидович, И. А. Марон, Э. 3. Шувалова. -М. :Наука. -1967

55. Демидов, Г. В. Оценка ошибки одношаговых методов интегрирования обыкновенных дифференциальных уравнений. /Г. В. Демидов, Е. А. Новиков//Числ. мет. мех. сплош. среды. -Новосибирск. -1985. -т. 16. -т. -С. 27−39.

56. Новиков, Е. А. Апроксимация матрицы Якоби в (М. К.)-методах третьего порядка точности // Е. А. Новиков, М. И. Голушко, Ю. А. Шитов .- Препринт Ml: Красноярск, ВЦ СО РАН .- 1991 .- 36 с.

57. Swart, J. J. В. On the Construction of Error Estimators for Implicit Runge-Kutta Methods/ J. J. B. de Swart, G. Soderlind //MAS-R9704. -1997.

58. Enright, W. H. Comparing numerical methods for the solutions of systems of ODE’s / W.H. Enright, Т.Е. Hull //BIT .- 1975 .- № 15.- C. 10 48.

59. Демидов, Г. В. Исследование точности неявных одношаговых методов // Г. В. Демидов, JI. А. Юматова .- Препринт № 11: Новосибирск, ВЦ СО АН СССР.- 1976 .- 22 с.

Заполнить форму текущей работой