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.