# Procés d'ortogonalització de Gram-Schmidt

En matemàtiques, i en particular en àlgebra lineal i anàlisi numèrica, el procés d'ortogonalització de Gram-Schmidt és un mètode per ortonormalitzar un conjunt de vectors d'un espai prehilbertià, habitualment l'espai euclidià R$^n$ dotat amb el producte escalar estàndard. El procés de Gram-Schmidt pren un conjunt finit linealment independent S = {v$_1$, ..., v$_k$} per k ≤ n i produeix un conjunt ortogonal S′ = {u$_1$, ..., u$_k$} que genera el mateix subespai k-dimensional de R$^n$ que S.
El procés rep aquest nom per Jørgen Pedersen Gram i Erhard Schmidt, encara que va aparèixer anteriorment en l'obra de Laplace i Cauchy. En la teoria de descomposicions de grups de Lie es generalitza com la descomposició d'Iwasawa.
L'aplicació del procés d'ortogonalització de Gram-Schmidt al cas dels vectors d'una matriu amb rang per columnes complet proporciona la descomposició QR (la matriu descompon en una matriu ortogonal i una matriu triangular).

## El procés de Gram-Schmidt

Definim l'operador de projecció com
    $\mathrm {proj} _{\mathbf {u} }\,(\mathbf {v} )={\langle \mathbf {v} ,\mathbf {u} \rangle \over \langle \mathbf {u} ,\mathbf {u} \rangle }\mathbf {u}$,
on $\langle \mathbf {v} ,\mathbf {u} \rangle$ denota el producte escalar dels vectors v i u. Aquest operador projecta v ortogonalment sobre la recta generada pel vector u. Si u=0, definim $\mathrm {proj} _{\mathbf {0} }\,(\mathbf {v} ):={\mathbf {0} }$; és a dir, la projecció $\mathrm {proj} _{\mathbf {0} }$ és l'aplicació nul·la, que envia tot vector al vector nul.
El procés d'ortogonalització de Gram-Schmidt funciona llavors de la següent manera:
    ${\begin{aligned}\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}\|}.\end{aligned}}$
La successió u$_1$, ..., u$_k$ és el sistema desitjat de vectors ortogonals, i els vectors normalitzats e$_1$, ..., e$_k$ formen un conjunt ortonormal. El càlcul de la successió u$_1$, ..., u$_k$ es coneix com a ortogonalització de Gram-Schmidt, mentre que el càlcul de la successió e$_1$, ..., e$_k$ es coneix com a ortonormalització de Gram-Schmidt, ja que els vectors estan normalitzats.
Per verificar que aquestes fórmules proporcionen uns successió ortogonal, primer calculem ‹u$_1$, u₂› substituint la fórmula anterior per u₂: el resultat és 0. Després usem aquest resultat per calcular ‹u$_1$, u₃› substituint de nou la fórmula per u₃: el resultat és 0. La demostració general s'obté per inducció matemàtica.
Geomètricament, aquest mètode funciona de la següent manera: per calcular u$_i$, es projecta v$_i$ ortogonalment sobre el subespai U generat per u$_1$, ..., u$_{i−1}$, que és el mateix subespai que el generat per v$_1$, ..., v$_{i−1}$. Llavors es defineix el vector u$_i$ com la diferència entre v$_i$ i la seva projecció, garantint que sigui ortogonal a tots els vectors del subespai U.
El procés d'ortogonalització de Gram-Schmidt també es pot fer servir per a una successió infinita numerable linealment independent {v$_i$}$_i$. El resultat és una successió ortogonal (o ortonormal) {u$_i$}$_i$ tal que, per a tot nombre natural n, el subespai generat per v$_1$, ..., v$_n$ és el mateix que el subespai generat per u$_1$, ..., u$_n$.
Si s'aplica el procés d'ortogonalització de Gram-Schmidt a una successió linealment dependent, s'obté el vector 0 en el pas i-sim, posat que v$_i$ sigui una combinació lineal de v$_1$, ..., v$_{i−1}$. Si es desitja obtenir una base ortonormal, llavors l'algorisme ha de verificar si s'està calculant un vector nul, i ha de descartar-lo, ja que cap múltiple d'un vector nul pot tenir longitud 1. El nombre de vectors obtinguts per l'algorisme serà llavors la dimensió de l'espai generat per la successió original.
Emprant recursió transfinita, es pot aplicar una variant del procés de Gram-Schmidt a una successió infinita de vectors (possiblement no numerable) $(v_{\alpha })_{\alpha <\lambda }$, amb la qual cosa s'obté un conjunt de vectors ortonormals $(u_{\alpha })_{\alpha <\kappa }$ amb $\kappa \leq \lambda$, tal que per a qualsevol $\alpha \leq \lambda$, la compleció de l'espai generat per $\lbrace u_{\beta }:\beta <\min(\alpha ,\kappa )\rbrace$ és la mateixa que la de $\lbrace v_{\beta }:\beta <\alpha \rbrace$. En particular, quan s'aplica a una base (algebraica) d'un espai de Hilbert (o, més en general, a una base d'un subespai dens qualsevol), hom obté una base ortonormal (funcional-analítica). Notem que, en general, hom té la desigualtat estricta $\kappa <\lambda$, fins i tot en el cas que el conjunt inicial sigui linealment independent, i l'espai generat per $(u_{\alpha })_{\alpha <\kappa }$ no té per què ser un subespai de l'espai generat per $(v_{\alpha })_{\alpha <\lambda }$ (de fet, és un subespai de la seva compleció).

## Exemple

Considerem el següent conjunt de vectors de R² (amb el producte escalar habitual):
    $S=\left\lbrace \mathbf {v} _{1}={\begin{pmatrix}3\\1\end{pmatrix}},\mathbf {v} _{2}={\begin{pmatrix}2\\2\end{pmatrix}}\right\rbrace$.
Ara apliquem el procés de Gram-Schmidt, per obtenir un conjunt ortogonal de vectors:
    ${\begin{aligned}\mathbf {u} _{1}&=\mathbf {v} _{1}={\begin{pmatrix}3\\1\end{pmatrix}}\end{aligned}}$
    ${\begin{aligned}\mathbf {u} _{2}&=\mathbf {v} _{2}-\mathrm {proj} _{\mathbf {u} _{1}}\,(\mathbf {v} _{2})=\\&={\begin{pmatrix}2\\2\end{pmatrix}}-\mathrm {proj} _{\left({3 \atop 1}\right)}\,({{\begin{pmatrix}2\\2\end{pmatrix}})}=\\&={\begin{pmatrix}2\\2\end{pmatrix}}-{\begin{pmatrix}4/5\end{pmatrix}}{\begin{pmatrix}3\\1\end{pmatrix}}=\\&={\begin{pmatrix}-2/5\\6/5\end{pmatrix}}.\end{aligned}}$
Comprovem que els vectors u$_1$ i u₂ són ortogonals (és a dir, que el seu producte escalar és 0):
    ${\begin{aligned}\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.\end{aligned}}$
Per als vectors no nuls, podem normalitzar-los, dividint-los per les seves longituds:
    $\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}}$.

## Estabilitat numèrica

Quan s'implementa aquest procés en un ordinador, és habitual que els vectors u$_k$ no siguin del tot ortogonals, a causa dels errors d'arrodoniment. En una implementació directa del procés d'ortogonalització de Gram-Schmidt (sovint anomenat "Gram-Schmidt clàssic") aquesta pèrdua d'ortogonalitat és especialment inconvenient; per tant, hom diu que el procés de Gram-Schmidt (clàssic) és numèricament inestable.
El procés d'ortogonalització de Gram-Schmidt es pot estabilitzar amb una petita modificació; de vegades es parla d'un procés de Gram-Schmidt modificat ((anglès) modified Gram-Schmidt o MGS). Aquest enfocament proporciona el mateix resultat que la fórmula original en el cas de treballar amb aritmètica exacta, i introdueix errors menors en aritmètica de precisió finita. En comptes de calcular el vector u$_k$ com
    $\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}),$
es calcula com
    ${\begin{aligned}\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}^{(k-1)}&=\mathbf {u} _{k}^{(k-2)}-\mathrm {proj} _{\mathbf {u} _{k-1}}\,(\mathbf {u} _{k}^{(k-2)}).\end{aligned}}$
En cada pas, es troba un vector $\mathbf {u} _{k}^{(i)}$ ortogonal a $\mathbf {u} _{k}^{(i-1)}$. Així, $\mathbf {u} _{k}^{(i)}$ també s'ortogonalitza respecte qualsevol error introduït en el càlcul de $\mathbf {u} _{k}^{(i-1)}$.
Aquest mètode és el que s'utilitza en l'animació anterior, quan s'empra el vector intermedi v '₃ en el pas d'ortogonalització del vector blau v₃.

## Algorisme

El següent algorisme implementa l'ortonormalització del procés de Gram-Schmidt estabilitzat. Els vectors v$_1$, ..., v$_k$ se substitueixen per vectors ortonormals que generen el mateix subespai.
    ${\begin{array}{l}e1_{1}\leftarrow {e_{1} \over \left|e_{1}\right|}\\\mathbf {per\ a\ cada\ } i\in [2,n]\\\quad \mathbf {per\ a\ cada\ } j\in [1,i-1]\\\qquad e_{i}\leftarrow e_{i}-\left(e1_{j}\cdot e_{i}\right)\cdot e1_{j}\\\quad \mathbf {fi\ per} \\\quad e1_{i}\leftarrow {e_{i} \over \left|e_{i}\right|}\\\mathbf {fi\ per} \\e_{1}\end{array}}$
El cost d'aquest algorisme és asimptòticament 2nk² operacions en coma flotant, on n és la dimensió dels vectors.

## Fórmula per determinants

El resultat del procés de Gram-Schmidt es pot expressar en termes no recursius utilitzant determinants:
    $\mathbf {e} _{j}={\frac {1}{\sqrt {D_{j-1}D_{j}}}}{\begin{vmatrix}\langle \mathbf {v} _{1},\mathbf {v} _{1}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{1}\rangle &\dots &\langle \mathbf {v} _{j},\mathbf {v} _{1}\rangle \\\langle \mathbf {v} _{1},\mathbf {v} _{2}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{2}\rangle &\dots &\langle \mathbf {v} _{j},\mathbf {v} _{2}\rangle \\\vdots &\vdots &\ddots &\vdots \\\langle \mathbf {v} _{1},\mathbf {v} _{j-1}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{j-1}\rangle &\dots &\langle \mathbf {v} _{j},\mathbf {v} _{j-1}\rangle \\\mathbf {v} _{1}&\mathbf {v} _{2}&\dots &\mathbf {v} _{j}\end{vmatrix}}$
    $\mathbf {u} _{j}={\frac {1}{D_{j-1}}}{\begin{vmatrix}\langle \mathbf {v} _{1},\mathbf {v} _{1}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{1}\rangle &\dots &\langle \mathbf {v} _{j},\mathbf {v} _{1}\rangle \\\langle \mathbf {v} _{1},\mathbf {v} _{2}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{2}\rangle &\dots &\langle \mathbf {v} _{j},\mathbf {v} _{2}\rangle \\\vdots &\vdots &\ddots &\vdots \\\langle \mathbf {v} _{1},\mathbf {v} _{j-1}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{j-1}\rangle &\dots &\langle \mathbf {v} _{j},\mathbf {v} _{j-1}\rangle \\\mathbf {v} _{1}&\mathbf {v} _{2}&\dots &\mathbf {v} _{j}\end{vmatrix}}$
on D$_0$ = 1 i, per a j ≥ 1, D$_j$ és el determinant de Gram:
    $D_{j}={\begin{vmatrix}\langle \mathbf {v} _{1},\mathbf {v} _{1}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{1}\rangle &\dots &\langle \mathbf {v} _{j},\mathbf {v} _{1}\rangle \\\langle \mathbf {v} _{1},\mathbf {v} _{2}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{2}\rangle &\dots &\langle \mathbf {v} _{j},\mathbf {v} _{2}\rangle \\\vdots &\vdots &\ddots &\vdots \\\langle \mathbf {v} _{1},\mathbf {v} _{j}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{j}\rangle &\dots &\langle \mathbf {v} _{j},\mathbf {v} _{j}\rangle \end{vmatrix}}.$
Cal notar que l'expressió per a u$_k$ és un determinant "formal", és a dir, la matriu conté tant escalars com vectors; el significat d'aquesta expressió és, precisament, la definició d'una expansió de Laplace al llarg de la fila de vectors.
La fórmula per determinants del procés de Gram-Schmidt és computacionalment més lenta (exponencialment més lenta) que els algorismes recursius vistos anteriorment; el seu interès és merament teòric.

## Alternatives

Altres algorismes d'ortogonalització utilitzen transformacions de Householder o rotacions de Givens. Els algorismes que utilitzen transformacions de Householder són més estables que el procés de Gram-Schmidt estabilitzat. Per altra banda, el procés de Gram-Schmidt produeix el j-sim vector ortogonalitzat després de la j-sima iteració, mentre que l'ortogonalització via reflexions de Householder produeix tots els vectors de cop al final del procés. Això fa que el procés de Gram-Schmidt sigui l'utilitzat en mètodes iteratius com la iteració d'Arnoldi.
Una altra alternativa ve motivada per l'ús de la factorització de Cholesky en el procés d'inversió de la matriu de les equacions normals en mínims quadrats ordinaris. Sigui $\mathbf {V}$ una matriu de rang per columnes complet, per a la qual hom desitja ortogonalitzar les columnes. La matriu $\mathbf {V} ^{*}\mathbf {V}$ és hermítica i definida positiva i, per tant, es pot escriure com $\mathbf {V} ^{*}\mathbf {V} ={\mathcal {L}}{\mathcal {L}}^{*}$, emprant la factorització de Cholesky. La matriu triangular inferior ${\mathcal {L}}$, que té les entrades de la diagonal estrictament positives, és invertible. Llavors, les columnes de la matriu $\mathbf {U} =\mathbf {V} ({\mathcal {L}}^{-1})^{*}$ són ortonormals i generen el mateix subespai que les columnes de la matriu original $\mathbf {V}$. L'ús explícit del producte $\mathbf {V} ^{*}\mathbf {V}$ fa que l'algorisme sigui inestable, especialment si el nombre de condició del producte és gran. Tot i això, aquest algorisme s'utilitza a la pràctica i s'implementa en alguns paquets de programari a causa de la seva elevada eficiència i simplicitat.
En mecànica quàntica, existeixen diversos esquemes d'ortogonalització amb característiques més adients que el procés de Gram-Schmidt original. No obstant això, aquest mètode continua sent un algorisme popular i eficient fins i tot per a les computacions d'estructures electròniques més grans.

## Referències

* ↑ Cheney, Ward; Kincaid, David. Linear Algebra: Theory and Applications. Sudbury, Ma: Jones and Bartlett, 2009, p. 544, 558. ISBN 978-0-7637-5020-6.
* ↑ Golub i Van Loan, 1996, §5.2.8.
* ↑ Hasegawa, Yukihiro; Iwata, Jun-Ichi; Tsuji, Miwako; Takahashi, Daisuke; Oshiyama, Atsushi; Minami, Kazuo; Boku, Taisuke; Shoji, Fumiyoshi; Uno, Atsuya; Kurokawa, Motoyoshi; Inoue, Hikaru; Miyoshi, Ikuo; Yokokawa, Mitsuo «First-principles calculations of electron states of a silicon nanowire with 100,000 atoms on the K computer». 2011 International Conference for High Performance Computing, Networking, Storage and Analysis (SC) [Seattle, Washington], 12-18 novembre 2011. DOI: 10.1145/2063384.2063386. ISSN: 2167-4329.

## Bibliografia

* Bau III, David; Trefethen, Lloyd N. Numerical linear algebra. Philadelphia: Society for Industrial and Applied Mathematics, 1997. ISBN 978-0-89871-361-9.
* Golub, Gene H.; Van Loan, Charles F. Matrix Computations. 3a edició. Johns Hopkins, 1996. ISBN 978-0-8018-5414-9.
* Greub, Werner H. Linear Algebra. 4a edició. Springer, 1975. ISBN 978-1-4684-9446-4.
* Soliverez, C. E.; Gagliano, E. «Orthonormalization on the plane: a geometric approach». Mex. J. Phys., 31, 4, 1985, pàg. 743-758. Arxivat de l'original el 2014-03-07 [Consulta: 27 maig 2016].

## Enllaços externs

* Michiel Hazewinkel (ed.). Orthogonalization. Encyclopedia of Mathematics (en anglès). Springer, 2001. ISBN 978-1-55608-010-4.
* Earliest known uses of some of the words of mathematics: G
* Miniaplicació d'ortogonalització de Gram-Schmidt