Gram-Schmidts ortogonaliseringsprocess

Från Wikipedia
Hoppa till: navigering, sök

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[redigera | redigera wikitext]

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.