Учебное пособие_Численные методы -26 -дек_2014 (97-2003)

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

2.5. Метод LU-разложения

Очень легко отыскать решение системы линейных алгебраических уравнений, если представить матрицу коэффициентов A системы как произведение двух матриц: верхней треугольной матрицы L и нижней треугольной матрицы U: A LU .

Такое разложение называется LU-разложением. Запишем определение LU-разложения в матричном виде на примере матрицы размера 4х4:

	a			a		a		a					1		0		0	0			u		u	12	u	13
			11	12		13		14														11
		a		a		a		a					m		1		0	0				0	u		u
			21		22		23		24					21										22		23
	a		31	a	32	a	33	a	34			m		31	m	32	1	0			0		0		u	33
				a42		a43									m42		m43
	a41							a441				m41						1				0	0		0

u	14
u	24
u	34
u	44

    

.

Заметим, что определение применимо и к произвольной матрице размера NxN.

Итак, пусть матрицу коэффициентов A линейной системы AX=B можно разложить на треугольные матрицы: LUX=B. Тогда решение можно получить, полагая Y=UX, и затем решить две системы: LUB, для Y, чтобы получить UX=Y для X.

2.6. Метод отражений

Под нормой вектора будем понимать евклидову норму, а под нормой матрицы спектральную норму.

Лемма 1. Спектральная норма всякой унитарной (ортогональной в вещественном случае) матрицы равна 1.

Доказательство. Поскольку унитарные матрицы сохраняют евклидову длину вектора, по определению спектральной нормы получаем для всякой унитарной матрицы U :

remu

U= sup x 0

Ux	= sup	x	= 1 .
x	x 0	x

Лемма 2. Собственные значения всякой унитарной матрицы по модулю равны 1.

Доказательство. Пусть произвольное собственное значение матрицы U . U = 1 по предыдущей лемме. С другой стороны, 1

31

является

	1	U		1

собственным значением матрицы U-1, которая тоже унитарна. = 1 – по лемме 1, т.е. 1. Следовательно, = 1.

Лемма	3.	Собственные			значения всякой самосопряженной
(симметричной в вещественном смысле) матрицы A (т.е. A(*)=A)
вещественны.
Доказательство. Пусть				–	произвольное собственное значение
матрицы A ,	x 0	– отвечающий			ему собственный вектор,	т.е. Ax = x .
Умножим это равенство скалярно на x : Ax,x = x,x , откуда						= Ax,x / x	2	.

Выражение

Ax,x

вещественно

Следовательно,

вещественно.

для самосопряженной матрицы A.

2.7. Матрица отражения и ее свойства
Матрицей отражения называется матрица вида U U x			I 2xx	, где
		= x1 ,..., xn	*
x единичный вектор,	т.е. x = 1. Напомним, что x		«матрица»
размера 1 n, x = x1 ,..., xn	*
	– «матрица» размера n 1 и потому		xx матрица
t			*

размера n n.

Установим основные свойства матрицы отражения.

Лемма 4. Матрица отражения является самосопряженной матрицей.

Доказательство. Вычислим сопряженную матрицу для матрицы отражения U x :

U x

I 2xx I 2 x

x

I 2xx U x ,

*

*

*

*

*

*

что и означает самосопряженность матрицы

U x .

Лемма 5. Матрица отражения является унитарной матрицей.

Доказательство. Вычислим для матрицы отражения U x :

I

,

U x U

x U x I 2xx

I 2xx

I 4xx

4xx

xx

I 4xx

4xx

*

2

*

*

*

*

*

*

*

поскольку матрицы U

xx*x .

= x,x = x	2

= 1

.

Это равенство и означает унитарность

Лемма 6.Собственные значения матрицы отображения равны либо 1, либо -1.

Доказательство. Из лемм 2 и 4 вытекает, что собственные значения матрицы отражения по модулю равны 1. Из лемм 3 и 5 следует, что они вещественны. Значит, собственные значения есть либо 1, либо -1.

Лемма 7. Матрица отражения U x имеет собственное значение -1 кратности 1, которому отвечает собственный вектор х, и собственное значение 1 кратности n-1, которому отвечает собственное подпространство x = y : y,x = 0 .

32

Доказательство.

Имеем

U x x = I 2xx

*

x = x

2xx

*

x = x 2x = x ,

*

x =

x,x = x

2

= 1

. Следовательно,

x

собственный вектор,

поскольку x

отвечающий собственному значению -1.

U x y = I 2xx* y = y 2xx* y = y ,

Далее,

для

всех

y x

*

y =

y,x = 0 .

Следовательно,

y собственный вектор,

поскольку x

отвечающий собственному значению 1.

Такие вектора

y x образуют

n 1 -мерное подпространство.

Лемма 8. Геометрический смысл преобразования, задаваемого

матрицей отражения

U x : отражение относительно гиперплоскости

x .

Доказательство. Всякий вектор z C

n

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

z=αx+y,

где y x . Здесь компонента αx параллельна x,

а компонента y

ортогональна

x,

. В

силу леммы 7

т.е. лежит в гиперплоскости x

U x z = U x αx + y = αx + y

,

т.е.

вектор

z

отразился

относительно

гиперплоскости x .

Лемма 9. Пусть е произвольный единичный вектор:

e

= 1. Тогда для

всякого

вектора

y C

n

существует

вектор

x C

n

,

x

= 1

такой, что

U x y =

y e .

Доказательство. Так как вектора y

и

y e должны быть получены друг

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

, то вектор y y e

x

должен быть параллелен

x , т.е.

x = α y

y e . Коэффициент α найдем из

условия		x				= 1	. Получаем

	x = ±	y	y e
		y	y e

.

2.8. Алгоритм метода отражений

Метод отражений применяется для решения систем линейных уравнений Ax f . Это один из лучших методов для решения СЛАУ общего вида (матрица системы может быть как действительной, так и комплексной). Идея метода заключается в следующем: матрица A системы раскладывается в произведение двух матриц – унитарной матрицы и правой треугольной матрицы A=WT, где W унитарная матрица; T правая треугольная матрица.

Унитарная матрица W – такая матрица, для которой выполнено:W W * E , где E единичная матрица. Унитарную матрицу W

33

A1 X B1 .

можно получить как матрицами отражения

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

Vi :	W Vi .
	i

Разложение матрицы:

a			a
	11		12
	a		a
A		21		22
			an2
an1

	a
		1n
	a
		2n
	ann

.

системы в произведение унитарной и правой треугольной происходит в несколько этапов:

задаем вектор S . В качестве данного вектора выбираем первый

столбец матрицы A системы S

Находим вектор ω1 по формуле

(a	, a		21	,
11
ω		S
		S

, a S e S e

n1	)

,

.

где	e единичный вектор. Заметим,	что
единичной длины (( , =1).
Строим матрицу отражения по формуле V1		E 2

Домножаем A слева на V1, получаем матрицу	A1
следующий вид:

ω ω* . 1 1

V1 A

вектор-столбец

, которая имеет

a		1	a	1		a	1
	11		a	12	1	a	1n	1
A1		0		22			2n		.
					1	a		1
		0	a
				n2			nn

Домножаем также B вектор свободных членов, слева на V1, получаем матрицу B1. Получаем новую систему

теперь в качестве вектора				выбираем	вектор		0, a22	1 ,..., an2	1 . В
			S			S
качестве же	e возьмем вектор, равный				e 0,1,0,...,0 . С помощью
приведенных выше формул			находим вектор 2 и строим матрицу V2
по формуле V2	E 2ω2 ω2 .
	*

Находим матрицу A2 V2 A1 , которая имеет вид

34

	a		2	a	2		a		2
		11		12				13
					2		a23		2
			0	a22
A			0		0		a		2
								33
2
							an3		2
			0		0

	a		2
		1n	2
	a2n
	a	3n	2

a2

nn

.

Домножаем B1 слева на V2. Получаем новую систему

A2

Продолжая описанный процесс построения, на (n-1) -м матрицу An 1 Vn 1 Vn 2 ... V2 V1 A , которая имеет вид

X B2

шаге

.

получим

		a		n 1	a		n 1
			11			12	n 1
				0	a22
A
n 1
							n 1
				0	a
						n 2

	a		n 1
	1n		n 1
	a2n
			n 1
	a
		nn

.

В итоге получим систему An 1 X Bn 1 . Далее решение можно легко найти, используя метод обратной подстановки:

			b	n 1
x
			n
	n		a	n 1
				nn

,

			n 1			n		n 1
		b					a		x
			k					ki		i
x
					i k 1
	k			a		n 1
						kk

,

k

n

1,...,1

.

Алгоритм состоит из двух частей. Сначала приводим исходную систему к верхней треугольной системе, а затем вычисляем векторрешение (аналогично обратному ходу метода Гаусса).

2.9. Примеры

Пример 2.1

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

10х				2х				2			3х			3			4х		4		1,
			1
	х			21х							3х							4х				2 ,
									2						3					4
			1
	х		5х				х						3,
		2				3						4
	х		х		2	х				3		8х				4		10.
	1

Решение. Составим расширенную матрицу системы:

		10	2	3	4	1
		1		3		2
			21		4
	A	0	1	5	1	3	.
		1	1	1	8	10
			35

Метод Гаусса. Ручной счет.

Прямой ход.

	10 2 3					4	1		10					10 2 3					4	1		10
	1 21				3	4 2			( 1)			→		1			21 3 4			2 ( 1)			→
	0 1				5	1	3							0 1 5 1						3
	1 1 1					8 10								1 1 1					8 10
			1		0,2	0,3	0,4		0,1									1	0,2		0,3	0,4	0,1
				21			4				1строка								21,2			4,4			( 21,2)
			1			3			2									0			2,7		1,9
→			0		1	5	1		3								→	0	1		5	1	3
			1		1	1	8		10		1строка							0	0,8		0,7	7,6	9,9		0,8
			1	0,2		0,3			0,4			0,1
						0,127 0,208						0,09
→			0		1														→
			0		1	5			1			3			2 строка
			0		1	0,875			9,5			12,375			2 строка
			1	0,2		0,3			0,4			0,1
						0,127						0,09
→			0		1			0,208											→
			0		0	4,873		0,792				3,09			( 4,873)
			0		0	1,002		9,292				12,465					1,002
			1	0,2		0,3			0,4			0,1
						0,127						0,09
→			0		1			0,208											→
			0		0	1		0,163				0,634
			0		0	1		9,271				12,435					3строка
			1	0,2		0,3			0,4			0,1
						0,127						0,09
→			0		1			0,208											→
			0		0	1		0,163				0,634
			0		0	0		9,433				13,069					9,433
			1	0,2		0,3			0,4			0,1
						0,127						0,09
→			0		1			0,208
			0		0	1		0,163				0,634
			0		0	0			1			1,385

36

→

Треугольный вид получен. Обратный ход:

x	4
x	3
x	2
x
1

1,385,

0,634 ( 0,163)x4 0,634 ( 0,163) 1,385 0,409,

0,09 0,208x4 ( 0,127)x3 0,09 0,208 1,385 ( 0,127) ( 0,409) 0,429,

0,1 0,4x4 0,3x3 0,2x2 0,1 0,4 1,385 0,3 ( 0,409) 0,2 ( 0,429) 0,246.

Ответ:	x	0,246	,	x	2	0,429	,	x	3	0,409	,	x	4
	1

Решение метода Гаусса в Microsoft Excel

1,385	.

представлено на рис. 2.1.

Рис. 2.1. Метод Гаусса (решение в Microsoft Excel)

37

Формулы в Microsoft Excel представлены на рис. 2.2.

Рис. 2.2. Формулы в Microsoft Excel

Метод простой итерации. Ручной счет

В расчетах использовать точность ε=0,1.

38

Условие сходимости:

10 2 3 4	10 9	выполнено ,
21 1 3 4	21 8	выполнено ,
5 0 1 1	5 2	выполнено ,
8 1 1 1	8 3	выполнено .

Итерационные формулы:

				1 2x		i	3x			i	4x	i
x	i	1				2				3		4	,
1							10
				3 x
					i	x		i
x	i 1				2			4	,				x	i 1
	3			5										4

Начальные приближения:

Итерация 1, i=0:

		x				2 x			i	3x		i	4x		i	,
			i 1					1				3			4
			2							21
	10 x				i	x	i	x		i
											.
				1			2			3
						8
x 0		0 ,			x 0 0 , x0						0		,	x 0	0 .
1						2				3				4

			1 2x	0	3x		0	4x		0			1 2 0 3 0 4 0				1
x	1			2			3			4								0,1,
1						10								10		10
			2 x						4x
					0	3x		0			0			2 0 3 0 4 0			2
x	1			1				3			4								0,095,
	2					21								21			21

x31

	x	1
		4

3 x20 x40

5

10 x	0	x
1
		8

3 0 0

5

0	x	0		10
2		3

30,6,

5

	0 0 0		10	1,25.
	8		8

x
1
x	2

x1 1

x1 2

	x	0		0,1 0 0,1
	1
	x		0	0,095 0
			2

< 0,1 – не выполнено, 0,095 <0,1 – не выполнено,

	x	1
		3

x14

	3 x	0	x		0			3 0 0
		2			4
	5							5
	10 x0			x0			x0			10
			1			2		3
				8

30,6

5

0 0 0

8

<0,1 – не выполнено,

108 1,25<,1 – не выполнено.

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

Итерация 2, i=1:

	x	2
	1
	x	2
		2
	x	2
		3
	x	2
		4

	1 2x		1	3x			1	4x			1				1 2		0,095 3 ( 0,6) 4 1,25
			2				3				4										0,201,
					10													10
	2 x			1	3x			1	4x			1				2	0,1 3 ( 0,6) 4 1,25
																				0,414,
			1					3				4
					21													21
	3 x	1	x			1			3 ( 0,095) 1,25
		2				4												0,369,
	5														5
	10 x1			x1			x1					10 0,1 ( 0,095) ( 0,6)
			1			2			3										1,324,
					8												8

x	x2	x1	0,201 0,1 0,301 <0,1 – не выполнено,
1	1	1
x2	x22	x12	0,414 ( 0,095) 0,319 <0,1 – не выполнено,
x3	x32	x31	0,369 ( 0,6) 0,231 <0,1 – не выполнено,
			39

x		x	2	x	1
	4		4		4

Условие на вычисления.

Итерация 3,

1,324 1,25

точность

i=2:

0,074 <0,1 – выполнено.

не выполнено, следовательно, продолжаем

	x	3
	1
	x	3
		2
	x	3
		3
	x	3
		4

	1 2x		2		3x				2	4x				2			1	2	( 0,414) 3 ( 0,369) 4 1,324
			2						3					4									0,236,
						10														10
	2 x			2		3x				2	4x				2			2	0,201 3 ( 0,369) 4 1,324
																						0,41,
			1							3					4
						21														21
	3 x	2	x				2				3 ( 0,414) 1,324
		2					4													0,418,
	5																5
	10 x		2		x			2	x			2			10 ( 0,201) ( 0,414) ( 0,369)
																					1,373,
			1					2				3
						8														8

x
1
x	2

x3

x	4

x3 1

x3 2

x33

x3 4

x1	0,236 ( 0,201) 0,035	<0,1 – выполнено,
2
x2	0,41 ( 0,414) 0,004	<0,1 – выполнено,
2
x32	0,418 ( 0,369) 0,05	<0,1 – выполнено,
x4	1,373 1,324 0,049 <0,1 – выполнено.
2

Условие на точность выполнено.

Ответ:

x1

0,236

,

x2

0,41,

x3

уравнений с точностью 0,1.

0,418

,

x	4

1,373

– решение системы

Метод простой итерации. Решение в Microsoft Excel представлено на рис. 2.3.

В расчетах использовать точность ε=0,001.

Рис. 2.3. Метод простой итерации (решение в Microsoft Excel)

Формулы в Microsoft Excel представлены на рис. 2.4.

40