Асимптотически оптимальные алгоритмы для эллиптических задач тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

0.1

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М. В. ЛОМОНОСОВА

Факультет вычислительной математики и кибернетики

На правах рукописи

ДЬЯКОНОВ Евгений Георгиевич

АСИМПТОТИЧЕСКИ ОПТИМАЛЬНЫЕ АЛГОРИТМЫ ДЛЯ ЭЛЛИПТИЧЕСКИХ ЗАДАЧ

Специальность: 01.01.07—вычислительная математика

АВТОРЕФЕРАТ

диссертации па соискание ученой степени доктора физико-математических наук

Москва 1993

Работа выполнена в Московском государственном университете им. М. В. Ломоносова.

Официальные оппоненты:

доктор физико-математических наук, профессор А. В. ГУЛИН

доктор физико-математических паук, профессор 10. А. ДУБИНСКИЙ

доктор физико-математических наук, профессор В. С. РЯБЕНЬКИЙ

Ведущее предприятие: ИВМ РАН.

с, _ г-%0

'Защита состоится .......»............199'*/ г. в./.*?.......ад-

сов на заседании специализированного совета Д 053.05.37 при факультете вычислительной математики и кибернетики МГУ им. М. В. Ломоносова.

Адрес: 119899, г. Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМиК МГУ, ауд. 685.

Автореферат разослан ......................199^ г.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ им. М. В. Ломоносова.

Ученый секретарь специализированного совета

Е. И. МОИСЕЕВ

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Минимизация вычислительной работы при решении эллиптических задач, к которым относятся краевые и спектральные задачи с сильно эллиптическими операторами, является одной из важнейших задач вычислительной математики. Она имеет и сильное идейное родство с классическими задачами оптимизации в теории аппроксимации функций и построения формул численного интегрирования. Четкая постановка этих задач и успехи в их решении прежде всего связаны с именами А.Н.Колмогорова, С.М.Никольского, С.Л.Соболева, Н.С.Бахвалова. Полученные ими результаты, а та1йке первые успехи в построении асимптотически оптимальных вычислительных алгоритмов для решения разностных систем И задачи Дирихле для гармонического уравнения, привели в начале 60-х годов К постановке задачи асимптотической минимизации вычислительной работы при решении с точностью £ задачи из класса эллиптических задач, решения которых образуют компакт в рассматриваемом пространстве Соболева, и появлению гипотезы Колмогорова-Бахралова о том, что логарифм оптимальной асимптотики должен быть эквивалентен е-энтропии этого компакта.

Особая роль ПСМ (проекпионно-сеточных методов) в решении этой задачи делает более естественным вместо е-энтропии использовать ]У(е)-попе-речннх в смысле Колмогорова данного компакта, как это было предложено в 1965г. в известной статье И.Бабушки и С.Л.Соболева. Более точно, пусть е > 0-нужная нам точность приближения к искомому решению и известна асимптотика ЛГ(€)-поперечника упомянутого компакта. Тогда построение вычислительных алгоритмов, приводящих к нужным е -аппроксимациям при выполнении И^е) арифметических действий (операций), где

\У{е)хЩе), (1)

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

проблемы и результатов, направленных на ее решение, является общепризнанной.

Именно асимтотически оптимальные алгоритмы с асимптотикой (1), а также почти асимтотически оптимальные алгоритмы с несколько худшей асимптотикой

1У(е) = 0(ЛГ(£)|Ье|г), г >0 • (2)

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

Цель работы. Целью работы было выяснить возможно ли получение алгоритмов с характеристиками типа (1) или (2) при специальных и весьма естественных выборах компактов, связанных с предположениями некоторой избыточной гладкости решения в терминах пространств Соболева— Слобояецкого = И'2т+Т(П), т — [т] > 1,0 < 7 < 1 или эквивалент-

ных им пространств Бесова (подобные предположения, по крайней мере для целых т + 7, стали стандартными в теории сеточных методов с конца 60-х годов). Более точно, пусть исходная линейная краевая задача для эллиптического уравнения 2-го порядка ставится в ограниченной области й С Я' с липшицевой кусочно гладкой границей Г и может рассматриваться как корректное операторное уравнение . '

1ы = / (3)

в гильбертовом пространстве С С '^'(П) =

С'1*. Пусть для его решения

известно, что

Ц«||т+7,П < К, т = [т] > 1,0 < 7 < 1. (4)

Тогда это неравенство определяет компакт в й и X е, где и = т + 7 — 1. Поэтому (2) переходит в

ИЧб)< Яе-^ЧЬеГ (5)

(условимся иногда обозначать разные константы одной и той же буквой). Другой важный выбор связан с разбиением й на блоки Пь..., и условиями

N11+./,П. < К., 8 = 1,...,р. (6)

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

, «(*) = £ <***(*) + «„(*), Ы*) е ^+"(П), о < 4 (7) *=1

с известными сингулярными функциями Хк(х), но неизвестными коэффициентами с ¡с. Для «0(1) возможны также условия (6).

Для систем эллиптического типа, имеющих дело с неизвестными вектор-функциями и = [«1,,.., и*], соответствующие условия имеют вид

. Мик 0, / = 1,. (8)

Для систем типа Стокса и Навье—Стохса' аналогичные условия па вектор скорости Й з [«1,..., и давление р принимают вид

М|1+».п. < < К, в = = 0 < ^ < 1. (9)

Для спектральных задач

£,« = А Мм (10)

с сильно эллиптическими операторами 2-го порядка £ £ С* (в) п подчиненными им операторами М = А/* > 0 0-го или 1-го порядков, сводимых к спектральным задачам Аи = «и с А = 1/в в гильбертовом пространстве с симметричными, положительными а компактными операторами А, целью служат алгоритмы отыскания (с точностью е5) нескольких младших собственных чисел А и соответствующих им собственных подпространств (с точностью (), требующие вычислительной работы с оценками (5), если

для элементов некоторых ортонормированных базисов этих подпространств выполнены условия типа (4), (6), (7).

Наконец, для двумерных задач связанных, например, с эллиптическими уравнениями 4-го порядка была интересна проблема построения вычислительных алгоритмов, приводящих к нужным «-аппроксимациям (в про-странстах и ИЛ®(Г2) для соответственно первых и вторых производ-

ных решения и € И/25+"(П), 0 < V < 1) и характеризуемых оценками (5). Подобная постановка объясняется тем, что изучались методы сведения данных краевых задач к соответствующим задачам для систем 2-го порядка с ограниченим сИу и = 0.

Таким образом, можно сказать, что главной целью для всех указанных типов эллиптических задач было построение вычислительных алгоритмов, приводящих к нужным «-аппроксимациям и требующих выполнения IV(е) арифметических действий с оценками (5), в которых случай г = 0 соответствует асимтотически оптимальным алгоритмам, а случаи г = 1 а г = 2 соответствуют почти асимтотически оптимальным алгоритмам.

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

Методическая характеристика работы. Методика построения асимптотически оптимальных вычислительных алгоритмов может быть еще более четко описана на основе выделения трех этапов, требовавших:

1. выбора асимтотически оптимального по точности сеточного метода;

2. построения асимтотически оптимального итерационного метода для приближенного решения возникающих сеточных систем;

3. применения многосеточного ускорения для построенного базисного оптимального итерационного метода.

Первый этап, в случае и < 1, основан на использовании сг-мейства квазиравномерных триангуляции (симплексных сеток) Гь(Пд) топологически эквивалентных триангуляция» Ть(С}) для некоторых модельных замкпу-

тых областей Q (ячейками последних служат симплексы, являющиеся регулярными частями кубов с длиной стороны Л). Здесь = П, если Í) состоит из конечного числа симплексои, а в общем случае Пд есть 0{h2)-аппрохсимадая для Ü (граница Па; обозначаемая через Г л н Г, принадлежит 0(Л2)-окрестности границы ÍÍ, обозначаемой через Г). Более точно, участок границы Го, соответствующий однородным условиям Дирихле, предполагается принадлежащим Q, а оставшийся-проходящим вне области П, что позволяет придать смысл щ - «, где йн € ^'(Q/,; Го) есть решение по'лучаемое в ЦСМ, связанным с рассматриваемой триангуляцией а« £ G = WjKíljTo) есть решение исходой задачи для эллиптического уравнения. Конечно, вопрос о возможности построения нужной триангуляции не является простым, и исследовался отдельно. Сам ПСМ использовал подпространство Gh = И^О^Го), образованное непрерывными на Па н кусочно линейными на 7Х(Пд) функциями (он является естественным обобщением классического метода Куранта для двумерных задач). В случае (7) в его базис дополнительно включались сингулярные функции хЦя), что предлагалось и ранее в простейших ситуациях (Fix G., Babushka I.).

Тогда ПСМ мог считаться асимтотически оптимальным по точности, если он приводил к корректым дискретным задачам и к оценке погрешности

J1«A — «л < (11)

где константа Л*о определяется константами из условий (4), (6), а в случае (7)-(9)-ап алогичными константами для щ(х). В некоторых простейших случаях подобные оценки установлены и для разностных методов.

Если имеет место (4) и П а = Ü, то оценки (11) ci/ = m + 7~-l верны, если на каждом симплексе из Га(Оа) элементы из Gh являются интерполяционными полиномами Лагранжа, в общем случае, степени т' > т (для общих областей возможно использование Евазитриангуляций). . Прп получении (11) (для уравнения и систем, линейных и нелинейных) были существенны как обобщения априорных оценок погрешности проекционных методов, например, для корректных задач (3), так и вопросы аппроксимации в пространствах Соболева.

Особый интерес представляют оценки погрешности (11) cus [ц;р] и ¿A s («а; Ра), применимые для двумерных и трехмерных краевых задач Дирихле для систем тппа Стохса и Навье—Стокса в ограниченной области с диншицевой кусочно гладкой грацицей, а также для родственных задач с ограничением

div w - ар = 0, (12)

где а-малый положительный параметр (такие задачи встречаются не только в гидродинамике, но и в теории упругости). Важной методической особенностью является рассмотрение краевой задачи как корректного операторного уравнения с седловым оператором в гильбертовом пространстве G — G1 х <?2, где

(^(^'(«»"'.CiSGiXl, (13)

G\ = ¿2(П),С2 \ 1 = {р : р € Ь2(О); (р, 1)0,« = 0}

и неизвестными функциями служат ы'= Uj = [ui(i;... \Щ,л]т € G\ и р s u2 6 (?2, a d = 2 или d = 3. Если эта задача аппроксимируется ПСМ с подпространствами G = G\ х G2, где Gj С Gi,G2 С Gi, и й = [Mi,ti2JT € G*', то, как это известно с начала 70-х годов для задач с а = 0 в (11), исключительно важен и* выбор, приводящий к неравенству

sup > <ТьЫо,п, cro>0, Vp 6 G2 (14)

ueG, IMIc.

с константой его, не зависящей от Л. При этом оставались проблемы справедливости (14) даже для двумерных невыпуклых областей с углами и наиболее простого выбора такой пары подпространств. Сами оценки (И) были получены довольно сложным образом лишь при v — 1, и их вывод при а > 0 был неизасстсн.

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

Наконец, для спектральных задач (10) применялись ПСМ того гке типа, что и для (3). Характерно, что аппроксимация собственных пидпро-страиств последовательно характеризовалась при помощи понятия раствора подпространств, введенного М.А.Красносельским и М.Г.Крейяом.

Перейдем теперь к характеристике 2-го этапа, связанного г построением . базисного оптимального итерационного метода. Начнем с рассмотрения

линейных и нелинейных эллиптических сеточных систем

¿л«Л = /Л (15),

в которых вектор ац = к = [мь... является элементом евклидова

пространства И = Н^ и образован из коэффициентов разложения й Е бн

по выбранному базису ф\(х),..., фн(х) подпространства С!/,. Отметим, что

(16)

Поэтому, если будет построен итерационный процеср, за одну итерацию (за фиксированное число итераций) уменьшающий разумно выбранную норму (она должна быть согласована с нормой в (5/,) ошибки в конечное число раз, независящее от сетки, и такой, что вычислительная работа на каждой итерации оценивается как IV = 0(7/), то получение нужной е-аппроксимации к решению (15) (тем самым, н к й) потребует затраты

^) = 0(^|Ье|) = 0(М) 4 (17)

арифмртцлеашх действий. В ряде случаев нужный оптимальный итерационный процесс получается довольно простой модификацией какого-нибудь классического итерационного метода. Например, для линейных задач с — > 0 (что тоже, с € £+(Н)) плодотворна концепция спектральной эквивалентности сеточного модельного оператора В/, £ С(Н) и исходного сеточного оператора Ь^, применяемая автором с начала 60-х годов. Для несимметричных операторов ее обобщения связаны с соответствующей симметризацией исходной линейной сеточной системы и оказались весьма оффехтшзнымн и для сеточных систем тппа Стокса. Для нелинейных задач удалось изучить лишь модификации классического метода простой итерации я пекоторых градиентных методов. Особо выделяется проблема шучепля модифицированных градиентных методов отыскания нескольких младших 'собственных чисел для получаемых сеточных спектральных задач

= ЛьМа«Ь. (18)

Здесь опять же ключевую роль играет задача построения модельного оператора В/, £ £+(Я) спектрально эквивалентного оператору значительные трудности вызывает также задача учета эффекта приближенного заданна ' проектора па подространство уже найденных собственных векторов.

Наконец, чтобы в оценках (17) убрать лишний множитель |1п«|, при-15епялась классическая пдея метода продолжения по параметру, основой

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

Возвращаясь к менее трудной проблеме построения почти асимтотиче-ски оптимальных алгоритмов с оценками (5), мы можем или вообще обойтись без применения Многосеточпого ускорения, ограничившись оценками (17), или даже применять базисные итерационные методы, приводящие к оценкам

Н'(е)<#е-,'/,'|Мн-,| (19)

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

)У = 0(Щ1п Я)*), « = 1,3 = 2 (20)

арифметических действий.

Научная новпзпа п практическая капкость работы. Диссертация является научной монографией к основана на исследованиях автора, результаты которых были опубликованы за период с 1961 г. по 1988 г.. Основные результаты (они указаны отдельно) па момент публикации были новыми и, в целом, дают подтвержден»? усиленного варианта гипотезы Колмогорова -Бахвалова для достаточно широкого круга эллиптических двумерных к многомерных задач. Номш?» некоторых результатоз была "подчеркнута в:>гшс при описании вргшеияемой методики репепяя указанной фундаментальной математической проблемы. В то же время следует отмстить, что отдельные и бодае частные темы были и остаются в центре

внимания многих исследователей. Подобные наиболее близкие результаты упомянуты ниже при изложении содержания работы, а ссылки на более отдаленные могут быть найдены о самом тексте книги (список литературы d ней содержит около 320 работ). Ряд относительно новых и важных - публикаций указан в статьях {2] u [3j.

Практическая ценность предложенных и родственных алгоритмов в пла-ие их применения при решении прикладных задач частично отмечена выше. Укажем дополнительно только несколько подобных задач из теории оболочек и теории упругости, в решении которых .автор или принимал непосредственное' участие или, по крайней мере, консультировал по поводу предложенных им методов. Наиболее длительное сотрудничество имело место с ВЦ НИИ шинной промышленности (с начала 60-х годов). Решавшиеся там системы сетчатых оболочек (линейные и геометрически нелинейные) соответствовали в некоторых случмх снльноэллиптическим системам в смысле Нирецберга 4-го порядка и позволяли нсполь-тйать почти ортогональные сетки на поверхности оболочки, тоцологпческл эквивалентные прямоугольным. Это делало, версвектшшым npnueircmu; рмиостных иетодод и двухступенчатых итерационных методов с модельным оператором, спектрально эквивалентным или исходному сеточному оператору /,<, пли его линеаризации, Составленные программы начали применяться для .расчета автомобильных шин с середины 60-х годов, а позднее, при их соответствующей модификации, Я для расчета авиационных шин, в том числа я специальных шин для "Бургша" (Н.К.Николаеп, начало 80-х годов). Конкретные сильнонелинешще B-гриацпошше неравенства (задачи с препятствиями) при их решении требозолд работы примерно с 50 тысячами неизвестных. Ряд родственных расчетов для упруго-пластических оболочек успешно провел Н.Н.Столяров (СамарскийПолитехнический Институт, 80-ые годы). Специальный класс двумерных и трехмерных задач теории упругости , связанных с кслшозитаыцп материалами и сложными геометриями области, эффективно решался и решается па кафедре теории композитов (МГУ) под общим руководством Е.Е.Побэдрп.

Апробация работы. Основные положения п результаты неоднократно докладывались п обсуждались на научных семинарах, например:

» МГУ им. М.В.ЛомоносОза (под руководством: Бахвалова Н.С.; Ильина В.А. п Бицадзе A.B.; Идыощипа A.A. я Победри Б.Е.; Олейггаа O.A.; Тпхоноза А.Н. и Самарского A.A.);

; »в МИ РАН им. В.А.Стекиоэа (под, руководством Бесова О.В., Кудряв-

цсва Л.Д., Никольского С.М. и Соболева C.J1.;)

• ИВМ РАН (под руководством: Марчука Г.И; Бахвалова Н.С. и Лебедева В.И.);

• ИПМ РАН им. М.В.Келдыша (под руководством: Бабенко К.И.; Рябенького B.C. и Федоренко Р.П.);

• ЛОМИ РАН им. В.А.Стеклова (под руководством Ильина В.П., Мих-липа С.Г. и Фаддсева Д.К.); •

• ВЦ СО РАН (под руководством Марчука Г.И.);

• МЭИ (под руководством Дубинского Ю.А.).

Многие результаты излагались также в курсах лекций, читавшихся автором для преподавателей, сотрудников, аспирантов и студентов старших курсов по прилашениям ряда университетов Болгарии, Великобритании, Литвы, Польши, США, Чехословакии, Украины.

Им же были посвящены доклады автора на ряде научных конференций и школ. Например, среди проводившихся в последние 10 лет можно назвать:

• Пктуго Всесоюзную конференцию "Вариационно-разностные методы в математической физике"(1983, Москва);

• Международную конференцию по дифференциальным уравнениям с. частными производными (1983, Новосибирск);

• Пятую Всесоюзную школу "Теоретические основы и конструирование численных алгоритмов .решеипя задач математической физики" (1984, Казань);

• Седьмую Всесоюзную конференцию "Вычислительные методы линейной алгебры" (1985, Москва);

« Первую Всесоюзную конференцию "Современные проблемы численного анализа" (1986, Москва);

в Семинар им. И.Г.Петровского и заседание ММО (1987, Москва);

• Вторую Всесоюзную конференцию "Современные проблемы численного' анализа" (19S9, Тбилиси);

• Четвертую Международную конференцию по дифференциальным уравнениям и методам их решения (1989, Русе, Болгария);

• Пятую Международную конференцию по методам декомпозиции области для уравнений в частных производных (1990, Москва);

в Международную конференцию "Современные проблемы численного анализа" (1992, Москва);

• Шестую Международную конференцию "Многосеточные методы" (1993, Коппер Маунтинз, США).

Структурой объем работы. Диссертация явлдется научной монографией. Состоит из предисловия, введения, 9 глав, списка основных обозначений, списка литературы, содержащего около 320 наименований, и предметного указателя. Объем диссерташсн до цитированной литературы 250 страниц.

СОДЕРЖАНИЕ РАБОТЫ-

Предисловие посвевдено актуальности проблемы, самому общему описанию полученных результатов и структуры монографии. С целью сделать монографию доступной для более широкого круга читателей в цей Имеется несколько параграфов, дающих необходимую и сжатую вводную Ииф9рмадщо. Такими частично служат 2 первых параграфа введения (параграфы 01 и 02), а также параграфы 21, 31, 33, 41, 91. С этой же целью введение содержит ряд важных, но наиболее просто получаемых результатов, служащих ориентирами для последующих более сложных построении. Так, например, в § 02 подчеркивается взаимосвязь ПСМ и разностных методов для двумерных задач. Важнейшее для всей работы понятие спектральной эквиазлеитностп сеточных операторов определяется в § 03 (оно было введено автором в 1965г., но фактически использовалось при построении итерационных алгоритмов с оценками (20) для решения разностных систем в его публикациях в 1961, и 1964 г.). Здесь асе и в § 04 подчеркиваете« его рояьпрн построении итерационных методов, сходящихся для суточных систем со скоростью, не зависящей от сетки, а также pro идейное родство с соответствующими понятиями из классических работ К.Фридрихса, Л .В.Канторовича, С.Г.Махлина. Особенно четко это родство проявляется для сеточных орераторов соответствущих адшроки-мациам Релея—Ритца для операторов L ^ C+(G) и фактически являющихся последовательностью матриц Гр&ца Li, выбранных базисов евклидовых

пространств V = V/, и отличающихся от Он лишь скалярным произведением порожденным оператором Ь. Тогда ¿л и Л = спектрально эквивалентны, а всякий оператор Б/, = В, спектрально эквивалентный оператору ¿а, порождает евклидово пространство Н(В) со скалярпым произведением (и, у)в з (Ви, у)ц — (Ви, у) й нормой согласованной с. нормой. С/, (нормы ||и||в и ||«||у = ||«|| эквивалентны равномерно по Л). Таким обра- . зом, в классе норм, согласованных с нормой в 6ь, нас интересуют только такие |[и||в, что системы

Ву = д (21)

(условимся опускать индекс сетки) для каждого заданного # могут быть решены (при отсутствии ошибок округления) алгоритмами с оценками

И' = О(Л') (22)

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

В«п+1 = Вип - гп(1»п -/), • (23)

поскольку скорость сходимости ее определяется константами (точсс, их отношением) из неравенств

6о(Вч,ь) < (Ь,1/) < ЦВи.и),. У».еЯ,$о>о' (24)

и из их следствия яр (В~гЬ) С [¿о, 5||. В § 04 показывается также, следуя статье автора от 1971г., справедливость неравенств типа

И^чь/уыф) < ко : (25)

и

. < Л'ь (26)

с Константами Къ и К\ не зависящими от /», как следствий проекционных аппрокс имаций обратимых операторов Ь 6 С(С) при-наличии аппроксима-шш гильбгртова пространства С последовательностью подпространств 6/, (вмгето I можно брать В): Для разностных систем неравенства типа (25), (26) применяются с середины 60-х годов; например, в статье автора от 1965 г. пм соответствовали условия '

йо|М1в<ИИ1в-.<*||М1в. УгеЯЛ>0;. ; (27)

их выполнимость, как следствий корректности исходной задачи, была показана им р конце 60-х годор. Важности подобных неравенств в теории разностных схем была подчеркнута А.А.Самарским (1966 г.); они могут быть также связаны с целым рядом более ранних работ (Ладыженская O.A., Лебедев В.И., Самарский A.A. и Тихонов А.Н. и др.) по исследованию разностных схем для эллиптических задач.

Простой и очену удобный критерий спектральной эквивалентности се-топных операторов, связанных с топологически эквивалентными триангу-ЯЯЯИЯМИ И кусочно дарейвыми функциями, дан в конце § 04, следуя статье автора от 1976'г.. *

Последний параграф посвящен оценкам поперечников типа (6) и основан на статье автора от 1978г. Наиболее близкая методика применялась ранее в частном случае Л.О.Оганесяном й Л.А.Руховцем.

Глава 1 посвящена некоторым общим вопросам теории численных,методов для операторных уравнений (линейных и нелинейных) в гильбертбвом Пространстве.' Дредложенная автором в 1971 г. (см. также более позднюю книгуР.Темама) схема исследования сходимости объединяет принятые в .теории Проекционных И разностных методов и позволяет получить, напри: мер, ряд полезных априорных оценок погрешности проекционных методов, приводимых В § 11. Они Могут рассматриваться как некоторое обобщение классических результатов (Канторович Л.В., Красносельский М.А., Мих-ЛИн С.Г:, Babushka I., pea J., Varga R. и др.)

: В § 12 приводятся, следуя статьяк автора от 1965-1971 г.г., некоторые априорные оценки решений и лопаточные условия корректности дискретных задач, связанные со многими классическими результатами из теории Монотонных шёраторов (Вайнберг М.М., В шпик М.Г., Лубинский Ю.А. и др.), а также с исследованиями корректности разностных схем (Ляш-Ко А'Д., Ривкинд В.Я. и Уральцева H.H., Рябенький B.C. и Филиппов А.Ф., Самарский Д.Д. й ¡Тихонов Д.Н.. и др.). Ряд приводимых теорем использует не монотонность оператора, а обратимость его главной части и соответствует классической теореме о возмущении обратимого оператора.

Итерационные методы с модельными симметричными операторами для CBCTétí уравнений. (операторных уравнений в евклидовом пространстве) *в4»ются объектом анализа в § 13 (приводимые результаты основаны на публикациях автора (l96Í-1987r.г.). Отметим, что общим вопросам сходимости итерационных методов посвящено огромное количество работ (Кан-¡торовчч Л.В., Кодаелев А.И., Марчук Г.И. и Кузнецов Ю.А., Марчук Г.И.

и Лебедев В.И., Самарский A.A. и Николаев Б.С., Axelson О., Gunn J., Hestenes М., Petryshyn W., Wachpress E. и др.). Сеточные системы для нелинейпых задач с локализацией имеют вид

ЬаЫ =/А. riH&Sh. (28)

Здесь и/, и Д—элементы евхлидова пространства Пк\ в дальнейшем индекс h не указывается и предполагается корректность (28).'

Для модельного оператора В £ £+(#) рассматривается Модифицированный метод простой итерации

Bun+l = Вип — r(L(un) — /) (29)

Его сходимость исследуется в евклидовом пространстве Н(В) с условиями на L в замкнутых шарах Sy{u) г) г £?, радиуса г > 0 и с использованием неотрицательных на [0, rj функций £*(<), ст*(<) (невозрастающих при к а О и неубывающих при к > 1); их минимальные (при к — 0) и соответсвенно максимальные значения обозначаются через 6k,at,k = 0,1 я предполагается, что 50 > 0, "о > 0 и что S С 5'г. Используются либо условия типа (для всех и 4- z G Sr) .

(L(u-f-i) — L{u),z) > .£о(||г||в)||2||я>

||L(tt + i)-"i(«)|||., < 5.(1!4Р)||г|||,, ;

либо более детальные, (для дифференцируемых на Sr операторов) типа

*о(!ИЫ1И!2в.< < *»<В*11в)№

с любыми г'; операторы (L'„+J), п (L^j.,)« соответстпуют симметрической и антисимметрической части производной неходкого оператора. Тогда уста- . навлипастся сходимость метода со скоростью геометрической прогрессии, если и0 £ 5, п положительное т достаточно мало, при этом оценки при гтрсмлсшш dj к 0 переходят в говсстаые веулучшасмые.

Сходимость метода исследована и в случае еькдвдова пространства П(В7), что важно для задач с сильной велвкейностмо. Все рассмотренные случаи при дальнейших упрощениях условий приводах к сжатым операторам, .

Для oGumx линейных задач естественно нспользовать их симметризации, что вместе с конструкцией оптимальвого модельного оператора было предложено s статьях автора (1955, 1S70 г.г.). В рассматриваемом более

общем случае можно творить о переходе от линейной системы Lu — f к снмметризованной системе ,

(30)

где А = BilL'B\lL, а В, € £+(ff),r = 1,2- некоторые модельные операторы. Доказываете!, что А € С+(Н(В?)) и что

spvlc {io.ijj, $>>0, ' (31)

если L обратим и ■ " '

Для В € £+(Я) интересны 3 случая: ' •

В, = /,5а = В3; В| = = 5, = ,

совпадающие друг с другом, если L = L*, J3L = LB. Из них наиболее ва-. жен третий сАз B~lL*B_1L, приводящий к условиям (25), (26) (с J — В), которые, как уже отмечалось, часто выполняются с константами, независящими от А. Указан удобный критерий, основанный на условии jD s A—cqM, где Л = А* > О, М - М* > 0 и А(М-Ы) > А0 > 0, |A(Ai~'L)| > d > 0. Таким образом, в указанном случае применима, в частности, модификация метода Ричардсона ' .

B(un+1 - «") = -т„Ь*В-,(Ьпя - /). • • - (32) Для Пес и более общих итераций : '

V+1 - и" = -rnB^ VBjl\L{un) - f], п = 0,1, л., it - 1 '

установлена теорема сходимости с оцеакамп не только для погрешности г" ¡= и" — и, по и д.тя невязки г" = — f ~ Lzn. Это позволило также получить некоторую адаптационную процедуру для улучшения пепользу-е?шх констант <£<я Йтераццошплг метод (23) также формально содержится в ухозгхшых птераштгх я его сходимость имеет насто в евклидовых пространства:; Н(В) з й(2.); последний варяалт najxen пря применении (23) о качестве внутренних итераций.' Отметем, что близкие конструкции хггерацпошшх методоз шучглвса psspii азторо» (Астраханцеэ Г.Л., Мар-чук Г.И.,Кузнецов К>.А., Сяизрсхий А.А., Bramble J., Glowinski R.f Pasciak J. а Яр.), по не замечалась, особая роль уежвай тина (25), (26), Идея сим-нятргоациа приводят для яеливейгшх йэдэч, иапрямер, к итерациям типа

-«ч - -гсх^ув-'щ«*)- /], • * (зз)

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

Ф(и) = {Аь,ь)В} - 2(д,ь)Вг, • записываемого также как функционал невязок

Ф(^) = - /н2йг, -

При дополнительных условиях Ь — Ь' изучены итерации типа (23) с орто-гоиализацией к собственным векторам I, соответствующим \{Ь) < 0, а при £ = Ь* > Ос сНт Кег Ь > 0, следуя статье автора (1977 г.), исследованы также и варианты с В = В' > 0 и с

Кег 1= КегВф Оо, Кос В .1<2о,

где ± понимается в смысле Я.

В § 14 рассматриваются асимптотические оценки вычислительной работы при решении сеточных систем и формулируются условий, при которых построенные выше итерации приводят к алгоритмам с характеристиками типа (17), (5). Для линейных задач эти условия мотут удобно формулироваться в терминах спектральной эквивалентности (например; итерации • (32) сходятся равномерно по сетке, если Ь*В~^Ь й В спектрально эквивалентны). Обращается особое внимание на сходимость при наличии возмущений в итерационном процессе и на применимость многосеточного ускорения в случае вложенных сеток и подпространств (последнее, как уже отмечалось особо важно при построении алгоритмов с оценками (16)). Такие оценки были указаны ¿втором в 1977 г.; для отдельных случаев подобные оценки с'<1 = 2 и целыми и анализировались Астраханцевьш Г.П, и Корне-евым В.Г.. Наконец, в § 15 для стандартного ыетаДа блочного исключения (метода окаймления), применяемого к системе

: с А = А* > 0,^1,1 > 0 изучаются свойства редуцироваянойсистемы

5г(Л)и2 е 5яи2т (А3,г г Л^А^А^)^ ~д2 . (35)

с матрицей Шура ^(Л) е А/А\:\. Показано, следуя статье автора (1978 г.), что в случае Д, А^, Ла(а, являющихся матрицами Грама для базисов под: пространств (7 в <?1 х важнейшие свойства^ Л) определяются ;

16 .-Ч

углом а 6 [0, тг/2] между Gi и Gi- Следует отметить, что оценки углов между подространствами и удачные рекуррентные расщепления конечно-элементных подпространств стали в настоящее время одним из важнейших инструментов в многосеточном построении модельных спектрально эквивалентных операторов (см. [2,3] и цитированные там работы). Нашла практическое применение и оценка (1 — cosa)D < А < (1 + cosa)D с матрицей D , соответствующей блочно диагональной части A (Bank R., Mandel Y., Мс Cormick S.( Yserentant H. и др.), в особенности для составных сеток с локальными сгущениями. •

Глава 2 посвящена конструированию ПСМ и исследованию их точности для эллиптических уравнений и систем второго порядка. В § 21, в основном, кратко описываются ПСМ, основанные на использования ¿-мерных симплексных сеток, и обсуждаются вопросы использования топологически эквивалентных триангуляций. В § 22 выделяются стандартные двумерные' и трехмерные блохи, на которые можно разбивать исходную замкнутую. область и для которых возможны относительно простые отображения на симплексы и кубы. Приводимые оценки эквивалентности (стать* автора, 1978 г.) используют геометрическую информацию о блоках; обращается внимание на возможность перехода используемых оценок в неулучшаемые в частных случаях отображении (например, в опенки спектральной эквн" валентности из § 04).

■ Родственный подход используется и в § 23, имеющим дело с оценками погрешности ПСМ. Характерно, что в случае сиплексов оценки даются в терминах собственных чисел матриц Грама порожденных векторами сдвига для данного симплекса. Указывается на важность построения модельных операторов а плане получения достаточно простых и общих апостериорных оценок погрешности (более тонкие, но и более частные приемы изучались во многих работах (Babushka I., Zienkevicz О. и др.).

В § 24 показывается, следуя статьям Стрелкова H.A. (1971 г., регуляр-' ньге триангуляции) и автора (1976 г., общие триангуляции), что усреднение по всем классам регулярных триангуляций получаемых проекционно-ссточных аппроксимацпй оператора Лапласа приводит к его разностным аппроксимациям. Тем самым доказывается важная спектральная эквивалентность указанных аппроксимаций дл* —Д па простейших сетках.

Глава 3 посвящена, в основном, конкретным итерационным алгоритмам почти оптимального типа решения сеточных систем для модельных областей. В § 31 очень кратко описываются известные быстрые прямые истоды решения простейших сеточных (разностных) систем для прямоугольников

J7

и параллелепипедов. Применимость методов разделения переменных с характеристикой (20) с s — 1 и основанных на использовании БДПФ для d-мерных систем, вероятно, было впервые отмечено в статье автора (1969 г.). Отмечается возможность и простых обобщений для некоторых треугольников и призм. Методам переменных направлений поевтцен § 32. Они строятся на основе понятия расщепляющегося разностного оператора, предложенного автором в 1961 г., и включают классические Двумерные и трехмерные варианты метода ( Douglas J,, Peaceman D., Rachfoid H. и др.).'Приводимая теорема (статья автора, 1965 г.) утверждает сходимость метода в классе норм родственных норме, порожденной исходным сеточным оператором, и дает оценки типа W(f) = Û(/Vlu/V|lne|), (см, (16)) для d-мерного параллелепипеда. Интересно заметить, что конструкция более общих (расширенно расщепляющихся) сеточных операторов (1962 г,) использует фиктивные узлы, а алгоритм решения соответствующих систем использует разрезы области и метод окаймления.

В § 33 дается очень краткий обзор методов с факторизованными операторами, довольно популярными на практике, но не обладающих асимптотикой вптимального типа. Весьма важны результаты из § 34, связанные с те? орией двухступенчатых итерационных методов, поскольку именно в классе подобных методов были получены первые почти асимптотически оптимальные алгоритмы для сеточных систем достаточно общего вида (автор (1961, 1964, 1965, 1966 г.г.), Gunn J. (1964, 1965 r.r.), Wachspress E. (1963 г.)). Кроме того, более поздние результаты (автор (1969 г.), Dupont Т/(1968 г.)) оказались крайне важными элементами многих современных итерационных методов. Используемые внутренние итерации для системы Av = F с Л € JС+(#) являются модификациями методами Ричардсона типа (23) в приводят к модельным операторам . ,

В s Л(1 - Z)~l

с Z = Z\i соответствующим оператору сокращения погрешности в M внутренних итераций и симметричным в смысле С(Н(А))- Если ¡¡Л||Л < q < 1, то В б £+(Я) Я ■

(1-в)Л<Л<(1+з)В:

Подобйые модельные операторы могут использоваться в самых разнообразных внешних итерациях, например, типа (32).

В § 35 приводятся результаты статьи автора (1979), посвященной методу разрезов (декомозиции области). Анализ, в отличие от статьи Кузнецова Ю.А. ^(1978 г.), основан на методе окаймления (см. (34), (35) с вектором

«2 соответствующим неизвестным на линиях (поверхностях) разрезов) и оценках для оператора 5г(Л); краевые условия могут быть умешанного типа. Подобная методика стала принципиальной основой многих современных вариантов (Мацокин A.M., Непомнящих С.А., Сиганевич Г.Л., Bramble J., Dryja М., Widiund О. и др.) метода.

В § 36 дана трактовка автора метода фиктивных сеточных Областей (Астрахаядев Г П., Кузнецов Ю.А., Марчук Г.И., Мацокин A.M., Сиганевич Г.Л. и др.) как метода построения модельных операторов типа Si(A) спектрально эквивалентных оператору L2 = L и указаны конкретные алгоритмы для некоторых трехмерпых задач.

В § 37 дается очень краткий обзор многосеточных итерационных методов (Астрахапцев Г.П., Бахвалов Н.С., Федоренко Р.П., НаскЪивЬ W., Мс Cormick S. и др.) и обращается внимание на возможность моднфикадни, приводящих к модельным операторам спектрально эквивалентным исход~ пому оператору. Такой подход, в особенности связанный с расщеплением, конечноэлементяых подростраяств, в последние годы дал ряд удачных конструкций, включая rf-мерныи случай (ш. [2,3] и цитированную там литературу).

Наконец, в § 38 даются конструкции нужных модельных операторов для общих областей в случае использования тркапгуляциЙ топологически эквивалентных трпангуляцняи модельных областей и особое внимание уделено двухступенчатым итерационным методам в комбинация с использованием линеаризации нелинейных оператороо. " '

Глава -4 посвящена вопросам построения упомянутых выше сеток и триангуляция спеш'л.тьпаго типа- § 41 дает краткий обзор применяемых па пракппаг конструкций, а § 42 и 5 43 посвящены алгебраическим алгоритмам построещтя сеток для стандартных блоков к способам разбиения сложной области на такие блока (статьи автора (1976, 1977 г.г.)). Например, для даукернык областей стандартным блоком служат криволинейный, треугольник, две стороны которого являются отрезками, а третья- дважды диффереяпнруклл! дугой, гашугааЗ аза вогаугоЗ} се яттротгстг-.гадпя должна или пршмдлгакать треутолыпщу, шст'ез иметь с trait общдх внутренних течек. Для одпоезеетых областей с грзтгжей Г, состгзлтетсй от конечного числа дуг -у„ уяеолстворяюшях указанным услозтшл а 0срйсехакяцяхся_ под внугрешпаш углами 0 с 0 < /?0 < /?.< ir — До, указывается способ построения кпатарзлпомерпых триаптуляций топологически зхппвалептнмх простейшим триагтгуляциям модельного прямоугольника. Для трехмерных областей процесс разбиения на стандартные блоки вызывает существенно яовыетрудностп. , • •

Глава 5 является итоговой в плане построения асимтотически оптимальных алгоритмов для краевых задач для уравнений и систем 2-го порядка.

В § 51 рассматриваются краевые задачи для линейных уравнений с положительной квадратичной формой. Обосновываются нужные оценки точности ПСМ, учитывающие аппроксимацию области, и особое внимание уделено анализу многосеточного ускорения. Рассмотрен также случай повышенной гладкости решения и использования полиномов Лагранжа в конструкции ПСМ. Родственные характеристики алгоритмов получены'для мпогосеточных методов в работах Астраханцева Г.П. и Корнеева В.Г. для некоторых более узких классов задач (целые индексы в (4), вложенные сетки, отсутствие сингулярных функций, определенные типы краевых условий).

В § 52 рассматриваются более общий случай, требующий использования либо итерационных методов типа (23) с ортогоналпзацией, либо итераций типа (32). Отдельно выделен случай вырожденного, оператора.

В § 53 изучаются ПСМ и итерационные процессы для сильцоэллплтиче-ския систем н задач теории упругости. Основное внимание, следуя статьям автора (1964, 1966, 1971 г.г)), уделяется построению блочно диагональных модельных операторов, спектрально эквивалентных исходному сеточному •оператору. Например, для трехмерных задач теории упругости и квазиравномерных триангуляции, топологически эквивалентных простейшим три-ангуляциям модельной области £) типа параллелепипеда, модельный оператор может быть, вида

£<3 О О О Во О

о о вя

с оператором Вц спектрально эквивалентным оператору — Д^. Отдельно рассмотрен случай задач с вырожденным оператором.

Заключительный § 54 посвящен квазилинейным задачам, в основном связанным с соответствующими монотонными операторами. Нужные сеточные неравенства получаются, следуя статьям автора (1966,1969,1973 г .г.). Указывается на возможность построения нужных алгоритмов ,и в случае возмущений линейных обратимых операторов и итераций типа (33). Для некоторых вариациопных неравенств классический метод штрафа позвр-ляет использовать ряд построенных итерационных алгоритмов, но в этом случае наличие большого параметра в нелинейном сеточном операторе не дает оптимальных асимптотик., •

/ Вя = В в

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

В § 61, следуя статьям автора (1971 г.), показывается справедливость неравенств типа (25), (26) как следствий обратимости линейного дифференциального оператора с краевыми условиями Дирихле, а затем ц оценок точности оптимального типа (см. (11) с и = 1; подобные оценки впервые были получены Ривкиндом В.Я. (19§6 г.) для более простых ситуаций). Тем самым обосповано применение итераций типа (23) (например, для разностных аналогов 1-ой краевой задачи теории упругости), что'и приводит к оценкам типа (5) (статьи автора (1971 г.); для областей сложной формы нужную асимптотику можно получить пли на основе сеточного варианта метода Шварца (статья автора (1963, 1971 г.г.)) или на основе более позднего метода разрезов). В общем случае помогают итерации типа- (32),'

В § 62 приведены сеточные неравенства аналогичные неравенствам острого угла (по терминологии Соболевского П.Е.) Между операторами (статьи автора 1966, 1971 г.г.; некоторые частные результаты для двумерных 'за: дач были получены ШЫсЬе I.). Они важны при изучении корректности, а также и сходимости птераций в сеточных нормах типа Ц^(П) и позволяют расширить круг нелинейных сеточных систем, для которых построены итерационные методы оптимального типа. Подобные системы'указаны в § 63, но основное внимание в нём уделено типам задач для которых достижимы оценки типа (5), ' .

Параграфы 64 и 65 посвящены итерационным методам оптимального типа для простейших разностных схем для уравнеий и систем 4-го порядка, в особенности, связанных с теорией плит и оболочек (статьи автора 1961, 1965, 1969, 1973 г.г.); краткий обзор практических применений основан па совместных статьях с Николаевым И.К. и Столяровым Н.Н..

Глава 7 посвящена асимптотической минимизации вычислительной работы при решении систем типа Стокса а Навье—Стокса. В основе ее лежат статьи автора 1983, 1334, 1257 г.г.. '

В § 71 изучается корректность ¿запйяых задач в гильбертовых пространствах, содержащих в себе йеяш! рад задач из гидродинамики и теории упругости и более общих задач п» «тзскаас ссдловых точек. Более точно, в гильбертовом пространстве С = С| х С?г рассматривается операторное уравнение

Lu =

с малым параметром

¿1,1 ¿1,2 "1 ' h

. ¿2,1 — «¿2,2

О < а < а0,а0 > 0.

Здесь

L,j е £(Gj;G¡), L¡ j = LJ¡hi € [1,2]J € (1,2) 7oh < ¿1,1 < 7i'b 7o > 0,72ij < ¿2,2 < lih, 72 > 0, H¿2,l|| s ||¿2.l|k~G, < «1

supl(¿2,.y2)l >g|M|, v«aeca,g>0.' »1?Í0 Fill

(36)

(37)

(38)

(39)

Доказывается, что Ь обратим и что ||Ь-1|] < К равномерно по а. Из этого, в частности, следует, что для произвольных неотрицательных а и оI верна оценка

|Ка)-и(«')||<Я'|а-а'|) ,.

(подобная оценка для системы Стокса была впервые получена Соболевским П.Е. и Васильевым В.В.).

В § 72 изучается проекционная аппроксимация указанной задачи на основе использования подпространств Сд з (?1,л х 62,А € О, При' этом выбор ¿( А = ¿1 и ¿2,а = ¿2 должен быть согласованным:

sup

ll<Mi

V02 6 02, ао > 0.

(40)

Тогда получаемые проекционные задачи поставлены корректно и имеют место оценки погрешности, пз которых следует что ||z|¡ < K(pi+/>2), где z н й - и, К~ Кз'(7о,71,«1.^о,7з,«о) п Pi н diste, {иг, Gi} Рг = distG){u2;G2}. Подчеркнем равномерность оценок по а и отсутствие предположений о гладкости решений. Изучение проекционных методов для аналогичных задач са=0 было начато в 70-х годах (Babushka I., Brezzi F., Сгоигеиг М., Fortín М., Raviart Р. и др.), úo часто характеризовалось использованием дополнительных предположений. Разностные методы изучались Валедин-ским'В.Д., Кобельковьш Г.М. и др..

'В § 73 основное внпманпе уделено конструкциям ПСМ, приводящим к справедливости (14). Подчеркнем, что это условие не следует из фундаментальных исследований свойств оператора дивергенции (Ладыженская

O.A., Солонняков В.A., Mageties Б., Nechas I. и др.), но именно эти исследования подтолкнули к поискам ПСМ с нужным свойством, (14). При выполнении (13) подпространства, предложенные автором в 1983 г., строятся на основе квазиравномерных триангуляций П) топологически эквивалентных триангуляциям T^\Q) модельной области Q, где ft — Пл С й-аппроксимирующая сеточная область того же типа, что и в главе 5. Тогда Gi состоит из функций, являющихся константами на каждом симплексе Т яз Ть\й) (базис более широкого пространства G'2 состоит из характеристических функций этих симплексов), а компоненты вектор-фукцяй из Gj состоят из кусочно линейных на Т^ф) функций, где триангуляция ljf>(fl) является сгущением T]P'(Ö) в d раз (при d = 2 она получается за счет проведения средних линий в Т) (в наиболее близких ПСМ (Crouzeuz М,, Raviatt Р.) при d = 2 использовались полиномы 2-го порядка, а вывод (14). требовал совпадения П п ft п выпуклости области). Допустимы включения сввгу-лярных функций в базис Gj. Рассмотрены также некоторые другие типы-пространств G2 и их аппроксимаций 62. Получеа важный для главы 8 результат, относящийся к некоторым областям с нелиппшцевой границей.

В параграфах 74 и 75 строятся аснмтотаческп оатимальные алгоритмы для систем типа Стокса и основное внимание уделено построению асимптотически оптимальных итерационных методов для того же, типа областей; что и в главе 5.' Эти вопросы были наименее разработаны; для разностных схем п простейших областей некоторые родственные результаты были получены Кобельковым Г.М.. Рассматриваемые сеточные системы имеют вяд

h

-XI [«пл

с дополнительпым условием

(«2,1)А«0, (42).

соотвстстуюшдм условию ортогональности щ и 1 (вектор и2 определяется значениями й2 па ашшгоксах из а Л и /2 суть матрицы Гра-ма для базисов <?1 п 6'2 соответственно). В простейших случаях, когда (£2,262» 1)ой ~ 0, показывается применимость итераций типа (32) с блоч-но даагопальпым оператором В Таким, что его диагональные блоки спектрально зквивалентиы операторам 3\ и В более сложных случаях предлагается несколько изменить задачу, заменяя X оператором

обладающим нужным свойством ер (В~1 (Ь0)*В~1 Ь°) С {0 и [fio.il]}- Получив приближенное решение этой задачи, легко найти приближение и к решению исходной. Также рассмотрены менее общие алгоритмы метода окаймления, связанные с операторами или

н Лг + «¿г,г, -Яг = Хз,)!^^^

или . "

51 = Хм + -Й), = Ьх^Ь^Ьг^.

а '

Указана конструкция модельного оператора Бх £ £+(#1) такого, что

г0Г>1 < 51 < ¿1£>1, (43)

с положительными константами ¿о и ¿¡, не зависящими ни от сетки, ни от параметра а; для решения системы с таким оператором требуется выполнения т — О (1п а) итераций типа

- ьк2) = -г!2)(Л2^ -где Л2 — аЬг^ + ^дВ!-11/1,5. Отметим, что для рассматриваемых ПСМ Ь2х2 суть диагональные матрицы. Имея указанные выше итерационные методы, можно получить и желаемые оценки (5) и Д), поскольку многосеточное •ускорение анализируется точно также как в в главе 5.

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

Наконец, в § 76 рассмотрены обобщения изученных алгоритмов аа случай нелинейных задач типа Навье—Стокса. Отдельно рассмотрены итерации, использующие линеаризацию и внутренние итерации для систем типа Стокса из § 74; для этих липеаризаций характерно отсутствие симметрии оператора. Помимо уже упомянутых работ по изучению ПСМ и итерационных методов, следует назвать ряд монографий (вкаиН У.п ШшаП Р., СЬ-тшИ И,., Тешат И.). ' ••

Глава 8 посвящена асимптотической минимизации вычислительной работы "для эллиптических задач 4-го порядка. В § 81 рассматриваются пр'остейпгае задачи в прямоугольнике, когда нет особых сложностей с построением подпространств Пространства И^(П) н основой итерационных методов служат результаты автора (1961, 1971 г.г.), посвященные двухступенчатым итерационным методам. Намного более общие классы задач

г

рассматриваются в § 82, в котором обосновывается возможность Сведения их к соответствующим задачам для систем 2-го порядка с линейным ограничении <1Ьг и — 0 и эквивалентных уравнениям типа (36) с а — 0 (статьи автора 1985, 1986 г.). Возникает новый класс краевых задач с нелокальными ограничениями. Корректность их показана за счет применения (14) для областей с нелипшидавой границей.

В § 83 анализируется сходимость ПСМ я эффективность итерационных процессов построенных по образцам 'из главы 7. Показывается, что при подходящих модификациях модельных операторов удается получить те же самые асимтотики типа (5) и (1) по отношению к производным решения (1-го и 2-го порядка).

Глава 9 посвящепа задачам построения асимптотически, эффективных алгоритмов решения спектральных задач типа (10), а также и некоторых более общих задач. § 91, в основном, является справочным; § 92 дает йеко-* торые модификации априорных оценок погрешности метода Релея—РитЦа. (отметим, что родственным вопросам, особенно, асимптотическим оценкам посвящено очень большое число работ (Вайникко Г.М. и др.)).

В. § 93 основное внимание уделено доказательству модификаций классического неравенства Тсмпля и вытекающих из них апостериорных оценрк.

Как уже отмечалось, наиболее существенные трудности для построения нужных алгоритмов были связаны с изучением итерационных методов для. сеточных спектральных задач (18). Модификации градиентных методов для отыскания наименьших собственных чисел задач (18) с М = / изучались рядом авторов (Годунов С .К., Огнева В. В., Прокопов Г. П., Само-кпш Б. А. й др.), но лишь в совместных статьях автора п Орехова М. Ю.. (1977, 1980 г.г.) былп получены необходимые оценки. Для более трудной задачи отыскания нескольких младших собственных чисел, особенно с учетом приближенной ортогональности к уже полученным приближенным собственным функциям, нужные оценки былп дали в статьях автора (1978,' 1979, 1983 г.г.). Именно эти оцепкл к служат осповей параграфов 94 и 95, Пусть .•'

ХМ г г» з Ып - А(ип)Мип.

Тогда исследуемый итерационный метод задается рекуррентными соотношениями: '■''..

. й«+| = + - • (44)

ип+1 = —-, (45)

где ||и"||л/ = 1,Рхи» — и", оператор Рх-ортопроектор в смысле Н(М) на ортогональное дополнение к линейной оболочке известных приближений к собственным векторам задачи (18), (п соответствует возможному возмущению метода, В 6 £+(Я)-модельный оператор (см.(24)).

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

. Ми = з1и, I 6 £+(С), М = М'.

§ 96 посвящен краткому описанию результатов по исследованию модифицированного метода итерирования подпространств, полученных совместно ■ с А.В.Князевым и особенно полезных для параллельных вычислений и для задач с близкими собственными числами.

На основе объединения конструкций ПСМ и модельных операторов из предыдущих глав и упомянутых выше результатов для спектральных задач с симметричными сильно эллиптическими операторами Ь 2-го порядка в § 97 строятся алгоритмы отыскания (с точностью е2) р младших собственных чисел А и соответствующих им собственных подпрострайств (с точностью е), требующие вычислительной работы с оценками (5) (вкючая оптимальный случай » — 0), если для элементов некоторых ортоиормированных базисов этих подпространств выполнены условия типа (4), (6), (7) и известно р-мерное подпространство Я® такое, что А(и) < к < Ар+1, Уи в Я°. Для задач с операторами 4-го порядка методика из главы 8 позволяет получить сеточные спектральные задачи вида

с а = 0 (см. (38), (40), (41)). Изучается их аппроксимация задачами с

а > 0, сводимыми к стандартным задачам

1 «

51«! = (¿1,1 + = ДМ1«ь

Конструкция модельного оператора 0\ £ £+(#1) из § 74 позволяет опять получить оценки типа (5) с в > 1 для отыскания с точностью е2 нескольких младших собственных чисел. В заключение указана возможность объединения результатов из глав 7 и 8 с известными результатами по исследованию ПСМ для дифференциальных задач типа (46) с о = 0 с тем, чтобы они стали применимы для задач с а > 0.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ, ;

1. На основе разработанной автором концепции спектральной эквшга-, лентности сеточных операторов п се обобщений для несимметричных операторов, связанных с соответствующей симметризацией исходной линейной сеточной системы, построены модификации классических итерационных методов, являющиеся астдтотпчески оптимальными алгоритмами или почти асимтотическя оптимальными алгоритмами Ллх приближенного решения эллиптических сеточных систем (линейных а нелинейных). Предложенные хопструкщга модельных сеточпых операторов основываются яа переходе к модельной области с сеткой топологически эквивалентной первоначальной я последующи.« применением: блочного окаймления матрицы и быстрых прямых методов; внутренних итераций по модифицированному методу Рпчардсояа либо по методу переменных направлений; метода разрезов (дехошгозшшп области) на стандартные блокп; метода дополнения области до стандартной за счет фиктивных сеточных областей; симметри-зованных многосеточпых итерационных методой или их новейших парная-, тов приводящих к мпогосеточяой конструкции модельного оператора.

2. Сочетание укагаппых итерационных алгоритмов с классической идей продолжеппя по параметру (применение ътзгосаточваго ускорения.) привело к конструкции асимтотическя оптимальных яля близких к ним алгоритмов для нахождения «-аппроксимаций к решениям корректных краевых за-, дач для линейных эллиптических уравнений 2-го порядка в ограниченных областях с весьма общей геометрией для двумерного случая и более простой геометрией для многомерного случая. Краевые условия могут быть смешанного типа с условиями Дирихле й с естественными условиями на различных участках границы; допустимо я их сочетание с условиями пе-

риодичности.

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

4. Аналогичные результаты получены для краевых задач для слабонелинейных уравнений и систем 2-го порядка, а также для некоторых задач с ограниченной нелинейностью, сводимых к корректным операторным уравнениям в некоторых шарах гильбертова пространства типа (И^О))*.

5. Построены асимтотически оптимальные или близкие к ним алгоритмы для решения двумерных и трехмерных краевых задач Дирихле для систем типа Стокса и Навье—Стокса в ограниченной области с лшшшцевой кусочно гладкой границей; при замене линейного ограничения сЦу и = 0 на сНу и— ар = 0 с малым параметром а > 0 построены алгоритмы с оценками (5) при V < 1, которые являются равномерными по а 6 (0,ао] (эти алгоритмы применимы, например, для изотропных задач теории упругости с большим параметром Ламэ А = Ао +1/а ).

& Подобные алгоритмы построены для ряда краевых задач 4-го порядка за счет сведения их к соответствующим задачам для систем 2-го порядка с линейным ограничении с11у и = 0.

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

Список цитированной литературы

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

2. Дьяконов Е. Г. Повышение эффективности сеточных методов при решении статических задач теории упругости. Вычислительная механика деформируемого твердого тела, Выпуск 2., 1991, с. 133-157.

3. Дьяконов Е. Г. Составные сетки и асимптотически оптимальные алгоритмы для задач типа Стокса и Навье—Стокса. Доклады РАН, 1993, 329, с. 265-269.