|
|
| Строка 3: |
Строка 3: |
| == Свойства и структура алгоритмов == | | == Свойства и структура алгоритмов == |
| === Общее описание алгоритма === | | === Общее описание алгоритма === |
| Процесс Грама-Шмидта — это один из алгоритмов, в которых на основе счётного множества линейно независимых векторов <math>{\displaystyle \mathbf {a} _{1},\;\ldots ,\;\mathbf {a} _{N}}</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} _{j}} </math> или <math>{\displaystyle \mathbf {e} _{j}} </math> может быть выражен линейной комбинацией векторов <math>{\displaystyle \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}_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>\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> — ортонормализации Грама — Шмидта.
| |
|
| |
| === Вычислительное ядро алгоритма === | | === Вычислительное ядро алгоритма === |
| === Макроструктура алгоритма === | | === Макроструктура алгоритма === |