Участник:KibAndrey/Ортогонализация Грама-Шмидта: различия между версиями
KibAndrey (обсуждение | вклад) |
Amelie (обсуждение | вклад) |
||
| Строка 91: | Строка 91: | ||
Как уже отмечено в [[#Вычислительное ядро алгоритма| описании вычислительного ядра алгоритма]], | Как уже отмечено в [[#Вычислительное ядро алгоритма| описании вычислительного ядра алгоритма]], | ||
основную часть метода составляют вычисления [[Скалярное_произведение_векторов,_вещественная_версия,_последовательно-параллельный_вариант| скалярных произведений]], | основную часть метода составляют вычисления [[Скалярное_произведение_векторов,_вещественная_версия,_последовательно-параллельный_вариант| скалярных произведений]], | ||
| − | как для | + | как для вычисления длины очередного вектора, так и для расчета проекций прочих векторов на новый вектор, |
а также умножения векторов на числа, используемые при корректировке | а также умножения векторов на числа, используемые при корректировке | ||
значений остальных векторов после вычисления очередного вектора, ортогонального предыдущим. | значений остальных векторов после вычисления очередного вектора, ортогонального предыдущим. | ||
Версия 01:07, 29 октября 2016
 | Эта работа ждет рассмотрения преподавателем Дата последней правки страницы: 29.10.2016 Авторы этой статьи считают, что задание выполнено. |
| Ортогонализация Грама-Шмидта | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]O\left(k^2n\right)[/math] |
| Объём входных данных | [math]kn[/math] |
| Объём выходных данных | [math]kn[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]O(k\sqrt{n})[/math] |
| Ширина ярусно-параллельной формы | [math]O(kn)[/math] |
Основные авторы описания: А.В.Кибанов, Т.З.Аджиева.
Все пункты данной статьи обсуждались и создавались совместно, доля ответственности равноправна.
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Процесс ортогонализации Грама–Шмидта[1] — алгоритм построения для данной линейно независимой системы векторов евклидова или эрмитова пространства [math]V[/math] ортогональной системы ненулевых векторов, при котором каждый вектор построенной системы линейно выражается через векторы данной системы. Процесс ортогонализации Грама-Шмидта может быть применен к любой, в том числе и линейно-зависимой системе элементов евклидова пространства. Если ортогонализуемая система линейно-зависима, то на некотором шаге (возможно несколько раз) мы получим нулевой элемент, после отбрасывания которого можно продолжить процесс ортогонализации[2], однако в данной статье этот случай мы не рассматриваем.
Исторически это первый алгоритм, описывающий процесс ортогонализации. Традиционно его связывают с именами Йоргена Педерсена Грама и Эрхарда Шмидта. Йорган Педерсен Грам[3] был датским актуарием, который в неявном виде представил суть процесса ортогонализации в 1883 году[4]. Нельзя не сказать о том, что метод ортогонализации в несколько ином, модифицированом виде, ранее использовал Пьер-Симон Лаплас при нахождении массы Сатурна и Юпитера из систем нормальных уравнений и расчете распределения ошибок при этих вычислениях[5]. Ясно, что Й. Грам не знал о том, что Лаплас ранее использовал этот метод. Эрхард Шмидт[3] был учеником великих математиков Германа Шварца и Давида Гильберта. Алгоритм ортогонализации был опубликован Э. Шмидтом в 1907 году в его исследовании интегральных уравнений[6], которое в свою очередь дало основание для развития теории гильбертовых пространств. Шмидт использовал процесс ортогонализации применительно к геометрии гильбертова пространства решений интегральных уравнений отмечал, что процесс ортогонализации принципиально такой же, какой прежде использовал Й. Грам. В отечественной литературе иногда этот процесс называют ортогонализацией Сонина–Шмидта[7][8]. Это название связано с тем, что разработанный Сониным[9] метод ортогонализации системы функций для частного случая по существу не отличается от метода ортогонализации системы функций, предложенного ранее Шмидтом[6].
Классический процесс ортогонализации Грама–Шмидта применяется в таких совменных областях, как анализ изображений[10], цифровая обработка сигналов[11], нейронные сети[12].
1.2 Математическое описание алгоритма
Bходные данные: [math]k[/math] линейно независимых векторов [math]\mathbf{a_1},\mathbf{a_2},\ldots,\mathbf{a_k}[/math] длины [math]n[/math] [math]\left(\alpha_{ij}\right.[/math], [math]j=1,2, \ldots,n[/math], — координаты вектора [math]\left.\mathbf{a_i}\right)[/math] .
Вычисляемые данные:
[math]k[/math] ортогональных векторов [math]\mathbf{b_1},\mathbf{b_2},...,\mathbf{b_k}[/math] длины [math]n[/math], причем [math]\mathbf{b_1}=\mathbf{a_1}[/math], либо
[math]k[/math] ортонормированных векторов [math]\mathbf{q_1},\mathbf{q_2},\ldots,\mathbf{q_k}[/math] длины [math]n[/math], причем [math]\mathbf{q_i}=\frac{\mathbf{b_i}}{|\mathbf{b_i}|}[/math], [math]i=1,2, \ldots,k[/math].
Формулы процесса ортогонализации:
- [math] \begin{align} \mathbf{b_{1}} & =\mathbf{a_{1}}, \\ \mathbf{b_{2}}& =\mathbf{a_{2}}-\mathbf{b_{1}} proj_{\mathbf{b_1}}\mathbf{a_{2}},\\ & ...\\ \mathbf{b_{i}} & =\mathbf{ a_{i}}-\sum\limits_{j=1}^{i-1}\mathbf{b_{i}} proj_{\mathbf{b_j}}\mathbf{a_{i}}.\\ & ...\\ \mathbf{b_{k}} & =\mathbf{ a_{k}}-\sum\limits_{j=1}^{k-1}\mathbf{b_{k}} proj_{\mathbf{b_j}}\mathbf{a_{k}}.\\ \end{align} [/math]
Здесь [math]proj_{\mathbf{b_j}}\mathbf{a_{i}}[/math], для [math]j=1,...,k-1[/math] — это число, равное по величине проекции вектора [math]\mathbf{a_{j}}[/math] на ось, проходящую через вектор [math]\mathbf{b_j}[/math].
Формула для ее вычисления, полученная из определения скалярного произведения: [math]proj_{\mathbf{b_j}}\mathbf{a_{i}}=\dfrac{(ai,bj)}{\mathbf{\left \|b_j\right \|}}[/math], для [math]j=1,...,i-1[/math]
Произведение длин [math]\mathbf{|b_1|},\mathbf{|b_2|},\ldots ,\mathbf{|b_k|}[/math] равно объему параллелепипеда, построенного на векторах системы [math]\left\{\mathbf{a_i}\right\}[/math], [math]i=1,2,\ldots ,k[/math], как на ребрах.
Явное выражение векторов [math]\mathbf{b_i}[/math] для [math]i=1,...,k[/math] через [math]\mathbf{a_1},\mathbf{a_2},...,\mathbf{a_k}[/math] дает формула
[math] \mathbf{b_i}= \begin{vmatrix} (a_1,a_1) & \cdots & (a_1,a_i-1) &a_1 \\ (a_{2},a_1) & \cdots & (a_2,a_i-1) &a_2 \\ \cdots & \cdots & \cdots& \cdots \\ (a_{i},a_1) & \cdots & (a_i,a_i-1) &a_i \\ \end{vmatrix} [/math]. (В правой части этого равенства определитель следует формально разложить по последнему столбцу).
Иногда полученные векторы нормируются сразу после их нахождения и находится система ортонормированных векторов [math]\mathbf{q_1},\mathbf{q_2},\ldots,\mathbf{q_k}[/math]. В этом случае знаменатель в формуле для вычисления проекции [math]|\mathbf{q_i}|=1[/math] для [math]i=1,...,k-1[/math], что существенно упрощает вычисления алгоритма. В настоящей статье применяя процесс ортогонализации к системе линейно независимых векторов, мы так и будем поступать.
Если в описанном алгоритме в формулах для вычисления векторов [math]\mathbf{b_i}\,[/math], для [math]i=1,...,k[/math] процесса ортогонализации заменить [math]proj_{\mathbf{b_j}}\mathbf{a_{i}}[/math], для [math]j=1,...,i-1[/math] на [math]proj_{\mathbf{b_j}}\mathbf{b_{i}}[/math], для [math]j=1,...,i-1[/math],алгоритм, полученный таким образом называется модифицированный алгоритм Грама–Шмидта.
Чаще всего, процесс Грама–Шмидта приводит к значительному нарушению ортогональности. Что касается модифицированного процесса Грама–Шмидта, он проявляет себя достаточно неусточиво, хоть и чуть менее, чем классический процесс.
1.3 Вычислительное ядро алгоритма
Вычислительное ядро алгоритма состоит из вычисления:
- [math]\dfrac{k(k+1)}{2}[/math] скалярных произведений векторов,
включая нахождения скалярных произведений одинаковых векторов дальнейшего нахождения их длин;
- [math]\dfrac{(k-1)k}{2}[/math] умножений векторов на число после вычисления нового базисного вектора на итерации.
1.4 Макроструктура алгоритма
Как уже отмечено в описании вычислительного ядра алгоритма, основную часть метода составляют вычисления скалярных произведений, как для вычисления длины очередного вектора, так и для расчета проекций прочих векторов на новый вектор, а также умножения векторов на числа, используемые при корректировке значений остальных векторов после вычисления очередного вектора, ортогонального предыдущим.
1.5 Схема реализации последовательного алгоритма
Входные данные: [math]k[/math] линейно независимых векторов [math]\mathbf{a_1},\mathbf{a_2},\ldots,\mathbf{a_k}[/math] длины [math]n[/math] [math]\left(\alpha_{ij}\right.[/math], где [math]j=1,2, \ldots,n[/math] — координаты вектора [math]\mathbf{a_i}[/math], для [math]\left.i=1,2, \ldots,k\right)[/math].
Вычисляемые данные:
[math]k[/math] ортогональных векторов [math]\mathbf{b_1},\mathbf{b_2},...,\mathbf{b_k}[/math] длины [math]n[/math] [math]\left(\beta_{ij}\right.[/math], где [math]j=1,2, \ldots,n[/math] — координаты вектора [math]\mathbf{b_i}[/math], для [math]\left.i=1,2, \ldots,k\right)[/math], причем [math]\mathbf{b_1}=\mathbf{a_1}[/math], либо
[math]k[/math] ортонормированных векторов [math]\mathbf{q_1},\mathbf{q_2},\ldots,\mathbf{q_k}[/math] длины [math]n[/math] ([math]\gamma_{ij}[/math], [math]j=1,2, \ldots,n[/math] — координаты вектора [math]\mathbf{q_i}[/math], для [math]\left.i=1,2, \ldots,k\right)[/math], причем [math]\mathbf{q_1}=\frac{\mathbf{b_i}}{|\mathbf{b_i}|}[/math], для [math]i=1,2, \ldots,k[/math].
Последовательность исполнения метода:
1. [math]len(a_1)=\sqrt{\alpha_{11}^2+\alpha_{12}^2+\ldots+\alpha_{1n}^2}[/math].
2. При [math]i[/math] от [math]1[/math] до [math]n[/math]:
- [math]\gamma_{1j}= \frac{\alpha_{1j}}{len(a_1)}[/math].
3. При [math]i[/math] от [math]2[/math] до [math]k[/math]:
- при [math]j[/math] от [math]1[/math] до [math]n[/math]:
- [math]\beta_{ij}=\alpha_{ij}-\sum\limits_{k=1}^{j-1}\left(\sum\limits_{m=1}^n \alpha_{im}\gamma_{km}\right)\gamma_{kj} [/math]
- [math]len(b_i)=\sqrt{\beta_{i1}^2+\beta_{i2}^2+\ldots+\beta_{in}^2}[/math]
- при [math]j[/math] от [math]1[/math] до [math]n[/math]:
- [math]\gamma_{ij}= \frac{\beta_{ij}}{len(b_{i})}[/math].
- при [math]j[/math] от [math]1[/math] до [math]n[/math]:
1.6 Последовательная сложность алгоритма
Для ортогонализации [math]n[/math] линейно независимых векторов длины [math]n[/math] в последовательном варианте с помощью классического метода ортогонализации Грама-Шмидта потребуется:
- [math]k[/math] вычислений квадратного корня
- [math]\frac{k(k-1)(n-1)}{2}[/math] сложений,
- [math]\frac{k(k-1)(n-1)}{2}[/math] вычитаний,
- [math]k^2 n[/math] умножений,
- [math]k[/math] делений.
Умножения, сложения и вычитания составляют основную часть алгоритма.
При классификации по последовательной сложности, таким образом, метода ортогонализации Грама-Шмидта с кубической сложностью.
1.7 Информационный граф
Представим граф алгоритма с помощью текстового описания, а также с помощью изображения.
Все вершины графа можно разбить на пять групп, каждой из которых соответствует вид исполняемой операции. Каждая вершина расположена в точках с целочисленными координатами, в пространствах с числом измерений от [math]1[/math] до [math]3[/math]. Дадим описание каждой из групп.
Первая группа — вершины, которым соответствует операция скалярного умножения вектора на себя. На графе они располагаются в одномерной области. [math]i[/math] изменяется от [math]1[/math] до [math]k[/math].
Значениями аргументов для этих функций являются:
- при [math]i = 1[/math] — входные данные [math]\{a_{1p}\}, p = 1..n[/math];
- при [math]i \gt 1[/math] — результат выполнения функции в вершине пятой группы с координатами [math]\{i-1,1,p\}, p = 1..n[/math].
Результат этих операций является промежуточным данным алгоритма.
Вторая группа — вершины, которым соответствует операция SQRT извлечения квадратного корня. Они расположены в одномерной области, [math]i [/math] изменяется от [math]1[/math] до [math]k[/math].
Значением аргумента для этих функций является результат выполнения функции в вершине первой группы, с координатой [math]i[/math].
Результат является промежуточным данным алгоритма.
Третья группа – вершины, которым соответствует операция деления. Располагаются в двумерной области, [math]i[/math] изменяется от [math]1[/math] до [math]k[/math], [math]p[/math] изменяется от [math]1[/math] до [math]n[/math].
Значениями аргументов для этих функций являются:
- делимое:
- при [math]i = 1[/math] — входные данные [math]a_{1p}[/math];
- при [math]i \gt 1[/math] — результат выполнения функции в вершине пятой группы с координатами [math]i-1,1,p[/math];
- делитель - результат выполнения функции в вершине второй группы с координатой [math]i[/math].
Результат является выходным данным алгоритма [math]q_{ip}[/math].
Четвертая группа — вершины, которым соответствует операция скалярного умножения векторов [math]\mathbf{a}\cdot\mathbf{b}[/math]. Располагаются в двумерной области, [math]i[/math] изменяется от [math]1[/math] до [math]k-1[/math], [math]j[/math] изменяется от [math]1[/math] до [math]k-i[/math].
Значениями аргументов для этих функций являются:
- [math]\mathbf{a}[/math] — входные данные [math]\{a_{1+j,p}\},p = 1..n [/math];
- [math]\mathbf{b}[/math] — результат выполнения функции в вершине третьей группы с координатой [math]\{i,p\}, p = 1..n [/math].
Результат является промежуточным данным алгоритма.
Пятая группа – вершины которые соответствуют операции [math]a - b c[/math]. Располагаются в трехмерной области, [math]i[/math] изменяется от [math]1[/math] до [math]k-1[/math], [math]j[/math] изменяется от [math]1[/math] до [math]k-i[/math], [math]p[/math] изменяется от [math]1[/math] до [math]n[/math].
Значениями аргументов для этих функций являются:
- [math]a[/math]:
- при [math]i = 1[/math] — входные данные [math]a_{1+j,p}[/math];
- при [math]i \gt 1[/math] — результат выполнения функции в вершине пятой группы с координатами [math]i-1,j+1,p[/math];
- [math]b[/math] — результат выполнения функции в вершине четвертой группы, с координатами [math]i,j[/math];
- [math]c[/math] — результат выполнения функции в вершине третьей группы с координатой [math]i,p[/math].
Результат является промежуточным данным алгоритма.
Описанный граф для случая [math]k = 3[/math], [math]n = 3[/math] изображен на рисунке. Каждая группа вершин отличается цветом и буквенным обозначением. "S" — первая группа, "SQ" — вторая группа, "Div" — третья группа, "Dot" — четвертая группа, "f" — пятая группа. Квадратные метки "In" и "out" обозначают передачу входных и выходных данных соответственно.
1.8 Ресурс параллелизма алгоритма
Для построения ортонормированного базиса методом Грама–Шмидта необходимо выполнить следующие ярусы операций:
- [math]k[/math] ярусов вычисления скалярных произведений векторов на самих себя (по одной операций на каждом, сложность операции по высоте и по ширине ЯПФ - корень квадратный);
- [math]k[/math] ярусов вычисления квадратного корня (по одной операции на каждом);
- [math]k[/math] ярусов деления (по [math]n[/math] операций на каждом);
- [math]k-1[/math] ярус вычисления скалярных произведений пары векторов (от [math]1[/math] до [math](k-1)[/math] операций на каждом,сложность операции по высоте и по ширине ЯПФ - корень квадратный);
- [math]k-1[/math] ярус умножения/вычитания чисел (от [math]n[/math] до [math](k-1)n[/math] операций на каждом).
В этом случае сложность алгоритма при классификации по высоте ЯПФ — [math]O(k\sqrt{n})[/math], при классификации по ширине ЯПФ — [math]O(kn)[/math].
1.9 Входные и выходные данные алгоритма
Входные данные: матрица [math]A[/math] с элементами [math]\alpha_{ij}[/math], где [math]i[/math] принимает значения [math]1,\ldots,k[/math], [math]j[/math] принимает значения [math] 1,\ldots,n[/math]. Здесь [math]k\leqslant n[/math]. По строкам этой матрицы записаны [math]k[/math] линейно-независимых векторов некоторого пространства размерности [math]n[/math].
Объем входных данных: [math]kn[/math].
Выходные данные: матрица [math]Q[/math] с элементами [math]\gamma_{ij}[/math]. Строки этой матрицы также задают [math]k[/math] векторов единичной длины размерности [math]n[/math], причем всякое скалярное произведение двух различных векторов этой системы равно [math]0[/math].
Объем выходных данных: [math]kn[/math].
Замечание: Алгоритм может работать с вырожденной матрицей, он выдаёт нулевую строку на шаге [math]j[/math], если строка [math]j[/math] матрицы [math]A[/math] является линейной комбинацией предыдущих строк. В этом случае для корректного продолжения работы алгоритма необходима дополнительная проверка на равенство строки нулю и пропуск соответствующих строк. Количество построенных векторов будет равняться размерности пространства, порождаемого строками матрицы.
1.10 Свойства алгоритма
Отношение последовательной и параллельной сложности алгоритма в случае неограниченных ресурсов равно [math]\dfrac{k^2n}{k\sqrt{n}}=k\sqrt{n}[/math]. Вычислительная мощность алгоритма линейная.
Алгоритм почти полностью детерминирован — единственность результата выполнения гарантирована, однако возможно накопление ошибок округления.
Алгоритм является численно неустойчивым — ошибки округления могут привести к неортогональности полученных векторов.
Большинство дуг информационного графа являются локальными. Исключение составляют дуги исходящие из операций деления и извлечения корня — для первой группы количество дуг пропорционально квадрату количества векторов, а для второй — пропорционально размерности пространства, в котором заданы эти вектора. Возникающие при это длинные дуги могут быть заменены несколькими короткими пересылками между соседями.
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Локальность данных и вычислений
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
Для классического метода ортогонализации Грама–Шмидта существуют реализации в математических программных пакетах, таких как
Также метод реализован в библиотеке SpectralPython для языка Python. Для устранения проблемы ошибок численных округлений иногда используется повторное применение метода к уже построенному ортогональному базису.
Поскольку метод ортогонализации Грама–Шмидта гарантирует получение [math]j[/math] ортогональных векторов к концу шага [math]j[/math], а не в самом конце работы алгоритма, используется в итерационных методах, таких как метод Арнольди. Для поддержки работы этого метода реализация ортогонализации Грама–Шмидта включена в библиотеку ARPACK.
3 Литература
- ↑ Математическая энциклопедия / Гл. ред. И. М. Виноградов — М: Советская энциклопедия — Т.4 Ок–Сло, 1984. — 215 с.
- ↑ А. Е. Умнов. Аналитическая геометрия и линейная алгебра — 3-е издание, исправленное и дополненное — М.: МФТИ — 2011 — 544 c.
- ↑ 3,0 3,1 Meyer C. D. Matrix analysis and applied linear algebra. — Siam, 2000. — Т.2.
- ↑ Gram J. P. Ueber die Entwickelung reeller Functionen in Reihen mittelst der Methode der kleinsten Quadrate. — Journal für die reine und angewandte Mathematik. — 1883. — Т. 94. — pp. 41–73.
- ↑ Marquis de Laplace P. S. Théorie analytique des probabilités. — V. Courcier, 1820.
- ↑ 6,0 6,1 Erchard Shmidt. Mathematische Annalen Zur Theorie der linearen und nichtlinearen Integralgleichungen, 1. Teil: Entwicklung willkürlicher
Funktionen nach Systemen vorgeschriebener. — Mathematische Annalen. — 1908. — V. 65. — №. 3. — pp. 370-399. Ошибка цитирования Неверный тег
<ref>: название «Shmidt» определено несколько раз для различного содержимого - ↑ Краснов М.Л. Интегральные уравнения. Введение в теорию. — М.: Наука, 1975. — 302 с.
- ↑ Марченко В.А. Введение в теорию обратных задач спектрального анализа. — Харьков: Акта, 2005. — 143 с.
- ↑ О некоторых неравенствах, относящихся к определенным интегралам. Записки Академии наук по физико-математическому отделению. Серия 8. Т. 6 № 6. — C. 1–53.
- ↑ Nussbaum S., Menz G. Object-based image analysis and treaty verification: new approaches in remote sensing-applied to nuclear facilities in Iran. — Springer Science & Business Media, 2008.
- ↑ Gopi E. S. Algorithm collections for digital signal processing applications using matlab. — Springer Science & Business Media, 2007.
- ↑ Rajasekaran S., Suresh D., Pai G. A. V. Application of sequential learning neural networks to civil engineering modeling problems. — Engineering with Computers. — 2002. — Т. 18. – №. 2. — pp. 138–147.
