Методы декомпозиции для решения некоторых параболических задач

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

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

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

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

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

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

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.