|
|
| (не показана 1 промежуточная версия этого же участника) |
| Строка 1: |
Строка 1: |
| − | ''' Ортогонализация Грамма-Шмидта '''
| |
| | | | |
| − | == Свойства и структура алгоритмов ==
| |
| − | === Общее описание алгоритма ===
| |
| − | Процесс Грама-Шмидта — это один из алгоритмов, в которых на основе счётного множества линейно независимых векторов <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> — ортонормализации Грама — Шмидта.
| |
| − |
| |
| − | === Вычислительное ядро алгоритма ===
| |
| − | === Макроструктура алгоритма ===
| |
| − | === Схема реализации последовательного алгоритма ===
| |
| − | === Последовательная сложность алгоритма ===
| |
| − | === Информационный граф ===
| |
| − | === Ресурс параллелизма алгоритма ===
| |
| − | === Входные и выходные данные алгоритма ===
| |
| − | === Свойства алгоритма ===
| |
| − |
| |
| − | == Программная реализация алгоритма ==
| |
| − | === Особенности реализации последовательного алгоритма ===
| |
| − | === Локальность данных и вычислений ===
| |
| − | === Возможные способы и особенности параллельной реализации алгоритма ===
| |
| − | === Масштабируемость алгоритма и его реализации ===
| |
| − | === Динамические характеристики и эффективность реализации алгоритма ===
| |
| − | === Выводы для классов архитектур ===
| |
| − | === Существующие реализации алгоритма ===
| |
| − |
| |
| − | == Литература ==
| |
