Оптимальные модифицированные методы Якоби и Гаусса-Зейделя (релаксации)

В модифицированном методе Якоби в процессе итераций (3)(4) участвует матрица (10), (11) (раздел 1.10), причем матрица (4) с нулевой главной диагональю. Для методов Якоби и Гаусса-Зейделя в рассматриваемом случае трехдиагональной матрицы (12) коэффициенты следующие: , . Заданный вектор правой части . Для модифицированных методов:

, , , (20)

Таким образом, максимальное по модулю собственное число и радиус сходимости обычного метода Якоби получается из (13), (15) и (17) при и

, (21)

ОП для сходимости модифицированного метода Якоби и его спектральный радиус получаются из (18) при :

1. Для : ;

2. Для : ; (22)

Таким образом, для случая улучшения сходимости в модифицированном методе Якоби нет. Анализ формул (17) и (21) показывает, что, как правило, область сходимости метода Якоби больше (в пространстве переменных ), чем метода Ричардсона, кроме области , где обратная ситуация в случае . Анализ формул (18) и (22) показывает, что в переменных спектральные радиусы МОПИ и Якоби совпадают.

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

(23)

То есть

, (24)

где , , .

Если - коэффициенты обычной матрицы Якоби, то коэффициенты в модифицированном методе определяются, согласно (12) и (24), следующим образом

(25)

Эти коэффициенты участвуют в модифицированном процессе (8).

Матрица эквивалентного действия для модифицированного ГЗ-оператора может быть получена из (23)

(26)

Заданный вектор правой части в этом случае .

Заметим, что метод простой итерации (3) с модифицированным ГЗ-оператором (23), (24) полностью совпадает с методом последовательной релаксации [8, 1-7] в других обозначениях

, (27)

Рассмотрим спектр модифицированного ГЗ-оператора в трехдиагональном случае, а также условия сходимости простой итерации с его участием.

Переобозначим для простоты записи

(28)

Лемма 2. Детерминанты характеристического уравнения для ГЗ-оператора (23), (24) в трехдиагональном случае с учетом (20) удовлетворяют рекуррентной формуле

(29)

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

Раскладывая детерминант по последнему столбцу, получим . Здесь - детерминант, который отличается от тем, что последний его элемент равен вместо . Таким образом, и, подставляя это в , получим формулировку Леммы.

Например, при , характеристическое уравнение

или

Здесь ГЗ-оператор (24). Детерминант . Собственные числа в этом случае, принимая во внимание (27)

(30)

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

, (31)

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

а). б).

Рис.9. Поведение двух ветвей функции , для случаев (а) и (б) и определение ОП для метода релаксации

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

Из (31) следует, что значение для всех , что значительно шире, чем для обычного метода Гаусса-Зейделя, для которого из (30) при получаем два собственных значения , и спектральный радиус . Итак, отношение для и для .

Для случая рис.9, б и для него 0.366, 0.268, что свидетельствует о достаточно быстрой сходимости модифицированного ряда. При этом и обычный метод Гаусса-Зейделя не сходится.

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

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

Сделаем замену переменной на переменную

(32)

Заметим, что , если .

В результате, также как и в п.1, получаем выражения для детерминантов через многочлены от переменной : для четных и для нечетных , . Для этих многочленов и в силу Леммы 2 получается рекуррентная формула (1.6), а также рекуррентные формулы (7) отдельно для или .

Далее, замена переменной (8) переводит многочлены в многочлены Чебышева второго рода (9), (10) с корнями на интервале .

Возвращаясь к переменной с помощью (22) и учитывая (28), получаем доказанной следующую теорему

Теорема 2.

1. Собственные числа модифицированного ГЗ-оператора (23), (24) в трехдиагональном случае (11), (20) произвольного размера , n=1,2,…:

, (33)

В случае нечетных существует ещё одно собственное число . Здесь и задаются формулами (14).

2. ОП для сходимости (3) с модифицированным ГЗ- оператором (оптимальный параметр метода релаксации)

(34)

здесь - максимальный корень многочленов Чебышева второго рода на интервале (0, 4), задаваемый формулой (16).

3. Спектральный радиус оптимального модифицированного ГЗ-оператора

(35)

Для и только для них оптимальный модифицированный ГЗ-метод (оптимальный метод релаксации) сходится.

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

Из Теоремы 2 и (22) при Следствие.

2. Собственные числа обычного ГЗ-оператора

кратности , ;

3. Радиус сходимости обычного ГЗ-метода

, (36)

где и задается формулой (16), а радиус сходимости метода Якоби представлен в (21). Поэтому сходимость обычного ГЗ-метода имеет место только для , что существенно меньше указанного в п.3 Теоремы 2. Матрица в (7) имеет такой же спектр (36). Поэтому, если поставить задачу определения ОП в процессе (3), (10) с этой матрицей, то получим , что существенно отличается от (34).

На рис. 10, (а) показано поведение спектральных радиусов , , для обычных методов Ричардсона, Якоби и ГЗ как функции от . Метод Ричардсона представлен двумя графиками: 1). для , когда в области сходимости последняя хуже, чем в остальных методах; 2). для и , когда для метод Ричардсона сходится, а остальные методы расходятся. В терминах матрицы (13) область сходимости оптимального ГЗ-метода совпадает с областью сходимости (19) оптимальных методов Ричардсона и Якоби. Но оптимальный ГЗ-метод сходится всегда быстрее. На рис. 10 (б) показано поведение спектральных радиусов (34), (18),(22)для этих методов.

а) б)

Рис.10 (а) спектральные радиусы стационарных методов без параметров и (б) методов МОПИ и оптимальной релаксации

Результат (24) для ОП находится в полном соответствии с теоремой [8], которая устанавливает, что для метода релаксации сходимость отсутствует, если находится вне интервала , т.е. если , согласно (26), находится вне интервала . Из (34) следует, что необходимое и достаточное условие сходимости (п.3 Теоремы 2) соответствует интервалу оптимального параметра . Отсутствие сходимости при следует также из исследования поведения функции (31) подобно тому, как это сделано для случая .

Оптимальный параметр для метода релаксации, согласно (34), (27)

(37)

Здесь -максимальное по модулю собственное число матрицы перехода обычного метода Якоби (21) (чисто мнимое для ). В работе [8] для положительно определенных и согласованно упорядоченных матриц (для них вещественно и 0< <1) найден ОП, совпадающий со второй частью (37). Таким образом, для таких матриц ОП (37) находится в области «верхней» релаксации. Этой области соответствует ( или на рис. 10). В рассматриваемом несимметричном трехдиагональном случае правая часть формулы (37) остаётся верной и для области «нижней» релаксации , т.е. при (ab<0 или область x<0 на рис. 10).

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

Исследование свойств сходимости итерационных методов на примере строгого решения для трехдиагональной матрицы помогает правильно построить методику расчетов для СЛАУ с большой ленточной матрицей. Из приведенной теории следует (и опыт проводимых расчетов это подтверждает), что безусловным лидером среди стационарных итерационных методов для решения СЛАУ с блочно-трехдиагональной положительно определенной матрицей является оптимальный метод релаксации.

Для пятидиагональных симметричных блочно-трехдиагональных теплицевых матриц (см. Приложение 1), которые возникают при численном решении краевых задач для эллиптических уравнений в частных производных, справедлива та же формула (2.18) с вещественным собственным числом матрицы Якоби [8], которое с минимальными затратами (в случае, если оно уединенное по модулю) находится степенным методом [3,5]. Далее, найденный для сравнительно небольших матриц с , ОП слабо изменяется для матриц большего размера. Это хорошо видно на примере трехдиагональной матрицы из формулы (37), в которой и практически не изменяется с ростом для больших размеров. Однажды найденный для данной сетки оптимальный параметр можно использовать для расчетов с различными граничными условиями и источниками, которые входят в правую часть СЛАУ. Формула (37) справедлива также, как показывает опыт расчетов, для кососимметричных матриц с чисто мнимым .

Изложенная теория справедлива также для СЛАУ с матрицами, которые связаны преобразованиями подобия [1] с рассмотренными трехдиагональными (13) или почти треугольными матрицами вида (26).

Непосредственно для задачи решения СЛАУ с трёхдиагональной матрицей изложенная теория даёт границы применимости наиболее экономичного по количеству арифметических операций (N~8n) в данном случае метода прогонки [5] (см. Приложение 2). Этот метод не приведет к результату в двух случаях: 1). если матрица сингулярна; 2). если при вычислении прогоночных коэффициентов обнаруживается деление на нуль. В первом случае метод прогонки неустойчив, во втором–некорректен. Оба они укладываются в рамки следующего соотношения между коэффициентами матрицы, получаемого (при ) из формулы (13):

(38)

Случай 1) следует из условия при . Случай 2) из равенства нулю знаменателя в прогоночном коэффициенте на -ом шаге. Последняя задача приводит к поиску корней многочленов Чебышева второго рода степени относительно переменной .

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