Исчерпывание при помощи вращений или устойчивых элементарных преобразований

52. Процесс исчерпывания для матриц Хессенберга формально тесно связан с методом Химана, а мы видели, что последний исключительно устойчив. Исчерпывание трехдиагональных матриц связано с простыми рекуррентными соотношениями, использующимися в § 8, и они также очень устойчивы.

Тем не менее процессы исчерпывания не обладают той же численной устойчивостью. Как можно понять, это происходит потому, что не используются перестановки. Но если они введены или если используются плоские вращения, то можно получить устойчивые формы исчерпывания. Рассмотрим их.

В § 14 было рассмотрено исключение последних элементов последнего столбца матрицы Хессенберга при помощи последовательного умножения справа на вращения в плоскостях В частном случае, когда собственному значению А, первый элемент преобразованной матрицы также должен быть равен нулю (если вычисления точные), и, следовательно, вычисленная матрица будет иметь такой же вид, как в (49.2). Преобразование подобия завершается умножением слева на вращения в плоскостях Очевидно, что каждое вращение сохраняет нули в последнем столбце и хессенбергову природу матрицы в верхнем левом углу, но вращение в плоскости вводит отличный от нуля элемент в позиции Окончательная матрица, полученная после прибавления имеет вид

Присутствие ненулевых элементов в последней строке неважно, и матрица Хессенберга порядка в верхнем левом углу снова имеет оставшееся собственное значение. Следовательно, форма Хессенберга инвариантна по отношению к нашему процессу исчерпывания, даже если используются плоские вращения. В точности эквивалентный процесс исчерпывания может быть выполнен с использованием устойчивых неунитарных элементарных преобразований, и он также приводит к матрице вида (52.1).

Прежде чем обсуждать влияние ошибок округления, рассмотрим те же процессы, примененные к трехдиагональной матрице. Ясно, что после окончания умножений справа преобразованная матрица имеет вид (50.1).

Покажем, что умножение слева приводит к матрице вида (52.1), т.е. трехдиагональная матрица заменяется, вообще говоря, полной матрицей Хессенберга. Доказательство по индукции. Предположим, что после умножения слева на вращение в плоскости матрица, например, для

случая имеет вид

При следующем вращении в плоскости строки заменяются своими линейными комбинациями. Следовательно, вообще говоря, строка получает ненулевые элементы в позициях от до строка — в позиции Снова элементарные устойчивые неунитарные преобразования дадут такой же эффект, хотя соответствующая матрица Хессенберга будет иметь большое количество нулевых элементов. Однако если исходная трехдиагональная матрица была симметричной, ортогональное исчерпывание сохраняет симметрию, и можно показать поэтому, что сохраняется трехдиагональный вид. Доказательство следующее.

Так как последний столбец окончательной матрицы равен нулю, должна равняться нулю и последняя строка. Это в свою очередь означает, что после умножения слева на вращение в плоскости элементы в позициях уже должны быть равны нулю. Действительно, единственная операция, которую осталось выполнить, это последовательная замена строки на

(здесь используются очевидные обозначения), и из того, что поддиагональные элементы исходной матрицы не равны нулю, следует, то не может быть Так как согласно (52.2) элементы в позициях каждой строки нулевые, соответствующие элементы строки уже должны быть равны нулю. Отсюда следует, что не вводится ненулевых элементов над диагональю, так что окончательная матрица трехдиагональная. Исчерпывание, использующее устойчивые неунитарные матрицы, не сохраняет симметрии или трехдиагонального вида.