Введение к работе
Актуальность работы. Минимизация вычислительной работы при решении эллиптических задач, к которым относятся краевые и спектральные задачи с сильно эллиптическими операторами, является одной из важнейших задач вычислительной математики. Она имеет и сильное идейное родство с классическими задачами оптимизации в теории аппроксимации функций и построения формул численного интегрирования. Четкая постановка этих задач и успехи в их решении прежде всего связаны с именами А.Н.Колмогорова, СМ.Никольского, С.Л.Соболева, Н.С.Бахвалова. Полученные ими результаты, а также первые успехи в построении асимптотически оптимальных вычислительных алгоритмов для решения разностных систем И задачи Дирихле для гармонического уравнения, привели в начале 60-х годов К постановке задачи асимптотической минимизации вычислительной работы при решении с точностью с задачи из класса эллиптических задач, решения которых образуют компакт в рассматриваемом пространстве Соболева, и появлению гипотезы Колмогорова-Бахвалова о том, что логарифм оптимальной асимптотики должен быть эквивалентен е-энтропии этого компакта.
Особая роль ПСМ (проекционно-сеточных методов) в решении этой задачи делает более естественным вместо «-энтропии использовать JV(e)-none-речник в смысле Колмогорова данного компакта, как это было предложено в 1965г. в известной статье И.Бабушки и С.Л.Соболева. Более точно, пусть е > 0-нужная нам точность приближения к искомому решению и известна асимптотика ЛГ(е)-поперечника упомянутого компакта. Тогда построение вычислительных алгоритмов, приводящих к нужным е -аппроксимациям при выполнении W(e) арифметических действий (операций), где
W{c)xN(i), (1)
является решением поставленной задачи минимизации вычислительной работы и соответствует усиленному варианту гипотезы Колмогорова—Бахва-лова., Поэтому актуальность указанной фундаментальной математической
проблемы и результатов, направленных на ее решение, является общепризнанной.
Именно асимтотически оптимальные алгоритмы с асимптотикой (1), а также почти асимтотически оптимальные алгоритмы с несколько худшей асимптотикой
W(e) = 0(N(e)\hM\r), г>0 (2)
построены в настоящей диссертации для достаточно широкого круга эллиптических двумерных и многомерных задач, включающего в себя основные типы краевых задач для уравнений и систем (линейных и нелинейных) эллиптического типа 2-го и 4-го порядка, а также для систем типа Стокса и Навье—Стокса, и, наконец, включающего в себя родственные спектральные задачи с сильноэллиптическими операторами. Следует также подчеркнуть и первостепенную значимость упомянутых алгоритмов в плане их применения при решении многих трудных прикладных задач, в особенности связанных с решением сеточных систем (линейных и нелинейных) большого порядка. Многие из них широко используются на практике. Появление современных многопроцессорных компьютеров и необходимость решать многомерные краевые задачи только повысило внимание к подобным классам алгоритмов, о чем свидельствуют многие международные научные конференции, посвященные, например, методам декомпозиции области и итерационным многосеточным методам.
Цель работы. Целью работы было выяснить возможно ли получение
алгоритмов с характеристиками типа (1) или (2) при специальных и весь
ма естественных выборах компактов, связанных с предположениями неко
торой избыточной гладкости решения в терминах пространств Соболева—
Слобояецкого G(m+,>) = W2m+T(fi), т ~ [т] > 1,0 < у < 1 или эквивалент
ных им пространств Бесова (подобные предположения, по крайней мере для
целых т + 7, стали стандартными в теории сеточных методов с конца 60-х
годов). Более точно, пусть исходная линейная краевая задача для эллипти
ческого уравнения 2-го порядка ставится в ограниченной области О С RJ
с липшицевой кусочно гладкой границей Г в может рассматриваться как
корректное операторное уравнение :.
" = / (з)
в гильбертовом пространстве G С Wj?(fl) = G^\ Пусть для его решения
известно, что
||«||m+7,n < К, m = [m] >1,0<7<1. (4)
Тогда это неравенство определяет компакт в G и N(e) х е~л'", где v = m + j — l. Поэтому (2) переходит в
W(t) < Ke-<""\lnt\r (5)
(условимся иногда обозначать разные константы одной и той же буквой). Другой важный выбор связан с разбиением ft на блоки fii,..., ftp и условиями
Nb+"A < К., * = !,...,/> (6)
Подобные условия существенно важны для уравнений с разрывными коэффициентами. Два указанных класса условий занимают центральное место в диссертация, но рассмотрен также случай условий
, «(*) = І ciXi(z) + ио(*0, Ы*) Є W2,+"(n), 0 < и, '* (7)
с известными сингулярными функциями Xk(x)t Но неизвестными коэффициентами ct. Для щ(х) возможны также условия (6).
Для систем эллиптического типа, имеющих дело с неизвестными вектор-функциями и s [tii, і u*]i соответствующие условия имеют вид
,Wi+v,n, <К,\ *~l,...,p; / = 1,...,*. (8)
Для систем типа Стохса и Навье—Стохса' аналогичные условия па вектор скорости Из [ui,.,.,Ui] п давлениер принимают вид
Nli+Mi. < ^.; fWkn, < ^ » = 1,...',<М»1,...Д 0<»/<1. (9)
Для спектральных задач
u = АМи (10)
с сильно эллиптическими операторами 2-го порядка L Є +(G) п подчиненными им операторами М = А/* > 0 0-го или 1-го цорядков, сводимых к спектральным задачам Аи = «и с А = 1/в в гильбертовом пространстве с симметричными, положительными и компактными операторами А, целью служат алгоритмы отыскания (с точностью е5) нескольких младших собственных чисел А и соответствующих им собственных подпространств (с точностью (), требующие вычислительной работы с оценками (5), если
для элементов некоторых ортоиормироваиных базисов этих подпространств выполнены условия типа (4), (6), (7).
Наконец, для двумерных задач связанных, например, с эллиптическими уравнениями 4-го порядка была интересна проблема построения вычислительных алгоритмов, приводящих к нужным «-аппроксимациям (в прс~ странстах И^П) и 1^(0) для соответственно первых и вторых производных решения и Є И/22+"(П), 0 < v < 1) и характеризуемых оценками (5). Подобная постановка объясняется тем, что изучались методы сведения данных краевых задач к соответствующим задачам для систем 2-го порядка с ограниченим div й — 0.
Таким образом, можно сказать, что главной целью для всех указаяпых типов эллиптических задач было построение вычислительных алгоритмов, приводящих к нужным ^-аппроксимациям и требующих выполнения W(e) арифметических действий с оценками (5), в которых случай г = 0 соответствует аснмтотически оптимальным алгоритмам, а случаи г = 1вг = 2 соответствуют почти асимтотпчески оптимальным алгоритмам.
Указапная центральная задача разбивалась на две подзадачи, связанные с выбором асимтотпчески оптимального по точности сеточного метода и с построением почти асимтотпчески оптимального итерационного метода для приближенного решения возникающих сеточных систем. Каждая из них была в центре внимания большого числа исследователей и имела свои трудности, преодоление которых потребовало значительных усилий и времени. Некоторые из них активно изучаются и несомненно будут изучаться в дальнейшем.
Методическая характеристика работы. Методика построения асимптотически оптимальных вычислительных алгоритмов может быть еще более четко описана на основе выделения трех этапов, требовавших:
-
выбора асимтотпчески оптимального по точности сеточного метода;
-
построения аснмтотически оптимального итерационного метода для приближенного решения возникающих сеточных систем;
-
применения многосеточного ускорения для построенного базисного оптимального итерационного метода.
Первый этап, в случае у < 1, основан на использовании семейства квазиравномерных триангуляции (симплексных сеток) ТЦПл) топологически эквивалентных трнангуляпихм ТЦф) для некоторых модельных замкну-
4 ...
тых областей Q (ячейками последних служат симплексы, являющиеся регулярными частями кубов с длиной стороны Л). Здесь Пд = Q, если Q состоит из конечного числа симплексои, а в общем случае Пд есть 0{h2)-аппроксимация для П (граница Пд; обозначаемая через Гд = Г, принад-лежит 0(Л2)-окрестности границы її, обозначаемой через Г). Более точно, участок границы Го, соответствующий однородным условиям Дирихле, предполагается принадлежащим Q, а оставшийся-проходящим вне области П, что позволяет придать смысл щ - «, где йн Є W% (П^; Го) есть решение получаемое в ЦСМ, связанным с рассматриваемой триангуляцией Та(Па), а и <Е G s W^Cl; Го) есть решение исходой задачи для эллиптического уравнения. Конечно, вопрос о возможности построения нужной триангуляции не является простым, и исследовался отдельно. Сам ПСМ использовал подпространство Gh = И^(Йа;Го), образованное непрерывными на Па н кусочно линейными на 7Х(Пд) функциями (он является естественным обобщением классического метода Куранта для двумерных задач). В случае (7) в его базис дополнительно включались сингулярные функции Хк(х), что предлагалось и ранее в простейших ситуациях (Fix G., Babushka 1.).
Тогда ПСМ мог считаться асимтотически оптимальным по точности, если он приводил к корректым дискретным задачам и к оценке погрешности
||й* - «II < tfofc", (11)
где константа Л*о определяется константами из условий (4), (6), а в случае (7)-(9)-аналогичными константами для щ(х). В некоторых простейших случаях подобные оценки установлены и для разностных методов.
Если имеет место (4) и Па = U, то оценки (11) сі* = т + 7-1 верны, если на каждом симплексе из Га(Па) элементы из Gh являются интерполяционными полиномами Лагранжа, в общем случае, степенп т' > т (для общих областей возмо>кно использование квазнтрнангз'ляций). . Прп получении (11) (для уравнения и систем, линейных и нелинейных) были существенны как обобщения априорных оценок погрешности проекционных методов, например, для корректных задач (3), так и вопросы аппроксимации в пространствах Соболева.
Особый интерес представляют оценки погрешности (11) сиг [и;р] и «А ~ («а; Ра), применимые для двумерных и трехмерных краевых задач Дирихле для систем типа Стокса и Навье—Стокса в ограниченной области с липшицевой кусочно гладкой границей, а также для родственных задач с ограничением
div w - ар = 0, (12)
где а-малый положительный параметр (такие задачи встречаются не только в гидродинамике, но и в теории упругости). Важной методической особенностью является рассмотрение краевой задачи как корректного операторного уравнения с седловым оператором в гильбертовом пространстве G = G\ х (?2, где
Gx = {W}((l)y,tGisG'2\lt (13)
С, з а(П),С2 \ 1 s {р : р Є Ь2(П); (р, 1)0,« = 0}
и неизвестными функциями служат «'= Uj = [ui(i;.. .juj^]7* Є Сі и р u2 Є (?2, a d = 2 или d = 3. Если эта задача аппроксимируется ПСМ с подпространствами G — G\ х G^, где G\ С G\,Gi С <-?г, и й = [«г.«г]т Є Ga, то, как это известно с начала 70-х годов для задач с а = 0 в (11), исключительно важен их выбор, приводящий к неравенству
вцр (div^pkn г аМ ао>0> у ^ (14)
иєС, llulk
с константой его, не зависящей от Л. При этом оставались проблемы спраг ведлцвости (14) даже для двумерных невыпуклых областей с углами и наиболее простого выбора такой пары подпространств. Сами оценки (11) были получены довольно сложным образом лишь при v — 1, и их вывод при а > 0 был неизвестен.
Применяемая методика для ряда двумерных краевых задач 4-го порядка характеризуется их сведением их к соответствующим задачам для систем 2-го порядка с линейным ограничением div u = 0, в котором и есть ротор решения исходной задачи. В случае систем 4-го порядка возникает несколько подобных ограничений. Важно было четко описать соответствующее гильбертово пространство роторов, особенно для разнообразных типов краевых условий и мпогосвязных областей. После этого необходимо было доказать неравенство типа (14) при разумном выборе аппроксимирующих подпространств.
Наконец, для спектральных задач (10) применялись ПСМ того гке типа, что и для (3). Характерно, что аппроксимация собственных хяудцро-страиств последовательно характеризовалась при помощи понятия раствора подпространств, введенного М.А.Красносельским и М.Г.Крейяом.
Перейдем теперь к характеристике 2-го этапа, связанного г построением , базисного оптимального итерационного метода. Начнем с рассмотрения
линейных и нелинейных эллиптических сеточных систем
huh = /л (15),
в которых вектор ил s u = (ui,..'., u# ]г является элементом евклидова пространства И = R" и образован из коэффициентов разложения й Є Ga по выбранному базису ^j(x),..., \А# (г) подпространства G/,. Отметим, что
»*к~Ф- (16)
Поэтому, если будет построен итерационный процесс, за одну итерацию (за фиксированное число итераций) уменьшающий разумно выбранную норму (она должна быть согласована с нормой в G/,) ошибки в конечное число раз, независящее от сеткн, и такой, что вычислительная работа на каждой итерации оценивается как W — 0(N)t то получение пужной е-аппрокспмацип к решению (15) (тем самым, н к и) потребует затраты
ИЧ)*0(ІУ|Ье|) = 0(^!) '''(17)
арифметических действий. В ряде случаев нужный оптимальный итерационный процесс получается довольно простой модификацией какого-нибудь классического итерационного метода. Например, для линейных задач с ь — LI > 0 (что тоже, с Li, Є С+(Н)) плодотворна концепция спектральной эквивалентности сеточного модельного оператора В/, Є (#) и исходного сеточного оператора L^, применяемая автором с начала 60-х годов. Дли несимметричных операторов ее обобщения связаны с соответствующей симметризацией исходной линейной сеточной системы и оказались весьма оффехтпвньшн и для сеточных систем тппа Стокса. Для пелниейных задз-ч удалось изучить лишь модификации классического метода простой итерации я пекоторых градиентных методов. Особо выделяется проблема пзучешія модифицированных градиентных методов отыскания нескольких яладшпх собственных чисел для получаемых сеточных спектральных задач
ЇМ = АьД4«ь. (18)
Здесь, опять асе ключевую роль играет задача построения модельного оператора-2 Є +(#) спектрально эквивалентного оператору Ьь; значительные трудности вызывает также задача учета эффекта приближенного заданна ' проектора па подространство уже найдепных собственных векторов.
Наконец, чтобы в оценках (17) убрать лшппий множитель 11пе{, при-ііепялась классическая идея метода продолжения по параметру, основой
которого служит выбор печального приближения в итерациях для системы с повым значением дискретного параметра на основе совпадения этого приближения с полученным для предыдущего значения параметра. Для сеточных систем эта идея давно известна и нашла, например, удачное применение в статье Н.С.Бахвалова в 1966 г., связанной с анализом много-сеточного итерационного метода для разностных систем и прямоугольной области (продожсние проводится по параметру сгущения сетки и приближенное решение на грубой сетке интерполируется на более мелкую). В данных же применениях необходимо было связать аналогичную процедуру с оценками (11) в Соболевских нормах и показать, что на каждой сетке можно обойтись конечным (достаточно большим, но не зависящим от е) числом итераций базисного оптимального итерационного метода. При этом важеп учет эффекта криволинейных областей, так как узлы старой сетки Могли ае быть узлами более мелкой. Для этого и была особенно полезна разработанная методика построения нужных сеток.
Возвращаясь к менее трудной проблеме построения почта асимтотиче-ски оптимальных алгоритмов с оценками (5), мы можем или вообще обойтись без применения Многосеточпого ускорения, ограничившись оценками (17), или даже применять базисные итерационные методы, приводящие к оценкам
W(e)
а затем улучшить их до оценок (5), применяя указанную процедуру многосеточпого ускорения. Например, допустимы базисные итерации, сходящиеся со скоростью не зависящей от сетки, по требующие па каждой итерации
W = 0(ЩЫ N)% s^l,s = 2 (20)
арифметических действий.
Научная новпзпа п практическая кавкость работы. Диссертация является научной монографией к сказана на исследованиях автора, результаты которых были опубликованы эа период с 1961 г. по 198S г.. Основные результаты (они указаны отдельно) па момент публикации были новыми и, в целом, дают подтвер^іксике усиленного варианта гипотезы Колмогорова -Бахвалова для достаточно широкого круга эллиптических двумерных и многомерных задач. Tlommta некоторых результатов была "подчеркнута выше при описании вргшеияемой методики регчепяя указанной фундаментальной математической ироблвмы. В то же время следует отмстить, что отдельные и бодае частные темы были и остаются в центре
внимания многих исследователей. Подобные наиболее близкие результаты упомянуты ниже при наложении содержания работы, а ссылки на более отдаленные могут быть найдены в самом тексте книги (список литературы d ней содержит около 320 работ). Ряд относительно новых и важных - публикаций указан в статьях {2j u [3j.
Практическая ценность предложенных и родственных алгоритмов в плане их применения при решении прикладных задач частично отмечена выше. Укажем дополнительно только несколько подобных задач из теории оболочек и теории упругости, в решении которых автор или принимал непосредственное' участие или, по крайней мере, консультировал по поводу предложенных им методов. Наиболее длительное сотрудничество имело место с ВЦ НИИ шинной промышленности (с начала 60-х годов). Решар-шнеся там системы сетчатых оболочек (линейные и геометрически нелинейные) соответствовали в некоторых случгшх сильноэллиптическим системам в смысле Ниренберга 4-го порядка и позволяли нсполь-тоать почти ортогональные сетки на поверхности оболочки, топологически эквивалентные прямоугольным. Это делало.перспективным применение разностных иетодод и двухступенчатых итерационных методов с модельііьш оператором, спектрально эквивалентным или исходному сеточному оператору L/, нли его линеаризации. Составленные программы началн применяться дда .расчета автомобильных шин с середины 60-х годов, а позднее, при их соответствующей модифіпсадац, Я для расчета авиационных шин, в том числи я специальных шин для" Бурана" (Н.К.Ннколаеп, начало 80-х годов). Конкретные сильнонелинеГшне вариационные неравенства (задачи с препятствиями) при пх решении требозолд работы примерно с 50 тысячами неизвестных. Рад родственных расчетоз для упруго-пластических оболочек успешно провел Н.Н.Столяров (Самарский-Политехнический Институт, 80-ые годы). Специальный класс двумерных и трехмерных задач теории упругости* связанных с кбмнозитаыян материалами и сложными геометриями области, эффективно решался и решается па кафедре теории композитов (МГУ) под общим руководством Б.Е.Победрн.
Апробация работы. Основные положеная п результаты неоднократно докладывались и обсуждались на научных семинарах, например:
в МГУ им. М.В.ЛомоносОза (под руководством: Бахвалова Н.С.; Ильина В.А. п Бицадзе А.В.; Идыощипа А.Д. я Победри Б.Е.; Олейша О.А.; Тпхоноза А.Н. и Самарского А.А.);
; »в МИ РАН им. Б.А.Стекяода (под, руководством Бесова О.В., Кудряв-
цсва Л.Д., Никольского СМ. и Соболева С.Л.;)
ИВМ РАН (под руководством: Марчука Г.И; Бахвалова Н.С. п Лебедева В.И.);
ИПМ РАН им. М.В.Келдыша (под руководством: Бабенко К.И.; Рябенького B.C. и Федоренко Р.П.);
ЛОМИ РАН им. В.А.Стеклова (под руководством Ильина В.П., Мгос-липа С.Г. и Фаддссва Д.К.);
ВЦ СО РАН (под руководством Марчука Г.И.);
МЭИ (под руководством Дубинского Ю.А.).
Многие результаты излагались также в курсах лекции, читавшихся автором для преподавателей, сотрудников, аспирантов и студентов старших курсов по прилашениям ряда университетов Болгарии, Великобрптаапи, Литвы, Польши, США, Чехословакии, Украины.
Им же были посвящены доклады автора на ряде научных конференций и школ. Например, среди проводившихся в последние 10 лет можно назвать:
Пятую Всесоюзную конференцию "Вариационно-разностные методы в математической физике"(1983, Москва);
Международную конференцию по дифференциальным уравнениям с. частными производными (1983, Новосибирск);
Пятую Всесоюзную школу "Теоретические основы и конструирование численных алгоритмов .решеипя задач математической физики" (1984, Казань);
Седьмую Всесоюзную конференцию "Вычислительные методы линейной алгебры" (1985, Москва);
е Первую Всесоюзную конференцию "Современные проблемы численного анализа" (198G, Москва);
в Сомшгяр им. И.Г.Петровского и заседание ММО (1987, Москва);
Вторую Всесоюзную конференцию "Современные проблемы численного анализа" (19S9, Тбилиси);
Четвертую Международную конференцию по двфференпязлышм уравнениям и методам их решения (1989,. Русе, Болгари*);
Пятую Международную конференцию по методам декомпозиции обла
сти для уравнений в частных производных (1990, Москва);
в Международную конференцию "Современные проблемы численного анализа" (1992, Москва);
Шестую Международную конференцию "Многосеточные методы" (1993,
Коппер Маунтинз, США).
Структурой объем работы. Диссертация является научной монографией. Состоит из предисловия, введения, 9 глав, списка основных обозначений, списка литературы, содержащего около 320 наименований, и предметного указателя. Объем диссертации до цитированной литературы 250 стравил..
Похожие диссертации на Асимптотически оптимальные алгоритмы для эллиптических задач
