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ⁿ dotat amb el producte escalar estàndard. El procés de Gram-Schmidt pren un conjunt finit linealment independent S = {v₁, ..., v_k} per k ≤ n i produeix un conjunt ortogonal S′ = {u₁, ..., u_k} que genera el mateix subespai k-dimensional de Rⁿ que S.

Els dos primers passos del procés d'ortogonalització de Gram-Schmidt

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

El procés de Gram-Schmidt modificat, aplicat a tres vectors linealment independents i no ortogonals d'una base de R³

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₁, ..., u_k és el sistema desitjat de vectors ortogonals, i els vectors normalitzats e₁, ..., e_k formen un conjunt ortonormal. El càlcul de la successió u₁, ..., u_k es coneix com a ortogonalització de Gram-Schmidt, mentre que el càlcul de la successió e₁, ..., 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₁, u₂› substituint la fórmula anterior per u₂: el resultat és 0. Després usem aquest resultat per calcular ‹u₁, 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₁, ..., u_i−1, que és el mateix subespai que el generat per v₁, ..., 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₁, ..., v_n és el mateix que el subespai generat per u₁, ..., 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₁, ..., 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₁ 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₁, ..., 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₀ = 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.

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. 
• Harvey Mudd College Math Tutorial on the Gram-Schmidt algorithm Arxivat 2016-04-02 a Wayback Machine.
• Earliest known uses of some of the words of mathematics: G
• Demos: Gram Schmidt process in plane Arxivat 2009-05-07 a Wayback Machine. i Gram Schmidt process in space Arxivat 2009-05-07 a Wayback Machine.
• Miniaplicació d'ortogonalització de Gram-Schmidt
• NAG: rutina per a l'ortogonalització de Gram-Schmidt de n vectors d'ordre m
• Demostració: Raymond Puzio, Keenan Kidwell. "proof of Gram-Schmidt orthogonalization algorithm" (version 8). PlanetMath.org.