4 5 x21

x22 =

0 1

(4x11

2

1

x11

x12

1

0

(x21

+ 5x21

= 0

=)

(3x21

=2

2

2

=)

=

6 2

2x11

+ x21 = 1

x11

+

1 x21

= 1

x11

=

5

(4x12

(3x22

(x22

3

+ 5x22

= 1

)

= 1

)

=

31

2x12

+ x22 = 0

=

x12

+

21 x22

= 0

=

x12

=

61

5

6

1

6

A 1 =

64

26

8Итерационные методы решения систем линейных уравнений

8.1Метод Якоби

Пусть дана линейная система

Ax = b (1)

где матрица

A = (aij) i; j = 1; 2; :::; n

имеет имеет обратную матрицу, Векторы свободных коэффициентов и неизвестных

=	0 21 x =					0x21
		1					x1
	B		C			Bx		C
	B nC					B nC
	@	:::	A			@	:::	A

Предполагаем, что диагональные элементы aii 6= 0. Разрешим первое уравнение системы (1) относительно x1, второе относительно x2, и т. д. Получим эквивалентную систему

i 1

xi = P aij xj j=1 aii

n

j=Pi+1 aii xj + aii i = 1; 2; :::n (2)
aij	bi

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

x(k) = (x(1k); :::; x(nk))

где x(ik) k-атая итерация i-ой компоненты вектора x.

В методе Якоби исходят из записи системы в виде (2), причем итерации определяются следующим образом

(k+1)		i 1 aij (k)			n	aij (k)			bi
	=	jP			P
xi								+ aii k = 0; 1; 2::: i = 1; 2; ::; n (3)
		=1 aii xj			j=i+1 aii xj

Начальные значения x(0)i для любого i задаются произвольно. Примечание 1. Условие aii 6= 0 не является обязательным. Имея систему

n

P

aijxj = bi i = 1; :::; n

j=1

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

aii = a(1)ii + a(2)ii

a(1)ii 6= 0

21

тогда i-ое уравнение, эквивалентное данному будет

		n	aij		(k)		bi
		jP
x =			(1) x			+ (1)
i		=1 aii			j		aii

Здесь при i = j коэффициент имеет вид

(2) a

ii(1) (4) aii

Примечание 2. Систему у-ний (2) можно записать по-иному.

( ij = 0		i = j i aii
ij =	aij	i 6= j =
	aii		bi
Тогда система (2) преобразуется к виду

8

>x1 = 1 + 12x2 + . . . + 1nxn

>

>

<x2 = 2 + 21x1 + 22x3 + . . . + 2nxn

(5)

>:::

>

>

:xn = n + n2x1 + . . . + n;n 1xn 1

Введем матрицу , где ii = 0.

Векторы свободных коэффициентов и неизвестных

=	0 2			1 x =			0x2			1	(6)
		1						x1
	B			C			Bx			C
	B		nC				B		nC
	@	:::		A			@	:::		A

Тогда систему (5) можно записать в матричной форме

x= + x

Апоследовательные приближения можно записать в виде

x(1) = + x(0)

x(2) = + x(1)

и т. д.

Любое k + 1 приближение вычисляют по формуле

x(k+1) = + x(k) (7)

8.1.1Сходимость метода Якоби

Пусть задана линейная система

x = + x (8)

где матрица и векторы ; x определяются выражениями (6).

Теорема. Процесс итераций для линейной системы (8) сходится к единственному решению, если какаялибо каноническая норма матрицы меньше 1. То есть, для итерационного процесса

x(k) = + x(k 1) (9)

достаточное условие сходимости есть

jj jj < 1.

22

Следствие 1. Процесс итерации системы (8) сходится, если:

nn

PP

1. норма jj jjm = max j ijj < 1 или j ijj < 1i = 1; :::; n

i j=1 j=1

nn

PP

2. норма jj jjl = j	i=1j		ijj	< 1	или i=1j	ijj	< 1 j = 1; :::; n
max

s

	n n
3. jj jjk =	iP P
	=1j=1j ijj2 < 1

Док-во. Нормы 1-3 являются каноническими нормами, поэтому условие теоремы выполняется.

Следствие 2. Для системы

n

P

aijxj = bi i = 1; 2; :::; n (13)

j=1

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

n

P

1. jaiij > jaijj i = 1; 2; :::; n

j=1

n

P

2. jajjj > jaijj j = 1; 2; :::; n

i=1

при суммировании пропускаются значения i = j (без док-ва).

8.1.2Оценка погрешности приближения процесса итерации в методе Якоби

Погрешность приближения оценивается неравенством

jjx x(k)jj 6 jj jjk jjx(1) x(0)jj (14)

1 jj jj

где x решение системы, x(k)- приближение на k том шаге. В частности, если выбрать x(0) = , то

								(1) = +
							x
тогда
				(k)	jj 6	jj jjk			jj jjk+1
jjx x						1 jj jj	jj + jj =		1 jj jj	jj jj (15)

В неравенствах (14; 15) можно брать любую каноническую норму. Число шагов, обеспечивающих заданную точность (погрешность ") может быть определено из (15)

jjx x(k)jj 6 jj jjk+1 jj jj 6 " (16)

1 jj jj

Окончание итерации определяется либо условие (16) или

max jx(ik+1) x(ik)j < "

16i6n

8.1.3Блок-схема алгоритма метода Якоби

Входные параметры: n-число уравнений, число неизвестных A = (aij) - матрица коэффициентов, b вектор правой части, x0 вектор начальных приближений " погрешность

Выходные параметры: x(k+1) решения, k + 1 число итераций

23