Участник:KibAndrey/Ортогонализация Грама-Шмидта

Ортогонализация Грама-Шмидта
Последовательный алгоритм
Последовательная сложность	[math]O\left(n^3\right)[/math]
Объём входных данных	[math][/math]
Объём выходных данных	[math][/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math][/math]
Ширина ярусно-параллельной формы	[math][/math]

Основные авторы описания: А.В.Кибанов, Т.З.Аджиева

1 ЧАСТЬ. Свойства и структура алгоритма

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

Ортогонализации Грама-Шмидта – алгоритм построения для данной линейно независимой системы векторов евклидова пространства ортогональной системы ненулевых векторов, которые имеют ту же самую линейную оболочку, при котором каждый вектор построенной системы линейно выражается через векторы данной системы. Исторически это первый алгоритм, описывающий процесс ортогониализации. Традиционно его связывают с именами Йоргена Педерсена Грама и Эрхарда Шмидта. Эрхард Шмидт был учеником великих математиков Германа Шварца и Давида Гильберта. Алгоритм ортогонализации был опубликован Э. Шмидтом в 1907 году в его исследовании интегральных уравнений, которое в свою очередь дало привело к развитию теории гильбертовых пространств. Шмидт использовал процесс ортогонализации применительно к геометрии гильбертова пространства решений интегральных уравнений отмечал, что процесс ортогонализации принципиально такой же, какой прежде использовал Й. Грам.

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

Исходные данные: [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уществует также модифицированная версия алгоритма, однако в данном описании разобран только классический алгоритм ортогонализации Грама-Шмидта.

1.3 Вычислительное ядро алгоритма

Анализ математических формул процесса ортогонализации Грама-Шмидта показывает, что алгоритм имеет три вычислительных ядра:

• вычисления скалярного произведения (к этой операции сводится вычисление длины вектора)
• умножения вектора на число
• сложения векторов.

Эти операции выполняются за время порядка [math]O\left(n\right)[/math]

1.5 Схема реализации последовательного алгоритма

[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]