Процес ортогоналізації Грама — Шмідта на трьох лінійно незалежних, неортогональних векторах Процес Грама - Шмідта — найвідоміший алгоритм ортогоналізації , в якому за лінійно-незалежною системою v 1 , v 2 , … , v k {\displaystyle \mathbf {v} _{1},\mathbf {v} _{2},\dots ,\mathbf {v} _{k}} будується ортогональна система u 1 , u 2 , … , u k {\displaystyle \mathbf {u} _{1},\mathbf {u} _{2},\dots ,\mathbf {u} _{k}} така, що кожний вектор u i {\displaystyle \mathbf {u} _{i}} лінійно виражається через v 1 , v 2 , … , v i {\displaystyle \mathbf {v} _{1},\mathbf {v} _{2},\dots ,\mathbf {v} _{i}} , тобто матриця переходу від { v i } {\displaystyle \{\mathbf {v} _{i}\}} до { u i } {\displaystyle \{\mathbf {u} _{i}\}} ― верхня трикутна матриця .
Можна пронормувати систему { u i } {\displaystyle \{\mathbf {u} _{i}\}} і зробити, щоб діагональні елементи матриці переходу були додатніми; ці умови однозначно визначають систему { u i } {\displaystyle \{\mathbf {u} _{i}\}} та матрицю переходу.
Процес Грама — Шмідта застосований до матриці з лінійно-незалежними стовпцями є QR розкладом матриці (розклад на ортогональну і верхню трикутну матрицю з додатніми діагональними елементами).
Перші 2 кроки ортогоналізації Визначимо ортогонально-проєкційний оператор
p r o j u v = ⟨ u , v ⟩ ⟨ u , u ⟩ u = u u ⊤ ⟨ u , u ⟩ ⋅ v = e e ⊤ ⋅ v , e = u ‖ u ‖ , {\displaystyle \mathrm {proj} _{\mathbf {u} }\,\mathbf {v} ={\langle \mathbf {u,v} \rangle \over \langle \mathbf {u,u} \rangle }\mathbf {u} ={\mathbf {uu^{\top }} \over \langle \mathbf {u,u} \rangle }\cdot \mathbf {v} =\mathbf {ee^{\top }} \cdot \mathbf {v} ,\qquad \mathbf {e} ={\mathbf {u} \over \|\mathbf {u} \|},} де <u , v > означає скалярний добуток векторів u and v . Цей оператор проектує вектор v ортогонально на вектор u .
Приймемо u 1 = v 1 {\displaystyle \mathbf {u} _{1}=\mathbf {v} _{1}} та запишемо рекурсивну формулу
u i = v i − ∑ j = 1 i − 1 ⟨ v i , u j ⟩ ⟨ u j , u j ⟩ u j = v i − ( ∑ j = 1 i − 1 e j e j ⊤ ) v i . {\displaystyle \mathbf {u} _{i}=\mathbf {v} _{i}-\sum _{j=1}^{i-1}{\frac {\langle \mathbf {v} _{i},\mathbf {u} _{j}\rangle }{\langle \mathbf {u} _{j},\mathbf {u} _{j}\rangle }}\mathbf {u} _{j}=\mathbf {v} _{i}-{\bigg (}\sum _{j=1}^{i-1}\mathbf {e} _{j}\mathbf {e} _{j}^{\top }{\bigg )}\mathbf {v} _{i}.} Нормуючи вектори u i {\displaystyle \mathbf {u} _{i}} , отримаємо ортонормовану систему о { e i } {\displaystyle \{\mathbf {e} _{i}\}} .
Геометричний зміст процесу в тому, що вектор u i {\displaystyle \mathbf {u} _{i}} є проєкцією вектора v i {\displaystyle \mathbf {v} _{i}} на перпендикуляр до лінійної оболонки векторів v 1 , … , v i − 1 . {\displaystyle \mathbf {v} _{1},\dots ,\mathbf {v} _{i-1}.}
Для кожного i {\displaystyle \ i} лінійні оболонки систем v 1 , … , v i {\displaystyle \mathbf {v} _{1},\dots ,\mathbf {v} _{i}} та u 1 , … , u i {\displaystyle \mathbf {u} _{1},\dots ,\mathbf {u} _{i}} збігаються. Добуток довжин u i {\displaystyle \mathbf {u} _{i}} дорівнює об'єму паралелепіпеда , побудованого на векторах системи { v i } {\displaystyle \{\mathbf {v} _{i}\}} , як на ребрах. Коли процес втілено на комп'ютері, вектори u k {\displaystyle \mathbf {u} _{k}} часто не точно ортогональні, через похибки заокруглювання. Для процесу Грама — Шмідта у вигляді описаному вище (іноді згадуваному як «класичний Грам — Шмідт») ця втрата ортогональності особливо шкідлива; кажуть, що (класичний) процес Грама — Шмідта числово нестійкий.
Процес Грама — Шмідта можна стабілізувати завдяки маленькій зміні; цю версію іноді згадують як модифікований Грам — Шмідт . Цей підхід дає той самий результат що й оригінальна формула в точній арифметиці і вводить менші похибки в арифметиці скінченної точності. Замість того, щоб обчислювати вектор u k як
u k = v k − p r o j u 1 ( v k ) − p r o j u 2 ( v k ) − ⋯ − p r o j u k − 1 ( v k ) , {\displaystyle \mathbf {u} _{k}=\mathbf {v} _{k}-\mathrm {proj} _{\mathbf {u} _{1}}\,(\mathbf {v} _{k})-\mathrm {proj} _{\mathbf {u} _{2}}\,(\mathbf {v} _{k})-\cdots -\mathrm {proj} _{\mathbf {u} _{k-1}}\,(\mathbf {v} _{k}),} його обчислюють як
u k ( 1 ) = v k − p r o j u 1 ( v k ) , u k ( 2 ) = u k ( 1 ) − p r o j u 2 ( u k ( 1 ) ) , ⋮ u k ( k − 2 ) = u k ( k − 3 ) − p r o j u k − 2 ( u k ( k − 3 ) ) , u k ( k − 1 ) = u k ( k − 2 ) − p r o j u k − 1 ( u k ( k − 2 ) ) . {\displaystyle {\begin{aligned}\mathbf {u} _{k}^{(1)}&=\mathbf {v} _{k}-\mathrm {proj} _{\mathbf {u} _{1}}\,(\mathbf {v} _{k}),\\\mathbf {u} _{k}^{(2)}&=\mathbf {u} _{k}^{(1)}-\mathrm {proj} _{\mathbf {u} _{2}}\,(\mathbf {u} _{k}^{(1)}),\\&\,\,\,\vdots \\\mathbf {u} _{k}^{(k-2)}&=\mathbf {u} _{k}^{(k-3)}-\mathrm {proj} _{\mathbf {u} _{k-2}}\,(\mathbf {u} _{k}^{(k-3)}),\\\mathbf {u} _{k}^{(k-1)}&=\mathbf {u} _{k}^{(k-2)}-\mathrm {proj} _{\mathbf {u} _{k-1}}\,(\mathbf {u} _{k}^{(k-2)}).\end{aligned}}} Кожен крок знаходить вектор u k ( i ) {\displaystyle \mathbf {u} _{k}^{(i)}} ортогональний до u k ( i − 1 ) {\displaystyle \mathbf {u} _{k}^{(i-1)}} . Таким чином, u k ( i ) {\displaystyle \mathbf {u} _{k}^{(i)}} також ортогональний похибкам введеним під час обчислення u k ( i − 1 ) {\displaystyle \mathbf {u} _{k}^{(i-1)}} .