Algoritme QR

El algoritme QR és un algoritme usat en àlgebra llineal per al càlcul de valors i vectores propis d'una matriu.

Es basa en la descomposició QR, desenrollada en la década de 1950 per John G.F. Francis (Regne Unit) i Vora N. Kublánovskaya (URSS), de forma independent. Açò és, usa l'oportunitat de representar qualsevol matriu regular H en forma de producte de $H=QR$ d'una matriu ortogonal Q per una matriu triangular superior R. L'idea bàsica és usar dita descomposició per a reescriure la matriu com el producte d'una matriu ortogonal i una matriu triangular superior. Si es multiplica a l'inversa, la matriu resultant seguix tenint els mateixos valors propis i iterando es pot aplegar a una matriu que els continga en la diagonal.

Descripció de l'algoritme

Formalment, siga A una matriu real de la que volem calcular els valors propis, s'assigna A₀:=A. En avant es calculen les següents iteraciones de forma:

• A_k=Q_kR_k a onQ_k és una matriu ortogonal i R_k és una matriu triangular superior.
• A_k+1 = R_kQ_k. S'ha de notar que

$A_{k+1}=R_k{Q}_k=Q_k^T{Q}_k{R}_k{Q}_k=Q_k^T{A}_k{Q}_k=Q_k^{-1}{A}_k{Q}_k,$

després totes les A_k són matrius semblants i per tant tenen els mateixos valors propis. L'algoritme és numèricament estable perque opera per transformacions ortogonals.

Baixe certes condicions les matrius A_k convergixen a una matriu triangular que és la triangulació de Schur de A. Ya que els valors propis d'una matriu triangular estan llistats en la seua diagonal, es poden obtindre directament llavors. Comprovar la seua convergència és impráctico, pero es pot acotar l'error pel Teorema de Gerschgorin.

Interpretació

L'algoritme QR es pot considerar una versió més sofisticada del método de les potències. Abdós métodos multipliquen repetidament un vector per la matriu de la que es volen conéixer els valors propis, normalisant despuix de cada iteración. Aixina est convergix als valors desijats.

No obstant, mentres que el método de les potències solament proporciona el major dels valors propis, el método QR usa la descomposició homònima per a normalisar i ortogonalizar despuix de cada iteración. Aixina per al valor final quan convergix AQ=QΛ s'obté la matriu diagonal Λ que conté tots els valors propis i per tant Q queda en els vectores propis en les columnes.