Calcolo numerico/Metodo della potenza inversa

Autovalore di modulo minimo

Il metodo della potenza inversa serve a calcolare l'autovalore e autovettore di modulo minimo. Si richiede che l'autovalore di modulo minimo sia strettamente maggiore di tutti gli altri, cioè

$|\lambda _{1}|\geq |\lambda _{2}|\geq \dots \geq |\lambda _{n-1}|>|\lambda _{n}|$

Considerando $\lambda$ autovalore di $A$ segue che:

$A{\boldsymbol {x}}=\lambda {\boldsymbol {x}}\,\longrightarrow \,A^{-1}\lambda {\boldsymbol {x}}={\boldsymbol {x}}\,\longrightarrow \,A^{-1}{\boldsymbol {x}}={\frac {1}{\lambda }}{\boldsymbol {x}},$

cioè se $\lambda$ è autovalore di $A$, $1/\lambda$ è autovalore di $A^{-1}$.

Allora

$\min _{i=1}^{n}\{|\lambda (A)|\}=\min _{i=1}^{n}{\frac {1}{|\lambda _{i}(A^{-1})|}}$

$={\frac {1}{\max\{\lambda _{i}(A^{-1})\}}}$

Ma per calcolare l'autovalore di modulo massimo si può applicare il metodo della potenza alla matrice inversa $A^{-1}$, e basta poi fare il reciproco dell'autovalore trovato.

Algoritmo del metodo

Dato ${\boldsymbol {z}}_{0}$, applichiamo il seguente algoritmo:

${\boldsymbol {y}}_{k}={\frac {{\boldsymbol {z}}_{k}}{\vert {\boldsymbol {z}}_{k}\vert }}$

${\boldsymbol {z}}_{k+1}=A^{-1}{\boldsymbol {y}}_{k}$

$\sigma _{k}={\boldsymbol {y}}_{k}^{h}{\boldsymbol {z}}_{k+1}$

${test\,d'arresto}$

$\lambda _{min}={\frac {1}{\sigma }}$

Si presenta il problema del calcolo dell'inversa $A^{-1}$, che è mal condizionato. Allora invece di calcolare il prodotto matrice per vettore

${\boldsymbol {z}}_{k+1}=A^{-1}{\boldsymbol {y}}_{k}$

risolvo il sistema

$A{\boldsymbol {z}}_{k+1}={\boldsymbol {y}}_{k}$

e per farlo uso la fattorizzazione $PA=LU$. I vettori ${\boldsymbol {y}}_{k}$ vengono trovato nelle successive iterazioni, ma la fattorizzazione $PA=LU$ dopo essere stata trovata nel primo passo viene sfruttata per tutte le iterazioni successive.

Calcolo dell'autovalore più vicino ad $\alpha$

Supponiamo di avere un valore assegnato $\alpha$: per calcolare l'autovalore di $A$ più vicino a esso applichiamo il metodo delle potenze a $B$ data da $(A-\alpha I)^{-1}$.

$\lambda _{i}(B)={\frac {1}{\lambda _{i}(A-\alpha I)}}={\frac {1}{\lambda _{i}(A)-\alpha }}$

otteniamo $\sigma _{k}\to {\frac {1}{\lambda (A)-\alpha }}$, allora $\lambda \to {\frac {1}{\sigma _{k}}}+\alpha$.

Algoritmo:

${\boldsymbol {y}}_{k}={\frac {{\boldsymbol {z}}_{k}}{\vert {\boldsymbol {z}}_{k}\vert }}$

${\boldsymbol {z}}_{k+1}=B{\boldsymbol {y}}_{k}\quad {\hbox{passaggio problematico, sostituito con }}(A-\alpha I){\boldsymbol {z}}_{k+1}={\boldsymbol {y}}_{k}$

$\sigma _{k}={\boldsymbol {y}}_{k}^{h}{\boldsymbol {z}}_{k+1}$

Test d'arresto:

$\sigma _{k}=1/\sigma _{k}+\alpha$