Приведение матриц в верхней форме Хессенберга к форме Фробениуса

52. Наконец, рассмотрим приведение верхних матриц Хессенберга к форме Фробениуса (гл. 1, §§ 11—14). Обозначив поддиагональные элементы матрицы через можно предположить, что

Действительно, если то

где в верхней форме Хессенберга, и, следовательно.

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

Сначала допустим, что относительно ничего, кроме того, что они отличны от нуля, не предполагается. Приведение состоит из основного шага. Перед началом шага текущая матрица в случае имеет вид

Поддиагональные элементы не меняются в течение процесса; шаг заключается в следующем.

Для всех значений от 1 до выполнить шаги (i) и (ii):

(i) Вычисляем .

(ii) Вычитаем из строки (строка

(iii) Для всех значений от 1 до прибавляем к

Это завершает преобразование подобия.

Окончательная матрица X и ее диагональное преобразование подобия имеют вид

где элементы равны

а равны

Такое приведение требует приблизительно умножений.