Gram-Schmidt reikniritið

Fyrstu tvö skref Gram-Schmidt reikniritsins.

Gram-Schmidt reikniritið er mikið notað reiknirit í línulegri algebru sem notað er til þess að þverstaðla mengi vigra í gefnu innfeldisrúmi, oftast Evklíðska rúmið $\mathbb {R} ^{n}$. Reikniritið tekur endanlegt, línulega óháð mengi vigra $S=\{v_{1},...,v_{n}\}$ og skilar út þverstöðluðu mengi $S'=\{u_{1},...,u_{n}\}$ sem spannar sama hlutrúmið.

Reikniritið er nefnt eftir Jørgen Pedersen Gram og Erhard Schmidt, en það kom áður fram í verkum Laplace og Cauchy. Í Lie-grúpufræði er aðferðin útvíkkuð með Iwasawa þáttun.

Beiting Gram-Schmidt reikniritsins á dálkvigra fylkis af fullri stétt gefur QR-þáttun þess.

Reikniritið

Við skilgreinum ofanvarpsvirkjann sem:

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

Hann varpar vigrinum v hornrétt á vigurinn u.

Þá virkar reikniritið þannig:

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

Mengið {u₁, …, u_k} er þá mengi þverstæðu vigrana, og stöðluðu vigrarnir {e₁, …, e_k} mynda þverstaðlaðan grunn fyrir hlutrúmið.