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

${\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{𝐮}(𝐯)=\frac{⟨𝐯,𝐮⟩}{⟨𝐮,𝐮⟩}𝐮,$

hvor $⟨𝐮,𝐯⟩$ 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:

$\begin{array}{cccc}{𝐮}_1& ={𝐯}_1,& {𝐞}_1& =\frac{{𝐮}_1}{\Vert {𝐮}_1\Vert }\\ {𝐮}_2& ={𝐯}_2-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_1}({𝐯}_2),& {𝐞}_2& =\frac{{𝐮}_2}{\Vert {𝐮}_2\Vert }\\ {𝐮}_3& ={𝐯}_3-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_1}({𝐯}_3)-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_2}({𝐯}_3),& {𝐞}_3& =\frac{{𝐮}_3}{\Vert {𝐮}_3\Vert }\\ {𝐮}_4& ={𝐯}_4-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_1}({𝐯}_4)-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_2}({𝐯}_4)-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_3}({𝐯}_4),& {𝐞}_4& =\frac{{𝐮}_4}{\Vert {𝐮}_4\Vert }\\ & ⋮& & ⋮\\ {𝐮}_k& ={𝐯}_k-\sum _{j=1}^{k-1}{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_j}({𝐯}_k),& {𝐞}_k& =\frac{{𝐮}_k}{\Vert {𝐮}_k\Vert }.\end{array}$

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

${𝐯}_1=\left(\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right),{𝐯}_2=\left(\begin{array}{c}1\\ 1\\ 0\\ 0\end{array}\right),{𝐯}_3=\left(\begin{array}{c}3\\ 1\\ 1\\ -1\end{array}\right)$

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

${𝐮}_1={𝐯}_1=\left(\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right)$

${𝐮}_2={𝐯}_2-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_1}({𝐯}_2)=\left(\begin{array}{c}1\\ 1\\ 0\\ 0\end{array}\right)-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{\left(\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right)}\left(\begin{array}{c}1\\ 1\\ 0\\ 0\end{array}\right)=\left(\begin{array}{c}1\\ 1\\ 0\\ 0\end{array}\right)-\frac{1}{2}\left(\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right)=\left(\begin{array}{c}1/2\\ 1/2\\ -1/2\\ -1/2\end{array}\right)$

${𝐮}_3={𝐯}_3-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_1}({𝐯}_3)-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_2}({𝐯}_3)=\left(\begin{array}{c}3\\ 1\\ 1\\ -1\end{array}\right)-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{\left(\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right)}\left(\begin{array}{c}3\\ 1\\ 1\\ -1\end{array}\right)-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{\left(\begin{array}{c}1\\ 1\\ 0\\ 0\end{array}\right)}\left(\begin{array}{c}3\\ 1\\ 1\\ -1\end{array}\right)=\left(\begin{array}{c}3\\ 1\\ 1\\ -1\end{array}\right)-\left(\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right)-2\left(\begin{array}{c}1/2\\ 1/2\\ -1/2\\ -1/2\end{array}\right)=\left(\begin{array}{c}1\\ -1\\ 1\\ -1\end{array}\right)$

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

$⟨{𝐮}_1,{𝐮}_3⟩=⟨\left(\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right),\left(\begin{array}{c}1\\ -1\\ 1\\ -1\end{array}\right)⟩=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:

${𝐞}_1=\frac{{𝐮}_1}{\Vert {𝐮}_1\Vert }=\frac{1}{2}\left(\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right)=\left(\begin{array}{c}1/2\\ 1/2\\ 1/2\\ 1/2\end{array}\right)$

${𝐞}_2=\frac{{𝐮}_2}{\Vert {𝐮}_2\Vert }=\left(\begin{array}{c}1/2\\ 1/2\\ -1/2\\ -1/2\end{array}\right)$

${𝐞}_3=\frac{{𝐮}_3}{\Vert {𝐮}_3\Vert }=\frac{1}{2}\left(\begin{array}{c}1\\ -1\\ 1\\ -1\end{array}\right)$

Reference

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