Файл: Собственные значения.doc

*	*	0	0	0	0
*	*	*	0	0	0
*	*	*	*	0	0
*	*	*	*	*	0
*	*	*	*	*	*
*	*	*	*	*	*

---

5. Определение собственных значений симметричной трехдиагональной матрицы

Приведя симметричную матрицу к трехдиагональному виду методом Гивенса или Хаусхолдера, необходимо найти ее собст­венные значения. Чтобы ясней были достоинства трехдиагональной формы, сформулируем задачу о собственных значениях в виде

dеt(А—E) = 0,

где А — симметричная трехдиагональная матрица. Раcкрыв выражение в скобках, получим

a1 - 	b2		0
b1	a2 - 			= 0
			bn
0		bn	an - 

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

f_m() = (a_m - ) f_m-1 () – b² _m f_m-2().

Приняв

f₀ () = 1 и f₁ () = a₁ -  при r = 2, .... п,

получим совокупность полиномов, известную как последовательность Штурма и обладающую тем свойством, что корни полинома f_j () располагаются между корнями полинома f_j+1 (). Поэтому для f₁ () = a₁—  можно утверждать, что значение К = а₁ заключено между корнями полинома f₂ () == (a₂ — ) (a₁ — ) —b₂². Это облегчает итера­ционное определение корней полинома, так как если известны границы интервалов, в которых лежат значения корней полино­ма, то их можно найти методом половинного деления. Так после­довательно находят корни всех полиномов, и последний из них f_n () дает все искомые п собственные значения. Эту процедуру можно проиллюстрировать графически (см. рис. 3).

---

Последовательность Штурма обладает еще и таким свойством: для любого значения b, при котором f_n (b) <> 0, число собствен­ных значений матрицы A, больших b, равно числу изменений знака последовательности

1, f₁ (b), f₂ (b), … , (1)ⁿ f_n (b).

Если целое число, равное числу изменений знака, обозначить че­рез V(b), то число собственных значений в интервале действи­тельных чисел [b, с] будет равно V(b)—V(c).

Корень многочлена

f₁ ()

f₁ (b)

Корни многочлена

f₂ ()

f₁ (b)

Корни многочлена

f₃ ()

f₁ (b)

………………………………………………………………………………………………………..

Корни многочлена

f_n-1 ()

f₁ (b)

---

Корни многочлена

f_n ()

f₁ (b)

Рис. 3. Итера­ционное определение корней полинома

6. ДРУГИЕ МЕТОДЫ ВЫЧИСЛЕНИЯ СОБСТВЕННЫХ ЗНАЧЕНИЙ

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

X1	*		…	…	*	*	*
	x2	*	…	…	*	*	*
		x3	…	…	*	*	*
			…	…	*	*	*
				…	*	*	*
					…	*	*
	0					…	*
							*

---

где блоки Х_m, представляют собой матрицы размерности 2 х 2, расположенные на главной диагонали. Собственные значения блоков Х_m, являются в то же время собственными значениями исходной матрицы размерности п x п. Такая форма удобна, так как детерминант второго порядка блоков Х_m позволяет опреде­лять комплексные собственные значения, не вводя комплексных элементов в окончательную матрицу. Если все собственные зна­чения исходной матрицы действительные, то в окончательном виде она будет треугольной, причем собственные значения будут расположены на диагонали.

Метод LR

Этот метод первоначально был разработан Рутисхаузером в 1958 г. Метод основан на представлении матрицы A в виде про­изведения

А = LR,

где L — левая треугольная матрица с единичными диагональ­ными элементами, а R — правая треугольная. Применяя преоб­разование подобия L^-1 A R, видим, что,

A₂ = L^-1 A R = L^-1 (RL)L = R L.

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

A_m-1 = L _m-1 R_m-1,

A_m = R _m-1 L_m-1.

Этот процесс повторяется до тех пор, пока L_s не превратится в единичную матрицу Е, а R_s не приобретет квазидиагональную форму. Хотя этот метод очень удобен, он не всегда устойчив. Поэтому предпочтение часто отдают другому методу.

Метод QR

Метод QR. предложен Фрэнсисом в 1961 г. Соответствующий ему алгоритм определяется соотношением

A_m = Q _m R_m.

где Q _m — ортогональная матрица, а R_m — верхняя треугольная матрица. При использовании метода последовательно получаем

A_m+1 = Q _m^T A_m Q _m = Q _m^T Q _m R_m Q _m = R_m Q _m.

В пределе последовательность матриц А стремится к квазидиа­гональной форме. Этот метод сложнее предыдущего и требует больших затрат машинного времени. Однако его устойчивость,обусловленная использованием ортогональных преобразующих матриц, обеспечила ему прочную репутацию лучшего метода решения задач самой общей формы.

---