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

Ортонормализация набора векторов

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

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

По техническому определению, это метод построения ортонормированного базиса из набора векторов в пространстве скалярного произведения , чаще всего евклидовом пространстве, снабженном стандартным скалярным произведением . Процесс Грама–Шмидта берет конечный линейно независимый набор векторов для k ≤ n и генерирует ортогональный набор , который охватывает то же самое -мерное подпространство , что и . ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle S=\{\mathbf {v} _{1},\ldots ,\mathbf {v} _{k}\}}$ ${\displaystyle S'=\{\mathbf {u} _{1},\ldots ,\mathbf {u} _{k}\}}$ ${\displaystyle k}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle S}$

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

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

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

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

Векторная проекция вектора на ненулевой вектор определяется как ^{[примечание 1]} где обозначает скалярное произведение векторов и . Это означает, что является ортогональной проекцией на прямую, натянутую на . Если является нулевым вектором, то определяется как нулевой вектор. ${\displaystyle \mathbf {v} }$ ${\displaystyle \mathbf {u} }$ $${\displaystyle \operatorname {proj} _{\mathbf {u} }(\mathbf {v} )={\frac {\langle \mathbf {v} ,\mathbf {u} \rangle }{\langle \mathbf {u} ,\mathbf {u} \rangle }}\,\mathbf {u} ,}$$ ${\displaystyle \langle \mathbf {v} ,\mathbf {u} \rangle }$ ${\displaystyle \mathbf {u} }$ ${\displaystyle \mathbf {v} }$ ${\displaystyle \operatorname {proj} _{\mathbf {u} }(\mathbf {v} )}$ ${\displaystyle \mathbf {v} }$ ${\displaystyle \mathbf {u} }$ ${\displaystyle \mathbf {u} }$ ${\displaystyle \operatorname {proj} _{\mathbf {u} }(\mathbf {v} )}$

Для данных векторов процесс Грама–Шмидта определяет векторы следующим образом: ${\displaystyle k}$ ${\displaystyle \mathbf {v} _{1},\ldots ,\mathbf {v} _{k}}$ ${\displaystyle \mathbf {u} _{1},\ldots ,\mathbf {u} _{k}}$ $${\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}-\operatorname {proj} _{\mathbf {u} _{1}}(\mathbf {v} _{2}),&\!\mathbf {e} _{2}&={\frac {\mathbf {u} _{2}}{\|\mathbf {u} _{2}\|}}\\\mathbf {u} _{3}&=\mathbf {v} _{3}-\operatorname {proj} _{\mathbf {u} _{1}}(\mathbf {v} _{3})-\operatorname {proj} _{\mathbf {u} _{2}}(\mathbf {v} _{3}),&\!\mathbf {e} _{3}&={\frac {\mathbf {u} _{3}}{\|\mathbf {u} _{3}\|}}\\\mathbf {u} _{4}&=\mathbf {v} _{4}-\operatorname {proj} _{\mathbf {u} _{1}}(\mathbf {v} _{4})-\operatorname {proj} _{\mathbf {u} _{2}}(\mathbf {v} _{4})-\operatorname {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}\operatorname {proj} _{\mathbf {u} _{j}}(\mathbf {v} _{k}),&\!\mathbf {e} _{k}&={\frac {\mathbf {u} _{k}}{\|\mathbf {u} _{k}\|}}.\end{aligned}}}$$

Последовательность — это требуемая система ортогональных векторов, а нормализованные векторы образуют ортонормированный набор . Вычисление последовательности известно как ортогонализация Грама–Шмидта , а вычисление последовательности известно как ортонормализация Грама–Шмидта . ${\displaystyle \mathbf {u} _{1},\ldots ,\mathbf {u} _{k}}$ ${\displaystyle \mathbf {e} _{1},\ldots ,\mathbf {e} _{k}}$ ${\displaystyle \mathbf {u} _{1},\ldots ,\mathbf {u} _{k}}$ ${\displaystyle \mathbf {e} _{1},\ldots ,\mathbf {e} _{k}}$

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

Геометрически этот метод работает следующим образом: для вычисления он ортогонально проецируется на подпространство , сгенерированное , которое совпадает с подпространством, сгенерированным . Затем вектор определяется как разность между и этой проекцией, гарантированно ортогональной всем векторам в подпространстве . ${\displaystyle \mathbf {u} _{i}}$ ${\displaystyle \mathbf {v} _{i}}$ ${\displaystyle U}$ ${\displaystyle \mathbf {u} _{1},\ldots ,\mathbf {u} _{i-1}}$ ${\displaystyle \mathbf {v} _{1},\ldots ,\mathbf {v} _{i-1}}$ ${\displaystyle \mathbf {u} _{i}}$ ${\displaystyle \mathbf {v} _{i}}$ ${\displaystyle U}$

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

Если процесс Грама-Шмидта применяется к линейно зависимой последовательности, он выводит вектор 0 на шаге , предполагая, что является линейной комбинацией . Если необходимо создать ортонормальный базис, то алгоритм должен проверить наличие нулевых векторов в выходных данных и отбросить их, поскольку ни один кратный нулевому вектор не может иметь длину 1. Количество векторов, выведенных алгоритмом, будет тогда размерностью пространства, охватываемого исходными входными данными. ${\displaystyle i}$ ${\displaystyle \mathbf {v} _{i}}$ ${\displaystyle \mathbf {v} _{1},\ldots ,\mathbf {v} _{i-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 }}$

Пример

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

Рассмотрим следующий набор векторов (с обычным скалярным произведением ): ${\displaystyle \mathbb {R} ^{2}}$ $${\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}-\operatorname {proj} _{\mathbf {u} _{1}}(\mathbf {v} _{2})={\begin{bmatrix}2\\2\end{bmatrix}}-\operatorname {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}}.}$$

Проверяем, что векторы и действительно ортогональны: отмечаем, что если скалярное произведение двух векторов равно 0, то они ортогональны. ${\displaystyle \mathbf {u} _{1}}$ ${\displaystyle \mathbf {u} _{2}}$ $${\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,}$$

Для ненулевых векторов мы можем затем нормализовать векторы, разделив их размеры, как показано выше: $${\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 (\mathbb {R} ^{n})^{k}\to (\mathbb {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 \mathbb {R} ^{n}\to \mathbb {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} (\mathbb {R} ^{n})}$ ${\displaystyle O(\mathbb {R} ^{n})}$

Численная стабильность

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

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

Вместо вычисления вектора uk _, как он вычисляется как $${\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 {e} _{k}&={\frac {\mathbf {u} _{k}^{(k-1)}}{\left\|\mathbf {u} _{k}^{(k-1)}\right\|}}\end{aligned}}}$$

Этот метод использовался в предыдущей анимации, когда промежуточный вектор использовался при ортогонализации синего вектора . ${\displaystyle \mathbf {v} '_{3}}$ ${\displaystyle \mathbf {v} _{3}}$

Вот еще одно описание модифицированного алгоритма. Учитывая векторы , на нашем первом шаге мы создаем векторы , удаляя компоненты вдоль направления . В формулах . После этого шага у нас уже есть два наших желаемых ортогональных вектора , а именно , но мы также сделали уже ортогональными к . Затем мы ортогонализируем оставшиеся векторы относительно . Это означает, что мы вычисляем путем вычитания . Теперь мы сохранили векторы, где первые три вектора уже есть , а оставшиеся векторы уже ортогональны к . Как теперь должно быть ясно, на следующем шаге выполняется ортогонализ против . Действуя таким образом, мы находим полный набор ортогональных векторов . Если требуются ортонормированные векторы, то мы нормализуем по ходу дела, так что знаменатели в формулах вычитания превращаются в единицы. ${\displaystyle \mathbf {v} _{1},\mathbf {v} _{2},\dots ,\mathbf {v} _{n}}$ ${\displaystyle \mathbf {v} _{1},\mathbf {v} _{2}^{(1)},\dots ,\mathbf {v} _{n}^{(1)}}$ ${\displaystyle \mathbf {v} _{1}}$ ${\displaystyle \mathbf {v} _{k}^{(1)}:=\mathbf {v} _{k}-{\frac {\langle \mathbf {v} _{k},\mathbf {v} _{1}\rangle }{\langle \mathbf {v} _{1},\mathbf {v} _{1}\rangle }}\mathbf {v} _{1}}$ ${\displaystyle \mathbf {u} _{1},\dots ,\mathbf {u} _{n}}$ ${\displaystyle \mathbf {u} _{1}=\mathbf {v} _{1},\mathbf {u} _{2}=\mathbf {v} _{2}^{(1)}}$ ${\displaystyle \mathbf {v} _{3}^{(1)},\dots ,\mathbf {v} _{n}^{(1)}}$ ${\displaystyle \mathbf {u} _{1}}$ ${\displaystyle \mathbf {u} _{2}=\mathbf {v} _{2}^{(1)}}$ ${\displaystyle \mathbf {v} _{3}^{(2)},\mathbf {v} _{4}^{(2)},\dots ,\mathbf {v} _{n}^{(2)}}$ ${\displaystyle \mathbf {v} _{k}^{(2)}:=\mathbf {v} _{k}^{(1)}-{\frac {\langle \mathbf {v} _{k}^{(1)},\mathbf {u} _{2}\rangle }{\langle \mathbf {u} _{2},\mathbf {u} _{2}\rangle }}\mathbf {u} _{2}}$ ${\displaystyle \mathbf {v} _{1},\mathbf {v} _{2}^{(1)},\mathbf {v} _{3}^{(2)},\mathbf {v} _{4}^{(2)},\dots ,\mathbf {v} _{n}^{(2)}}$ ${\displaystyle \mathbf {u} _{1},\mathbf {u} _{2},\mathbf {u} _{3}}$ ${\displaystyle \mathbf {u} _{1},\mathbf {u} _{2}}$ ${\displaystyle \mathbf {v} _{4}^{(2)},\dots ,\mathbf {v} _{n}^{(2)}}$ ${\displaystyle \mathbf {u} _{3}=\mathbf {v} _{3}^{(2)}}$ ${\displaystyle \mathbf {u} _{1},\dots ,\mathbf {u} _{n}}$

Алгоритм

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

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

Стоимость этого алгоритма асимптотически составляет O( nk ² ) операций с плавающей точкой, где n — размерность векторов. ^[2]

С помощью метода Гаусса

Если строки { v ₁ , ..., v _k } записаны в виде матрицы , то применение метода Гаусса к расширенной матрице даст ортогонализованные векторы вместо . Однако матрицу необходимо привести к форме ступенчатой ​​строки , используя только операцию строки добавления скалярного множителя одной строки к другой. ^[3] Например, принимая , как указано выше, мы имеем ${\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}}}$$

где и, для , — определитель Грама ${\displaystyle D_{0}=1}$ ${\displaystyle j\geq 1}$ ${\displaystyle 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}}.}$$

Обратите внимание, что выражение для является «формальным» определителем, т.е. матрица содержит как скаляры, так и векторы; значение этого выражения определяется как результат разложения сомножителей по строке векторов. ${\displaystyle \mathbf {u} _{k}}$

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

Выражено с помощью геометрической алгебры

Выраженные с использованием обозначений, используемых в геометрической алгебре , ненормализованные результаты процесса Грама-Шмидта могут быть выражены как что эквивалентно выражению с использованием оператора, определенного выше. Результаты могут быть эквивалентно выражены как ^[4] , что тесно связано с выражением с использованием детерминантов выше. $${\displaystyle \mathbf {u} _{k}=\mathbf {v} _{k}-\sum _{j=1}^{k-1}(\mathbf {v} _{k}\cdot \mathbf {u} _{j})\mathbf {u} _{j}^{-1}\ ,}$$ ${\displaystyle \operatorname {proj} }$ $${\displaystyle \mathbf {u} _{k}=\mathbf {v} _{k}\wedge \mathbf {v} _{k-1}\wedge \cdot \cdot \cdot \wedge \mathbf {v} _{1}(\mathbf {v} _{k-1}\wedge \cdot \cdot \cdot \wedge \mathbf {v} _{1})^{-1},}$$

Альтернативы

Другие алгоритмы ортогонализации используют преобразования Хаусхолдера или вращения Гивенса . Алгоритмы, использующие преобразования Хаусхолдера, более стабильны, чем стабилизированный процесс Грама–Шмидта. С другой стороны, процесс Грама–Шмидта производит 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}$

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

Сложность выполнения

Ортогонализация Грама-Шмидта может быть выполнена за сильно полиномиальное время . Анализ времени выполнения аналогичен анализу исключения Гаусса . ^{[6] : 40}

Смотрите также

• Линейная алгебра
• Рекурсия
• Ортогональность (математика)

Ссылки

1. Чейни, Уорд; Кинкейд, Дэвид (2009). Линейная алгебра: теория и приложения. Садбери, Массачусетс: Джонс и Бартлетт. стр. 544, 558. ISBN 978-0-7637-5020-6.
2. Голуб и Ван Лоан 1996, §5.2.8.
3. Pursell, Lyle; Trimble, SY (1 января 1991 г.). «Ортогонализация Грама-Шмидта методом исключения Гаусса». The American Mathematical Monthly . 98 (6): 544–549. doi :10.2307/2324877. JSTOR  2324877.
4. Доран, Крис; Ласенби, Энтони (2007). Геометрическая алгебра для физиков . Cambridge University Press. стр. 124. ISBN 978-0-521-71595-9.
5. Pursell, Yukihiro; et al. (2011). "Расчеты электронных состояний кремниевой нанопроволоки с 100 000 атомов на компьютере K из первых принципов". Труды Международной конференции 2011 года по высокопроизводительным вычислениям, сетевым технологиям, хранению и анализу . С. 1:1–1:11. doi :10.1145/2063384.2063386. ISBN 9781450307710. S2CID  14316074.
6. Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация, Алгоритмы и комбинаторика, том. 2 (2-е изд.), Springer-Verlag, Берлин, номер документа : 10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, г-н  1261419

Примечания

1. В комплексном случае это предполагает, что скалярное произведение линейно по первому аргументу и сопряженно-линейно по второму. В физике более распространенным соглашением является линейность по второму аргументу, в этом случае мы определяем $${\displaystyle \operatorname {proj} _{\mathbf {u} }(\mathbf {v} )={\frac {\langle \mathbf {u} ,\mathbf {v} \rangle }{\langle \mathbf {u} ,\mathbf {u} \rangle }}\,\mathbf {u} .}$$

Источники

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

Внешние ссылки

• Математический портал

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