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 sorgente]

Sia A\in\mathbb{C}^{n\times n} diagonalizzabile con autovalori \lambda_1, \lambda_2,  \ldots\ , \lambda_n tali che |\lambda_1|>|\lambda_2|\geq\ldots\geq|\lambda_n|

Fissato un vettore arbitrario x_0\in\mathbb{C}^n, si genera la successione  x_k=Ax_{k-1} per  k = 1, 2, \ldots

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

Convergenza[modifica | modifica sorgente]

Siccome A è per ipotesi diagonalizzabile, esiste una base di autovettori v_1, v_2, \ldots, v_n.

Allora il vettore x_0 può essere riscritto come

x_0=\sum_{i=1}^n \alpha_i v_i

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

 x_k=A^k x_{0}=\sum_{i=1}^n \alpha_iA^k v_i=\sum_{i=1}^n \alpha_i\lambda_{i}^{k} v_i .

Adesso, per comodità denotazionale, spostiamo gli indici da pedice in apice:  x_k=x^{(k)} e  x^{(k)}=\sum_{i=1}^n \alpha_i\lambda_{i}^{k} v^{(i)}

Indicando con x^{(k)}_r e v^{(i)}_r le componenti r-esime dei vettori x^{(k)} e v^{(i)}, per gli indici j per cui  x^{(k)}_j \ne 0 e  v^{(1)}_j \ne 0 si ha:

 \frac{ x^{(k+1)}_j}{ x^{(k)}_j}=\lambda_1 \frac{\alpha_1 v^{(1)}_j + \sum_{i=2}^n \alpha_i (\frac{\lambda_i}{\lambda_1})^{k+1} v^{(i)}_j}{\alpha_1 v^{(1)}_j + \sum_{i=2}^n \alpha_i (\frac{\lambda_i}{\lambda_1})^k v^{(i)}_j}

E poiché  \frac{\lambda_i}{\lambda_1} < 1 per  i \ge 2 si ha:

\lim_{k\rightarrow \infty} \frac{ x^{(k+1)}_j}{ x^{(k)}_j}=\lambda_1

Quindi da un certo indice k in poi l’autovalore \lambda_1 può essere approssimato con il rapporto indicato.

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

 \frac{ x^{(k+1)}}{ x^{(k)}_j}=\lambda_1 \frac{\alpha_1 v^{(1)} + \sum_{i=2}^n \alpha_i (\frac{\lambda_i}{\lambda_1})^{k+1} v^{(i)}}{\alpha_1 v^{(1)}_j + \sum_{i=2}^n \alpha_i (\frac{\lambda_i}{\lambda_1})^k v^{(i)}_j}

E passando al limite:

\lim_{k\rightarrow \infty} \frac{ x^{(k+1)}}{ x^{(k)}_j}=\frac{v^{(1)}}{v^{(1)}_j} Che sarebbe l’autovettore v^{(1)} opportunamente normalizzato.

Implementazione[modifica | modifica sorgente]

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  x_k=Ax_{k-1} per  k = 1, 2, \ldots così definita


\left\{
\begin{matrix} y_k = Ax_{k-1}  \\x_k = \frac{y_k}{\beta_k}\,\end{matrix}
\right.

Dove  \beta_k è uno scalare tale che \|x_k\| = 1 (tipicamente si prende la norma due di y_k)

Utilizzi[modifica | modifica sorgente]

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.

Varianti[modifica | modifica sorgente]

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 sorgente]

  • 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