Неполные блочные разложения, основанные на аппроксимантах Паде

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

АВТОРЕФЕРАТ

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

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

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

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

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

1. Общая характеристика работы

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

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

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

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

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

2. Содержание работы

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

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

Теорема. Пусть блочная трехдиагональная матрица системы K имеет вид K = blocktridiag{-L_i-₁, D_i, -U_i}, где блоки D_i , L_i , D_i регулярные. Обозначим через ||·|| какую-либо из матричных норм, а через б_i = ||U_i||, в_i = || L_i||. Пусть также для трехдиагональной матрицы Якоби J = tridiag {в_i-₁, 1, б_i} существует LU - разложение J = L D -¹U, а для элементов d_i, i>1 диагональной матрицы D выполняются условия d_i = 1---б_i в_i/d_i-₁ > 0. Тогда для матрицы K такого вида существует ее полное блочное разложение.

K =--(L + T) T-¹ (U + T),

где L=blocktridiag {-L_i, 0, 0}, U = blocktridiag {0, 0, -U_i}, T = blockdiag {T_i}. Матрица K регулярная. Блоки T_i полного блочного разложения удовлетворяют оценке ||D_i|| ? 1/d_i.

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

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

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

T_i = L^1/2 F_i(C) L^1/2, где C =--L-^1/2 D L-^1/2,

а F_i - некоторые рациональные функции. Мы получим простейшее неполное блочное разложение матрицы K для модельной задачи, если заменим в последнем разложении функции от матриц F_i(C) их линейными аппроксимациями. При замене функций F_i(л) на линейные функции, отвечающие касательным, проходящим через точки (л⁽¹⁾, F_i(л⁽¹⁾)), мы получим касательное разложение, отвечающее параметру л⁽¹⁾. Если заменить эти функции функциями, отвечающими секущим, проходящим через точки (л⁽¹⁾, F_i(л⁽¹⁾)) и (л⁽²⁾, F_i(л⁽²⁾)), то мы получим, так называемое, двухчастотное разложение. Впервые эти разложения были изучены Г. Виттумом и А.А. Буздиным. В работе даны определения касательного и двухчастотного разложений для модельных задач, рассмотренных в первой главе и являющихся обобщениями задач, исследованных этими авторами. Приведены доказательства существования этих разложений в тех случаях, когда существуют полные блочные разложения для тех же матриц. Исследованы условия существования этих разложений, в частности, доказано их существование для M - матриц.

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

Определение. Касательное (двухчастотное) разложение блочной трехдиагональной матрицы K = blocktridiag {-L_i-₁, D_i, -U_i}, для заданного тестового вектора e⁽¹⁾ Rⁿ (векторов e⁽¹⁾, e⁽²⁾ Rⁿ) имеет вид

M = (L + ) (L^T + ),

где L - нижняя блочнотреугольная часть K, матрицы - блочнодиагональные матрицы вида = blockdiag {, … , }, блоки касательного разложения

=D₁, = D_i + ()² - (L_i?1 + ), i>1,

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

=D₁, = D_i + - ( + ) L_i?1, i>1,

а параметры вычисляются по формуле =(L_i e^(l), e^(l))/(e^(l),e^(l)), l=1,2.

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

в [0,1] Ч[0,1],

где коэффициент (уравнение Пуассона) и . Заметим, что во втором случае дифференциальный оператор этого уравнения является вырождающимся эллиптическим оператором. Численное решение задач подобного рода обычно связано с большими трудностями. Как видно из таблицы, и в этом случае построенные методы показывают высокую скорость сходимости. В таблице представлены средние численные значения скорости сходимости _cg касательных разложений, использованных в качестве предобуславливателя в методе сопряженных градиентов (МСГ), рассчитанные за 50 итераций. Значения скорости сходимости для уравнения Пуассона обозначены через _{cg, poiss}, а для уравнения с коэффициентом через _{cg, exp}. Через h здесь и далее обозначен шаг сетки.

Таблица 1

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

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

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

В четвертой главе рассматриваются последовательности касательных и двухчастотных разложений и задача о выборе оптимальных параметров этих разложений. На основе анализа ее теоретического и численного решения для модельной задачи предложен простой и дающий высокую скорость сходимости способ выбора параметров для задач с переменными коэффициентами. Например, выбирая число разложений k как, например, k = = log₂ (1/h) и задавая тестовые вектора для последовательности касательных разложений как e^(l) = (sin (2^l-¹jh))_j=1,…,n, мы получим следующую скорость сходимости для рассмотренной выше задачи Дирихле. В таблице через ₁ обозначена, так называемая, эффективная скорость сходимости составной итерации из k разложений. Ее значение вычисляется как .

Таблица 2

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

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

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

Таблица 3

В конце четвертой главы приведены результаты применения предложенных методов к задачам с разным числом узлов в блоках. В качестве примеров были рассмотрены задача Дирихле для уравнения Пуассона в треугольнике, L - образной области и в многосвязной области - квадрате с «отверстием» при различных способах выбора параметров. Для всех рассмотренных задач они показали высокую скорость сходимости. В таблице представлены значения скорости сходимости последовательностей касательных разложений для задачи Дирихле для уравнения Пуассона в L - образной области, представляющей собой единичный квадрат с «отверстием» 0.5? x, y ? 1.

Таблица 4

Другим способом увеличения скорости сходимости неполных блочных разложений, описанным в начале пятой главы, является улучшение способа аппроксимации блоков T_i полного блочного разложения. Наиболее просто идею метода можно описать на примере модельной задачи, когда матрица системы уравнений K u = f, u, f R^nЧm имеет вид

K =-- blocktridiag {- L, D, -L}, где D, L > 0, D 2L.

Основной идеей улучшения способа аппроксимации блоков полного блочного разложения

T_i = L^1/2 F_i(C) L^1/2,

где C= L^-1/2 D L^-1/2, является приближение функций F_i(C) не линейными, а рациональными функциями от матрицы C. Для этого каждой из функций от матрицы F_i(C) сопоставляется функция F_i(x) и приближается рациональной функцией вида

(x) = (x) / (x),

где (x), (x) - некоторые полиномы степени L и M соответственно. Для однозначного определения каждой из функций (x) достаточно потребовать, чтобы в некотором количестве точек x_l (l = 1, …, N_p) ее значения и значения ее производных совпадали со значениями приближаемой функции и ее производных в тех же точках. Для однозначности общее количество условий должно равняться N = M + L + 1. Построенному аппроксиманту (x) ставится в соответствие рациональная функция от матрицы (C) = (C) .

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

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

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

Теорема. Обозначим через T^i,j(x) секущие, проведенные через точки (x_i, f_i) и (x_j, f_j) кривой f(x), а через T^i,i(x) - касательные к той же кривой в точках (x_i, f_i) и определим вектор 1 = (1, 1, …,1)^T. Пусть, далее

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

[M / M-1] P_M / Q_M-1 = (1^T B^-1 1)^-1.

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

Определение. Пусть K симметричная блочная трехдиагональная матрица вида K = blocktridiag {-L_i-1, D_i, -U_i} и пусть заданы M тестовых векторов e⁽¹⁾,…, e^(M) Rⁿ. Тогда для матрицы K можно определить обобщенное касательное разложение порядка M

M = (L + ) ( + L^T) ,

где = blockdiag{} - матрица, состоящая из блоков

Здесь - касательные разложения, отвечающие тестовым векторам e^(l) (l = 1, …, M), а , k l - двухчастотные разложения, отвечающие тестовым векторам e^(k), e^(l) (k, l = 1, …, M).

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

Таблица 5

Для того, чтобы корректно сравнить значения скорости сходимости разложений различных порядков, вычислялась эффективная скорость сходимости каждого из разложений (для разложения k - го порядка = = ). Численные исследования показали, что наиболее существенный рост скорости сходимости дает увеличение порядка разложения с первого на второй (например, при h = 1/256 эффективная скорость сходимости изменяется с 0.85 до 0.59). Дальнейший рост порядка разложения не приводит к сильному увеличению эффективной скорости сходимости (при h = 1/256 и k = 3, 4 значения эффективной скорости сходимости соответственно равны 0.44 и 0.37).

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

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

3. Основные результаты и научные выводы

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

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

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

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

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

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

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

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

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

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

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

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

блочный разложение аппроксимант матричный

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

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

1. Васильева Е.А. (совместно с Буздиным А.А.). Неполное блочное разложение, основанное на аппроксимациях Паде. // Математическое моделирование, 2006. Т. 18 N 4. С. 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.

Размещено на Allbest.ru