Analisi Numerica:
AutoValori e Autovettori
Valentina Campisi
Autovalori e Autovettori (1/2)
Sia ACnxn.
Un vettore vCn, v≠0 si dice autovettore per A se
Av = v con C
 è detto autovalore per A.
Si ricava il sistema (A-I)v = 0.
Da cui segue che gli autovalori sono le radici del polinomio
caratteristico
pA()=det(A-I)
cioè� i valori per cui la matrice A-I è� singolare e quindi il
sistema ammette soluzioni diverse da v=0 .
Autovalori e Autovettori (2/2)
Ricavarsi gli autovalori in questo modo comporta il calcolo del
determinante di una matrice che � una operazione
altamente costosa.
Si cercano quindi strade alternative per la ricerca degli
autovalori.
Noi considereremo solo uno di questi metodi, che si applica ad
un caso molto particolare e tuttavia molto frequente nelle
applicazioni: la ricerca dell'autovalore dominante cio�è di
un autovalore maggiore in modulo di tutti gli altri.
Quoziente di Rayleigh
L’autovalore  corrispondente all’autovettore v si ottiene calcolando
il quoziente di Rayleigh
=vTAv/ vTv
Implementazione:
function [lam,x] = ray_quo
Riceve in input la matrice A a partire da un vettore non nullo
calcola il quoziente di Rayleigh per restituire l’autovalore in lam e
in x l’autovettore associato
Metodo delle Potenze (1/3)
Supponiamo che la matrice A abbia un autovalore dominante
1 tale che
| 1|> | 2|≥…. ≥ | n|
Il metodo delle potenze fornisce un metodo iterativo per
approssimare l'autovalore dominante.
Dato un vettore di innesco u0≠0 si definisce una successione di
vettori in questo modo:
uk+1 = A uk
Si pu�ò dimostrare che l'autovalore dominante �
approssimato dalla seguente espressione:
k= (uk)Tuk+1 / (uk)Tuk
Metodo delle Potenze (2/3)
Per evitare problemi di overflow o underflow si usa una versione
normalizzata del metodo delle potenze, nella quale tutti i vettori
uk sono divisi per la loro norma in modo che la norma dei vettori
cos� ottenuti sia sempre unitaria.
yk= uk /||uk||2
uk+1 = Ayk
k+1= (yk)Tuk+1/ (yk)Tyk= (yk)Tuk+1
dove l'ultima eguaglianza deriva dal fatto che
(yk)Tyk=||yk||2=1
Metodo delle potenze (3/3)
• Implementazione:
La procedura metodoPotenze utilizza lo schema usando come
condizione di arresto | k- k-1 |<.
[lambda,x,iter]=potenze
Riceve in A la matrice di cui si vuole calcolare l'autovalore
dominante, in x0 un vettore di innesco (non nullo), in toll
l’accuratezza desiderata e in nmax un limite superiore al
numero di iterazioni.
Restituisce in lambda l'approssimazione dell'autovalore
dominante, in x l’autovettore e in iter il numero di iterazioni
effettuate.
Matrice di Hessenberg
Siano A,B simili, aventi cioè gli stessi autovalori,
  S, S-1 : A=SBS-1
Inoltre,per motivi di efficienza, il calcolo degli autovalori di B
deve essere più facile di quello di A. Se B è triangolare gli
autovalori sono gli elementi della diagonale.
Si ha: U : A=UTU* dove T è triangolare superiore.
Ma ricavare A in questo modo non è semplice allora troviamo S
tale che B=SAS-1 sia una matrice di Hessenberg:
H = h11
h21
0
h12 ….
h1n
h21
. h2n
.
.
.
.
hmn-1 hmn
Per ridurre una matrice qualunque in forma di Hessenberg
utilizziamo il metodo di HouseHolder
Metodo di Householder (1/2)
Se v �è dato come un vettore colonna unità� e I �è la matrice
identità la trasformazione lineare è data dalla matrice di
Householder
P=I-2vvT/vTv
La matrice di Householder ha le seguenti propriet�à:
• simmetrica: P = PT
• ortogonale: P-1 = PT
Si trova che P riflette effettivamente un punto x, che viene
rappresentato con il suo vettore posizione x:
Px = x − 2vvTx
Questo vettore è detto vettore di riflessione o di Householder
Metodo di Householder (2/2)
Implementazione:
Ciascun passo k-esimo consiste in una trasformazione per
similitudine di A tramite la matrice di Householder che ha l’effetto
di rendere nulli gli elementi di posizione di k+2,..,n della colonna
k-esima della matrice per k=1,..,n-2.
function [Q,H] = houseHolder_Hessenberg(A)
Riceve in A una matrice e restituisce in H la matrice trasformata in
forma di Hessenberg e in G la matrice ortognale.
Per il calcolo del vettore di Householder si utlizza il programma:
function[v,beta]=vHouse(x)
Metodo di Givens
Le matrici di Givens sono matrici di rotazioni ortogonali che hanno
la proprietà di annullare selettivamente singoli elementi di una
matrice o di un vettore. Fissati due indici i e K e un certo angolo
, esse sono definite come:
G(i,k,) = I - Y
nxn
dove YC è una matrice identicamente nulla fatta eccezione per
gli elementi yii = ykk = 1-cos e yik = -sin = -yki
G(i,k,) =
1
0
1
cos sin
-sin cos
1
0
1
Data una matrice possiamo calcolare la fattorizzazione QR, ottenendo
A=QR che tende ad assumere una forma triangolare. Utilizziamo
function [Q,R]=rotqr_demo(A)