Vizualizare sursă pentru „Procedeul Gram–Schmidt”

În [[matematică]] și [[analiză numerică]], '''procedeul Gram–Schmidt''' este o metodă de [[ortogonalizare]] a unei mulțimi de [[vector]]i într-un [[spațiu cu produs scalar]], în mod obișnuit în [[spațiul euclidian]] '''R'''<sup>''n''</sup>. Procedeul Gram–Schmidt se execută pe o mulțime [[Mulțime finită|finită]] [[liniar independentă]] ''S'' = {''v''<sub>1</sub>, …, ''v''<sub>''n''</sub>} și produce o [[mulțime ortogonală]] ''S''<nowiki>'</nowiki> = {''u''<sub>1</sub>, …, ''u''<sub>''n''</sub>} care generează același subspațiu ca și ''S''.

Metoda își trage numele de la [[Jørgen Pedersen Gram]] și [[Erhard Schmidt]] dar a apărut anterior acestora, în lucrările lui [[Laplace]] și [[Cauchy]]. În teoria descompunerii grupurilor Lie, el este generalizat de [[descompunerea Iwasawa]].

Aplicarea procedeului Gram–Schmidt pe vectorii coloană ai unei [[matrice]] [[rang]] produce [[descompunerea QR]] (se descompune într-o matrice [[Matrice ortogonală|ortogonală]] și una [[Matrice triunghiulară|triunghiulară]]).

== Procedeul Gram-Schmidt ==

Se definește [[operator (matematică)|operatorul]] [[proiecție (algebră liniară)|proiecție]] prin
:<math>\mathrm{proj}_{\mathbf{u}}\,\mathbf{v} = {\langle \mathbf{u}, \mathbf{v}\rangle\over\langle \mathbf{u}, \mathbf{u}\rangle}\mathbf{u}, </math>
unde cu <'''u''', '''v'''> se notează [[produsul scalar]] al vectorilor '''u''' și '''v'''. Acest operator proiectează '''v''' ortogonal pe vectorul '''u'''. 

Procedeul Gram-Schmidt funcționează după cum urmează:

{|
|width="20px"| ||<math>\mathbf{u}_1 = \mathbf{v}_1,</math> 
|width="20px"| ||<math>\mathbf{e}_1 = {\mathbf{u}_1 \over \|\mathbf{u}_1\|}</math>
|-
|| ||<math>\mathbf{u}_2 = \mathbf{v}_2-\mathrm{proj}_{\mathbf{u}_1}\,\mathbf{v}_2, </math>
|| ||<math>\mathbf{e}_2 = {\mathbf{u}_2 \over \|\mathbf{u}_2\|}</math>
|-
|| ||<math>\mathbf{u}_3 = \mathbf{v}_3-\mathrm{proj}_{\mathbf{u}_1}\,\mathbf{v}_3-\mathrm{proj}_{\mathbf{u}_2}\,\mathbf{v}_3, </math>
|| ||<math>\mathbf{e}_3 = {\mathbf{u}_3 \over \|\mathbf{u}_3\|}</math>
|-
|| ||<math>\mathbf{u}_4 = \mathbf{v}_4-\mathrm{proj}_{\mathbf{u}_1}\,\mathbf{v}_4-\mathrm{proj}_{\mathbf{u}_2}\,\mathbf{v}_4-\mathrm{proj}_{\mathbf{u}_3}\,\mathbf{v}_4, </math>
|| ||<math>\mathbf{e}_4 = {\mathbf{u}_4 \over \|\mathbf{u}_4\|}</math>
|-
|| ||align="center"|<math>\vdots</math>
|| ||align="center"|<math>\vdots</math>
|-
|| ||<math>\mathbf{u}_k = \mathbf{v}_k-\sum_{j=1}^{k-1}\mathrm{proj}_{\mathbf{u}_j}\,\mathbf{v}_k, </math>
|| ||<math>\mathbf{e}_k = {\mathbf{u}_k\over \|\mathbf{u}_k \|}</math>
|}
[[Fișier:Gram–Schmidt process.svg|right|frame|Primii doi paşi ai procedeului Gram–Schmidt.]]
Secvența '''u'''<sub>1</sub>, …, '''u'''<sub>''k''</sub> este sistemul cerut de vectori ortogonali, iar vectorii normalizați '''e'''<sub>1</sub>, …, '''e'''<sub>''k''</sub> formează o mulțime [[ortonormalitate|orto''normală'']].

Pentru a verifica dacă aceste formule produc o secvență ortogonală, întâi se calculează 〈'''u'''<sub>1</sub>, '''u'''<sub>2</sub>〉 prin înlocuirea cu '''u'''<sub>2</sub> în formula de mai sus: se obține zero. Apoi se folosește aceasta pentru a calcula 〈'''u'''<sub>1</sub>, '''u'''<sub>3</sub>〉 din nou prin înlocuire în formulă cu '''u'''<sub>3</sub>: se obține zero. Demonstrația pe cazul general continuă prin [[inducție matematică]].

Geometric, această metodă are următorii pași: pentru a calcula '''u'''<sub>''i''</sub>, se proiectează '''v'''<sub>''i''</sub> ortogonal pe subspațiul ''U'' generat de '''u'''<sub>1</sub>, …, '''u'''<sub>''i''−1</sub>, care este același lucru cu subspațiul generat de '''v'''<sub>1</sub>, …, '''v'''<sub>''i''−1</sub>. Vectorul '''u'''<sub>''i''</sub> se definește apoi ca diferența dintre '''v'''<sub>''i''</sub> și această proiecție, garantată a fi ortogonală pe toți vectorii din subspațiul ''U''.

Procedeul Gram–Schmidt se aplică și pe o secvență [[infinită]] liniar independentă {'''v'''<sub>''i''</sub>}<sub>''i''</sub>. Rezultă o secvență ortogonală (sau ortonormală) {'''u'''<sub>''i''</sub>}<sub>''i''</sub> astfel încât pentru orice număr natural ''n'':
spațiul generat de '''v'''<sub>1</sub>, …, '''v'''<sub>''n''</sub> este același cu cel generat de '''u'''<sub>1</sub>, …, '''u'''<sub>''n''</sub>.

Dacă procedeul Gram–Schmidt se aplică pe o secvență liniar dependentă, rezultă vectorul '''0''' la pasul <math>i</math>, presupunând că <math>\mathbf{v_i}</math> este o combinație liniară de <math>\mathbf{v_1}, \mathbf{v_2}, \ldots, \mathbf{v_{i-1}}</math>.

== Exemplu ==
Se consideră următoarea mulțime de vectori din '''R'''<sup>2</sup> (cu produsul scalar convențional)
:<math>S = \left\lbrace\mathbf{v}_1=\begin{pmatrix} 3 \\ 1\end{pmatrix}, \mathbf{v}_2=\begin{pmatrix}2 \\2\end{pmatrix}\right\rbrace.</math>

Acum, aplicăm Gram–Schmidt, pentru a obține o mulțime ortogonală de vectori:
:<math>\mathbf{u}_1=\mathbf{v}_1=\begin{pmatrix}3\\1\end{pmatrix}</math>
:<math> \mathbf{u}_2 = \mathbf{v}_2 - \mathrm{proj}_{\mathbf{u}_1} \, \mathbf{v}_2 = \begin{pmatrix}2\\2\end{pmatrix} - \mathrm{proj}_{({3 \atop 1})} \, {\begin{pmatrix}2\\2\end{pmatrix}} = \begin{pmatrix} -2/5 \\6/5 \end{pmatrix}. </math>

Verificăm că vectorii '''u'''<sub>1</sub> și '''u'''<sub>2</sub> sunt ortogonali:
:<math>\langle\mathbf{u}_1,\mathbf{u}_2\rangle = \left\langle \begin{pmatrix}3\\1\end{pmatrix}, \begin{pmatrix}-2/5\\6/5\end{pmatrix} \right\rangle = -\frac65 + \frac65 = 0.</math>

Apoi putem normaliza vectorii împărțindu-i la norma lor:
:<math>\mathbf{e}_1 = {1 \over \sqrt {10}}\begin{pmatrix}3\\1\end{pmatrix}</math>
:<math>\mathbf{e}_2 = {1 \over \sqrt{40 \over 25}} \begin{pmatrix}-2/5\\6/5\end{pmatrix}
 = {1\over\sqrt{10}} \begin{pmatrix}-1\\3\end{pmatrix}. </math>
 
== Stabilitate numerică ==
 
La implementarea pe calculator a procedeului, vectorii <math>u_k</math> nu sunt chiar ortogonali datorită [[Eroare de rotunjire|erorilor de rotunjire]]. Pentru procedeul Gram–Schmidt descris mai sus, această pierdere de ortogonalitate este deosebit de gravă; de aceea, se spune că procedeul Gram–Schmidt este [[Stabilitate numerică|instabil numeric]].
 
Procedeul Gram–Schmidt poate fi stabilizat cu o foarte mică modificare. În loc de a calcula vectorul '''u'''<sub>''k''</sub> ca
:<math> \mathbf{u}_k = \mathbf{v}_k - \mathrm{proj}_{\mathbf{u}_1}\,\mathbf{v}_k - \mathrm{proj}_{\mathbf{u}_2}\,\mathbf{v}_k - \cdots - \mathrm{proj}_{\mathbf{u}_{k-1}}\,\mathbf{v}_k, </math>
el este calculat ca
:<math> \mathbf{u}_k^{(1)} = \mathbf{v}_k - \mathrm{proj}_{\mathbf{u}_1}\,\mathbf{v}_k, </math>
:<math> \mathbf{u}_k^{(2)} = \mathbf{u}_k^{(1)} - \mathrm{proj}_{\mathbf{u}_2} \, \mathbf{u}_k^{(1)}, </math>
:::<math> \vdots </math>
:<math> \mathbf{u}_k^{(k-2)} = \mathbf{u}_k^{(k-3)} - \mathrm{proj}_{\mathbf{u}_{k-2}} \, \mathbf{u}_k^{(k-3)}, </math>
:<math> \mathbf{u}_k = \mathbf{u}_k^{(k-2)} - \mathrm{proj}_{\mathbf{u}_{k-1}} \, \mathbf{u}_k^{(k-2)}. </math>
Această serie de calcule dă același rezultat ca și formula originală în aritmetica exactă, dar introduce erori mai mici în aritmetica cu precizie finită.
 
== Algoritm ==
 
Următorul algoritm implementează procedeul Gram–Schmidt stabilizat. Vectorii '''v'''<sub>1</sub>, …, '''v'''<sub>''k''</sub> sunt înlocuiți de vectori ortonormali care generează același subspațiu.
 : '''for''' ''j'' '''from''' 1 '''to''' ''k'' '''do'''
 :: '''for''' ''i'' '''from''' 1 '''to''' ''j'' − 1 '''do'''
 ::: <math> \mathbf{v}_j \leftarrow \mathbf{v}_j - \langle \mathbf{v}_j, \mathbf{v}_i \rangle \mathbf{v}_i </math> (''elimină componenta pe direcția '' '''v'''<sub>''i''</sub>)
 :: '''end for'''
 :: <math> \mathbf{v}_j \leftarrow \frac{\mathbf{v}_j}{\|\mathbf{v}_j\|} </math> (''normalizare'')
 : '''end for'''
Costul acestui algoritm este asimptotic 2''kn''<sup>2</sup> operații în [[virgulă mobilă]], unde ''n'' este dimensiunea vectorilor.
 
== Alternative ==
 
Alți algoritmi de ortogonalizare folosesc [[Transformare Householder|transformările Householder]] sau [[Rotația Givens|rotațiile Givens]]. Algoritmii cu transformări Householder sunt mai stabili decât procedeul Gram–Schmidt stabilizat. Pe de altă oarte, procedeul Gram–Schmidt dă al <math>j</math>-lea vector ortogonalizat după a <math>j</math>-a iterație, în vreme ce tehnica cu reflectorii Householder produce toți vectorii doar la sfârșit. Aceasta face ca procedeul Gram–Schmidt să fie singurul aplicabil în [[Metodă iterativă|metodele iterative]] cum ar fi [[iterația Arnoldi]].
 
== Bibliografie ==
* Lloyd N. Trefethen and David Bau, III, ''Numerical Linear Algebra'', Society for Industrial and Applied Mathematics, 1997. ISBN 0-89871-361-7.
 
== Legături externe ==
* [http://video.google.com/videoplay?docid=-2274442444593051761 MIT Linear Algebra Lecture on Orthogonal Matrices] {{Webarchive|url=https://web.archive.org/web/20071107094329/http://video.google.com/videoplay?docid=-2274442444593051761 |date=2007-11-07 }} at Google Video, from MIT OpenCourseWare
* [https://web.archive.org/web/19990508225359/http://members.aol.com/jeff570/g.html Gram–Schmidt orthogonalization] on the [https://web.archive.org/web/19990117033417/http://members.aol.com/jeff570/mathword.html Earliest known uses of some of the words of mathematics]

{{Algebră liniară}}

[[Categorie:Algebră liniară]]
[[Categorie:Analiză funcțională]]