The QR algorithm §

The QR algorithm for computing eigenvalues is one of the best known algorithms in numerical analysis. It was developed by G.F. Francis in the $1950$s.

The QR algorithm efficiently provides approximations for all eigenvalues and eigenvectors of a matrix.

Versione base §

$A^0=A$ For $k=1,2,\dots$ $A^{k-1}=Q^k{R}^k$ $A^k=R^k{Q}^k$ End

Osservazione Per costruzione le matrici $A^{k-1}$ e $A^k$ sono unitariamente simili:

$$A^k=R^k{Q}^k$$

moltiplicando a sinistra per $Q^k$ e a destra per ${Q^k}^H$ :

$$Q_k^H{A}^k{Q}_k=A^{k-1}$$

Anche questa versione semplice dell’algoritmo realizza numericamente una Decomposizione di Schur della matrice $A$, ovver la successione $\{A^k\}\to U$. Tale schema è stato raffinato, sia per indebolire le condizioni necessarie per la convergenza che per aumentarne la rapidità.

Prima variante §

Il primo migioramento consiste nel trasformare la matrice $A$ in una matrice $H$ di hessemberg superiore unitariamente simile (per preservare lo spettro). L’idea è che ora si devono annullare solo gli $n-1$ elementi della sottodiagonale.

Inoltre ad ogni passo si effettueranno solo $O(n^2)$ operazioni contro le $O(n^3)$ necessarie per la fattorizzazione QR e il prodotto tra matrici.

Inoltre se $A$ è hermitiana, $H$ è tridiagonale, dunque le operazioni si riducono a $O(n)$.

Teorema Se gli autovalori di $A$ hanno tutti moduli distinti, ovvero $|{\lambda }_1|>|{\lambda }_2|>\cdots >|{\lambda }_n|$, allora la successione $\{H^k\}\to U$. La velocità di convergenza a zero degli $n-1$ elementi sottodiagonali di $H^k$, chiamati $h_{i,i-1}^k$ $i=2,\dots ,n$ è data da:

$$|h_{i,i-1}^k|=O\left({\left|\frac{{\lambda }_i}{{\lambda }_{i-1}}\right|}^k\right)$$

Seconda variante: shift e deflazione §

Il teorema precedente mostra come la velocità di convergenza del metodo QR dipende da quanto sono ben separati gli autovalori. Con il seguente accorgimento è possibile incrementare la velocità di convergenza.

Shift §

Assumiamo di avere per ogni iterazione uno shift ${\mu }_k$. Lo schema con shift: $H^0=Q^{H}AQ$ For $k=1,2,\dots$ $H^{k-1}-{\mu }_{k}I=Q^k{R}^k$ $H^k=R^k{Q}^k+{\mu }_{k}I$ End

le matrici $H^k$ continuano ad essere unitariamente simili.

Troviamo un ${\mu }_k$ ottimale ad ogni passo. Euristicamente, siccome la convergenza è dal basso verso l’alto, la migliore stima di ${\lambda }_n$ si ha per l’elemento $h_{n,n}^k$.

Lo shift viene chiamato così perchè shifta lo spettro. Dunque la velocità di convergenza, per il teorema precedente, risulta:

$$|h_{n,n-1}^k|=O\left({\left|\frac{{\lambda }_n-{\mu }_k}{{\lambda }_{n-1}-{\mu }_k}\right|}^k\right)$$

quindi abbiamo reso piccolo il numeratore. Come condizione di stop controlliamo che l’elemento $h_{n,n-1}^k$ sia abbastanza piccolo:

$$|h_{n,n-1}^k|<ϵ(|h_{n-1,n-1}^k|+|h_{n,n}^k|)$$

Si può dimostrare che la convergenza a zero è quadratica.

Deflazione §

Giunti a convergenza, la strategia della deflazione si traduce nell’applicare la medesima procedura alla matrice ridotta (ovvero porre in maniera ricorsiva $n\to n-1$ fino a $n=2$.