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

Ортогонализация Грама-Шмидта
Последовательный алгоритм
Последовательная сложность	$O(nm^2)$
Объём входных данных	$nm$
Объём выходных данных	$nm$
Параллельный алгоритм
Высота ярусно-параллельной формы	$?$
Ширина ярусно-параллельной формы	$?$

Основные авторы описания: Белов Н. А., Богомолов Д. А..

1 Свойства и структура алгоритма

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

Ортогонализация ― алгоритм построения для данной линейно независимой системы векторов евклидова или эрмитова пространства V ортогональной системы ненулевых векторов, порождающих то же самое подпространство в V.

Ортогонализация Грама–Шмидта (процесс Грама–Шмидта) ― наиболее известный алгоритм ортогонализации. Назван в честь Йоргена Педерсена Грама и Эрхарда Шмидта, однако ранее уже появлялся в работах Лапласа и Коши. Является частным случаем разложения Ивасавы, так как может быть представлен как разложение невырожденной квадратной матрицы в произведение ортогональной (или унитарной матрицы в случае эрмитова пространства) и верхнетреугольной матрицы с положительными диагональными элементами.

Рассматриваемый алгоритм применяется для борьбы с помехами в адаптивной системе селекции движущихся целей, в протоколах безопасности, для повышения экономичности алгоритмов оценивания параметров моделей объектов управления и в других областях.

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

Входные данные. $m$ линейно независимых векторов $\mathbf{a}_1,...,\mathbf{a}_m$ c размерностью пространства $n$, записанных в матрице $A$ с элементами $\alpha_{ij}$.

Выходные данные. $m$ ортогональных векторов $\mathbf{b}_1,...,\mathbf{b}_m$ c размерностью пространства $n$, записанных в матрице $B$ с элементами $\beta_{ij}$.

Определим оператор проекции (проецирует вектор $\mathbf{a}$ коллинеарно вектору $\mathbf{b}$) $\mathbf{proj_b a = \frac{\left \langle a,b \right \rangle}{\left \langle b,b \right \rangle }b}$, где $\mathbf{\left \langle a,b \right \rangle}$ ― скалярное произведение векторов $\mathbf{a}$ и $\mathbf{b}$.

Тогда ортогональные векторы вычисляются следующим образом:

$\mathbf{b}_1 = \mathbf{a}_1$

$\mathbf{b}_2 = \mathbf{a}_2 - \mathbf{proj}_{\mathbf{b}_1} \mathbf{a}_2$

$\mathbf{b}_3 = \mathbf{a}_3 - \mathbf{proj}_{\mathbf{b}_1} \mathbf{a}_3 - \mathbf{proj}_{\mathbf{b}_2} \mathbf{a}_3$

$\vdots$

$\mathbf{b}_m = \mathbf{a}_m - \sum_{j=1}^{m-1} \mathbf{proj}_{\mathbf{b}_j} \mathbf{a}_m$

Или поэлементно:

$\beta_{1j} = \alpha_{1j}$

$\beta_{ij} = \alpha_{ij} - (\sum_{k=1}^{i-1} \mathbf{proj}_{\mathbf{b}_k} \mathbf{a}_i)_j = \alpha_{ij} - \sum_{k=1}^{i-1}\frac{\sum_{s=1}^{n}\alpha_{is}\beta_{ks}}{\sum_{s=1}^{n}\beta_{ks}\beta_{ks}}\beta_{kj}$

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

Основное время работы алгоритма приходится на вычисление сумм $\sum_{i=1}^{j-1} \mathbf{proj}_{\mathbf{b}_i} \mathbf{a}_k \forall j: j=\overline{1, m}$.

1.4 Макроструктура алгоритма

Из описания алгоритма в предыдущих разделов следует, что основную часть данного метода составляют операции вычисления проекций векторов, а также их сумм.

1.6 Последовательная сложность алгоритма

Рассмотрим $n$ векторов длины $m$.

1. Скалярное произведение векторов требует $n - 1$ сложение и $n$ произведений.
2. Нормализация вектора требует 1 скалярного произведения, 1 вычисления квадратного корня и $n$ делений, то есть:
   1. $n-1$ ($+$);
   2. $n$ ($\times$);
   3. $n$ ($\div$);
   4. $1$ ($\sqrt{}$).
3. Вычитание проекции вектора требует 1 скалярного произведения, $n$ сложений и $n$ умножений, то есть:
   1. $2n-1$ ($+$);
   2. $2n$ ($\times$).
4. Вычисление $i$-го вектора требует $i-1$ вычитаний проекций с нормализацией, то есть:
   1. $(2n-1)(i-1)+n-1$ ($+$);
   2. $2n(i-1)+n$ ($\times$);
   3. $n$ ($\div$);
   4. $1$ ($\sqrt{}$).
5. Мы вычисляем вектора от $i=1$ до $m$, поэтому $i-1$ множителей выражаются треугольным числом $(m-1)\frac{m}{2}$, а элементы независимых $i$ умножаются на $m$.
   1. $(2n-1)(m-1)\frac{m}{2}+(n-1)m$ ($+$);
   2. $2n(m-1)\frac{m}{2}+nm$ ($\times$);
   3. $nm$ ($\div$);
   4. $m$ ($\sqrt{}$).
6. В скалярном произведении $n$ делений могут быть рассмотрены как $n$ умножений:
   1. $(2n-1)(m-1)\frac{m}{2}+(n-1)m$ ($+$);
   2. $2n(m-1)\frac{m}{2}+2nm$ ($\times$);
   3. $m$ ($\div$);
   4. $m$ ($\sqrt{}$).

Таким образом, требуется $2nm^2$ операций. Сложность алгоритма $O(nm^2)$.

1.9 Входные и выходные данные алгоритма

Входные данные. Матрица $A$ с элементами $\alpha_{ij}$, где $i = \overline{1, n}$ (размерность пространства) и $j = \overline{1, m}$ (количество линейно-независимых векторов), при этом $n \leqslant m$.

Объем входных данных. $nm$

Выходные данные. Матрица $B$ с элементами $\beta_{ij}$, где $i = \overline{1, n}$ и $j = \overline{1, m}$, тогда $b_{i1}, \dots, b_{im}$ — система ортогональных векторов.

Объем выходных данных. $nm$

2 Программная реализация алгоритма

2.4 Масштабируемость алгоритма и его реализации

Срок сдачи продлен до 15 ноября.