Уровень алгоритма

Классический метод ортогонализации: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
м
Строка 9: Строка 9:
  
 
== Свойства и структура алгоритмов ==
 
== Свойства и структура алгоритмов ==
 +
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
Создатели алгоритма Эрхард Шмидт и Йорген Педерсен Грам.
 
 
'''Эрхард Шмидт''' (14 января 1876 — 6 декабря 1959) — немецкий математик, с 1917 года профессор Берлинского университета. В 1946—58 первый директор Института математики АН ГДР. Основные труды по теории функций, интегральным уравнениям, функциональному анализу. Определил и изучил геометрически гильбертово пространство, используя аналогии с геометрией Евклида. Занимался квадратичными формами. Известен оператор Гильберта-Шмидта и процесс Грама ― Шмидта.
 
 
'''Йорген Педерсен Грам''' (27 июня 1850 - 29 апреля 1916) датский математик, родился в герцогстве Шлезвиг, Дания и умер в Копенгагене, Дания. Основные его работы "On series expansions determined by the methods of least squares", "Investigations of the number of primes less than a given number". Математический метод, который носит его имя, процесс Грама-Шмидта, впервые был опубликован в 1883. Теорема Грама и Определитель Грама также назван в его честь.
 
  
Процесс Грама-Шмидта — это один из алгоритмов, в которых на основе множества линейно независимых векторов <math>{\displaystyle \mathbf {a} _{1},\;\ldots ,\;\mathbf {a} _{N}}</math> строится множество ортогональных векторов <math>{\displaystyle \mathbf {b}_{1},\;\ldots ,\;\mathbf {b} _{N}} </math> или ортонормированных векторов <math>{\displaystyle \mathbf {e} _{1},\;\ldots ,\;\mathbf {e}_{N}} </math>, причём так, что каждый вектор <math>{\displaystyle \mathbf {b} _{j}} </math> или <math>{\displaystyle \mathbf {e} _{j}}</math> может быть выражен линейной комбинацией векторов <math>{\displaystyle \mathbf {a} _{1},\;\ldots ,\; \mathbf {a} _{j}}</math>.
+
Процесс ортогонализации Грама-Шмидта — это один из алгоритмов, в которых на основе множества линейно независимых векторов <math>{\displaystyle \mathbf {a} _{1},\;\ldots ,\;\mathbf {a} _{N}}</math> строится множество ортогональных <math>{\displaystyle \mathbf {b}_{1},\;\ldots ,\;\mathbf {b} _{N}} </math> или ортонормированных векторов <math>{\displaystyle \mathbf {e} _{1},\;\ldots ,\;\mathbf {e}_{N}} </math>, причём так, что каждый вектор <math>{\displaystyle \mathbf {b} _{j}} </math> или <math>{\displaystyle \mathbf {e} _{j}}</math> может быть выражен линейной комбинацией векторов <math>{\displaystyle \mathbf {a} _{1},\;\ldots ,\; \mathbf {a} _{j}}</math>.
  
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===
==== Классический процесс Грама — Шмидта ====
 
  
===== Алгоритм =====
 
 
Пусть имеются линейно независимые векторы <math>\mathbf{a}_1,\;\ldots,\;\mathbf{a}_N</math>.
 
Пусть имеются линейно независимые векторы <math>\mathbf{a}_1,\;\ldots,\;\mathbf{a}_N</math>.
  
Определим оператор проекции следующим образом: <math>\mathbf{proj}_{\mathbf{b}}\,\mathbf{a} = {\langle \mathbf{a}, \mathbf{b} \rangle \over \langle \mathbf{b}, \mathbf{b}\rangle} \mathbf{b} ,</math>  
+
Если определить оператор проекции следующим образом: <math>\mathbf{proj}_{\mathbf{b}}\,\mathbf{a} = {\langle \mathbf{a}, \mathbf{b} \rangle \over \langle \mathbf{b}, \mathbf{b}\rangle} \mathbf{b} ,</math>  
 
 
где <math>\langle \mathbf{a}, \mathbf{b} \rangle</math> — скалярное произведение векторов <math>\mathbf{a}</math> и <math>\mathbf{b}</math>.
 
 
 
Скалярное произведение для двух векторов  <math>\mathbf{ a= [a_1, a_2, ...,a_k]}</math> и <math>\mathbf{ b= [b_1, b_2, ..., b_k]}</math>  в '''''k'''''-мерном действительном пространстве определяется как:
 
:<math>\langle \mathbf{a}, \mathbf{b} \rangle=\sum_{i=1}^k a_ib_i=a_1b_1+a_2b_2+\cdots+ a_kb_k</math>.
 
 
 
Этот оператор проецирует вектор <math>\mathbf{a}</math> коллинеарно вектору <math>\mathbf{b}</math>.
 
  
Ортогональность векторов <math>\mathbf{a}</math> и <math>\mathbf{b}</math> достигается на шаге (2).
+
где <math>\langle \mathbf{a}, \mathbf{b} \rangle</math> — скалярное произведение векторов <math>\mathbf{a}</math> и <math>\mathbf{b}</math>,
  
Классический процесс Грама — Шмидта выполняется следующим образом:
+
то классический процесс Грама — Шмидта выполняется следующим образом:
  
 
: <math>
 
: <math>
Строка 48: Строка 35:
  
  
На основе каждого вектора <math>\mathbf{b}_j \;(j = 1 \ldots N)</math> может быть получен нормированный вектор: <math>\mathbf{e}_j = {\mathbf{b}_j\over \| \mathbf{b}_j \|}</math> (у нормированного вектора направление будет таким же, как у исходного, а длина — единичной). Причем берется норма согласованная со скалярным произведением <math>\| x \| = \sqrt{\langle x, x \rangle}</math>
+
На основе каждого вектора <math>\mathbf{b}_j \;(j = 1 \ldots N)</math> может быть получен нормированный вектор: <math>\mathbf{e}_j = {\mathbf{b}_j\over \|\| \mathbf{b}_j \|\|_2}</math> (у нормированного вектора направление будет таким же, как у исходного, а длина — единичной).
  
 
Результаты процесса Грама — Шмидта:
 
Результаты процесса Грама — Шмидта:
Строка 56: Строка 43:
 
<math>\mathbf{e}_1,\;\ldots,\;\mathbf{e}_N</math> — система ортонормированных векторов.
 
<math>\mathbf{e}_1,\;\ldots,\;\mathbf{e}_N</math> — система ортонормированных векторов.
  
Вычисление <math>\mathbf{b}_1,\;\ldots,\;\mathbf{b}_N</math> носит название ортогонализации Грама — Шмидта, а <math>\mathbf{e}_1,\;\ldots,\;\mathbf{e}_N</math> — ортонормализации Грама — Шмидта.
 
 
===== Доказательство =====
 
Докажем ортогональность векторов <math>\mathbf{b}_1,\;\ldots,\;\mathbf{b}_N</math>.
 
 
Для этого вычислим скалярное произведение <math>\langle \mathbf{b}_1, \mathbf{b}_2 \rangle</math>, подставив в него формулу (2). Мы получим ноль. Равенство нулю скалярного произведения векторов означает, что эти векторы ортогональны. Затем вычислим скалярное произведение <math>\langle \mathbf{b}_1, \mathbf{b}_3 \rangle</math>, используя результат для <math>\langle \mathbf{b}_1, \mathbf{b}_2 \rangle</math> и формулу (3). Мы снова получим ноль, то есть векторы <math>\mathbf{b}_1</math> и <math>\mathbf{b}_3</math> ортогональны. Общее доказательство выполняется методом математической индукции.
 
 
===== Геометрическая интерпретация — вариант 1 =====
 
[[Файл:Gram-Schmidt-step2.svg|right|frame|Рис. 1. Второй шаг процесса Грама — Шмидта]]
 
Рассмотрим формулу (2) — второй шаг алгоритма.
 
Её геометрическое представление изображено на рис. 1:
 
 
1 — получение проекции вектора <math>\mathbf{a}_2</math> на <math>\mathbf{b}_1</math>;
 
 
2 — вычисление <math>\mathbf{a}_2-\mathbf{proj}_{\mathbf{b}_1}\mathbf{a}_2</math>, то есть [[перпендикуляр]]а, которым выполняется проецирование конца <math>\mathbf{a}_2</math> на <math>\mathbf{b}_1</math>.
 
 
Этот перпендикуляр — вычисляемый в формуле (2) вектор <math>\mathbf{b}_2</math>;
 
 
3 — перемещение полученного на шаге 2 вектора <math>\mathbf{b}_2</math> в начало координат. Это перемещение сделано на рисунке лишь для наглядности. Оно не является математическим действием и поэтому не отражается в формуле (2).
 
 
На рисунке видно, что вектор <math>\mathbf{b}_2</math> ортогонален вектору <math>\mathbf{b}_1</math>, так как <math>\mathbf{b}_2</math> является перпендикуляром, по которому <math>\mathbf{a}_2</math> проецируется на <math>\mathbf{b}_1</math>.
 
 
Рассмотрим формулу (3) — третий шаг алгоритма — в следующем варианте:
 
: <math>
 
\begin{array}{lcr}
 
\mathbf{b}_3 = \mathbf{a}_3-(\mathbf{proj}_{\mathbf{b}_1}\mathbf{a}_3+\mathbf{proj}_{\mathbf{b}_2}\mathbf{a}_3) & & (6) \\
 
\end{array}
 
</math>
 
 
Её геометрическое представление изображено на рис. 2:
 
[[Файл:Gram-schmidt-step3base1.png|center|frame|Рис. 2. Третий шаг процесса Грама — Шмидта]]
 
 
1 — получение проекции вектора <math>\mathbf{a}_3</math> на <math>\mathbf{b}_1</math>;
 
 
2 — получение проекции вектора <math>\mathbf{a}_3</math> на <math>\mathbf{b}_2</math>;
 
 
3 — вычисление суммы <math>\mathbf{proj}_{\mathbf{b}_1}\mathbf{a}_3 + \mathbf{proj}_{\mathbf{b}_2}\mathbf{a}_3</math>, то есть проекции вектора <math>\mathbf{a}_3</math> на плоскость, образуемую векторами <math>\mathbf{b}_1</math> и <math>\mathbf{b}_2</math>. Эта плоскость закрашена на рисунке серым цветом;
 
 
4 — вычисление <math>\mathbf{a}_3-(\mathbf{proj}_{\mathbf{b}_1}\mathbf{a}_3 + \mathbf{proj}_{\mathbf{b}_2}\mathbf{a}_3)</math>, то есть перпендикуляра, которым выполняется проецирование конца <math>\mathbf{a}_3</math> на плоскость, образуемую векторами <math>\mathbf{b}_1</math> и <math>\mathbf{b}_2</math>. Этот перпендикуляр — вычисляемый в формуле (6) вектор <math>\mathbf{b}_3</math>;
 
 
5 — перемещение полученного <math>\mathbf{b}_3</math> в начало координат. Это перемещение сделано на рисунке лишь для наглядности. Оно не является математическим действием и поэтому не отражается в формуле (6).
 
 
На рисунке видно, что вектор <math>\mathbf{b}_3</math> ортогонален векторам <math>\mathbf{b}_1</math> и <math>\mathbf{b}_2</math>, так как <math>\mathbf{b}_3</math> является перпендикуляром, по которому <math>\mathbf{a}_3</math> проецируется на плоскость, образуемую векторами <math>\mathbf{b}_1</math> и <math>\mathbf{b}_2</math>.
 
 
Таким образом, в процессе Грама — Шмидта для вычисления <math>\mathbf{b}_j</math> выполняется проецирование <math>\mathbf{a}_j</math> ортогонально на [[гиперплоскость]]?, формируемую векторами <math>\mathbf{b}_1,\;\ldots,\;\mathbf{b}_{j-1}</math>. Вектор <math>\mathbf{b}_j</math> затем вычисляется как разность между <math>\mathbf{a}_j</math> и его проекцией. То есть <math>\mathbf{b}_j</math> — это перпендикуляр? от конца <math>\mathbf{a}_j</math> к гиперплоскости?, формируемой векторами <math>\mathbf{b}_1,\;\ldots,\;\mathbf{b}_{j-1}</math>. Поэтому <math>\mathbf{b}_j</math> ортогонален векторам, образующим эту гиперплоскость?.
 
 
===== Численная неустойчивость =====
 
При вычислении на ЭВМ по формулам (1) — (5) векторы <math>\mathbf{b}_1,\;\ldots,\;\mathbf{b}_{N-1}</math> часто не точно ортогональны из-за [[Ошибка квантования|ошибок округления]]. Из-за потери ортогональности в процессе вычислений классический процесс Грама — Шмидта называют [[Численная устойчивость|численно неустойчивым]].
 
 
==== Модифицированный процесс Грама — Шмидта ====
 
Процесс Грама — Шмидта может быть сделан более вычислительно устойчивым путём небольшой модификации. Вместо вычисления <math>\mathbf{b}_j</math> как: <math> \mathbf{b}_j = \mathbf{a}_j - \mathbf{proj}_{\mathbf{b}_1}\,\mathbf{a}_j - \mathbf{proj}_{\mathbf{b}_2}\,\mathbf{a}_j - \ldots - \mathbf{proj}_{\mathbf{b}_{j-1}}\,\mathbf{a}_j  \; (7) </math> этот вектор вычисляется следующим образом:
 
: <math> \begin{array}{lclr}
 
\mathbf{a}_j^{(1)} & = &\mathbf{a}_j - \mathbf{proj}_{\mathbf{b}_1}\,\mathbf{a}_j & (8) \\
 
\mathbf{a}_j^{(2)} & = &\mathbf{a}_j^{(1)} - \mathbf{proj}_{\mathbf{b}_2} \, \mathbf{a}_j^{(1)} & (9) \\& \vdots & & \\
 
\mathbf{a}_j^{(j-2)} & = & \mathbf{a}_j^{(j-3)} - \mathbf{proj}_{\mathbf{b}_{j-2}} \, \mathbf{a}_j^{(j-3)} & (10) \\
 
\mathbf{b}_j & = & \mathbf{a}_j^{(j-2)} - \mathbf{proj}_{\mathbf{b}_{j-1}} \, \mathbf{a}_j^{(j-2)} & (11)
 
\end{array} </math>
 
  
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===
Строка 119: Строка 49:
  
 
=== Макроструктура алгоритма ===
 
=== Макроструктура алгоритма ===
Данный алгоритм использует в качестве составных частей другие алгоритмы. В дальнейшем имеет смысл описывать алгоритм не в максимально детализированном виде (т.е. на уровне арифметических операций), а давать только его макроструктуру, то есть описывает структуру и состав макроопераций. Типичной макрооперацией, часто встречающиеся в алгоритме является оператор проекции векторов. Как записано и в описании ядра алгоритма, основную часть метода ортогонализации Грамма-Шмидта составляют множественные (всего их <math>\frac{N(N-1)}{2}</math>) вычисления оператора проекции.
+
 
 +
Данный алгоритм использует в качестве составных частей другие, более мелкие. Далее описание будет не в максимально детализированном виде (т.е. на уровне арифметических операций), а только на уровне его макроструктуры. Типичной макрооперацией, часто встречающиеся в алгоритме является оператор проекции векторов. Как записано и в описании ядра алгоритма, основную часть метода ортогонализации Грамма-Шмидта составляют множественные (всего их <math>\frac{N(N-1)}{2}</math>) вычисления оператора проекции.
  
 
=== Схема реализации последовательного алгоритма ===
 
=== Схема реализации последовательного алгоритма ===
  
 
Следующий алгоритм реализует нормализацию Грамма-Шмидта. Векторы <math>v_1,...,v_k</math> заменяются набором ортонормированных векторов, которые имеют ту же линейную оболочку.
 
Следующий алгоритм реализует нормализацию Грамма-Шмидта. Векторы <math>v_1,...,v_k</math> заменяются набором ортонормированных векторов, которые имеют ту же линейную оболочку.
 +
 
[[File:Gram-Schmidt ortho.png|none|thumb]]
 
[[File:Gram-Schmidt ortho.png|none|thumb]]
  
Строка 132: Строка 64:
 
1. <math>\mathbf  {b}_{1}=\mathbf  {a}_{1}</math>
 
1. <math>\mathbf  {b}_{1}=\mathbf  {a}_{1}</math>
  
2. Далее для всех векторов <math>\mathbf  {b}_{i}</math> для <math>i=2 ... N</math> производим вычисление по следующей формуле:
+
2. Далее для всех векторов <math>\mathbf  {b}_{i}</math> для <math>i=2 ... N</math> производится вычисление по следующей формуле:
 
<math>{\mathbf  {b}}_{i}={\mathbf  {a}}_{i}-\displaystyle \sum _{{j=1}}^{{i-1}}{\mathbf  {proj}}_{{{\mathbf  {b}}_{j}}}\,{\mathbf  {a}}_{i}</math>.  
 
<math>{\mathbf  {b}}_{i}={\mathbf  {a}}_{i}-\displaystyle \sum _{{j=1}}^{{i-1}}{\mathbf  {proj}}_{{{\mathbf  {b}}_{j}}}\,{\mathbf  {a}}_{i}</math>.  
  
 
В ней на каждом шаге <math>i</math> по очереди вычисляются все <math>{\mathbf  {proj}}_{{{\mathbf  {b}}_{j}}}\,{\mathbf  {a}}_{i}</math> для <math>j=1 ... i-1</math>
 
В ней на каждом шаге <math>i</math> по очереди вычисляются все <math>{\mathbf  {proj}}_{{{\mathbf  {b}}_{j}}}\,{\mathbf  {a}}_{i}</math> для <math>j=1 ... i-1</math>
  
Пример реализации на Python. Функция работает для произвольного количества векторов любой размерности. При этом если количество векторов <math>\mathbf{a}_1,\;\ldots,\;\mathbf{a}_N</math> больше их размерности или они линейно зависимы то функция возвращает максимально возможное число линейно независимых векторов <math>\mathbf{b}_1,\;\ldots,\;\mathbf{b}_n</math>, а остальные векторы <math>\mathbf{b}_{n+1},\;\ldots,\;\mathbf{b}_N</math> нулевые.
+
==== Пример реализации на Python ====
 +
 
 +
Функция работает для произвольного количества векторов любой размерности. При этом если количество векторов <math>\mathbf{a}_1,\;\ldots,\;\mathbf{a}_N</math> больше их размерности или они линейно зависимы то функция возвращает максимально возможное число линейно независимых векторов <math>\mathbf{b}_1,\;\ldots,\;\mathbf{b}_n</math>, а остальные векторы <math>\mathbf{b}_{n+1},\;\ldots,\;\mathbf{b}_N</math> нулевые.
 
<source lang="python">
 
<source lang="python">
 
import random
 
import random
Строка 192: Строка 126:
  
 
=== Информационный граф ===
 
=== Информационный граф ===
 +
 
Опишем граф алгоритма как аналитически, так и в виде рисунка.
 
Опишем граф алгоритма как аналитически, так и в виде рисунка.
  
Строка 265: Строка 200:
 
При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных, также линейна.
 
При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных, также линейна.
  
Алгоритм почти полностью детерминирован — единственность результата выполнения гарантирована, однако возможно накопление ошибок округления при использовании классического процесса Грама-Шмидта. При этом модифицированный алгоритм дает более хороший результат.
+
Алгоритм почти полностью детерминирован — единственность результата выполнения гарантирована, однако возможно накопление ошибок округления при использовании классического процесса Грама-Шмидта.  
  
 
Алгоритм является численно неустойчивым — ошибки округления могут привести к неортогональности полученных векторов.
 
Алгоритм является численно неустойчивым — ошибки округления могут привести к неортогональности полученных векторов.

Версия 15:23, 20 января 2018


Классическая ортогонализация Грама-Шмидта
Последовательный алгоритм
Последовательная сложность O(N^3)
Объём входных данных N^2
Объём выходных данных 3N^2/2
Параллельный алгоритм
Высота ярусно-параллельной формы O(N)
Ширина ярусно-параллельной формы O(N^2)


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

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

Процесс ортогонализации Грама-Шмидта — это один из алгоритмов, в которых на основе множества линейно независимых векторов {\displaystyle \mathbf {a} _{1},\;\ldots ,\;\mathbf {a} _{N}} строится множество ортогональных {\displaystyle \mathbf {b}_{1},\;\ldots ,\;\mathbf {b} _{N}} или ортонормированных векторов {\displaystyle \mathbf {e} _{1},\;\ldots ,\;\mathbf {e}_{N}} , причём так, что каждый вектор {\displaystyle \mathbf {b} _{j}} или {\displaystyle \mathbf {e} _{j}} может быть выражен линейной комбинацией векторов {\displaystyle \mathbf {a} _{1},\;\ldots ,\; \mathbf {a} _{j}}.

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

Пусть имеются линейно независимые векторы \mathbf{a}_1,\;\ldots,\;\mathbf{a}_N.

Если определить оператор проекции следующим образом: \mathbf{proj}_{\mathbf{b}}\,\mathbf{a} = {\langle \mathbf{a}, \mathbf{b} \rangle \over \langle \mathbf{b}, \mathbf{b}\rangle} \mathbf{b} ,

где \langle \mathbf{a}, \mathbf{b} \rangle — скалярное произведение векторов \mathbf{a} и \mathbf{b},

то классический процесс Грама — Шмидта выполняется следующим образом:

{\begin{array}{lclr} {\mathbf {b}}_{1}&=&{\mathbf {a}}_{1}&(1)\\ {\mathbf {b}}_{2}&=&{\mathbf {a}}_{2}-{\mathbf {proj}}_{{{\mathbf {b}}_{1}}}\,{\mathbf {a}}_{2}&(2)\\ {\mathbf {b}}_{3}&=&{\mathbf {a}}_{3}-{\mathbf {proj}}_{{{\mathbf {b}}_{1}}}\,{\mathbf {a}}_{3}-{\mathbf {proj}}_{{{\mathbf {b}}_{2}}}\,{\mathbf {a}}_{3}&(3)\\ {\mathbf {b}}_{4}&=&{\mathbf {a}}_{4}-{\mathbf {proj}}_{{{\mathbf {b}}_{1}}}\,{\mathbf {a}}_{4}-{\mathbf {proj}}_{{{\mathbf {b}}_{2}}}\,{\mathbf {a}}_{4}-{\mathbf {proj}}_{{{\mathbf {b}}_{3}}}\,{\mathbf {a}}_{4}&(4)\\ &\vdots &&\\{\mathbf {b}}_{N}&=&{\mathbf {a}}_{N}-\displaystyle \sum _{{j=1}}^{{N-1}}{\mathbf {proj}}_{{{\mathbf {b}}_{j}}}\,{\mathbf {a}}_{N}&(N) \end{array}}


На основе каждого вектора \mathbf{b}_j \;(j = 1 \ldots N) может быть получен нормированный вектор: \mathbf{e}_j = {\mathbf{b}_j\over \|\| \mathbf{b}_j \|\|_2} (у нормированного вектора направление будет таким же, как у исходного, а длина — единичной).

Результаты процесса Грама — Шмидта:

\mathbf{b}_1,\;\ldots,\;\mathbf{b}_N — система ортогональных векторов либо

\mathbf{e}_1,\;\ldots,\;\mathbf{e}_N — система ортонормированных векторов.


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

Вычислительное ядро последовательной версии метода ортогонализации Грамма-Шмидта можно составить из множественных (всего их \frac{N(N-1)}{2}) вычислений проекций : \mathbf{proj}_{\mathbf{b_j}}\,\mathbf{a_i}

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

Данный алгоритм использует в качестве составных частей другие, более мелкие. Далее описание будет не в максимально детализированном виде (т.е. на уровне арифметических операций), а только на уровне его макроструктуры. Типичной макрооперацией, часто встречающиеся в алгоритме является оператор проекции векторов. Как записано и в описании ядра алгоритма, основную часть метода ортогонализации Грамма-Шмидта составляют множественные (всего их \frac{N(N-1)}{2}) вычисления оператора проекции.

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

Следующий алгоритм реализует нормализацию Грамма-Шмидта. Векторы v_1,...,v_k заменяются набором ортонормированных векторов, которые имеют ту же линейную оболочку.

Gram-Schmidt ortho.png

Вычислительная сложность этого 2Nk^2 операции с плавающей точкой, где N - размерность векторов.

Последовательность исполнения метода следующая:

1. \mathbf {b}_{1}=\mathbf {a}_{1}

2. Далее для всех векторов \mathbf {b}_{i} для i=2 ... N производится вычисление по следующей формуле: {\mathbf {b}}_{i}={\mathbf {a}}_{i}-\displaystyle \sum _{{j=1}}^{{i-1}}{\mathbf {proj}}_{{{\mathbf {b}}_{j}}}\,{\mathbf {a}}_{i}.

В ней на каждом шаге i по очереди вычисляются все {\mathbf {proj}}_{{{\mathbf {b}}_{j}}}\,{\mathbf {a}}_{i} для j=1 ... i-1

1.5.1 Пример реализации на Python

Функция работает для произвольного количества векторов любой размерности. При этом если количество векторов \mathbf{a}_1,\;\ldots,\;\mathbf{a}_N больше их размерности или они линейно зависимы то функция возвращает максимально возможное число линейно независимых векторов \mathbf{b}_1,\;\ldots,\;\mathbf{b}_n, а остальные векторы \mathbf{b}_{n+1},\;\ldots,\;\mathbf{b}_N нулевые.

import random

def GramSchmidt(*a):
    k=len(a[0])
    N=len(a);
    b = [[0] * k for i in range(N)]
    b[0]=a[0]
    for i in range(1,N):
        sum=a[i]
        for j in range(0,i):
            scolar_ab=0
            scolar_bb=0
            proj=[i for i in range(k)]
            for n in range(k):
                scolar_ab+=b[j][n]*a[i][n]
                scolar_bb+=b[j][n]*b[j][n]
            for n in range(k):
                proj[n]=(scolar_ab/scolar_bb)*b[j][n]
            for n in range(k):
                sum[n]-=proj[n]
        b[i]=sum
    return b;

l1=[random.randrange(0,10) for i in range(3)]
l2=[random.randrange(0,10) for i in range(3)]
l3=[random.randrange(0,10) for i in range(3)]
print(l1,l2,l3)
print(GramSchmidt(l1,l2,l3))

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

Для построения ортогонального набора векторов в последовательном варианте требуется:

При k=N:

  • \frac{N(N-1)}{2} делений,
  • \frac{N(N-1)(3N-1)}{2} сложений (вычитаний),
  • \frac{3N^2 (N-1)}{2} умножений.

При k≠N

  • \frac{N(N-1)}{2} делений,
  • \frac{N(N-1)(3k-1)}{2} сложений (вычитаний),
  • \frac{3Nk (N-1)}{2} умножений.

При классификации по последовательной сложности, таким образом, ортогонализация Грамма-Шмидта относится к алгоритмам с кубической сложностью.

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

Опишем граф алгоритма как аналитически, так и в виде рисунка.

Граф алгоритма состоит из двух групп вершин, расположенных в целочисленных узлах двух областей.

Первая группа вершин расположена в двумерной области, соответствующая ей операция \mathbf{proj}_{\mathbf{b_j}}\,\mathbf{a_i} = {\langle \mathbf{a_i}, \mathbf{b_j} \rangle \over \langle \mathbf{b_j}, \mathbf{b_j}\rangle} \mathbf{b_j} , .

Естественно введённые координаты области таковы:

i — меняется в диапазоне от 2 до N, принимая все целочисленные значения;

j — меняется в диапазоне от 1 до i-1, принимая все целочисленные значения.

Аргументы операции следующие:

a_i: элементы входных данных, а именно a_i;

b_j: результат срабатывания операции, соответствующей вершине из второй группы, с координатой j.

Вторая группа вершин расположена в двухмерной области, соответствующая ей операция a - b.

Естественно введённые координаты области таковы:

i — меняется в диапазоне от 2 до N, принимая все целочисленные значения;

j — меняется в диапазоне от 1 до i-1, принимая все целочисленные значения.

Аргументы операции следующие:

a:

j=1 - входные данные a_j

j>1 - результат срабатывания операции, соответствующей вершине из второй группы, с координатой j-1

b:

результат срабатывания операции, соответствующей вершине из первой группы, с координатой j

Рис. 5. Граф алгоритма с отображением входных и выходных данных. Proj - вычисление оператора проекции, F - операция a-b, In - входные данные, Out - результаты.

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

В параллельном варианте, в отличие от последовательного, вычисления \mathbf{proj}_{\mathbf{b_j}}\,\mathbf{a_i} можно выполнять параллельно. То есть после каждого вычисления b_j можно запускать параллельное вычисление \mathbf{proj}_{\mathbf{b_j}}\,\mathbf{a_i} для всех i=j+1..N. Кроме того можно параллельно производить вычитание соответствующего \mathbf{proj}_{\mathbf{b_j}}\,\mathbf{a_i} для всех i=j+1..N.

Для ортогонализации в параллельном варианте требуется последовательно выполнить следующие ярусы:

  • N ярусов в каждом из которых будет выполнятся,
  • по N - 1 операторов проекций (в каждом из ярусов линейное количество проекций, в зависимости от яруса — от N-1 до 1),
  • по N - 1 сложений (в каждом из ярусов линейное количество сложений, в зависимости от яруса — от N-1 до 1),

При классификации по высоте (количество ярусов в ЯПФ ) ЯПФ, таким образом, ортогонализация Грамма-Шмидта относится к алгоритмам со сложностью O(N).

При классификации по ширине (максимальное количество вершин в ярусе) ЯПФ его сложность будет O(N^2).

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

Входные данные: множества линейно независимых векторов {\displaystyle \mathbf {a} _{1},\;\ldots ,\;\mathbf {a} _{N}}, каждый из которых описывается \mathbf{ a_i= [a^i_1, a^i_2, ..., a^i_k]} .

Дополнительные ограничения:

  • вектора {\displaystyle \mathbf {a} _{1},\;\ldots ,\;\mathbf {a} _{N}} линейно независимы, поэтому k \geqslant N.

Объём входных данных: Nk

Выходные данные: множество ортогональных векторов {\displaystyle \mathbf {b} _{1},\;\ldots ,\;\mathbf {b} _{N}} , каждый из которых описывается \mathbf{ b_i= [b^i_1, b^i_2, ..., b^i_k]} .

Объём выходных данных: Nk

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

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является линейным (отношение кубической к квадратичной).

При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных, также линейна.

Алгоритм почти полностью детерминирован — единственность результата выполнения гарантирована, однако возможно накопление ошибок округления при использовании классического процесса Грама-Шмидта.

Алгоритм является численно неустойчивым — ошибки округления могут привести к неортогональности полученных векторов.

Процесс Грама — Шмидта может применяться также к бесконечной последовательности линейно независимых векторов.

Кроме того, процесс Грама — Шмидта может применяться к линейно зависимым векторам. В этом случае он выдаёт \mathbf{0} (нулевой вектор) на шаге j, если \mathbf{a}_j является линейной комбинацией векторов \mathbf{a}_1,\;\ldots,\;\mathbf{a}_{j-1}. Если это может случиться, то для сохранения ортогональности выходных векторов и для предотвращения деления на ноль при ортонормировании алгоритм должен делать проверку на нулевые векторы и отбрасывать их. Количество векторов, выдаваемых алгоритмом, будет равно размерности подпространства, порождённого векторами (т.е. количеству линейно независимых векторов, которые можно выделить среди исходных векторов).

Процесс Грама ― Шмидта может быть истолкован как разложение невырожденной квадратной матрицы в произведение ортогональной (или унитарной матрицы в случае эрмитова пространства) и верхнетреугольной матрицы с положительными диагональными элементами ― QR-разложение, что есть частный случай разложения Ивасавы.