Procesul Gram-Schmidt

Procesul Gram - Schmidt transformă o secvență de vectori liniar independenți într- un sistem ortonormal de vectori și în așa fel încât fiecare vector să fie o combinație liniară de . $\mathbf {a} _{1},\;\ldots,\;\mathbf {a} _{n)$ $\mathbf {e} _{1},\;\ldots,\;\mathbf {e} _{n)$ $\mathbf{e}_j$ ${\mathbf {a}}_{1},\;\ldots ,\;{\mathbf {a}}_{j}$

Procesul Gram-Schmidt clasic

Algoritm

Să fie vectori liniar independenți și să fie operatorul de proiecție al unui vector pe un vector definit ca $\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 \ peste \langle {\mathbf {b)),{\mathbf {b}}\rangle }{\mathbf {b)),

unde este produsul scalar al vectorilor și . $\langle {\mathbf {a}},{\mathbf {b}}\rangle$ ${\mathbf {a}}$ ${\mathbf {b}}$

Procesul Gram-Schmidt clasic se realizează după cum urmează:

{\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)\\&\puncte &&\\\mathbf {b} _{n}&=&\mathbf {a} _{n}-\mathbf {proiect} _{\mathbf {b} _{1}}\,\mathbf {a} _{n}-\mathbf {proiect} _{\mathbf {b} _ {2}}\,\mathbf {a} _{n}-\dots -\mathbf {proj} _{\mathbf {b} _{n-1}}\,\mathbf {a} _{n}& (n)\end{matrice}}

Pe baza fiecărui vector , se poate obține un vector normalizat de unitate de lungime , definit ca $\mathbf {b} _{j}\;(j=1\ldots n)$ $\mathbf{e}_j$

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

Rezultatele procesului Gram-Schmidt:

$\mathbf {b} _{1},\;\ldots,\;\mathbf {b} _{n)$ este un sistem de vectori ortogonali sau

$\mathbf {e} _{1},\;\ldots,\;\mathbf {e} _{n)$ este un sistem de vectori ortonormali.

Calculul se numește ortogonalizare Gram-Schmidt și ortonormalizare Gram-Schmidt. $\mathbf {b} _{1},\;\ldots,\;\mathbf {b} _{n)$ $\mathbf {e} _{1},\;\ldots,\;\mathbf {e} _{n)$

Interpretare geometrică

Luați în considerare formula (2), a doua etapă a algoritmului. Reprezentarea sa geometrică este prezentată în Fig. unu:

obţinerea proiecţiei vectorului pe ; ${\mathbf {a}}_{2}$ ${\mathbf {b}}_{1}$
calculul , adică perpendiculara care se proiectează pe . Această perpendiculară este vectorul calculat în formula (2) ; ${\mathbf {a}}_{2}-{\mathbf {proj}}_{({\mathbf {b}}_{1}}}{\mathbf {a}}_{2}$ ${\mathbf {a}}_{2}$ ${\mathbf {b}}_{1}$ ${\mathbf {b}}_{2}$
deplasarea vectorului obţinut la pasul 2 la origine. Această mișcare este făcută în figură doar pentru claritate; ${\mathbf {b}}_{2}$

Figura arată că vectorul este ortogonal cu vectorul , deoarece este perpendiculara de-a lungul căreia este proiectat . ${\mathbf {b}}_{2}$ ${\mathbf {b}}_{1}$ ${\mathbf {b}}_{2}$ ${\mathbf {a}}_{2}$ ${\mathbf {b}}_{1}$

Luați în considerare formula (3), al treilea pas al algoritmului, în următoarea versiune:

{\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{matrice}}

Reprezentarea sa geometrică este prezentată în Fig. 2:

obţinerea proiecţiei vectorului pe ; ${\mathbf {a}}_{3}$ ${\mathbf {b}}_{1}$
obţinerea proiecţiei vectorului pe ; ${\mathbf {a}}_{3}$ ${\mathbf {b}}_{2}$
calculul sumei , adică proiecția vectorului pe planul format din vectorii și . Acest plan este umbrit în gri în figură; ${\mathbf {proiect}}_{{{\mathbf {b}}_{1}}}{\mathbf {a}}_{3}+{\mathbf {proiect}}_{{{\mathbf {b }}_{2}}}{\mathbf {a}}_{3}$ ${\mathbf {a}}_{3}$ ${\mathbf {b}}_{1}$ ${\mathbf {b}}_{2}$
calcul , adică perpendiculara, care este proiectată pe planul format din vectorii și . Această perpendiculară este vectorul calculat în formula (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}$
deplasarea primită la origine. Această mișcare este făcută în figură doar pentru claritate. Nu este o operație matematică și, prin urmare, nu este reflectată în formula (6). ${\mathbf {b}}_{3}$

Figura arată că vectorul este ortogonal cu vectorii și , deoarece este o perpendiculară de-a lungul căreia este proiectat pe planul format de vectorii și . ${\mathbf {b}}_{3}$ ${\mathbf {b}}_{1}$ ${\mathbf {b}}_{2}$ ${\mathbf {b}}_{3}$ ${\mathbf {a}}_{3}$ ${\mathbf {b}}_{1}$ ${\mathbf {b}}_{2}$

Astfel, în procesul Gram-Schmidt , proiecția este realizată ortogonal pe hiperplanul acoperit de vectori . Vectorul este apoi calculat ca diferență între și proiecția sa. Adică este perpendiculara de la hiperplanul acoperit de vectori . Prin urmare, este ortogonală cu vectorii care formează acest hiperplan. ${\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}$

Ocazii speciale

Procesul Gram-Schmidt poate fi aplicat și unei secvențe infinite de vectori liniar independenți.

În plus, procesul Gram-Schmidt poate fi aplicat vectorilor dependenți liniar. În acest caz, produce un (vector zero) la pas dacă este o combinație liniară de vectori . Pentru a păstra ortogonalitatea vectorilor de ieșire și pentru a preveni diviziunea la zero în timpul ortogonalizării, algoritmul trebuie să elimine vectorii zero. Numărul de vectori produși de algoritm va fi egal cu dimensiunea subspațiului generat de vectori (adică numărul de vectori liniar independenți care pot fi distinși de vectorii originali). $\mathbf {0}$ $j$ ${\mathbf {a}}_{j}$ ${\mathbf {a}}_{1},\;\ldots ,\;{\mathbf {a}}_{{j-1}}$

Proprietăți

Matricea de tranziție de la la este o matrice triunghiulară superioară . ${\mathbf {a}}_{1},\;\ldots ,\;{\mathbf {a}}_{j}$ ${\mathbf {b}}_{1},\;\ldots ,\;{\mathbf {b}}_{j}$

Produsul lungimilor este egal cu volumul paralelipipedului construit pe vectorii sistemului ca pe margini. ${\mathbf {b}}_{1},\;\ldots ,\;{\mathbf {b}}_{j}$ ${\mathbf {a}}_{1},\;\ldots ,\;{\mathbf {a}}_{j}$

Procesul Gram–Schmidt pentru vectorii coloană ai matricei din determină echivalența homotopiei . $GL(n)$ $GL(n)\la O(n)$

Interpretări suplimentare

Procesul Gram-Schmidt poate fi interpretat ca descompunerea unei matrice pătrate nedegenerate în produsul unei matrice ortogonale (sau unitare în cazul unui spațiu hermitian ) și a unei matrice triunghiulare superioare cu elemente diagonale pozitive, descompunerea QR , care este o caz special al descompunerii Iwasawa .

Literatură

Beklemishev DV Curs de geometrie analitică și algebră liniară. — M .: Nauka .

Link -uri

https://www.youtube.com/watch?v=GhhpG1tCQLU Animație a procesului în avion