Ортогонализация: определение и основные методы¶

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

¶Основные понятия

Ортогональность двух векторов \(x\) и \(y\) в евклидовом пространстве определяется равенством нулю их скалярного произведения: \(\langle x, y \rangle = 0\). Система векторов называется ортогональной, если все её векторы попарно ортогональны. Если при этом каждый вектор имеет единичную норму (\(\|x_i\| = 1\)), система называется ортонормированной.

Ортогонализация не меняет линейную оболочку исходной системы векторов: если векторы \(v_1, \dots, v_n\) линейно независимы, то после ортогонализации получается система \(u_1, \dots, u_n\), порождающая то же подпространство. Это свойство делает процедуру незаменимой при построении базисов.

¶Классические методы ортогонализации

¶Процесс Грама — Шмидта

Наиболее известный алгоритм — процесс Грама — Шмидта. Для линейно независимых векторов \(v_1, \dots, v_n\) он строит ортогональную систему \(u_1, \dots, u_n\) рекуррентно:

1. \(u_1 = v_1\);
2. для \(k = 2, \dots, n\):

\[ u_k = v_k - \sum_{j=1}^{k-1} \frac{\langle v_k, u_j \rangle}{\langle u_j, u_j \rangle} u_j. \]

Полученная система затем нормируется (\(w_k = u_k / \|u_k\|\)) для получения ортонормированного базиса. Алгоритм прост в реализации, однако численно неустойчив: из-за ошибок округления ортогональность быстро теряется, особенно при большой размерности или близких к линейно зависимым векторах.

¶Модифицированный метод Грама — Шмидта

Улучшенная версия алгоритма — модифицированный процесс Грама — Шмидта (MGS). Отличие заключается в том, что вычитание проекций выполняется поэтапно: на каждом шаге вектор \(v_k\) сначала ортогонализуется к \(u_1\), затем результат — к \(u_2\), и так далее. Это снижает накопление ошибок округления и даёт заметно лучшую численную устойчивость по сравнению с классическим вариантом. MGS широко применяется в QR-разложении матриц.

¶Ортогонализация Хаусхолдера (отражения Хаусхолдера)

Метод основан на применении матриц отражения (преобразований Хаусхолдера) для зануления поддиагональных элементов матрицы. Он используется при QR-разложении и считается одним из самых численно устойчивых подходов. В отличие от процесса Грама — Шмидта, метод Хаусхолдера работает не с отдельными векторами, а со всей матрицей, что делает его предпочтительным для плотных матриц высокой размерности.

¶Вращения Гивенса

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

¶Применение

Ортогонализация лежит в основе многих вычислительных алгоритмов:

• QR-разложение: представление матрицы \(A\) в виде произведения ортогональной матрицы \(Q\) и верхнетреугольной матрицы \(R\). Используется для решения переопределённых систем методом наименьших квадратов, вычисления собственных значений и сингулярных чисел.
• Метод наименьших квадратов: ортогонализация позволяет устойчиво решать задачи аппроксимации, избегая проблем с плохой обусловленностью нормальных уравнений.
• Построение ортогональных полиномов: в численном анализе применяются полиномы Лежандра, Чебышёва, Эрмита и Лагерра, которые получаются ортогонализацией степенных функций \(1, x, x^2, \dots\) с различными весовыми функциями.
• Квантовая химия и физика: метод Хартри — Фока и теория функционала плотности используют ортогонализацию для построения базисных наборов молекулярных орбиталей.
• Обработка сигналов и изображений: разложение сигналов по ортогональным базисам (например, преобразование Фурье, вейвлеты) применяется для сжатия данных и фильтрации.

¶Численная устойчивость

Выбор метода ортогонализации существенно влияет на точность вычислений. Классический процесс Грама — Шмидта может приводить к значительной потере ортогональности при плохо обусловленных матрицах. Модифицированный алгоритм и метод Хаусхолдера обеспечивают гораздо меньшую ошибку. На практике для плотных матриц стандартом де-факто является QR-алгоритм на основе отражений Хаусхолдера, реализованный в библиотеках LAPACK и MATLAB.

¶Ограничения

Ортогонализация применима только к линейно независимым системам векторов. Если исходные векторы линейно зависимы, процесс Грама — Шмидта приведёт к получению нулевого вектора, что сигнализирует о вырожденности. В таких случаях требуется предварительный анализ ранга матрицы или использование методов сингулярного разложения (SVD), которые позволяют работать с неполноранговыми системами.