Procedeul Gram–Schmidt

(Redirecționat de la Procedeul Gram-Schmidt)

În matematică și analiză numerică, procedeul Gram–Schmidt este o metodă de ortogonalizare a unei mulțimi de vectori într-un spațiu cu produs scalar, în mod obișnuit în spațiul euclidian Rn. Procedeul Gram–Schmidt se execută pe o mulțime finită liniar independentă S = {v1, …, vn} și produce o mulțime ortogonală S' = {u1, …, un} 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 ortogonală și una triunghiulară).

Procedeul Gram-Schmidt

modificare

Se definește operatorul proiecție prin

 

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ă:

   
   
   
   
   
   
 
Primii doi paşi ai procedeului Gram–Schmidt.

Secvența u1, …, uk este sistemul cerut de vectori ortogonali, iar vectorii normalizați e1, …, ek formează o mulțime ortonormală.

Pentru a verifica dacă aceste formule produc o secvență ortogonală, întâi se calculează 〈u1, u2〉 prin înlocuirea cu u2 în formula de mai sus: se obține zero. Apoi se folosește aceasta pentru a calcula 〈u1, u3〉 din nou prin înlocuire în formulă cu u3: 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 ui, se proiectează vi ortogonal pe subspațiul U generat de u1, …, ui−1, care este același lucru cu subspațiul generat de v1, …, vi−1. Vectorul ui se definește apoi ca diferența dintre vi ș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ă {vi}i. Rezultă o secvență ortogonală (sau ortonormală) {ui}i astfel încât pentru orice număr natural n: spațiul generat de v1, …, vn este același cu cel generat de u1, …, un.

Dacă procedeul Gram–Schmidt se aplică pe o secvență liniar dependentă, rezultă vectorul 0 la pasul  , presupunând că   este o combinație liniară de  .

Se consideră următoarea mulțime de vectori din R2 (cu produsul scalar convențional)

 

Acum, aplicăm Gram–Schmidt, pentru a obține o mulțime ortogonală de vectori:

 
 

Verificăm că vectorii u1 și u2 sunt ortogonali:

 

Apoi putem normaliza vectorii împărțindu-i la norma lor:

 
 

Stabilitate numerică

modificare

La implementarea pe calculator a procedeului, vectorii   nu sunt chiar ortogonali datorită 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 instabil numeric.

Procedeul Gram–Schmidt poate fi stabilizat cu o foarte mică modificare. În loc de a calcula vectorul uk ca

 

el este calculat ca

 
 
 
 
 

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

modificare

Următorul algoritm implementează procedeul Gram–Schmidt stabilizat. Vectorii v1, …, vk 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
:::   (elimină componenta pe direcția  vi)
:: end for
::   (normalizare)
: end for

Costul acestui algoritm este asimptotic 2kn2 operații în virgulă mobilă, unde n este dimensiunea vectorilor.

Alternative

modificare

Alți algoritmi de ortogonalizare folosesc transformările Householder sau 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  -lea vector ortogonalizat după a  -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 metodele iterative cum ar fi iterația Arnoldi.

Bibliografie

modificare
  • 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

modificare