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

Первые два шага процесса Грама – Шмидта

В математике , особенно в линейной алгебре и численном анализе , процесс Грама – Шмидта - это метод ортонормирования набора векторов во внутреннем пространстве произведения , чаще всего в евклидовом пространстве R ^n, снабженном стандартным внутренним произведением . Процесс Гр-Шмидт принимает конечен , линейно независимые множества векторов S = { v ₁ , ..., v _K } для к ≤ пи генерирует ортогональный набор S ' = { U ₁ , ..., U _K } , что пролеты то же к - мерное подпространство R ^п , как S .

Метод назван в честь Йоргена Педерсена Грама и Эрхарда Шмидта , но Пьер-Симон Лаплас был знаком с ним еще до Грама и Шмидта. ^[1] В теории разложений групп Ли оно обобщается разложением Ивасавы .

Применение процесса Грама – Шмидта к векторам-столбцам матрицы полного столбца рангов дает QR-разложение (оно разлагается на ортогональную и треугольную матрицу ).

Процесс Грама – Шмидта [ править ]

Модифицированный процесс Грама-Шмидта выполняется на трех линейно независимых, неортогональных векторах базиса для R ³ . Нажмите на изображение, чтобы узнать подробности. Модификация объясняется в разделе «Числовая стабильность» этой статьи.

Определим оператор проекции как

${\ displaystyle \ mathrm {proj} _ {\ mathbf {u}} (\ mathbf {v}) = {\ frac {\ langle \ mathbf {u}, \ mathbf {v} \ rangle} {\ langle \ mathbf { u}, \ mathbf {u} \ rangle}} {\ mathbf {u}},}$

где обозначает скалярное произведение векторов u и v . Этот оператор проецирует вектор v ортогонально на линию, натянутую на вектор u . Если u = 0 , мы определяем , т. Е. Карта проекции является нулевой картой, отправляя каждый вектор в нулевой вектор.${\ Displaystyle \ langle \ mathbf {u}, \ mathbf {v} \ rangle}$${\ Displaystyle \ mathrm {proj} _ {\ mathbf {0}} (\ mathbf {v}): = \ mathbf {0}}$${\ displaystyle \ mathrm {proj} _ {\ mathbf {0}}}$

Тогда процесс Грама – Шмидта работает следующим образом:

${\displaystyle {\begin{aligned}\mathbf {u} _{1}&=\mathbf {v} _{1},&\mathbf {e} _{1}&={\frac {\mathbf {u} _{1}}{\|\mathbf {u} _{1}\|}}\\\mathbf {u} _{2}&=\mathbf {v} _{2}-\mathrm {proj} _{\mathbf {u} _{1}}(\mathbf {v} _{2}),&\mathbf {e} _{2}&={\frac {\mathbf {u} _{2}}{\|\mathbf {u} _{2}\|}}\\\mathbf {u} _{3}&=\mathbf {v} _{3}-\mathrm {proj} _{\mathbf {u} _{1}}(\mathbf {v} _{3})-\mathrm {proj} _{\mathbf {u} _{2}}(\mathbf {v} _{3}),&\mathbf {e} _{3}&={\frac {\mathbf {u} _{3}}{\|\mathbf {u} _{3}\|}}\\\mathbf {u} _{4}&=\mathbf {v} _{4}-\mathrm {proj} _{\mathbf {u} _{1}}(\mathbf {v} _{4})-\mathrm {proj} _{\mathbf {u} _{2}}(\mathbf {v} _{4})-\mathrm {proj} _{\mathbf {u} _{3}}(\mathbf {v} _{4}),&\mathbf {e} _{4}&={\mathbf {u} _{4} \over \|\mathbf {u} _{4}\|}\\&{}\ \ \vdots &&{}\ \ \vdots \\\mathbf {u} _{k}&=\mathbf {v} _{k}-\sum _{j=1}^{k-1}\mathrm {proj} _{\mathbf {u} _{j}}(\mathbf {v} _{k}),&\mathbf {e} _{k}&={\frac {\mathbf {u} _{k}}{\|\mathbf {u} _{k}\|}}.\end{aligned}}}$

Последовательность у ₁ , ..., у _к является искомой системой ортогональных векторов, а нормализованные векторы х ₁ , ..., е _к образуют орто нормальный набор. Вычисление последовательности u ₁ ,…, u _k известно как ортогонализация Грама – Шмидта , а вычисление последовательности e ₁ ,…, e _k известно как ортонормировка Грама – Шмидта, поскольку векторы нормализованы.

Чтобы проверить, что эти формулы дают ортогональную последовательность, сначала вычислите , подставив приведенную выше формулу для u ₂ : мы получаем ноль. Затем используйте это для вычисления снова, подставив формулу для u ₃ : мы получаем ноль. Общее доказательство проводится по математической индукции .${\displaystyle \langle \mathbf {u} _{1},\mathbf {u} _{2}\rangle }$${\displaystyle \langle \mathbf {u} _{1},\mathbf {u} _{3}\rangle }$

Геометрически этот метод действует следующим образом: для вычисления u _i он ортогонально проецирует v _i на подпространство U, порожденное u ₁ ,…, u _{i −1} , которое совпадает с подпространством, порожденным v ₁ ,…, v _{i −1} . Вектор U _я затем определяется как разница между V _я и эта проекция, гарантированно ортогональна все векторы в подпространстве U .

Процесс Грама – Шмидта также применим к линейно независимой счетно бесконечной последовательности { v _i } _i . Результатом является ортогональная (или ортонормированная) последовательность { u _i } _i такая, что для натурального числа n : алгебраическая оболочка v ₁ ,…, v _n такая же, как у u ₁ ,…, u _n .

Если процесс Грама – Шмидта применяется к линейно зависимой последовательности, он выводит вектор 0 на i- м шаге, предполагая, что v _i является линейной комбинацией v ₁ ,…, v _{i −1} . Если должен быть создан ортонормированный базис, то алгоритм должен проверить наличие нулевых векторов в выходных данных и отбросить их, потому что никакое число, кратное нулевому вектору, не может иметь длину 1. Число векторов, выводимых алгоритмом, будет тогда измерением. пространства, занимаемого исходными входами.

Вариант процесса Грама-Шмидта с использованием трансфинитную рекурсии применяется к (возможно , несчетное) бесконечной последовательности векторов дает набор ортогональных векторов с таким образом, что для любого , то завершение в промежуток такой же , как и у . В частности, когда он применяется к (алгебраическому) базису гильбертова пространства (или, в более общем смысле, базису любого плотного подпространства), он дает (функционально-аналитический) ортонормированный базис. Обратите внимание, что в общем случае часто выполняется строгое неравенство , даже если начальное множество было линейно независимым, и промежуток не обязательно должен быть подпространством промежутка${\displaystyle (v_{\alpha })_{\alpha <\lambda }}$${\displaystyle (u_{\alpha })_{\alpha <\kappa }}$${\displaystyle \kappa \leq \lambda }$${\displaystyle \alpha \leq \lambda }$${\displaystyle \{u_{\beta }:\beta <\min(\alpha ,\kappa )\}}$${\displaystyle \{v_{\beta }:\beta <\alpha \}}$${\displaystyle \kappa <\lambda }$${\displaystyle (u_{\alpha })_{\alpha <\kappa }}$${\displaystyle (v_{\alpha })_{\alpha <\lambda }}$ (скорее, это подпространство его завершения).

Пример [ править ]

Евклидово пространство [ править ]

Рассмотрим следующий набор векторов в R ² (с обычным внутренним произведением )

${\displaystyle S=\left\{\mathbf {v} _{1}={\begin{bmatrix}3\\1\end{bmatrix}},\mathbf {v} _{2}={\begin{bmatrix}2\\2\end{bmatrix}}\right\}.}$

Теперь выполните Грама – Шмидта, чтобы получить ортогональный набор векторов:

${\displaystyle \mathbf {u} _{1}=\mathbf {v} _{1}={\begin{bmatrix}3\\1\end{bmatrix}}}$

${\displaystyle \mathbf {u} _{2}=\mathbf {v} _{2}-\mathrm {proj} _{\mathbf {u} _{1}}(\mathbf {v} _{2})={\begin{bmatrix}2\\2\end{bmatrix}}-\mathrm {proj} _{\left[{\begin{smallmatrix}3\\1\end{smallmatrix}}\right]}{\begin{bmatrix}2\\2\end{bmatrix}}={\begin{bmatrix}2\\2\end{bmatrix}}-{\frac {8}{10}}{\begin{bmatrix}3\\1\end{bmatrix}}={\begin{bmatrix}-2/5\\6/5\end{bmatrix}}.}$

Проверяем, что векторы u ₁ и u ₂ действительно ортогональны:

${\displaystyle \langle \mathbf {u} _{1},\mathbf {u} _{2}\rangle =\left\langle {\begin{bmatrix}3\\1\end{bmatrix}},{\begin{bmatrix}-2/5\\6/5\end{bmatrix}}\right\rangle =-{\frac {6}{5}}+{\frac {6}{5}}=0,}$

отмечая, что если скалярное произведение двух векторов равно 0, то они ортогональны.

Для ненулевых векторов мы можем затем нормализовать векторы, разделив их размеры, как показано выше:

${\displaystyle \mathbf {e} _{1}={\frac {1}{\sqrt {10}}}{\begin{bmatrix}3\\1\end{bmatrix}}}$

${\displaystyle \mathbf {e} _{2}={\frac {1}{\sqrt {40 \over 25}}}{\begin{bmatrix}-2/5\\6/5\end{bmatrix}}={\frac {1}{\sqrt {10}}}{\begin{bmatrix}-1\\3\end{bmatrix}}.}$

Свойства [ править ]

Обозначим через результат применения процесса Грама – Шмидта к набору векторов . Это дает карту .${\displaystyle \operatorname {GS} (\mathbf {v} _{1},\dots ,\mathbf {v} _{k})}$${\displaystyle \mathbf {v} _{1},\dots ,\mathbf {v} _{k}}$${\displaystyle \operatorname {GS} \colon (\mathbf {R} ^{n})^{k}\to (\mathbf {R} ^{n})^{k}}$

Обладает следующими свойствами:

• Это непрерывно
• Это сохраняет ориентацию в том смысле, что .${\displaystyle \operatorname {or} (\mathbf {v} _{1},\dots ,\mathbf {v} _{k})=\operatorname {or} (\operatorname {GS} (\mathbf {v} _{1},\dots ,\mathbf {v} _{k}))}$
• Он коммутирует с ортогональными отображениями:

Позвольте быть ортогональным (по отношению к данному внутреннему продукту). Тогда у нас есть${\displaystyle g\colon \mathbf {R} ^{n}\to \mathbf {R} ^{n}}$

${\displaystyle \operatorname {GS} (g(\mathbf {v} _{1}),\dots ,g(\mathbf {v} _{k}))=\left(g(\operatorname {GS} (\mathbf {v} _{1},\dots ,\mathbf {v} _{k})_{1}),\dots ,g(\operatorname {GS} (\mathbf {v} _{1},\dots ,\mathbf {v} _{k})_{k})\right)}$

Далее параметризованная версия процесса Грама – Шмидта дает (сильную) деформационную ретракцию общей линейной группы на ортогональную группу .${\displaystyle \mathrm {GL} (\mathbf {R} ^{n})}$${\displaystyle O(\mathbf {R} ^{n})}$

Числовая стабильность [ править ]

Когда этот процесс реализуется на компьютере, векторы часто не совсем ортогональны из-за ошибок округления . Для процесса Грама – Шмидта, описанного выше (иногда называемого «классическим Грамом – Шмидтом»), эта потеря ортогональности особенно велика; поэтому говорят, что (классический) процесс Грама – Шмидта численно нестабилен .${\displaystyle \mathbf {u} _{k}}$

Процесс Грама – Шмидта можно стабилизировать с помощью небольшой модификации; эту версию иногда называют модифицированной версией Грама-Шмидта или MGS. Этот подход дает тот же результат, что и исходная формула в точной арифметике, и вносит меньшие ошибки в арифметику конечной точности. Вместо вычисления вектора u _k как

${\displaystyle \mathbf {u} _{k}=\mathbf {v} _{k}-\operatorname {proj} _{\mathbf {u} _{1}}(\mathbf {v} _{k})-\operatorname {proj} _{\mathbf {u} _{2}}(\mathbf {v} _{k})-\cdots -\operatorname {proj} _{\mathbf {u} _{k-1}}(\mathbf {v} _{k}),}$

он вычисляется как

${\displaystyle {\begin{aligned}\mathbf {u} _{k}^{(1)}&=\mathbf {v} _{k}-\operatorname {proj} _{\mathbf {u} _{1}}(\mathbf {v} _{k}),\\\mathbf {u} _{k}^{(2)}&=\mathbf {u} _{k}^{(1)}-\operatorname {proj} _{\mathbf {u} _{2}}\left(\mathbf {u} _{k}^{(1)}\right),\\&\;\;\vdots \\\mathbf {u} _{k}^{(k-2)}&=\mathbf {u} _{k}^{(k-3)}-\operatorname {proj} _{\mathbf {u} _{k-2}}\left(\mathbf {u} _{k}^{(k-3)}\right),\\\mathbf {u} _{k}^{(k-1)}&=\mathbf {u} _{k}^{(k-2)}-\operatorname {proj} _{\mathbf {u} _{k-1}}\left(\mathbf {u} _{k}^{(k-2)}\right),\\\mathbf {u} _{k}&={\frac {\mathbf {u} _{k}^{(k-1)}}{\left\|\mathbf {u} _{k}^{(k-1)}\right\|}}\end{aligned}}}$

Этот метод используется в предыдущей анимации, когда промежуточный вектор v ' ₃ используется при ортогонализации синего вектора v ₃ .

Алгоритм [ править ]

Следующий алгоритм MATLAB реализует ортонормировку Грама – Шмидта для евклидовых векторов. Векторы v ₁ ,…, v _k (столбцы матрицы V, так что V(:,j)это j- й вектор) заменяются ортонормированными векторами (столбцами U), которые охватывают то же подпространство.

функция  [U] = грамшмидт ( В )[ n , k ] = размер ( V );  U = нули ( n , k );  U (:, 1 ) = V (:, 1 ) / norm ( V (:, 1 ));  для i = 2 : k    U (:, я ) = V (:, я ); для j = 1 : i - 1  U (:, i ) = U (:, i ) - ( U (:, j ) '* U (:, i ) ) / ( norm ( U (:, j ))) ^ 2 * U (:, j );    конец U (:, i ) = U (:, i ) / norm ( U (:, i ));  конецконец

Стоимость этого алгоритма асимптотически составляет O ( nk ² ) операций с плавающей запятой, где n - размерность векторов ( Голуб и Ван Лоан, 1996 , §5.2.8).

С помощью исключения Гаусса [ править ]

Если строки { v ₁ ,…, v _k } записаны как матрица , то применение исключения Гаусса к расширенной матрице даст ортогонализированные векторы вместо . Однако матрица должна быть приведена к форме эшелона строк , используя только строчную операцию добавления скалярного кратного одной строки к другой. ^[2] Например, как указано выше, мы имеем${\displaystyle A}$${\displaystyle \left[AA^{\mathsf {T}}|A\right]}$${\displaystyle A}$${\displaystyle AA^{\mathsf {T}}}$${\displaystyle \mathbf {v} _{1}={\begin{bmatrix}3&1\end{bmatrix}},\mathbf {v} _{2}={\begin{bmatrix}2&2\end{bmatrix}}}$

${\displaystyle \left[AA^{\mathsf {T}}|A\right]=\left[{\begin{array}{rr|rr}10&8&3&1\\8&8&2&2\end{array}}\right]}$

И сокращение этого до формы эшелона строк дает

${\displaystyle \left[{\begin{array}{rr|rr}1&.8&.3&.1\\0&1&-.25&.75\end{array}}\right]}$

Нормализованные векторы тогда

${\displaystyle \mathbf {e} _{1}={\frac {1}{\sqrt {.3^{2}+.1^{2}}}}{\begin{bmatrix}.3&.1\end{bmatrix}}={\frac {1}{\sqrt {10}}}{\begin{bmatrix}3&1\end{bmatrix}}}$

${\displaystyle \mathbf {e} _{2}={\frac {1}{\sqrt {.25^{2}+.75^{2}}}}{\begin{bmatrix}-.25&.75\end{bmatrix}}={\frac {1}{\sqrt {10}}}{\begin{bmatrix}-1&3\end{bmatrix}}.}$

как в примере выше.

Формула определения [ править ]

Результат процесса Грама – Шмидта может быть выражен в нерекурсивной формуле с использованием определителей .

${\displaystyle \mathbf {e} _{j}={\frac {1}{\sqrt {D_{j-1}D_{j}}}}{\begin{vmatrix}\langle \mathbf {v} _{1},\mathbf {v} _{1}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{1}\rangle &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{1}\rangle \\\langle \mathbf {v} _{1},\mathbf {v} _{2}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{2}\rangle &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{2}\rangle \\\vdots &\vdots &\ddots &\vdots \\\langle \mathbf {v} _{1},\mathbf {v} _{j-1}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{j-1}\rangle &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{j-1}\rangle \\\mathbf {v} _{1}&\mathbf {v} _{2}&\cdots &\mathbf {v} _{j}\end{vmatrix}}}$

${\displaystyle \mathbf {u} _{j}={\frac {1}{D_{j-1}}}{\begin{vmatrix}\langle \mathbf {v} _{1},\mathbf {v} _{1}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{1}\rangle &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{1}\rangle \\\langle \mathbf {v} _{1},\mathbf {v} _{2}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{2}\rangle &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{2}\rangle \\\vdots &\vdots &\ddots &\vdots \\\langle \mathbf {v} _{1},\mathbf {v} _{j-1}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{j-1}\rangle &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{j-1}\rangle \\\mathbf {v} _{1}&\mathbf {v} _{2}&\cdots &\mathbf {v} _{j}\end{vmatrix}}}$

где D ₀ = 1, а для J ≥ 1, D _J представляет собой определитель Грама

${\displaystyle D_{j}={\begin{vmatrix}\langle \mathbf {v} _{1},\mathbf {v} _{1}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{1}\rangle &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{1}\rangle \\\langle \mathbf {v} _{1},\mathbf {v} _{2}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{2}\rangle &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{2}\rangle \\\vdots &\vdots &\ddots &\vdots \\\langle \mathbf {v} _{1},\mathbf {v} _{j}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{j}\rangle &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{j}\rangle \end{vmatrix}}.}$

Обратите внимание, что выражение для u _k является «формальным» определителем, т.е. матрица содержит как скаляры, так и векторы; значение этого выражения определяется как результат расширения кофактора по строке векторов.

Детерминантная формула для Грама-Шмидта в вычислительном отношении медленнее (экспоненциально медленнее), чем рекурсивные алгоритмы, описанные выше; это в основном теоретический интерес.

Альтернативы [ править ]

Другие алгоритмы ортогонализации используют преобразования Хаусхолдера или вращения Гивенса . Алгоритмы, использующие преобразования Хаусхолдера, более стабильны, чем стабилизированный процесс Грама – Шмидта. С другой стороны, процесс Грама – Шмидта создает th ортогонализированный вектор после th итерации, в то время как ортогонализация с использованием отражений Хаусхолдера дает все векторы только в конце. Это делает применимым только процесс Грама – Шмидта для итерационных методов, таких как итерация Арнольди .${\displaystyle j}$${\displaystyle j}$

Еще одна альтернатива мотивирована использованием разложения Холецкого для обращения матрицы нормальных уравнений в линейных наименьших квадратах . Позвольте быть матрица ранга полного столбца , столбцы которой необходимо ортогонализировать. Матрица является эрмитовой и положительно определен , поэтому она может быть записана в виде , используя разложение Холецкого . Нижнетреугольная матрица со строго положительными диагональными элементами обратима . Тогда столбцы матрицы являются ортонормированными и охватывают то же подпространство в качестве столбцов исходной матрицы${\displaystyle V}$${\displaystyle V^{*}V}$${\displaystyle V^{*}V=LL^{*},}$${\displaystyle L}$${\displaystyle U=V\left(L^{-1}\right)^{*}}$${\displaystyle V}$. Явное использование продукта делает алгоритм нестабильным, особенно если число условий продукта велико. Тем не менее, этот алгоритм используется на практике и реализован в некоторых программных комплексах из-за его высокой эффективности и простоты.${\displaystyle V^{*}V}$

В квантовой механике существует несколько схем ортогонализации, характеристики которых лучше подходят для определенных приложений, чем оригинальные схемы Грама – Шмидта. Тем не менее, он остается популярным и эффективным алгоритмом даже для самых крупных расчетов электронной структуры. ^[3]

Ссылки [ править ]

Источники [ править ]

• Бау III, Давид; Трефетен, Ллойд Н. (1997), Численная линейная алгебра , Филадельфия: Общество промышленной и прикладной математики, ISBN 978-0-89871-361-9.
• Голуб, Джин Х .; Ван Лоан, Чарльз Ф. (1996), Matrix Computations (3-е изд.), Johns Hopkins, ISBN 978-0-8018-5414-9.
• Greub, Вернер (1975), Линейная алгебра (4-е изд.), Springer.
• Соливерез, CE; Гальяно, Э. (1985), "Ортонормализация на плоскости: геометрический подход" (PDF) , Mex. J. Phys. , 31 (4): 743–758.

Внешние ссылки [ править ]

• "Ортогонализация" , Математическая энциклопедия , EMS Press , 2001 [1994]
• Учебник по математике колледжа Харви Мадда по алгоритму Грама-Шмидта
• Самые ранние известные варианты использования некоторых слов математики: G В статье «Ортогонализация по Граму-Шмидту» содержится некоторая информация и ссылки на происхождение метода.
• Демонстрации: процесс Грама Шмидта на плоскости и процесс Грама Шмидта в пространстве
• Апплет ортогонализации Грама-Шмидта
• Ортогонализация NAG по Граму – Шмидту n векторов порядка m.
• Доказательство: Раймонд Пузио, Кинан Кидвелл. «Доказательство алгоритма ортогонализации Грама-Шмидта» (версия 8). PlanetMath.org.