Metodo QR

Template:Da controllare Il metodo QR è il metodo più utilizzato per il calcolo degli autovalori e degli autovettori di una matrice diagonalizzabile. Il metodo è molto complesso sia nella descrizione che nell'implementazione, ma il principio su cui si basa, ovvero la fattorizzazione QR, è molto semplice.

Algoritmo di base

Nel metodo QR viene generata una successione $\{A_k{\}}_{k=1,2,...}$ di matrici nel modo seguente: posto $A_1=A$, si calcola una fattorizzazione QR di $A_k$.

$A_k=Q_k{R}_k$

dove $Q_k$ è unitaria ovvero vale che $Q_k^H{Q}_k=Q_k{Q}_k^H=I$, ed $R_k$ è triangolare superiore. Si definisce $A_{k+1}$ come segue:

$A_{k+1}=R_k{Q}_k=Q_k^H{Q}_k{R}_k{Q}_k=Q_k^H{A}_k{Q}_k$

pertanto le matrici della successione $\{A_k{\}}_{k=1,2,...}$ sono tutte simili tra loro. Sotto opportune ipotesi la successione converge ad una matrice triangolare superiore che sulla diagonale principale ha gli autovalori della matrice $A$. Nel caso in cui $A$ è hermitiana, la successione converge ad una matrice diagonale.

Risultati di convergenza

Vale il seguente teorema, detto teorema di convergenza.

Sia $A\in {ℂ}^{n\times n}$ una matrice diagonalizzabile tale che i suoi autovalori ${\lambda }_i,i=1,2,...,n$ abbiano tutti modulo distinto, cioè $|{\lambda }_1|>|{\lambda }_2|>...>|{\lambda }_n|>0$. Indichiamo con $X$ la matrice degli autovettori di $A$ tale che la sua inversa $X^{-1}$ ammetta una fattorizzazione LU. Sia inoltre $D=X^{-1}AX=diag({\lambda }_i)$ una matrice diagonale, sulla cui diagonale principale vi sono gli autovalori di $A$. Allora esistono delle matrici di fase $S_k$ tali che:

$\underset{k\to \mathrm{\infty }}{\lim }{S}_k^H{R}_k{S}_k^{-1}=\underset{k\to \mathrm{\infty }}{\lim }{S}_{k-1}^H{A}_k{S}_{k-1}=T$ , dove $T$ è una matrice tridiagonale superiore che ha sulla diagonale principale gli autovalori di $A$,

e $\underset{k\to \mathrm{\infty }}{\lim }{S}_{k-1}^H{Q}_k{S}_k=I$.

Questo teorema garantisce che gli elementi della successione $\{A_k{\}}_{k=1,2,...}$ tendano agli autovalori di $A$.

Nel caso in cui la matrice $X^{-1}$ non fosse fattorizzabile in forma LU, il metodo QR risulterebbe comunque convergente, ma gli autovalori non sarebbero stampati in ordine decrescente, cosa che invece accade se questa ipotesi è verificata.

Con opportune modifiche è possibile dimostrare la convergenza del metodo anche nei casi in cui gli autovalori ${\lambda }_i,i=1,2,...,n$ non risultino distinti.

Costo computazionale e stabilità

Il metodo QR applicato ad una matrice di ordine n ha un costo computazionale di $n^3$ operazioni moltiplicative. Per abbassare il costo computazionale è possibile trasformare la matrice $A$ in forma di Hessenberg superiore. In questo caso si ha un costo di $2n^2$ operazioni moltiplicative. Nel caso di una matrice in forma tridiagonale questo si riduce ulteriormente e risulta lineare in n.

Condizioni di arresto

Il metodo QR è un metodo di tipo iterativo, pertanto è opportuno fissare delle condizioni di arresto per tale metodo.

Fissata una tolleranza $\epsilon$, si procede applicando il metodo QR ad una matrice $A$ in forma di Hessenberg superiore fino a quando per un indice $p$, con $1\le p\le n$, non risulti soddisfatta la seguente espressione:

$|(a_{p+1,p}^{(k)})|<\epsilon (|(a_{p,p}^{(k)})|+|(a_{p+1,p+1}^{(k)})|)$

ovvero fino a quando $(a_{p+1,p}{)}^{(k)}$ diventa sufficientemente piccolo.

Quando questa condizione è verificata

$A_k=\left(\begin{array}{c}{B}_k{D}_k\\ E_k{C}_k\end{array}\right)$

dove $B_k\in {ℂ}^{p\times p}$, $C_k\in {ℂ}^{(n-p)\times (n-p)}$ ed $E_k$ ha un elemento di modulo molto piccolo e tutti gli altri nulli. Si procede operando separatamente con le matrici $B_k$ e $C_k$.

Tecnica di shift

La velocità di convergenza del metodo dipende dal rapporto $\left|\frac{{\lambda }_i}{{\lambda }_j}\right|$ per $i>j$ e quindi, per l'ipotesi $|{\lambda }_1|>|{\lambda }_2|>...>|{\lambda }_n|$, dipende dal numero

$\underset{1\le i\le n-1}{\max }\left|\frac{{\lambda }_{i+1}}{{\lambda }_i}\right|$

Se tale rapporto è vicino a 1 la convergenza risulta lenta. Per accelerare la convergenza si utilizza una tecnica di shift. Sia $\mu$ un valore che approssima un autovalore $\lambda$ meglio degli altri. Si può applicare il metodo QR alla matrice $A-\mu I$ come segue

$A_k-\mu I=Q_k{R}_k$

$A_{k+1}=R_k{Q}_k+\mu I$

e risulta $Q_k{A}_{k+1}=A_k{Q}_k$.

Tenendo presente che gli autovalori di $A-\mu I$ sono ${\lambda }_i-\mu$ è possibile scegliere $\mu$ in modo da accelerare la velocità di convergenza. In genere si applica il metodo QR senza shift per i primi p passi e si sceglie $\mu =a_{n,n}^{(p)}$ per le successive iterazioni con shift. Dal momento che $\mu$ può essere modificato ad ogni iterazione risulta conveniente scegliere ${\mu }_k=a_{n,n}^{(k)},k=1,2,...$