Участник:BDA/Ортогонализация Грама-Шмидта
| Ортогонализация Грама-Шмидта | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ O(nm^2) }[/math] |
| Объём входных данных | [math]\displaystyle{ nm }[/math] |
| Объём выходных данных | [math]\displaystyle{ nm }[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]\displaystyle{ ? }[/math] |
| Ширина ярусно-параллельной формы | [math]\displaystyle{ ? }[/math] |
Основные авторы описания: Белов Н. А., Богомолов Д. А..
Свойства и структура алгоритма
Общее описание алгоритма
Ортогонализация ― алгоритм построения для данной линейно независимой системы векторов евклидова или эрмитова пространства V ортогональной системы ненулевых векторов, порождающих то же самое подпространство в V.
Ортогонализация Грама–Шмидта[1] (процесс Грама–Шмидта) ― наиболее известный алгоритм ортогонализации. Назван в честь Йоргена Педерсена Грама[2] и Эрхарда Шмидта[3], однако ранее уже появлялся в работах Лапласа и Коши. Является частным случаем разложения Ивасавы, так как может быть представлен как разложение невырожденной квадратной матрицы в произведение ортогональной (или унитарной матрицы в случае эрмитова пространства) и верхнетреугольной матрицы с положительными диагональными элементами.
Рассматриваемый алгоритм применяется для борьбы с помехами в адаптивной системе селекции движущихся целей[4], в протоколах безопасности[5], для повышения экономичности алгоритмов оценивания параметров моделей объектов управления[6] и в других областях.
Математическое описание алгоритма
Входные данные. [math]\displaystyle{ m }[/math] линейно независимых векторов [math]\displaystyle{ \mathbf{a}_1,...,\mathbf{a}_m }[/math] c размерностью пространства [math]\displaystyle{ n }[/math], записанных в матрице [math]\displaystyle{ A }[/math] с элементами [math]\displaystyle{ \alpha_{ij} }[/math].
Выходные данные. [math]\displaystyle{ m }[/math] ортогональных векторов [math]\displaystyle{ \mathbf{b}_1,...,\mathbf{b}_m }[/math] c размерностью пространства [math]\displaystyle{ n }[/math], записанных в матрице [math]\displaystyle{ B }[/math] с элементами [math]\displaystyle{ \beta_{ij} }[/math].
Определим оператор проекции (проецирует вектор [math]\displaystyle{ \mathbf{a} }[/math] коллинеарно вектору [math]\displaystyle{ \mathbf{b} }[/math]) [math]\displaystyle{ \mathbf{proj_b a = \frac{\left \langle a,b \right \rangle}{\left \langle b,b \right \rangle }b} }[/math], где [math]\displaystyle{ \mathbf{\left \langle a,b \right \rangle} }[/math] ― скалярное произведение векторов [math]\displaystyle{ \mathbf{a} }[/math] и [math]\displaystyle{ \mathbf{b} }[/math].
Тогда ортогональные векторы вычисляются следующим образом:
[math]\displaystyle{ \mathbf{b}_1 = \mathbf{a}_1 }[/math]
[math]\displaystyle{ \mathbf{b}_2 = \mathbf{a}_2 - \mathbf{proj}_{\mathbf{b}_1} \mathbf{a}_2 }[/math]
[math]\displaystyle{ \mathbf{b}_3 = \mathbf{a}_3 - \mathbf{proj}_{\mathbf{b}_1} \mathbf{a}_3 - \mathbf{proj}_{\mathbf{b}_2} \mathbf{a}_3 }[/math]
[math]\displaystyle{ \vdots }[/math]
[math]\displaystyle{ \mathbf{b}_m = \mathbf{a}_m - \sum_{j=1}^{m-1} \mathbf{proj}_{\mathbf{b}_j} \mathbf{a}_m }[/math]
Или поэлементно:
[math]\displaystyle{ \beta_{1j} = \alpha_{1j} }[/math]
[math]\displaystyle{ \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]
Вычислительное ядро алгоритма
Основное время работы алгоритма приходится на вычисление сумм [math]\displaystyle{ \sum_{i=1}^{j-1} \mathbf{proj}_{\mathbf{b}_i} \mathbf{a}_k \forall j: j=\overline{1, m} }[/math].
Макроструктура алгоритма
Из описания алгоритма в предыдущих разделов следует, что основную часть данного метода составляют операции вычисления проекций векторов, а также их сумм.
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
Рассмотрим [math]\displaystyle{ n }[/math] векторов длины [math]\displaystyle{ m }[/math].
- Скалярное произведение векторов требует [math]\displaystyle{ n - 1 }[/math] сложение и [math]\displaystyle{ n }[/math] произведений.
- Нормализация вектора требует 1 скалярного произведения, 1 вычисления квадратного корня и [math]\displaystyle{ n }[/math] делений, то есть:
- [math]\displaystyle{ n-1 }[/math] ([math]\displaystyle{ + }[/math]);
- [math]\displaystyle{ n }[/math] ([math]\displaystyle{ \times }[/math]);
- [math]\displaystyle{ n }[/math] ([math]\displaystyle{ \div }[/math]);
- [math]\displaystyle{ 1 }[/math] ([math]\displaystyle{ \sqrt{} }[/math]).
- Вычитание проекции вектора требует 1 скалярного произведения, [math]\displaystyle{ n }[/math] сложений и [math]\displaystyle{ n }[/math] умножений, то есть:
- [math]\displaystyle{ 2n-1 }[/math] ([math]\displaystyle{ + }[/math]);
- [math]\displaystyle{ 2n }[/math] ([math]\displaystyle{ \times }[/math]).
- Вычисление [math]\displaystyle{ i }[/math]-го вектора требует [math]\displaystyle{ i-1 }[/math] вычитаний проекций с нормализацией, то есть:
- [math]\displaystyle{ (2n-1)(i-1)+n-1 }[/math] ([math]\displaystyle{ + }[/math]);
- [math]\displaystyle{ 2n(i-1)+n }[/math] ([math]\displaystyle{ \times }[/math]);
- [math]\displaystyle{ n }[/math] ([math]\displaystyle{ \div }[/math]);
- [math]\displaystyle{ 1 }[/math] ([math]\displaystyle{ \sqrt{} }[/math]).
- Мы вычисляем вектора от [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].
- [math]\displaystyle{ (2n-1)(m-1)\frac{m}{2}+(n-1)m }[/math] ([math]\displaystyle{ + }[/math]);
- [math]\displaystyle{ 2n(m-1)\frac{m}{2}+nm }[/math] ([math]\displaystyle{ \times }[/math]);
- [math]\displaystyle{ nm }[/math] ([math]\displaystyle{ \div }[/math]);
- [math]\displaystyle{ m }[/math] ([math]\displaystyle{ \sqrt{} }[/math]).
- В скалярном произведении [math]\displaystyle{ n }[/math] делений могут быть рассмотрены как [math]\displaystyle{ n }[/math] умножений:
- [math]\displaystyle{ (2n-1)(m-1)\frac{m}{2}+(n-1)m }[/math] ([math]\displaystyle{ + }[/math]);
- [math]\displaystyle{ 2n(m-1)\frac{m}{2}+2nm }[/math] ([math]\displaystyle{ \times }[/math]);
- [math]\displaystyle{ m }[/math] ([math]\displaystyle{ \div }[/math]);
- [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, m} }[/math] (количество линейно независимых векторов) и [math]\displaystyle{ j = \overline{1, n} }[/math] (размерность пространства), при этом [math]\displaystyle{ m \leqslant n }[/math].
Объем входных данных. [math]\displaystyle{ mn }[/math]
Выходные данные. Матрица [math]\displaystyle{ B }[/math] с элементами [math]\displaystyle{ \beta_{ij} }[/math], где [math]\displaystyle{ i = \overline{1, m} }[/math] и [math]\displaystyle{ j = \overline{1, n} }[/math], тогда [math]\displaystyle{ b_{1}, \dots, b_{m} }[/math] — система ортогональных векторов.
Объем выходных данных. [math]\displaystyle{ mn }[/math]
Свойства алгоритма
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
Срок сдачи продлен до 15 ноября.
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
Данный алгоритм реализован во множестве библиотек и математических программных пакетах.
- Библиотека Epicycle (C#).
- Библиотека Spectral Python (SPy).
- Библиотека vect (Haskell).
Пакет Mathematica
Приведем пример скрипта, предназначенного для пакета Mathematica, который проводит процесс ортогонализации Грама-Шмидта над векторами, заданными в фигурных скобках последней строки. Количество векторов и их координат могут быть произвольными. В данном случае для примера взяты векторы [math]\displaystyle{ \{-2,\;1,\;0\} }[/math], [math]\displaystyle{ \{-2,\;0,\;1\} }[/math], [math]\displaystyle{ \{-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}}]
Пакет Maxima
Приведем пример скрипта, предназначенного для пакета Maxima, который проводит процесс ортогонализации Грама-Шмидта над векторами, заданными в фигурных скобках последней строки. Количество векторов и их координат могут быть произвольными. В данном случае для примера взяты векторы [math]\displaystyle{ \{-2,\;1,\;0\} }[/math], [math]\displaystyle{ \{-2,\;0,\;1\} }[/math], [math]\displaystyle{ \{-0{.}5,\;-1,\;1\} }[/math].
load(eigen);
x: matrix ([-2,1,0],[-2,0,1],[-0.5,-1,1]);
y: gramschmidt(x);
Пакет MATLAB
Приведем пример скрипта, предназначенного для пакета MATLAB, который проводит процесс ортогонализации Грама-Шмидта над векторами, заданными в фигурных скобках последней строки. В данном пакете уже существует функция, которая осуществляет данный процесс. Столбцы входной матрицы предполагаются линейно-независимыми, количество векторов и их координат могут быть произвольными. Функция возращает матрицу X с ортонормированными столбцами и обратимую верхне-треугольную матрицу Y.
В данном случае для примера взяты векторы [math]\displaystyle{ \{-2,\;1,\;0\} }[/math], [math]\displaystyle{ \{-2,\;0,\;1\} }[/math], [math]\displaystyle{ \{-0{.}5,\;-1,\;1\} }[/math].
[x y]=gschmidt([-2 1 0; -2 0 1; -0.5 -1 1])
Литература
- ↑ Канатников А.Н., Крищенко А.П. "Линейная алгебра." ― 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].