Gram–Schmidts ortogonaliseringsprocess

Gram–Schmidts ortogonaliseringsprocess är en algoritm för att generera en ortonormerad bas (ortogonal bas med norm 1) ur en given mängd vektorer tillhörande ett inre produktrum med en skalärprodukt ${\displaystyle \langle \cdot ,\cdot \rangle }$.

Metoden är uppkallad efter Erhard Schmidt och Jørgen Pedersen Gram, men dök upp tidigare i verk av Laplace och Cauchy. Iwasawafaktorisering är en generalisering av metoden.

Algoritmen

Steg 0: Ta bort vektorer ur den givna mängden till dess att mängden är linjärt oberoende. Antag att denna eventuellt ändrade mängd vektorer är ${\displaystyle \{{\bar {v_{0}}},\ldots {\bar {v}}_{n-1}\}}$ och låt ${\displaystyle {\underline {f}}_{0}=\left\{{\frac {1}{|{\bar {v}}_{0}|}}{\bar {v}}_{0}\right\}}$.

Steg i (i = ${\displaystyle 1,2,\ldots }$): Antag att en bas ${\displaystyle {\underline {f}}_{i-1}=\{f_{0},\ldots f_{i-1}\}}$ har konstruerats genom att ha använt vektorerna ${\displaystyle {\bar {v}}_{0}\ldots {\bar {v}}_{i-1}}$. Om ${\displaystyle i=n}$ så är algoritmen färdig. Låt ${\displaystyle {\bar {u}}={\bar {v}}_{i}-\sum _{k=0}^{i-1}{\frac {1}{|{\bar {v}}_{i-1}||{\bar {f}}_{k}|}}{\bar {f}}_{k}}$ och sätt ${\displaystyle {\underline {f}}_{i}={\underline {f}}_{i-1}\cup \{{\frac {1}{|{\bar {u}}|}}{\bar {u}}\}}$.

Här har ${\displaystyle |{\bar {v}}|}$ använts för att beteckna ${\displaystyle {\sqrt {\langle {\bar {v}},{\bar {v}}\rangle }}}$.

Algoritmen ger som resultat den ortonormerade mängden ${\displaystyle {\underline {f}}_{n}=\{{\bar {f}}_{0},\ldots {\bar {f}}_{n}\}}$. Att algoritmen vid steg i, ${\displaystyle i>0}$ kräver en linjärt oberoende mängd vektorer inses vid steget ${\displaystyle {\bar {u}}={\bar {v}}_{i}-\sum _{k=0}^{i-1}{\frac {1}{|{\bar {v}}_{i-1}||{\bar {f}}_{k}|}}{\bar {f}}_{k}}$. Om ${\displaystyle {\bar {v}}_{i}}$ här är linjärt beroende med ${\displaystyle {\underline {f}}_{i-1}}$, så är ${\displaystyle {\bar {u}}=0\Leftrightarrow |{\bar {u}}|=0}$, och uttrycket ${\displaystyle {\underline {f}}_{i}={\underline {f}}_{i-1}\cup \{{\frac {1}{|{\bar {u}}|}}{\bar {u}}\}}$ saknar mening.