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

• Быченков, Юрий Владимирович
• кандидат физико-математических наук
• 2003

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

Введение

1 Линейные симметричные системы

§1.1 Постановки задач оптимизации

• §1.2 Оптимизация алгоритма в классе К.

§1.3 Свойства некоторых классов функций.

§1.4 Оптимизация алгоритма в классе Ki

§1.5 Оптимизация алгоритма в классе К

§1.6 Оптимизация алгоритма для нерегулярных задач

2 Системы типа Навье-Стокса

§2.1 Постановка задачи.

§2.2 Оценки скорости сходимости алгоритма.

3 Системы с сильно монотонной нелинейной частью

§3.1 Постановка задачи.

§3.2 Оценки скорости сходимости.

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

Одной из простейших математических моделей динамики жидкости является модель стационарного течения вязкой однородной несжимаемой жидкости в объеме (области) Q С Кп (п = 2,3), которая описывается следующей системой уравнений в безразмерной форме где / : Q —W1 - заданное отображение (вектор постоянных внешних массовых сил). Долгое время эта система оставалась за рамками строгого математического изучения, что тем не менее, не мешало эффективно использовать её для исследования в приложениях. Однако, в 60-х годах прошлого века, благодаря выдающимся трудам О.А. Ладыженской, был найден подход к математическому исследованию этой крайне сложной с математической точки зрения проблемы. В работах О.А. Ладыженской была впервые указана и обоснована корректная постановка задачи (1) (см. [22] и цитированные в ней ссылки). Дальнейшее развитие теории и, в особенности, методов численного решения задач (1) и ей подобных выявило тот факт, что существенную роль для теорем существования и необходимым условием сходимости многих алгоритмов играет, так называемое, условие -v Ай + (и • V)u + Vp = /, xGQ, divu = 0, x 6 < й = 0, х едП,

1)

Ладыженской-Бабушки-Брецци (ЛББ-условие) и его дискретные аналоги, имеющее вид

7|ИК sup {P\.d™U) VpGL2(Q)/R, (2) 0^е(я01(О))тг INIi где Hq(Q) = Wj^) - пространство Соболева, || -1|2 - норма в этом пространстве, || || - норма в а константа 7 > 0 зависит только от области Q.

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

Uw + вР = /

В и = д где А(и) = —i/Aqu+N(u)u, В - дискретные аналоги операторов —ь>/\й+(й • V)it + - divit • й, grad, a U Э и, Р Эр - конечномерные аппроксимации пространств (Я(}(0))п и при этом {A(u)v,v) ^ 0, u,v е U.

Такие системы уравнений относятся к классу, так называемых, задач с седловыми операторами, наиболее общая форма которых где А(и) и С(р) - абстрактные локально монотонные операторы в соответствующих евклидовых пространствах. Системы вида Bp = f

- С(р) = 9

4)

4) довольно часто возникают в приложениях: кроме численного решения задач механики вязкой жидкости ещё и в теории зовании смешанных аппроксимаций эллиптических уравнений, в методах декомпозиции и др. ([14], [45], [37], [33], [27]) При этом главенствующую роль для теоретического анализа все таки играют системы вида (3), исследованию алгоритмов решения которых и посвящена данная работа.

К настоящему времени, предложено немалое количество эффективных алгоритмов для решения задач подобного вида (см., * например, [33], [14], [34], [15], [28] и цитированную в них литературу). Среди самых простых можно выделить обобщенный итерационный алгоритм Эрроу-Гурвица (оригинальный алгоритм (Q = I) впервые появился в [33]) где Q : U —>• U - положительно определенный самосопряженный оператор в U. Алгоритмы такого типа до сих пор не потеряли свою привлекательность, что связано с простотой их реализации и минимальными требованиями к объему памяти. Особенно стоит подчеркнуть, что в случае линейных симметричных сед-ловых задач, предельные характеристики эффективности этого алгоритма (Q = А, г - "оптимальные") по порядку не уступают многим другим, более сложным алгоритмам [28].

После своего появления, алгоритм (5) неоднократно подвергался различным модификациям и обобщениям. Так в работе [43] в алгоритм (5) (в контексте задачи Стокса), по-видимому впервые, было введено дополнительное слагаемое XBB*uk, А > упругости, в математическом программировании, при исполь

5)

О в следующем виде

7/^+1 qjk

Q- + А(ик) + \ВВ*ик + Врк =f + \Bg

-/3 (pk+1 - рк) + В* uk+1 = д

6) однако, судя по всему, этой модификации автором не придавалось большое значение (величина Л считалась фиксированной константой). В отечественной литературе подобное слагаемое было введено Г.М. Кобельковым в [16]. В этой работе (для решения задачи Навье-Стокса) был построен алгоритм следующего вида к+1 к

Q--— + А(ик) + f3'lBB*uk + В рк =f + /3~1Bg

-Р (;рк+1 - рк) + В* uk+1 = д

7) но, что самое главное, впервые была подчеркнута особая роль слагаемого j3~lBB*uk в ускорении сходимости алгоритма, что подтвердилось для нелинейных задач результатами численных экспериментов.

Дальнейшее обобщение этих идей приводит к следующему алгоритму, который является основным объектом исследования этой работы: к-\-1 к

QU ~U + (А(ик) + f3BC~lB*uk) + В рк = / + ($В С~1д -а С (рк+1 - рк) + В* ик+1 = д

8)

Здесь Q : U —> U, С : Р —»• Р - положительно определенные самосопряженные операторы, a>0,r>0,/3eR - итерационные параметры, и0 £ Q, р° £ Р - начальные приближения. Основной особенностью этого алгоритма является наличие трех независимых итерационных параметров. Еще раз отметим, что частным случаем этого алгоритма являются алгоритмы Эрроу-Гурвица (/3 = О, С = I) и Кобелькова (/3 = а-1, С = /), a таьсже модифицированный метод верхней релаксации (MSOR) в случае незнакоопределенной симметричной матрицы [55].

Расширение класса решаемых задач приводит к дальнейшему обобщению алгоритма. Так для решения линейных задач с вырожденным оператором А в работе рассматривается четы-рехпараметрическая модификация алгоритма Q иМ~ +(Avuk + /3BC-1B*uk) + В pk = f (9) -аС (рш - pk) + В* uk+1 = д где Av = А + vBC~xB\ f = f + ((3 + и)В C~lg. Особенность этого алгоритма заключается в том, что четвертый параметр ь> > О входит в постановку задачи оптимизации, поэтому не может быть явно исключен из алгоритма.

Исследованию алгоритмов из класса (8) (в основном алгоритму Эрроу-Гурвица (/3 = 0)) посвящено немалое количество работ. Кроме исследования свойств сходимости алгоритма в таких работах как [33], [27], [43], [16], существует множество работ связанных с оптимизацией скорости сходимости, большинство которых относится к случаю линейных симметричных задач. Рассмотрим подробнее этот класс задач. Во многих случаях в качестве дополнительной информации к постановке задачи оптимизации авторы предполагают, что выполнены неравенства

7С < В*А~гВ ^ ГС, SQ^A^AQ, (10) первое из которых является аналогом ЛББ-условия (2) для задачи Навье-Стокса, а последние связаны с задачей построения эффективных предобуславливателей для оператора А (оператор Лапласа в задаче Стокса), кроме того, иногда используется альтернативная постановка

5Q^A^AQ. (11)

Отметим, что в случае S = А обе постановки эквивалентны. По видимому, пионерской работой в области оптимизации (8) является работа [51], в которой для специальной нормы ошибки приближения на к-ой итерации алгоритма получена специальная оценка вида ^ ot)eо и найдено оптимальное значение go = min а), которое удовлетворяет неравенству а,т> О

Яо К \J 1 - Coptic2 < 1 - ^ 1/8 < Copt < 1, где а; = <$/Д, £ = 7/Г.

В дальнейшем этот результат был улучшен в работе [35] и получен показатель скорости сходимости q = I ((1 - Qu + " О2"2 + 4(1 - ы)) < 1 - ^ а*.

Позднее эта оценка была уточнена в [56], но без качественного улучшения показателя.

Существенно иной подход был предложен в работе [1] и получена следующая асимптотика оптимального показателя

Я opt ~ 1 - 2апри £ —>• О, си у 1.

И, наконец, в работе [29] при специальных дополнительных условиях на алгоритм были получены точные формулы для оптимального показателя сходимости со следующей асимптотикой qopt ~ 1 ~ \ VC, ПРИ f 0, cj = const. у ^ — LJ

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

Теорема 1. Пусть оператор А — линейный самосопряженный положительно определенный и выполнены следующие неравенства В* А'1 В < Г С, SQ ^ А < A Q, где 0 < £ ^ Д, 0 < 7 ^ Г - фиксированные величины. Тогда задача асимптотической оптимизации алгоритма (8) имеет единственное решение

Г + 7 (l-g02)2 1-9о2

25 (2u,-l) + gg >0' А = 0, = —>0' где £ = 7/Г, и = 5/A, a qo является единственным на интервале (0,1) корнем уравнения q3 - (1 + + " 1)д + (1 - ш) = 0.

Указанная теорема дает окончательный ответ о пределах сходимости алгоритма в терминах спектрального радиуса оператора перехода. Как известно из общей теории итерационных методов, спектральный радиус оператора перехода итерационного алгоритма дает точную нижнюю и асимптотическую оценки скорости сходимости метода в терминах любой фиксированной нормы (см. [26]). Тем не менее, даже при "хороших" значениях этой величины (например, ^1/2), реальный итерационный процесс может быть неустойчив и расходиться (см., например, [2]). Такое поведение в основном обусловлено внутренней структурой оператора перехода, а именно, наличием в жордановой форме оператора клеток достаточно больших размеров. Однако, известно, что при различных естественных ограничениях на исходный алгоритм (8), оператор перехода имеет жордановы клетки ограниченного порядка. Например [29], если пространство ker В* и его ортогональное дополнение инвариантны относительно оператора Q~lA, то оператор перехода в методе имеет жордановы клетки не более чем второго порядка.

Оптимизация такого класса алгоритмов как (8) носит сложный технический и теоретический характер. Это связано с тем, что обычно получаемые в результате оценок спектра оператора перехода минимаксные задачи носят неаналитический (или очень сложный аналитический) и недифференцируемый характер, что крайне затрудняет, а часто просто делает невозможным, применение стандартных методов теории минимаксных задач. Для преодоления этих трудностей при доказательстве теоремы 1 были разработаны и исследованы специальные классы функций на прямой, а также особый аппарат доказательства. Использование этого аппарата позволило в дальнейшем получить аналогичные результаты для других задач и алгоритмов. В частности, в этой работе доказан результат аналогичный теореме 1, но для другой постановки задачи - (11), а также для задач с вырожденным А в случае алгоритма (9).

Кроме линейного алгоритма в данной работе был также исследован трехпараметрический алгоритм (8) для нелинейных задач с квадратичной нелинейностью типа Навье-Стокса и задач с сильно монотонной нелинейностью.

Диссертация состоит из введения, трех глав, приложения и заключения.

Заключение диссертации по теме «Вычислительная математика», Быченков, Юрий Владимирович

Основные результаты работы состоят в следующем:

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

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

3. Исследован случай задач с седловыми операторами типа Навье-Стокса, доказана глобальная сходимость алгоритма и получена оценка скорости сходимости и ее предельные характеристики.

4. Исследован случай задач с седловыми операторами с сильно монотонной нелинейной частью, доказана сходимость в широкой области начальных приближений и получена оценка скорости сходимости и ее предельные характеристики.

Заключение

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

1. Астраханцев Г.П. Анализ алгоритмов типа Эрроу-Гурвица. ПЖВМиМФ, 2001, том 41, № 1, с. 17 - 28.

2. Бахвалов Н.С. Численные методы М.: Наука, 1975, 632 с.

3. Бахвалов Н.С., Кобельков Г.М., Чижонков Е.В. Эффективные методы решения уравнений Навье-Стокса. Численное моделирование в аэрогидродинамике. М.: Наука, 1998, с. 37^5.

4. Борисович Ю.Г., Близняков Н.М., Израилевич Я.А., Фоменко Т.Н. Введение в топологию. М.: Наука, 1995, 416 с.

5. Быченков Ю.В. Об одном трехпараметрическом методе решения уравнений Навье-Стокса. // ЖВМ и МФ, 2002, том 42, №9, с. 1420- 1427.

6. Быченков Ю.В. Оптимизация трехпараметрических алгоритмов для решения седловых задач. // Доклады Академии Наук, 2002, том 384, №4, с. 439 441.

7. Быченков Ю.В., Чижонков Е.В. Об одном подходе к регуляризации задач с седловой точкой. // Материалы Четвертого Всероссийского семинара "Сеточные методы для краевых задач и приложения". — Казань: Изд-во Казанского мат. общества, 2002, с. 40-42.

8. Валединский В.Д., Кобельков Г.М. О разностном аналоге неравенства ||р||ь2 ^ C||grad р \\w-i. II Матер, сем. ОБМАН СССР, Препринт, Москва, 1983, №67.

9. Воеводин В.В., Кузнецов Ю.Ф. Матрицы и вычисления. М.: Наука, 1984, 320 с.

10. Годунов С.К. Современные аспекты линейной алгебры. Новосибирск: Научная книга, 1997, 390 + xxvi с.

11. Демьянов В.Ф., Малозёмов В.Н. Введение в мини-макс. М.: Наука, 1972, 368 с.

12. Дьяконов Е.Г. Минимизация вычислительной работы. Асимптотически оптимальные алгоритмы для эллиптических задач. М.: Наука, 1989.

13. Кобельков Г.М. О численных методах решения уравнений Навье-Стокса в переменных скорость давление. Вычислительные процессы и системы, вып. 8. М.: Наука, 1991, с. 204-236.

14. Кобельков Г.М. О методах решения уравнений Навье-Стокса. II Докл. АН СССР, 1978, том 243, №4, с. 843 -846.

15. Кобельков Г.М. Об эквивалентных нормировках подпространств Ь2. П Analysis Mathematica, 1977, том 3, №3, с. 177- 186.

16. Кобельков Г.М. Решение задачи о стационарной свободной конвекции. П Докл. АН СССР, 1980, том 255, №2, с. 277 282.

17. Красносельский М. А. Топологические методы в теории нелинейных интегральных уравнений. M.-JL: Госте-хиздат, 1956, 392 с.

18. Красносельский М. А., Забрейко П.П. Геометрические методы нелинейного анализа. М.: Наука, 1975, 512 с.

19. Кураев Г.Н. Задача о стационарной свободной конвекции при нелинейных граничных условиях. Л ЖВМ и МФ, 1978, том 18, №3, с. 784-789.

20. Ладыженская О.А. Математические вопросы динамики вязкой несжимаемой жидкости. М.: Наука, 1970, 288 с.

21. Ладыженская О.А., Солонников В.А. О некоторых задачах векторного анализа и обобщенных постановках краевых задач для уравнений Навье-Стокса. // Зап. науч. сем. ЛОМИ АН СССР, 1976, №59, с. 81 118.

22. Лебедев В.И. Метод сеток для уравнений типа Соболева. И Докл. АН СССР, 1956, том 114, №6, с. 1166 1169.

23. Пасконов В.М., Полежаев В.И., Чудов JI.A. Численное моделирование процессов тепло и массообмена. М.: Наука, 1984, 285 с.

24. Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 1978, 592 с.

25. Темам Р. Уравнения Навье-Стокса. М.: Мир, 1981, 408 с.

26. Чижонков Е. В. Релаксационные методы решения сед-ловых задач. М.: ИВМ РАН, 2002, 239 с.

27. Чижонков Е.В. Об одном обобщенном релаксационном методе решения линейных задач с седловым оператором. // Машем, моделирование, 2001, том 13, № 12, с. 107 114.

28. Чижонков Е.В. О сходимости алгоритма Эрроу -Гурвица для алгебраической системы типа Стокса. // Доклады Академии Наук, 1998, том 361, №5, с. 1 3.

29. Чижонков Е.В. О сходимости одного алгоритма для решения задачи Стокса. // Вестник Моск. Ун-та. Сер. 15: Вычисл. матем. и киберн., 1995, №2, с. 12-17.

30. Чижонков Е.В. К сходимости метода искусственной сжимаемости. // Вестник Моск. Ун-та. Сер. 1: Математика, механика., 1996, №2, с. 13 — 19.

31. Arrow К., Hurwicz L., Uzawa Н. Studies in Nonlinear Programming. Stanford, CA: Stanford University Press, 1958, 334 p.

32. Bramble J.H., Pasciak J.E. A preconditioning technique for indefinite systems resulting from mixed approximations of elliptic problems. // Mathematics of Computation, 1988, vol. 50, №181, p. 1 17.

33. Bramble J.H., Pasciak J.E., Vassilev A.T. Analysis of the inexact Uzawa algorithm for saddle point problems. // SIAMJ. Numer. Analys., 1997, №3, p. 1072 1092.

34. Bramble J.H., Pasciak J.E., Vassilev A.T. Inexact Uzawa algorithms for nonsymmetric saddle point problems. // Math. Сотр., 2000, vol. 69, №230, p. 667 689.

35. Brezzi F., Fortin M. Mixed and Hybrid Finite Element Methods. New York: Springer Verlag, 1991, 350 p.

36. Bychenkov Yu.V. Optimization of one class of nonsymmetrizable algorithms for saddle point problems // Russian Journal of Numerical Analysis and Mathematical Modeling, 2002, vol. 17, №6, p. 521 546.

37. Bychenkov Yu.V., Chizhonkov E.V. Optimization of one three-parameter method of solving an algebraic system of the Stokes type. // Russian Journal of Numerical Analysis and Mathematical Modeling, 1999, vol. 10, № 1, p. 33 40.

38. Chizhonkov E.V. On Solving an Algebraic System of Stokes Type under Block Diagonal Preconditioning. // Сотр. Math, and Math. Physics., 2001, vol. 41, №4, p. 514 521.

39. Clarke F.H. Optimization and Nonsmooth Analysis. New York: Wiley, 1983, 308 p.

40. Crouzeix M. Etude d'une methode de linearisation. Resolution numberique des equations de Stokes stationnaires. Application aux equations de Navier-Stokes stationnaires. // IRIA, 1974, № 12, p. 141 244.

41. Crouzeix M., Ravi art P. A. Conforming and nonconforming finite element methods for solving the stationary Stokes equations. // R.A.I.R.O., 1973, №R-3, p. 77 104.

42. D'yakonov E. G. Optimization in solving elliptic problems. New York: CRC Press, 1996, 562 p.

43. Elman H., Silvester D. Fast nonsymmetric iterations and preconditioning for Navier-Stokes equations. // SIAM J. Sci. Copmut., 1996, vol. 17, p. 33 46.

44. Golub G.H., Wathen A.J. An iteration for indefinite systems and its application to the Navier-Stokes equations. // SIAM J. Sci. Comput., 1998, vol. 19, №2, p. 530 539.

45. Hackbusch W. Multi-Grid Methods and Applications. Berlin-Heidelberg: Springer-Verlag, 1985, 377 + xiv p.

46. Queck W. The convergence factor of preconditioned algorithms of the Arrow-Hurwicz type. // SI AM J. Sci. Copmut., 1989, №4, p. 1016 1030.

47. Rannacher R., Turek S. A simple nonconforming quadrilateral Stokes element. // Numer. Meth. Part. Diff. Equ., 1992, №8, p. 97-111.

48. Turek S. Efficient Solvers for Incompressible Flow Problems: An Algorithmic and Computational Approach. Springer Verlag, 1999, 310 p.

49. Xiaojun Chen. On preconditioned Uzawa methods and SOR methods for saddle-point problems. // J. of Сотр. and Appl. Math., 1998, № 100, p. 207 224.

50. Young d.m. Iterative Solution of Large Linear Systems. New York: Academic Press, 1971.

51. Zulehner W. Analysis of iterative methods for saddle point problems: a unified approach. // Math. Сотр., 2002, vol. 71, №238, p. 479-505.

52. Finite Element Analysis Tool (FEATFLOW).http://www.feat/low. de.