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 $⟨\cdot ,\cdot ⟩$.

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{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{𝐯}𝐱=\frac{⟨𝐱,𝐯⟩}{⟨𝐯,𝐯⟩}𝐯.$

La $v_1,\mathrm{..}{v}_n$ vera resulatet av algoritmen, altså den ortonormale basisen. La $x_1,\mathrm{..},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-pro{j}_{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-pro{j}_{v_1}{x}_3+pro{j}_{v_2}{x}_3$. Slik held algoritmen fram til ein har konstruert ein ortonormal basis.

Heile algoritmen kan oppsummerast stegvis som

	${𝐯}_1={𝐱}_1,$		${𝐞}_1=\frac{{𝐯}_1}{||{𝐯}_1||}$
	${𝐯}_2={𝐱}_2-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐯}_1}{𝐱}_2,$		${𝐞}_2=\frac{{𝐯}_2}{||{𝐯}_2||}$
	${𝐯}_3={𝐱}_3-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐯}_1}{𝐱}_3-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐯}_2}{𝐱}_3,$		${𝐞}_3=\frac{{𝐯}_3}{||{𝐯}_3||}$
	$⋮$		$⋮$
	${𝐯}_k={𝐱}_k-\sum _{j=1}^{k-1}{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐯}_j}{𝐱}_k,$		${𝐞}_k=\frac{{𝐯}_k}{||{𝐯}_k||}$

For kvart steg vert vektoren $v_k$normalisert.

Kjelder

• Denne artikkelen bygger på «Gram–Schmidts ortogonaliseringsprocess» frå Mal:Wikipedia-utgåve, den 8. september 2019.