Вращения Гивенса и отражения Хаусхолдера: ортогональные преобразования

Матрицы вращения Гивенса: точечное обнуление

Вращение Гивенса представляет собой ортогональную матрицу, которая описывает поворот в плоскости, натянутой на две выбранные координатные оси. Главная цель этого поворота — обнулить ровно один конкретный элемент вектора или матрицы, оставив остальные элементы практически нетронутыми. Матрица Гивенса отличается от единичной матрицы только четырьмя элементами, расположенными на пересечении строк и столбцов с индексами i и j: там стоят косинусы и синусы угла поворота. Вычисляя значения этих тригонометрических функций через координаты вектора, мы можем селективно «выбивать» нули под главной диагональю матрицы. Этот метод идеально подходит для работы с сильно разреженными матрицами, где нужно обнулить лишь несколько разрозненных элементов, не нарушая общую структуру.

Отражения Хаусхолдера: масштабное уничтожение элементов

В то время как вращения Гивенса действуют точечно, метод Хаусхолдера работает как «математическая кувалда». Матрица Хаусхолдера описывает зеркальное отражение пространства относительно гиперплоскости, проходящей через начало координат. Если нам нужно обнулить целый столбец матрицы ниже главной диагонали (как в методе Гаусса), отражение Хаусхолдера позволяет сделать это за одну единственную матричную операцию. Мы подбираем такой вектор нормали к гиперплоскости, чтобы при отражении исходный вектор столбца «упал» точно на нужную нам координатную ось, а все остальные его координаты мгновенно стали нулями. Матрица Хаусхолдера симметрична и ортогональна одновременно (она является обратной самой себе).

Алгоритмическая эффективность и QR-разложение

Выбор между Гивенсом и Хаусхолдером зависит от плотности матрицы. Для плотных матриц (заполненных ненулевыми числами) метод Хаусхолдера значительно эффективнее, так как он требует меньше арифметических операций для обнуления столбцов целиком и быстрее приводит матрицу к верхнетреугольному виду (QR-разложению). Для матрицы размера n на n алгоритм Хаусхолдера требует примерно (4/3)*n^3 операций. Однако в задачах параллельных вычислений метод Гивенса берет реванш: независимые точечные вращения в разных плоскостях можно вычислять одновременно на сотнях ядер современных видеокарт (GPU). Кроме того, метод Гивенса незаменим для матриц ленточной структуры, так как он сохраняет ширину ленты, не заполняя нули лишним «мусором».

Применение в фильтрах Калмана и обработке сигналов

Ортонормированные преобразования Гивенса и Хаусхолдера играют критическую роль не только в решении абстрактных СЛАУ, но и в задачах реального времени, таких как фильтрация сигналов и навигация. Например, в алгоритме фильтра Калмана (Square Root Information Filter, SRIF), который используется для управления космическими аппаратами и автопилотами, постоянно обновляемые матрицы ковариации ошибок могут потерять свойство положительной определенности из-за накопления погрешностей процессора. Применение ортогональных матриц Хаусхолдера для обновления состояния фильтра гарантирует, что дисперсии останутся положительными, а сам алгоритм будет работать бесконечно долго без сбоев и вычислительных катастроф.