Metodo QR

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca

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

[modifica | modifica wikitesto]

Nel metodo QR viene generata una successione di matrici nel modo seguente: posto , si calcola una fattorizzazione QR di .

dove è unitaria ovvero vale che , ed è triangolare superiore. Si definisce come segue:

pertanto le matrici della successione 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 . Nel caso in cui è hermitiana, la successione converge ad una matrice diagonale.

Risultati di convergenza

[modifica | modifica wikitesto]

Vale il seguente teorema, detto teorema di convergenza.

Sia una matrice diagonalizzabile tale che i suoi autovalori abbiano tutti modulo distinto, cioè . Indichiamo con la matrice degli autovettori di tale che la sua inversa ammetta una fattorizzazione LU. Sia inoltre una matrice diagonale, sulla cui diagonale principale vi sono gli autovalori di . Allora esistono delle matrici di fase tali che:

, dove è una matrice tridiagonale superiore che ha sulla diagonale principale gli autovalori di ,

e .


Questo teorema garantisce che gli elementi della successione tendano agli autovalori di .

Nel caso in cui la matrice 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 non risultino distinti.

Costo computazionale e stabilità

[modifica | modifica wikitesto]

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

Condizioni di arresto

[modifica | modifica wikitesto]

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

Fissata una tolleranza , si procede applicando il metodo QR ad una matrice in forma di Hessenberg superiore fino a quando per un indice , con , non risulti soddisfatta la seguente espressione:

ovvero fino a quando diventa sufficientemente piccolo.

Quando questa condizione è verificata

dove , ed ha un elemento di modulo molto piccolo e tutti gli altri nulli. Si procede operando separatamente con le matrici e .

Tecnica di shift

[modifica | modifica wikitesto]

La velocità di convergenza del metodo dipende dal rapporto per e quindi, per l'ipotesi , dipende dal numero

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

e risulta .

Tenendo presente che gli autovalori di sono è possibile scegliere 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 per le successive iterazioni con shift. Dal momento che può essere modificato ad ogni iterazione risulta conveniente scegliere

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