Metodo QR

Questa voce o sezione sull'argomento matematica è ritenuta da controllare.

Motivo: Descrizione poco contestualizzata

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.

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

${\displaystyle A_{k}=Q_{k}R_{k}}$

dove ${\displaystyle Q_{k}}$ è unitaria ovvero vale che ${\displaystyle Q_{k}^{H}Q_{k}=Q_{k}Q_{k}^{H}=I}$, ed ${\displaystyle R_{k}}$ è triangolare superiore. Si definisce ${\displaystyle A_{k+1}}$ come segue:

${\displaystyle 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 ${\displaystyle \{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 ${\displaystyle A}$. Nel caso in cui ${\displaystyle A}$ è hermitiana, la successione converge ad una matrice diagonale.

Vale il seguente teorema, detto teorema di convergenza.

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

${\displaystyle \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 ${\displaystyle T}$ è una matrice tridiagonale superiore che ha sulla diagonale principale gli autovalori di ${\displaystyle A}$,

e ${\displaystyle \lim _{k\rightarrow \infty }{S_{k-1}^{H}Q_{k}S_{k}}=I}$.

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

Nel caso in cui la matrice ${\displaystyle 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 ${\displaystyle \lambda _{i},i=1,2,...,n}$ non risultino distinti.

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

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

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

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

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

Quando questa condizione è verificata

${\displaystyle A_{k}={\begin{pmatrix}B_{k}\ D_{k}\\E_{k}\ C_{k}\end{pmatrix}}}$

dove ${\displaystyle B_{k}\in \mathbb {C} ^{p\times p}}$, ${\displaystyle C_{k}\in \mathbb {C} ^{(n-p)\times (n-p)}}$ ed ${\displaystyle E_{k}}$ ha un elemento di modulo molto piccolo e tutti gli altri nulli. Si procede operando separatamente con le matrici ${\displaystyle B_{k}}$ e ${\displaystyle C_{k}}$.

La velocità di convergenza del metodo dipende dal rapporto ${\displaystyle \left\vert {\frac {\lambda _{i}}{\lambda _{j}}}\right\vert }$ per ${\displaystyle i>j}$ e quindi, per l'ipotesi ${\displaystyle |\lambda _{1}|>|\lambda _{2}|>...>|\lambda _{n}|}$, dipende dal numero

${\displaystyle \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 ${\displaystyle \mu }$ un valore che approssima un autovalore ${\displaystyle \lambda }$ meglio degli altri. Si può applicare il metodo QR alla matrice ${\displaystyle A-\mu I}$ come segue

${\displaystyle A_{k}-\mu I=Q_{k}R_{k}}$

${\displaystyle A_{k+1}=R_{k}Q_{k}+\mu I}$

e risulta ${\displaystyle Q_{k}A_{k+1}=A_{k}Q_{k}}$.

Tenendo presente che gli autovalori di ${\displaystyle A-\mu I}$ sono ${\displaystyle \lambda _{i}-\mu }$ è possibile scegliere ${\displaystyle \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 ${\displaystyle \mu =a_{n,n}^{(p)}}$ per le successive iterazioni con shift. Dal momento che ${\displaystyle \mu }$ può essere modificato ad ogni iterazione risulta conveniente scegliere ${\displaystyle \mu _{k}=a_{n,n}^{(k)},\ k=1,2,...}$

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica