Gram-Schmidt reikniritið

Úr Wikipediu, frjálsa alfræðiritinu

Fyrstu tvö skref Gram-Schmidt reikniritsins.
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 = {v1,...,vn} og skilar út þverstöðluðu mengi S' = {u1,...,un} 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.

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


Greinar í stærðfræði tengdar línulegri algebru

Vigur | Lína | Fylki | Plan | Háplan | Vigurrúm | Innfeldisrúm | Línuleg spönn | Línuleg vörpun | Línuleg jöfnuhneppi | Línulegt óhæði | Línuleg samantekt | Línulegur grunnur | Dálkarúm | Raðarúm | Þverlægni | Eigingildi | Eiginvigur | Eiginrúm | Kennimargliða | Útfeldi | Krossfeldi | Innfeldi | Ákveður | Bylta | Fylkjaliðun (LU-þáttun, QR-þáttun) | Hornalínugeranleiki | Hjáþættir | Gauß-eyðing | Gauß-Jordan eyðing | Gram-Schmidt reikniritið | Regla Cramers | Rófsetningin