Gram-Schmidt proces

Gram - Schmidt - processen transformerer en sekvens af lineært uafhængige vektorer til et ortonormalt system af vektorer og på en sådan måde, at hver vektor er en lineær kombination af . ${\displaystyle \mathbf {a} _{1},\;\ldots ,\;\mathbf {a} _{n))$ ${\displaystyle \mathbf {e} _{1},\;\ldots ,\;\mathbf {e} _{n))$ $\mathbf{e}_j$ ${\mathbf {a}}_{1},\;\ldots ,\;{\mathbf {a}}_{j}$

Den klassiske Gram-Schmidt-proces

Algoritme

Lad der være lineært uafhængige vektorer og lad være projektionsoperator for en vektor på en vektor defineret som ${\displaystyle \mathbf {a} _{1},\;\ldots ,\;\mathbf {a} _{n))$ $\mathbf {proj} _{\mathbf {b} }\,\mathbf {a}$ ${\mathbf {a}}$ ${\mathbf {b}}$

{\mathbf {proj}}_{{{\mathbf {b}}}}\,{\mathbf {a}}={\langle {\mathbf {a}},{\mathbf {b}}\rangle \ over \langle {\mathbf {b)),{\mathbf {b}}\rangle }{\mathbf {b)),

hvor er skalarproduktet af vektorer og . $\langle {\mathbf {a}},{\mathbf {b}}\rangle$ ${\mathbf {a}}$ ${\mathbf {b}}$

Den klassiske Gram-Schmidt-proces udføres som følger:

{\begin{array}{lclr}\mathbf {b} _{1}&=&\mathbf {a} _{1}&(1)\\\mathbf {b} _{2}&= &\mathbf {a} _{2}-\mathbf {proj} _{\mathbf {b} _{1}}\,\mathbf {a} _{2}&(2)\\\mathbf {b} _{3}&=&\mathbf {a} _{3}-\mathbf {proj} _{\mathbf {b} _{1}}\,\mathbf {a} _{3}-\mathbf {proj } _{\mathbf {b} _{2}}\,\mathbf {a} _{3}&(3)\\&\dots &&\\\mathbf {b} _{n}&=&\mathbf {a} _{n}-\mathbf {proj} _{\mathbf {b} _{1}}\,\mathbf {a} _{n}-\mathbf {proj} _{\mathbf {b} _ {2}}\,\mathbf {a} _{n}-\dots -\mathbf {proj} _{\mathbf {b} _{n-1}}\,\mathbf {a} _{n}& (n)\end{array}}

Baseret på hver vektor kan en normaliseret vektor af enhedslængde opnås , defineret som $\mathbf {b} _{j}\;(j=1\ldots n)$ $\mathbf{e}_j$

{\mathbf {e}}_{j}={{\mathbf {b}}_{j} \over \|{\mathbf {b}}_{j}\|}

Resultater af Gram-Schmidt-processen:

${\displaystyle \mathbf {b} _{1},\;\ldots ,\;\mathbf {b} _{n))$ er et system af ortogonale vektorer eller

${\displaystyle \mathbf {e} _{1},\;\ldots ,\;\mathbf {e} _{n))$ er et system af ortonormale vektorer.

Beregningen kaldes Gram-Schmidt-ortogonaliseringen og Gram-Schmidt-ortonormaliseringen. ${\displaystyle \mathbf {b} _{1},\;\ldots ,\;\mathbf {b} _{n))$ ${\displaystyle \mathbf {e} _{1},\;\ldots ,\;\mathbf {e} _{n))$

Geometrisk fortolkning

Overvej formel (2), det andet trin i algoritmen. Dens geometriske repræsentation er vist i fig. en:

få projektionen af vektoren på ; ${\mathbf {a}}_{2}$ ${\mathbf {b}}_{1}$
beregning af , altså den vinkelrette , der projiceres på . Denne vinkelrette er vektoren beregnet i formel (2) ; ${\mathbf {a}}_{2}-{\mathbf {proj}}_{({\mathbf {b}}_{1}}}{\mathbf {a}}_{2}$ ${\mathbf {a}}_{2}$ ${\mathbf {b}}_{1}$ ${\mathbf {b}}_{2}$
at flytte vektoren opnået i trin 2 til oprindelsen. Denne bevægelse er lavet i figuren kun for klarhedens skyld; ${\mathbf {b}}_{2}$

Figuren viser, at vektoren er ortogonal på vektoren , da det er den vinkelrette, som den projiceres på . ${\mathbf {b}}_{2}$ ${\mathbf {b}}_{1}$ ${\mathbf {b}}_{2}$ ${\mathbf {a}}_{2}$ ${\mathbf {b}}_{1}$

Overvej formel (3), det tredje trin i algoritmen, i følgende version:

{\begin{array}{lcr}{\mathbf {b}}_{3}={\mathbf {a}}_{3}-({\mathbf {proj}}_{{{\mathbf {b} }_{1))}{\mathbf {a}}_{3}+{\mathbf {proj}}_{({\mathbf {b}}_{2}}}{\mathbf {a}}_ {3})&&(6)\\\end{array}}

Dens geometriske repræsentation er vist i fig. 2:

få projektionen af vektoren på ; ${\mathbf {a}}_{3}$ ${\mathbf {b}}_{1}$
få projektionen af vektoren på ; ${\mathbf {a}}_{3}$ ${\mathbf {b}}_{2}$
beregning af summen , det vil sige projektionen af vektoren på planen dannet af vektorerne og . Dette plan er gråtonet i figuren; ${\mathbf {proj}}_{{{\mathbf {b}}_{1}}}{\mathbf {a}}_{3}+{\mathbf {proj}}_{{{\mathbf {b }}_{2}}}{\mathbf {a}}_{3}$ ${\mathbf {a}}_{3}$ ${\mathbf {b}}_{1}$ ${\mathbf {b}}_{2}$
beregning , altså den vinkelrette, som projiceres på det plan, der er dannet af vektorerne og . Denne vinkelrette er vektoren beregnet i formel (6) ; ${\mathbf {a}}_{3}-({\mathbf {proj}}_{({\mathbf {b}}_{1}}}{\mathbf {a}}_{3}+{\ mathbf {proj}}_{{{\mathbf {b}}_{2}}}{\mathbf {a}}_{3})$ ${\mathbf {a}}_{3}$ ${\mathbf {b}}_{1}$ ${\mathbf {b}}_{2}$ ${\mathbf {b}}_{3}$
flytte modtaget til oprindelsen. Denne bevægelse er lavet i figuren kun for klarhedens skyld. Det er ikke en matematisk operation og afspejles derfor ikke i formel (6). ${\mathbf {b}}_{3}$

Figuren viser, at vektoren er ortogonal i forhold til vektorerne og , da det er en vinkelret, langs hvilken den projiceres på det plan, der er dannet af vektorerne og . ${\mathbf {b}}_{3}$ ${\mathbf {b}}_{1}$ ${\mathbf {b}}_{2}$ ${\mathbf {b}}_{3}$ ${\mathbf {a}}_{3}$ ${\mathbf {b}}_{1}$ ${\mathbf {b}}_{2}$

I Gram-Schmidt-processen udføres projektion således ortogonalt på hyperplanet omspændt af vektorer . Vektoren beregnes derefter som forskellen mellem og dens projektion. Det vil sige , det er vinkelret fra til hyperplanet spændt af vektorerne . Derfor er den ortogonal i forhold til vektorerne, der danner dette hyperplan. ${\mathbf {b}}_{j}$ ${\mathbf {a}}_{j}$ ${\mathbf {b}}_{1},\;\ldots ,\;{\mathbf {b}}_{{j-1}}$ ${\mathbf {b}}_{j}$ ${\mathbf {a}}_{j}$ ${\mathbf {b}}_{j}$ ${\mathbf {a}}_{j}$ ${\mathbf {b}}_{1},\;\ldots ,\;{\mathbf {b}}_{{j-1}}$ ${\mathbf {b}}_{j}$

Særlige lejligheder

Gram-Schmidt-processen kan også anvendes på en uendelig sekvens af lineært uafhængige vektorer.

Derudover kan Gram-Schmidt-processen anvendes på lineært afhængige vektorer. I dette tilfælde producerer den en (nul vektor) på trin, hvis det er en lineær kombination af vektorer . For at bevare ortogonaliteten af outputvektorerne og for at forhindre division med nul under ortogonalisering, skal algoritmen kassere nulvektorer. Antallet af vektorer produceret af algoritmen vil være lig med dimensionen af underrummet genereret af vektorerne (det vil sige antallet af lineært uafhængige vektorer, der kan skelnes fra de oprindelige vektorer). $\mathbf {0}$ $j$ ${\mathbf {a}}_{j}$ ${\mathbf {a}}_{1},\;\ldots ,\;{\mathbf {a}}_{{j-1}}$

Egenskaber

Overgangsmatricen fra til er en øvre trekantet matrix . ${\mathbf {a}}_{1},\;\ldots ,\;{\mathbf {a}}_{j}$ ${\mathbf {b}}_{1},\;\ldots ,\;{\mathbf {b}}_{j}$

Produktet af længderne er lig med volumenet af parallelepipedet bygget på systemets vektorer som på kanterne. ${\mathbf {b}}_{1},\;\ldots ,\;{\mathbf {b}}_{j}$ ${\mathbf {a}}_{1},\;\ldots ,\;{\mathbf {a}}_{j}$

Gram-Schmidt-processen for matrixens kolonnevektorer bestemmer homotopi-ækvivalensen . $GL(n)$ $GL(n)\to O(n)$

Yderligere fortolkninger

Gram-Schmidt-processen kan tolkes som nedbrydningen af en ikke- degenereret kvadratisk matrix til produktet af en ortogonal (eller enhedsform i tilfælde af et hermitisk rum ) og en øvre trekantet matrix med positive diagonale elementer, QR-nedbrydningen , som er en særligt tilfælde af Iwasawa-nedbrydningen .

Litteratur

Beklemishev DV Kursus i analytisk geometri og lineær algebra. — M .: Nauka .