книги / Численные методы. Ч. 1

откуда можно оценить норму

Цбх1 = Цл-'бг (X -А - Е)х| ^ |А-1 • |5fl|+||А-А - Е| - И .

Оценим порознь слагаемые в правой части этого неравенства:

| * - Н м - Л - 1 Ф * С ) ||А

|А-'А - е | = ||(А+ 6а )*'а - е| = | а (е + А-'бА))" а - е| = |(а (е + с))" а - е| =

=1е +с)"а "а - е11=|(е +с) " - е1=1е +с)"(е -(е +с) |= Н е +с)"с1^

< 1 Е I сУ'Д ДС|И		^ SAI ^ ^
- I С) I |С|- 1-М " 1-|А-аА|- 1-JA-|.|RA|*
Подставим Полученные оценки в исходную формулу:
w ■ i-| i^fl5^AjM +	=	+||бА|'^ '
Учитывая, что
М Н М ^ М ^ ^ Н - Н .

ы-	И fN|Hiу M5/J J ]	KIN ГМ,Mtj
м -	1 - ||А - ||.|м 1 ИИ H ™ J	1_|A-|.w ^ l II г и

Вспоминая, что МА = ||А',||-||А||, получаем доказываемое утверждение теоремы

	Представим матрицу коэффициентов А в виде суммы						A = A ,+ D + A ; , где
[A,]	= a IJf	i> j	нижняя	треугольная	матрица	с	нулевой	диагональю:
[А2]	= a 1Jf	i< j	верхняя	треугольная	матрица	с	нулевой	диагональю:
[D ](J = a(J,		i = j	- диагональная матрица. Теперь систему уравнений Ах = Г можно
представить в виде:
			Ах = (А, + D + А,)х = f.
			Dx = f -(А , + A^)x,
и метод Якоби будет выглядеть следующим образом:
			Dx(n+I) = f —(А, + А 2)х(п).
	Учитывая, что А, +А 2 = А - D , последнее выражение можно также представить в
форме
			D(x1,wl) - x ln)) + Ax(n) = f					( 2. 10)

Рис. 2.1. Схема выполнения метода Якоби

Преобразуем выражение (2.9) к виду

i = l,m

(2. 11)

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

шах|х( п>,) - х (п,|< е ,
Isjsm I J	J I

6>0 - заданная точность вычисления результата.

Пример 2.4. Рассмотрим систему алгебраических уравнений, указанную в предыдущем примере:

[4х + 2у = 5, [Зх + 5у = 9.

Представим полученные выражения в виде итерационной схемы

S_9v,n' xt«i. = L _ d !_

4

(n+D

;5

Это означает, что для нахождения величины у на (п+1) итерации используется значение х. только что вычисленное на этой же итерации. В качестве начального приближения также примем х(0) =0, yl0) =0. Результаты расчетов сведены в табл. 2.2. На рис. 2.2 графически показан ход выполнения итерационной процедуры Зейделя.

Как и в предыдущем случае, представим матрицу коэффициентов А в виде суммы А = А, + D + A. с теми же обозначениями. Метод Зейделя можно представить в форме

(А, + D)x(n+,) = f - A 2x(n)
Учитывая, как и ранее, что A2= A - A ,- D , последнее	выражение можно
записать в виде итерационной схемы
(А, + D )(x(n+,) - x(n)) + Ax(n) = f .	(2.12)

1Зейдель Филипп Людвиг [24.10.1821 - 13.8.1896] - немецкий астроном и математик. С 1851 стал

членом Баварской академии наук; с 1854 - членом Геттингенской академии наук.

Таблица 2.

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

	п	х<">	уОО
	0	1,25	0
	1		1,05
	2	0,725
			1,365
	3	0,5675
			1,4595
	4	0,5203
			1,4879
	5	0,5061
			1,4964
	6	0,5018
			1,4989
	7	0,5005
			1,4997

Рис. 2.2. Схема выполнения метода Зейдеяя

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

Сравнивая формулы (2.10) метода Якоби и (2.12) метода Зейделя, можно заметить,

что если методы сходятся, то есть в некотором смысле (х(п+1) - х(п)) 0, п -» х , то они

сходятся к решению исходных задач Ax(n) = f, п оо.

Пример 2.5. Рассмотрим еще одну систему алгебраических уравнений, несколько

отличающуюся от приведенных в предыдущих примерах:

( 4х + 2у = 5,

}-20х + 5у = -2,5.

Точное решение этой системы х = 0,5,	у = 1,5 .
Для решения воспользуемся методом Зейделя. Как и ранее, представим уравнения
в виде итерационной схемы
(	5-2У<я>
	4 ’

-2.5 + 20Х1"*11

У5

Результаты расчетов сведены в табл. 2.3. На рис. 2.3 отражен ход выполнения процедуры Зейделя.

Таблица 2.3

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

	п	х<“>	у(п)
	0		0,0
	1	1,25	4,5
	2	-1,0
			-4,5
	3	3,5
			13.5
	4	-5,5
			-22,5
	5	12,5
			49,5
	6

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

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

(п+1) _	Т (П)	+ Ax(nJ=f, П = 0,1,.	(2.13)
o(n+l) i
-(П+1)

где в (п+|).т (п } - итерационные параметры.

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

В случае, если в{п+|), х(п+|) не зависят от номера итерации, метод называется

стационарным. В частности, для метода Якоби B(n+I) = D, т(п+,) = 1; для метода Зейделя B(n+,) = А, + D, т(п+|) = 1.

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

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

т

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

(D+©Ai) х"и,) -х«“’ +Axtn)=f. CD>0.

©

Введем пространство H c R mm - мерных векторов со скалярным произведением

ш

M=Zu.v,

1=1

и нормой

H=V (w'w) = j Z w?

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

(Cx,x)>0 V x eH .х*0.

Иначе это определение может быть записано следующим образом: 35>0, (Сх.х)>б||х||\ х*0 .

Чтобы определить величину б, рассмотрим два случая:

1. Пусть симметричная матрица С > 0, тогда согласно первоначальному

определению	квадратичная форма1		(Сх,х)	> 0	Но	квадратичную форму	можно
привести к каноническому виду в главных осях:
		(Сх,х) = ^ с ,,х )х1=
			i.J=l	1=1
где X,		- собственные числа матрицы С;			- главные координаты.
В силу	С	m	вследствие			__	отсюда
		> 0 имеем				чего X, >0, i = l.m, и
		i^i
получаем
		(с х .х )= |;я .д 1! > х п,1П| ; ^ = х ттн г
		»=1		Г-1

то есть в качестве 5 может быть взято наименьшее собственное значение матрицы С. 2. Если С несимметричная матрица, поступают следующим образом для

определения 5:

(Сх.х) = 2 ]с1,х1х ,, '•] I

1Согласно [7], квадратичная форма определяется только для симметричных матриц.