Алгебраическая проблема собственных значений
ома
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 позволяет найти собственные значения.
{**********************************************************************}
Программа определение всех собственных значений произвольной матрицы
размерности 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)
101. FORMAT(6(1X,F10.5))
100 FORMAT(6F10.5)
CALL HSBG(6,A,6)
WRITE(6,105)
105 FORMAT(///1X,'THE MATRIX W HESSENBUR5 FORM IS') WRITE(6,103)
WRITE(6,101)((A(I,J),J=1,6),I=1,6)
WRITE(6,103)
CALL ATEIG(6,A,RR,RI,IANA,6)
WRITE(6,106)
106. FORHAT(///1X,'THE EIGENVALUES ARE AS FOLLOUS')
WRITE(6,107)
107 FORMAT (1X, 23(‘-‘),/,4X,’REAL',12X,’IMAG’,/,23(‘-‘))
WRITE(6,102)(RR(I),PKI),I=1,6)
WRITE(6,108)
108 FORMAT(1X,23(‘-‘))
FORMAT<2(2X,F10.5)»
STOP
END
Результат получаем в виде
Исходная матрица имеет вид
|2.3000|4.300|5.600|3.200|1,400|2.2000|
|0 |00 |00 |00 |00 |0 |
|1.4000|2.400|5.700|8.400|3.400|5.2000|
|0 |00 |00 |00 |00 |0 |
|2.5000|6.500|4.200|7.100|4.700|9.3000|
|0 |00 |00 |00 |00 |0 |
|3.8000|5.700|2.900|1.600|2.500|7.9000|
|0 |00 |00 |00 |00 |0 |
|2.4000|5.400|3.700|6.200|3.900|1.8000|
|0 |00 |00 |00 |00 |0 |
|1.8000|1.700|3.900|4.600|5.700|5.9000|
|0 |00 |00 |00 |00 |0 |
Матрица в форме Гессенберга.
|-1.13162|3.2040| | | | |
| |2 -0, |-0.0563|3.88246|1.40000|2.20000|
| | |1 | | | |
|-0.75823|0.0746| | | |10.3628|
| |8 0, |0.48742|6.97388|5.37А35|3 |
| 0. |1.1378|-2.6380|10.1861| |17.0624|
| |3 -2, |3 |8 |7.15297|2 |
| 0. | 0. | | 7. | |13.9215|
| | |3.35891|50550 |7.09754|4 |
| 0. | 0. |0. |13.3627|10.5894|16.7842|
| | | |9 |7 |1 |
| 0. | 0. |0. |0. | | |
| | | | |5.70000|5.90000|
Собственные значения
-----------------------------------
Действит. Миним.
-----------------------------------
|25.52757 |0. |
|-5.63130 |0. |
|0.88433 |3.44455 |
|0.88433 |-3.44455 |
|-0.68247 |1.56596 |
|-0.68247 |-1.56596 |
7. ВЫБОР АЛГОРИТМА РЕШЕНИЯ ЗАДАЧ НА СОБСТВЕННЫЕ
ЗНАЧЕНИЯ
Выбор подходящего алгоритма для решения той или иной задачи на собственные
значения определяется типом собственных значений, типом матрицы и числом
искомых собственных значений. Чем сложнее задача, тем меньше число
алгоритмов, из которых можно выбирать. Таблица 1 позволяет облегчить этот
выбор. Обычно пакеты математического обеспечения ЭВМ содержат подпрограммы,
в которых используются все эти алгоритмы или некоторые из них. Одним из
эффективных способов использования имеющегося математического обеспечения
является одновременное применение двух подпрограмм, позволяющее совместить
их лучшие качества. Например, имея матрицу общего вида, можно методом
Хаусхолдера свести ее к виду Гессенберга, а затем с помощью алгоритма QR
найти собственные значения. При этом будут использованы как быстрота,
обеспечиваемая методом Хаусхолдера, так и универсальность алгоритма QR.
Таблица 1 Выбор алгоритма решения задачи на собственные значения
|Название |Применяе| |Рекомендуется для | |
|алгоритма |тся для |Результат |отыскания собственных|Примечание |
| | | |значений | |
| | | | | |
| | | | | |
| | | | | |
| | | |Наибол|Всех |Всех | |
| | | |ьшего |<=6 |>=6 | |
| | | |или | | | |
| | | |наимен| | | |
| | | |ьшего | | | |
|Определитель|Матриц |Собственны| |* | |Требует нахождения|
|(итерация) |общего |е значения| | | |корней полинома |
| |вида | | | | |общего вида |
|Итерация |То же |Собственны|* |* |* |Обеспечивает |
|(итерация) | |е значения| | | |наилучшую точность|
| | |и | | | |для наибольшего и |
| | |собственны| | | |наименьшего |
| | |е векторы | | | |собственных |
| | | | | | |значений |
|Метод Якоби |Симметри|Диагональн| |* |* |Теоретически |
|(преобразова|чных |ая форма | | | |требует |
|ние) |матриц |матрицы | | | |бесконечного числа|
| | | | | | |шагов |
| |То же |Трехдииона| |* |* |Требует знания |
| | |льльная | | | |корней простого |
| | |форма | | | |полинома |
|Метод | |матрицы | | | | |
|Гивенса | | | | | | |
|(преобразова| | | | | | |
|ние) | | | | | | |
| | | | | |
| | скачать работу |
Алгебраическая проблема собственных значений |