Инвариантность верхней формы Хессенберга

17. Сначала докажем, что верхняя форма Хессенберга инвариантна по отношению к модифицированному алгорифму. Мы уже обсудили приведение верхних матриц Хессенберга к треугольному виду при помощи метода Гаусса с перестановками (гл. 4, § 33). На шаге приведения выбор ведущего элемента возможен только из строк и единственный отличный от нуля элемент соответствующей матрицы (за исключением единичных диагональных элементов) находится в. позиции . Матрица поэтому имеет вид (гл. 1, § 40 (vii)). Нужно показать, что матрица вида

есть верхняя матрица Хессенберга. Здесь обозначает либо либо в зависимости от того, необходима или нет перестановка на шаге приведения к треугольному виду.

Будем доказывать по индукции. Предположим, что матрица

имеет первые столбцов в верхней форме Хессенберга, а остальные столбцы в треугольной форме, так что, например, при имеет вид

Следующий шаг — умножение справа на Если этот множитель мы переставляем столбцы в противном случае он ничего не меняет. В результате получается матрица вида (а) или

Умножение справа на состоит в добавлении к столбцу столбца умноженного на множитель, и, следовательно, в результате

получается матрица вида или

В обоих случаях матрица имеет первые столбцов в верхней форме Хессенберга, а остальные столбцы в треугольной форме. Нулевой элемент в не имеет особого значения. Результат установлен.

Для приведения к треугольному виду нужно приблизительно умножений, и еще последующего умножения справа, так что для одного полного шага LR-процесса производится умножений по сравнению с для полной матрицы.