Викия

Математика

Процесс Грама ― Шмидта

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Процесс Грама ― Шмидта ― наиболее известный алгоритм ортогонализации, при котором по линейно независимой системе a_1, a_2,...,a_k строится ортогональная система b_1, b_2,...,b_k такая, что каждый вектор b_i линейно выражается через a_1,a_2,...,a_i, то есть матрица перехода от \{a_i\} к \{b_i\}верхнетреугольная матрица. При этом можно добиться того, чтобы система \{b_i\} была ортонормированной и чтобы диагональные элементы матрицы перехода были положительны; этими условиями система \{b_i\} и матрица перехода определяются однозначно.

Этот процесс применим также и к счётной системе векторов.

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

АлгоритмПравить

Полагают b_1=a_1, и, если уже построены векторы b_1,b_2,..,b_{i-1}, то

b_i=a_i-\sum_{j=1}^{i-1}\frac{\langle a_i,b_j\rangle}{\langle b_j,b_j\rangle} b_j.

Геометрический смысл описанного процесса состоит в том, что на каждом шагу вектор b_i является перпендикуляром, восстановленным к линейной оболочке векторов a_1,...,a_{i-1} до конца вектора a_i.

Нормируя полученные векторы b_i,

c_i=b_i/|b_i|

получают искомую ортонормированную систему \{c_i\}.

Вывод алгоритма построения ортогонального базиса по линейно независимому набору векторов {\mathbf{a}_i} Править

Процесс построения базиса заключается в проецировании первого вектора базиса на следующие за \mathbf{a}_0 вектора \mathbf{a}_i и нахождения ортогональных к этим проекциям векторов \mathbf{b}_i.

Первый вектор строящегося базиса выбираем так:
1. \mathbf{b}_0 = \mathbf{a}_0 - так выбираем первый вектор строящегося базиса.
2. \mathbf{e}_{b_0} = \frac{ \mathbf{b}_0 }{ \| \mathbf{b}_0 \|  } - нормируем вектор \mathbf{b_0}
3. \mathbf{b}_1 = \mathbf{a}_1 - \langle \mathbf{a_1}, \mathbf{e_{b_0}} \rangle \cdot \mathbf{e_{b_0}} , где \langle \mathbf{a_1}, \mathbf{e_{b_0}} \rangle \cdot \mathbf{e_{b_0}} - проекция вектора \mathbf{a_1} на вектор  \mathbf{e_{b_0}} , вдоль нормированного вектора \mathbf{e_{b_0}}.
4. \mathbf{b}_2 = \mathbf{a}_2 - \langle \mathbf{a}_2, \mathbf{e_{b_0}} \rangle \cdot \mathbf{e_{b_0}} - \langle \mathbf{a}_2, \mathbf{e_{b_1}} \rangle \cdot \mathbf{e_{b_1}}
5. \mathbf{b}_i = \mathbf{a}_i - \sum\limits_{k=0}^{i-1} \langle \mathbf{a}_i, \mathbf{e_{b_k}} \rangle \cdot \mathbf{e_{b_k}} - в общем виде.
Заметим что: \langle \mathbf{a}, \mathbf{e_{b}} \rangle \cdot \mathbf{e_{b}} = \langle \mathbf{a}, \frac{ \mathbf{b}}{ \| \mathbf{b} \|  } \rangle \cdot \frac{ \mathbf{b}}{ \| \mathbf{b} \|  } = \frac{ \langle \mathbf{a}, \mathbf{b} \rangle}{\| \mathbf{b} \|^2} \cdot \mathbf{b}

А так как норма(длинна вектора)  \| \mathbf{b} \| в линейном пространстве \mathbf{B} задаётся скалярным произведением, \| \mathbf{b} \| = \sqrt{\langle \mathbf{b}, \mathbf{b} \rangle},\quad \mathbf{b} \in \mathbf{B}.
получаем: \frac{ \langle \mathbf{a}, \mathbf{b} \rangle}{\| \mathbf{b} \|^2} \cdot \mathbf{b} = \frac{ \langle \mathbf{a}, \mathbf{b} \rangle}{\langle \mathbf{b}, \mathbf{b} \rangle} \cdot \mathbf{b}

И получаем окончательный вид:
Первый вектор строящегося базиса определяется как:
1. \mathbf{b}_0 = \mathbf{a}_0 - первый вектор с индексом i = 0
2. \mathbf{b}_i = \mathbf{a}_i - \sum\limits_{k=0}^{i-1} \frac{ \langle \mathbf{a}_i, \mathbf{b}_k \rangle}{\langle \mathbf{b}_k, \mathbf{b}_k \rangle} \cdot \mathbf{b}_k - все остальные векторы с индексами:  i = 1 \ldots N-1

Реализация алгоритмаПравить

Данный скрипт, предназначенный для пакета Mathematica, проводит процесс ортогонализации Грама ― Шмидта над векторами, заданными в фигурных скобках предпоследний строки. Количество векторов и их координат могут быть произвольными. В данном случае для примера взяты вектора {-2, 1, 0}, {-2, 0, 1}, {-0.5, -1, 1}

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}}]
Null

СвойстваПравить

hr:Gram-Schmidtov postupak is:Gram-Schmidt reikniritiðnl:Gram-Schmidtmethode pl:Ortogonalizacja Grama-Schmidtasr:Грам-Шмитов поступак

Викия-сеть

Случайная вики