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

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

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

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

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

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

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

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

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

Данный $k$ векторы $\mathbf {v} _{1},\ldots ,\mathbf {v} _{k}$ процесс Грама – Шмидта определяет векторы $\mathbf {u} _{1},\ldots ,\mathbf {u} _{k}$ следующее: $${\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}}$$

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

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

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

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

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

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

Пример

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

Рассмотрим следующий набор векторов в $\mathbb {R} ^{2}$ (с обычным внутренним продуктом ) $$S=\left\{\mathbf {v} _{1}={\begin{bmatrix}3\\1\end{bmatrix}},\mathbf {v} _{2}={\begin{bmatrix}2\\2\end{bmatrix}}\right\}.$$

Теперь выполните операцию Грама – Шмидта, чтобы получить ортогональный набор векторов: $$\mathbf {u} _{1}=\mathbf {v} _{1}={\begin{bmatrix}3\\1\end{bmatrix}}$$ $$\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}}.$$

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

Для ненулевых векторов мы можем затем нормализовать векторы, разделив их размеры, как показано выше: $$\mathbf {e} _{1}={\frac {1}{\sqrt {10}}}{\begin{bmatrix}3\\1\end{bmatrix}}$$ $$\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}}.$$

Характеристики

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

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

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

Позволять $g\colon \mathbb {R} ^{n}\to \mathbb {R} ^{n}$ быть ортогональными (относительно заданного скалярного произведения). Тогда у нас есть $$\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)$$

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

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

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

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

Вместо вычисления uk _как вектора $$\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}),$$ оно рассчитывается как $${\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}}$$

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

Вот еще одно описание модифицированного алгоритма. Учитывая векторы $\mathbf {v} _{1},\mathbf {v} _{2},\dots ,\mathbf {v} _{n}$, на первом этапе мы создаем векторы $\mathbf {v} _{1},\mathbf {v} _{2}^{(1)},\dots ,\mathbf {v} _{n}^{(1)}$путем удаления компонентов в направлении $\mathbf {v} _{1}$. В формулах $\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}$. После этого шага у нас уже есть два желаемых ортогональных вектора. $\mathbf {u} _{1},\dots ,\mathbf {u} _{n}$, а именно $\mathbf {u} _{1}=\mathbf {v} _{1},\mathbf {u} _{2}=\mathbf {v} _{2}^{(1)}$, но мы также сделали $\mathbf {v} _{3}^{(1)},\dots ,\mathbf {v} _{n}^{(1)}$ уже ортогонально $\mathbf {u} _{1}$. Далее мы ортогонализуем оставшиеся векторы относительно $\mathbf {u} _{2}=\mathbf {v} _{2}^{(1)}$. Это означает, что мы вычисляем $\mathbf {v} _{3}^{(2)},\mathbf {v} _{4}^{(2)},\dots ,\mathbf {v} _{n}^{(2)}$ путем вычитания $\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}$. Теперь мы сохранили векторы $\mathbf {v} _{1},\mathbf {v} _{2}^{(1)},\mathbf {v} _{3}^{(2)},\mathbf {v} _{4}^{(2)},\dots ,\mathbf {v} _{n}^{(2)}$ где первые три вектора уже есть $\mathbf {u} _{1},\mathbf {u} _{2},\mathbf {u} _{3}$ а остальные векторы уже ортогональны $\mathbf {u} _{1},\mathbf {u} _{2}$. Теперь должно быть ясно, что следующим шагом будет ортогонализация $\mathbf {v} _{4}^{(2)},\dots ,\mathbf {v} _{n}^{(2)}$ против $\mathbf {u} _{3}=\mathbf {v} _{3}^{(2)}$. Действуя таким образом, находим полный набор ортогональных векторов $\mathbf {u} _{1},\dots ,\mathbf {u} _{n}$. Если желательны ортонормированные векторы, то нормализуем по ходу дела, чтобы знаменатели в формулах вычитания превратились в единицы.

Алгоритм

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

function U = gramschmidt(V)
    [n, k] = size(V);
    U = zeros(n,k);
    U(:,1) = V(:,1) / norm(V(:,1));
    for i = 2:k
        U(:,i) = V(:,i);
        for j = 1:i-1
            U(:,i) = U(:,i) - (U(:,j)'*U(:,i)) * U(:,j);
        end
        U(:,i) = U(:,i) / norm(U(:,i));
    end
end

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

Через исключение Гаусса

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

И приведение этого к форме эшелона строк дает $$\left[{\begin{array}{rr|rr}1&.8&.3&.1\\0&1&-.25&.75\end{array}}\right]$$

Тогда нормированные векторы $$\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}}$$ $$\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}},$$ как в примере выше.

Они определяют формулу

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

$$\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}}$$

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

$$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}}.$$

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

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

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

Выраженные с использованием обозначений, используемых в геометрической алгебре , ненормализованные результаты процесса Грама – Шмидта могут быть выражены как $$\mathbf {u} _{k}=\mathbf {v} _{k}-\sum _{j=1}^{k-1}(\mathbf {v} _{k}\cdot \mathbf {u} _{j})\mathbf {u} _{j}^{-1}\ ,$$ что эквивалентно выражению, использующему $\operatorname {proj}$ оператор, определенный выше. Результаты эквивалентно могут быть выражены как $$\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},$$ что тесно связано с выражением с использованием определителей, приведенным выше.

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

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

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

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

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

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

См. также

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

Источники

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

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

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