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

Версия 13:48, 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 Математическое описание алгоритма

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

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

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

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

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

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

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

Скалярное произведение векторов требует [math]n - 1[/math] сложение и [math]n[/math] произведений.
Нормализация вектора требует 1 скалярного произведения, 1 вычисления квадратного корня и [math]n[/math] делений, то есть:
1. [math]n-1[/math] ([math]+[/math]);
2. [math]n[/math] ([math]\times[/math]);
3. [math]n[/math] ([math]\div[/math]);
4. [math]1[/math] ([math]\sqrt{}[/math]).
Вычитание проекции вектора требует 1 скалярного произведения, [math]n[/math] сложений и [math]n[/math] умножений, то есть:
1. [math]2n-1[/math] ([math]+[/math]);
2. [math]2n[/math] ([math]\times[/math]).
Вычисление [math]i[/math]-го вектора требует [math]i-1[/math] вычитаний проекций с нормализацией, то есть:
1. [math](2n-1)(i-1)+n-1[/math] ([math]+[/math]);
2. [math]2n(i-1)+n[/math] ([math]\times[/math]);
3. [math]n[/math] ([math]\div[/math]);
4. [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].
1. [math](2n-1)(m-1)\frac{m}{2}+(n-1)m[/math] ([math]+[/math]);
2. [math]2n(m-1)\frac{m}{2}+nm[/math] ([math]\times[/math]);
3. [math]nm[/math] ([math]\div[/math]);
4. [math]m[/math] ([math]\sqrt{}[/math]).
В скалярном произведении [math]n[/math] делений могут быть рассмотрены как [math]n[/math] умножений:
1. [math](2n-1)(m-1)\frac{m}{2}+(n-1)m[/math] ([math]+[/math]);
2. [math]2n(m-1)\frac{m}{2}+2nm[/math] ([math]\times[/math]);
3. [math]m[/math] ([math]\div[/math]);
4. [math]m[/math] ([math]\sqrt{}[/math]).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 г.
↑ Пискова А.В., Менщиков А.А., Коробейников А.Г "Использование ортогонализации Грама-Шмидта в алгоритме приведения базиса решетки для протоколов безопасности"
↑ А.Е. Карелин, А.А. Светлаков "Использование ортогонализации Грама-Шмидта для повышения экономичности многоточечных алгоритмов рекуррентного оценивания параметров моделей объектов управления" ― Известия Томского политехнического университета [Известия ТПУ]. — 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] Пискова А.В., Менщиков А.А., Коробейников А.Г "Использование ортогонализации Грама-Шмидта в алгоритме приведения базиса решетки для протоколов безопасности"

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

[1]

[2]

[3]

[4]

[5]

[6]

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