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