Введение перестановок

13. Численная устойчивость разложения в произведение двух треугольных матриц может быть улучшена введением там, где это необходимо, перестановок. Этот прием уже использовался при подобном преобразовании к форме Хессенберга. Рассмотрим аналогичную модификацию LR-алгорифма.

Если А — произвольная матрица, то, как мы видели в гл. 4, § 21, существуют такие матрицы что

где все элементы не более единицы. Преобразование подобия А заканчивается умножением справа на

так что

В частном случае, когда перестановки не требуются и произведение матриц, предшествующее А в (13.1), это матрица для которой так что В этом случае матрица в правой части (13.2) есть Соответственно предлагаем следующую модификацию LR-алгорифма.

На каждом этапе матрица приводится к верхней треугольной матрице методом Гаусса с перестановками. Затем умножается справа на сомножители, обратные к используемым при приведении. Это дает нам матрицу Объем вычислений такой же, как и при обычном -процессе.

Для того чтобы избежать утомительных выкладок, проанализируем связь между более подробно только в случае Имеем

где все члены в круглых скобках равны Обозначим

причем имеют ту же форму, что и но их поддиагональные элементы расположены в другом порядке. После перегруппировки сомножителей (13.3) дает

Очевидно, единичная нижняя треугольная матрица, это которой переставлены строки и столбцы. Если положить

где матрица перестановок, то