Методы декомпозиции для решения некоторых параболических задач тема диссертации и автореферата по ВАК РФ 01.01.07, кандидат физико-математических наук Гололобов, Сергей Владимирович

• Гололобов, Сергей Владимирович
• кандидат физико-математических наук
• 2000

Оглавление диссертации кандидат физико-математических наук Гололобов, Сергей Владимирович

Введение

0.1. Предварительные замечания.

0.2. Параболические начально-краевые задачи.

0.3. Нелинейные задачи

0.4. Дискретизация и вспомогательные неравенства

1. Явно-неявный метод декомпозиции области

1.1. Некоторые вспомогательные неравенства

1.2. Формулировка метода.

1.3. Свойства полиномов Ланцоша.

1.4. Устойчивость

1.5. Теоремы сходимости

1.6. Численные эксперименты ( одномерная задача )

1.7. Явно-неявный метод дбкймпозиции с расщеплением

1.8. Численные эксперименты ( дв^ерная задача )

2. Метод декомпозиции области типа переменных направлений

2.1. Формулировка метода

2.2. Теоремы сходимости.

2.3. Теоремы сходимости для одномерной задачи.

2.4. Численные эксперименты.

3. Неявные методы с параметром для нелинейных задач

3.1. Устойчивость неявного метода с параметром

3.2. Теоремы сходимости.

3.2.1. Произвольные шаги по времени.

3.2.2. Почти постоянные шаги по времени.

3.3. Численные эксперименты.

3.4. Экстраполяционные неявные методы с параметром . 95 3.4.1. Экстраполяционные неявные методы с параметром для модельной задачи.

3.4.2. Неявный метод с параметром со статической экстраполяцией для задач реакции-диффузии

3.4.3. Неявный метод с параметром с динамической экстраполяцией для монотонных операторов

3.5. Адаптивные сетки.

3.5.1. Построение адаптивной сетки по пространству

3.5.2. Построение адаптивной сетки по времени

3.6. Численные эксперименты.

Заключительные замечания

Введение диссертации (часть автореферата) на тему «Методы декомпозиции для решения некоторых параболических задач»

0.1. Предварительные замечания

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

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

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

Теперь кратко остановимся на научной новизне полученных в диссертации результатов. В основе исследования, проведенного в главах 1 и 2 лежит известная идея метода штрафа, которая используется для построения методов декомпозиции области на несогласованных сетках. В главе 1 рассматривается явно-неявный метод, для которого расширена область устойчивости за счет использования полиномов Ланцоша. В главе 2 предлагается метод декомпозиции области типа переменных направлений, имеющий повышенную скорость сходимости. В главе 3 рассматривается экстраполяционная методика как эффективный способ распараллеливания вычислений. При этом экстраполяция проводится не по параметру дискретизации, а по некоторому весовому параметру, что является новой идеей. Однако идея получения оценок, основанных на односторонней константе Липшица, широко известна. Все изложенные результаты являются оригинальными, за исключением результатов пунктов 3.1-3.2, которые фактически были получены О.Аксельссоном, а в данной работе они приводятся в адаптированной для дальнейших исследований форме. Результаты данной диссертации получены в соавторстве с Ю.М.Лаевским, а исследования, приведенные в главе 3, проводились также в соавторстве и с О.Аксельссоном.

И наконец, несколько слов о структуре диссертации. Работа состоит из введения, трех глав, заключительной части и спис

Список литературы диссертационного исследования кандидат физико-математических наук Гололобов, Сергей Владимирович, 2000 год

1. Бесов О.В., Ильин В.П., Никольский С.М. Интегральные представления функций и теоремы вложения // М., Наука, (1975).

2. Вабищевич П.Н. Разностные схемы декомпозиции расчетной области при решении нестационарных задач // Журн.вычислит, математики и мат.физики, (1989). Т.29, №12. С. 1822-1829.

3. Ладыженская O.A. Краевые задачи математической физики // М., Наука, (1973).

4. Лаевский Ю.М. Методы разбиения области при решении двумерных параболических уравнений // Вариационно-разностные методы в задачах численного анализа. Новосибирск: ВЦ СО АН СССР, (1987). С. 112-128.

5. Лаевский Ю.М. Об одном алгоритме декомпозиции области без налегания подобластей решения параболических уравнений // Журн.вычислит, математики и мат.физики, (1992). Т.32, №11. С. 1744-1755.

6. Лаевский Ю.М. Метод конечных элементов решения многомерных параболических уравнений // Новосибирск, НГУ, (1993).

7. Лаевский Ю.М. О декомпозиции области для параболических задач с разрывными решениями и методе штрафа // Журн.вычислит.математики и мат.физики, (1994). Т.34, №5. С. 702-718.

8. Лаевский Ю.М., Гололобов С.В. Явно-неявные методы декомпозиции области решения параболических уравнений // Сиб.мат.журн., (1995). Т.36, №3, С. 590-601.

9. Лаевский Ю.М., Литвиненко С.А. О методе декомпозиции области с покомпонентным расщеплением решения параболических уравнений // Новосибирск, Препринт/РАН Сиб. отд-ние. ВЦ, (1993). №991.

10. Лаевский Ю.М., Мацокин A.M. Методы декопозиции решения эллиптических и параболических краевых задач // Сиб.журн.выч.математики, (1999). Т. 2, № 4, С. 361-372.

11. Лебедев В.И. Явные разностные схемы с переменными шагами по времени для решения жестких систем уравнений // М., Препринт/АН СССР. ОВМ, (1987). №177.

12. Лебедев В.И. Как решать явными методами жесткие системы дифференциальных уравнений // Вычислительные процессы и системы. М., Вып. 8, (1991). С. 237-291.

13. Лебедев В.И., Финогенов С.А. О порядке выбора итерационных параметров в чебышевском циклическом итерационном методе // Журн.вычислит. математики и мат.физики, (1971). Т.11, №2. С. 425-438.

14. Лионе Ж.-Л., Мадженес Э. Неоднородные граничные задачи и их приложения // М., Мир, (1971).

15. Локуциевский В.О., Локуциевский О.В. Применение чебышевских параметров для численного решения некоторых эволюционных задач // М., Препринт/АН СССР. ИПМ, (1984). №98.

16. Марчук Г.И., Шайдуров В.В. Повышение точности решений разностных схем // М., Наука, (1979).

17. Михлин С.Г. Вариационные методы в математической физике // М., Наука, (1970).

18. Обэн Ж.-П. Приближенное решение эллипттических краевых задач // М., Мир, (1977).

19. Оганесян Л.А., Руховец Л.А. Вариационно-разностные методы решения эллиптических уравнений // Ереван: Изд. АН АрмССР, (1979).

20. Самарский A.A. Введение в теорию разностных схем // М., Наука, (1971).

21. Самарский A.A., Николаев Е.С. Методы решения сеточных уравнений // М., Наука, (1978).

22. Сьярле Ф. Метод конечных элементов для эллиптических задач // М., Мир, (1980).

23. Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры // М.-Л., Гос. изд-во физ.-мат. лит-ры, (1963).

24. Шайдуров В.В. Многосеточные методы конечных элементов // М., Наука, (1989).

25. Яковлев Г.Н. О следах функций из пространства W^ на кусочно-гладких поверхностях // Матем.сб., (1967). Т. 74, № 4, С. 526-543.

26. Axelsson О. Error estimates for Galerkin methods for quasilinear parabolic and elliptic differential equations in divergence form // Numer. Math., (1977). V. 28. pp. 1-14.

27. Axelsson O. Error estimates over infinite intervals of some discretizations of evolution equations // BIT, (1984). V. 24, pp. 413-424.

28. Axelsson 0. Stability and error estimates valid for infinite time, for strongly monotone and infinitely stiff evolution equations // Equadiff 6 ( edited by J.Vosmansky and M.Zlamal ), J.E.Purkyne University, Brno, Czechoslovakia, (1985). pp. 274-284.

29. Axelsson O. A priori bounds and discretization error estimates for parabolic problems // Proceedings of ISNA, Prague (1987), Teubner, Band 107, Leipzig, (1988). pp. 8-18.

30. Axelsson O., Gololobov S.V. Stability and error estimates for the 0-method for strongly monotone and infinitely stiff evolution equations // Dept. of Math., Catholic University of Nijmegen, The Netherlands, Report No. 9908, (1999).

31. Axelsson O., Gololobov S.V., Laevsky Yu.M. Extrapolated 0-methods for nonlinear reaction-diffusion problems // East-West Journ. Numer. Anal., (1999). V.7, No.4. pp. 45-52.

32. Axelsson O., Steihaug T. Some computational aspects in the numerical solution of parabolic equations // J. Comp. App. Math., (1978). V.4. pp. 129-142.

33. Babuska I. The finite element method with penalty // Math, of Comput., (1973). V.27, N. 122. pp. 221-228.

34. Dahlquist G., Error analysis for a class of methods for stiff nonlinear initial value problems // Numerical Analysis ( G.A.Watson, ed. ), Dundee 1975, Springer-Verlag, LNM 506, (1976).

35. Dawson C.N., Du O. A domain decomposition method for parabolic equations based on finite elements // Domain Decomposition Methods for Partial Differential Equations. Philadelphia: SIAM, (1991). pp. 255-263.

36. Dawson C.N., Dupont T.F. Noniterative domain decomposition for second order hyperbolic problems // Domain Decomposition Methods in Science and Engineering, Abstr. Villa Olmo, Como (Italy), (1992). p. 11.

37. Dryja M. Substructuring methods for parabolic problems // Technical Report 529, N.Y.University, Computer Sci. Dept., (1990).

38. Dupont T. Mesh modification for evolution equations // Math. Comp., (1982). V. 39. pp. 85-107.

39. Eriksson K., Johnson C. Error estimates and automatic step control for nonlinear parabolic problems, I // SIAM J. Numer. Anal., (1987). V. 24. pp. 12-23.

40. Eriksson K., Johnson C. Adaptive finite element methods for parabolic problems IV: nonlinear problems // SIAM J. Numer. Anal., (1995). V. 32. pp. 1729-1749.

41. Eriksson K., Johnson C. Adaptive finite element methods for parabolic problems V: long-time integration // SIAM J. Numer. Anal., (1995). V. 32. pp. 1750-1763.

42. Ewing R.E., LazarovR.D., Vassilev A.T. Adaptive techniques for time-dependent problems // Comp. Meth. Appl. Mech. Engrg., (1992). V. 101. pp. 113-126.

43. Ewing R.E., LazarovR.D., Vassilev A.T. Finite difference scheme for parabolic problems on composite grids with refinement in time and space // SIAM J. Numer. Anal., (1994). V. 31. pp. 1605-1622.

44. Prank R., Schneid J., Ueberhuber C.W. The concept of B-convergence // SIAM J. Numer. Anal., (1981). V. 18. pp. 753-780.

45. Gololobov S.V. Explicit-implicit domain decomposition methods based on splitting for solving parabolic equations // Bull. Novosibirsk Comp. Center, Ser. Numer. Anal., (1996). Is.7. pp. 19-36.

46. Gololobov S.V., Laevsky Yu.M. On one domain decomposition method with nonmatching grids for solving parabolic equations // Bull. Novosibirsk Comp. Center, Ser. Numer. Anal., (1996). Is.7. pp. 37-50.

47. Johnson C., Nie Y., Thomee V. An a posteriori error estimate and adaptive time step control for a backward Euler discretization of a parabolic problem // SIAM J. Numer. Anal., (1990). V. 27. pp. 277-291.

48. Kraaijevanger J.F.B.M. B-convergence of the implicit midpoint rule and the trapezoidal rule // BIT, (1985). V. 25. pp. 652-666.

49. Kraaijevanger J.F.B.M. Contractivity of Runge-Kutta methods // BIT, (1991). V. 31. pp. 482-528.

50. Laevsky Yu.M. The use of the Lanczos polynomials for solving parabolic equations // Numerical Methods and Applications. Sofia: Publishing House of the Bulg. Acad, of Sci., (1989). pp. 244-249.

51. Laevsky Yu.M. On the domain decomposition method for parabolic problems // Bull, of the Novosibirsk Computing Center, Ser. Numer. Anal., (1993). Is. 1. pp. 41-62.

52. Laevsky Yu.M. On the explicit-implicit domain decomposition method for parabolic problems // Bull, of the Novosibirsk Computing Center, Ser. Numer. Anal., (1993). Is. 2. pp. 79-90.

53. Laevsky Yu.M. Preconditioning operators for grid parabolic problems // Rus. J. of Numer. Anal, and Math. Modell., (1996). V. 11, No. 6. pp. 497-515.

54. Laevsky Yu.M., Litvinenko S.A. On the domain decomposition method with the splitting in subdomains for solving parabolic problems // Rus. J. of Numer. Anal, and Math. Modell., (1996). V. 11, No. 2. pp. 167-182.

55. Lang J., Walter A. A finite element method adaptive in space and time for nonlinear reaction-diffusion systems // IMPACT Comput. Sci. Eng., (1992). V. 4. pp. 269-314.

56. Litvinenko S.A. On the explicit-implicit domain decomposition method without overlapping for parabolic problems // Bull, of the Novosibirsk Computing Center, Ser. Numer. Anal., (1994). Is. 6. pp. 43-60.

57. Mathew T., Russo G., Wang J. A domain decomposition based splitting method for solving parabolic problems // Domain Decomposition Methods in Science and Engineering, Abstr. Penn. St. Univ., Pennsylvania, (1993).

58. Ortega J.M., Rheinboldt W.C. Iterative solution of nonlinear equations in several variables // Academic Press, New York, (1970).

59. Prothero A., Robinson A. The stability and accuracy of one-step methods // Math. Comp., (1974). V. 28. pp. 145-162.

60. Rannacher R. A domain decomposition algorithm for parabolic problems // The Summer Conference on Domain Decomposition in Lambrecht (Germany), Abstr. Das Zentrum fur Practische Mathematik wird gefordert von der Volkswagen-Stiftung, (1991).

61. Rektorys K. The method of discretization in time and partial differential equations // D. Reidel Publ. Co., Dordrecht-Holland, Boston-USA, (1982).

62. Wheeler M.F. A priori X2 estimates for Galerkin approximations to parabolic partial differential equations // SIAM J. Numer. Anal., (1973). V. 10, No. 4. pp. 723-759.