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

Для перехода к методу релаксации запишем исходное уравнение в эквивалентном виде с помощью матрицы перехода Якоби и некоторого произвольного параметра :

С учетом того, что для матрицы перехода Якоби диагональные элементы суть нулевые (), матрицу, участвующую в процессе релаксации , которая есть матрица Якоби с добавлением параметра , можно представить

(32)

Алгоритмнеявногометода релаксации (32) записывается аналогично алгоритму метода Зейделя, только с параметром. При значении параметра он переходит в алгоритм метода Зейделя. В неявном матричном виде процесс метода релаксации имеет вид

Также как и в методе Зейделя процесс (32) можно рассматривать как воздействие линейного непрерывного оператора релаксации на вектор предыдущей итерации . При этом эквивалентная матрица релаксации, которая производит такое же действие, но в процессе релаксации не участвует, есть

(33)

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

Для некоторого класса матриц, возникающих в краевых задачах для дифференциальных уравнений в частных производных, оптимальный параметр найден [7]. Так, для блочно-трехдиагональной, а также самосопряженной и положительно (отрицательно) определенной матрицы (, ) оптимальный параметр для сходимости [7] :

, (34)

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

В литературе для параметра метода релаксации используется обозначение или , которое связаны с параметром как

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

Найдем значение радиуса сходимости для оптимального метода релаксации . Для таких матриц радиус сходимости метода Якоби и для радиуса сходимости метода Зейделя . Учитывая получаем из (34) . Радиус сходимости этого метода на примере решения СЛАУ с трехдиагональной матрицей (см. раздел 1.7)

(35)

где оптимальный параметр дается формулой (34). Для малых значений получаем

В завершение выразим радиусы сходимости всех стационарных методов для случая , .

Пусть - матрица перехода в методе Ричардсона. Её собственные числа связаны с числами исходной матрицы , т.е. .

Оптимальный параметр сходимости метода простой итерации Ричардсона

Спектральный радиус матрицы перехода

Здесь обозначено . Для оптимального метода Ричардсона

(36)

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

(37)

На примере решения СЛАУ с трехдиагональной теплицевой матрицей найдено, что радиус сходимости метода Зейделя есть квадрат спектрального радиуса матрицы перехода Якоби (см. (36) в 1.12). Этот вывод остается, как правило, справедливым для блочно-трехдиагональных матриц

(38)

Таким образом, для таких матриц метод Якоби и метод Зейделя сходятся всегда, при этом метод Зейделя сходится лучше. Для самосопряженных, положительно определенных и (дополнительно!) блочно-трехдиагональных теплицевых матриц, самым быстрым оказывается метод оптимальной релаксации.

Учитывая (34) и (35) для радиуса сходимости метода Релаксации получаем

(39)

На рис.7 приведены знаменатели сходимостей всех стационарных методов, а также асимптотические знаменатели сходимости нестационарного метода с чебышевским набором параметров и метода сопряженных градиентов (Гл.II) для самосопряженных положительно определенных блочно трехдиагональных матриц. Представлены зависимости спектральных радиусов различных методов (36)-(39) от параметра . Верхняя (сплошная) кривая показывает самую слабую сходимость (36), (37) у оптимального ряда простой итерации и метода Якоби, ниже (пунктир) знаменатель сходимости метода Зейделя (38), на этом же уровне (точечная) кривая для асимптотического знаменателя сходимости нестационарного метода с чебышевским набором параметров (МЧП) ((4) из 2.3, ).

Рис.7. Знаменатели сходимости стационарных методов для матриц специального типа, а также асимптотические знаменатели сходимости методов МЧП и МСГ

МЧП показывает лучший результат в случае слабой сходимости и сходится хуже, чем метод Зейделя в случае быстрой сходимости . Для метода сопряженных градиентов (МСГ) средний асимптотический знаменатель сходимости не хуже, чем (4) из 2.3 [4]. На практике сходимость МСГ может быть лучше (см. Приложение 1). И, наконец, знаменатель сходимости метода релаксации (39), как квадрат предыдущего знаменателя, представляет лучший результат для блочно трехдиагональных симметричных положительно определенных матриц (кривая «точка- пунктир»).

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

(40)

Приведем еще пример использования подпрограммы метода Зейделя (рис.6) для вычислений по методу оптимальной релаксации. Это возможно, так как по сути метод релаксации есть метод Зейделя с параметром. В п/п метода Зейделя на рис.6 нулевые диагональные элементы матрицы Якоби используются в цикле, а для метода релаксации они уже зависят от параметров. Здесь же приведен пример такого обращения к п/п Seidel.