Gram-Schmidt-processen

Inden for Lineær algebra er Gram-Schmidt-processen en algoritme til at ortonormalisere et endeligt set af lineært uafhængige vektorer inden for et indre produkt-rum, ofte for Rⁿ udstyret med skalarproduktet.

Processen er opkaldt efter den danske matematiker Jørgen Pedersen Gram og tysk-baltiske matematiker Erhard Schmidt, selvom den tidligere har været taget i brug af Laplace.

Gram–Schmidt processen

Gram-Schmidt processen bygger på ortogonale projektioner

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

hvor ${\displaystyle \langle \mathbf {u} ,\mathbf {v} \rangle }$ betegner det Indre produkt af vektorerne u og v. Projektionen projicerer vektoreren v ned på u og skaber da en ny vektor med samme retning sum u, men med den projicerede længde. Følgende betegner Gram-Schhmidt processen:

${\displaystyle {\begin{aligned}\mathbf {u} _{1}&=\mathbf {v} _{1},&\mathbf {e} _{1}&={\mathbf {u} _{1} \over \|\mathbf {u} _{1}\|}\\\mathbf {u} _{2}&=\mathbf {v} _{2}-\mathrm {proj} _{\mathbf {u} _{1}}\,(\mathbf {v} _{2}),&\mathbf {e} _{2}&={\mathbf {u} _{2} \over \|\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}&={\mathbf {u} _{3} \over \|\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}&={\mathbf {u} _{k} \over \|\mathbf {u} _{k}\|}.\end{aligned}}}$

hvor vektorerne v₁...v_k betegner inputtet bestående af lineært uafhængige vektorer og e₁...e_k de resulterende ortonormaliserede vektorer. Yderligere er vektorerne u₁...u_k også en ortogonal mængde, men uden garanti for at have længden 1.

Eksempel

Euklidisk rum

Som Eksempel ses på vektorrummet R⁴ udstyret med skalarproduktet.

Lad

${\displaystyle \mathbf {v} _{1}={\begin{pmatrix}1\\1\\1\\1\end{pmatrix}},\mathbf {v} _{2}={\begin{pmatrix}1\\1\\0\\0\end{pmatrix}},\mathbf {v} _{3}={\begin{pmatrix}3\\1\\1\\-1\end{pmatrix}}}$

Det er givet at v₁, v₂ og v₃ er lineært uafhængige. Gram-Schmidt udføres:

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

${\displaystyle \mathbf {u} _{2}=\mathbf {v} _{2}-\mathrm {proj} _{\mathbf {u} _{1}}\,(\mathbf {v} _{2})={\begin{pmatrix}1\\1\\0\\0\end{pmatrix}}-\mathrm {proj} _{\begin{pmatrix}1\\1\\1\\1\end{pmatrix}}\,{\begin{pmatrix}1\\1\\0\\0\end{pmatrix}}={\begin{pmatrix}1\\1\\0\\0\end{pmatrix}}-{1 \over 2}{\begin{pmatrix}1\\1\\1\\1\end{pmatrix}}={\begin{pmatrix}1/2\\1/2\\-1/2\\-1/2\end{pmatrix}}}$

${\displaystyle \mathbf {u} _{3}=\mathbf {v} _{3}-\mathrm {proj} _{\mathbf {u} _{1}}\,(\mathbf {v} _{3})-\mathrm {proj} _{\mathbf {u} _{2}}\,(\mathbf {v} _{3})={\begin{pmatrix}3\\1\\1\\-1\end{pmatrix}}-\mathrm {proj} _{\begin{pmatrix}1\\1\\1\\1\end{pmatrix}}\,{\begin{pmatrix}3\\1\\1\\-1\end{pmatrix}}-\mathrm {proj} _{\begin{pmatrix}1\\1\\0\\0\end{pmatrix}}\,{\begin{pmatrix}3\\1\\1\\-1\end{pmatrix}}={\begin{pmatrix}3\\1\\1\\-1\end{pmatrix}}-{\begin{pmatrix}1\\1\\1\\1\end{pmatrix}}-2{\begin{pmatrix}1/2\\1/2\\-1/2\\-1/2\end{pmatrix}}={\begin{pmatrix}1\\-1\\1\\-1\end{pmatrix}}}$

Det kan tjekkes om vektorerne er ortogonale ved at beregne de indbyrdes skalarprodukter. Eksempelvis u₁ og u₃:

${\displaystyle \langle \mathbf {u} _{1},\mathbf {u} _{3}\rangle =\left\langle {\begin{pmatrix}1\\1\\1\\1\end{pmatrix}},{\begin{pmatrix}1\\-1\\1\\-1\end{pmatrix}}\right\rangle =1-1+1-1=0,}$

Vektorerne er ortogonale da deres indre produkt er 0.

For at finde de normaliserede vektorer e₁, e₂ og e₃ gøres følgende:

${\displaystyle \mathbf {e} _{1}={\mathbf {u} _{1} \over \|\mathbf {u} _{1}\|}={1 \over 2}{\begin{pmatrix}1\\1\\1\\1\end{pmatrix}}={\begin{pmatrix}1/2\\1/2\\1/2\\1/2\end{pmatrix}}}$

${\displaystyle \mathbf {e} _{2}={\mathbf {u} _{2} \over \|\mathbf {u} _{2}\|}={\begin{pmatrix}1/2\\1/2\\-1/2\\-1/2\end{pmatrix}}}$

${\displaystyle \mathbf {e} _{3}={\mathbf {u} _{3} \over \|\mathbf {u} _{3}\|}={1 \over 2}{\begin{pmatrix}1\\-1\\1\\-1\end{pmatrix}}}$

Reference

• Thomsen, Jesper Funnch (2020), Lineær algebra, Aarhus Universitet, Institut for matematik
• https://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process