Metodo delle potenze

Da Wikipedia, l'enciclopedia libera.

Il metodo delle potenze è un semplice metodo iterativo per il calcolo approssimato dell'autovalore di modulo massimo di una matrice e il corrispondente autovettore.

Il metodo[modifica | modifica wikitesto]

Sia diagonalizzabile con autovalori tali che

Fissato un vettore arbitrario , si genera la successione per

Si può allora dimostrare che la successione degli tende all'autovettore relativo all'autovalore di modulo massimo

Convergenza[modifica | modifica wikitesto]

Siccome è per ipotesi diagonalizzabile, esiste una base di autovettori .

Allora il vettore può essere riscritto come

e conseguentemente, per la definizione di autovalore di una matrice, il risultato della k-esima iterazione come:

.

Adesso, per comodità denotazionale, spostiamo gli indici da pedice in apice: e

Indicando con e le componenti r-esime dei vettori e , per gli indici per cui e si ha:

E poiché per si ha:

Quindi da un certo indice in poi l'autovalore può essere approssimato con il rapporto indicato.

Con questo metodo si può approssimare anche l'autovettore . Infatti si ha:

E passando al limite:

Che sarebbe l'autovettore opportunamente normalizzato.

Implementazione[modifica | modifica wikitesto]

Il metodo delle potenze non viene praticamente mai implementato nella formulazione data, poiché dopo pochi passi si potrebbero avere problemi di underflow o overflow. Per evitare questi problemi è necessario eseguire ad ogni passo una normalizzazione del vettore ottenuto, costruendo una successione per così definita

Dove è uno scalare tale che (tipicamente si prende la norma due di )

Utilizzi[modifica | modifica wikitesto]

Il metodo delle potenze è scarsamente utilizzato poiché permette il calcolo dei soli autovalori e autovettori dominanti. Trova però degli impieghi in specifici problemi: ad esempio è alla base del metodo utilizzato da Google per il proprio algoritmo di PageRank.[senza fonte]

Varianti[modifica | modifica wikitesto]

Esistono numerose varianti del metodo delle potenze. La più famosa è quella del metodo delle potenze inverse che permette il calcolo approssimato dell'autovalore in modulo minore e del rispettivo autovettore. L'algoritmo si basa sull'osservazione che l'autovalore minore in modulo di una matrice, sarà l'autovalore dominante della matrice inversa.

Per il calcolo di un autovalore di modulo compreso fra il massimo ed il minimo autovalore si può invece utilizzare il metodo delle potenze inverse con shift, abbinato ai Teoremi di Gerschgorin sulla localizzazione degli autovalori: modificando la matrice tramite un parametro μ, il metodo trova l'autovalore di modulo più prossimo al valore del parametro.

Riferimenti[modifica | modifica wikitesto]

  • D. Bini, M. Capovani, O. Menchi (1988): Metodi Numerici per l'Algebra Lineare, Zanichelli, ISBN 88-08-06438-7
Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica