Процесс Грама ― Шмидта
Процесс Грама (англ.) ― Шмидта — это один из алгоритмов, в которых на основе счётного множества линейно независимых векторов <math>\mathbf{a}_1,\;\ldots,\;\mathbf{a}_N</math> строится множество ортогональных векторов <math>\mathbf{b}_1,\;\ldots,\;\mathbf{b}_N</math> или ортонормированных векторов <math>\mathbf{e}_1,\;\ldots,\;\mathbf{e}_N</math>, причём так, что каждый вектор <math>\mathbf{b}_j</math> или <math>\mathbf{e}_j</math> может быть выражен линейной комбинацией векторов <math>\mathbf{a}_1,\;\ldots,\;\mathbf{a}_j</math>.
Содержание
Классический процесс Грама — Шмидта
Алгоритм
Пусть имеются линейно независимые векторы <math>\mathbf{a}_1,\;\ldots,\;\mathbf{a}_N</math>.
Определим оператор проекции следующим образом:
- <math>\mathbf{proj}_{\mathbf{b}}\,\mathbf{a} =
{\langle \mathbf{a}, \mathbf{b} \rangle \over \langle \mathbf{b}, \mathbf{b}\rangle} \mathbf{b} ,</math> где <math>\langle \mathbf{a}, \mathbf{b} \rangle</math> — скалярное произведение векторов <math>\mathbf{a}</math> и <math>\mathbf{b}</math>. Этот оператор проецирует вектор <math>\mathbf{a}</math> коллинеарно вектору <math>\mathbf{b}</math>.
Ортогональность векторов <math>\mathbf{a}</math> и <math>\mathbf{b}</math> достигается на шаге (2).
Классический процесс Грама — Шмидта выполняется следующим образом:
- <math>
\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} </math>
На основе каждого вектора <math>\mathbf{b}_j \;(j = 1 \ldots N)</math> может быть получен нормированный вектор: <math>\mathbf{e}_j = {\mathbf{b}_j\over \| \mathbf{b}_j \|}</math> (у нормированного вектора направление будет таким же, как у исходного, а длина — единичной).
Результаты процесса Грама — Шмидта:
<math>\mathbf{b}_1,\;\ldots,\;\mathbf{b}_N</math> — система ортогональных векторов либо
<math>\mathbf{e}_1,\;\ldots,\;\mathbf{e}_N</math> — система ортонормированных векторов.
Вычисление <math>\mathbf{b}_1,\;\ldots,\;\mathbf{b}_N</math> носит название ортогонализации Грама — Шмидта, а <math>\mathbf{e}_1,\;\ldots,\;\mathbf{e}_N</math> — ортонормализации Грама — Шмидта.
Вывод алгоритма построения ортогонального базиса по линейно независимому набору векторов <math>{\mathbf{a}_i}</math>
Требуется построить ортогональную систему векторов <math>\{\mathbf{b_i}\}_{i=0}^n</math> по линейно-независимому набору векторов <math>\{\mathbf{a_i}\}_{i=0}^n</math>.
Процесс построения базиса заключается в проецировании первого вектора базиса на следующие за <math>\mathbf{a}_0</math> вектора <math>\mathbf{a}_i</math> и нахождения ортогональных к этим проекциям векторов <math>\mathbf{b}_i</math>.
Первый вектор строящегося базиса выбираем так:
1. <math>\mathbf{b}_0 = \mathbf{a}_0 </math> — так выбираем первый вектор строящегося базиса.
2. <math>\mathbf{e}_{b_0} = \frac{ \mathbf{b}_0 }{ \| \mathbf{b}_0 \| } </math> — нормируем вектор <math>\mathbf{b_0}</math>.
3. <math>\mathbf{b}_1 = \mathbf{a}_1 - \langle \mathbf{a_1}, \mathbf{e_{b_0}} \rangle \cdot \mathbf{e_{b_0}} </math>, где <math>\langle \mathbf{a_1}, \mathbf{e_{b_0}} \rangle \cdot \mathbf{e_{b_0}}</math> — проекция вектора <math>\mathbf{a_1}</math> на вектор <math> \mathbf{e_{b_0}} </math>, вдоль нормированного вектора <math>\mathbf{e_{b_0}}</math>.
4. <math>\mathbf{b}_2 = \mathbf{a}_2 - \langle \mathbf{a}_2, \mathbf{e_{b_0}} \rangle \cdot \mathbf{e_{b_0}} - \langle \mathbf{a}_2, \mathbf{e_{b_1}} \rangle \cdot \mathbf{e_{b_1}}. </math>
5. <math>\mathbf{b}_i = \mathbf{a}_i - \sum\limits_{k=0}^{i-1} \langle \mathbf{a}_i, \mathbf{e_{b_k}} \rangle \cdot \mathbf{e_{b_k}} </math> — в общем виде.
Заметим что:
<math>\langle \mathbf{a}, \mathbf{e_{b}} \rangle \cdot \mathbf{e_{b}} = \left\langle \mathbf{a}, \frac{ \mathbf{b}}{ \| \mathbf{b} \| } \right\rangle \cdot \frac{ \mathbf{b}}{ \| \mathbf{b} \| } = \frac{ \langle \mathbf{a}, \mathbf{b} \rangle}{\| \mathbf{b} \|^2} \cdot \mathbf{b}. </math>
А так как норма (длина вектора) <math> \| \mathbf{b} \|</math> в линейном пространстве <math>\mathbf{B}</math> порождается скалярным произведением, <math>\| \mathbf{b} \| = \sqrt{\langle \mathbf{b}, \mathbf{b} \rangle},\quad \mathbf{b} \in \mathbf{B},</math>
получаем:
<math>\frac{ \langle \mathbf{a}, \mathbf{b} \rangle}{\| \mathbf{b} \|^2} \cdot \mathbf{b} = \frac{ \langle \mathbf{a}, \mathbf{b} \rangle}{\langle \mathbf{b}, \mathbf{b} \rangle} \cdot \mathbf{b}.</math>
И получаем окончательный вид:
Первый вектор строящегося базиса определяется как:
1. <math>\mathbf{b}_0 = \mathbf{a}_0 </math> — первый вектор с индексом <math>i = 0</math>.
2. <math>\mathbf{b}_i = \mathbf{a}_i - \sum\limits_{k=0}^{i-1} \frac{ \langle \mathbf{a}_i, \mathbf{b}_k \rangle}{\langle \mathbf{b}_k, \mathbf{b}_k \rangle} \cdot \mathbf{b}_k </math> — все остальные векторы с индексами: <math> i = 1 \ldots N-1</math>.
Доказательство
Докажем ортогональность векторов <math>\mathbf{b}_1,\;\ldots,\;\mathbf{b}_N</math>.
Для этого вычислим скалярное произведение <math>\langle \mathbf{b}_1, \mathbf{b}_2 \rangle</math>, подставив в него формулу (2). Мы получим ноль. Равенство нулю скалярного произведения векторов означает, что эти векторы ортогональны. Затем вычислим скалярное произведение <math>\langle \mathbf{b}_1, \mathbf{b}_3 \rangle</math>, используя результат для <math>\langle \mathbf{b}_1, \mathbf{b}_2 \rangle</math> и формулу (3). Мы снова получим ноль, то есть векторы <math>\mathbf{b}_1</math> и <math>\mathbf{b}_3</math> ортогональны. Общее доказательство выполняется методом математической индукции.
Геометрическая интерпретация — вариант 1
Рассмотрим формулу (2) — второй шаг алгоритма.
Её геометрическое представление изображено на рис. 1:
1 — получение проекции вектора <math>\mathbf{a}_2</math> на <math>\mathbf{b}_1</math>;
2 — вычисление <math>\mathbf{a}_2-\mathbf{proj}_{\mathbf{b}_1}\mathbf{a}_2</math>, то есть перпендикуляра, которым выполняется проецирование конца <math>\mathbf{a}_2</math> на <math>\mathbf{b}_1</math>. Этот перпендикуляр — вычисляемый в формуле (2) вектор <math>\mathbf{b}_2</math>;
3 — перемещение полученного на шаге 2 вектора <math>\mathbf{b}_2</math> в начало координат. Это перемещение сделано на рисунке лишь для наглядности. Оно не является математическим действием и поэтому не отражается в формуле (2).
На рисунке видно, что вектор <math>\mathbf{b}_2</math> ортогонален вектору <math>\mathbf{b}_1</math>, так как <math>\mathbf{b}_2</math> является перпендикуляром, по которому <math>\mathbf{a}_2</math> проецируется на <math>\mathbf{b}_1</math>.
Рассмотрим формулу (3) — третий шаг алгоритма — в следующем варианте:
- <math>
\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} </math>
Её геометрическое представление изображено на рис. 2:
1 — получение проекции вектора <math>\mathbf{a}_3</math> на <math>\mathbf{b}_1</math>;
2 — получение проекции вектора <math>\mathbf{a}_3</math> на <math>\mathbf{b}_2</math>;
3 — вычисление суммы <math>\mathbf{proj}_{\mathbf{b}_1}\mathbf{a}_3 + \mathbf{proj}_{\mathbf{b}_2}\mathbf{a}_3</math>, то есть проекции вектора <math>\mathbf{a}_3</math> на плоскость, образуемую векторами <math>\mathbf{b}_1</math> и <math>\mathbf{b}_2</math>. Эта плоскость закрашена на рисунке серым цветом;
4 — вычисление <math>\mathbf{a}_3-(\mathbf{proj}_{\mathbf{b}_1}\mathbf{a}_3 + \mathbf{proj}_{\mathbf{b}_2}\mathbf{a}_3)</math>, то есть перпендикуляра, которым выполняется проецирование конца <math>\mathbf{a}_3</math> на плоскость, образуемую векторами <math>\mathbf{b}_1</math> и <math>\mathbf{b}_2</math>. Этот перпендикуляр — вычисляемый в формуле (6) вектор <math>\mathbf{b}_3</math>;
5 — перемещение полученного <math>\mathbf{b}_3</math> в начало координат. Это перемещение сделано на рисунке лишь для наглядности. Оно не является математическим действием и поэтому не отражается в формуле (6).
На рисунке видно, что вектор <math>\mathbf{b}_3</math> ортогонален векторам <math>\mathbf{b}_1</math> и <math>\mathbf{b}_2</math>, так как <math>\mathbf{b}_3</math> является перпендикуляром, по которому <math>\mathbf{a}_3</math> проецируется на плоскость, образуемую векторами <math>\mathbf{b}_1</math> и <math>\mathbf{b}_2</math>.
Таким образом, в процессе Грама — Шмидта для вычисления <math>\mathbf{b}_j</math> выполняется проецирование <math>\mathbf{a}_j</math> ортогонально на гиперплоскость?, формируемую векторами <math>\mathbf{b}_1,\;\ldots,\;\mathbf{b}_{j-1}</math>. Вектор <math>\mathbf{b}_j</math> затем вычисляется как разность между <math>\mathbf{a}_j</math> и его проекцией. То есть <math>\mathbf{b}_j</math> — это перпендикуляр? от конца <math>\mathbf{a}_j</math> к гиперплоскости?, формируемой векторами <math>\mathbf{b}_1,\;\ldots,\;\mathbf{b}_{j-1}</math>. Поэтому <math>\mathbf{b}_j</math> ортогонален векторам, образующим эту гиперплоскость?.
Геометрическая интерпретация — вариант 2
Рассмотрим проекции некоторого вектора <math>\mathbf{a}</math> на векторы <math>\mathbf{b}_1</math> и <math>\mathbf{b}_2</math> как компоненты вектора <math>\mathbf{a}</math> в направлениях <math>\mathbf{b}_1</math> и <math>\mathbf{b}_2</math> (рис. 3):
Если удалить из <math>\mathbf{a}</math> компоненту в направлении <math>\mathbf{b}_2</math>, то <math>\mathbf{a}</math> станет ортогонален <math>\mathbf{b}_2</math> (рис. 4):
Если из <math>\mathbf{a}</math> удалить компоненты в направлениях <math>\mathbf{b}_1</math> и <math>\mathbf{b}_2</math>, то <math>\mathbf{a}</math> станет ортогонален и <math>\mathbf{b}_1</math>, и <math>\mathbf{b}_2</math> (рис. 5):
В формуле (2) из вектора <math>\mathbf{a}_2</math> удаляется компонента в направлении вектора <math>\mathbf{b}_1</math>. Получаемый вектор <math>\mathbf{b}_2</math> не содержит компоненту в направлении <math>\mathbf{b}_1</math> и поэтому ортогонален вектору <math>\mathbf{b}_1</math>.
В формуле (3) из вектора <math>\mathbf{a}_3</math> удаляются компоненты в направлениях <math>\mathbf{b}_1</math> и <math>\mathbf{b}_2</math> (формуле 3 соответствует переход от рис. 3 к рис. 5; рис. 4 не соответствует формуле 3). Получаемый вектор <math>\mathbf{b}_3</math> ортогонален векторам <math>\mathbf{b}_1</math> и <math>\mathbf{b}_2</math>.
В формуле (4) из вектора <math>\mathbf{a}_N</math> удаляются компоненты в направлениях <math>\mathbf{b}_1,\;\ldots,\;\mathbf{b}_{N-1}</math>. Получаемый вектор <math>\mathbf{b}_N</math> ортогонален векторам <math>\mathbf{b}_1,\;\ldots,\;\mathbf{b}_{N-1}</math>.
Таким образом, по формулам (1) — (4) на основе векторов <math>\mathbf{a}_1,\;\ldots,\;\mathbf{a}_N</math> получается набор ортогональных векторов <math>\mathbf{b}_1,\;\ldots,\;\mathbf{b}_N</math>.
Численная неустойчивость
При вычислении на ЭВМ по формулам (1) — (5) векторы <math>\mathbf{b}_1,\;\ldots,\;\mathbf{b}_{N-1}</math> часто не точно ортогональны из-за ошибок округления. Из-за потери ортогональности в процессе вычислений классический процесс Грама — Шмидта называют численно неустойчивым.
Модифицированный процесс Грама — Шмидта
Процесс Грама — Шмидта может быть сделан более вычислительно устойчивым путём небольшой модификации. Вместо вычисления <math>\mathbf{b}_j</math> как
- <math> \mathbf{b}_j = \mathbf{a}_j - \mathbf{proj}_{\mathbf{b}_1}\,\mathbf{a}_j - \mathbf{proj}_{\mathbf{b}_2}\,\mathbf{a}_j - \ldots - \mathbf{proj}_{\mathbf{b}_{j-1}}\,\mathbf{a}_j \; (7) </math>
этот вектор вычисляется следующим образом:
- <math> \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} </math>
Геометрическая интерпретация
Рассмотрим получение <math>\mathbf{b}_3</math> по формулам (8) — (11):
- <math> \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} </math>
Геометрически это показано на рис 6:
На рис. 6 вектор <math>\mathbf{a}_3^{(1)}</math> обозначен как <math>\mathbf{R}</math>.
1 — получение проекции вектора <math>\mathbf{a}_3</math> на <math>\mathbf{b}_1</math> для формулы (12), то есть компоненты <math>\mathbf{a}_3</math> в направлении <math>\mathbf{b}_1</math>;
2 — вычитание по формуле (12), то есть удаление из <math>\mathbf{a}_3</math> компоненты в направлении <math>\mathbf{b}_1</math>. Получаемый вектор <math>\mathbf{R}</math> ортогонален <math>\mathbf{b}_1</math>, так как не имеет компоненты в направлении <math>\mathbf{b}_1</math>;
3 — перенос вектора <math>\mathbf{R}</math> в начало координат. Это перемещение сделано на рисунке лишь для наглядности. Оно не является математическим действием и поэтому не отражается в формуле (12).
4 — получение проекции вектора <math>\mathbf{R}</math> на <math>\mathbf{b}_2</math> для формулы (13), то есть компоненты <math>\mathbf{R}</math> в направлении <math>\mathbf{b}_2</math>;
5 — вычитание по формуле (13), то есть удаление из <math>\mathbf{R}</math> компоненты в направлении <math>\mathbf{b}_2</math>. Получаемый вектор <math>\mathbf{b}_3</math> ортогонален <math>\mathbf{b}_2</math>, так как не имеет компоненты в направлении <math>\mathbf{b}_2</math>. При вычитании из <math>\mathbf{R}</math> компоненты в направлении <math>\mathbf{b}_2</math> в результирующем векторе <math>\mathbf{b}_3</math> не появляется компонента в направлении <math>\mathbf{b}_1</math>;
6 — перенос вектора <math>\mathbf{b}_3</math> в начало координат. Это перемещение сделано на рисунке лишь для наглядности. Оно не является математическим действием и поэтому не отражается в формуле (13).
Таким образом, получаемый на рис. 6 вектор <math>\mathbf{b}_3</math> не имеет компонент в направлениях <math>\mathbf{b}_1</math> и <math>\mathbf{b}_2</math> и поэтому ортогонален <math>\mathbf{b}_1</math> и <math>\mathbf{b}_2</math>.
Рассмотрим непосредственно формулы (8) — (11).
В формуле (8) из вектора <math>\mathbf{a}_j</math> удаляется компонента в направлении вектора <math>\mathbf{b}_1</math>. Получаемый вектор <math>\mathbf{a}_j^{(1)}</math> не содержит компоненту в направлении <math>\mathbf{b}_1</math> и поэтому ортогонален вектору <math>\mathbf{b}_1</math>.
Далее в формуле (9) из результата удаляется его компонента в направлении вектора <math>\mathbf{b}_2</math>. Получаемый вектор <math>\mathbf{a}_j^{(2)}</math> не содержит компоненту в направлении <math>\mathbf{b}_2</math> и поэтому ортогонален вектору <math>\mathbf{b}_1</math>.
Путём дальнейшего последовательного удаления из результата его компонент получается вектор <math>\mathbf{b}_j</math>, не содержащий компонент в направлениях <math>\mathbf{b}_1,\;\ldots,\;\mathbf{b}_{j-1}</math> и потому ортогональный векторам <math>\mathbf{b}_1,\;\ldots,\;\mathbf{b}_{j-1}</math>.
Эквивалентность классического и модифицированного процессов
Классический и модифицированный процессы можно сопоставить следующим образом:
- <math>
\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}
</math>
Формула (14) показывает вычисление <math>\mathbf{b}_j</math> в классическом процессе, а формула (15) — в модифицированном.
Разница между (14) и (15) заключается в том, от каких векторов вычисляются компоненты: от <math>\mathbf{a}_j</math> в классическом процессе или от результата предыдущего вычитания, то есть от <math>\mathbf{a}_j^{(k)}</math> в модифицированном процессе. <math>\mathbf{a}_j^{(k)}</math> представляет собой <math>\mathbf{a}_j</math>, из которого удалены компоненты в направлениях <math>\mathbf{b}_1,\,\;\ldots,\;\mathbf{b}_{k}</math>. Компонента вектора <math>\mathbf{a}_j</math> в направлении <math>\mathbf{b}_{k+1}</math> при этом удалении не затрагивается и поэтому она в <math>\mathbf{a}_j^{(k)}</math> такая же, как в <math>\mathbf{a}_j</math>. Другими словами,
- <math>\mathbf{proj}_{\mathbf{b}_{k+1}}\,\mathbf{a}_j^{(k)} = \mathbf{proj}_{\mathbf{b}_{k+1}}\,\mathbf{a}_j (16)</math>
На рис. 6 равенство (16) имеет форму «<math>\mathbf{proj}_{\mathbf{b}_2}\,\mathbf{R} = \mathbf{proj}_{\mathbf{b}_2}\,\mathbf{a}_3 </math>».
Равенство (16) отображено знаками "||" между формулами (14) и (15). Это позволяет видеть, что формулы (14) и (15) эквивалентны. Таким образом, классический и модифицированный процессы эквивалентны, но только при идеально точных вычислениях. Реальные вычисления имеют погрешность из-за ошибок округления.
Особые случаи
Процесс Грама — Шмидта может применяться также к бесконечной последовательности линейно независимых векторов.
Кроме того, процесс Грама — Шмидта может применяться к линейно зависимым векторам. В этом случае он выдаёт <math>\mathbf{0}</math> (нулевой вектор) на шаге <math>j</math>, если <math>\mathbf{a}_j</math> является линейной комбинацией векторов <math>\mathbf{a}_1,\;\ldots,\;\mathbf{a}_{j-1}</math>. Если это может случиться, то для сохранения ортогональности выходных векторов и для предотвращения деления на ноль при ортонормировании алгоритм должен делать проверку на нулевые векторы и отбрасывать их. Количество векторов, выдаваемых алгоритмом, будет равно размерности подпространства, порождённого векторами (т.е. количеству линейно независимых векторов, которые можно выделить среди исходных векторов).
Свойства
- Матрица перехода от <math>\mathbf{a}_1,\;\ldots,\;\mathbf{a}_j</math> к <math>\mathbf{b}_1,\;\ldots,\;\mathbf{b}_j</math> — верхнетреугольная матрица.
- Произведение длин <math>\mathbf{b}_1,\;\ldots,\;\mathbf{b}_j</math> равно объёму параллелепипеда, построенного на векторах системы <math>\mathbf{a}_1,\;\ldots,\;\mathbf{a}_j</math> как на рёбрах.
Единственность результата
Матрица перехода от <math>\mathbf{a}_1,\;\ldots,\;\mathbf{a}_j</math> к <math>\mathbf{e}_1,\;\ldots,\;\mathbf{e}_j</math> и множество векторов <math>\mathbf{e}_1,\;\ldots,\;\mathbf{e}_j</math> определяются однозначно, если принять, что диагональные элементы матрицы перехода положительны.
Дополнительные толкования
Процесс Грама ― Шмидта может быть истолкован как разложение невырожденной квадратной матрицы в произведение ортогональной (или унитарной матрицы в случае эрмитова пространства) и верхнетреугольной матрицы с положительными диагональными элементами ― QR-разложение, что есть частный случай разложения Ивасавы.
Реализации
Реализация для пакета Mathematica
Данный скрипт, предназначенный для пакета Mathematica, проводит процесс ортогонализации Грама ― Шмидта над векторами, заданными в фигурных скобках последней строки. Количество векторов и их координат могут быть произвольными. В данном случае для примера взяты векторы <math>\{-2,\;1,\;0\}</math>, <math>\{-2,\;0,\;1\}</math>, <math>\{-0{.}5,\;-1,\;1\}</math>.
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}}]Projection[v1_, v2_] := (v1.v2*v2)/v2.v2
MultipleProjection[v1_, vecs_] := Plus @@ (Projection[v1, #1] &) /@ vecs
GramSchmidt[mat_] := Fold[Join[#1, {Normalize[#2 - MultipleProjection[#2, #1]]}] &, {}, mat]
GramSchmidt[{{-2, 1, 0}, {-2, 0, 1}, {-0.5, -1, 1}}]Реализация для Maxima
Данный скрипт, предназначенный для пакета Maxima, проводит процесс ортогонализации Грама ― Шмидта над векторами, заданными в квадратных скобках. Количество векторов и их координат могут быть произвольными. В данном случае для примера взяты векторы <math>[-2,1,0]</math>, <math>[-2,0,1]</math>, <math>[-0.5,-1,1]</math>.
load(eigen);
x: matrix ([-2,1,0],[-2,0,1],[-0.5,-1,1]);
y: gramschmidt(x);
Напишите отзыв о статье "Процесс Грама ― Шмидта"
Литература
- Беклемишев Д. В. Курс аналитической геометрии и линейной алгебры. — М.: Наука.
Ссылки
- www.youtube.com/watch?v=GhhpG1tCQLU Анимация процесса на плоскости
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
Отрывок, характеризующий Процесс Грама ― Шмидта
Княжна Марья тяжело вздохнула и этим вздохом признала справедливость слов Наташи; но словами она не согласилась с ней.– Разве можно забыть? – сказала она.
– Мне так хорошо было нынче рассказать все; и тяжело, и больно, и хорошо. Очень хорошо, – сказала Наташа, – я уверена, что он точно любил его. От этого я рассказала ему… ничего, что я рассказала ему? – вдруг покраснев, спросила она.
– Пьеру? О нет! Какой он прекрасный, – сказала княжна Марья.
– Знаешь, Мари, – вдруг сказала Наташа с шаловливой улыбкой, которой давно не видала княжна Марья на ее лице. – Он сделался какой то чистый, гладкий, свежий; точно из бани, ты понимаешь? – морально из бани. Правда?
– Да, – сказала княжна Марья, – он много выиграл.
– И сюртучок коротенький, и стриженые волосы; точно, ну точно из бани… папа, бывало…
– Я понимаю, что он (князь Андрей) никого так не любил, как его, – сказала княжна Марья.
– Да, и он особенный от него. Говорят, что дружны мужчины, когда совсем особенные. Должно быть, это правда. Правда, он совсем на него не похож ничем?
– Да, и чудесный.
– Ну, прощай, – отвечала Наташа. И та же шаловливая улыбка, как бы забывшись, долго оставалась на ее лице.
Пьер долго не мог заснуть в этот день; он взад и вперед ходил по комнате, то нахмурившись, вдумываясь во что то трудное, вдруг пожимая плечами и вздрагивая, то счастливо улыбаясь.
Он думал о князе Андрее, о Наташе, об их любви, и то ревновал ее к прошедшему, то упрекал, то прощал себя за это. Было уже шесть часов утра, а он все ходил по комнате.
«Ну что ж делать. Уж если нельзя без этого! Что ж делать! Значит, так надо», – сказал он себе и, поспешно раздевшись, лег в постель, счастливый и взволнованный, но без сомнений и нерешительностей.
«Надо, как ни странно, как ни невозможно это счастье, – надо сделать все для того, чтобы быть с ней мужем и женой», – сказал он себе.
Пьер еще за несколько дней перед этим назначил в пятницу день своего отъезда в Петербург. Когда он проснулся, в четверг, Савельич пришел к нему за приказаниями об укладке вещей в дорогу.
«Как в Петербург? Что такое Петербург? Кто в Петербурге? – невольно, хотя и про себя, спросил он. – Да, что то такое давно, давно, еще прежде, чем это случилось, я зачем то собирался ехать в Петербург, – вспомнил он. – Отчего же? я и поеду, может быть. Какой он добрый, внимательный, как все помнит! – подумал он, глядя на старое лицо Савельича. – И какая улыбка приятная!» – подумал он.
– Что ж, все не хочешь на волю, Савельич? – спросил Пьер.
– Зачем мне, ваше сиятельство, воля? При покойном графе, царство небесное, жили и при вас обиды не видим.
– Ну, а дети?
– И дети проживут, ваше сиятельство: за такими господами жить можно.
– Ну, а наследники мои? – сказал Пьер. – Вдруг я женюсь… Ведь может случиться, – прибавил он с невольной улыбкой.
– И осмеливаюсь доложить: хорошее дело, ваше сиятельство.
«Как он думает это легко, – подумал Пьер. – Он не знает, как это страшно, как опасно. Слишком рано или слишком поздно… Страшно!»
– Как же изволите приказать? Завтра изволите ехать? – спросил Савельич.
– Нет; я немножко отложу. Я тогда скажу. Ты меня извини за хлопоты, – сказал Пьер и, глядя на улыбку Савельича, подумал: «Как странно, однако, что он не знает, что теперь нет никакого Петербурга и что прежде всего надо, чтоб решилось то. Впрочем, он, верно, знает, но только притворяется. Поговорить с ним? Как он думает? – подумал Пьер. – Нет, после когда нибудь».
За завтраком Пьер сообщил княжне, что он был вчера у княжны Марьи и застал там, – можете себе представить кого? – Натали Ростову.
Княжна сделала вид, что она в этом известии не видит ничего более необыкновенного, как в том, что Пьер видел Анну Семеновну.
– Вы ее знаете? – спросил Пьер.
– Я видела княжну, – отвечала она. – Я слышала, что ее сватали за молодого Ростова. Это было бы очень хорошо для Ростовых; говорят, они совсем разорились.
– Нет, Ростову вы знаете?
– Слышала тогда только про эту историю. Очень жалко.
«Нет, она не понимает или притворяется, – подумал Пьер. – Лучше тоже не говорить ей».
Княжна также приготавливала провизию на дорогу Пьеру.
«Как они добры все, – думал Пьер, – что они теперь, когда уж наверное им это не может быть более интересно, занимаются всем этим. И все для меня; вот что удивительно».
В этот же день к Пьеру приехал полицеймейстер с предложением прислать доверенного в Грановитую палату для приема вещей, раздаваемых нынче владельцам.
«Вот и этот тоже, – думал Пьер, глядя в лицо полицеймейстера, – какой славный, красивый офицер и как добр! Теперь занимается такими пустяками. А еще говорят, что он не честен и пользуется. Какой вздор! А впрочем, отчего же ему и не пользоваться? Он так и воспитан. И все так делают. А такое приятное, доброе лицо, и улыбается, глядя на меня».
Пьер поехал обедать к княжне Марье.
Проезжая по улицам между пожарищами домов, он удивлялся красоте этих развалин. Печные трубы домов, отвалившиеся стены, живописно напоминая Рейн и Колизей, тянулись, скрывая друг друга, по обгорелым кварталам. Встречавшиеся извозчики и ездоки, плотники, рубившие срубы, торговки и лавочники, все с веселыми, сияющими лицами, взглядывали на Пьера и говорили как будто: «А, вот он! Посмотрим, что выйдет из этого».
При входе в дом княжны Марьи на Пьера нашло сомнение в справедливости того, что он был здесь вчера, виделся с Наташей и говорил с ней. «Может быть, это я выдумал. Может быть, я войду и никого не увижу». Но не успел он вступить в комнату, как уже во всем существе своем, по мгновенному лишению своей свободы, он почувствовал ее присутствие. Она была в том же черном платье с мягкими складками и так же причесана, как и вчера, но она была совсем другая. Если б она была такою вчера, когда он вошел в комнату, он бы не мог ни на мгновение не узнать ее.
Она была такою же, какою он знал ее почти ребенком и потом невестой князя Андрея. Веселый вопросительный блеск светился в ее глазах; на лице было ласковое и странно шаловливое выражение.
Пьер обедал и просидел бы весь вечер; но княжна Марья ехала ко всенощной, и Пьер уехал с ними вместе.
На другой день Пьер приехал рано, обедал и просидел весь вечер. Несмотря на то, что княжна Марья и Наташа были очевидно рады гостю; несмотря на то, что весь интерес жизни Пьера сосредоточивался теперь в этом доме, к вечеру они всё переговорили, и разговор переходил беспрестанно с одного ничтожного предмета на другой и часто прерывался. Пьер засиделся в этот вечер так поздно, что княжна Марья и Наташа переглядывались между собою, очевидно ожидая, скоро ли он уйдет. Пьер видел это и не мог уйти. Ему становилось тяжело, неловко, но он все сидел, потому что не мог подняться и уйти.
Княжна Марья, не предвидя этому конца, первая встала и, жалуясь на мигрень, стала прощаться.
– Так вы завтра едете в Петербург? – сказала ока.
– Нет, я не еду, – с удивлением и как будто обидясь, поспешно сказал Пьер. – Да нет, в Петербург? Завтра; только я не прощаюсь. Я заеду за комиссиями, – сказал он, стоя перед княжной Марьей, краснея и не уходя.
Наташа подала ему руку и вышла. Княжна Марья, напротив, вместо того чтобы уйти, опустилась в кресло и своим лучистым, глубоким взглядом строго и внимательно посмотрела на Пьера. Усталость, которую она очевидно выказывала перед этим, теперь совсем прошла. Она тяжело и продолжительно вздохнула, как будто приготавливаясь к длинному разговору.
Все смущение и неловкость Пьера, при удалении Наташи, мгновенно исчезли и заменились взволнованным оживлением. Он быстро придвинул кресло совсем близко к княжне Марье.
– Да, я и хотел сказать вам, – сказал он, отвечая, как на слова, на ее взгляд. – Княжна, помогите мне. Что мне делать? Могу я надеяться? Княжна, друг мой, выслушайте меня. Я все знаю. Я знаю, что я не стою ее; я знаю, что теперь невозможно говорить об этом. Но я хочу быть братом ей. Нет, я не хочу.. я не могу…
Он остановился и потер себе лицо и глаза руками.
– Ну, вот, – продолжал он, видимо сделав усилие над собой, чтобы говорить связно. – Я не знаю, с каких пор я люблю ее. Но я одну только ее, одну любил во всю мою жизнь и люблю так, что без нее не могу себе представить жизни. Просить руки ее теперь я не решаюсь; но мысль о том, что, может быть, она могла бы быть моею и что я упущу эту возможность… возможность… ужасна. Скажите, могу я надеяться? Скажите, что мне делать? Милая княжна, – сказал он, помолчав немного и тронув ее за руку, так как она не отвечала.
– Я думаю о том, что вы мне сказали, – отвечала княжна Марья. – Вот что я скажу вам. Вы правы, что теперь говорить ей об любви… – Княжна остановилась. Она хотела сказать: говорить ей о любви теперь невозможно; но она остановилась, потому что она третий день видела по вдруг переменившейся Наташе, что не только Наташа не оскорбилась бы, если б ей Пьер высказал свою любовь, но что она одного только этого и желала.
– Говорить ей теперь… нельзя, – все таки сказала княжна Марья.
– Но что же мне делать?
– Поручите это мне, – сказала княжна Марья. – Я знаю…
Пьер смотрел в глаза княжне Марье.
– Ну, ну… – говорил он.
– Я знаю, что она любит… полюбит вас, – поправилась княжна Марья.
Не успела она сказать эти слова, как Пьер вскочил и с испуганным лицом схватил за руку княжну Марью.
– Отчего вы думаете? Вы думаете, что я могу надеяться? Вы думаете?!
– Да, думаю, – улыбаясь, сказала княжна Марья. – Напишите родителям. И поручите мне. Я скажу ей, когда будет можно. Я желаю этого. И сердце мое чувствует, что это будет.
– Нет, это не может быть! Как я счастлив! Но это не может быть… Как я счастлив! Нет, не может быть! – говорил Пьер, целуя руки княжны Марьи.
– Вы поезжайте в Петербург; это лучше. А я напишу вам, – сказала она.
– В Петербург? Ехать? Хорошо, да, ехать. Но завтра я могу приехать к вам?
На другой день Пьер приехал проститься. Наташа была менее оживлена, чем в прежние дни; но в этот день, иногда взглянув ей в глаза, Пьер чувствовал, что он исчезает, что ни его, ни ее нет больше, а есть одно чувство счастья. «Неужели? Нет, не может быть», – говорил он себе при каждом ее взгляде, жесте, слове, наполнявших его душу радостью.
Когда он, прощаясь с нею, взял ее тонкую, худую руку, он невольно несколько дольше удержал ее в своей.
«Неужели эта рука, это лицо, эти глаза, все это чуждое мне сокровище женской прелести, неужели это все будет вечно мое, привычное, такое же, каким я сам для себя? Нет, это невозможно!..»
– Прощайте, граф, – сказала она ему громко. – Я очень буду ждать вас, – прибавила она шепотом.
И эти простые слова, взгляд и выражение лица, сопровождавшие их, в продолжение двух месяцев составляли предмет неистощимых воспоминаний, объяснений и счастливых мечтаний Пьера. «Я очень буду ждать вас… Да, да, как она сказала? Да, я очень буду ждать вас. Ах, как я счастлив! Что ж это такое, как я счастлив!» – говорил себе Пьер.
В душе Пьера теперь не происходило ничего подобного тому, что происходило в ней в подобных же обстоятельствах во время его сватовства с Элен.
Он не повторял, как тогда, с болезненным стыдом слов, сказанных им, не говорил себе: «Ах, зачем я не сказал этого, и зачем, зачем я сказал тогда „je vous aime“?» [я люблю вас] Теперь, напротив, каждое слово ее, свое он повторял в своем воображении со всеми подробностями лица, улыбки и ничего не хотел ни убавить, ни прибавить: хотел только повторять. Сомнений в том, хорошо ли, или дурно то, что он предпринял, – теперь не было и тени. Одно только страшное сомнение иногда приходило ему в голову. Не во сне ли все это? Не ошиблась ли княжна Марья? Не слишком ли я горд и самонадеян? Я верю; а вдруг, что и должно случиться, княжна Марья скажет ей, а она улыбнется и ответит: «Как странно! Он, верно, ошибся. Разве он не знает, что он человек, просто человек, а я?.. Я совсем другое, высшее».
Только это сомнение часто приходило Пьеру. Планов он тоже не делал теперь никаких. Ему казалось так невероятно предстоящее счастье, что стоило этому совершиться, и уж дальше ничего не могло быть. Все кончалось.
Радостное, неожиданное сумасшествие, к которому Пьер считал себя неспособным, овладело им. Весь смысл жизни, не для него одного, но для всего мира, казался ему заключающимся только в его любви и в возможности ее любви к нему. Иногда все люди казались ему занятыми только одним – его будущим счастьем. Ему казалось иногда, что все они радуются так же, как и он сам, и только стараются скрыть эту радость, притворяясь занятыми другими интересами. В каждом слове и движении он видел намеки на свое счастие. Он часто удивлял людей, встречавшихся с ним, своими значительными, выражавшими тайное согласие, счастливыми взглядами и улыбками. Но когда он понимал, что люди могли не знать про его счастье, он от всей души жалел их и испытывал желание как нибудь объяснить им, что все то, чем они заняты, есть совершенный вздор и пустяки, не стоящие внимания.
Когда ему предлагали служить или когда обсуждали какие нибудь общие, государственные дела и войну, предполагая, что от такого или такого исхода такого то события зависит счастие всех людей, он слушал с кроткой соболезнующею улыбкой и удивлял говоривших с ним людей своими странными замечаниями. Но как те люди, которые казались Пьеру понимающими настоящий смысл жизни, то есть его чувство, так и те несчастные, которые, очевидно, не понимали этого, – все люди в этот период времени представлялись ему в таком ярком свете сиявшего в нем чувства, что без малейшего усилия, он сразу, встречаясь с каким бы то ни было человеком, видел в нем все, что было хорошего и достойного любви.
Рассматривая дела и бумаги своей покойной жены, он к ее памяти не испытывал никакого чувства, кроме жалости в том, что она не знала того счастья, которое он знал теперь. Князь Василий, особенно гордый теперь получением нового места и звезды, представлялся ему трогательным, добрым и жалким стариком.
Пьер часто потом вспоминал это время счастливого безумия. Все суждения, которые он составил себе о людях и обстоятельствах за этот период времени, остались для него навсегда верными. Он не только не отрекался впоследствии от этих взглядов на людей и вещи, но, напротив, в внутренних сомнениях и противуречиях прибегал к тому взгляду, который он имел в это время безумия, и взгляд этот всегда оказывался верен.
«Может быть, – думал он, – я и казался тогда странен и смешон; но я тогда не был так безумен, как казалось. Напротив, я был тогда умнее и проницательнее, чем когда либо, и понимал все, что стоит понимать в жизни, потому что… я был счастлив».
Безумие Пьера состояло в том, что он не дожидался, как прежде, личных причин, которые он называл достоинствами людей, для того чтобы любить их, а любовь переполняла его сердце, и он, беспричинно любя людей, находил несомненные причины, за которые стоило любить их.
С первого того вечера, когда Наташа, после отъезда Пьера, с радостно насмешливой улыбкой сказала княжне Марье, что он точно, ну точно из бани, и сюртучок, и стриженый, с этой минуты что то скрытое и самой ей неизвестное, но непреодолимое проснулось в душе Наташи.
Все: лицо, походка, взгляд, голос – все вдруг изменилось в ней. Неожиданные для нее самой – сила жизни, надежды на счастье всплыли наружу и требовали удовлетворения. С первого вечера Наташа как будто забыла все то, что с ней было. Она с тех пор ни разу не пожаловалась на свое положение, ни одного слова не сказала о прошедшем и не боялась уже делать веселые планы на будущее. Она мало говорила о Пьере, но когда княжна Марья упоминала о нем, давно потухший блеск зажигался в ее глазах и губы морщились странной улыбкой.
Перемена, происшедшая в Наташе, сначала удивила княжну Марью; но когда она поняла ее значение, то перемена эта огорчила ее. «Неужели она так мало любила брата, что так скоро могла забыть его», – думала княжна Марья, когда она одна обдумывала происшедшую перемену. Но когда она была с Наташей, то не сердилась на нее и не упрекала ее. Проснувшаяся сила жизни, охватившая Наташу, была, очевидно, так неудержима, так неожиданна для нее самой, что княжна Марья в присутствии Наташи чувствовала, что она не имела права упрекать ее даже в душе своей.
Наташа с такой полнотой и искренностью вся отдалась новому чувству, что и не пыталась скрывать, что ей было теперь не горестно, а радостно и весело.
Когда, после ночного объяснения с Пьером, княжна Марья вернулась в свою комнату, Наташа встретила ее на пороге.
– Он сказал? Да? Он сказал? – повторила она. И радостное и вместе жалкое, просящее прощения за свою радость, выражение остановилось на лице Наташи.
– Я хотела слушать у двери; но я знала, что ты скажешь мне.
Как ни понятен, как ни трогателен был для княжны Марьи тот взгляд, которым смотрела на нее Наташа; как ни жалко ей было видеть ее волнение; но слова Наташи в первую минуту оскорбили княжну Марью. Она вспомнила о брате, о его любви.
