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

Страница 6

………………………………………………………………………………………………………

	Корни многочлена fn-1 (l) f1 (b)
	Корни многочлена fn (l) f1 (b)

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

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

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

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

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

Метод LR

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

А = LR,

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

A2 = L-1 A R = L-1 (RL)L = R L.

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

Am-1 = L m-1 Rm-1,

Am = R m-1 Lm-1.

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

Метод QR

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

Am = Q m Rm.

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

Am+1 = Q mT Am Q m = Q mT Q m Rm Q m = Rm Q m.

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

Пример 3

Пусть требуется найти все собственные значения произвольной матрицы размерности 6 x 6

2,3	4,3	5,6	3,2	1,4	2,2
1,4	2,4	5,7	8,4	3,4	5,2
2,5	6,5	4,2	7,1	4,7	9,3
3,8	5,7	2,9	1,6	2,5	7,9
2,4	5,4	3,7	6,2	3,9	1,8
1,8	1,7	3,9	4,6	5,7	5,9

Сделаем это в два приема, приведя сначала матрицу с помощью преобразова­ния подобия к виду Гсссенберга, затем с помощью разновидности метода QR найдем собственные значения. В приведенной ниже программе использованы две подпрограммы из пакета программ для научных исследований фирмы IВМ. Подпрограмма НSВС преобразует матрицу размерности 6 x 6 к форме Гессенберга, а подпрограмма АТЕIG позволяет найти собственные значения.