Методы вычислительной математики

можно представить в виде

Ax = (A1 + D + A2 )x = f ,

Dx = f − (A1 + A2 )x,

и формула метода Якоби будет выглядеть следующим образом:

Dx(s+1) = f − (A1 + A2 )x(s).

Учитывая, что A1 + A2 = A − D , последнее выражение можно также представить в форме

1 Зейдель Филипп Людвиг [24.10.1821 – 13.8.1896] – немецкий астроном и математик. С 1851 стал членом Баварской академии наук; с 1854 – членом Геттингенской академии наук.

51

где s – номер итерации. В отличие от метода Якоби, теперь для вычисления очередной неизвестной xi(s+1) на s + 1 итерации используются найденные на той же итерации значения всех величин x(js+1), j =1,i −1. Как и ранее, вычислительный процесс заканчивается, когда выполняется условие

max x(js+1) − x(js) < ε,

1≤ j≤m

где ε > 0 – заданная погрешность вычисления результата.

Точное решение этой системы: x1 = 0,5, x2 = 1,5.

Это означает, что для нахождения x2 на s + 1 итерации используется значение x1, вычисленное ранее на этойже итерации. В качестве начального приближения принимаются x(0) = 0 , y(0) = 0. Результаты расчетов сведены в табл. 2.3. Нарис. 2.4 показан ход выполнения итерационной процедуры Зейделя.

52

Таблица 2.3 Результаты выполнения итерационной процедуры метода Зейделя

Как и в предыдущем случае, матрица коэффициентов А представляется в виде суммы A = A1 + D + A2 с теми же обозначениями. Итерационную форму-

лу метода Зейделя можно представить в форме

(A1 + D)x(s+1) = f − A2 x(s) .

Учитывая, как и ранее, что A2 = A − A1 − D , последнее выражение можно записать в виде итерационной схемы

2.4.3. Сходимость итерационных методов

Сравнивая формулы (2.14) метода Якоби и (2.16) метода Зейделя, можно заметить, что если последовательность решений сходится, то есть в некотором смысле (x(s+1) − x(s) )→ 0, s → ∞ , то она сходится к решению исходной задачи,

поскольку в этом случае имеет место Ax(s) = f , s → ∞.

Пример 2.5. Решить систему линейных алгебраических уравнений:

x1 = 0,5, x2 =1,5. Для нахождения решения используется метод Зейделя. Как и ранее, уравнения системы записываются в виде итерационной схемы:

53

Результаты вычислений представлены в табл. 2.4. На рис. 2.5 отражен ход поиска решения системы линейных алгебраических уравнений методом Зейделя.

–5

Рис. 2.5. Отсутствие сходимости решения при использовании метода Зейделя

54

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

Итерационные методы решения систем линейных алгебраических уравнений можно записать в канонической форме с использованием итерационных параметров B(s+1) и τ(s+1) :

метода Зейделя B(s+1) = A1 + D, τ(s+1) =1.

Если B(s+1) = E , метод называется явным; в противном случае – неявным. Примеры итерационных методов:

– явный стационарный метод простых итераций:

(x(s+1) − x(s) )τ + Ax(s) = f ;

– неявный стационарный метод верхней релаксации:

(D + ωA1 )(x(s+1) − x(s) )ω + Ax(s) = f , ω > 0 .

В пространстве m-мерных векторов Rm со скалярным произведением

m

(u,v)= ∑uivi

i=1

и нормой

m

w = (w, w) = ∑wi2

i=1

определяется матричное неравенство: квадратная матрица C > 0 тогда и только тогда, когда

(Cx, x) > 0 x H , x ≠ 0 .

Иначе это определение может быть записано следующим образом [9]:δ > 0, (Cx, x) ≥ δx 2 , x ≠ 0.

55

Эта оценка позволяет утверждать, что существует обратная матрица C −1 , так как в случае положительной определенности матрицы все ее главные (угловые) миноры положительны (критерий Cильвестра1, [9]).

Для установления условий сходимости формулой z(s) = x(s) − x определяется погрешность метода, и тогда из формулы (2.17) для стационарного итерационного метода можно получить

Теорема 2.4. Пусть А – симметричная положительно определенная матрица, A > 0. Итерационные параметры удовлетворяют соотношению

B −τA2 > 0, τ > 0 .

Тогда стационарный итерационный метод сходится.

Доказательство. Для доказательства теоремы следует показать, что по-

грешность метода z(s) →0 при любой начальной погрешности z(0) . Для

s→∞

этого строится числовая последовательность вида J (s) = (Az(s) , z(s) ). Из фор-

мулы (2.18) следует

z(s+1) = z(s ) − τB−1 Az(s) , Az(s+1) = Az(s ) − τAB−1 Az(s ) .

Теперь можно подсчитать

J (s+1) = (Az(s+1) , z(s+1) )= (Az(s) − τAB−1 Az(s) ,z(s) − τB−1 Az(s) )=

= (Az(s) , z(s) )− τ(AB−1 Az(s) ,z(s) )− τ(Az(s) ,B−1 Az(s) )+ τ2 (AB−1 Az(s) ,B−1 Az(s) ).

Вследствие симметрии матрицы А имеет место равенство

(AB−1 Az(s) , z(s) )= (Az(s) , B−1 Az(s) ).

Отсюда следует:

J (s+1) = (Az(s) , z(s) )− 2τ(Az(s) , B−1 Az(s) )+ τ2 (AB−1 Az(s) , B−1 Az(s) )=

= J (s) − (2τAz(s) − τ2 AB−1 Az(s) , B−1 Az(s) ) = J (s) − 2τ((B − τA2)B−1 Az(s) , B−1 Az(s) ) =

=J (s ) − 2τ((B − τA2)u(s) ,u(s) ),

1Сильвестр Джеймс Джозеф [3.9.1814 – 15.3.1897] – английский математик. Окончил Кембриджский университет в 1837 году. С 1855 по 1870 годы являлся профессором Королевской академии в Вулидже; с 1876 по 1883 год – профессором университета Джона Хопкинса в г. Балтиморе; с 1883 года – профессором Оксфордского университета; с 1872 года – иностранным членом-корреспондентом Петербургской академии наук.

56

где u(s) = B−1 Az(s) . В силу условия теоремы [(B − τA2)u(s) , u(s) ]> 0 u(s) , следует, что J (s+1) ≤ J (s ) , то есть построенная последовательность является монотонно убывающей и, кроме того, в силу J (s+1) = (Az(s+1), z(s+1) )> 0 ограничена снизу. Отсюда вытекает, что существует предел этой последовательности

J = lim J (s) .

s→∞

Из положительной определенности (B − τA2)> 0 следует существование константы δ > 0 такой, что имеет место

((B − τA2)B−1 Az(s) , B−1 Az(s) )≥ δB−1 Az(s) 2 .

Предыдущее выражение может быть переписано в форме неравенства:

J (s+1) = J (s) − 2τ((B − τA2)B−1 Az(s) , B−1 Az(s) )≤ J (s ) − 2τδB−1 Az(s) 2 .

При s → ∞ из последнего выражения следует

J ≤ J − 2τδlim B−1 Az(s) 2 .

s→∞

Очевидно, что неравенство lim B−1 Az(s) 2 ≤ 0 может выполняться лишь при

s→∞

чем A−1 существует в силу положительной определенности матрицы А, как это определено условием теоремы. Норма погрешности оценивается выражением

Следствие 1. Пусть А – симметричная положительно определенная матрица. Тогда метод верхней релаксации

(D + ωA1 )(x(s+1) − x(s) )ω + Ax(s) = f , ω > 0

сходится при 0 < ω < 2. В частности, метод Зейделя (ω = 1) сходится.

Доказательство. В рассматриваемом случае B = D + ωA1, τ = ω,

(Ax, x) = ((A1 + D + A2 )x, x) = (A1 x, x)+ (Dx, x)+ (A2 x, x) = (Dx, x)+ 2(A1 x, x).

Последнее соотношение справедливо в силу симметрии матрицы А:

57

Условие сходимости итерационного метода B −0,5τA > 0, τ > 0 теоремы 2.4

принимает вид

((B − ωA2)x, x) = (Bx, x) − ω(Ax, x)2 = (Dx, x) + ω(A1x, x)− ω[(Dx, x)+ 2(A1x, x)]2 = = (Dx, x)+ω(A1x, x)−ω(Dx, x)2 −ω(A1x, x) = (1−ω2)(Dx, x) > 0.

Очевидно, что последнее неравенство выполняется при условии

1−ω2 > 0, 0 < ω< 2 .

Следствие 2. Пусть А – симметричная положительно определенная матрица с диагональным преобладанием, то есть имеет место

aii > ∑ ai j , i, j =1,m .

i≠ j

Тогда метод Якоби сходится.

Доказательство. Поскольку в рассматриваемом случае B = D, условие сходимости принимает вид неравенства 2D > A . Из неравенств

(xi − x j )2 = xi2 − 2xi x j + x2j ≥ 0 , xi x j ≤ (xi2 + x2j )2

получается:

В силу симметричности и положительной определенности А следует:

Использование предположения следствия приводит к выражению

2aii > ∑ ai j + aii , i =1,m . i≠ j

Из двух последних неравенств получается

m

(Ax, x)< 2∑aii xi2 = 2(Dx, x).

i=1

Что и требовалось доказать.

2.4.4. Итерационный метод с чебышёвским набором параметров

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

58

(x(s+1) − x(s) )τ(s+1) + Ax(s) = f , s = 0,1, 2, …

Следует так определить набор итерационных параметров τ(1) , τ(2) , …, τ(n) , чтобы норма x(n) − x была минимальной для заданного числа итераций n.

Теорема 2.5. Пусть А – симметричная положительно определенная матрица, λmin > 0, λmax > 0 – ее наименьшее и наибольшее собственные значения; за-

По построению T (n) – симметричная матрица. Погрешность на n-й итерации можно представить выражением

z(n) =T (n) z(0) , z(n) = T (n) z(0) .

59

Для симметричной положительно определенной матрицы в качестве нормы может быть выбран спектральный радиус ν = λmax (T (n) ) . Действительно, для собственного вектора V, соответствующего собственному значению λmax ,

T (n)V = λmaxV ,

можно подсчитать норму оператора

60