Неполные блочные разложения, основанные на аппроксимантах Паде тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Васильева, Екатерина Алексеевна

• Васильева, Екатерина Алексеевна
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Васильева, Екатерина Алексеевна

Введение

1 Полное блочное разложение

1.1 Полное блочное разложение для блочных трехдиагональных матриц.

1.2 Полное блочное разложение для модельных задач.

2 Касательное и двухчастотное разложения

2.1 Определение касательного и двухчастотного разложений для модельных задач

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

2.3 Касательное разложение как симметричная итерация.

2.4 Связь между касательным разложением и методом Гаусса-Зейделя

3 Теоретические и численные оценки скорости сходимости касательного и двухчастотного разложений

3.1 Вспомогательные теоремы.

3.2 Оценки снизу для матрицы системы К для модельной задачи

3.3 Сходимость последовательности блоков Т» и блоков матрицы остатка iVj для касательного и двухчастотного разложений.

3.4 Оценки для нормы итерационного оператора.

3.5 Оценки для классических симметричных задач.

4 Последовательности касательных и двухчастотных разложений

4.1 Теоретические оценки скорости сходимости последовательностей касательных и двухчастотных разложений.

4.2 Численные оценки скорости сходимости последовательностей касательных и двухчастотных разложений

4.3 Результаты численных экспериментов.

4.4 Обобщения.

5 Разложения высоких порядков

5.1 Обобщенное касательное и М—частотное разложения.

5.2 Оценка скорости сходимости и оптимальные параметры обобщенного касательного и М-частотного разложений для модельной задачи.

5.3 Теорема существования обобщенного касательного и

М-частотного разложений для модельной задачи.

5.4 Разложения высоких порядков для матриц общего вида.

5.5 Результаты численных экспериментов.

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

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

Пусть требуется решить следующую краевую задачу

V (ф(х,у) Vu) + cu = /,

T(u|en) = О, где Q G К2 - ограниченная область, и : Q К - неизвестная функция, с - константа, / : Q —Ж - правая часть, а Т - граничное условие.

Аналитическое решение этой системы возможно лишь в самых простых случаях. В остальных требуется использование численных методов. Численное решение можно разбить на два этапа. Первый - дискретизация уравнений. В результате возникает система линейных алгебраических уравнений, решение которой является приближенным решением исходной системы. Свойства системы алгебраических уравнений зависят от способа дискретизации. Наиболее известными являются методы конечных разностей и конечных элементов (конечных объемов в трехмерном случае). Последние предпочтительнее для областей со сложной геометрией и широко используются в математическом моделировании.

Для дискретизации вводится сетка С П и во всех ее внутренних узлах дифференциальное уравнений заменяется на алгебраическое. Максимальное расстояние между соседними узлами сетки называется шагом сетки h и характеризует уровень точности дискретизации. При h —> О решение алгебраической системы уравнений сходится к решению системы дифференциальных уравнений. Очевидно, что чем меньше шаг сетки, тем больше число неизвестных в системе алгебраических уравнений. Таким образом, одним из важных свойств матрицы системы алгебраических уравнений является, как правило, ее большая размерность, которая возрастает с увеличением точности.

Однако каждое из уравнений содержит лишь небольшое число ненулевых коэффициентов, не зависящее от h. Это также является характерным свойством рассматриваемых нами систем уравнений. Матрицы подобных систем уравнений называются разреженными. Поэтому использование классических прямых методов таких, как, например, метод исключения Гаусса, нецелесообразно, т. к. в процессе счета разреженность исчезает. Поэтому предпочтение отдается итерационным методам.

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

Рассмотрим в качестве примера задачу Дирихле в единичном квадрате для уравнения

Иц BUyy - fy и|ш = 1) где константа в > 0.

При в — 1 мы получим уравнение Пуассона, а при в ф 1 - анизотропное уравнение диффузии. Введем для дискретизации равномерную сетку

Oft = {(я»» Vi) xi = »/(« + !)> Уз = j/(n + !)> 0 ^ ЬЗ ^ n + 1} и воспользуемся методом конечных разностей. Неизвестную сеточную функцию мы снова обозначим через и, а ее значения в узлах сетки через щ. Значения и^ при г, j = 0 и п+1 определяются из граничных условий: uoj = Un+ij = Щ,о - Щ,п+1 = 1, 0 ^ г, j ^ п + 1.

Заменяя в остальных узлах производные на конечные разности, после умножения на /г2, где h = l/n - шаг сетки, получим систему п2 линейных уравнений

-EUij-г - Uj-ij + (2 + 2в)щ3 ~ щ+ij - sulJ+1 = fij, 1 ^ i,j ^ n, где f^ = h2f(xi,xj). Линейный оператор левой части записывается в виде следующего шаблона в

-1 2 + 2е -1 • —в

В уравнениях, соответствующих приграничным узлам (при i,j = 1 и п), слагаемые, содержащие известные значения и^ с границы, переносятся в правую часть.

Затем, после лексикографической нумерации узлов сетки, полученную систему уравнений можно записать в матричной форме

К u = f, где К = blocktridiag{—L, D, —L} - блочная трехдиагональная матрица К € К"2 хп'2 с блоками D — tridiag{—1,2+2е, —1}, L = в1, D,L G R"xn. В каждой из строк матрицы системы К находится не более пяти ненулевых элементов, находящихся на главной и четырех побочных диагоналях. Поэтому говорят, что матрица К имеет ленточную структуру. Собственные значения этой матрицы хорошо известны и равны

Amin = 4(1 + е) sin2(7i7i/2), Amax = 4(1 + в) cos2(tt/i/2).

Отсюда число обусловленности матрицы К

К) = Amin/Amax = 0(п2).

Отсюда видно, что оно растет пропорционально квадрату п, поэтому матрица К при больших п является очень плохо обусловленной.

Рассмотренный пример является одним из классических примеров, на которых тестируются методы решения систем линейных уравнений с блочной трехдиагональной матрицей, т. к. мы наперед знаем его решение. Отметим, что вместо рассмотренного шаблона можно использовать и другие. В дальнейшем будем называть задачи с матрицей вида К = blocktridiag{—L, D, —L} модельными.

Существуют прямые методы решения систем линейных алгебраических уравнений вида

К u = f (1) с большой разреженной и плохо обусловленной матрицей. Однако их использование из-за больших вычислительных затрат не является целесообразным. Поэтому для решения подобных систем уравнений используют итерационные методы. Их основная идея состоит в том, что, начиная с некоторого начального приближения щ, рекурсивно строится последовательность

Щ, йь. сходящуюся к решению и*. При этом в процессе вычислений матрицу К заменяют на ее приближение W, имеющее такую же структуру, что и К. Самые простые методы такого типа можно записать в виде йк+i = йк- W1(/ - Kfifc).

Матрица W называется приближенно обратной или предобуславливателем. При этом подразумевается, что вычислить вектор с = W-1r, гораздо проще, чем найти решение системы (1). Это выполняется, например, в том случае, когда матрица W диагональная, треугольная или является произведением треугольных. К такому классу методов относятся: метод Гаусса-Зейделя, метод верхней релаксации (МБР), попеременно-треугольный метод и др. Этому же классу принадлежат и различные варианты неполного разложения (ILU - incomplete LU-decomposition) и неполного блочного разложения (IBLU - incomplete block LU-decomposition). Свойства каждого из методов в этом случае определяются свойствами его предобуславливателя.

Эффективность метода оценивается при помощи скорости сходимости p = p(/-W"1K), где р- спектральный радиус. При р < 1 последовательность приближений Uk сходится к решению системы алгебраических уравнений (1) и при этом выполняется lim рк = lim ' 1 = p, k-toо k-too 11 Tfc j j где Tk — f — K£tfc - невязка относительно щ и нормы || • ||. В этом случае говорят, что метод сходится. Чем меньше значение р, тем лучше скорость сходимости, и тем сильнее уменьшается за итерацию значение нормы невязки. При численных исследованиях за скорость сходимости обычно принимают либо среднюю скорость сходимости за заданное число итераций, либо, если метод обладает ассимптотическим свойством, отношение невязок рдг при достаточно большим N. Как правило, существует следующая зависимость между скоростью сходимости и числом обусловленности матрицы К : при к (К) —у оо значение р —> 1. Это происходит, как уже было сказано выше, при уменьшении шага h и, как следствие, росте размера задачи. Например, метод Гаусса-Зейделя имеет скорость сходимости 1 — О (h2), а МВР при оптимальном выборе параметра 1 — O(h). Уже отсюда видно, что при малых h МВР лучше метода Гаусса-Зейделя, т. к. скорость сходимости последнего быстрее стремится к единице. Если для некоторого метода его скорость сходимости представима в виде р = \-0{ЬР), то число р называют порядком сходимости метода.

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

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

Другим подходом к решению системы (1) является использование неполных разложений (неполной факторизации) матрицы системы К. Его идея заключается в том, чтобы заменить матрицу системы К по некоторому правилу на ее приближение W = LU таким образом, чтобы оно было представимо в виде произведения разреженных легко обратимых матриц L и U.

Отечественная наука считает основоположником метода неполной факторизации Бу-леева Н. И. [8], предложившего метод, который теперь называется явным методом Булеева, хорошо и достаточно полно изложенный в [14]. Ключевым моментом этого метода является, так называемый, принцип согласования строчных сумм, заключающийся в том, что суммы элементов соответствующих строк матрицы системы К и предобуславливаю-щей матрицы W одинаковы: Ке = We. Впервые этот метод был опубликован в работе [8] и ранее изложен в книге Марчука Г. И. [16].

В иностранной литературе принято считать, что независимо от Булеева понятие неполного разложения ввел Варга [60], а Мейеринк и Ван дер Форст [51] привели анализ предложенного метода. Позднее появился ряд модификаций этого метода: ILUi в [40], ILUW, 1С (incomplete Cholesky) [48] и др. Например, при построении неполного разложения по методу Холецкого, зануляются элементы матриц L и £/, лежащие на побочных диагоналях таким образом, чтобы эти матрицы имели структуру, аналогичную структуре исходной матрице системы.

К методам неполного разложения примыкает и оригинальный метод а — /3 итераций, предложенный Четверушкиным Б. Н, подробное изложение которого можно найти в [28]. Метод неполного разложения зарекоммендовал себя как робастный, т. е. он показывает высокую скорость сходимости не только для модельных задач (уравнение Пуассона, анизотропное уравнение диффузии и др.), но и для задач с перемнными коэффициентами.

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

Большой класс практически важных задач сводится к решению систем уравнений с блочными трехдиагональными матрицами. Блочному методу Гаусса соответствует полное блочное разложение матрицы системы К = blocktridiag{—Lj-b А, — Ui} вида

К = (Ы-Т)Т1(и + Т), где L = blocktridiag{—Lfi,0,0}, U = blocktridiag{0,0, -Ui-i}, Т = blockdiag{7;} и Ti = Di, Tj = Di — L{r^\Ui. В общем случае матрицы Tj являются заполненными. Заменив эти матрицы их на разреженные легкообратимые аппроксимации Тг-, мы получим вместо прямого метода итерационный. Способ задания аппроксимаций Тг- и определяет вид неполного блочного разложения

W = (L + Tyr-^U + T), где Т = blockdiag{Tj} и fi = A, fi = Di-Lifi-1Ui.

Метод неполного блочного разложения получил развитие с начала 80-х гг. В 1981 г. Кеттлер [49] предложил использовать в качестве предобуславливателя матрицу W, которая строится следующим образом: при рекуррентном построении блоков значения на "лишних" диагоналях отбрасываются, т. е.

Ti = Di-Li(f-\f)Ui (г >2), где — {dij} обозначает матрицу следующего вида

A)W=rij ПРИ <

I 0 в остальных случаях.

Этот метод (ILLU - incomplete line LU) используется как предобуславливатель в МСГ или как сглаживатель в многосеточном методе.

Дальнейшее развитие метод неполного блочного разложения получил в работах [31], [43], [47], [52] и др. Особо отметим работу Еремина и Колотил иной [12], предложивших в 1987 г. целый класс предобуславливателей, использующих для блочных матриц обобщение принципа согласования строчных сумм. Этот принцип также использовали Аксельсон и Полман [32] при построении алгебраического двухсеточного метода.

В 1992 г. Г. Виттум [65] предложил использовать не одно, а набор разложений, каждое из которых давит высокие или низкочастотные компоненты ошибки. Этот метод получил название метода частотно-фильтрующих разложений (FF - frequence filtering decomposition). Для построения разложений использовался набор "тестовых" векторов е^,., еУ*\ Каждое из разложений W^ строилось с применением либо одного, либо двух векторов е^ так, чтобы на них предобуславливающая матрица W и матрица системы К действовали одинаково. Можно показать, что это условие можно заменить на эквивалентное:

Тге? = Ае?, Тге^ = (Д - ЦТ^Ще? (г ^ 2). Виттум рассматривал в качестве блоков неполного блочного разложения матрицы вида

Ti=Db Ti = Di-Qi (г ^ 2), где Оi - диагональные или трехдиагональные матрицы. Воспользовавшись последним условием, можно найти компоненты матриц 0; из соотношений LiD^Uie^ (г > 2).

Он применял следующие тестовые вектора: е® = su^ncu^Hh) или е^ = cos(iruj(l4h): h— шаг сетки. Если выбрать "высокочастотные" тестовые вектора (ш^ 2г> 1), то мы получим метод, который хорошо давит высокочастотные компоненты ошибки, т. е., в терминологии многосеточного метода, слаживатель. Если "низкочастотные", то мы получим корректор, который давит гладкую часть ошибки. Применение FF - разложений позволяло достичь для модельных задач независимости скорости сходимости от числа узлов сетки при выборе числа разложений пропорциональным логарифму размера блока.

К. Вагнер продолжил исследования в этом направлении и построил, также с использованием тестовых векторов, так называемое, касательное фильтрующее разложение TFF (tangential filtering decomposition), действующее на ошибку аналогично FF-разложению. Матрицы неполного блочного разложения предлагалось строить по рекуррентным формулам

Ti = A, fi = Di + Qi,i-1fi^Qihi-Qi!i1Ui-LiQi^i (г >2), где компоненты "матриц преобразования" ©у находятся из условий

•.i-i^-i - Li^frJ^Q^fi^ - = 0.

Буздин А. А. в [35] показал, что для построения TFF-разложений можно обойтись без тестовых векторов. Идею их построения можно проиллюстрировать на следующем примере. Для модельной задачи блоки Tj полного блочного разложения можно представить как функции от матрицы

Т{ = L^Fi(C)L^ где С = a Fi(А) - некоторые рациональные функции. Следуя [35] и [37], мы получим простейшее' неполное блочное разложение матрицы К для модельной задачи, если заменим функции от матриц Fi(C) их линейными аппроксимациями. Если заменить функции Fi(А) на линейные функции, отвечающие касательным, проходящим через точки (А^, Fi(X^)), то мы получим касательное разложение, отвечающее параметру А^. Если заменить эти функции на секущие, проходящие через точки (A^i^A^)) и то мы получим, так называемое, двухчастотное разложение.

Для построения касательного и двухчастотного разложений для немодельных задач понятие тестовых векторов используется, но лишь как один из возможных способов определения параметров разложений. Преимуществом касательного разложения перед частотно-фильтрующим касательным разложением Вагнера является то, что для его реализации достаточно хранить только набор скалярных величин. Помимо этого, упрощается задача поиска параметров разложений. Отметим, что для модельных задач FF-, TFF- и касательное разложения совпадают, если в качестве тестовых векторов взять собственные вектора обобщенной задачи на собственные значения De = ALe.

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

Так как блоки неполного блочного разложения Тг являются аппроксимациями блоков полного блочного разложения Тг-, то представляет интерес выяснение достаточных и лег-копроверяемых условий существования полного блочного разложения. Хорошо известны условия типа "диагонального преобладания" [22]. Более мягкие условия были доказаны в [11] и приведены в [13] и [14]. В первой главе настоящей работы доказывается, что достаточным условием существования полного блочного разложения для блочной трех-диагональной матрицы является существование обычного LU-разложения для для трех-диагональной матрицы, элементами которой являются значения норм блоков исходной матрицы.

Были проведены как численные, так и теоретические исследования скорости сходимости построенных касательных и двухчастотных разложений. Они показали, что они для модельных задач дают скорость сходимости 1 — О (/г2/3), а при использовании в МСГ 1 — Эти результаты были известны ранее лишь для простейшей модельной задачи.

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

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

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

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

Рассмотренные методы формально переносятся на трехмерные задачи. В отличие от двумерных задач, когда для обращения блоков Т{, являющихся трехдиагональными матрицами, эффективен метод прогонки, при решении трехмерной задачи возникает необходимость обращать "двумерные" блоки. Обращение этих блоков можно приближенно реализовать, например, при помощи двумерных вариантов тех же методов. Однако можно существенно сократить объем вычислений, используя для решения двумерных задач не последовательности разложений, а лишь по одному разложению. Подробно реализация этого подхода изложена во второй части четвертой главы. Также там описан способ выбора оптимальных параметров разложений для трехмерной и возникающих двумерных задач. Численные исследования показали, что значения скорости сходимости для трехмерной задачи близки к значениям для двумерной, причем и для задач с переменными коэффициентами.

Для реализации изложенных ранее в [35], [37], [61], [62], [63], [65] и др. методов требовалось, чтобы блоки матрицы системы были квадратные и состояли из одинакового числа элементов. Методы, предложенные в настоящей работе свободны от этого ограничения. Они показали высокую скорость сходимости для задач с разным числом узлов в блоках. В качестве примеров были рассмотрены задача Дирихле для уравнения Пуассона в треугольнике, L - образной области и в многосвязной области - квадрате с "отверстием" при различных способах выбора параметров.

Другим способом увеличения скорости сходимости неполных блочных разложений является улучшение способа аппроксимации блоков Tj полного блочного разложения.Наиболее просто идею метода можно описать на примере модельной задачи, когда матрица системы уравнений К и = /, и, / € RTlXm имеет вид К = blocktridiag{—L, D, —L}, где D,L > О,D ^ 2L. Основной идеей улучшения способа аппроксимации блоков Tj является приближение функций Fi(C) не линейными, а рациональными функциями от матрицы С. Для этого каждой из функций от матрицы Fi{C) сопоставляется функция Fi(x) и приближается рациональной функцией вида

Fi{x) = lf{x)/Q${x), где Pl\x),Qm(x)— некоторые полиномы степени L и М соответственно. Для однозначного определения каждой из функций Fi(x) требуется, чтобы в некотором количестве точек Xi (I = 1,., Np) значения Ft(x) и ее производных совпадали со значениями приближаемой функции и ее производных в тех же точках. Для однозначности общее количество условий должно равняться N = М + L + 1. Построенному аппроксиманту Ft(x) ставится в соответствие рациональная функция от матрицы Fi(C) = Pl\C)(Qm(C))~1 .

В пятой главе работы рассматриваются различные виды апроксимантов в зависимости от соотношения степеней полиномов Pl(x) и Qm(x) и видов условий (задача Коши-Якоби, когда задаются только значения функции в N точках, и обобщенная задача Паде). Исследуется корректность предложенных алгоритмов для рассмотренных в работе модельных задач. Численно выясняется, использование каких интерполяций является наиболее эффективным, а именно, при каком соотношении степеней числителя L и знаменателя М достигается наиболее высокая скорость сходимости разложений. Особо выделяются обобщенное касательное разложение, соответствующее задаче, когда в точках заданы значения функции и ее первой производной и М-частотное разложение, соответствующее задаче Коши-Якоби. Рассматривается задача о выборе параметров разложений, обеспечивающих наибольшую скорость сходимости.

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

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Васильева, Екатерина Алексеевна

Все выводы, касающиеся поведения оценки скорости сходимости касательного разложения, справедливы и для двухчастотного. Подтвердим их аналогичными численными результатами. Рассмотрим задачу Дирихле для уравнения Пуассона в единичном квадрате. В таблицах 3.5-3.7 представлены теоретические оценки т] скорости сходимости и оптимальные параметры ш®, и^ = 4sin2 ^н+Т) (У — 1) 2) двухчастотного разложения для трех случаев: п = ш, п = 64, п — 256.

Заключение

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

Теоретически и численно была исследована скорость сходимости этих разложений. Проведенные исследования показали высокую эффективность этих методов для решения модельных задач (краевые задачи для уравнения Пуассона, для анизотропного уравнения диффузии, уравнения с разрывными коэффициентами). Результаты исследований показали, что касательное и двухчастотное разложения для модельных задач дают скорость сходимости 1 — 0(h2/3), а при использовании в МСГ 1 — О (/г1/3). Эти результаты были известны ранее лишь для простейшей модельной задачи.

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

Так как блоки неполного блочного разложения являются аппроксимациями блоков полного блочного разложения, то был рассмотрен вопрос о достаточных и легко проверяемых условиях существования полного блочного разложения. Было показано, что достаточным условием существования полного блочного разложения для блочной трехдиагональной матрицы является существование обычного LU-разложения для трехдиагональной матрицы, элементами которой являются значения норм блоков исходной матрицы.

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

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

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

Численные исследования показали, что значения скорости сходимости для рассмотренных трехмерных задач близки к значениям для двумерных, причем это верно и для задач с переменными коэффициентами.

Для применения методов касательного и двухчастотного разложения обычно требовалось (см., напр., [35], [37], [65]), чтобы все блоки матрицы системы К были квадратными. В работе предложены варианты этих методов, свободные от этого ограничения. Для рассмотренных задач с разным числом узлов в блоках таких, как задача Дирихле для уравнения Пуассона в треугольнике, L-образной области и в многосвязной области -квадрате с "отверстием", эти методы показали высокую скорость сходимости.

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

Для модельной задачи получены теоретические и практические оценки скорости сходимости при различных соотношениях степеней числителя и знаменателя рационального аппроксиманта. Оказалось, что если число точек, по которым строится аппроксимант равно 2М, то это аппроксимант вида [М — 1/М], а если 2М+1, то вида [М/М]. В этих случаях для реализации одной итерации метода р—го порядка для модельной задачи требуется выполнить р прогонок, которые могут быть выполнены параллельно.

Так как для реализации одной итерации разложения М—го порядка требуется примерно в М раз больше арифметических действий, чем для реализации одной итерации касательного разложения, то с целью сравнения эффективности разложений различных порядков значения скорости сходимости были пересчитаны в расчете на одну итерацию касательного разложения. Анализ полученных данных показал, что применение вместо касательного разложения разложений более высокого порядка резко увеличивает эффективность метода. Отметим однако, что различия между разложениями порядка М ^ 2 не столь значительны, как между разложениями первого и второго порядков. Аналогичная зависимость эффективной скорости сходимости от порядка разложения имеет место и для 2М— частотных разложений, связанных с аппроксимациями Коши-Якоби.

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Васильева, Екатерина Алексеевна, 2008 год

1. Аткинсон Ф. Дискретные и непрерывные граничные задачи. Пер. с англ. И. С. Иохви-дова и Г. А. Каральник. Под ред. и с доп. И. С. Каца и М. Г. Крейна. Предисловия И. С. Крейна и др.] М.: Мир, 1968. — 749 с.

2. Ахиезер Н. И. Классическая проблема моментов и некоторые вопросы анализа, связанные с нею. М.: Физматгиз, 1961 — 310 с.

3. Бейкер Дж, мл., Грейвс Моррис П. Аппроксимации Паде. 1. Основы теории. 2. Обобщения и приложения. Пер. с англ. - М.: Мир, 1986. - 502 е., ил.

4. Петров И. В., Лобанов А. И. Лекции по вычислительной математике. — М.: Интернет-Университет Информационных технологий. — 2006. — 523 с.

5. Буздин А. А., Васильева Е. А. Об одном варианте метода неполного блочного разложения / / Вестник Калининградского Государственного Университета. — 2005. — Вып. 1-2. Сер. Информатика и телекоммуникации. — с. 70-76.

6. Буздин А. А., Васильева Е. А. Неполное блочное разложение, основанное на аппроксимациях Паде// Математическое моделирование. — 2006. — Т. 18. — N 4. — с. 89-99.

7. Буздин А. А., Васильева Е. А., Латышев К. С. О последовательностях двухчастотных разложений // Вестник Калининградского Государственного Университета. — 2006. — Вып. 10. — Сер. Физико математические науки. — с. 64-69.

8. Булеев Н. И. Численный метод решения двумерных и трехмерных уравнений диффузии. Математический сборник — 1960. — Вып. 51. — с. 227-238.

9. Булеев Н. И. Пространственная модель турбулентного обмена. М: Наука, 1989. — 343 с.

10. Воеводин В. В., Кузнецов Ю. А. Матрицы и вычисления. — М.: Наука, 1984. — 318 с.

11. Джангава П. В. Об одном свойстве коэффициентов метода "прогонки" // Тр. Вычислительного центра ГрАН СССР. — Тбилиси, 1976. — с. 5-13.

12. Еремин А. Ю., Колотилина Л. Ю. Методы неполных блочных разложений для матриц сложной структуры. — Записки научных семинаров ленинградского отделения математического института им. Стеклова АН СССР —1987. — Том 159. — с 5-22.

13. Ильин В. П. Методы неполной факторизации для решения алгебраических систем. — М.: Наука. Физматлит, 1995. — 286 с.

14. Ильин В. П. Методы конечных разностей и конечных объемов для эллиптических уравнений. — Новосибирск: Издательство Института математики, 2000.— 344 с.

15. Кац И. С., Крейн М. Г. IZ-функции — аналитические функции, отображающие верхнюю полуплоскость в себя. Дополнение 1 к 1.

16. Марчук Г. И. Методы расчета ядерных реакторов. — М.: Атомиздат, 1958. — 667 с.

17. Марчук Г. И. Методы вычислительной математики. — М.: Наука, 1977.— 455 с.

18. Михлин С. Г. Вариационные методы в математической физике. — М.: Наука, 1973.

19. Крейн М. Г., Нудельман А. А. Проблема моментов Маркова и экстремальные задачи. Идеи и проблемы П. JI. Чебышева и А. А. Маркова и их дальнейшее развитие. — М.: Наука, 1973. — 552 с.

20. Ольшанский М. А. Лекции и упражнения по многосеточным методам. — М.: Физ-матлит — 2005. — 168 с.

21. Палло П. А. Метод касательного разложения для решения больших систем алгебраических уравнений: Дипломная работа. — Калининградский Государственный Университет, 2000.

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

23. Стилтьес Т. Исследования о непрерывных дробях! Под ред. Н. И. Ахиезера. — ОНТИ, 1936. — с. 1-154.

24. Фаддеев Д. К., Фадцеева В. Н. Вычислительные методы линейной алгебры. — СПб.: Лань, 2002. — 733 с.

25. Федоренко Р. П. Релаксационный метод решения разностных эллиптических уравнений. // Журнал выч. мат. и мат. физ. — 1961. — Т.1 — с. 922 927.

26. Федоренко Р. П. Итерационные методы решения разностных эллиптических уравнений. // Успехи математических наук — 1973. Том 28 — Вып. 2(170).

27. Федоренко Р. П. Приближенное решение задач оптимального управления. — М.: Наука, 1978. — 488 с.

28. Четверушкин Б. Н. Математическое моделирование задач динамики излучающего газа. — М.: Наука, 1985. — 304 с.

29. Шайдуров В. В. Многосеточные методы конечных элементов. — М.: Наука, 1989. — 288 с.

30. Элементы теории функций. Функции действительного переменного. Приближение функций. Почти-периодические функции. / Под ред. П. JI. Ульянова. — М.: Физматгиз, 1963. — 244 с.

31. Axelson О., Brinkkemper S., Il'in V. P. On some versions of incomplete block-mtrix factorization iterative methods. LAA 1984. — Vol. 58. — p. 3-15.

32. Axelson O., Polman B. A robust preconditioner based on algebraic substructuring and two-level grids // W. Hackbusch, ed., Robust multigrid methods, NNFM Bd.23, Vieweg-Verlag, Braunschweig, 1989.

33. Baker G. A. Jr. Essentials of Pade Approximants. — New York: Academic Press, 1975.

34. Baker G. A. Jr. The Pade approximant and some related generalisations. // G. A. Backer, Jr., and J. L. Gammel (eds), The Pade Approximant in Theoretical Physics, Academic Press, New York. 1970. — p. 1-39.

35. Buzdin A. Tangential decomposition // Computing. — 1998. — Vol. 61. — p. 257-276.

36. Buzdin A., Logashenko D. Incomplete Block Triangular Decompositions of order I// Computing. 2000. - Vol. 64. - p. 69 - 95.

37. Buzdin A., Wittum G. Two-Frequency Decomposition. // Numerische Mathematik. — 2004. — Vol. 97. p. 269-295.

38. Cauchy M. A. L. Cours d'analyse. De l'Ecole Royale Polytechnique, premiere partie, L'Imprimerie Royale, Paris, 1821.

39. Gander M. J., Nataf F. AILU: A Preconditioner Based on the Analytic Factorization of the Elliptic Operator // Numerical Linear Algebra with Applications. — 2000. — N. 7. (7-8) — p. 505-526.

40. Gustafsson I. A class of first order factorisation methods. // BIT. — 1978. — Vol. 18. — p. 142-156.

41. Hackbusch W. Multi-grid methods snd Applications. — Berlin, Heidelberg, Springer-Verlag, 1985 — 382 p.

42. Hackbusch W. Iterative solution of large sparse systems of equations. — New York, Springer-Verlag, 1993 — 382 p.

43. Hemker P. W. Multigrid methods for problems with a small parameter in the highest derivate. In D. F. Griffiths, ed., Numerical analysis, Proceedings, Dundee 1983. Lecture Notes in Math. 1066, Springer-Verlag, Berlin, 1993.

44. Herglotz G. Uber Potenzreihen mit positiven reelen Teil im Einheitskreise. j / Ber. Verh. Sachs Acad. Wiss. Leipzig. — 1911 — Vol. 63. — p. 501-511.

45. Incomplete Decomposition (ILU) — Algirithms, Theory, and Applications. — Proceedings of the Eighth GAMM Seminar, Kiel, January 24-26, 1992. Edited by Hackbusch W. and Wittum G.— 231 p.

46. Jacobi C. G. J. Uber die Darstellung einer Reihe gegebner Werte durch eine gebrochene rationale Function // J. ftir Reine Angewandte Math. — 1846. — Vol. 30. — p. 127-156.

47. Jennings A., Malik G. M. Partial elimination. // J. IMA. — 1977. — Vol. 20. — p. 307-316.

48. Kershow D. The incomplete Cholesky conjugate gradient method for iterative solution of systems of linear equations. // J. Сотр. Phys — 1978. — Vol. 26. — N 1. — p 43-45.

49. Kettler R. Analysis and comparison of relaxation schemes in robust multigrid and preconditioned conjugate gradient methods. // W.Hackbusch und U.Trottenberg, ed. — Multigrid methods, Proceedings, Koln-Porz, 1981.

50. Lukacs. Verscharfung der ersten Mittelwertsatzes der Integralrechnung fur rationale Polynome 11 Math. Zeitschrft.— 1918.— N 2. — p. 229-305.

51. Meijerink J. A., Van der Vorst H. A. An iterative solution method for linear systems of which the coefficient matrix is a symmetric M matrix. // Math. Сотр. — 1977. — Vol. 31. - p. 148-162.

52. Meijerink J. A. Iterative methods for the solution of linear equations based on incomplete factorization of the matrix. Shell Publ. 643, Rijswijk, 1983.

53. Nuttall J. Convergence of Pade approximants for the Bethe-Salpeter amplitude. // Phys. Rev. — 1967. — Vol. 157. p. 1312 - 1316.

54. Riesz F. Sur certaines systemes singulieres d'equations integrales. // Ann. Ec. Norm. — 1911. — N. 28.

55. Stieltjes T. Recherches sur les fractions continues // Ann. de Toulouse. — 1984. — Vol. VIII. p. 1-122; 1895. - Vol. IX. - p. 1-47.

56. Stoer J. Uber zwei Algorithmen zur Interpolation mit rationalen Functionen // Num. Math. 1961. - N. 3. - p. 285-304.

57. Stoer J., Bulirsch R. Introduction to numerical analysis. — New York, Springer-Verlag, 1992.

58. Thiele T. N Interpolationsrechnung. — Teubner, 1909.

59. Varga R. Matrix iterative analysis. — Prentice-Hall, Englewood Cliffs, 1962.

60. Varga R. Factorization and normalized iterative methods. — Boundary problems in differential equations (Hrg.: R. E. Langer). —- University of Wisconsin Press, Madison. 1960. - p. 127-142.

61. Wagner C. Frequenzfilternde Zerlegungen fur unsymmetrische Matrizen und Matrizen mit stark variierenden Koeffizienten. ICA-Preprint 95/7 , Stuttgart, 1995.

62. Wagner C. Tangential frequency filtering decompositions for symmetric matrices. // Numer. Math. — 1997. Vol. 78. - p. 119-142.

63. Wagner C. Frequency filtering decompositions for unsymmetric matrices. // Numer. Math. 1997. - Vol. 78. - p. 143-163.

64. Wagner C., Wittum G. Adaptive filtering. // Numer. Math. — 1997. — Vol.78. — p. 305-328.

65. Wittum G. Filternde Zerlegungen Schnelle Loser fiir grofie Gleichungssysteme. — Teubner Skripten zur Numerik, Stuttgart, Teubner-Verlag, Band 1, 1992.