ГЛАВА 8. LR- и QR-алгоритмы
Введение
1. В гл. 1, § 42 мы показали, что любую матрицу преобразованием подобия можно привести к треугольному виду, и далее в § 47 показали, что матрица преобразования может быть выбрана унитарной. Очевидно, что любой алгорифм, дающий такое приведение, должен быть по существу итерационным, так как он приводит к определению нулей полинома.
Как показано в гл. 2, § 48, унитарное преобразование, приводящее нормальную матрицу к треугольному виду, на самом деле должно приводить ее к диагональному виду. Метод Якоби (гл. 5, § 3) дает такое приведение в случае вещественных симметричных матриц. Основная стратегия этого метода заключается в том, что при помощи последовательных элементарных ортогональных преобразований уменьшается норма матрицы из наддиагональных элементов. При этом в силу симметрии одновременно уменьшается норма матрицы из поддиагональных элементов.
Метод Якоби может быть весьма просто распространен на все нормальные матрицы (Голдстайн и Хорвиц, 1959), и естественно пытаться распространить метод, основанный на подобной стратегии, на приведение произвольных матриц к треугольному виду. Но, несмотря на большое количество попыток, до сих пор не появилось алгорифмов, сравнимых на практике с описанными в главах 6 и 7.
Методы исчерпывания, описанные в гл. 7, §§ 49—54, эффективно осуществляют приведение матрицы Хессенберга к треугольному виду, но они численно неустойчивы. В главе 9 будут описаны устойчивые методы исчерпывания, которые обеспечат подобное приведение произвольной матрицы к треугольному виду.
В этой главе мы займемся двумя алгорифмами, известными под названиями LR- и 
-алгорифмов. Первый из них, развитый Рутисхаузером, приводит произвольную матрицу к треугольному виду при помощи неунитарных преобразований. По моему мнению, создание этого метода является наиболее значительным вкладом в решение проблемы собственных значений, сделанным после появления автоматических вычислительных машин. Алгорифм QR, развитый позже Френсисом, тесно связан с QR-алгорифмом, но основан на использовании унитарных преобразований. Во многих отношениях он является наиболее эффективным из известных методов решения общей алгебраической проблемы собственных значений.
