Vés al contingut

Descomposició QR

De la Viquipèdia, l'enciclopèdia lliure
(S'ha redirigit des de: Factorització QR)

En àlgebra lineal, una descomposició QR (també anomenada factorització QR) d'una matriu és una descomposició d'una matriu A en el producte A=QR d'una matriu ortogonal Q per una matriu triangular superior R (de l'anglès right, dreta, ja que una matriu triangular superior té tots els seus elements no-nuls a sobre i a la dreta de la diagonal principal –inclosa–). La descomposició QR es fa servir en la resolució de problemes de mínims quadrats, i és la base per un algorisme especial pel càlcul dels valors propis d'una matriu, l'algorisme QR.

Si An columnes linealment independents, llavors les primeres n columnes de Q configuren una base ortonormal de l'espai de columnes d'A. Concretament, les primeres k columnes de Q formen una base ortonormal per a l'espai vectorial generat per les primeres k columnes d'A, per qualsevol 1≤kn.[1] El fet que tota columna k d'A només depengui de les primeres k columnes de Q és l'argument bàsic per tal que la matriu R sigui triangular.[1]

Definicions

[modifica]

Matrius quadrades

[modifica]

Qualsevol matriu real quadrada A es pot descompondre com a

on Q és una matriu ortogonal (les seves columnes són vectors unitaris ortogonals, la qual cosa implica que QTQ = I) i R és una matriu triangular superior. Aquesta definició es pot generalitzar al cas d'una matriu quadrada complexa A i una matriu unitària Q. Si A és invertible, llavors la descomposició és única si s'afegeix la hipòtesi que els elements de la diagonal de R siguin positius.

Matrius rectangulars

[modifica]

En un cas més general, es pot factoritzar una matriu complexa A m×n, amb mn, com el producte d'una matriu unitària Q m×m i una matriu triangular superior R m×n. Com que les últimes (mn) files d'una matriu triangular superior m×n són entrades a zero, de vegades és útil segmentar la matriu R, o bé tant R com Q:

on R1 és una matriu triangular superior n×n, Q1 és m×n, Q₂ és m×(mn), i tant Q1 com Q₂ tenen columnes ortogonals.

Golub & Van Loan (1996, §5.2) anomenen Q1R1 la factorització QR aprimada d'A; per la seva banda, Trefethen & Bau l'anomenen factorització QR reduïda.[1]

Si Arang complet n i s'afegeix la hipòtesi que els elements de la diagonal de R1 siguin positius, llavors R1 i Q1 són úniques, però en general Q₂ no ho és. En aquest cas, R1 és igual al factor triangular superior de la factorització de Cholesky de A* A (= ATA si A és real).

Descomposicions QL, RQ i LQ

[modifica]

Anàlogament, es poden definir descomposicions QL, RQ, i LQ, on L és una matriu triangular inferior (de l'anglès lower, inferior).

Càlcul de la descomposició QR

[modifica]

Existeixen diversos mètodes per calcular la descomposició QR, com ara el procés d'ortogonalització de Gram–Schmidt, les transformacions de Householder o les rotacions de Givens. Cadascun té els seus avantatges i els seus desavantatges.

Mètode de Gram–Schmidt

[modifica]

Considerem el procés d'ortogonalització de Gram–Schmidt aplicat a les columnes de la matriu de rang complet per columnes , amb el producte escalar (o pel cas complex).

Definim la projecció

Llavors:

Reescrivim ara les equacions anteriors de tal manera que els termes apareguin a l'esquerra, emprant el fet que els vectors són unitaris:

on . Això es pot escriure en forma matricial:

on:

Exemple

[modifica]

Considerem la descomposició de

Recordem que una matriu ortogonal té la propietat

Aleshores, podem calcular mitjançant Gram–Schmidt de la manera següent:

Així, tenim

Relació amb la descomposició RQ

[modifica]

La descomposició RQ transforma una matriu A en el producte d'una matriu triangular superior R per una matriu ortogonal Q. L'única diferència amb la descomposició QR és l'ordre d'aquestes matrius.

La descomposició QR és l'ortogonalització de Gram–Schmidt de les columnes d'A, començant des de la primera columna.

La descomposició RQ és l'ortogonalització de Gram–Schmidt de les files d'A, començant des de l'última fila.

Ús de transformacions de Householder

[modifica]
Transformació de Householder per una descomposició QR: l'objectiu és trobar una transformació lineal que canviï el vector en un vector de la mateixa longitud i que sigui col·lineal a . Podríem usar una projecció ortogonal (Gram-Schmidt), però això podria ser numèricament inestable si els vectors i són gairebé ortogonals. En lloc d'això, la transformació de Householder calcula la reflexió per la línia de punts (que és la bisectriu de l'angle entre i ). L'angle màxim amb aquesta transformació és de 45 graus.

Una transformació de Householder és una transformació que pren un vector i en calcula la reflexió per un pla o hiperplà. Podem usar aquesta operació per calcular la descomposició QR d'una matriu m×n on mn.

Q es pot usar per reflectir un vector de tal manera que desapareguin totes les seves coordenades menys una.

Sigui un vector columna real qualsevol de dimensió m d' tal que |||| = |α| per un escalar α. Si l'algorisme s'implementa mitjançant aritmètica de coma flotant, llavors α haurà de tenir el signe contrari de la k-sima coordenada de , on és la coordenada «pivot»; és a dir, totes les altres coordenades de seran 0 en la forma triangular superior final d'A, sense pèrdua de dígits significatius. En el cas complex, establim

(Stoer & Bulirsch 2002, p. 225) i substituïm la transposició per la transposició conjugada en la construcció de Q que ara veurem.

Llavors, si denotem per el vector (1,0,...,0)T, ||·|| la norma euclidiana i és una matriu identitat m×m, definim:

O, si és complexa,

, amb

on és la transposada conjugada de .

Ara, és una matriu m×m de Householder i

Aquest procés es pot repetir per transformar gradualment una matriu A m×n en forma triangular superior. Primer, multipliquem A per la matriu de Householder Q1 obtinguda quan escollim que x sigui la primera columna de la matriu. Això resulta en una matriu Q1A amb zeros a la columna de l'esquerra (excepte a la primera fila).

Això es pot repetir per A′ (obtinguda a partir de Q1A eliminant la primera fila i la primera columna), la qual cosa resulta en una matriu de Householder Q′₂. Notem que Q′₂ és més petita que Q1. Com que, de fet, volem que operi sobre Q1A en comptes de sobre A′, primer necessitem ampliar-la per l'extrem superior esquerre, amb un 1, o en general:

Després de iteracions d'aquest procés, on ,

és una matriu triangular superior. Així doncs, si denotem

tenim que és una descomposició QR d'.

Aquest mètode té millor estabilitat numèrica que el mètode de Gram–Schmidt que hem vist abans.

La següent taula mostra el nombre d'operacions en el pas k-sim de la descomposició QR per transformacions de Householder, suposant una matriu quadrada de dimensió n.

Operació Nombre d'operacions en el pas k-sim
multiplicacions
sumes
divisions
arrels quadrades

Sumant aquests nombres pels passos (per a una matriu quadrada de dimensió n), la complexitat de l'algorisme (en termes de multiplicacions en coma flotant) ve donada per

Exemple

[modifica]

Calculem la descomposició de

Primer, hem de trobar una reflexió que transformi la primera columna d'A, el vector , en

Ara,

i

Aquí,

i

Per tant,

i , i llavors

Notem ara que:

de tal manera que tenim gairebé una matriu triangular. Només hem de posar a zero l'entrada (3, 2).

Prenem el menor (1, 1), i apliquem de nou el procés per

Pel mateix mètode que hem vist abans, obtenim la matriu de la transformació de Householder

després de realitzar una suma directa amb 1 per assegurar que el següent pas del procés funciona correctament.

Trobem

Llavors

La matriu Q és ortogonal, i R és triangular superior; per tant, A = QR és la descomposició QR que volíem.

Ús de rotacions de Givens

[modifica]

Hom pot calcular també una descomposició QR mitjançant rotacions de Givens. Cada rotació fa que un element de la subdiagonal de la matriu quedi a zero, formant així la matriu R. La concatenació de totes les rotacions de Givens forma la matriu ortogonal Q.

A la pràctica, per calcular les rotacions de Givens no es construeix la matriu sencera i es realitza una multiplicació de matrius. En comptes d'això, hom utilitza un procediment que realitza l'equivalent de la multiplicació per les matrius disperses de Givens, sense la feina addicional de tenir en compte els elements dispersos. El procediment de les rotacions de Givens és útil en situacions en què només un nombre relativament petit d'elements han d'esdevinir 0, i es pot paral·lelitzar de forma més senzilla que les transformacions de Householder.

Exemple

[modifica]

Calculem la descomposició de

Primer, necessitem construir una matriu de rotació que posi a zero l'element de l'extrem inferior esquerre, . Construïm aquesta matriu usant el mètode de rotació de Givens, i l'anomenem matriu . Primer rotem el vector , perquè estigui alineat amb l'eix de les X. Aquest vector té un angle . Construïm ara la matriu de rotació ortogonal de Givens, :

I el resultat de té ara un zero a l'entrada .

De forma semblant, podem crear matrius de Givens i , que anul·len els elements de la subdiagonal i , i formant així una matriu triangular . La matriu ortogonal està formada per la concatenació de totes les matrius de Givens . Així, tenim , i la descomposició QR és .

Relació amb el determinant i el producte dels valors propis

[modifica]

Podem usar la descomposició QR per trobar el valor absolut del determinant d'una matriu quadrada. Suposem que una matriu A es descompon com a . Aleshores tenim

Com que Q és unitària, . Per tant,

on són les entrades de la diagonal de R.

Addicionalment, com que el determinant és igual al producte dels valors propis, tenim

on són els valors propis d'.

Podem estendre les propietats anteriors a matrius complexes no quadrades , tot substituint el concepte «valor propi» per «valor singular».

Suposem que tenim una descomposició QR per una matriu no quadrada A:

on és una matriu nul·la i és una matriu unitària.

A partir de les propietats de la descomposició en valors singulars i del determinant d'una matriu, tenim

on són els valors singulars d'.

Notem que els valors singulars d' i són idèntics, encara que els valors propis complexos poden ser diferents. Tot i això, si A és quadrada, es compleix que

És a dir, la descomposició QR es pot usar de forma eficient per calcular el producte dels valors propis o els valors singulars d'una matriu.

Ús de pivot per columnes

[modifica]

La descomposició QR amb pivots per columnes introdueix una matriu permutació P:

o, equivalentment,

El pivot per columnes és útil quan Arang deficient (o gairebé deficient), o bé quan hom sospita que pot ser-ho. També pot millorar la precisió numèrica. Habitualment s'escull la matriu P de tal manera que els elements de la diagonal de R siguin no-creixents: . Aquest mètode es pot usar per trobar el rang (numèric) d'A amb un cost computacional menor que el d'una descomposició en valors singulars; de fet, aquesta és la base dels anomenats algorismes QR reveladors del rang.

Resolució de problemes de la inversa lineal

[modifica]

En comparació al càlcul directe de la inversa d'una matriu, les solucions per la inversa que utilitzen la descomposició QR són numèricament més estables, atès que tenen un nombre de condició més reduït [Parker, Geophysical Inverse Theory, Ch1.13].

Per resoldre el sistema d'equacions lineals subdeterminat () on la matriu A té dimensions i rang , primer trobem la descomposició QR de la transposada d'A: , on Q és una matriu ortogonal (és a dir, ), i R té una forma especial: . Aquí, és una matriu triangular superior quadrada , i la matriu nul·la té dimensió . Després d'alguns càlculs, hom pot demostrar que una solució al problema de la matriu inversa es pot expressar com:

on, per trobar es pot fer servir el mètode de reducció de Gauss o bé calcular directament per substitucions endavant. Aquesta última tècnica té major precisió numèrica i necessita menys càlculs.

Per trobar una solució, , al sistema sobredeterminat () que minimitzi la norma , trobem primer la descomposició QR d'A: . Ara, hom pot expressar la solució com , on és una matriu que conté les primeres columnes de la base ortonormal completa , i on és com abans. De la mateixa manera que en el cas subdeterminat, hom pot fer servir substitucions enrere per calcular aquest sense haver d'invertir de forma explícita.

Referències

[modifica]
  1. 1,0 1,1 1,2 L. N. Trefethen and D. Bau, Numerical Linear Algebra (SIAM, 1997).

Vegeu també

[modifica]

Bibliografia

[modifica]

Enllaços externs

[modifica]
  • LAPACK users manual proporciona detalls de subrutines per calcular la descomposició QR
  • ALGLIB inclou un port parcial de LAPACK a C++, C#, Delphi, etc.
  • Eigen::QR Inclou una implementació en C++ de la descomposició QR