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 $\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 $\{{\bar {v_{0}}},\ldots {\bar {v}}_{n-1}\}$ och låt ${\underline {f}}_{0}=\left\{{\frac {1}{|{\bar {v}}_{0}|}}{\bar {v}}_{0}\right\}$.

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

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

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