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

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

Васильева Екатерина Алексеевна

НЕПОЛНЫЕ БЛОЧНЫЕ РАЗЛОЖЕНИЯ, ОСНОВАННЫЕ НА АППРОКСИМАНТАХ ПАДЕ

05.13.18 — математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Калининград - 2008

Работа выполнена в Российском государственном университете имени И. Канта

Научный руководитель - доктор физико-математических наук,

профессор

Латышев Константин Сергеевич Официальные оппоненты - доктор физико-математических наук,

профессор

Петров Игорь Борисович - кандидат физико-математических наук, доцент

Гущин Олег Андрианович Ведущая организация - Институт математического

моделирования РАН

Защита состоится ^■ссь^и^сй^- 2008 г. в ^^ часов на заседа-

нии диссертационного совета К 212.084.10 по защите диссертаций на соискание ученой степени кандидата физико-математических наук в Российском государственном университете имени И. Канта по адресу: г. Кали нинград, ул. А. Невского, 14

С диссертацией можно ознакомиться в библиотеке Российского государственного университета имени И. Канта

Автореферат разослан 3/ января 2008 г.

Ученый секретарь

диссертационного совета ¿¿'¿З^^ Токарь В. Г.

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

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

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

Научная новизна работы. Построены новые предобуславливатели на основе МНБФ Решена задача выбора оптимальных параметров неполных блочных разложений для модельных задач и предложен эффективный способ выбора параметров для задач с переменными коэффициентами На основе новых представлений для рациональных аппроксимантов построены и исследованы неполные блочные разложения высоких порядков

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

размером вплоть до 1000 х 1000 не превышает 0 6 в пересчете на одно разложение

Апробация работы. Основные положения диссертации докладывались и обсуждались на Международной конференции, приуроченной к 200-летию К. Г Якоби (4-8 апреля 2005 г., Калининград)

Публикации. Материалы диссертации отражены в 5 печатных работах.

Объем работы. Диссертация состоит из введения, пяти глав, заключения и списка литературы, включающего 65 наименований. Объем диссертационной работы - 184 страницы, основной текст изложен на 155 страницах. Количество рисунков в основном тексте - 15, количество таблиц в основном тексте - 38

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

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

Одним из методов решения систем алгебраических уравнений является метод Гаусса или, как его вариант, Ш - разложение Если разбить матрицу системы на блоки, то можно построить блочное Ьи - разложение, которое мы в дальнейшем будем называть полным разложением В первой главе исследован вопрос существования полного блочного разложения для блочных трехдиагональных матриц Основным результатом первой части главы является следующая теорема

Теорема. Пусть блочная трехдиагонстъная матрица системы К имеет вид К = Ыоскй-цЬгц^-Х,-/, Д -и,}, где блоки Д е 11"'х\ I, е , Д регулярные Обозначим через ) | ] | какую-либо из матричных норм, а через а, - 11Д"1 Щ ¡, Д = 11Д+1 | Пусть также для трехдиагоналъной матрицы Якоби J = 1пёт£ {/?,_;, 1, а,} существует Ш - разложение I = £ Ю а для элементов й?„ г>1 диагональной матрицы !Ю выполняются условия <з?, =

= 1 - а,р/с1,-1 > 0 Тогда для матрицы К такого вида существует ее полное блочное разложение

К = (Ь + Т)Т'(и + Т), где Ъ=Ь1оск1пс11а§ {-Ь„ 0, 0}, и = blocktndlag {О, О, -Щ, Т = ЫосксЬав Ш Матрица К регулярная Блоки Т, полного блочного разложения удовлетворяют оценке | | Т~х Д11 < 1М,

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

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

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

примере Известно, что для модельной задачи блоки Т, полного блочного разложения представимы в виде функций от матрицы

Т, = I)'1 Р,(С) £1/2, где С = Ь~У2 В Ь~ю, а Р, - некоторые рациональные функции Мы получим простейшее неполное блочное разложение матрицы К для модельной задачи, если заменим в последнем разложении функции от матриц Р,(С) их линейными аппроксимациями При замене функций на линейные функции, отвечающие касательным, проходящим через точки (А(|), мы получим касатель-

ное разложение, отвечающее параметру Я(1) Если заменить эти функции функциями, отвечающими секущим, проходящим через точки (А(1), /\(/(1))) и (Л(2>, Р,(Л(2})), то мы получим, так называемое, двухчастотное разложение Впервые эти разложения были изучены Г Виттумом и А А Буздиным В работе даны определения касательного и двухчастотного разложений для модельных задач, рассмотренных в первой главе и являющихся обобщениями задач, исследованных этими авторами. Приведены доказательства существования этих разложений в тех случаях, когда существуют полные блочные разложения для тех же матриц Исследованы условия существования этих разложений, в частности, доказано их существование для М - матриц

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

Определение. Касательное (двухчастотное) разложение блочной трехдиагоналъной матрицы К = ЫоскШс1щ§ {—Ь,^, Д, —V,}, для заданного тестового вектора ет е (векторов е°\ е(2) е Я") имеет вид М = (Ь+ Т) Т-,(1/+ Т),

где Ь блочнотреугольная часть К, матрицы Т - блочнодиаго-

нальные матрицы вида Т - Ыоскёш£ {7] , , Тт }, блоки касательного разложения

% = Д + (М<1>)2 7^1 - + />;,

блоки двухчастотного разложения

%=Оь Тг= Д + - (/£} +

а параметры /л\1) вычисляются по формуле /и\1)={Ь1е(1), е(1))/{ Т^®,е(1)), 1=1,2

В третьей главе приводятся как численные, так и теоретические исследования скорости сходимости описанных во второй главе касательных и двухчастотных разложений, которые были известны ранее лишь для простейшей модельной задачи Эти исследования показали, что применение рассмотренных разложений при использовании их в качестве предобу-славливателей дает скорость сходимости 1 - 0(/г2/3) (й - шаг сетки), а в сочетании с методом сопряженных градиентов 1 - 0(й1/3) Теоретические и численные результаты, представленные в работе, доказывают высокую эффективность этих методов как для решения модельных задач (краевые задачи для уравнения Пуассона, для анизотропного уравнения диффузии, уравнения с разрывными коэффициентами), так и для задач с переменными коэффициентами Приведем в качестве примера значения скорости сходимости касательного разложения для задачи Дирихле с однородными граничными условиями для уравнения

У(^,у)Уи) = / в [0,1] х[0,1], где коэффициент ф{х,у) = 1 (уравнение Пуассона) и ф(х,у) = 1 - ехр(-ху) Заметим, что во втором случае дифференциальный оператор этого уравнения является вырождающимся эллиптическим оператором Численное решение задач подобного рода обычно связано с большими трудностями

Как видно из таблицы, и в этом случае построенные методы показывают высокую скорость сходимости В таблице представлены средние численные значения скорости сходимости касательных разложений, использованных в качестве предобуславливателя в методе сопряженных градиентов (МСГ) Значения скорости сходимости для уравнения Пуассона обозначены через rjcg, poissa а для уравнения с коэффициентом ф(х,у) = 1 - ехр(-ху) через î)c& схр Через h здесь и далее обозначен шаг сетки

h 1/16 1/32 1/64 1/128 1/256 1/512 1/1024

7cg, exp rjcg, poiss 0 13 0 08 0 18 0 13 0 27 0 23 0 36 0 32 0 46 0 42 0 55 0 53 0 64 0 62

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

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

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

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

В четвертой главе рассматриваются последовательности касательных и двухчастотных разложений и задача о выборе оптимальных параметров этих разложений На основе анализа ее теоретического и численного решения для модельной задачи предложен простой и дающий высокую скорость сходимости способ выбора параметров для задач с переменными коэффициентами Например, выбирая число разложений к как, например, к = = 1о§2 {НИ) и задавая тестовые вектора для последовательности касательных разложений как (вш „, мы получим следующую скорость сходимости для рассмотренной выше задачи Дирихле В таблице через г] 1 обозначена, так называемая, эффективная скорость сходимости составной итерации из к разложений Ее значение вычисляется как {[г]

к 1/16 1/32 1/64 1/128 1/256 1/512 1/1024

Л 3 34е-4 8.19е-4 1 36е—3 1.87е-3 2 31е-3 2 68е-3 3 00е-3

т 0 14 0 24 0 33 0 41 0 47 0 52 0 56

Из таблицы видно, что даже для сетки 1024 х 1024 значение эффективной скорости сходимости последовательности касательных разложений не превосходит 0 6

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

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

И 1/16 1/32 1/64 1/128

п 7 91е-4 1 90е-3 3.11е—3 4 19е-3

ГЦ 0 17 0 29 0.38 0 46

В конце четвертой главы приведены результаты применения предложенных методов к задачам с разным числом узлов в блоках В качестве примеров были рассмотрены задача Дирихле для уравнения Пуассона в треугольнике, Ь - образной области и в многосвязной области - квадрате с «отверстием» при различных способах выбора параметров. Для всех рассмотренных задач они показали высокую скорость сходимости В таблице представлены значения скорости сходимости последовательностей касательных разложений для задачи Дирихле для уравнения Пуассона в Ь - образной области, представляющей собой единичный квадрат с «отверстием» 0 5< л:, у < 1

н 1/16 1/32 1/64 1/128 1/256 1/512 1/1024

п 313е-4 3 90е-4 943е-4 1 70е-3 2 52е-3 3 ЗОе-З 3 97е-3

т 0 13 0.21 031 0.40 0 47 0 53 0 58

Другим способом увеличения скорости сходимости неполных блочных разложений, описанным в начале пятой главы, является улучшение способа аппроксимации блоков Т, полного блочного разложения Наиболее просто идею метода можно описать на примере модельной задачи, когда матрица системы уравнений К и и,/е11к>"" имеет вид К = = blocktrldlag {- £, Д -¿}, где Д Ь > О, I) > 2Ь Основной идеей улучшения способа аппроксимации блоков полного блочного разложения Т, -= I1'2 Ьш, где С= Ь~ш, является приближение функций не линейными, а рациональными функциями от матрицы С Для этого каждой из функций от матрицы Р,(С) сопоставляется функция Р^х) и приближается рациональной функцией вида

1{Х)=р[Нх)/ а^(х), где Р1'\х), (¿ц (х) - некоторые полиномы степени Ь и М соответственно Для однозначного определения каждой из функций /:(х) достаточно потребовать, чтобы в некотором количестве точек X/ (1=1, , ее значения и значения ее производных совпадали со значениями приближаемой функции и ее производных в тех же точках. Для однозначности общее количество условий должно равняться N = М + Ь + 1 Построенному аппрок-симанту (х) ставится в соответствие рациональная функция от матрицы

£(&= Р1ЧС) (2^(С)'Г

Исследуются различные виды аппроксимантов в зависимости от количества и типа заданных условий Теоретические и практические исследо-

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

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

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

Теорема. Обозначим через Т'(х) секущие, проведенные через точки (х, А и (хр кривой Дх), а через Т'!(х) — касательные к той же кривой в точках (.хи определим вектор 1 = (1,1,. ,1)т Пусть, далее

(Т11(х) Т12(х) Т2'\х) Т2'2(х)

Тм'\х)

Тм'м(х),

Тогда решение сформулированной аппроксимационной задачи имеет вид

1

[М/ М-1] = Ри/Ом-, = ВТ11У

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

Определение. Пусть К симметричная блочная трехдиагоналъная матрица вида К = Ыоскйкк^ Д, -1У,} и пусть заданы М тестовых

векторов е(Х\ , е IIй Тогда для матрицы К можно определить обобщенное касательное разложение порядка М

М = (ь + т<м))(т(Т(М)+ЬГЛ где Т(М) = Ыоскёщ§{ Т1{М)} — матрица, состоящая из блоков

Т<.м) _

Гт\Т

и

( г1-1

"2,1

г1,2 I

*2,2

М, 1

и

Здесь Т^1 - касательные разложения, отвечающие тестовым векторам е(1) (1=1, , М), а Т*'1, двухчастотныеразложения, отвечающие

тестовым векторам е(А>, (к, 1= 1, ,М)

Приведем значения скорости сходимости касательных разложений г}к) порядка к = 1, ,4 для задачи Дирихле с однородными граничными условиями для уравнения Пуассона

/г 1/32 1/64 1/128 1/256 1/512 1/1024

5 14е-1 6 51е-1 7 70е-1 8 46е-1 9 04е-1 9 45е-1

п(2) 6 96е-2 1 40е-1 2 31е-1 3 51е-1 4 68е-1 5.65е-1

п(ъ) 6 06е-3 1 88е-2 4 61е-2 8.70е-2 1.43е-1 2 04е-1

п{4) 5 27е-4 2 42е-3 7 64е-3 1 83е-2 3 55е-2 6 18е-2

Для того, чтобы корректно сравнить значения скорости сходимости разложений различных порядков, вычислялась эффективная скорость сходимости ?]\к) каждого из разложений (для разложения к - го порядка г/\к) =

= Численные исследования показали, что наиболее существенный

рост скорости сходимости дает увеличение порядка разложения с первого на второй (например, при к = 1/256 эффективная скорость сходимости изменяется с 0 85 до 0 59). Дальнейший рост порядка разложения не приводит к сильному увеличению эффективной скорости сходимости (при к = 1/256 и к = 3, 4 значения эффективной скорости сходимости соответственно равны 0 44 и 0 37)

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

В заключении кратко изложены результаты и научные выводы диссертационной работы

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И НАУЧНЫЕ ВЫВОДЫ

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

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

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

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

4 Решен вопрос выбора оптимальных параметров касательного и двух-частотного разложений для модельной задачи и предложен простой способ приближенного выбора параметров, позволяющий получить

высокую скорость сходимости и для задач с переменными коэффициентами

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

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

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

8 Рассмотрены системы уравнений с разным числом узлов в блоках такие, как задача Дирихле для уравнения Пуассона в треугольнике, Ь - образной области и в многосвязной области - квадрате с «отверстием» при различных способах выбора параметров Методы последовательностей касательных и двухчастотных разложений показали высокую скорость сходимости для этих задач

9 Построены неполные блочные разложения высоких порядков такие, как обобщенное касательное и М - частотное, доказана их корректность и решена задача выбора оптимальных параметров этих разложений для модельной задачи Для модельных задач были получены теоретические и численные оценки скорости сходимости Экспери-

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

10 Построены новые представления для рациональных аппроксимантов

11 Рассмотрены обобщения разложений высоких порядков на задачи с переменными коэффициентами и численно исследована их скорость сходимости

Слисок публикаций, отражающих основное содержание диссертации

Работы, опубликованные ведущих рецензируемых научных журналах, включенных в перечень ВАК

1 Васильева Е А (совместно с Буздиным А А ) Неполное блочное разложение, основанное на аппроксимациях Паде // Математическое моделирование, 2006 Т 18 N4 С 89-99

2 Васильева Е. А Применение касательного разложения для решения трехмерных краевых задач // Сборник трудов ИСА РАН Издательство URSS 2006 Том 18(1) С 84-97

Работы, опубликованные в прочих журналах

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

4 Васильева Е А. (совместно с Буздиным А А ) Об одном варианте метода неполного блочного разложения // Избранные вопросы современной математики Тезисы Международной конференции, при-

уроченной к 200-летию К Г Якоби (4-8 апреля 2005 г, Калининград ) Калининград Изд-во КГУ, 2005 5 Васильева Е А (совместно с Буздиным А А и Латышевым К С ) О последовательностях двухчастотных разложений // Вестник Калининградского Государственного Университета Вып 10 Сер Физико-математические науки, 2006 С 64-69

Екатерина Алексеевна ВАСИЛЬЕВА

НЕПОЛНЫЕ БЛОЧНЫЕ РАЗЛОЖЕНИЯ, ОСНОВАННЫЕ НА АППРОКСИМАНТАХ ПАДЕ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 21. 12. 07 г. Формат 60x90 Бумага для множительных аппаратов. Ризограф. Усл. печ. л. 1.0. Уч.-изд. л. 0,9. Тираж 80 экз. Заказ 202

Издательство

Российского государственного университета имени Иммануила Канта 236041, г. Калининград, ул. А. Невского, 14

Введение

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М— частотных разложений, связанных с аппроксимациями Коши-Якоби.

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

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

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

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

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

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

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.