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 Rⁿ. Procedeul Gram–Schmidt se execută pe o mulțime finită liniar independentă S = {v₁, …, v_n} și produce o mulțime ortogonală S' = {u₁, …, u_n} 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

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 u₁, …, u_k este sistemul cerut de vectori ortogonali, iar vectorii normalizați e₁, …, e_k formează o mulțime ortonormală.

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

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

Se consideră următoarea mulțime de vectori din R² (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 u₁ și u₂ 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 =-{\frac {6}{5}}+{\frac {6}{5}}=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ă

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 u_k 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

Următorul algoritm implementează procedeul Gram–Schmidt stabilizat. Vectorii v₁, …, v_k 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 2kn² operații în virgulă mobilă, unde n este dimensiunea vectorilor.

Alternative

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

• 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

• MIT Linear Algebra Lecture on Orthogonal Matrices Arhivat în 7 noiembrie 2007, la Wayback Machine. at Google Video, from MIT OpenCourseWare
• Gram–Schmidt orthogonalization on the Earliest known uses of some of the words of mathematics