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

Процесс Грама — Шмидта — это алгоритм ортогонализации и ортонормализации конечного набора линейно независимых векторов в евклидовом или эрмитовом пространстве. Процесс позволяет построить ортогональный базис (или ортонормированный базис) по заданному исходному базису, сохраняя при этом линейную оболочку каждого подмножества исходных векторов. Метод назван в честь датского математика Йёргена Педерсена Грама (1850—1916) и немецкого математика Эрхарда Шмидта (1876—1959), хотя впервые подобная процедура была описана ещё в работах Пьера-Симона Лапласа и Огюстена Луи Коши.

¶Определение и математическая формулировка

Пусть задано конечное множество линейно независимых векторов \(v_1, v_2, \dots, v_k\) в пространстве со скалярным произведением \(\langle \cdot, \cdot \rangle\). Процесс Грама — Шмидта последовательно строит ортогональные векторы \(u_1, u_2, \dots, u_k\) по следующему рекуррентному правилу:

\[ u_1 = v_1, \] \[ u_i = v_i - \sum_{j=1}^{i-1} \frac{\langle v_i, u_j \rangle}{\langle u_j, u_j \rangle} u_j, \quad i = 2, \dots, k. \]

Если требуется получить ортонормированный базис, каждый полученный вектор \(u_i\) нормируется: \(e_i = \frac{u_i}{\|u_i\|}\).

Геометрический смысл процедуры заключается в последовательном вычитании из очередного вектора его проекций на уже построенные ортогональные направления. В результате каждый новый вектор оказывается ортогональным всем предыдущим.

¶Свойства

• Сохранение линейной оболочки: для каждого \(i\) выполняется \(\operatorname{span}\{v_1, \dots, v_i\} = \operatorname{span}\{u_1, \dots, u_i\}\). Это означает, что процесс не меняет подпространства, порождённые первыми \(i\) векторами.
• Единственность: при фиксированном порядке исходных векторов ортогональный базис, полученный процессом Грама — Шмидта, определён однозначно с точностью до умножения каждого вектора на ненулевой скаляр.
• Обратимость: процесс можно обратить — по ортогональному базису и коэффициентам разложения восстановить исходные векторы.

¶Алгоритм

¶Классический вариант

1. Положить \(u_1 = v_1\).
2. Для \(i = 2\) до \(k\):

• Вычислить проекцию \(v_i\) на подпространство, порождённое \(u_1, \dots, u_{i-1}\):

\[ \operatorname{proj}_{U_{i-1}}(v_i) = \sum_{j=1}^{i-1} \frac{\langle v_i, u_j \rangle}{\langle u_j, u_j \rangle} u_j. \]

• Вычесть проекцию: \(u_i = v_i - \operatorname{proj}_{U_{i-1}}(v_i)\).

¶Модифицированный вариант (численно устойчивый)

Модифицированный процесс Грама — Шмидта (MGS) отличается порядком вычислений: вместо однократного вычитания полной проекции выполняется последовательное вычитание проекций на каждый из уже построенных ортогональных векторов. Это уменьшает накопление ошибок округления при вычислениях с плавающей запятой.

Алгоритм MGS:

1. Для \(i = 1\) до \(k\):

• \(u_i = v_i\).
• Для \(j = 1\) до \(i-1\):
• \(u_i = u_i - \frac{\langle u_i, u_j \rangle}{\langle u_j, u_j \rangle} u_j\).

¶Пример

Рассмотрим два вектора в \(\mathbb{R}^2\): \(v_1 = (1, 1)^T\), \(v_2 = (2, 3)^T\) со стандартным скалярным произведением.

1. \(u_1 = v_1 = (1, 1)^T\).
2. Вычисляем проекцию \(v_2\) на \(u_1\):

\[ \frac{\langle v_2, u_1 \rangle}{\langle u_1, u_1 \rangle} = \frac{2\cdot 1 + 3\cdot 1}{1^2 + 1^2} = \frac{5}{2} = 2.5. \] Тогда \(u_2 = v_2 - 2.5 u_1 = (2, 3)^T - (2.5, 2.5)^T = (-0.5, 0.5)^T\).

Полученные векторы \(u_1\) и \(u_2\) ортогональны: \(\langle u_1, u_2 \rangle = 1\cdot (-0.5) + 1\cdot 0.5 = 0\).

¶Применение

¶QR-разложение матриц

Процесс Грама — Шмидта лежит в основе одного из методов построения QR-разложения матрицы. Если столбцы матрицы \(A\) линейно независимы, то процесс позволяет представить \(A = QR\), где \(Q\) — матрица с ортонормированными столбцами, а \(R\) — верхняя треугольная матрица. Коэффициенты \(r_{ij}\) в этом разложении совпадают с коэффициентами, вычисляемыми в процессе ортогонализации.

¶Решение систем линейных уравнений

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

¶Вычислительная математика

В методе сопряжённых градиентов и других итерационных методах решения систем линейных уравнений используется идея последовательной ортогонализации, восходящая к процессу Грама — Шмидта.

¶Обработка сигналов и данных

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

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

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

¶Обобщения

Процесс Грама — Шмидта может быть применён не только к конечным наборам векторов, но и к последовательностям функций в гильбертовых пространствах. Например, ортогонализация степеней \(1, x, x^2, \dots\) с весом \(e^{-x^2}\) на всей числовой прямой приводит к полиномам Эрмита, а с весом \(1\) на отрезке \([-1, 1]\) — к полиномам Лежандра.

¶История

Первое описание процедуры, близкой к процессу Грама — Шмидта, встречается в работах Пьера-Симона Лапласа (1812) и Огюстена Луи Коши (1836). Датский математик Йёрген Педерсен Грам в 1879 году опубликовал работу по методу наименьших квадратов, в которой использовал ортогонализацию. Эрхард Шмидт в 1907 году в статье об интегральных уравнениях дал чёткое и систематическое изложение процесса, после чего метод стал широко известен.

¶Источники

• Гантмахер Ф. Р. Теория матриц. — М.: Наука, 1967.
• Стренг Г. Линейная алгебра и её применения. — М.: Мир, 1980.
• Björck Å. Numerical Methods for Least Squares Problems. — SIAM, 1996.
• Голуб Дж., Ван Лоун Ч. Матричные вычисления. — М.: Мир, 1999.