Ricerca dell’autovalore di modulo massimo

(1)

Metodo delle potenze

(2)

Data una matrice A ∈ R

^n×n

, supponiamo che ammetta n autovalori tali che

|λ

₁

| > |λ

₂

| ≥ · · · ≥ |λ

_n

|

Problema

Vogliamo trovare (l’unico) autovalore di modulo massimo λ

₁

(3)

x

₁

, x

₂

, . . . , x

n

associati a λ

₁

, . . . , λ

_n

. Essi sono linearmente indipendenti ⇒ sono una base di R

ⁿ

.

1

Considero un vettore iniziale v

⁽⁰⁾

. Esso si pu `o scrivere come

v

⁽⁰⁾

=

n

X

i=1

α

_i

x

_i

2

Suppongo che v

⁽⁰⁾

sia tale che α

₁

6= 0.

3

genero la successione

v

⁽¹⁾

= Av

⁽⁰⁾

, v

⁽²⁾

= Av

⁽¹⁾

, . . . , v

^(m)

= Av

^(m−1)

...

4

v

^(m)

= λ

^m₁

α

1

x

₁

+ α

2

λ₂ λ1

m

x

₂

+ · · · + α

n

λn

λ1

m

x

_n

(4)

Si dimostra che, fissata una componente k ,

m→∞

lim v

^(m)_k

v

^(m−1)_k

= λ

₁

e

m→∞

lim v

^(m)

λ

^m₁

= α

₁

x

₁

Velocit `a di convergenza

La velocit `a di convergenza del metodo dipende da

λ

2

λ

1

m

(5)

Al crescere del numero di iterazioni m, accade che

|λ

₁

|

^m

→ ∞ quando |λ

1

| > 1 V OVERFLOW

|λ

₁

|

^m

→ 0 quando |λ

₁

| < 1 V UNDERFLOW

Soluzione

Normalizzare la successione dei vettori y

⁽¹⁾

= Av

⁽⁰⁾

, v

⁽¹⁾

=

_ky^y(1)⁽¹⁾k∞

y

⁽²⁾

= Av

⁽¹⁾

, v

⁽²⁾

=

^y⁽²⁾

ky⁽²⁾k∞

. . . .

y

⁽ⁿ⁾

= Av

⁽ⁿ⁻¹⁾

, v

⁽ⁿ⁾

=

^y⁽ⁿ⁾

ky⁽ⁿ⁾k∞

y⁽ⁿ⁺¹⁾_k v⁽ⁿ⁾_k

→ λ

₁

(6)

Algoritmo

Input A, TOL, componente k, NMAX. Output λ

₀

1

v 0 = [1, 1..1]

2

pongo l’errore iniziale e = 1, i = 0 (contatore iterazioni), λ

₀

= 1

3

Fino a quando e > TOL & i ≤ NMAX y = A ∗ v 0

λ

₁

= y (k )/v 0(k ) v 0 = y /||y ||

∞

e = |λ

₁

− λ

₀

|/|λ

₁

| i = i + 1

λ

0

= λ

1

4

Se i > NMAX , il metodo non converge altrimenti λ

₀

`e la

soluzione

(7)

Attenzione

Potrebbe capitare che la componente v 0(k ) sia nulla. Per evitare ci `o `e sufficiente scegliere ad ogni passo l’indice k

₀

in modo che

|y (k

₀

)| = ky k

∞

V v0(k

0

) = 1

In questo caso k

₀

potrebbe non rimanere costante per tutte le iterazioni. In ogni caso si pu `o dimostrare che anche la

successione y

⁽ⁿ⁺¹⁾_k

/v

⁽ⁿ⁾_k

converge a λ

₁

[cmax,ind]=max(v)

fornisce la componente massima del vettore (cmax) e l’indice

(ind) di tale componente

(8)

Osservazioni

1

Se v

₀

`e tale che α

₁

= 0, il metodo dovrebbe convergere a λ

₂

. In pratica, a causa degli errori di arrotondamento, ci `o non accade

2

Quando |λ

₁

| ≈ |λ

₂

| la convergenza pu `o risultare molto lenta

3

Se λ

₁

= −λ

₂

Ricerca dell’autovalore di modulo massimo

Metodo delle potenze

Data una matrice A ∈ R

, supponiamo che ammetta n autovalori tali che

|λ

| > |λ

| ≥ · · · ≥ |λ

|

Problema

Vogliamo trovare (l’unico) autovalore di modulo massimo λ

x

, x

, . . . , x

associati a λ

, . . . , λ

. Essi sono linearmente indipendenti ⇒ sono una base di R

.

Considero un vettore iniziale v

. Esso si pu `o scrivere come

v

=

X

α

x

Suppongo che v

sia tale che α

6= 0.

genero la successione

v

= Av

, v

= Av

, . . . , v

= Av

...

v

= λ



α

x

+ α





x

+ · · · + α





x



Si dimostra che, fissata una componente k ,

lim v

v

= λ

e

lim v

λ

= α

x

Velocit `a di convergenza

La velocit `a di convergenza del metodo dipende da

λ

λ

Al crescere del numero di iterazioni m, accade che

|λ

|

→ ∞ quando |λ

| > 1 V OVERFLOW

|λ

|

→ 0 quando |λ

| < 1 V UNDERFLOW

Soluzione

Normalizzare la successione dei vettori y

= Av

, v

=

y

= Av

, v

=