Участник:Valeriya Shervarly/Ортогонализация Грама-Шмидта: различия между версиями
| Строка 5: | Строка 5: | ||
== Общее описание алгоритма == | == Общее описание алгоритма == | ||
| − | Процесс Грама-Шмидта - это алгоритм построения множества ортогональных (или ортонормированных) линейно-независимых векторов по исходному множеству векторов, при этом линейные оболочки получившегося и исходного множеств векторов совпадают. | + | Процесс Грама-Шмидта - это алгоритм построения множества ортогональных (или ортонормированных) линейно-независимых векторов по исходному множеству векторов, при этом линейные оболочки получившегося и исходного множеств векторов совпадают. Иными словами, построение ортогонального базиса из векторов, образующих произвольный базис. |
| − | Процесс Грама | + | Процесс Грама-Шмидта также можно рассматривать как разложение невырожденной квадратной матрицы в произведение унитарной (ортогональной) и верхнетреугольной матрицы с положительными диагональными элементами (QR-разложение). |
| − | Задача построения или вычисления ортогонального базиса некоторого линейного подпространства или пространства часто является подзадачей более крупных широко используемых задач, так что ортогонализация Грама-Шмидта является важным алгоритмом в линейной алгебре. | + | Задача построения или вычисления ортогонального базиса некоторого линейного подпространства или пространства часто является подзадачей более крупных широко используемых задач, так что ортогонализация Грама-Шмидта является важным и часто используемым алгоритмом в линейной алгебре. |
== Математическое описание алгоритма == | == Математическое описание алгоритма == | ||
| + | |||
| + | Процесс ортогонализации описывается следующей последовательностью формул: | ||
:: <math> | :: <math> | ||
| Строка 24: | Строка 26: | ||
где: | где: | ||
| − | <math>a_1, ..., a_n </math> - множество | + | <math>a_1, ..., a_n </math> - исходное множество линейно-независимых векторов |
<math>b_1, ..., b_n</math> - множество искомых векторов | <math>b_1, ..., b_n</math> - множество искомых векторов | ||
| Строка 38: | Строка 40: | ||
== Макроструктура алгоритма == | == Макроструктура алгоритма == | ||
| − | На уровне макроструктуры будем рассматривать <math>\frac{<a, b>}{\|b\|^2} * b</math> как отдельную макрооперацию <math>proj_{b}a</math> | + | На уровне макроструктуры будем рассматривать <math>\frac{<a, b>}{\|b\|^2} * b</math> как отдельную макрооперацию <math>proj_{b}a</math>. |
== Схема реализации последовательного алгоритма == | == Схема реализации последовательного алгоритма == | ||
| − | input: a | + | input: a = (a[1], ..., a[n]) |
| − | output: b | + | output: b = (b[1], ..., b[n]) |
| − | for j = | + | b[1] = a[1] |
| + | for j = 2,...,n | ||
b[j] = a[j] | b[j] = a[j] | ||
for k = 1,...,j-1 | for k = 1,...,j-1 | ||
| Строка 76: | Строка 79: | ||
== Свойства алгоритма == | == Свойства алгоритма == | ||
| − | + | Классический алгоритм (CGS) является численно-неустойчивым из-за частой потери ортогональности, вызванной ошибками округления в процессе вычислений. | |
| − | Существует | + | |
| + | Существует модификации алгоритма Грама-Шмидта, которые являются более устойчивами, например, модифицированный алгоритм Грама-Шмидта (MGS), блочные и итеративные варианты CGS и MGS. MGS численно эквивалентен методу Хаусхолдера QR-разложения, примененного к матрице, полученной из исходной путем добавления к ней сверху прямоугольной матрицы из нулевых элементов. | ||
| + | |||
Алгоритм является детерминированным. | Алгоритм является детерминированным. | ||
Версия 06:40, 19 октября 2016
Содержание
- 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 Общее описание алгоритма
Процесс Грама-Шмидта - это алгоритм построения множества ортогональных (или ортонормированных) линейно-независимых векторов по исходному множеству векторов, при этом линейные оболочки получившегося и исходного множеств векторов совпадают. Иными словами, построение ортогонального базиса из векторов, образующих произвольный базис.
Процесс Грама-Шмидта также можно рассматривать как разложение невырожденной квадратной матрицы в произведение унитарной (ортогональной) и верхнетреугольной матрицы с положительными диагональными элементами (QR-разложение).
Задача построения или вычисления ортогонального базиса некоторого линейного подпространства или пространства часто является подзадачей более крупных широко используемых задач, так что ортогонализация Грама-Шмидта является важным и часто используемым алгоритмом в линейной алгебре.
1.2 Математическое описание алгоритма
Процесс ортогонализации описывается следующей последовательностью формул:
- [math] \begin{align} b_1 & = a_1 \\ b_2 & = a_2 - \frac{\lt a_2, b_1\gt }{\|b_1\|^2} * b_1 \\ b_3 & = a_3 - \frac{\lt a_3, b_1\gt }{\|b_1\|^2} * b_1 - \frac{\lt a_3, b_2\gt }{\|b_2\|^2} * b_2 \\ ... \\ b_n & = a_n - \frac{\lt a_n, b_1\gt }{\|b_1\|^2} * b_1 - ... - \frac{\lt a_n, b_{n-1}\gt }{\|b_{n-1}\|^2} * b_{n-1} \\ \end{align} [/math]
где: [math]a_1, ..., a_n [/math] - исходное множество линейно-независимых векторов
[math]b_1, ..., b_n[/math] - множество искомых векторов
[math]\lt a,b\gt [/math] - скалярное произведение векторов
[math]\|b\| = \sqrt{\lt b,b\gt }[/math]
1.3 Вычислительное ядро алгоритма
Вычислительным ядром алгоритма является весь алгоритм (за исключением инициализации первого вектора ортогонального базиса [math]b_1[/math]).
1.4 Макроструктура алгоритма
На уровне макроструктуры будем рассматривать [math]\frac{\lt a, b\gt }{\|b\|^2} * b[/math] как отдельную макрооперацию [math]proj_{b}a[/math].
1.5 Схема реализации последовательного алгоритма
input: a = (a[1], ..., a[n]) output: b = (b[1], ..., b[n])
b[1] = a[1]
for j = 2,...,n
b[j] = a[j]
for k = 1,...,j-1
b[j] = b[j] - <a[j],b[k]>/<b[k],b[k]>*b[k]
1.6 Последовательная сложность алгоритма
Сложность алгоритма - [math]O(n^3)[/math]
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
Возможно параллельное вычисление всех [math]proj_{b_j}a_i, i=1,...n[/math] для уже найденных [math]b_j[/math] вместо вычисления каждого вектора [math]b_j[/math] по очереди. Таким образом после каждой итерации будет получен один посчитанный вектор, необходимый для расчетов на следующей итерации. Однако степень распараллеливания будет падать на каждой итерации, что вместе с необходимостью синхронизации и многочисленными обменами информации может снизить эффективность распараллеливания.
1.9 Входные и выходные данные алгоритма
Входные данные: N линейно независимых векторов (процесс Грама — Шмидта может применяться также к бесконечной последовательности линейно независимых векторов, а также к линейно зависимым векторам. В последнем случае вектор [math]a_j[/math] получится нулевым, если он зависит от векторов [math]a_1, ..., a_{j-1}[/math], и алгоритм должен сразу отбрасывать нулевые векторы)
Выходные данные: N ортогональных векторов, линейная оболочка которых совпадает с линейной оболочкой входного множества векторов.
1.10 Свойства алгоритма
Классический алгоритм (CGS) является численно-неустойчивым из-за частой потери ортогональности, вызванной ошибками округления в процессе вычислений.
Существует модификации алгоритма Грама-Шмидта, которые являются более устойчивами, например, модифицированный алгоритм Грама-Шмидта (MGS), блочные и итеративные варианты CGS и MGS. MGS численно эквивалентен методу Хаусхолдера QR-разложения, примененного к матрице, полученной из исходной путем добавления к ней сверху прямоугольной матрицы из нулевых элементов.
Алгоритм является детерминированным.
2 ЧАСТЬ. Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Локальность данных и вычислений
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
- реализация для системы компьютерной алгебры maxima (GNU GPL)
load(eigen); x: matrix ([-2,1,0],[-2,0,1],[-0.5,-1,1]); y: gramschmidt(x);
- пример реализации для системы компьютерной алгебры mathematica (проприетарное программное обеспечение)
Projection[v1_, v2_] := (v1.v2*v2)/v2.v2
MultipleProjection[v1_, vecs_] := Plus @@ (Projection[v1, #1] &) /@ vecs
GramSchmidt[mat_] := Fold[Join[#1, {Normalize[#2 - MultipleProjection[#2, #1]]}] &, {}, mat]
GramSchmidt[{{-2, 1, 0}, {-2, 0, 1}, {-0.5, -1, 1}}]
- библиотека fplll (функция GSO) (GNU LESSER GENERAL PUBLIC LICENSE)
- Math.NET Numerics (функция MathNet.Numerics.LinearAlgebra.Factorization.GramSchmidt<T>)
- библиотека PETSc (KSPGMRESClassicalGramSchmidtOrthogonalization)
