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

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

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим [math]\displaystyle{ n }[/math] векторов длины [math]\displaystyle{ m }[/math].

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

Таким образом, требуется [math]\displaystyle{ 2nm^2 }[/math] операций. Сложность алгоритма [math]\displaystyle{ O(nm^2) }[/math].

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

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

Объем входных данных. [math]\displaystyle{ nm }[/math]

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

Объем выходных данных. [math]\displaystyle{ nm }[/math]

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

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

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