Metodo delle potenze inverse con shift. Metodo QR. Convergenza QR.

Calcolo di autovalori e autovettori ¹

A. Sommariva

²

Keywords: Teoremi di localizzazione di Gerschgorin (con esempi). Metodo delle potenze. Convergenza del metodo delle potenze. Metodo delle potenze inverse.

Metodo delle potenze inverse con shift. Metodo QR. Convergenza QR.

Implementazione di QR con matrici di Hessenberg.

Revisione: 11 maggio 2021

1. Autovalori

Il problema del calcolo degli autovalori di una matrice quadrata A di ordine n consiste nel trovare gli n numeri (possibilmente complessi) λ tali che

Ax = λx, x 6= 0 (1)

Gli autovalori sono anche gli zeri del polinomio caratteristico p(λ) = det(A−λI

n

) e quindi sono n numeri complessi, ognuno contato con la sua molteplicit´a.

Si osservi che a seconda delle esigenze

• talvolta `e richiesto solamente il calcolo di alcuni autovalori (ad esempio quelli di massimo modulo, per determinare lo spettro della matrice),

• talvolta si vogliono determinare tutti gli n autovalori in C.

Nota 1.1. Una interessante applicazione `e l’algoritmo di PageRank, utilizzato per for- nire i risultati migliori tra i siti web relativamente a certe parole chiave. Indicativa- mente si basa sul calcolo di un autovettore relativo all’autovalore 1 di una matrice stocastica di dimensioni enormi.

In questo paragrafo mostriamo tre teoremi di localizzazione di autovalori dovuti a Gershgorin (cf. [1, p.76]).

Teorema 1.2 (Primo teorema di Gershgorin, (Gershgorin, 1931)). Gli autovalori di una matrice A di ordine n sono tutti contenuti nell’unione dei cerchi di Gershgorin

K

i

= {z ∈ C : |z − a

^i,i

| ≤

n

X

j=1,j6=i

|a

i,j

|}

Figura 1: Cerchi di Gershgorin della matrice A definita in (6)

Esempio 1.1. Vediamo quale esempio la matrice

A =





15 −2 2

1 10 −3

−2 1 0



 (2)

Il primo teorema di Gershgorin stabilisce che gli autovalori stanno nell’unione dei cerchi di Gershgorin

K

1

= {z ∈ C : |z − 15| ≤ | − 2| + |2| = 4}

K

₂

= {z ∈ C : |z − 10| ≤ |1| + | − 3| = 4}

K

3

= {z ∈ C : |z − 0| ≤ | − 2| + |1| = 3}

Teorema 1.3 (Secondo teorema di Gershgorin, (Brauer, 1948)). Se l’unione M

1

di k cerchi di Gershgorin `e disgiunta dall’unione M

2

dei rimanenti n − k, allora k autovalori appartengono a M

1

e n − k appartengono a M

2

.

Nota 1.4. Nel teorema precedente ogni autovalore viene calcolato con la sua molte- plicita’.

Esempio 1.2. Relativamente a

A =





15 −2 2

1 10 −3

−2 1 0



 (3)

dal secondo teorema di Gershgorin, vista la figura, abbiamo che un autovalore sta nel cerchio K

₃

mentre due stanno in K

₁

∪ K

₂

.

Definizione 1.5. Una matrice di ordine n ≥ 2 `e riducibile se esiste una matrice di permutazione Π e un intero k, 0 < k < n, tale che

B = ΠAΠ

^T

=

 A

1,1

A

1,2

0 A

2,2



in cui A

1,1

∈ C

^k×k

, A

2,2

∈ C

(n−k)×(n−k)

.

Definizione 1.6. Una matrice si dice irriducibile se non `e riducibile.

Nota 1.7. Per verificare se una matrice A = (a

i,j

) sia irriducibile, ricordiamo che data una qualsiasi matrice, `e possibile costruire un grafo avente come nodi gli indici della matrice. In particolare, il nodo i-esimo `e connesso al nodo j-esimo se l’elemento a

_i,j

`e diverso da 0.

Il grafo associato si dice fortemente connesso se per ogni coppia (i, j) posso rag- giungere j a partire da i.

Una matrice `e irriducibile se e solo se il grafo ad essa associata (detto di adiacen- za) `e fortemente connesso.

In altre parole, una matrice `e riducibile se e solo se il grafo di adiacenza ad esso associato non `e fortemente connesso.

Teorema 1.8 (Terzo teorema di Gershgorin, (Brauer, 1948)). Se la matrice di ordi- ne n `e irriducibile e un autovalore λ sta sulla frontiera dell’unione dei cerchi di Gershgorin, allora sta sulla frontiera di ogni cerchio di Gershgorin.

Esempio 1.3. La matrice

B =









2 −1 0 0

−1 2 −1 0

0 −1 2 −1

0 0 −1 2









`e irriducibile, in quanto il grafico di adiacenza `e fortemente connesso. Gli autova- lori stanno nella disco centrato in (2, 0) e raggio 2 (primo teorema di Gershgorin), ma non sulla frontiera (terzo teorema di Gershgorin). Quindi `e non singolare.

Sia nuovamente

A =





15 −2 2

1 10 −3

−2 1 0



 (4)

La matrice A ha grafo ´e fortemente connesso e quindi irriducibile. Nessun punto ´e sulla frontiera di tutti i dischi, quindi nessun autovalore sta sulla loro frontiera.

Numericamente si conferma la localizzazione degli autovalori.

>> A=[15 -2 2; 1 10 -3; -2 1 0]

A =

15 -2 2

1 10 -3

-2 1 0

>>eig(A) ans =

0.5121 14.1026 10.3854

>>

Nota 1.9. • Ricordiamo che A `e una matrice a coefficienti reali, allora A e A

^T

hanno gli stessi autovalori (cf. [1, p.47]) e quindi applicando i teoremi di Gershgorin alla matrice trasposta possiamo ottenere nuove localizzazioni degli autovalori.

• Nel caso A sia a coefficienti complessi, se λ `e un autovalore di A allora il suo coniugato λ `e autovalore della sua trasposta coniugata A. Da qui si possono fare nuove stime degli autovalori di A.

Esercizio 1.1. Cosa possiamo dire relativamente agli autovalori di A se applichiamo i teoremi di Gershgorin ad A

^T

invece che ad A?

Nota 1.10. • Il primo teorema di Gerschgorin `e stato pubblicato nel 1931 nell’ar- ticolo ¨ Uber die Abgrenzung der Eigenwerte einer Matrix dal matematico bielorusso di origine ebraica Semyon Aranovich Gerschgorin (1901- 1933).

• Fra il 1946 e il 1948 Brauer, un allievo di Schur, pubblica una raccolta sistemati- ca di teoremi di limitazione degli autovalori, fra i quali quelli noti come secondo e terzo teorema di Gerschgorin e anche la generalizzazione data in termini degli ovali di Cassini.

Il metodo delle potenze, come vedremo, `e particolarmente indicato per il calcolo dell’autovalore di massimo modulo di una matrice.

Sia A una matrice quadrata di ordine n con

• n autovettori x

₁

, . . ., x

n

linearmente indipendenti,

• autovalori λ

1

, . . ., λ

n

tali che

|λ

1

| > |λ

2

| ≥ . . . ≥ |λ

n

|. (5) A tal proposito ricordiamo (cf. [2], p. 951) i seguenti risultati.

• Una matrice A `e diagonalizzabile se e solo se possiede n autovettori linearmen- te indipendenti.

• Se tutti gli autovalori di A sono distinti la matrice `e diagonalizzabile; l’opposto

`e ovviamente falso (si pensi alla matrice identica).

• Una matrice simmetrica (hermitiana) `e diagonalizzabile. L’opposto `e ovviamen- te falso, visto che la matrice

A =

 15 0 1 10



(6)

`e diagonalizzabile visto che ha tutti gli autovalori distinti ma non `e simmetrica.

Teorema 1.11 (Convergenza del metodo delle potenze, (Muntz, 1913)). Siano

• A ∈ C

^n×n

una matrice diagonalizzabile con autovalori λ

k

t.c.

|λ

1

| > |λ

2

| ≥ . . . ≥ |λ

n

|.

• u

k

6= 0 autovettori relativi all’autovalore λ

k

, cio`e Au

k

= λ

k

u

k

.

• y

0

= P

k

α

k

u

k

, α

1

6= 0.

La successione {y

s

} del metodo delle potenze definita da

y

s+1

= Ay

s

, s = 0, 1, 2, . . . (7)

converge per direzione a quella di u

1

e il quoziente di Rayleigh

ρ(y

s

, A) := (Ay

s

, y

s

)

(y

s

, y

s

) (8)

converge all’autovalore λ

1

.

Dimostrazione 1.12. Essendo la matrice A diagonalizzabile, esistono n autovettori u

_k

(relativi rispettivamente agli autovalori λ

_k

) che sono linearmente indipendenti e quindi formano una base di C

ⁿ

.

Sia y

₀

= P

k

α

_k

u

_k

, α

₁

6= 0.

Essendo Au

k

= λ

k

u

k

abbiamo y

1

= Ay

0

= A( X

k

α

k

u

k

) = X

k

α

k

Au

k

= X

k

α

k

λ

k

u

k

y

₂

= Ay

₁

= A( X

k

α

_k

λ

_k

u

_k

) = X

k

α

_k

λ

_k

Au

_k

= X

k

α

_k

λ

²_k

u

_k

e pi`u in generale

y

_s+1

= Ay

_s

= A( X

k

α

_k

λ

^s_k

u

_k

) = X

k

α

_k

λ

^s_k

Au

_k

= X

k

α

_k

λ

^s+1_k

u

_k

.

Osserviamo ora che da y

s+1

= P

k

α

k

λ

^s+1_k

u

k

deduciamo y

s+1

λ

^s+1₁

= X

k

α

k

λ

^s+1_k

λ

^s+1₁

u

k

= α

1

u

1

+ X

k>1

α

k

 λ

k

λ

₁



^s+1

u

k

(9)

per cui essendo |λ

k

| < |λ

₁

| qualora k 6= 1, necessariamente 

  

λ

_k

λ

1

   

< 1, k 6= 1 e di conseguenza

s→+∞

lim

 λ

k

λ

₁



^s

= 0

e quindi la direzione di

_λ^yss

1

tende a quella dell’autovettore u

1

. Per concludere, dal fatto che

• lim

s

(y

s

)/λ

^s₁

= α

1

u

1

;

• se β

s

, γ

s

sono convergenti allora lim

s

(β

_s

, γ

_s

) = (lim

_s

β

_s

, lim

_s

γ

_s

),

• se v

_s

`e convergente allora lim

_s

Av

_s

= A lim

_s

v

_s

, abbiamo

lim

s

ρ(y

_s

, A) := lim

s

(Ay

_s

, y

_s

) (y

s

, y

s

) = lim

s

(A(y

_s

/λ

^s₁

), y

_s

/λ

^s₁

) (y

s

/λ

^s₁

, y

s

/λ

^s₁

)

= (lim

s

A(y

s

/λ

^s₁

), lim

s

(y

s

/λ

^s₁

))

(lim

s

(y

s

/λ

^s₁

), lim

s

(y

s

/λ

^s₁

)) = (α

1

Au

1

, α

1

u

1

) (α

1

u

1

, α

1

u

1

)

= (Au

₁

, u

₁

)

(u

1

, u

1

) = λ

₁

(u

₁

, u

₁

)

(u

1

, u

1

) = λ

₁

. (10)

Nota 1.13. Il metodo converge anche nel caso in cui λ

1

= . . . = λ

r

per r > 1, tuttavia non `e da applicarsi quando l’autovalore di modulo massimo non sia unico.

Nota 1.14. In virt´u di possibili underflow e overflow si preferisce normalizzare il vetto- re y

k

precedente definito. Partendo da t

0

= P

k

α

k

u

k

, α

1

6= 0, kt

0

k

2

= 1, si generano la successione {t

k

}, {I

k

}:

γ

k

= At

k−1

t

k

=

_kγ^γk

kk2

, l

k

= ρ(t

k

, A)

(11)

dove ρ(t

k

, A) `e il coefficiente di Rayleigh definito in (8).

Una variante particolarmente interessante del metodo delle potenze, detta delle po- tenze inverse `e stata scoperta da Wielandt nel 1944 ed e’ particolarmente utile nel caso in cui A sia una matrice quadrata con n autovettori linearmente indipendenti,

|λ

1

| ≥ |λ

2

| ≥ . . . > |λ

n

| > 0. (12) e si desideri calcolare il pi ´u piccolo autovalore in modulo, cio`e λ

_n

, applicando il metodo delle potenze ad A

⁻¹

.

Lemma 1.15. Se A ha autovalori {λ

k

}

k=1,...,n

, tali che |λ

1

| ≥ |λ

2

| ≥ . . . ≥ |λ

n

| > 0

e Au

k

= λ

k

u

k

, u

k

6= 0 allora

• allora A

⁻¹

ha autovalori ξ

k

= 1/λ

n−k+1

, con |ξ

1

| ≥ |ξ

2

| ≥ . . . ≥ |ξ

n

| > 0;

• i vettori v

_k

= u

_n−k+1

sono tali che A

⁻¹

v

_k

= ξ

_k

v

_k

.

Applicando il metodo delle potenze ad A

⁻¹

, con A diagonalizzabile, partendo da t

₀

= P

k

α

_k

u

_k

, con α

_n

> 0, kt

0

k

₂

= 1, qualora |λ

1

| ≥ |λ

₂

| ≥ . . . >|λ

_n

| > 0, otteniamo la successione {t

s

} definita da

 γ

s

= A

⁻¹

t

s−1

t

s

=

_kγ^γs

sk2

, ⇔

 Aγ

s

= t

s−1

t

s

=

_kγ^γs

sk2

,

e convergente per direzione ad un vettore parallelo a v

1

= u

_n

. La successione di quozienti di Rayleigh `e tale che, visto che (t

_s

, t

_s

) = kt

_s

k

²₂

= 1

ρ(t

s

, A

⁻¹

) := (A

⁻¹

t

s

, t

s

)

(t

s

, t

s

) = (t

s

, γ

s+1

) → ξ

1

= 1/λ

n

. (13) o similmente, visto che t

s

tende alla direzione di v

1

ovvero di u

n

ρ(t

_s

, A) → λ

_n

. (14)

Nota 1.16 (Facoltativa). Si osserva subito che se A

⁻¹

u = ξ

i

u, con ξ

i

6= 0, allora Au = A (A

⁻¹

u/ξ

i

)

| {z }

u

= (1/ξ

i

)u,

cio`e

• ξ

⁻¹_i

`e un autovalore di A;

• se u `e autovettore di A

⁻¹

relativo all’autovalore ξ

i

, allora u autovettore di A relativo all’autovalore ξ

⁻¹_i

.

Conseguentemente

• se ξ

1

`e l’autovalore di massimo modulo di A

⁻¹

e λ

n

`e l’autovalore di minimo modulo di A si ha λ

n

= ξ

⁻¹₁

;

• u `e autovettore per A relativamente all’autovalore λ

_n

.

In generale, fissato µ ∈ C `e possibile calcolare, se esiste unico, l’autovalore λ pi`u vicino a µ tramite il seguente algoritmo.

Osserviamo che da

Au = λu ⇔ (A − µI)u = λu − µu = (λ − µ)

| {z }

σ

u

• se σ `e un autovalore di minimo modulo di A − µI allora λ = σ + µ `e uno degli

autovalori di A di minima distanza da µ;

• se u `e autovettore di σ relativamente a A − µI allora lo `e pure per λ.

Nelle ipotesi che il metodo delle potenze inverse sia applicabile alla matrice A−µI, per un vettore iniziale t

0

tale che kt

0

k

2

= 1, il metodo delle potenze inverse con shift

`e definito da:

(A − µI) γ

k

= t

k−1

t

k

= γ

k

/kγ

k

k

2

σ

_k

= t

^H_k

At

_k

.

(15)

Nota 1.17. • Il metodo delle potenze inverse genera una sequenza di vettori t

k

convergente alla direzione dell’autovettore di A, relativo a λ, ossia l’autovalore di A pi`u vicino a µ; per questo si applica il quoziente di Rayleigh direttamente ad A, per ottenere l’approssimazione di λ.

• Per versioni pi´u sofisticate di questa tecnica detta di shift (o in norma infinito invece che in norma 2) si confronti [1, p.379].

Il metodo QR, considerato tra i 10 algoritmi pi`u rilevanti del ventesimo secolo, cerca di calcolare tutti gli autovalori di una matrice A.

Teorema 1.18 (Fattorizzazione QR). Sia A una matrice quadrata di ordine n. Esi- stono

• Q unitaria (cio`e Q

^T

∗ Q = Q ∗ Q

^T

= I),

• R triangolare superiore tali che

A = QR.

Citiamo alcune cose:

• La matrice A ha quale sola particolarit`a di essere quadrata. Nel caso generale per`o la sua fattorizzazione QR in generale non `e unica bens`ı determinata a meno di una matrice di fase (cf. [1, p.149]) .

• Nel caso sia non singolare, allora tale fattorizzazione `e unica qualora si chieda che i coefficienti diagonali di R siano positivi.

• La routine Matlab qr effettua tale fattorizzazione. Si consiglia di consultare l’help di Matlab, per consultare le particolarit`a di tale routine.

• Se la matrice H `e simile a K (cio`e esiste una matrice non singolare S tale che H = S

⁻¹

KS) allora H e K hanno gli stessi autovalori.

• Si pu`o vedere facilmente che la relazione di similitudine `e transitiva, cio`e se H

1

`e simile ad H

2

e H

2

`e simile ad H

3

allora H

1

`e simile ad H

3

.

Il metodo QR venne pubblicato indipendemente nel 1961 da Francis e da Kubla- novskaya e successivamente implementato in EISPACK. Ci limiteremo a considerare versioni di base del metodo.

Lemma 1.19. Sia

A

₀

= Q

₀

R

₀

la fattorizzazione QR di A

₀

e

A

₁

:= R

₀

Q

₀

.

Le matrici A

₀

e A

₁

sono simili e quindi hanno gli stessi autovalori.

Dimostrazione 1.20. Basta notare che

Q

0

A

1

Q

^T₀

= Q

0

R

0

Q

0

Q

^T₀

= A

0

e quindi la matrice A

1

`e simile ad A

0

(si ponga S = Q

⁻¹₀

= Q

^T₀

) Definiamo il seguente metodo, detto QR, dovuto a Francis (1961).

Metodo. 1.1 (QR). Posto A

0

= A, il metodo QR consiste nel calcolare le iterate A

k

definite da

A

k

= Q

k

R

k

A

k+1

= R

k

Q

k

dove ad ogni iterazione viene calcolata la fattorizzazione QR della matrice A

k

. Le matrici A

k

, k = 1, 2, . . . sono simili alla matrice A e quindi hanno gli stessi autovalori.

Teorema 1.21 (Convergenza metodo QR). Se A ∈ R

^n×n

ha autovalori tutti distinti in modulo, con

|λ

₁

| > . . . > |λ

_n

| (16) allora l’algoritmo QR converge a A

_∞

= (a

^∞_i,j

) triangolare superiore, cio`e

lim

k

A

k

=























a

^∞_1,1

a

^∞_1,2

. . . . . . a

^∞_1,n

0 a

^∞_2,2

a

^∞_2,3

. . . a

^∞_2,n

0 0 a

^∞_3,3

. . . a

^∞_3,n

0 0 . . . . . . . . .

.. . .. . .. . .. . .. . 0 0 0 a

^∞_n−1,n−1

a

^∞_n−1,n

0 0 0 0 a

^∞_n,n























(17)

con λ

_k

= a

^∞_k,k

.

Inoltre

• Se la condizione (16) non `e verificata si pu`o dimostrare che la successione {A

k

} tende a una forma triangolare a blocchi.

• se A

k

= (a

^(k)_i,j

), e λ

i−1

6= 0

|a

^(k)_i,i−1

| = O

 |λ

i

|

|λ

i−1

|



k

, i = 2, . . . , n, k → ∞. (18)

Nelle implementazioni si calcola con un metodo scoperto da Householder (ma esiste un metodo alternativo dovuto a Givens) una matrice di Hessenberg T

T =

















a

1,1

a

1,2

a

1,3

. . . a

1,n

a

2,1

a

2,2

a

2,3

. . . a

2,n

0 a

_3,2

a

_3,3

. . . a

_3,n

0 0 a

_4,3

. . . a

_4,n

. . . . . . . . . . . . . . .

0 0 0 a

_n,n−1

a

_n,n

















simile ad A ed in seguito si applica il metodo QR relativamente alla matrice T . Nota 1.22. Se A `e simmetrica la matrice di Hessenberg T simile ad A risulta tridia- gonale simmetrica.

Si pu`o mostrare che le iterazioni mantengono la struttura, cio`e

• se A

0

= T `e di Hessenberg, allora A

k

`e di Hessenberg,

• se A

0

= T `e tridiagonale allora A

k

`e tridiagonale.

Se A `e una matrice Hessenberg allora l’algoritmo QR converge ad A

∞

triangolare a blocchi, simile ad A e con gli autovalori di ogni blocco diagonale tutti uguali in modulo (Francis, 1961).

Ovviamente, pure in questo caso. se |λ

1

| > . . . > |λ

n

|

|a

^(k)_i,i−1

| = O (|λ

_i

|/|λ

_i−1

|)

^k

, i = 2, . . . , n, k → ∞. (19)

Nota 1.23 (Operazioni trasformazioni in matrici di Hessenberg). Il numero di mol- tiplicazioni necessarie

• all’algoritmo di Givens per calcolare tale matrice di Hessenberg T a partire da A `e approssimativamente 10n

³

/3;

• all’algoritmo di Householder per calcolare tale matrice di Hessenberg T a par-

tire da A `e approssimativamente 5n

³

/3.

Nota 1.24 (Costo QR). Il metodo QR applicato ad una matrice A in forma di Hessen- berg superiore ha ad ogni passo un costo di 2n

²

operazioni moltiplicative.

Si osservi che, utilizzando un metodo dovuto a Householder, il costo di una fatto- rizzazione QR di una matrice generica ´e di O(2n

³

/3) operazioni moltiplicative.

Nota 1.25 (Shift). Per motivi computazionali, a partire da una matrice in forma di Hessenberg o tridiagonale di dimensione n, si preferisce applicare QR shiftato, dove

• A

₀

= A;

• A

_k

− λ

_k

I = Q

_k

R

_k

;

• A

k+1

= R

k

Q

k

+ λ

k

I = Q

^∗_k

(A

k

− λ

k

I)Q

k

+ λ

k

I = Q

^∗_k

A

k

Q

k

Quale λ

k

si possono fare molte scelte, tipicamente (A

k

)

n,n

Nota 1.26 ([3, p.59]). For symmetric matrices, the eigenproblem is relatively simple ... and the eigenproblem may be considered as solved:

• for small matrices n ≤ 25 we have the QR method, one of the most elegant techniques produced in the field of numerical analysis;

• for large matrices (but smaller than a few thousand), we have a combination of divide and conquer with QR techniques;

• for the largest matrices there is the Lanczos method.

For unsymmetric matrices the picture is less rosy.

[1] D. Bini, M. Capovani e O. Menchi, Metodi numerici per l’algebra lineare, Zanichelli, 1988.

[2] V. Comincioli, Analisi Numerica, metodi modelli applicazioni, Mc Graw-Hill, 1990.

[3] G.H. Golub, H.A. van der Vorst, Eigenvalue computation in the 20th century, JCAM 123 (2000), p. 35–65.

[4] G.H. Golub e C.F. Van Loan, Matrix Computation, 3rd Edition, The John Hopkins

University Press 1996.