Gram–Schmidts ortogonaliseringsprossess

Gram–Schmidts ortogonaliseringsprossess er ein algoritme for å generera ein ortonormalisert basis (ortogonal basis med norm 1) frå ei gjeven mengde vektorar knytte til eit indreproduktrom med eit gjeve skalarprodukt ${\displaystyle \langle \cdot ,\cdot \rangle }$.

Metoden vart oppkalla etter Erhard Schmidt og Jørgen Pedersen Gram, sjølv om han tidlegare vart teken i bruk i verka til Laplace og Cauchy.

Han vert nytta i dei høva ein ønskjer ein ortonormal/ortogonal basis. Å finna QR-faktoriseringa av ei matrise er i røynda Gram-Schmidts ortogonaliseringsprossess.

Algoritme

Algoritmen er basert på definisjonen av projeksjonar. Ein projeksjon er definert som;

$\mathrm {proj} _{\mathbf {v} }\,\mathbf {x} ={\langle \mathbf {x} ,\mathbf {v} \rangle \over \langle \mathbf {v} ,\mathbf {v} \rangle }\mathbf {v} .$

La $v_{1},..v_{n}$ vera resulatet av algoritmen, altså den ortonormale basisen. La $x_{1},..,x_{n}$ vera vektorane det skal konstruerast ein ortonormal basis av. Ein let $v_{1}=x_{1}$ og normaliserer vektoren. Vidare vert vektoren $x_{2}$ projektert på vektoren $v_{1}$. Ut i frå dette vert $v_{2}$vektoren som står ortogonalt på denne projeksjonen, altså $v_{2}=x_{2}-proj_{v_{1}}x_{2}=x_{2}-{\frac {x_{2}\cdot v_{1}}{v_{1}\cdot v_{1}}}v_{1}$. Vidare vert $x_{3}$ projektert på flata utspend av $v_{1}$ og $v_{2}$. Vektoren som står ortogonalt på denne flata er $v_{3}$. Med andre ord så vert $v_{3}=x_{3}-proj_{v_{1}}x_{3}+proj_{v_{2}}x_{3}$. Slik held algoritmen fram til ein har konstruert ein ortonormal basis.

Heile algoritmen kan oppsummerast stegvis som

	$\mathbf {v} _{1}=\mathbf {x} _{1},$		$\mathbf {e} _{1}={\mathbf {v} _{1} \over ||\mathbf {v} _{1}||}$
	$\mathbf {v} _{2}=\mathbf {x} _{2}-\mathrm {proj} _{\mathbf {v} _{1}}\,\mathbf {x} _{2},$		$\mathbf {e} _{2}={\mathbf {v} _{2} \over ||\mathbf {v} _{2}||}$
	$\mathbf {v} _{3}=\mathbf {x} _{3}-\mathrm {proj} _{\mathbf {v} _{1}}\,\mathbf {x} _{3}-\mathrm {proj} _{\mathbf {v} _{2}}\,\mathbf {x} _{3},$		$\mathbf {e} _{3}={\mathbf {v} _{3} \over ||\mathbf {v} _{3}||}$
	$\vdots$		$\vdots$
	$\mathbf {v} _{k}=\mathbf {x} _{k}-\sum _{j=1}^{k-1}\mathrm {proj} _{\mathbf {v} _{j}}\,\mathbf {x} _{k},$		$\mathbf {e} _{k}={\mathbf {v} _{k} \over ||\mathbf {v} _{k}||}$

For kvart steg vert vektoren $v_{k}$normalisert.

Kjelder

• Denne artikkelen bygger på «Gram–Schmidts ortogonaliseringsprocess» frå Wikipedia på svensk, den 8. september 2019.