Реферат: Алгебраическая проблема собственных значений
получим совокупность полиномов, известную как последовательность Штурма и обладающую тем свойством, что корни полинома fj (l) располагаются между корнями полинома fj +1 (l). Поэтому для f1 (l) = a1 — l можно утверждать, что значение lК = а1 заключено между корнями полинома f2 (l) == (a2 — l) (a1 — l) —b2 2 . Это облегчает итерационное определение корней полинома, так как если известны границы интервалов, в которых лежат значения корней полинома, то их можно найти методом половинного деления. Так последовательно находят корни всех полиномов, и последний из них fn (l) дает все искомые п собственные значения. Эту процедуру можно проиллюстрировать графически (см. рис. 3).
Последовательность Штурма обладает еще и таким свойством: для любого значения b , при котором fn (b ) <> 0, число собственных значений матрицы A, больших b, равно числу изменений знака последовательности
1, f1 (b ), f2 (b ), … , (1)n fn (b).
Если целое число, равное числу изменений знака, обозначить через V(b), то число собственных значений в интервале действительных чисел [b, с] будет равно V(b)—V(c).
| |
| |
|
………………………………………………………………………………………………………..
| |
|
Рис. 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 .
Следовательно,
A m-1 = L m-1 R m-1,
A m = R m-1 L m-1 .
Этот процесс повторяется до тех пор, пока Ls не превратится в единичную матрицу Е, а 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 .
В пределе последовательность матриц А стремится к квазидиагональной форме. Этот метод сложнее предыдущего и требует больших затрат машинного времени. Однако его устойчивость,обусловленная использованием ортогональных преобразующих матриц, обеспечила ему прочную репутацию лучшего метода решения задач самой общей формы.
Пример 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 позволяет найти собственные значения.
{**********************************************************************}
Программа определение всех собственных значений произвольной матрицы размерности 6х5. Используются подпрограммы НSВСи АТЕIG из пакета программ для научных исследований фирмы IBM
{**********************************************************************}
DIMENSION A(6,6),RR(6),RI(6),IANA(6)
READ(5,100)((A(I,J),J=1,6),I=1,6)
WRITE(6,104)
104 FORMAT(///lX,’THE ORIGINAL MATRIX IS AS FOLLOWS’)
WRITE(6,103)
103 FORMAT(1X,65(-'--'))
WRITE(6,101)((A(I,J),J=1,6),I=1,6)
WRITE(6,103)
101FORMAT(6(1X,F10.5))
100 FORMAT(6F10.5)