Metodo della potenza

Autovalore di modulo massimo[modifica | modifica wikitesto]

Supponiamo che l'autovalore di modulo massimo sia strettamente maggiore dell'autovalore successivo, cioè

si esclude quindi il caso in cui è un autovalore complesso (e avrebbe modulo uguale a quello del suo coniugato) o in cui ha molteplicità maggiore di 1 (non sarebbe strettamente maggiore di se stesso).

Supponiamo che esistano autovettori linearmente indipendenti, che formano una base.

Considero un vettore

rappresentato nella base degli autovettori. Richiedo che nella scrittura di ci sia un contributo dell'autovettore relativo all'autovalore, cioè .
Genero una successione di vettori tali che
Allora sostituendo a la rappresentazione ottengo:
e siccome gli sono autovettori posso scrivere:
e raccogliendo :
, allora per , .

Definisco il quoziente di Rayleigh:

Verifichiamo che . Sostituisco l'espressione di nel che ho definito:
Per i termini , mentre i termini si semplificano e rimane:
Sul calcolatore il problema compare nella divisione per , perché si rischia di andare nella barriera di overflow o di underflow. Per risolvere il problema, invece di considerare , lo si normalizza in norma 2 cioè si considera:
e in questo modo nel quoziente di Rayleigh si divide per un vettore di norma 1.

Implementazione dell'algoritmo[modifica | modifica wikitesto]

Dato , eseguo le seguenti operazioni:

e se una certa condizione imposta nel test d'arresto non è verificata, si procede.

Il costo è dato da operazioni del prodotto matrice-vettore, e operazioni per i prodotti scalari nelle norme.

, cioè la velocità con cui converge a è come il rapporto tra , e se i due autovalori sono ben separati il metodo converge rapidamente.

Il metodo converge anche se l'autovalore di modulo massimo non ha molteplicità algebrica uguale a 1, in particolare:

  1. . I due (o ) autovalori dominanti sono coincidenti. In questo caso il metodo risulta ancoraconvergente, ma converge ad un vettore nel sottospazio generato da e ;
  2. . I due autovalori dominanti sono opposti. In questo caso l'autovalore di modulomassimo può essere approssimato applicando il metodo delle potenze alla matrice , inmodo che e l'analisi ricada nel punto precedente;
  3. I due autovalori dominanti sono complessi coniugati. In questo caso si hannodelle oscillazioni non smorzate nella sequenza dei vettori e il metodo delle potenzenon converge.

non è un'ipotesi essenziale se si lavora in aritmetica floating point.

Test di arresto[modifica | modifica wikitesto]

Test dell'incremento: richiedo che

e il metodo prosegue fino a quando questa condizione non è verificata.
Nel caso in cui è una matrice normale, cioè , posso considerare altri due test d'arresto.

Proposizione 3.1

Supponiamo di avere normale, consideriamo , e razionale definita su un sottoinsieme del piano complesso che contiene tutti gli autovalori di . Allora esiste tale che

 

Test 1: Impongo la condizione

che permette di avere un controllo sull'errore assoluto.
Infatti, se scelgo la funzione (errore assoluto) e , allora, per la proposizione:
ma per costruzione, allora
Test 2: se è normale e non singolare, allora la condizione
permette di controllare l'errore relativo.

Scelgo (errore relativo), e pongo , applico poi la proposizione:

 PrecedenteSuccessivo