Участник:DVIN

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

Свойства и структура алгоритмов

Общее описание алгоритма

Процесс Грама-Шмидта — это один из алгоритмов, в которых на основе счётного множества линейно независимых векторов [math]\displaystyle{ {\displaystyle \mathbf {a} _{1},\;\ldots ,\;\mathbf {a} _{N}} }[/math] строится множество ортогональных векторов [math]\displaystyle{ {\displaystyle \mathbf {b} _{1},\;\ldots ,\;\mathbf {b} _{N}} }[/math] или ортонормированных векторов [math]\displaystyle{ {\displaystyle \mathbf {e} _{1},\;\ldots ,\;\mathbf {e} _{N}} }[/math], причём так, что каждый вектор [math]\displaystyle{ {\displaystyle \mathbf {b} _{j}} }[/math] или [math]\displaystyle{ {\displaystyle \mathbf {e} _{j}} }[/math] может быть выражен линейной комбинацией векторов [math]\displaystyle{ {\displaystyle \mathbf {a} _{1},\;\ldots ,\;\mathbf {a} _{j}} }[/math].

Математическое описание алгоритма

Пусть имеются линейно независимые векторы [math]\displaystyle{ \mathbf{a}_1,\;\ldots,\;\mathbf{a}_N }[/math].

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

[math]\displaystyle{ \mathbf{proj}_{\mathbf{b}}\,\mathbf{a} = {\langle \mathbf{a}, \mathbf{b} \rangle \over \langle \mathbf{b}, \mathbf{b}\rangle} \mathbf{b} , }[/math]

где [math]\displaystyle{ \langle \mathbf{a}, \mathbf{b} \rangle }[/math] — скалярное произведение векторов [math]\displaystyle{ \mathbf{a} }[/math] и [math]\displaystyle{ \mathbf{b} }[/math]. Этот оператор проецирует вектор [math]\displaystyle{ \mathbf{a} }[/math] коллинеарно вектору [math]\displaystyle{ \mathbf{b} }[/math].

Ортогональность векторов [math]\displaystyle{ \mathbf{a} }[/math] и [math]\displaystyle{ \mathbf{b} }[/math] достигается на шаге (2).

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

[math]\displaystyle{ \begin{array}{lclr} \mathbf{b}_1 & = & \mathbf{a}_1 & (1) \\ \mathbf{b}_2 & = & \mathbf{a}_2-\mathbf{proj}_{\mathbf{b}_1}\,\mathbf{a}_1 & (2) \\ \mathbf{b}_3 & = & \mathbf{a}_3-\mathbf{proj}_{\mathbf{b}_1}\,\mathbf{a}_1-\mathbf{proj}_{\mathbf{b}_2}\,\mathbf{a}_2 & (3) \\ \mathbf{b}_4 & = & \mathbf{a}_4-\mathbf{proj}_{\mathbf{b}_1}\,\mathbf{a}_1-\mathbf{proj}_{\mathbf{b}_2}\,\mathbf{a}_2-\mathbf{proj}_{\mathbf{b}_3}\,\mathbf{a}_3 & (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]\displaystyle{ \mathbf{b}_j \;(j = 1 \ldots N) }[/math] может быть получен нормированный вектор: [math]\displaystyle{ \mathbf{e}_j = {\mathbf{b}_j\over \| \mathbf{b}_j \|} }[/math] (у нормированного вектора направление будет таким же, как у исходного, а длина — единичной).

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

[math]\displaystyle{ \mathbf{b}_1,\;\ldots,\;\mathbf{b}_N }[/math] — система ортогональных векторов либо

[math]\displaystyle{ \mathbf{e}_1,\;\ldots,\;\mathbf{e}_N }[/math] — система ортонормированных векторов.

Вычисление [math]\displaystyle{ \mathbf{b}_1,\;\ldots,\;\mathbf{b}_N }[/math] носит название ортогонализации Грама — Шмидта, а [math]\displaystyle{ \mathbf{e}_1,\;\ldots,\;\mathbf{e}_N }[/math] — ортонормализации Грама — Шмидта.