Vés al contingut

Procés d'ortogonalització de Gram-Schmidt

De la Viquipèdia, l'enciclopèdia lliure
Els dos primers passos del 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à Rn dotat amb el producte escalar estàndard. El procés de Gram-Schmidt pren un conjunt finit linealment independent S = {v1, ..., vk} per kn i produeix un conjunt ortogonal S′ = {u1, ..., uk} que genera el mateix subespai k-dimensional de Rn 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.[1]

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

[modifica]
El procés de Gram-Schmidt modificat, aplicat a tres vectors linealment independents i no ortogonals d'una base de R3

Definim l'operador de projecció com

,

on 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 ; és a dir, la projecció é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:

La successió u1, ..., uk és el sistema desitjat de vectors ortogonals, i els vectors normalitzats e1, ..., ek formen un conjunt ortonormal. El càlcul de la successió u1, ..., uk es coneix com a ortogonalització de Gram-Schmidt, mentre que el càlcul de la successió e1, ..., ek 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 u1, u₂› substituint la fórmula anterior per u₂: el resultat és 0. Després usem aquest resultat per calcular u1, 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 ui, es projecta vi ortogonalment sobre el subespai U generat per u1, ..., ui−1, que és el mateix subespai que el generat per v1, ..., vi−1. Llavors es defineix el vector ui com la diferència entre vi 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 {vi}i. El resultat és una successió ortogonal (o ortonormal) {ui}i tal que, per a tot nombre natural n, el subespai generat per v1, ..., vn és el mateix que el subespai generat per u1, ..., un.

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 vi sigui una combinació lineal de v1, ..., vi−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) , amb la qual cosa s'obté un conjunt de vectors ortonormals amb , tal que per a qualsevol , la compleció de l'espai generat per és la mateixa que la de . 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 , fins i tot en el cas que el conjunt inicial sigui linealment independent, i l'espai generat per no té per què ser un subespai de l'espai generat per (de fet, és un subespai de la seva compleció).

Exemple

[modifica]

Considerem el següent conjunt de vectors de R² (amb el producte escalar habitual):

.

Ara apliquem el procés de Gram-Schmidt, per obtenir un conjunt ortogonal de vectors:

Comprovem que els vectors u1 i u₂ són ortogonals (és a dir, que el seu producte escalar és 0):

Per als vectors no nuls, podem normalitzar-los, dividint-los per les seves longituds:

,
.

Estabilitat numèrica

[modifica]

Quan s'implementa aquest procés en un ordinador, és habitual que els vectors uk 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 uk com

es calcula com

En cada pas, es troba un vector ortogonal a . Així, també s'ortogonalitza respecte qualsevol error introduït en el càlcul de .

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

[modifica]

El següent algorisme implementa l'ortonormalització del procés de Gram-Schmidt estabilitzat. Els vectors v1, ..., vk se substitueixen per vectors ortonormals que generen el mateix subespai.

El cost d'aquest algorisme és asimptòticament 2nk² operacions en coma flotant, on n és la dimensió dels vectors.[2]

Fórmula per determinants

[modifica]

El resultat del procés de Gram-Schmidt es pot expressar en termes no recursius utilitzant determinants:

on D0 = 1 i, per a j ≥ 1, Dj és el determinant de Gram:

Cal notar que l'expressió per a uk é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

[modifica]

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 una matriu de rang per columnes complet, per a la qual hom desitja ortogonalitzar les columnes. La matriu és hermítica i definida positiva, i per tant es pot escriure com , emprant la factorització de Cholesky. La matriu triangular inferior , que té les entrades de la diagonal estrictament positives, és invertible. Llavors, les columnes de la matriu són ortonormals i generen el mateix subespai que les columnes de la matriu original . L'ús explícit del producte 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.[3]

Referències

[modifica]
  1. Cheney, Ward; Kincaid, David. Linear Algebra: Theory and Applications. Sudbury, Ma: Jones and Bartlett, 2009, p. 544, 558. ISBN 978-0-7637-5020-6. 
  2. Golub i Van Loan, 1996, §5.2.8.
  3. 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

[modifica]

Enllaços externs

[modifica]