Gram-Schmidt reikniritið

Úr Wikipediu, frjálsa alfræðiritinu
Stökkva á: flakk, leita
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ð[breyta]

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ð {u1, …, uk} er þá mengi þverstæðu vigrana, og stöðluðu vigrarnir {e1, …, ek} mynda þverstaðlaðan grunn fyrir hlutrúmið.