Введение перестановок
13. Численная устойчивость разложения в произведение двух треугольных матриц может быть улучшена введением там, где это необходимо, перестановок. Этот прием уже использовался при подобном преобразовании к форме Хессенберга. Рассмотрим аналогичную модификацию LR-алгорифма.
Если А — произвольная матрица, то, как мы видели в гл. 4, § 21, существуют такие матрицы
что
где все элементы
не более единицы. Преобразование подобия А заканчивается умножением
справа на
так что
В частном случае, когда перестановки не требуются и
произведение матриц, предшествующее А в (13.1), это матрица
для которой
так что
В этом случае матрица в правой части (13.2) есть
Соответственно предлагаем следующую модификацию LR-алгорифма.
На каждом этапе матрица
приводится к верхней треугольной матрице
методом Гаусса с перестановками. Затем
умножается справа на сомножители, обратные к используемым при приведении. Это дает нам матрицу
Объем вычислений такой же, как и при обычном
-процессе.
Для того чтобы избежать утомительных выкладок, проанализируем связь между
более подробно только в случае
Имеем
где все члены в круглых скобках равны
Обозначим
причем
имеют ту же форму, что и
но их поддиагональные элементы расположены в другом порядке. После перегруппировки сомножителей (13.3) дает
Очевидно,
единичная нижняя треугольная матрица,
это
которой переставлены строки и столбцы. Если положить
где
матрица перестановок, то