Участник:KibAndrey/Ортогонализация Грама-Шмидта: различия между версиями
Amelie (обсуждение | вклад) |
Amelie (обсуждение | вклад) |
||
| Строка 27: | Строка 27: | ||
== Математическое описание алгоритма == | == Математическое описание алгоритма == | ||
| + | Исходные данные: <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> | ||
| + | \begin{vmatrix} | ||
| + | (a_1,a_1) & \cdots & (a_1,a_n-1) &a_1 \\ | ||
| + | \cdots & \cdots & \cdots & \cdots \\ | ||
| + | (a_{i},a_1) & \cdots & (a_i,a_n-1) &a_i \\ | ||
| + | \cdots & \cdots & \cdots \\ | ||
| + | (a_{k},a_1) & \cdots & (a_k,a_n-1) &a_k | ||
| + | \end{vmatrix} | ||
| + | </math> | ||
| + | (В правой части этого равенства определитель следует формально разложить по последнему столбцу). | ||
| + | В этом случае знаменатель в формуле для вычисления проекции <math>|\mathbf{e_i}|=1</math> для <math>i=1,...,n-1</math>, что существенно упрощает вычисления алгоритма. | ||
| + | |||
| + | Произведение длин <math>| mathbf{b_1}|, | mathbf{b_2}|,… ,| mathbf{b_k}|</math> равно объему параллелепипеда, построенного на векторах системы <math>\left{a_i\right}</math>, как на ребрах | ||
| + | |||
| + | Иногда полученные векторы нормируются сразу после их нахождения и находится система ортонормированных векторов <math>\mathbf{e_1},\mathbf{e_2},...,\mathbf{e_n}</math>. | ||
| + | |||
| + | Явное выражение векторов <math>|\mathbf{b_i}|=1</math> для <math>i=1,...,k</math> через <math>\mathbf{a_1},\mathbf{a_2},...,\mathbf{a_n}</math> дает формула | ||
| + | |||
| + | |||
== Вычислительное ядро алгоритма == | == Вычислительное ядро алгоритма == | ||
Версия 01:09, 13 октября 2016
| Ортогонализация Грама-Шмидта | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]O\left(n^3\right)[/math] |
| Объём входных данных | [math][/math] |
| Объём выходных данных | [math][/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math][/math] |
| Ширина ярусно-параллельной формы | [math][/math] |
Основные авторы описания: А.В.Кибанов, Т.З.Аджиева,.
[math] \begin{vmatrix} (a_1,a_1) & \cdots & (a_1,a_n-1) &a_1 \\ \cdots & \cdots & \cdots & \cdots \\ (a_{i},a_1) & \cdots & (a_i,a_n-1) &a_i \\ \cdots & \cdots & \cdots \\ (a_{k},a_1) & \cdots & (a_k,a_n-1) &a_k \end{vmatrix} [/math]
Содержание
- 1 ЧАСТЬ. Свойства и структура алгоритма
- 2 ЧАСТЬ Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 ЧАСТЬ. Свойства и структура алгоритма
1.1 Общее описание алгоритма
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] \begin{vmatrix} (a_1,a_1) & \cdots & (a_1,a_n-1) &a_1 \\ \cdots & \cdots & \cdots & \cdots \\ (a_{i},a_1) & \cdots & (a_i,a_n-1) &a_i \\ \cdots & \cdots & \cdots \\ (a_{k},a_1) & \cdots & (a_k,a_n-1) &a_k \end{vmatrix} [/math] (В правой части этого равенства определитель следует формально разложить по последнему столбцу). В этом случае знаменатель в формуле для вычисления проекции [math]|\mathbf{e_i}|=1[/math] для [math]i=1,...,n-1[/math], что существенно упрощает вычисления алгоритма.
Произведение длин [math]| mathbf{b_1}|, | mathbf{b_2}|,… ,| mathbf{b_k}|[/math] равно объему параллелепипеда, построенного на векторах системы [math]\left{a_i\right}[/math], как на ребрах
Иногда полученные векторы нормируются сразу после их нахождения и находится система ортонормированных векторов [math]\mathbf{e_1},\mathbf{e_2},...,\mathbf{e_n}[/math].
Явное выражение векторов [math]|\mathbf{b_i}|=1[/math] для [math]i=1,...,k[/math] через [math]\mathbf{a_1},\mathbf{a_2},...,\mathbf{a_n}[/math] дает формула
