2.1.3. Оценки погрешностей решения системы

Приведем оценки погрешностей системы (2.1).

Пусть A

=

(aij)

– матрица

коэффициентов

системы,

æ

n

ö

T

T

A

aij

–

ее

норма, b = (b1 ,b2

,...,bn )

, x = (x1 , x2

,..., xn )

–

= maxç

å

÷

1£i£n è

j=1

ø

соответственно

столбики

свободных

членов

и

неизвестных,

= max

b

,

x

= max

x

– нормы, D

, D

и d

=

D

,

d

=

Dx

–

b

b

i

i

b

x

b

x

b

x

1£i£n

1£i£n

соответственно их абсолютные и относительные погрешности.

Тогда абсолютная погрешность решения системы(2.1) имеет оценку:

Dx £ A-1 × Db ,

а относительная погрешность – оценку:

dx £ A × A-1 ×db .

2.2.Итерационные методы решения

2.2.1. Метод простой итерации (МПИ)

Система вида Ax = b может быть преобразована к эквивалентной ей системе

x = (E - A)x + b .
Обозначим через B = (E - A) , тогда x = Bx + b .
Образуем итерационный процесс
x k +1 = Bx k + b .	(2.8)
Теорема (о простых итерациях). Необходимым и достаточным

условием сходимости МПИ (2.8) при любом начальном векторе							x	0	к
решению	x	*	системы (2.2) является выполнение условия: или ||B|| < 1
(хотя бы в одной норме), или все собственные числа						.
Для			определения	количества	итераций, необходимых				для

достижения заданной точности ε, можно воспользоваться априорной

26

Lx + Dx + Rx = b .

оценкой погрешности решения системы и это значение найти из неравенства:

B k

1 - B

× x1 - x 0 < e .

Апостериорную (уточненную) оценку погрешности решения находят по формуле

D

£

B

×

x

k -

x

k -1

.

x

k

B

1

-

2.2.2. Метод Якоби

Для сходимости МПИ необходимо выполнение соответствующих условий. Одним достаточно эффективным способом приведения системы к виду, чтобы было выполнено условие сходимости МПИ,

является метод Якоби.

Представим А = L + D + R, где D – диагональная матрица, L, R –

левая	и	правая	строго	треугольные	матрицы(с нулевыми
диагоналями).

Тогда систему (2.2) можно записать в виде Если на диагонали исходной матрицы нет0, то эквивалентной к

формуле (2.2) задачей будет x = -D -1 (L + R)x + D -1b ,

где B = -D-1 (L + R) , c = D -1b – вектор свободных членов.

Тогда итерационный процесс Якоби:

x	k +1 = -D-1 (L + R)	x	k + D-1b .			(2.9)
Чтобы записать метод Якоби в развернутом ви, деостаточно
заметить, что обратной матрицей к						матрицеD = (aii )in=1 служит
диагональная матрица D-1 с элементами dii =						1	.
						aii

Тогда (2.9) имеет вид:

27

ìx k +1		= - (a12 x2k		+ ... + a1n xnk	- b1 )
ï	1			a11
ï
ï			k	k	- b2 )
ïx k +1		= -	(a21 x2	+ ... + a2n xn
í	2			a22	.
ï...
ï
ï			k		k
ïxnk +1 = -			(an1 x1	+ ... + an,n-1 xn - bn )
				ann
î
Теорема. В				случае диагонального преобладания в матрицеА,

n

метод Якоби (2.9) сходится. aii > å aij " i =1, n i ¹ j .

j =1

2.2.3. Метод Зейделя

Метод Зейделя применяется в основном к системам, в которых преобладающими элементами являются диагональные. В противном

случае скорость его сходимости практически не

отличается от

скорости сходимости МПИ.

Рассмотрим систему (2.1), где aii

¹ 0

i =

.

1, n

В (2.1) разделим i-е уравнение на aii

~

aij

~

b

.

i

и обозначим aij

=

, bi

=

aii

aii

Получим

эквивалентную (2.1)

систему, выразив

в каждомi-м

уравнении компонент решения xi

ìx

~

~

x

~

x

= b

- a

2

- ... - a

n

ï

1

1

12

1n

~

~

x

~

x

ïx

= b

- a

- ... - a

2 n

n .

(2.10)

í

2

2

21 1

ï...

~

~

~

ï

îxn

= bn

- an1 x1

- ... - an,n-1 xn-1

Идея метода Зейделя: При проведении итераций по формуле

(2.10) используется результат предыдущих уравнений

в

процессе

одной итерации.

28

Общая формула:

k +1

~

i-1 ~

k +1

n ~

k

(2.11)

xi

= bi -

åaij

x j

- åaij

x j .

j =1

j =i+1

j ¹i

Теорема.

Для

того чтобы метод Зейделя сходился, достаточно

n

выполнения

одного из

условий:

aii

> å

aij

" i =

1, n

i ¹ j

или А –

j =1

вещественная, симметричная, положительно определенная матрица.

2.2.4. Метод релаксации

Пусть имеется система линейных алгебраических уравнений. Преобразуем эту систему следующим образом.

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

на ( - a11 ), второе

уравнение на( - a22 ) и т.д. Получим

систему,

подготовленную к релаксации:

ì- x

~

x

~

x

~

+ a

2

+ ... + a

n

+ b = 0

ï

~

1

12

~

1n

~

1

x

- x

+

x

= 0

ïa

... + a

2 n

n

+ b

,

(2.12)

í

21

1

2

2

ï...

~

~

ï

~

= 0

îan1 x1

+ an 2 x2 + ... - xn

+ bn

~

aij

(i ¹ j) ,

~

b

.

aij

= -

bi =

aii

aii

Пусть

x

0

= (x0 ,..., x

0 )Т

– начальное приближение системы (2.12).

1

n

Подставляя эти значения в систему (2.12), получим невязки.

ì	0	~	0	n	~	0
ïR1		= b1	- x1	+ åa1 j		x j
ï				j =2
		~		n	~
ï	0		0			0
ïR2		= b2	- x2	+ åa2 j x j			(2.13)
í				j ¹2		.
				j =1
ï
ï...		~
ï	0		0	n-1	~	0
ïRn		= bn	- xn	+ åanj x j
î				j =1

29