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

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

виду.

Жозеф Лиувилль использовал собственные значения в исследованиях краевой задачи для дифференциальных уравнений 2–го порядка.

Жак Шарль Франсуа Штурм обобщил задачу о собственных значениях при решении систем обыкновенных дифференциальных уравнений.

За 80 лет до этого Жан Лерон Даламбер,

исследуя системы линейных дифференциальных Жан Лерон Даламбер уравнений и колебания струны, использовал

(1717 – 1783)

собственные значения.

5.1. Математическое обоснование метода

Рассмотрим квадратную матрицу n-го порядка:

	a		a	...	a
		11	12		1n
A	a21		a22	...	a2n
						.
		...	... ... ...
			an 2	...
	an1				ann

Собственные

значения i

(i 1, n)

квадратной

матрицы

A есть

действительные или комплексные числа,

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

условию

(A λE)X 0 , E – единичная матрица,

X x1 , x2 ,..., xn

-

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

матрицы A, соответствующий некоторому собственному значению .

Матрица A λE

называется характеристической матрицей матрицы A.

Так как в матрице E по главной диагонали стоят

, а все остальные

элементы равны нулю, то характеристическая матрица имеет вид

a

11

λ

a

12

...

a

1n

a

a

λ

...

a

C A λE

21

22

2n

.

...

... ... ...

a

a

...

a

λ

n1

n2

nn

Определитель этой матрицы называется характеристическим, или весовым определителем и равен

151

a	11	λ		a	12	...		a	1n
C det(A λE)	a	21	a	22	λ	...		a	21	.
	...			...		...		...
	a	n1		a	n 2	...	a	nn	λ

В развернутом виде он является многочленом n-й степени относительно , так как при вычислении этого определителя произведение элементов главной диагонали дает многочлен со старшим

членом

( 1)

n

λ

n

, т.е.

det(A λE) ( 1)

n

λ

n

p1λ

n 1

p2 λ

n 2

... ( 1)

n

pn , и

называется характеристическим многочленом.

Корни

λ1 , λ 2 ,..., λ n

этого

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

матрицы	A.	Числа	p1 , p2 ,..., pn	называются	коэффициентами
характеристического многочлена.
Ненулевой вектор X x1 , x2 ,..., xn называется собственным вектором
матрицы A,	если эта матрица переводит вектор X в вектор AX λX , то
есть произведение матрицы A на вектор X и произведение
характеристического числа на вектор X есть один и тот же вектор.
Каждому собственному значению λi				матрицы	соответствует свой
собственный вектор X i i			1,2,..., n .

Для определения координат собственного вектора составляется характеристическое уравнение A λE X 0 . Переписав его в векторном виде и выполнив умножение, получим систему линейных однородных уравнений

(a

λ)x

a

x

2

a

x

3

...

a

x

n

0,

11

1

12

13

1n

a

21

x

(a

22

λ)x

2

a

23

x

3

...

a

2n

x

n

0,

1

a

31

x

a

32

x

2

(a

33

λ)x

3

...

a

3n

x

n

0,

1

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

a

x

a

n2

x

2

a

n3

x

3

... (a

nn

λ)x

n

0.

n1 1

Определитель этой системы равен нулю, так как из этого условия были определены собственные значения матрицы A. Следовательно, система имеет бесконечное множество решений. Ее можно решить с точностью до постоянного множителя (как систему однородных уравнений). Решив эту систему, мы найдем все координаты собственного вектора X. Подставляя в систему однородных уравнений поочередно λ1 , λ 2 ,..., λ n , получаем n собственных векторов.

152

5.2. Метод итераций

Для решения частичной проблемы собственных значений (отыскания наибольших и наименьших собственных чисел) применяется метод простой итерации решения систем уравнений λ X AX . .

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

Итак, пусть det A λE 0		характеристическое уравнение; λ1 , λ 2 ,..., λ n
его корни, являющиеся собственными значениями матрицы					A aij .
Предположим, что	λ1 λ 2	... λ n , т.е.	λ1	наибольшее по	модулю

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

1) произвольно выбирают начальный вектор Y;

2) составляют последовательные итерации:

Y Y Y . Y Y

(1)	AY ,
(2)	A AY					A		2
	A A				Y A
(3)			2
. . . . . . . . . . . .
	A		A			Y
(m)				m-1
(m 1)		A A				m	Y

Y ,
3	Y ,
A		m		Y ,
A			m 1
				Y ;

3) выбирают из этой последовательности два последних значения и принимают за наибольшее собственное число следующее соотношение:

			( m 1)
λ		lim	y
			i	,
	1		( m )
		m
			yi
где yi(m 1) , yi(m) - соответствующие координаты векторов Y					(m 1)	, Y	(m)	.

Таким образом, взяв достаточно большой номер итерации m, можно с любой степенью точности вычислить наибольший по модулю корень λ1 характеристического уравнения матрицы. Для нахождения этого корня может быть использована любая координата вектора Y (m) , в частности, можно взять среднее арифметическое соответствующих отношений для разных координат.

5.3. Метод Леверрье-Фадеева

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

153

упрощен советским математиком Фаддеевым. Метод Леверрье основан на формулах Ньютона для сумм степеней корней алгебраического уравнения и заключается в следующем. Пусть

det(A λE) λ	n	p λ	n 1
		1

характеристический многочлен матрицы

p2 λn 2

A aij

...

,

p	n

и λ1, λ2 ,..., λn полная

совокупность корней суммы:

	S		λ	k	λ	k	... λ	k
		k		1		2		n

иначе:

характеристического многочлена. Рассмотрим

,	k 1, 2,..., n ,

S

1

λ

1

λ

2

...

λ

n

Sp A,

S

λ

2

λ

2

λ

2

Sp A

2

1

2

n

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

S

λ

n

λ

n

λ

n

Sp A

n

1

2

n

2

n

,

,

(каждая сумма			S k	есть
формулы Ньютона: Sk
	при k 1	p1	S1	,
	при k 2	p2		1	(S
				2		2

след матрицы

p S	k 1	... p	k 1	S	1
1

p S ),
1	1

Ak ).

kp	k	,

Тогда при k n справедливы откуда получаем:

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

	при k n	pn		1	(Sn	p1Sn 1 p2 Sn 2	... pn 1S1 ).
				n

	Следовательно, коэффициенты характеристического	многочлена
p1	, p2 , ..., pn можно легко определить, если известны суммы S1 , S	2 ,..., Sn .
	Таким образом, схема раскрытия характеристического многочлена
состоит в следующем:
	вычисляют степени Ak Ak 1 A (k 1,2,..., n);			;
	определяют S k суммы элементов главных диагоналей матриц A		k

по вышеприведенным формулам Ньютона находят коэффициенты

pi .
Видоизмененный метод Леверрье, предложенный Фаддеевым,
заключается в вычислении последовательности матриц	A1 , A2 ,..., An	по
следующей схеме:

154

A
1
A
2
. .
A	n
A
n

A;

AB1;

. . . . . .

-1	AB	n
AB
	n 1

.

2 ;

. ;

SpA q ;					B		A q E;
1	1				1		1	1
SpA	q		;		B		A q E;
2
2		2			2			2	2
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
SpA	q			;	B		A		q		E;
n 1
		n 1			n 1			n 1		n 1
n 1
SpA	q	;			B	A q E;
n
n	n				n			n	n

q

p ;

q

2

p

;...;

q

n 1

p

n 1

;

q

n

p

.

1

1

2

n

5.4. Метод Данилевского

Суть метода Данилевского заключается в приведении векового определителя к так называемому нормальному виду Фробениуса:

p	λ	p	2	p	3		p	n
1
	1	λ		0			0
D λ	0	1		- λ			0
	. . . . .
	0	0		0			- λ

.

Если

разлагая

D λ 1 n

нам удалось

λ	его		по
	n	p λ	n 1	p
		1			2

записать вековой определитель в такой форме, то, элементам первой строки, будем иметь

λ	n-2	... pn	.

Таким образом, задача сводится Фробениуса, подобной матрице инвариантны относительно операции

к нахождению матрицы P в форме A, так как собственные числа подобия, т.е.

	p		p	2		p	n 1	p
		1						n
		1	0			0		0
	P							.
		0	0			1		0

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

Опишем первое из преобразований, которое приводит n-ю строку исходной матрицы A к необходимому виду. Вначале преобразуем матрицу A в матрицу B по следующим формулам:

bij aij ai,n 1	anj	при
	an,n 1

1 i n;

j

n

1

,

155

bai,n 1 i,n 1 a

n,n

1

при

1 i

n

.

Последняя строка построенной матрицы B будет удовлетворять нашим условиям, номатрица В не будет подобна матрице A, поэтому проведем еще одно преобразование и получим матрицу С, подобную A и сохраняющую последнюю строку:

сij=bij при i=1,..,n-2.

cn-1 j=an 1b1 j+an 2b2 j+ . . . +an nbn j при j=1,...,n.

Таким образом, получили матрицу С, подобную A, и с последней строкой, как в матрице Р в форме Фробениуса. Далее преобразуем аналогично n-1 строку матрицы С и т.д. Допустим, что при преобразовании матрицы A в матрицу Фробениуса P мы пришли к матрице вида

	d		11	d	12
		d		d
			21		22
		d		d
	D		k1		k 2
		0		0
		0		0

причем оказалось, что dk k-1=0.

Тогда преобразования методом Здесь возможны два случая:

d	1k		d	1n 1	d	1n
d			d		d
	2k			2n 1		2n
dkk			dkn 1		dkn			,
1				0	0
0				1	0

Данилевского нельзя продолжить.

1.Существует элемент dkl, отличный от нуля, где l<k-1, тогда переставляем местами (k-1) и l столбцы и (k-1) и l строки и получаем матрицу, подобную D, для которой возможны дальнейшие преобразования по методу Данилевского.

2.Все элементы k строки равны нулю, тогда полученная матрица имеет вид

	D	D
			1
			0

L D 2

.

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

5.5. Примеры

Пример 5.1

156

Используя метод Леверрье-Фадеева, найти собственные числа матрицы, а также наибольший собственный вектор

		2,6	1,2
	A	1,2	2,1
		0,1	1,6

0,1
1,6
0,8

.

Решение. Определяем коэффициенты характеристического уравнения λ3 λ2 p1 λp2 p3 посредством построения последовательности матриц.

				2,6	1,2
	A			1,2	2,1
	1
				0,1	1,6
				2,6	1,2
	B			1,2	2,1
	1
				0,1	1,6
				2,6	1,2
	A			1,2	2,1
	2
				0,1	1,6

0,1
1,6
0,8
0,1
1,6
0,8
0,1
1,6
0,8

,

-

	p1 2,6 2,1 0,8 5,5.
5,5		0		0			2,9				1,2	0,1
											3,4
	0	5,5		0					1,2			1,6 .
	0	0	5,5							0,1	1,6	4,7
2,9			1,2		0,1					6,09		1,12
	1,2	3,4				1,6					1,12	3,14
	0,1		1,6		4,7						2,13	4,28

	2,13
	4,28
	1,19

,

				SpA		6,09 3,14 1,19	5,21.
	p			2
		2		2		2

Результаты дальнейших вычислений примут вид

			0,88		1,12	2,13				3,84		0
				1,12		4,28						3,84
B	2				2,07		,	A			0
								3
				2,13	4,28	4,02					0	0

	0
	0	,
	3,84

p	3	3,84.

Получим характеристическое уравнение:	λ	3	5,5λ	2	5,21λ 3,84 0.

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

чисел: λ1 0,4766; λ 2 2,0558; λ3 3,9203.

Решение в Microsoft Excel представлено на рис. 5.1. Собственные значения λ найдены с точностью 0,001.

157

а)

Рис. 5.1. Решение в Microsoft Excel:

а) нахождение коэффициентов характеристического уравнения; б) нахождение собственных значений

б)

Рис. 5.1. (окончание)

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

158

а)

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

а) нахождение коэффициентов характеристического уравнения; б) нахождение собственных значений

б)

Рис. 5.2. (окончание)

Пример 5.2

159

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

	2,6		1,2
	A	1,2	2,1
		0,1	1,6

0,1
1,6
0,8

.

Решение. Выбираем начально-свободный вектор

																																																	1
																																			Y		(0)			X			(0)
																																																		1 .
																																																		1
Вычисляем												Y			(1)	AY									(0)		,
				2,6					1,2					0,1									1							3,7
A				1,2					2,1						1,6
																								1							4,9 .
			0,1						1,6						0,8									1							2,3
				y	(k 1)						3,7															y		(k 1)						4,9									y		(k 1)								2,3
	(1)														,				(1)																	,			(1)						3										.
				1																								2
1				y			(k )					1							2								y		(k )					1					3					y		(k )							1
						1																						12																	13
																						2,6							1,2					0,1						3,7							15,27
	(2)	A Y							(1)				(2)
Y										,	Y										1,2									2,1				1,6						4,9								18,41 .
																				0,1									1,6					0,8						2,3									9,31
				y		(k 1)					15,27																			y	(k 1)				18,41														y		(k 1)					9,31
	(2)																,						(2)																		,		(3)								3						.
					1																										2
1				y				(k )				3,7											2							y		(k )				4,9							3							y		(k )				2,3
							1																								12																				13

Дальнейшие вычисления можно свести в табл. 5.1.

Результаты вычислений

A	2,6	1,2	-0,1	y	(k 1)		y	(k 1)
	1,2	2,1	1,6		1			2
				y		(k )	y		(k )
						1
	-0,1	1,6	0,8					12
Y0	1,00	1,00	1,00
Y1	3,70	4,90	2,30	4,13			3,76
Y2	15,27	18,41	9,31	3,99			3,90
Y3	60,86	71,88	35,38	3,96			3,90
Y4	240,96	280,59	137,22	3,94			3,91
Y5	949,49	1097,95	534,63	3,93			3,92
Y6	3732,75	4300,49	2089,48	3,93			3,92
Y7	14656,79	16853,49	8179,09	3,92			3,92
Y8	57531,93	66067,02	32043,18

Таблица 5.1

	y	(k 1)
		3
	y		(k )
			13

4,05

3,80

3,88

3,90

3,91

3,91

3,92

Дальнейшие итерации							можно прекратить. Собственное значение
					T		T
(наибольшее) λ1 3,92 ,
			X 1			X 8 57531,93; 66067,02; 32043,18. Нормированный
		T		(0,871; 1; 0,485) .
собственный вектор X 1

160