Calcolo di autovalori e autovettori

(1)

Calcolo di autovalori e autovettori

Alvise Sommariva

Universit`a degli Studi di Padova Dipartimento di Matematica

(2)

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 − λIn) e quindi sono n numeri complessi, ognuno contato con la sua molteplicit´a.

Si osservi che a seconda delle esigenze

talvolta `e richiestosolamente il calcolo di alcuni autovalori(ad esempio quelli di massimo modulo, per determinare lo spettro della matrice), talvolta si vogliono determinaretutti gli n autovaloriin C.

Nota.

Una interessante applicazione `e l’algoritmo diPageRank, utilizzato per fornire i risultati migliori tra i siti web relativamente a certe parole chiave.

(3)

Teoremi di Gershgorin

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

Teorema (Primo teorema di Gershgorin, (Gershgorin, 1931))

Gli autovalori di una matrice A di ordine n sono tutti contenuti nell’unione dei cerchi di Gershgorin

Ki = {z ∈ C : |z − ai ,i| ≤ n X j =1,j 6=i

(4)

Teoremi di Gershgorin

Esempio

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

(5)

Teoremi di Gershgorin

(6)

Teoremi di Gershgorin

Teorema (Secondo teorema di Gershgorin, (Brauer, 1948))

Se l’unione M1di k cerchi di Gershgorin `e disgiunta dall’unione M2dei

rimanenti n − k, allora k autovalori appartengono a M1e n − k

appartengono a M2. Nota.

Nel teorema precedente ogni autovalore viene calcolato con la sua molteplicita’. Esempio Relativamente a A =   15 −2 2 1 10 −3 −2 1 0   (3)

(7)

Teoremi di Gershgorin

Definizione

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

B = ΠAΠT = A1,1 A1,2 0 A2,2 in cui A1,1 ∈ Ck×k, A2,2 ∈ C(n−k)×(n−k). Definizione

(8)

Teoremi di Gershgorin

Nota.

Per verificare se una matrice A = (ai ,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 ai ,j `e diverso da 0.

Il grafo associato si dicefortemente connessose per ogni coppia (i , j ) posso raggiungere j a partire da i .

Unamatrice `e irriducibilese e solo se il grafo ad essa associata (detto di adiacenza) `efortemente connesso.

(9)

Teoremi di Gershgorin

Teorema (Terzo teorema di Gershgorin, (Brauer, 1948))

Se la matrice di ordine 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 La matrice B =     2 −1 0 0 −1 2 −1 0 0 −1 2 −1 0 0 −1 2    

(10)

Teoremi di Gershgorin

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.

(11)

Teoremi di Gershgorin

Nota.

Ricordiamo che A `e una matrice a coefficienti reali, allora A e AT _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

(12)

Nota storica

Nota.

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

(13)

Metodo delle potenze

Ilmetodo 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 x1, . . ., xn linearmente indipendenti, autovalori λ1, . . ., λn tali che

(14)

Metodo delle potenze

A tal proposito ricordiamo (cf. [2], p. 951) i seguenti risultati. Una matrice A `e diagonalizzabile se e solo se possieden autovettori linearmente indipendenti.

Se tutti gli autovalori di A sono distintila matrice `e diagonalizzabile; l’opposto `e ovviamente falso (si pensi alla matrice identica).

Una matrice simmetrica (hermitiana) `e diagonalizzabile. L’opposto `e ovviamente falso, visto che la matrice

A = 15 0 1 10 (6) `

(15)

Metodo delle potenze

Teorema (Convergenza del metodo delle potenze, (Muntz, 1913))

Siano

A ∈ Cn×n_{una matrice}_{diagonalizzabile}_{con autovalori λk}_t.c. |λ1| > |λ2| ≥ . . . ≥ |λn|.

uk6= 0 autovettori relativi all’autovalore λk, cio`eAuk= λkuk.

y0=P

kαkuk, α16= 0.

La successione {ys} del metodo delle potenze definita da

ys+1= Ays, s = 0, 1, 2, . . . (7)

converge per direzione a quella di u1e il quoziente di Rayleigh

ρ(ys, A) :=

(Ays, ys)

(ys, ys)

(16)

Metodo delle potenze

Dimostrazione.

Essendo la matrice A diagonalizzabile, esistono n autovettoriuk (relativi rispettivamente agli autovalori λk) che sono linearmente indipendenti e quindi formano unabase di Cn.

(17)

Metodo delle potenze

Osserviamo ora che da ys+1 =Pkαkλs+1_k uk deduciamo ys+1 λs+1₁ = X k αk λs+1_k λs+1₁ uk = α1u1+ X k>1 αk λk λ1 s+1 uk (9)

per cui essendo |λk| < |λ1| qualora k 6= 1, necessariamente λk λ1 < 1, k 6= 1 e di conseguenza lim s→+∞ λk λ1 s = 0 e quindila direzione di _λyss

(18)

Metodo delle potenze

Per concludere, dal fatto che lims(ys)/λs

1= α1u1;

se βs, γssono convergenti alloralims(βs, γs) = (limsβs, limsγs),

se vs`e convergente alloralimsAvs= A limsvs,

abbiamo

lim

s ρ(ys, A) := lims

(Ays, ys) (ys, ys) = lims

(19)

Metodo delle potenze

Nota.

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.

In virt´u di possibili underflow e overflow si preferisce normalizzare il vettore yk precedente definito. Partendo da t0=P

kαkuk, α16= 0, kt0k2= 1, si generano la successione {tk}, {Ik}: γk= Atk−1 tk=kγγ_kkk₂, lk= ρ(tk, A) (11)

(20)

Metodo delle potenze inverse

Una variante particolarmente interessante del metodo delle potenze, dettadelle potenze 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 ilpi´u piccolo autovalore in modulo, cio`e λn,

applicando il metodo delle potenze ad A−1. Lemma

Se A ha autovalori {λk}k=1,...,n, tali che |λ1| ≥ |λ2| ≥ . . . ≥ |λn| > 0 e

Auk = λkuk, uk 6= 0 allora

allora A−1_{ha autovalori ξ}

k = 1/λn−k+1, con

|ξ1| ≥ |ξ2| ≥ . . . ≥ |ξn| > 0;

(21)

Metodo delle potenze inverse

Applicando il metodo delle potenze ad A−1, con A diagonalizzabile, partendo da t0=Pkαkuk, con αn> 0, kt0k2= 1, qualora

|λ1| ≥ |λ2| ≥ . . .>|λn| > 0, otteniamo la successione {ts} definita da

_γ s = A−1ts−1 ts =_kγγs sk2, ⇔ _Aγ s = ts−1 ts = _kγγs sk2,

e convergenteper direzionead un vettore parallelo a v1= un. La

successione di quozienti di Rayleigh `e tale che, visto che (ts, ts) = ktsk22= 1

ρ(ts, A−1) :=

(A−1ts, ts)

(ts, ts)

= (ts, γs+1) → ξ1= 1/λn. (13)

o similmente, visto che ts tende alla direzione di v1ovvero di un

(22)

Metodo delle potenze inverse

Nota. (Facoltativa)

Si osserva subito che se A−1u = ξiu, con ξi 6= 0, allora Au = A (A−1u/ξi) | {z } u = (1/ξi)u, cio`e ξ_i−1`e un autovalore di A;

se u `e autovettore di A−1 relativo all’autovalore ξi, allora u autovettore di A relativo all’autovalore ξi−1.

Conseguentemente

se ξ1`e l’autovalore di massimo modulo di A−1 e λn`e l’autovalore di minimo modulo di A si ha λn= ξ−1₁ ;

(23)

Metodo delle potenze inverse con shift

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 t0tale che kt0k2= 1, il metodo

delle potenze inverse con shift `e definito da: (A − µI ) γk = tk−1

tk = γk/kγkk2

σk = tkHAtk.

(24)

Metodo delle potenze inverse

Nota.

Il metodo delle potenze inverse genera una sequenza di vettori tk

(25)

Metodo QR

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

Teorema (Fattorizzazione QR)

Sia A una matrice quadrata di ordine n. Esistono Q unitaria (cio`e QT∗ Q = Q ∗ QT _{= I ),} R triangolare superiore

tali che

(26)

Metodo QR

Citiamo alcune cose:

La matrice A ha quale sola particolarità di essere quadrata. Nel caso generale però la sua fattorizzazioneQR in generale non è unicabens`ı 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.

(27)

Metodo QR

Se la matrice H `e similea K (cio`e esiste una matrice non singolare S tale che H = S−1KS ) allora H e K hanno gli stessi autovalori.

Si può vedere facilmente che la relazione disimilitudine è transitiva, cioè se H1 è simile ad H2 e H2 è simile ad H3 allora H1 è simile ad H3.

(28)

Metodo QR

Lemma Sia A0= Q0R0 la fattorizzazione QR di A0 e A1 := R0Q0.

Le matrici A0 e A1 sono simili e quindi hanno gli stessi autovalori. Dimostrazione.

Basta notare che

Q0A1Q0T = Q0R0Q0Q0T = A0

(29)

Metodo QR

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

Metodo (QR)

Posto A0 = A, il metodo QR consiste nel calcolare le iterate Ak definite da

Ak = QkRk

Ak+1 = RkQk

dove ad ogni iterazione viene calcolata la fattorizzazione QR della matrice Ak.

(30)

Metodo QR

Teorema (Convergenza metodo QR)

Se A ∈ Rn×n haautovalori tutti distinti in modulo, con

(31)

Metodo QR

Inoltre

(32)

Implementazione del metodo QR

Nelle implementazioni si calcola con un metodo scoperto da

Householder(ma esiste un metodo alternativo dovuto a Givens) una matrice di Hessenberg T

T =         a1,1 a1,2 a1,3 . . . a1,n a2,1 a2,2 a2,3 . . . a2,n 0 a3,2 a3,3 . . . a3,n 0 0 a4,3 . . . a4,n . . . . 0 0 0 an,n−1 an,n        

simile ad A ed in seguito si applica il metodo QR relativamente alla matrice T .

Nota.

(33)

Implementazione del metodo QR

Si può mostrare che le iterazioni mantengono la struttura, cioè se A0 = T è di Hessenberg, allora Ak è di Hessenberg, se A0 = T è tridiagonale allora Ak è tridiagonale.

Se A `e una matrice Hessenbergallora 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_{i ,i −1}(k) | = O(|λi|/|λi −1|)k

(34)

Nota. (Operazioni trasformazioni in matrici di Hessenberg)

Il numero di moltiplicazioni necessarie

all’algoritmo di Givens per calcolare tale matrice di Hessenberg T a partire da A `e approssimativamente10n3/3;

all’algoritmo di Householder per calcolare tale matrice di Hessenberg T a partire da A `e approssimativamente5n3/3.

Nota. (Costo QR)

Ilmetodo QRapplicato ad una matrice A in forma di Hessenberg superiore ha ad ogni passo un costo di2n2operazioni moltiplicative.

Si osservi che, utilizzando un metodo dovuto a Householder, il costo di una fattorizzazione QRdi una matrice generica ´e diO(2n3_/3)_operazioni

(35)

Implementazione del metodo QR: shift

Nota. (Shift)

Per motivi computazionali, a partire da una matrice in forma di Hessenberg o tridiagonale di dimensione n, si preferisce applicare QR shiftato, dove

A0= A;

Ak− λkI = QkRk;

Ak+1= RkQk+ λkI = Qk∗(Ak− λkI )Qk+ λkI = Qk∗AkQk

Quale λksi possono fare molte scelte, tipicamente (Ak)n,n

Nota. ([3, p.59])

Forsymmetric matrices, the eigenproblem is relatively simple ... and the eigenproblem may be considered as solved:

forsmall matricesn ≤ 25 we have the QR method, one of the most elegant

techniques produced in the field of numerical analysis;

forlarge matrices(but smaller than a few thousand), we have a combination of

divide and conquer with QR techniques;

(36)

Bibliografia

D. Bini, M. Capovani e O. Menchi, Metodi numerici per l’algebra lineare, Zanichelli, 1988. V. Comincioli, Analisi Numerica, metodi modelli applicazioni, Mc Graw-Hill, 1990.