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|\ge |{\lambda }_2|\ge \dots \ge |{\lambda }_{n-1}|>|{\lambda }_n|$

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

$A𝒙=\lambda 𝒙⟶A^{-1}\lambda 𝒙=𝒙⟶A^{-1}𝒙=\frac{1}{\lambda }𝒙,$

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 ${𝒛}_0$, applichiamo il seguente algoritmo:

${𝒚}_k=\frac{{𝒛}_k}{|{𝒛}_k|}$

${𝒛}_{k+1}=A^{-1}{𝒚}_k$

${\sigma }_k={𝒚}_k^h{𝒛}_{k+1}$

$test{d}^{\prime }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

${𝒛}_{k+1}=A^{-1}{𝒚}_k$

risolvo il sistema

$A{𝒛}_{k+1}={𝒚}_k$

e per farlo uso la fattorizzazione $PA=LU$. I vettori ${𝒚}_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:

${𝒚}_k=\frac{{𝒛}_k}{|{𝒛}_k|}$

${𝒛}_{k+1}=B{𝒚}_k\text{passaggio problematico, sostituito con }(A-\alpha I){𝒛}_{k+1}={𝒚}_k$

${\sigma }_k={𝒚}_k^h{𝒛}_{k+1}$

Test d'arresto:

${\sigma }_k=1/{\sigma }_k+\alpha$