z (k) = Aq (k 1) 1. Nel caso in cui ci siano due autovalori di modulo massimo uquale, λ 2 = λ 1 abbiamo:

(1)

Esercitazione 9

Richiami di Teoria

Metodo delle potenze per gli autovalori

Il metodo delle potenze`e un metodo iterativo per il calcolo approssimato dell’autovalore di modulo massimo di una matrice A diagonalizzabile con autovalori |λ¹| > |λ²| ≥ . . . ≥ |λⁿ| ed il corrispondente autovettore.

L’algoritmo si basa sulla seguente idea. Fissato un vettore arbitrario q⁰ ∈ Cⁿ con norma euclidea unitaria, si genera la seguente successione

z^(k) = Aq^(k−1) q^(k)= z^(k)/||z^(k)||² λ^(k)= q^(k)HAq^(k).

Si pu`o allora dimostrare che la successione degli q^(k) tende all’autovettore relativo all’autovalore di modulo massimo x¹ mentre λ^(k), tende all’autovalore di modulo massimo λ1.

Osservazioni relative al metodo delle potenze

1. L’analisi di convergenza mostra che l’efficacia del metodo delle potenze dipende forte- mente dal fatto se l’autovalore dominante sia ben separato, cio`e

λ₂ λ₁

≪ 1. Nel caso in cui ci siano due autovalori di modulo massimo uquale, |λ²| = |λ¹| abbiamo:

(a) λ2 = λ1: I due autovalori dominanti sono coincidenti. In questo caso il metodo

`e ancora convergente e λ^(k) → λ¹ ma q^(k) converge ad un vettore nel sottospazio generato da x¹ e x²;

(b) λ2 = −λ¹: I due autovalori dominanti sono opposti. In questo caso l’autovalore di modulo massimo pu`o essere approssimato applicando il metodo delle potenze alla matrice A², in modo che λ²₂ = λ²₁ e l’analisi ricade nel punto precedente;

(c) λ = λ : I due autovalori dominanti sono complessi coniugati. In questo caso si

(2)

2. Per quanto riguarda l’implementazione al calcolatore vale la pena notare che le norma- lizzazioni dei vettori q^(k) a 1.0 evita gli errori di overflow (quando λ₁ > 1) e underflow (quando λ1 < 1).

3. Un’ulteriore richiesta `e che il vettore iniziale q⁽⁰⁾ = Pn

k=1αkxk abbia una componente α₁ 6= 0 lungo l’autovettore associato all’autovalore di modulo massimo x¹. Infatti, anche se pu`o essere dimostrato che, lavorando in aritmetica esatta, la sequenza q^(k) converge alla coppia (λ2, x²) se α1 = 0 l’insorgere di (inevitabili) errori di arrotondamento assicura che in pratica la successione q^(k)contiene una componente non nulla anche nella direzione di x¹ e questo consente al metodo di convergere verso l’autovalore λ1.

4. Se A `e “difettiva”, cio`e a meno di n autovettori linearmente indipendenti, si dimostra che si ha comunque convergenza (anche se lenta) allautovalore λ₁, a patto che non si abbia λ1 6= λ² con |λ¹| = |λ²|.

Il metodo delle potenze si pu`o pertanto scrivere come (manca un flag per segnalare la convergenza o meno del metodo nel numero massimo di iterazioni):

[λ,q] ← potenze ( A, z⁰, tol, maxiter ) 1 q ← z⁰/||z⁰||²

2 z ← Aq

3 scarto ← tol +1 4 iter ← 0

5 λold ← 0

6 // ciclo di convergenza

7 while scarto ≥ tol and iter < maxiter do 8 iter ← iter +1

9 q← z/||z||2

10 z← Aq

11 λ ← q^Hz

12 scarto ← |λ − λold|/|λ|

13 λold ← λ 14 end

(3)

Esercizio 1

Calcolare l’autovalore dominante ed il corrispondente autovettore utilizzando il metodo delle potenze per le seguenti matrici

A₁ =







4 −1 0 −1 0 0 0 0 0

−1 4 −1 0 −1 0 0 0 0

0 −1 4 0 0 −1 0 0 0

−1 0 0 4 −1 0 −1 0 0

0 −1 0 −1 4 −1 0 −1 0

0 0 −1 0 −1 4 0 0 −1

0 0 0 −1 0 0 4 −1 0

0 0 0 0 −1 0 −1 4 −1

0 0 0 0 0 −1 0 −1 4





 e

A₂ =







2 −1 0 0 0 0 0 0 0 0

−1 2 −1 0 0 0 0 0 0 0

0 −1 2 −1 0 0 0 0 0 0

0 0 −1 2 −1 0 0 0 0 0

0 0 0 −1 2 −1 0 0 0 0

0 0 0 0 −1 2 −1 0 0 0

0 0 0 0 0 −1 2 −1 0 0

0 0 0 0 0 0 −1 2 −1 0

0 0 0 0 0 0 0 −1 2 −1

0 0 0 0 0 0 0 0 −1 2







Per verificare i calcoli si disegni l’andamento al variare dell’iterazione dell’errore relativo commesso dove l’autovalore di modulo massimo e ottenuto attraverso l’utilizzo del comando Ma- tLab eig. Si faccia attenzione alla matrice A². Si consideri come vettore iniziale il vettore z0 = (1, 1, . . . , 1)^T.

Si commentino i risultati.

Nota: La prima matrice pu`o essere generata mediante il comando MatLab:

A1=full(gallery(’poisson’,3)).

(4)

Risultati

0 10 20 30 40 50 60 70 80

10⁻¹⁶ 10⁻¹⁴ 10⁻¹² 10⁻¹⁰ 10⁻⁸ 10⁻⁶ 10⁻⁴ 10⁻² 10⁰

Andamento dello scarto relativo tra due iterate

0 200 400 600 800 1000 1200

10⁻¹⁶ 10⁻¹⁴ 10⁻¹² 10⁻¹⁰ 10⁻⁸ 10⁻⁶ 10⁻⁴ 10⁻² 10⁰

Andamento errore relativo

Figura 1: Esercizio 1: Matrice A1.

0 200 400 600 800 1000 1200

10⁻¹⁶ 10⁻¹⁴ 10⁻¹² 10⁻¹⁰ 10⁻⁸ 10⁻⁶ 10⁻⁴ 10⁻² 10⁰

Andamento dello scarto relativo tra due iterate

0 200 400 600 800 1000 1200

10⁻¹⁶ 10⁻¹⁴ 10⁻¹² 10⁻¹⁰ 10⁻⁸ 10⁻⁶ 10⁻⁴ 10⁻² 10⁰

Andamento errore relativo

Figura 2: Esercizio 1: Matrice A2.

(5)

Esercizio 2

Si consideri al variare del parametro α la seguente matrice

A=







1 1 0 2 3 0 6 6 α







Calcolare al variare di α ∈ (2 − √

3, 2 +√

3) l’autovalore di modulo massimo. Riportare in un grafico il numero di iterazioni richieste. Si consideri come vettore iniziale il vettore z0 = (1, 1, . . . , 1)^T.

Risultati

0 0.5 1 1.5 2 2.5 3 3.5 4

0 20 40 60 80 100 120

Valore di a

Iterazioni eseguite

0 0.5 1 1.5 2 2.5 3 3.5 4

3.73 3.735 3.74 3.745 3.75 3.755 3.76 3.765 3.77 3.775

Valore di a

Autovalore dominante

vero calcolato

Figura 3: Esercizio 2: Soluzione.

(6)

Esercizio 3

Utilizzare il metodo delle potenze per calcolare l’autovalore dominande della seguente matrice

A=







2 1 0

1 −2 1

0 1 α







al variare di α ∈ {1, 2, 3}. Si consideri come vettore iniziale il vettore z⁰ un vettore random (routine rand di MatLab).

Esercizio 4 (facoltativo)

Disegnare al variare dell’iterazione del metodo delle potenze l’andamento dell’errore relativo nel calcolo dell’autovalore massimo per le seguenti due matrici:

• A¹ come la seconda matrice dell’esercizio 1 cio`e

A₁ =







2 −1 0 0 0 0 0 0 0 0

−1 2 −1 0 0 0 0 0 0 0

0 −1 2 −1 0 0 0 0 0 0

0 0 −1 2 −1 0 0 0 0 0

0 0 0 −1 2 −1 0 0 0 0

0 0 0 0 −1 2 −1 0 0 0

0 0 0 0 0 −1 2 −1 0 0

0 0 0 0 0 0 −1 2 −1 0

0 0 0 0 0 0 0 −1 2 −1

0 0 0 0 0 0 0 0 −1 2







• A² matrice con gli stessi autovalori di A1 ma non simmetrica calcolata con i seguenti comandi MatLab:

e = eig(A1) p = poly(e) A2 = compan(p)

(7)

Richiami di Teoria

Metodo delle potenze: Deflazione

Nel caso in cui A abbia gli autovalori |λ¹| > |λ²| > . . . > |λⁿ| `e possibile calcolarli utilizzando il procedimento detto di deflazione che consiste nell’eliminare l’autovalore λ1 una volta che sia stata ottenuta una sua approssimazione. Una procedura per la deflazione consiste nel costruire una matrice non singolare P, mediante le trasformazioni di Householder tale che Pv1 = e¹. Allora, da Av¹ = λ1v1 si ha

PAP^TPv1 = λ₁Pv1 ⇒ (PAP^T)e¹ = λ₁e1.

La matrice PAP^T ha gli stessi autovalori di A e quindi deve avere la seguente forma PAP^T = λ1 b^T

0 A1

dove A¹`e la matrice cercata di ordine (n−1) che ha gli stessi autovalori di A trane, ovviamente λ1. Per determinare λ2 e x² `e sufficiente applicare il metodo delle potenze alla nuova matrice A1.

Lo pseudo–codice dell’algoritmo `e il seguente:

[lambdaset] ← deflazione ( A, tol, maxiter ) 1 nloop ← row (A)

2 lambdaset ← [ ]

3 for i ← 1 to nloop do 4 n ← row (A) 5 z0 ← rand (n,1)

6 [λ,q] ← potenze (A,z⁰, tol, maxiter) 7 lambdaset accoda (λ)

8 // Costruisci riflettore di Householder 9 P← HRiflettore (q)

10 K← PAP^T

11 A ← K2...n,2...,n

12 end

(8)

Esercizio 6

Si consideri la seguente matrice A generata dai comandi MatLab A = rand(50,50);

A = A+A’;

Per la matrice A si calcolino tutti gli autovalori mediante il metodo delle potenze con deflazione e si riporti l’andamento dell’errore relativo per ogni autovalore trovato. Come autovalori “veri”

si utilizzino quelli ottenuti dal comando eig di MatLab.

Risultati

−10 0 10 20 30 40 50 60

10⁻¹² 10⁻¹⁰ 10⁻⁸ 10⁻⁶ 10⁻⁴ 10⁻² 10⁰

Autovalori

Err. Rel.

Figura 4: Esercizio 6: Soluzione.

(9)

Richiami di Teoria

Il metodo delle potenze inverse

Applicando il metodo delle potenze alla matrice A⁻¹, si pu`o calcolare l’autovalore minimo λn

della matrice A. Supponiamo che A sia non singolare, diagonalizzabile e con autovalori tali che:

λ1 ≥ λ² ≥ . . . ≥ λⁿ⁻¹ > λn> 0 . Come sappiamo, la matrice A⁻¹ ha autovalori 1/λi tali che:

1 λn

> 1

λ_n−1 ≥ · · · ≥ 1 λ1

. Pertanto, il metodo delle potenze inverse si scrive:

q⁽⁰⁾ fissato, q^(k+1) = A⁻¹q^(k), k ≥ 0 .

Poichè in generale A⁻¹ non è nota (e comunque molto costosa da calcolare), il vettore q^(k+1) si troverà risolvendo il sistema lineare Aq^(k+1)= q^(k). Tali sistemi si risolvono efficientemente utilizzando la fattorizzazione LU o di Cholesky di A.

Note: Il codice per il metodo delle potenze inverse richiede rispetto al metodo delle potenze le seguenti modifiche:

1. calcolo della fattorizzazione LU o di Cholesky di A all’esterno del ciclo di convergenza;

2. sostituizione al prodotto z = Aq con la risoluzione del sistema Az = q mediante uso della fattorizzazione del punto precedente;

3. esecuzione del reciproco di λ.

Esercizio 7

Calcoloare l’autovalore minimo delle seguenti matrici con il metodo delle potenze inverse.

A₁ =





4 −1 0 −1 0 0 0 0 0

−1 4 −1 0 −1 0 0 0 0

0 −1 4 0 0 −1 0 0 0

−1 0 0 4 −1 0 −1 0 0

0 −1 0 −1 4 −1 0 −1 0

0 0 −1 0 −1 4 0 0 −1

0 0 0 −1 0 0 4 −1 0





(10)

e

A₂ =







2 −1 0 0 0 0 0 0 0 0

−1 2 −1 0 0 0 0 0 0 0

0 −1 2 −1 0 0 0 0 0 0

0 0 −1 2 −1 0 0 0 0 0

0 0 0 −1 2 −1 0 0 0 0

0 0 0 0 −1 2 −1 0 0 0

0 0 0 0 0 −1 2 −1 0 0

0 0 0 0 0 0 −1 2 −1 0

0 0 0 0 0 0 0 −1 2 −1

0 0 0 0 0 0 0 0 −1 2







Per verificare i calcoli si disegni l’andamento al variare dell’iterazione dell’errore relativo commesso dove l’autovalore di minimo e ottenuto attraverso l’utilizzo del comando MatLab eig.

Richiami di Teoria

Variante del metodo delle potenze con shifting (traslazione) Si osservi che da Ix = x e Ax = λx segue che

∀µ ∈ C, (µI)x = µx e B= (µI − A)x = µx − λx = (µ − λ)x .

Quindi la matrice shiftata B = (µI − A) ha autovalori σⁱ traslati di µ, i.e. σi = µ − λ e stessi autovettori di A.

Quindi:

1. si pu`o accelerare il metodo delle potenze con l’uso dello shift quando il rapporto

λ2

λ₁

`e prossimo a 1.0 per cui la convergenza risulta lenta. Ad esempio se σ(A) = {3.0, −2.9, 1.0}

si trova

λ₂ λ₁

= ^2.9_3.0 ≡ 0.97. Preso µ = −2 (scelta sperimentale) si ha che σ(B) = σ(A − µI) = {5.0, −0.9, 3.0} e quindi

λ₂ λ₁

=

3.0

5.0 ≡ 0.6.

2. si può combinare lo shift con il metodo delle potenze inverse per trovare l’autovalore di A più vicino a un dato valore µ: (A − µI)q^(k+1) = q^(k). Oppure, combinandolo con il metodo delle potenze, si può trovare l’autovalore di A più lontano da µ: q^(k+1) = (A − µI)q^(k).

L’implentazione consiste nelle seguenti modifiche rispetto al metodo delle potenze inverse:

(11)

• fattorizzare la matrice (A − µI)

• una volta calcolato σ (approssimazione dell’autovalore) ricordarsi di calcolare λ come λ = µ + 1/σ.

Esercizio 8

Per le matrici dell’esercizio 2, dopo aver calcolato un’approssimazione iniziale dell’autovalore dominante con due cifre decimali esatte dopo la virgola si calcoli l’autovalore dominante con il metodo delle potenze inverse con shifting. Confrontare il numero di iterazioni eseguite dal metodo delle potenze ed dal metodo delle potenze inverse con shifting.

Esercizio 9 (facoltativo)

Ripetere l’esercizio precedente con riferimento al valore minimo.

Esercizio 10 (facoltativo)

Con riferimento alla seguente matrice

A=







19 −7 −1 −1 2 14 −3 −2 −2 3 10 −2 −1 −4 −5

7 −1 0 −6 7

3 −1 10 −5 4





 si hanno a disposizione le seguenti stime per gli autovalori:

λ1 ≈ 13.04 λ² ≈ 2.60 λ ≈ −5.71 λ⁴ ≈ 1.52 + 9.3i λ⁵ ≈ 1.52 − 9.3i

Calcolare tutti gli autovalori ed autovettori. Confrontare i risultati con il comando MatLab [V,D] = eig(A) per verificare che l’autovalore calcolato `e multiplo (per una certa costante) con quello calcolato da MatLab.

Si utilizzi eventualmente il seguente codice MatLab

% lambda, q autovalore ed autovettore trovato dal metodo delle pot. inv.

[V,D] = eig(A)

(12)

Vm./q

per il confronto delle costanti multiplicative tra il vettore calcolato in MatLab e quello calcolato dal metodo delle potenze inverse con shifting.