Оптимальный параметр сходимости метода релаксации на примере решения СЛАУ с трехдиагональной несимметричной теплицевой матрицей

Рассматривается решение системы линейных алгебраических уравнений (СЛАУ) с неособенной квадратной матрицей коэффициентов

(1)

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

(2)

Далее процесс итераций строится по закону

, (3)

Здесь - матрица перехода или оператор перехода(в случае метода Зейделя), не зависящие от номера итерации .

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

В методе Якоби начальное уравнение записывается в виде (2), где

(4)

-матрица с нулевой главной диагональю и остальными коэффициентами в виде , . Правая часть .

Далее для метода Якоби в процессе итераций (3) участвует матрица (4).

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

(5)

Здесь заданный вектор правой части . Оператор (5), действующий в комплексном пространстве - мерных векторов, назовем оператором Зейделя. Легко можно показать, что он является линейным непрерывным оператором в этом пространстве.

Обычно оператор перехода в методе Зейделя записывают в неявном матричном виде

(6)

Однако, действие оператора перехода на вектор предыдущей итерации определяется простым процессом, при котором новые координаты вектора задаются по следующему закону

, (7)

Старые координаты в правой части (7) по мере роста заменяются на уже найденные в левой части новые. Здесь - коэффициенты матрицы Якоби (4).

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

(8)

Из (6) получаем, что эта матрица есть и заданный вектор правой части в процессе (3) с её участием . Однако, процессы, происходящие в левой и правой частях равенства (8), существенно различны. Так, например, в случае трехдиагональной СЛАУ количество арифметических операций слева и справа в (8) равно, соответственно, и . Как будет показано далее, оптимальный спектральный параметр, найденный для модифицированного метода с оператором в одном случае и с матрицей в другом, также существенно различны.

Доказывается, что необходимым и достаточным условием сходимости процесса простой итерации (3) с участием матрицы [1] или с участием линейного непрерывного конечномерного оператора [10] является

, (9)

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

Для ускорения сходимости метода простой итерации уравнение (2) и процесс (3) могут быть эквивалентно переписаны

, , (10)

где матрица определяется формулой

(11)

Здесь - пока произвольный, параметр, выбором которого попытаемся удовлетворить условию или условию в случае, если (9) не выполняется или сходимость обычного метода слабая. – единичная матрица.

Рассмотрим СЛАУ (1) и (2) с трехдиагональной теплицевой матрицей [4] вида (12)(соответственно матрицы и ). Везде далее предполагается, что коэффициент и произведение коэффициентов вещественны.

, (12)

Если СЛАУ (1) с матрицей А из (12) решается обычным или модифицированным методом Зейделя, то в переходном процессе (3) участвует соответствующий оператор, при этом матрица, являющаяся его основой (т.е. матрица соответствующего метода Якоби), имеет трехдиагональную структуру из (12). Матрица такой структуры часто возникает при решении обыкновенных дифференциальных уравнений. Блочно-трехдиагональные матрицы возникают при решении краевых задач для дифференциальных уравнений в частных производных [8].

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

(13)

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

т.е.

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

Метод Зейделя (7) с модифицированной матрицей Якоби (13) совпадает с методом последовательной верхней релаксации [8] в других обозначениях .

Обычный и модифицированный операторы Зейделя, определенные через матрицу Якоби и процесс (7), имеют тот же спектр, что и соответствующие эквивалентные матрицы перехода. Исследование спектра необходимо для определения радиуса сходимости методов и условий его минимизации. В работе [6] найдены собственные числа обычного и модифицированного оператора Зейделя в случае трехдиагональной теплицевой, в общем случае несимметричной, матрицы СЛАУ произвольного размера.

Так, для обычного оператора Зейделя в этом случае собственные числа следующие:

кратности , (14)

Здесь - корни многочлена Чебышева второго рода на отрезке [0, 4]. Параметры матрицы перехода Якоби и введены выше. Таким образом, спектр располагается на отрезке [0, ], где . Если искать оптимальный параметр метода простой итерации для процесса (10) с эквивалентной матрицей перехода, то для оптимального параметра имеем .

Для модифицированного оператора Зейделя собственные числа следующие [17]:

, (15)

Случай соответствует обычному оператору Зейделя и из (15) следует (14). Оптимальным параметром, доставляющим минимум радиусу сходимости,

является

(16)

Здесь - максимальное по модулю собственное число матрицы перехода Якоби. В случае быстрой сходимости метода Зейделя

При этом оптимальном параметре собственные числа (15) выстраиваются в комплексную окружность

где .

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

(17)

Сходимость метода есть, если . Из (17) следует, что для сходимости должно быть . Из (16) следует, что это может быть только при вещественных и . Если коэффициенты исходной матрицы на побочных диагоналях одного знака и , то оптимальный параметр лежит в интервале , что соответствует известной области верхней релаксации . Если же коэффициенты разного знака , то , что соответствует области нижней релаксации . В работе [8] найден оптимальный параметр метода релаксации для положительно определенной, блочно-трехдиагональной матрицы СЛАУ, который лежит в области верхней релаксации. Для матриц с , в частности для косо-симметричных матриц, оптимальный параметр метода релаксации, как следует из (16), лежит в области нижней релаксации. При этом максимальное по модулю собственное число матрицы перехода Якоби есть чисто мнимая величина. Для случая быстрой сходимости метода Зейделя знаменатель сходимости метода релаксации примерно в четыре раза меньше .

Спектральные свойства оператора Зейделя, определенного с помощью процесса (7), изменяются нелинейно при линейных преобразованиях базисной матрицы Якоби. Это происходит в силу заложенного в методе принципа последовательных смещений, когда вектор, на который воздействует оператор, изменяется на данной итерации после каждого умножения на него соответствующей строки матрицы. В результате спектр обычного оператора Зейделя, который является вещественным отрезком, после линейного преобразования (11) базисной матрицы Якоби с оптимальным параметром (16), превращается в комплексный круг.

Покажем, что сходимость метода оптимальной релаксации лучше, чем сходимость метода оптимальной простой итерации с эквивалентной оператору Зейделя матрицей перехода, а та в свою очередь лучше, чем сходимость метода Зейделя. Обозначим радиусы сходимости этих методов соответственно , , . Надо показать, что Пусть для определенности . Тогда собственные числа оператора Зейделя положительны и максимальное из них есть радиус сходимости . Значение определяется формулой (17). Для определения заметим, что при линейном преобразовании (11) эквивалентной матрицы её спектр изменяется также линейно , причем при центр спектрального отрезка переходит в т.0 и радиус сходимости . Теперь, так как , неравенства оказываются верными , ч.т.д. В случае и неравенства, после внесения модулей, только усиливаются.

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

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