part2 / vm

Полученные n систем линейных уравнений для j=1, 2, …, n, имеющих одну и ту же матрицу A и различные свободные члены, одновременно можно решить методом Гаусса. Применяя метод Гаусса, мы получим, например, для компонент j – столбца матрицы A−1

a(0) x	a(0) x	2 j	a(0) x		nj		(0)
11 1 j	12		1n				1 j
	(1)		(1)	xnj			(1)
	a22 x2 j		a2n				2 j
								, (2.31)
			(n 1)	xnj			(n 1)
			ann				nj

где ij(i 1) вычислены по формулам (2.25)i . Количество операций порядка O(n3).

2.3 Итерационные методы решения систем линейных алгебраических уравнений.

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

полученное с помощью прямого метода, либо самостоятельно получить это

решение.

Метод простой итерации. Найдем решение системы линейных уравнений

(2.17), предполагая, что все диагональные коэффициенты матрицы aii≠0.

Приведем систему Ax=b к виду

x=Cx+f,

(2.32)

где C- некоторая матрица, f – вектор–столбец.

Исходя из произвольного вектора x(0), строим итерационный процесс

x(k 1) Cx(k ) f ,

k 0,1,

или в развернутом виде

x(k 1)

c x(k ) c x(k )

c

x(k ) f

,

1

11 1

12

2

1n

n

1

(2.33)

x(k 1)

c

x(k ) c

n2

x(k ) c

nn

x(k ) f

n

.

n

n1 1

2

n

31

Произведя итерации, получим последовательность векторов x(1), x(2),…, x(n).

Можно доказать, что если элементы матрицы C удовлетворяют одному из условий

n
		cij	1,	(i 1, 2, , n)	(2.34)
j 1
или
n
		cij	1,	(i 1, 2, , n),	(2.35)
i 1

то процесс итерации сходится к точному решению системы x при любом x(0),

т.е. x lim x(k ) .

k

Оценка погрешности этого приближенного решения x(k) дается одной из

следующих формул:

xi

xi(k )

max

x(jk ) x(jk 1)

(2.36)

либо

1

j 1,n

n

xi

xi(k )

x(jk ) x(jk 1)

.

(2.37)

1

j 1

Иногда за x(0) берут f, хотя наиболее целесообразно в качестве компонент x(0)

взять приближенные значения неизвестных, полученные грубой прикидкой либо прямыми методами.

Приведение системы (2.18) к виду (2.32) можно осуществить различными способами. Если диагональные элементы матрицы A не равны нулю,

т.е. aii 0, i 1, n , то систему Ax=b можно записать в виде

x

1

b a x

a

x

1

a11

1

12 2

1n

n

x

1

b a x a

x

2

a22

2

21 1

2n n

(2.36)

x

1

b a x a

x

a

x

n

n2

nn 1

ann

n

n1 1

2

n

В этом случае элементы матрицы C определяются следующим образом:

	c			aij	(i j), c		0
		ij		aii		ii

32

и тогда условия (2.34), (2.35) соответственно приобретают вид

	n	a
			ij		1,	(i 1,2, , n) ,
		aii
	j 1
		a
	n
				ij	1,	(i 1,2, , n),
		aii
	i 1

Эти неравенства будут выполнены, если диагональные элементы матрицы A

удовлетворяют условию

				i		,
aii		aij	,		1, n
	j i

т.е. если модули диагональных коэффициентов для каждого уравнения системы больше суммы модулей всех остальных коэффициентов (не считая свободных членов).

Метод итераций, если он сходится, дает преимущества по сравнению с прямыми методами.

1. Если итерации сходятся достаточно быстро, т.е. если для решения системы требуется менее n итераций, то получаем выигрыш во времени, так как число арифметических операций, необходимых для одной итерации,

пропорционально n2 , а общее число арифметических действий в методе Гаусса,

например, пропорционально n3.

2. Погрешности округления в методе итераций сказываются значительно меньше, чем в методе Гаусса. Кроме того, метод итераций является самоисправляющимся, т.е. отдельная ошибка, допущенная в вычислениях, не отражается на окончательном результате, т.к. ошибочное приближение можно рассматривать как новый начальный вектор.

Последнее обстоятельство часто используется для уточнения значений неизвестных, полученных методом Гаусса.

3.Метод итераций становится особенно выгодным при решении систем, у

которых значительное число коэффициентов равно нулю.

4.Процесс итераций приводит к выполнению однообразных операций и сравнительно легко программируется на ЭВМ.

33

Метод итераций Зейделя. Метод Зейделя является модификацией метода простой итерации. Он заключается в том, что при вычислении (k+1) – го приближения неизвестного xi при i>1используются уже вычисленные ранее соответствующие приближения неизвестных x1, x2,…, xi–1. Таким образом, для системы (2.32) вычисления по методу Зейделя ведутся по формулам:

x(k 1)	c x(k ) c x(k ) c x(k ) f								,
1	11 1	12	2		1n n			1
x(k 1)	c x(k 1) c			x(k ) c				x(k ) f ,			(2.37)
2	21 1		22	2		2n		n	2
x(k 1)	c x(k 1)	c	n2	x(k 1)	c			x(k ) f			.
n	n1 1			2			nn n			n

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

метода Зейделя. Обычно метод Зейделя дает лучшую сходимость, чем метод простой итерации. Кроме того, метод Зейделя может оказаться более удобным

при программировании,	так как при вычислении xi(k 1) нет необходимости
хранить значения x(k ) , x(k ) , , x(k ) .
1 2	i

2.4 Решение систем уравнений с матрицами специального вида

(трехдиагональные матрицы)

Рассмотрим частный случай «разреженной» матрицы – трехдиагональную матрицу.

Определение. Квадратная матрица A размера n×n называется k–

диагональной (k – конкретное, нечетное, целое, положительное число), если ее

элементы удовлетворяют соотношениям:

aij 0, i j (k 1)2.

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

34

Метод прогонки решения систем алгебраических уравнений. Метод прогонки является модификацией прямого метода Гаусса для частного случая разреженной матрицы – трехдиагональной матрицы. Такие системы уравнений возникают при построении сплайн–функций (см.4.4), при конечно–разностных аппроксимациях краевых задач для обыкновенных дифференциальных уравнений и в уравнениях с частными производными.

Рассмотрим систему n линейных алгебраических уравнений с n

неизвестными, имеющую следующий специальный вид:

b1 x1

c1 x2

d1

a2 x1

b2 x2

c2 x3

d2

a3 x2

b3 x3

c3 x4

d3

(2.38)

an 1 xn 1

bn 1 xn 1

cn 1 xn

d n 1

an xn 1

bn xn

dn

На главной диагонали матрицы этой системы стоят элементы b1, b2,…, bn,

над ней – элементы c1, c2,…, cn, под ней – a1, a2,…, an. При этом обычно все коэффициенты bi не равны нулю.

Метод прогонки состоит из двух этапов – прямой прогонки (аналога прямого хода метода LU – разложений) и обратной прогонки (аналога обратного хода). Прямая прогонка состоит в том, что каждое неизвестное xi

выражается через xi+1 с помощью прогоночных коэффициентов Ai, Bi:

xi Ai xi 1 Bi ,

i 1,2, , n 1.

(2.39)

Из первого уравнения системы (2.37) найдем

x

c1

x

d1

2

1

b1

b1

С другой стороны, по формуле (2.39) x1=A1x2+B1. Приравнивая

коэффициенты в обоих выражениях для x1, получим

A

c1

, B

d1

(2.40)

1

b1

1

b1

Из второго уравнения системы (2.38) выразим x2

через x3, заменяя x1 по

формуле (2.39):

a2 A1 x2 B1 b2 x2 c2 x3 d2 .

35

Отсюда

x	2		c2 x3 d2 a2 B1 A x					3	B			,
			a2 A1 b2		2						2
где
A		c2	, B	d2 a2 B1	, e		a				A b .
						2				2
2		e2	2	e2							1		2

Аналогично можно вычислить прогоночные коэффициенты для любого номера

A	ci	,	B	di	ai Bi 1	,	e a A		b ,	i 2,3, , n 1 (2.41)
i	ei		i		ei		i	i i 1	i

Обратная прогонка состоит в последовательном вычислении неизвестных xi. Сначала нужно найти xn. Для этого воспользуемся выражением (2.39) при i=n−1 и последним уравнением системы (2.38). Запишем их:

xn 1 An 1 xn Bn 1 , an xn 1 bn xn dn .

Откуда, исключая xn–1, находим:

x			dn an Bn 1	B	.
	n
				n
			bn an An 1

Далее, используя формулу (2.39) и выражения для прогоночных коэффициентов (2.40), (2.41) последовательно вычисляем все неизвестные

xn 1 , xn 2 , , x1 .

При анализе алгоритма метода прогонки надо учитывать возможность деления на нуль в формулах (2.41). Можно показать, что при выполнении условий

b j a j c j ,

причем хотя бы для одного значения j имеет место строгое неравенство,

деления на нуль не возникает и система (2.39) имеет единственное решение.

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

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

36

Aq q,

Rn n

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

2.5 Методы решения проблемы собственных значений и собственных векторов матриц

Собственные значения и вектора матриц. Пусть матрица A –

симметричная (A=AT) квадратная матрица . Если для некоторого ненулевого вектора q и некоторого числа λ выполнено равенство

(2.42)

то λ и q называются соответственно собственным значением (или числом) и

собственным вектором матрицы A. В равенстве (2.42) неизвестны и число λ и

вектор q. Чтобы найти их, перепишем равенство (2.42) в виде однородной системы линейных уравнений

A En q Οn , (2.43)

где En=diag{1, …, 1}, On – нулевой элемент–матрица Rn n . Система (2.43)

имеет нетривиальное (отличное от нуля) решение лишь в том случае, если

det A En 0. (2.44)

Уравнение (2.44) называется характеристическим уравнением матрицы A

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

a11 x1 a12 x2 a1n xn 0 a21x1 a22 x2 a2n xn 0

......................................................

an1 x1 an2 x2 ann xn 0.

Определитель системы (2.44) является многочленом степени n

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

n n c1 n 1 cn 1 cn (2.45)

и называется характеристическим многочленом матрицы A. Таким образом,

собственные значения матрицы A – корни характеристического многочлена:

37

(ABC)−1=C−1B−1A−1

A QΛQT

AQ QΛ.

n i 0, i 1, n. Подставляя последовательно собственные числа λ1, λ2, …, λn в

однородную систему (2.43), находим собственные векторы qi							матрицы A:
Aq i	i qi ,	i 1, n. (2.46)
Считаем для простоты, что	все	i , i 1, n. различны.					Совокупность n

векторных равенств (2.46) можно записать в виде одного матричного равенства.

Введем для этого матрицу Q, столбцы которой есть собственные векторы матрицы A: Q={q1, q2, …, qn} и диагональную матрицу Λ с собственными

	n	матрицы A на диагонали: Λ=diag{λ1, λ2, …, λn}. Тогда n
значениями i i 1
равенств	(2.46)		эквивалентны	одному	матричному

A(q1,q2,…,qn)=(λ1q1,λq2,…,λnqn) или

(2.47)

Если матрица A вещественная симметричная, т.е. AT=A, то собственные векторы, отвечающие собственным числам, ортогональны:

qi ,q j ij qi 2 .

Поскольку собственные векторы qi определены с точностью до произвольного множителя (уравнение (2.42) и слева, и справа можно умножить на произвольное число α и переобозначить αq через q), то выберем длину каждого собственного вектора равной единице. Тогда матрицу Q, имеющую ортогональные столбцы, длины которых равны единице, называют ортогональной, (Q−1=QT). Домножив обе части матричного равенства (2.47)

слева на QT= Q−1, получим так называемую диагональную форму матрицы A

ΛQT AQ. (2.48)

Сдругой стороны, домножив (2.47) справа на QT, находим

(2.49)

что позволяет вернуться от диагональной формы матрицы к самой матрице A.

Для невырожденных матриц и тогда линейную систему Ax=b перепишем

x QΛQT 1 b QT 1 Λ 1Q 1b QΛ 1QT b

и так как

38

x=A−1b,

мы тотчас получаем

A 1 QΛ 1QT (2.50)

(сравним с формулой (2.49)).

Формула (2.50) является частным случаем формулы

A Q Λ QT , (2.51)

определяющей любую функцию от квадратной матрицы A

Λ diag 1 , 2 , , n .

Подытоживая результаты для симметричных матриц с различными ненулевыми собственными значениями, можно сформулировать следующий теоретический факт о спектральном разложении матрицы.

Справедливо следующее утверждение: для матрицы A, симметричной и имеющей n различных собственных значений λi, имеет место равенство

A 1q1q1T 2q2qT2 nqnqTn . (2.52)

По существу это иная форма записи равенства (2.49)

A QΛQT .

Задача нахождения всех собственных значений и собственных векторов числовой матрицы называется полной проблемой собственных значений. Эта задача в общем случае достаточно сложная. Мы остановимся только на некоторых важных частных задачах.

Нахождение максимального по модулю собственного значения.

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

Предположим, что квадратная матрица A порядка n имеет полную систему нормированных собственных векторов e1, e2,…, en, т.е.

Aei=λiei, ||ei||=||ei||2=‹ei, ei›1/2=1, (2.53)

39

где ‹x, y› – скалярное произведение в n – мерном векторном пространстве; λi –

собственные значения матрицы A, отвечающие собственному вектору ei, i=1,2,…,n. Такая полная система собственных векторов существует у симметричных матриц. Допустим, что

	1				2				3				n		.	(2.54)

Выберем произвольный вектор x(0)≠0. Имеем

x (0)=c1e1+ c2e2+…+ cnen,

где c1, c2, …, cn – координаты вектора x(0) в базисе e1, e2, …, en.

Предположим, что

с1≠0.

Последовательно находим векторы

x(k)=Ax(k–1), k=1,2,… (2.55)

Тогда согласно (2.53)

x(1)

Ax (0) A c e

c

e

2

... c

e

n

1 1

2

n

n

1 c1e1

η(1)

ci

i ei

i 1

и вообще,

x(k ) (k ) c e

η(k ) ,

(2.56)

1

1

1

(k )

2

k

n

k

где η

c2

e2

1

cn

1

en , причем из (2.54) имеем

2

k

η(k )

O

0.

1

k

Здесь и ниже в данном параграфе верхний индекс у векторов, например, x(k)

указывает номер приближения, у скаляров, например, λk верхний индекс означает степень, а в качестве нормы векторов принята вторая норма, т.е.

||x||=||x||2=‹x,x›1/2. Далее ограничимся рассмотрением класса симметричных матриц. Учитывая, что собственные вектора симметричной матрицы ортогональны, из формулы (2.56) получим следующее выражение для скалярного произведения:

40