|
|
| Строка 14: |
Строка 14: |
|
| |
|
| == Общее описание алгоритма == | | == Общее описание алгоритма == |
| Ортогонализации Грама-Шмидта – алгоритм построения для данной линейно независимой системы векторов евклидова пространства ортогональной системы ненулевых векторов, которые имеют ту же самую линейную оболочку, при котором каждый вектор построенной системы линейно выражается через векторы данной системы. Исторически это первый алгоритм, описывающий процесс ортогониализации. Традиционно его связывают с именами Йоргена Педерсена Грама и Эрхарда Шмидта. Эрхард Шмидт<ref>Meyer C. D. Matrix analysis and applied linear algebra. – Siam, 2000. – Т. 2.</ref> был учеником великих математиков Германа Шварца и Давида Гильберта. Алгоритм ортогонализации был опубликован Э. Шмидтом в 1907 году <ref>Erchard Shmidt. Mathematische Annalen Zur Theorie der linearen und nichtlinearen Integralgleichungen, 1. Teil: Entwicklung willkürlicher
| |
| Funktionen nach Systemen vorgeschriebener. – Mathematische Annalen, 63 (1907), pp. 433–476.</ref> в его исследовании интегральных уравнений, которое в свою очередь дало привело к развитию теории гильбертовых пространств. Шмидт использовал процесс ортогонализации применительно к геометрии гильбертова пространства решений интегральных уравнений отмечал, что процесс ортогонализации принципиально такой же, какой прежде использовал Й. Грам.
| |
|
| |
|
| == Математическое описание алгоритма == | | == Математическое описание алгоритма == |
|
| |
| Исходные данные: <math>k</math> векторов <math>\mathbf{a_1},\mathbf{a_2},...,\mathbf{a_n}</math> длины <math>n</math> <math>\left(\alpha_{ij}\right.</math>, <math>j=1,2,...,n</math>, — координаты вектора <math>\left.\mathbf{a_i}\right)</math> .
| |
|
| |
| Вычисляемые данные:
| |
|
| |
| <math>k</math> ортогональных векторов <math>\mathbf{b_1},\mathbf{b_2},...,\mathbf{b_n}</math> длины <math>n</math>, причем <math>\mathbf{b_1}=\mathbf{a_1}</math> либо
| |
|
| |
| <math>k</math> ортонормированных векторов <math>\mathbf{e_1},\mathbf{e_2},...,\mathbf{e_n}</math> длины <math>n</math>, причем <math>\mathbf{e_1}=\frac{\mathbf{a_1}}{|\mathbf{a_1}|}</math>
| |
|
| |
| Формулы процесса ортогонализации:
| |
| :<math>
| |
| \begin{align}
| |
| \mathbf{b_{1}} & =\mathbf{a_{1}}, \\
| |
| \mathbf{b_{2}}& =\mathbf{a_{2}}-proj_{\mathbf{b_1}}\mathbf{a_{1}}, \\
| |
| & ...\\
| |
| \mathbf{b_{{i} }} & = \mathbf{a_{i}}-\sum\limits_{j=1}^{i-1} proj_{\mathbf{b_j}}\mathbf{a_{j}},\\
| |
| & ...\\
| |
| \mathbf{b_{n}} & =\mathbf{ a_{n}}-\sum\limits_{j=1}^{n-1} proj_{\mathbf{b_j}}\mathbf{a_{j}},\\
| |
| \end{align}
| |
| </math>
| |
|
| |
| Здесь <math>proj_{\mathbf{b_j}}\mathbf{a_{j}}</math>, для <math>j=1,...,n-1</math> — проекция вектора <math>\mathbf{a_{j}}</math> на направление вектора <math>\mathbf{b_{j}}</math>.
| |
| Это число, равное по величине проекции вектора <math>\mathbf{a_{j}}</math> на ось, проходящую через вектор <math>\mathbf{b_j}</math>.
| |
|
| |
| Формула для ее вычисления, полученная из определения скалярного произведения:
| |
| :<math> proj_{\mathbf{b_j}}\mathbf{a_{j}}=\frac{(\mathbf{aj},\mathbf{bj})}{|\mathbf{b_j}|}. </math>
| |
| Иногда полученные векторы нормируются сразу после их нахождения и находится система ртонормированных векторов <math>\mathbf{e_1},\mathbf{e_2},...,\mathbf{e_n}</math>.
| |
|
| |
| В этом случае знаменатель в формуле для вычисления проекции <math>|\mathbf{e_i}|=1</math> для <math>i=1,...,n-1</math>, что существенно упрощает вычисления алгоритма.
| |
|
| |
| Cуществует также модифицированная версия алгоритма, однако в данном описании разобран только классический алгоритм ортогонализации Грама-Шмидта.
| |
|
| |
|
| == Вычислительное ядро алгоритма == | | == Вычислительное ядро алгоритма == |
|
| |
| Анализ математических формул процесса ортогонализации Грама-Шмидта показывает, что алгоритм имеет три вычислительных ядра:
| |
|
| |
| * вычисления скалярного произведения (к этой операции сводится вычисление длины вектора)
| |
| * умножения вектора на число
| |
| * сложения векторов.
| |
|
| |
| Эти операции выполняются за время порядка <math>O\left(n\right)</math>
| |
|
| |
| == Макроструктура алгоритма ==
| |
|
| |
| == Схема реализации последовательного алгоритма ==
| |
| :<math>
| |
| \begin{align}
| |
| a_{1} & =b_{1}, \\
| |
| \beta_{ij} & = \frac{(a_{i},b_j)}{(b_j,b_j)}=-\frac{(a_i,b_j)}{|b_j|^2}, \quad i \in [2, n], \quad j \in [1, n] ,\\
| |
|
| |
| \end{align}
| |
| </math>
| |
|
| |
|
| |
|
| == Последовательная сложность алгоритма == | | == Последовательная сложность алгоритма == |
| Ортогонализация Грама-Шмидта
|
| Последовательный алгоритм
|
| Последовательная сложность
|
[math]\displaystyle{ O\left(n^3\right) }[/math]
|
| Объём входных данных
|
[math]\displaystyle{ }[/math]
|
| Объём выходных данных
|
[math]\displaystyle{ }[/math]
|
| Параллельный алгоритм
|
| Высота ярусно-параллельной формы
|
[math]\displaystyle{ }[/math]
|
| Ширина ярусно-параллельной формы
|
[math]\displaystyle{ }[/math]
|
Основные авторы описания: А.В.Кибанов, Т.З.Аджиева
ЧАСТЬ. Свойства и структура алгоритма
Общее описание алгоритма
Математическое описание алгоритма
Вычислительное ядро алгоритма
Последовательная сложность алгоритма
Информационный граф
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
Свойства алгоритма
ЧАСТЬ Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
Литература
