Metodo QR

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 \mathbb {C} ^{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:

$\lim _{k\rightarrow \infty }{S_{k}^{H}R_{k}S_{k}^{-1}}=\lim _{k\rightarrow \infty }{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 $\lim _{k\rightarrow \infty }{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 $\varepsilon$, si procede applicando il metodo QR ad una matrice $A$ in forma di Hessenberg superiore fino a quando per un indice $p$, con $1\leq p\leq n$, non risulti soddisfatta la seguente espressione:

$|(a_{p+1,p}^{(k)})|<\varepsilon (|(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}={\begin{pmatrix}B_{k}\ D_{k}\\E_{k}\ C_{k}\end{pmatrix}}$

dove $B_{k}\in \mathbb {C} ^{p\times p}$, $C_{k}\in \mathbb {C} ^{(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\vert {\frac {\lambda _{i}}{\lambda _{j}}}\right\vert$ per $i>j$ e quindi, per l'ipotesi $|\lambda _{1}|>|\lambda _{2}|>...>|\lambda _{n}|$, dipende dal numero

$\max _{1\leq i\leq n-1}\left\vert {\frac {\lambda _{i+1}}{\lambda _{i}}}\right\vert$

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,...$