Ортогонализация Грама ― Шмидта

24-07-2023

Перейти к: навигация, поиск

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

Содержание

Классический процесс Грама — Шмидта

Алгоритм

Пусть имеются линейно независимые векторы .

Определим оператор проекции следующим образом:

\mathbf{proj}_{\mathbf{b}}\,\mathbf{a} = 
{\langle \mathbf{a}, \mathbf{b} \rangle
\over
\langle \mathbf{b}, \mathbf{b}\rangle}
\mathbf{b} ,

где  — скалярное произведение векторов и . Этот оператор проецирует вектор ортогонально на вектор .

Классический процесс Грама — Шмидта выполняется следующим образом:


\begin{array}{lclr}
\mathbf{b}_1 & = & \mathbf{a}_1 & (1) \\
\mathbf{b}_2 & = & \mathbf{a}_2-\mathbf{proj}_{\mathbf{b}_1}\,\mathbf{a}_2 & (2) \\
\mathbf{b}_3 & = & \mathbf{a}_3-\mathbf{proj}_{\mathbf{b}_1}\,\mathbf{a}_3-\mathbf{proj}_{\mathbf{b}_2}\,\mathbf{a}_3 & (3) \\
\mathbf{b}_4 & = & \mathbf{a}_4-\mathbf{proj}_{\mathbf{b}_1}\,\mathbf{a}_4-\mathbf{proj}_{\mathbf{b}_2}\,\mathbf{a}_4-\mathbf{proj}_{\mathbf{b}_3}\,\mathbf{a}_4 & (4) \\
& \vdots & & \\
\mathbf{b}_N & = & \mathbf{a}_N-\displaystyle\sum_{j=1}^{N-1}\mathbf{proj}_{\mathbf{b}_j}\,\mathbf{a}_N & (N)
\end{array}

На основе каждого вектора может быть получен нормированный вектор: (у нормированного вектора направление будет таким же, как у исходного, а длина — единичной).

Результаты процесса Грама — Шмидта:

 — система ортогональных векторов либо

 — система ортонормированных векторов.

Вычисление носит название ортогонализации Грама — Шмидта, а  — ортонормализации Грама — Шмидта.

Доказательство

Докажем ортогональность векторов .

Для этого вычислим скалярное произведение , подставив в него формулу (2). Мы получим ноль. Равенство нулю скалярного произведения векторов означает, что эти вектора ортогональны. Затем вычислим скалярное произведение , используя результат для и формулу (3). Мы снова получим ноль, то есть вектора и ортогональны. Общее доказательство выполняется методом математической индукции.

Геометрическая интерпретация — вариант 1

Рис. 1. Второй шаг процесса Грама — Шмидта

Рассмотрим формулу (2) — второй шаг алгоритма. Её геометрическое представление изображено на рис. 1:

1 — получение проекции вектора на ;

2 — вычисление , то есть перпендикуляра, которым выполняется проецирование конца на . Этот перпендикуляр — вычисляемый в формуле (2) вектор ;

3 — перемещение полученного на шаге 2 вектора в начало координат. Это перемещение сделано на рисунке лишь для наглядности. Оно не является математическим действием и поэтому не отражается в формуле (2).

На рисунке видно, что вектор ортогонален вектору , так как является перпендикуляром, по которому проецируется на .

Рассмотрим формулу (3) — третий шаг алгоритма — в следующем варианте:


\begin{array}{lcr}
\mathbf{b}_3 = \mathbf{a}_3-(\mathbf{proj}_{\mathbf{b}_1}\mathbf{a}_3+\mathbf{proj}_{\mathbf{b}_2}\mathbf{a}_3) & & (6) \\
\end{array}

Её геометрическое представление изображено на рис. 2:

Рис. 2. Третий шаг процесса Грама — Шмидта

1 — получение проекции вектора на ;

2 — получение проекции вектора на ;

3 — вычисление суммы , то есть проекции вектора на плоскость, образуемую векторами и . Эта плоскость закрашена на рисунке серым цветом;

4 — вычисление , то есть перпендикуляра, которым выполняется проецирование конца на плоскость, образуемую векторами и . Этот перпендикуляр — вычисляемый в формуле (6) вектор ;

5 — перемещение полученного в начало координат. Это перемещение сделано на рисунке лишь для наглядности. Оно не является математическим действием и поэтому не отражается в формуле (6).

На рисунке видно, что вектор ортогонален векторам и , так как является перпендикуляром, по которому проецируется на плоскость, образуемую векторами и .

Таким образом, в процессе Грама — Шмидта для вычисления выполняется проецирование ортогонально на гиперплоскость?, формируемую векторами . Вектор затем вычисляется как разность между и его проекцией. То есть  — это перпендикуляр? от конца к гиперплоскости?, формируемой векторами . Поэтому ортогонален векторам, образующим эту гиперплоскость?.

Геометрическая интерпретация — вариант 2

Рассмотрим проекции некоторого вектора на вектора и как компоненты вектора в направлениях и (рис. 3):

Рис. 3. Вектор имеет компоненты в направлениях и

Если удалить из компоненту в направлении , то станет ортогонален (рис. 4):

Рис. 4. Вектор имеет компоненту в направлении , а компонента в направлении отсутствует (нулевая)

Если из удалить компоненты в направлениях и , то станет ортогонален и , и (рис. 5):

Рис. 5. Вектор не имеет компонент в направлениях и

В формуле (2) из вектора удаляется компонента в направлении вектора . Получаемый вектор не содержит компоненту в направлении и поэтому ортогонален вектору .

В формуле (3) из вектора удаляются компоненты в направлениях и (формуле 3 соответствует переход от рис. 3 к рис. 5; рис. 4 не соответствует формуле 3). Получаемый вектор ортогонален векторам и .

В формуле (4) из вектора удаляются компоненты в направлениях . Получаемый вектор ортогонален векторам .

Таким образом, по формулам (1) — (4) на основе векторов получается набор ортогональных векторов .

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

При вычислении на ЭВМ по формулам (1) — (5) вектора часто не точно ортогональны из-за ошибок округления. Из-за потери ортогональности в процессе вычислений классический процесс Грама — Шмидта называют численно неустойчивым.

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

Процесс Грама — Шмидта может быть сделан более вычислительно устойчивым путём небольшой модификации. Вместо вычисления как

этот вектор вычисляется следующим образом:

 \begin{array}{lclr}
\mathbf{a}_j^{(1)} & = &\mathbf{a}_j - \mathbf{proj}_{\mathbf{b}_1}\,\mathbf{a}_j & (8) \\
\mathbf{a}_j^{(2)} & = &\mathbf{a}_j^{(1)} - \mathbf{proj}_{\mathbf{b}_2} \, \mathbf{a}_j^{(1)} & (9) \\
& \vdots & & \\
\mathbf{a}_j^{(j-2)} & = & \mathbf{a}_j^{(j-3)} - \mathbf{proj}_{\mathbf{b}_{j-2}} \, \mathbf{a}_j^{(j-3)} & (10) \\
\mathbf{b}_j & = & \mathbf{a}_j^{(j-2)} - \mathbf{proj}_{\mathbf{b}_{j-1}} \, \mathbf{a}_j^{(j-2)} & (11)
\end{array}

Геометрическая интерпретация

Рассмотрим получение по формулам (8) — (11):

 \begin{array}{lllllr}
\mathbf{a}_3^{(1)} & = & \mathbf{a}_3       & - & \mathbf{proj}_{\mathbf{b}_1}\,\mathbf{a}_3        & (12) \\
\mathbf{b}_3       & = & \mathbf{a}_3^{(1)} & - & \mathbf{proj}_{\mathbf{b}_2}\,\mathbf{a}_3^{(1)}  & (13) \\
\end{array}

Геометрически это показано на рис 6:

Рис. 6. Геометрическое представление модифицированного процесса

На рис. 6 вектор обозначен как .

1 — получение проекции вектора на для формулы (12), то есть компоненты в направлении ;

2 — вычитание по формуле (12), то есть удаление из компоненты в направлении . Получаемый вектор ортогонален , так как не имеет компоненты в направлении ;

3 — перенос вектора в начало координат. Это перемещение сделано на рисунке лишь для наглядности. Оно не является математическим действием и поэтому не отражается в формуле (12).

4 — получение проекции вектора на для формулы (13), то есть компоненты в направлении ;

5 — вычитание по формуле (13), то есть удаление из компоненты в направлении . Получаемый вектор ортогонален , так как не имеет компоненты в направлении . При вычитании из компоненты в направлении в результирующем векторе не появляется компонента в направлении ;

6 — перенос вектора в начало координат. Это перемещение сделано на рисунке лишь для наглядности. Оно не является математическим действием и поэтому не отражается в формуле (13).

Таким образом, получаемый на рис. 6 вектор не имеет компонент в направлениях и и поэтому ортогонален и .


Рассмотрим непосредственно формулы (8) — (11).

В формуле (8) из вектора удаляется компонента в направлении вектора . Получаемый вектор не содержит компоненту в направлении и поэтому ортогонален вектору .

Далее в формуле (9) из результата удаляется его компонента в направлении вектора . Получаемый вектор не содержит компоненту в направлении и поэтому ортогонален вектору .

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

Эквивалентность классического и модифицированного процессов

Классический и модифицированный процессы можно сопоставить следующим образом:

 

\begin{array}{l}
\mathbf{b}_j\\
  \\
\mathbf{b}_j
\end{array}

\begin{array}{c}
= \\
  \\
=
\end{array}

\underbrace{
\underbrace{
\underbrace{

\begin{array}{c}
\mathbf{a}_j \\
   \\
\mathbf{a}_j
\end{array}

\begin{array}{c}
- \\
  \\
-
\end{array}

\begin{array}{c}
\mathbf{proj}_{\mathbf{b}_1}\,\mathbf{a}_j \\
   ||                                      \\
\mathbf{proj}_{\mathbf{b}_1}\,\mathbf{a}_j
\end{array}

}_{\mathbf{a}_j^{(1)}}

\begin{array}{c}
- \\
  \\
-
\end{array}

\begin{array}{c}
\mathbf{proj}_{\mathbf{b}_2}\,\mathbf{a}_j       \\
   ||                                            \\
\mathbf{proj}_{\mathbf{b}_2}\,\mathbf{a}_j^{(1)}
\end{array}

}_{\mathbf{a}_j^{(2)}}

\begin{array}{c}
- \\
  \\
-
\end{array}

\begin{array}{c}
\mathbf{proj}_{\mathbf{b}_3}\,\mathbf{a}_j       \\
   ||                                            \\
\mathbf{proj}_{\mathbf{b}_3}\,\mathbf{a}_j^{(2)}
\end{array}

}_{\mathbf{a}_j^{(3)}}

\begin{array}{ccc}
- & \ldots & - \\
               \\
- & \ldots & - 
\end{array}

\begin{array}{cc}
\mathbf{proj}_{\mathbf{b}_{j-1}}\,\mathbf{a}_j         & (14) \\
   ||                                                  &      \\
\mathbf{proj}_{\mathbf{b}_{j-1}}\,\mathbf{a}_j^{(j-2)} & (15)
\end{array}

Формула (14) показывает вычисление в классическом процессе, а формула (15) — в модифицированном.

Разница между (14) и (15) заключается в том, от каких векторов вычисляются компоненты: от в классическом процессе или от результата предыдущего вычитания, то есть от в модифицированном процессе. представляет собой , из которого удалены компоненты в направлениях . Компонента вектора в направлении при этом удалении не затрагивается и поэтому она в такая же, как в . Другими словами,

На рис. 6 равенство (16) имеет форму «».

Равенство (16) отображено знаками "||" между формулами (14) и (15). Это позволяет видеть, что формулы (14) и (15) эквивалентны. Таким образом, классический и модифицированный процессы эквивалентны, но только при идеально точных вычислениях. Реальные вычисления имеют погрешность из-за ошибок округления.

Особые случаи

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

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

Свойства

  • Произведение длин равно объёму параллелепипеда, построенного на векторах системы как на рёбрах.

Единственность результата

Матрица перехода от к и множество векторов определяются однозначно, если принять, что диагональные элементы матрицы перехода положительны.

Дополнительные толкования

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

Реализации

Реализация для пакета Mathematica

Данный скрипт, предназначенный для пакета Mathematica, проводит процесс ортогонализации Грама ― Шмидта над векторами, заданными в фигурных скобках предпоследней строки. Количество векторов и их координат могут быть произвольными. В данном случае для примера взяты векторы , , .

Projection[v1_, v2_] := (v1.v2*v2)/v2.v2
MultipleProjection[v1_, vecs_] := Plus @@ (Projection[v1, #1] &) /@ vecs
GramSchmidt[mat_] := Fold[Join[#1, {#2 - MultipleProjection[#2, #1]}] &, {}, mat]
GramSchmidt[{{-2, 1, 0}, {-2, 0, 1}, {-0.5, -1, 1}}]

Литература

  • Беклемишев Д. В. Курс аналитической геометрии и линейной алгебры. — М.: Наука.

Ортогонализация Грама ― Шмидта.

© 2011–2023 stamp-i-k.ru, Россия, Барнаул, ул. Анатолия 32, +7 (3852) 15-49-47