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

Версия 20:20, 16 октября 2016

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

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

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

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

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

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

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

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

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

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

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

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

[math]\mathbf{b}_1 = \mathbf{a}_1[/math]

[math]\mathbf{b}_2 = \mathbf{a}_2 - \mathbf{proj}_{\mathbf{b}_1} \mathbf{a}_2 [/math]

[math]\mathbf{b}_3 = \mathbf{a}_3 - \mathbf{proj}_{\mathbf{b}_1} \mathbf{a}_3 - \mathbf{proj}_{\mathbf{b}_2} \mathbf{a}_3 [/math]

[math]\vdots[/math]

[math]\mathbf{b}_m = \mathbf{a}_m - \sum_{j=1}^{m-1} \mathbf{proj}_{\mathbf{b}_j} \mathbf{a}_m[/math]

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

[math]\beta_{1j} = \alpha_{1j}[/math]

[math]\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} [/math]

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

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

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

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

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

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

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

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

Таким образом, cложность алгоритма [math]O(nm^2)[/math].

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

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

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

Объем входных данных. [math]mn[/math]

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

Объем выходных данных. [math]mn[/math]

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

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

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

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

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

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

Данный алгоритм реализован во множестве библиотек и математических программных пакетах.

Библиотека Epicycle (C#).
Библиотека Spectral Python (SPy).
Библиотека vect (Haskell).

2.7.1 Пакет Mathematica

Приведем пример скрипта, предназначенного для пакета Mathematica, который проводит процесс ортогонализации Грама-Шмидта над векторами, заданными в фигурных скобках последней строки. Количество векторов и их координат могут быть произвольными. В данном случае для примера взяты векторы [math]\{-2,\;1,\;0\}[/math], [math]\{-2,\;0,\;1\}[/math], [math]\{-0{.}5,\;-1,\;1\}[/math].

Projection[v1_, v2_] := (v1.v2*v2)/v2.v2
MultipleProjection[v1_, vecs_] := Plus @@ (Projection[v1, #1] &) /@ vecs
GramSchmidt[mat_] := Fold[Join[#1, {#2 - MultipleProjection[#2, #1]}] &, {}, mat]
GramSchmidt[{{-2, 1, 0}, {-2, 0, 1}, {-0.5, -1, 1}}]

2.7.2 Пакет Maxima

Приведем пример скрипта, предназначенного для пакета Maxima, который проводит процесс ортогонализации Грама-Шмидта над векторами, заданными в фигурных скобках последней строки. Количество векторов и их координат могут быть произвольными. В данном случае для примера взяты векторы [math]\{-2,\;1,\;0\}[/math], [math]\{-2,\;0,\;1\}[/math], [math]\{-0{.}5,\;-1,\;1\}[/math].

load(eigen);
x: matrix ([-2,1,0],[-2,0,1],[-0.5,-1,1]);
y: gramschmidt(x);

2.7.3 Пакет MATLAB

Приведем пример скрипта, предназначенного для пакета MATLAB, который проводит процесс ортогонализации Грама-Шмидта над векторами, заданными в фигурных скобках последней строки. В данном пакете уже существует функция, которая осуществляет данный процесс. Столбцы входной матрицы предполагаются линейно-независимыми, количество векторов и их координат могут быть произвольными. Функция возращает матрицу X с ортонормированными столбцами и обратимую верхне-треугольную матрицу Y.

В данном случае для примера взяты векторы [math]\{-2,\;1,\;0\}[/math], [math]\{-2,\;0,\;1\}[/math], [math]\{-0{.}5,\;-1,\;1\}[/math].

[x y]=gschmidt([-2 1 0; -2 0 1; -0.5 -1 1])

3 Литература

↑ Канатников А.Н., Крищенко А.П. "Линейная алгебра." ― 3-е изд., стер. ― М.: Изд-во МГТУ им. Н.Э. Баумана, 2002
↑ O'Connor, John J.; Robertson, Edmund F., "Jørgen Pedersen Gram", MacTutor History of Mathematics archive, University of St Andrews.
↑ O'Connor, John J.; Robertson, Edmund F., "Erhard Schmidt", MacTutor History of Mathematics archive, University of St Andrews.
↑ Орешкин Б.Н., Бакулев П.А. "Быстрая процедура ортогонализации Грамма–Шмидта и ее применение для борьбы с помехами в адаптивной системе селекции движущихся целей" ― Радиотехника / №12 за 2007 г.
↑ Пискова А.В., Менщиков А.А., Коробейников А.Г. "Использование ортогонализации Грама-Шмидта в алгоритме приведения базиса решетки для протоколов безопасности" ― Вопросы кибербезопасности №1(14) 2016
↑ Карелин А.Е., Светлаков А.А. "Использование ортогонализации Грама-Шмидта для повышения экономичности многоточечных алгоритмов рекуррентного оценивания параметров моделей объектов управления" ― Известия Томского политехнического университета [Известия ТПУ]. — 2006. — Т. 309, № 8. — [С. 15-19].

[1] Канатников А.Н., Крищенко А.П. "Линейная алгебра." ― 3-е изд., стер. ― М.: Изд-во МГТУ им. Н.Э. Баумана, 2002

[2] O'Connor, John J.; Robertson, Edmund F., "Jørgen Pedersen Gram", MacTutor History of Mathematics archive, University of St Andrews.

[3] O'Connor, John J.; Robertson, Edmund F., "Erhard Schmidt", MacTutor History of Mathematics archive, University of St Andrews.

[4] Орешкин Б.Н., Бакулев П.А. "Быстрая процедура ортогонализации Грамма–Шмидта и ее применение для борьбы с помехами в адаптивной системе селекции движущихся целей" ― Радиотехника / №12 за 2007 г.

[5] Пискова А.В., Менщиков А.А., Коробейников А.Г. "Использование ортогонализации Грама-Шмидта в алгоритме приведения базиса решетки для протоколов безопасности" ― Вопросы кибербезопасности №1(14) 2016

[6] Карелин А.Е., Светлаков А.А. "Использование ортогонализации Грама-Шмидта для повышения экономичности многоточечных алгоритмов рекуррентного оценивания параметров моделей объектов управления" ― Известия Томского политехнического университета [Известия ТПУ]. — 2006. — Т. 309, № 8. — [С. 15-19].

[1]

[2]

[3]

[4]

[5]

[6]

@@ Строка 53: / Строка 53: @@
 *
 === Последовательная сложность алгоритма ===
-Рассмотрим <math>n</math> векторов длины <math>m</math>.
+Рассмотрим <math>m</math> векторов длины <math>n</math>.
-# Скалярное произведение векторов требует <math>n - 1</math> сложение и <math>n</math> произведений.
+# Скалярное произведение векторов требует <math>n-1</math> сложение и <math>n</math> произведений.
-# Нормализация вектора требует 1 скалярного произведения, 1 вычисления квадратного корня и <math>n</math> делений, то есть:
+# Вычитание проекции вектора требует <math>2</math> скалярных произведения, <math>1</math> деление, <math>n</math> умножений и <math>n</math> сложений, то есть:
-## <math>n-1</math> (<math>+</math>);
+## <math>3n-2</math> (<math>+</math>);
-## <math>n</math> (<math>\times</math>);
+## <math>3n</math> (<math>\times</math>);
-## <math>n</math> (<math>\div</math>);
+## <math>1</math> (<math>\div</math>).
-## <math>1</math> (<math>\sqrt{}</math>).
+# Вычисление <math>i</math>-го вектора требует <math>i-1</math> вычитаний проекций, то есть:
-# Вычитание проекции вектора требует 1 скалярного произведения, <math>n</math> сложений и <math>n</math> умножений, то есть:
+## <math>(3n-2)(i-1)</math> (<math>+</math>);
-## <math>2n-1</math> (<math>+</math>);
+## <math>3n(i-1)</math> (<math>\times</math>);
-## <math>2n</math> (<math>\times</math>).
+## <math>i-1</math> (<math>\div</math>).
-# Вычисление <math>i</math>-го вектора требует <math>i-1</math> вычитаний проекций с нормализацией, то есть:
+# Мы вычисляем вектора от <math>i=1</math> до <math>m</math>, поэтому <math>i-1</math> множителей выражаются ''треугольным числом'' <math>(m-1)\frac{m}{2}</math>.
-## <math>(2n-1)(i-1)+n-1</math> (<math>+</math>);
+## <math>(3n-2)(m-1)\frac{m}{2}</math> (<math>+</math>);
-## <math>2n(i-1)+n</math> (<math>\times</math>);
+## <math>3n(m-1)\frac{m}{2}</math> (<math>\times</math>);
-## <math>n</math> (<math>\div</math>);
+## <math>(m-1)\frac{m}{2}</math> (<math>\div</math>).
-## <math>1</math> (<math>\sqrt{}</math>).
-# Мы вычисляем вектора от <math>i=1</math> до <math>m</math>, поэтому <math>i-1</math> множителей выражаются ''треугольным числом'' <math>(m-1)\frac{m}{2}</math>, а элементы независимых <math>i</math> умножаются на <math>m</math>.
-## <math>(2n-1)(m-1)\frac{m}{2}+(n-1)m</math> (<math>+</math>);
-## <math>2n(m-1)\frac{m}{2}+nm</math> (<math>\times</math>);
-## <math>nm</math> (<math>\div</math>);
-## <math>m</math> (<math>\sqrt{}</math>).
-# В скалярном произведении <math>n</math> делений могут быть рассмотрены как <math>n</math> умножений:
-## <math>(2n-1)(m-1)\frac{m}{2}+(n-1)m</math> (<math>+</math>);
-## <math>2n(m-1)\frac{m}{2}+2nm</math> (<math>\times</math>);
-## <math>m</math> (<math>\div</math>);
-## <math>m</math> (<math>\sqrt{}</math>).
-Таким образом, требуется <math>2nm^2</math> операций. Сложность алгоритма <math>O(nm^2)</math>.
+Таким образом, cложность алгоритма <math>O(nm^2)</math>.
 === Информационный граф ===