Приведение матрицы к форме Хессенберга¶
Приведение матрицы к форме Хессенберга — это алгоритмическая операция в линейной алгебре, заключающаяся в преобразовании исходной квадратной матрицы к верхней (или нижней) форме Хессенберга посредством подобия. Форма Хессенберга — это матрица, у которой все элементы ниже (для верхней формы) или выше (для нижней формы) первой поддиагонали равны нулю. Данное преобразование широко применяется в численных методах как подготовительный этап для вычисления собственных значений, решения систем линейных уравнений и других задач, поскольку оно значительно сокращает объём вычислений по сравнению с работой с плотной матрицей общего вида.
¶Определение и виды
Матрица H размера n×n называется верхней матрицей Хессенберга, если для всех индексов i > j+1 выполняется условие h<sub>ij</sub> = 0. Иными словами, ненулевые элементы могут находиться только на главной диагонали, первой наддиагонали и выше. Нижняя форма Хессенберга определяется аналогично: h<sub>ij</sub> = 0 для всех j > i+1.
Верхняя форма используется чаще, так как она напрямую связана с QR-алгоритмом поиска собственных значений. Нижняя форма получается транспонированием верхней.
¶Методы приведения
Существуют два основных класса методов приведения матрицы к форме Хессенберга: на основе преобразований Гаусса (отражений Хаусхолдера) и на основе вращений Гивенса.
¶Метод отражений Хаусхолдера
Этот метод является наиболее распространённым благодаря своей численной устойчивости. На каждом шаге k (от 1 до n−2) строится матрица отражения (хаусхолдеровская матрица) P<sub>k</sub>, которая обнуляет все элементы под поддиагональю в k-м столбце. Преобразование выполняется по формуле:
A<sub>k+1</sub> = P<sub>k</sub><sup>T</sup> A<sub>k</sub> P<sub>k</sub>
При этом левое умножение обнуляет элементы в столбце, а правое — сохраняет уже полученные нули в строках. Сложность алгоритма составляет примерно (10/3)*n³ арифметических операций, что вдвое меньше, чем при приведении к полной треугольной форме.
¶Метод вращений Гивенса
Данный подход использует последовательность плоских вращений для обнуления отдельных элементов. Он требует большего числа операций (примерно (14/3)*n³), но обладает лучшими свойствами для разреженных матриц и удобен для параллельных вычислений. На практике применяется реже, чем метод Хаусхолдера.
¶Свойства и особенности
- Подобие: Преобразование является преобразованием подобия, поэтому собственные значения исходной матрицы A и полученной матрицы H полностью совпадают.
- Сохранение структуры: Если исходная матрица симметрична, то после приведения к форме Хессенберга она становится трёхдиагональной, что дополнительно упрощает дальнейшие вычисления.
- Инвариантность: Форма Хессенберга не является единственной — она зависит от конкретного алгоритма и порядка обнуления элементов. Однако все такие формы связаны между собой диагональным подобием.
¶Применение
Основная область применения — численные методы линейной алгебры, в частности:
- QR-алгоритм: Приведение к форме Хессенберга является обязательным предварительным шагом перед итерационным QR-алгоритмом для вычисления всех собственных значений матрицы. Это сокращает стоимость одной итерации с O(n³) до O(n²).
- Решение матричных уравнений: В некоторых итерационных методах (например, метод Арнольди) форма Хессенберга используется для построения проекционного подпространства Крылова.
- Матричные функции: Вычисление функций от матриц (экспонента, синус и др.) часто начинается с приведения матрицы к форме Хессенберга для ускорения вычислений.
¶Пример
Рассмотрим матрицу 4×4:
`` A = [ 4 1 2 3 1 5 0 1 2 0 6 2 3 1 2 7 ] ``
После приведения методом Хаусхолдера к верхней форме Хессенберга получается матрица вида:
`` H = [ 4.0 -3.74 0.00 0.00 -3.74 5.23 1.63 0.00 0.00 1.63 6.77 2.15 0.00 0.00 2.15 7.00 ] ``
Как видно, все элементы ниже первой поддиагонали равны нулю, а собственные значения матриц A и H идентичны.
¶Программная реализация
Приведение к форме Хессенберга реализовано во всех основных библиотеках численных методов, включая LAPACK (подпрограмма dgehrd), MATLAB (функция hess), NumPy (функция numpy.linalg.hessenberg в версиях 2.0+) и SciPy (функция scipy.linalg.hessenberg).
¶Источники
- Голуб Дж., Ван Лоун Ч. Матричные вычисления. — М.: Мир, 1999.
- Уилкинсон Дж. Х., Райнш К. Справочник алгоритмов на языке АЛГОЛ. Линейная алгебра. — М.: Машиностроение, 1976.
- Деммель Дж. Вычислительная линейная алгебра. — М.: Мир, 2001.