LR-алгоритм
3. Алгорифм Рутисхаузера основан на разложении матрицы в произведение треугольных (гл. 4, § 36). По Рутисхаузеру (1958)
где 
единичная нижняя треугольная, 
верхняя треугольная. В этой главе используется обозначение 
вместо 
для того, чтобы облегчить сравнение с работой Рутисхаузера.
Предположим, что мы составим преобразование подобия 
матрицы А. Тогда
Следовательно, если разложить А в произведение треугольных, а затем перемножить сомножители в обратном порядке, то получится матрица, подобная А. В LR-алгорифме этот процесс бесконечно повторяется. Если исходную матрицу переобозначить через 
то алгорифм определится уравнениями
Очевидно, что 
подобна 
следовательно, по индукции подобна 
Рутисхаузер показал, что при некоторых ограничениях
4. Прежде чем доказывать этот результат, установим некоторые соотношения между последовательными итерациями, которые будут постоянно нужны. Из (3.3) имеем
и повторное применение дает
или
Матрицы
это единичная нижняя треугольная и верхняя треугольная соответственно.
Рассмотрим произведение 
Имеем
Повторно применяя этот результат, получим
так что 
дает разложение матрицы 
в произведение двух треугольных.
