Procedeul Gram–Schmidt

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

Î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 | modificare sursă]

Se definește operatorul proiecție prin

\mathrm{proj}_{\mathbf{u}}\,\mathbf{v} = {\langle \mathbf{u}, \mathbf{v}\rangle\over\langle \mathbf{u}, \mathbf{u}\rangle}\mathbf{u},

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

\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\|}
\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, \mathbf{e}_4 = {\mathbf{u}_4 \over \|\mathbf{u}_4\|}
\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 \|}
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 i, presupunând că \mathbf{v_i} este o combinație liniară de \mathbf{v_1}, \mathbf{v_2}, \ldots, \mathbf{v_{i-1}}.

Exemplu[modificare | modificare sursă]

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

S = \left\lbrace\mathbf{v}_1=\begin{pmatrix} 3 \\ 1\end{pmatrix}, \mathbf{v}_2=\begin{pmatrix}2 \\2\end{pmatrix}\right\rbrace.

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

\mathbf{u}_1=\mathbf{v}_1=\begin{pmatrix}3\\1\end{pmatrix}
 \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}.

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

\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.

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

\mathbf{e}_1 = {1 \over \sqrt {10}}\begin{pmatrix}3\\1\end{pmatrix}
\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}.

Stabilitate numerică[modificare | modificare sursă]

La implementarea pe calculator a procedeului, vectorii u_k 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

 \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,

el este calculat ca

 \mathbf{u}_k^{(1)} = \mathbf{v}_k - \mathrm{proj}_{\mathbf{u}_1}\,\mathbf{v}_k,
 \mathbf{u}_k^{(2)} = \mathbf{u}_k^{(1)} - \mathrm{proj}_{\mathbf{u}_2} \, \mathbf{u}_k^{(1)},
 \vdots
 \mathbf{u}_k^{(k-2)} = \mathbf{u}_k^{(k-3)} - \mathrm{proj}_{\mathbf{u}_{k-2}} \, \mathbf{u}_k^{(k-3)},
 \mathbf{u}_k = \mathbf{u}_k^{(k-2)} - \mathrm{proj}_{\mathbf{u}_{k-1}} \, \mathbf{u}_k^{(k-2)}.

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 | modificare sursă]

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
:::  \mathbf{v}_j \leftarrow \mathbf{v}_j - \langle \mathbf{v}_j, \mathbf{v}_i \rangle \mathbf{v}_i  (elimină componenta pe direcția  vi)
:: end for
::  \mathbf{v}_j \leftarrow \frac{\mathbf{v}_j}{\|\mathbf{v}_j\|}  (normalizare)
: end for

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

Alternative[modificare | modificare sursă]

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 j-lea vector ortogonalizat după a j-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 | modificare sursă]

  • 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 | modificare sursă]