Alvise Sommariva
Universit`
a degli Studi di Padova
Dipartimento di Matematica
Metodo delle potenze
Metodo (Potenze)
Siano
A una matrice diagonalizzabile con autovalori {λj} tali che |λ1| > |λk|
per ogni k > 1,
il vettore iniziale t0
non sia parallelo all’autovettore u1
relativo
all’autovalore λ1.
Il
metodo delle potenze
genera la successione
y0
= t0
Partiamo con una versione
metodo potenze
del metodo delle
potenze
f u n c t i o n [ lambda1 , x1 , niter , err ]= m e t o d o _ p o t e n z e ( A , z0 , toll , nmax ) % INPUT :
% A : MATRICE DI CUI VOGLIAMO CALCOLARE L ’ AUTOVALORE DI MASSIMO MODULO. % z 0 : VETTORE I N I Z I A L E (NON NULLO) .
% t o l l : TOLLERANZA .
% nmax : NUMERO MASSIMO DI ITERAZIONI . % OUTPUT :
% l a m b d a 1 : VETTORE DELLE APPROSSIMAZIONI DELL ’ AUTOVALORE DI MASSIMO MODULO. % x1 : AUTOVETTORE RELATIVO ALL ’ AUTOVALORE DI MASSIMO MODULO.
% n i t e r : NUMERO DI ITERAZIONI .
% e r r : VETTORE DEI RESIDUI PESATI RELATIVI A ” l a m b d a 1 ” . %
q=z0 /norm( z0 ) ; q2=q ; err = [ ] ; l a m b d a 1 = [ ] ; res=t o l l +1; n i t e r =0; z=A∗q ;
w h i l e ( res >= toll & niter <= nmax ) q=z /norm( z ) ; z=A∗q ; lam=q ’ ∗ z ; x1=q ;
z2=q2 ’∗ A ; q2=z2/norm( z2 ) ; q2=q2 ’ ; y1=q2 ; c o s t h e t a=a b s( y1 ’∗ x1 ) ; res=norm( z−lam∗q ) / costheta ;
n i t e r=n i t e r +1; err =[ err ; res ] ; l a m b d a 1 =[ l a m b d a 1 ; lam ] ;
Il metodo delle potenze in Matlab
Il vettore iniziale
z0
e’ normalizzato e e assegnato a
q
;
l’assegnazione
res=toll+1;
forza l’algoritmo ad entrare nel ciclo
while
;
pone
z=A*q
e calcola il coefficiente di Rayleigh
lam=q’*z
; si osservi che essendo
q
un versore
ρ(A, q) =
(q, Aq)
q, q
= q
0
Aq = q
0· z.
pone in
x1
un’approssimazione dell’autoversore destro normalizzato relativo a
λ
1;
di seguito pone in
y1
un’approssimazione dell’autoversore sinistro normalizzato
relativo a λ
1;
nel ciclo
while
,
q
`
e un’approssimazione di un autoversore relativo a λmax,
mentre
lam
di λmax;
il ciclo si interrompe se un numero massimo di iterazioni
niter
`
e raggiunto
oppure
||Aq − λ||
2| cos(θ
λ)|
< tol
Testiamo il codice per il calcolo dell’autovalore di massimo modulo di
A
=
−15.5
7.5
1.5
−51
25
3
−25.5
7.5
11.5
=
1
2
3
2
5
6
7
9
3
·
10
0
0
0
10
0
0
0
1
·
1
2
3
2
5
6
7
9
3
−1(1)
La matrice A `
e diagonalizzabile e ha autovalori 10, 10, 1. Si pu`
o vedere che
una base di autovettori relativa agli autovalori 10, 10, 1 `
e composta da (1, 2, 7),
(2, 5, 9), (3, 6, 3). Quale vettore iniziale del metodo delle potenze consideriamo
z0
= (1, 1, 1) = (7/6) · (1, 2, 7) − 1 · (2, 5, 9) + (11/18) · (3, 6, 3)
e quindi il metodo delle potenze applicato ad A, e avente quale punto iniziale
z0
pu`
o essere utilizzato per il calcolo dell’autovalore di massimo modulo di A,
Il metodo delle potenze in Matlab: esempio I
Dalla shell di Matlab/Octave:
Il metodo delle potenze in Matlab: esempio I
La convergenza `
e abbastanza veloce come si vede dalla quantit`
a
err
, che consiste in un particolare residuo pesato.
Una questione sorge spontanea. Cosa sarebbe successo se avessimo
utilizzato l’algoritmo senza normalizzazione come ad esempio
metodo potenze0
definito da
f u n c t i o n [ lambda , v ]= m e t o d o _ p o t e n z e 0 ( A , x0 , maxit ) v=x0 ;
f o r i n d e x =1: m a x i t v _ o l d=v ; v=A∗v_old ;
l a m b d a =( v_old ’∗ v ) /( v_old ’ ∗ v_old ) ;
Proviamo il test, facendo iterare il metodo prima 5, poi 100 volte e
alla fine 1000 volte (si noti il settaggio della variabile
maxit
relativa al numero di iterazioni da compiere):
Vediamo le ragioni di questo comportamento dell’algoritmo.
Supponiamo che sia per un certo k
At
k
≈ 10t
k
.
Allora per s ≥ k
t
s
≈ A
s−k
· t
k
≈ 10 · A
s−k−1
· t
k
≈ · · · ≈ 10
s−k
· t
k
da cui
kt
s
k
2
≈ 10
s−k
· kt
k
k
2
Il metodo delle potenze in Matlab: esempio II
Proviamo un test diverso, questa volta con la matrice
(diagonalizzabile)
A =
1
2
0
−1
,
avente autovalori λ
1
= 1 e λ
2
= −1 e autovettori linearmente
indipendenti (1, 0), (−1, 1). Quale vettore iniziale poniamo
x
0
= (1, 3) = 4 · (1, 0) + 3 · (−1, 1)
e quindi il metodo delle potenze applicato ad A, partendo da x
0
Dalla shell di Matlab/Octave:
>> A =[1 2 ; 0 −1] A =
1 2
0 −1
>> [ lambda1 , x1 , niter , err ]= m e t o d o _ p o t e n z e ( A , [ 1 ; 3 ] , 1 0 ˆ ( − 8 ) , 1 5 ) l a m b d a 1 = −3.4483 e−002 −2.0000 e−001 . . . −3.4483 e−002 −2.0000 e−001 −3.4483 e−002 −2.0000 e−001 x1 = 3 . 1 6 2 3 e−001 9 . 4 8 6 8 e−001 n i t e r = 16 err = 4 . 4 5 6 7 e−001 2 . 4 0 0 0 e+000 . . . 4 . 4 5 6 7 e−001 2 . 4 0 0 0 e+000 4 . 4 5 6 7 e−001 2 . 4 0 0 0 e+000 >>
Dal residuo pesato `
e chiaro che il metodo non converge, e come
anticipato il motivo `
e la presenza di autovalori distinti aventi
Il metodo delle potenze in Matlab: esempio III
Vediamo il caso della matrice diagonalizzabile (autovalori distinti!)
A =
1
2
0
10
,
in cui il metodo funziona rapidamente (λmax = 10).
>> A =[1 2 ; 0 1 0 ] ; [ lambda1 , x1 , niter , err ]= m e t o d o _ p o t e n z e ( A , [ 1 ; 3 ] , 1 0 ˆ ( − 8 ) , 1 5 ) l a m b d a 1 = 9 . 9 7 7 9 e+000 9 . 9 9 7 9 e+000 9 . 9 9 9 8 e+000 . . . 1 . 0 0 0 0 e+001 1 . 0 0 0 0 e+001 1 . 0 0 0 0 e+001 x1 = 2 . 1 6 9 3 e−001 9 . 7 6 1 9 e−001 n i t e r = 8 err = 9 . 6 7 2 6 e−002 9 . 7 5 2 9 e−003 9 . 7 6 1 0 e−004 . . . 9 . 7 6 1 9 e−007 9 . 7 6 1 9 e−008 9 . 7 6 1 9 e−009
Una versione di base
metodo potenze inverse
del
metodo delle
potenze inverse
`
e
f u n c t i o n [ lambda , x , niter , err ]= m e t o d o _ p o t e n z e _ i n v e r s e ( A , z0 , mu , toll , nmax ) % DATO UN VALORE mu , S I CALCOLA L ’ AUTOVALORE ” lambda mu ” PIU ’ VICINO A mu . % INPUT :
% A : MATRICE DI CUI VOGLIAMO CALCOLARE L ’ AUTOVALORE ” lambda mu ” . % z 0 : VETTORE I N I Z I A L E (NON NULLO) .
% mu : VALORE DI CUI VOGLIAMO CALCOLARE L ’ AUTOVALORE PIU ’ VICINO . % t o l l : TOLLERANZA .
% nmax : NUMERO MASSIMO DI ITERAZIONI . %
% OUTPUT :
% lambda : VETTORE DELLE APPROSSIMAZIONI DELL ’ AUTOVALORE DI MINIMO MODULO. % x : AUTOVETTORE RELATIVO ALL ’ AUTOVALORE DI MINIMO MODULO.
% n i t e r : NUMERO DI ITERAZIONI .
% e r r : VETTORE DEI RESIDUI PESATI RELATIVI A ” lambda ” . %
Il metodo delle potenze inverse in Matlab
n=max(s i z e( A ) ) ; M=A−mu∗e y e( n ) ; [ L , U , P ]=l u( M ) ; q=z0 /norm( z0 ) ; q2=q ’ ; err = [ ] ; l a m b d a = [ ] ; res=t o l l +1; n i t e r =0;
w h i l e ( res >= toll & niter <= nmax ) n i t e r=n i t e r +1; b=P∗q ; y=L\b ; z=U\y ; q=z /norm( z ) ; z=A∗q ; lam=q ’ ∗ z ;
b=q2 ’ ; y=U ’ \ b ; w=L ’ \ y ; x=q ;
q2=(P ’∗ w ) ’ ; q2=q2/norm( q2 ) ; c o s t h e t a=a b s( q2∗q ) ;
i f ( c o s t h e t a > 5e−2)
res=norm( z−lam∗q ) / costheta ; err=[err ; res ] ; lambda =[ lambda ; lam ] ;
e l s e
d i s p(’ \n \ t [ ATTENZIONE ] : AUTOVALORE MULTIPLO ’) ; b r e a k;
Forniamo ora alcune spiegazioni del codice in
metodo potenze inverse
.
Per risolvere il sistema lineare proprio del metodo delle
potenze inverse, si effettua una fattorizzazione PM = LU
della matrice M = A − µI ;
All’interno del ciclo while, nella prima riga si calcola z
k
,
mentre nella successiva un suo versore q
k
, e σ
k
`
e
immagazzinato in
lam
;
Il metodo delle potenze inverse in Matlab: esempio I
Applichiamo il metodo delle potenze inverse per il calcolo dell’autovalore pi`
u
piccolo in modulo della matrice
A
=
−15.5
7.5
1.5
−51
25
3
−25.5
7.5
11.5
=
1
2
3
2
5
6
7
9
3
·
10
0
0
0
10
0
0
0
1
·
1
2
3
2
5
6
7
9
3
−1(2)
Come visto la matrice A `
e quindi diagonalizzabile, ha autovalori 10, 10, 1 e
relativi autovettori `
e (1, 2, 7), (2, 5, 9), (3, 6, 3) formanti una base di R
3. Quale
vettore iniziale consideriamo
z0
= (1, 1, 1) = (7/6) · (1, 2, 7) − 1 · (2, 5, 9) + (11/18) · (3, 6, 3)
e quindi il metodo delle potenze inv. applicato ad A, e avente quale punto
>> z0 = [ 1 ; 1 ; 1 ] ; mu =0; toll =10ˆ(−8) ; nmax =10; >> A =[ −15.5 7 . 5 1 . 5 ; −51 25 3 ; −25.5 7 . 5 1 1 . 5 ] ;
>> [ lambda , x , niter , err ]= m e t o d o _ p o t e n z e _ i n v e r s e ( A , z0 , mu , toll , nmax ) l a m b d a = 0 . 3 9 0 1 6 1 1 5 3 5 1 9 9 3 0 . 9 4 2 3 7 5 6 3 9 4 1 2 6 8 0 . 9 9 4 2 6 9 2 2 9 3 6 8 5 4 0 . 9 9 9 4 2 7 2 3 7 7 6 6 5 6 0 . 9 9 9 9 4 2 7 2 6 9 2 3 1 5 0 . 9 9 9 9 9 4 2 7 2 7 2 3 7 8 0 . 9 9 9 9 9 9 4 2 7 2 7 2 7 0 0 . 9 9 9 9 9 9 9 4 2 7 2 7 2 8 0 . 9 9 9 9 9 9 9 9 4 2 7 2 7 3 x = 0 . 4 0 8 2 4 8 2 9 0 5 3 8 0 9 0 . 8 1 6 4 9 6 5 8 0 8 5 3 5 0 0 . 4 0 8 2 4 8 2 9 0 5 3 8 0 9 n i t e r = 9 err = 0 . 8 1 5 3 5 2 1 6 5 0 7 3 7 7 0 . 0 8 3 5 8 1 0 1 2 8 9 0 6 2 0 . 0 0 8 3 8 1 2 6 2 5 8 3 9 6 0 . 0 0 0 8 3 8 3 6 0 7 8 8 9 1 0 . 0 0 0 0 8 3 8 3 8 4 2 7 1 2 0 . 0 0 0 0 0 8 3 8 3 8 6 6 2 0 0 . 0 0 0 0 0 0 8 3 8 3 8 6 8 5 0 . 0 0 0 0 0 0 0 8 3 8 3 8 6 8 0 . 0 0 0 0 0 0 0 0 8 3 8 3 8 7 >>
La convergenza `
e lineare (come si intuisce dalle approssimazioni
Il metodo delle potenze inverse in Matlab: esempio I
1 2 3 4 5 6 7 8 9 10−9 10−8 10−7 10−6 10−5 10−4 10−3 10−2 10−1 100Per vederlo, dalla shell di Matlab/Octave calcoliamo l’errore
assoluto/relativo relativo all’autovalore 1:
>> s=1−lambda s = 0 . 6 0 9 8 3 8 8 4 6 4 8 0 0 7 0 . 0 5 7 6 2 4 3 6 0 5 8 7 3 2 0 . 0 0 5 7 3 0 7 7 0 6 3 1 4 6 0 . 0 0 0 5 7 2 7 6 2 2 3 3 4 4 0 . 0 0 0 0 5 7 2 7 3 0 7 6 8 5 0 . 0 0 0 0 0 5 7 2 7 2 7 6 2 2 0 . 0 0 0 0 0 0 5 7 2 7 2 7 3 0 0 . 0 0 0 0 0 0 0 5 7 2 7 2 7 2 0 . 0 0 0 0 0 0 0 0 5 7 2 7 2 7 >> s e m i l o g y( 1 :l e n g t h( s ) , s )
Il metodo QR in Matlab
Nel metodo
QR
, data una matrice A, la si trasforma in una matrice
simile in forma di Hessenberg A
0
= T e quindi si eseguono le
iterazioni
A
k
= Q
k
R
k
, A
k+1
= R
k+1
Q
k+1
Una versione di base del metodo QR `
e la seguente. Si salvi il files
houshess.m
che implementa la trasformazione per similitudine di A
in una matrice di Hessenberg
f u n c t i o n [ H , Q ]= h o u s h e s s ( A )
Il metodo QR in Matlab
ove
vhouse.m
`
e definito da
f u n c t i o n [ v ,b e t a]= vhouse ( x ) % BUILDING HOUSEHOLDER VECTOR .
A partire da queste routines,
metodo QR.m
determina la matrice
(quasi-)triangolare (a blocchi) T descritta nel teorema di convergenza del
metodo QR.
f u n c t i o n [ T ,h i s t]= m e t o d o _ Q R ( T_input , maxit )
% QR METHOD FOR A SYMMETRIC TRIDIAGONAL MATRIX ” T i n p u t ” . T=T _ i n p u t ;
h i s t=s o r t(d i a g( T ) ) ;
f o r i n d e x =1: m a x i t [ Q , R ]=q r( T ) ;
T=R∗Q ; % NEW SIMILAR MATRIX .
h i s t=[h i s t s o r t(d i a g( T ) ) ] ; % IT STORES THE DIAGONAL ELEMENTS % OF THE ” i n d e x ” ITERATION .
end
Il codice non `
e ovviamente ottimizzato e si interrompe dopo
maxit
iterazioni,
Il metodo QR: esempio I
>> maxit =100; siz =2; A=g a l l e r y(’ p o i s s o n ’, siz ) ; A=f u l l( A ) ; eigs=e i g( A ) ; >> [ H , Q ]= h o u s h e s s ( A ) ; % H s i m i l e ad A , ma d i H e s s e n b e r g . >> [ T ,h i s t]= m e t o d o _ Q R ( H , maxit ) ; >> A A = 4 −1 −1 0 −1 4 0 −1 −1 0 4 −1 0 −1 −1 4 >> H H = 4 . 0 0 0 0 1 . 4 1 4 2 0 . 0 0 0 0 −0.0000 1 . 4 1 4 2 4 . 0 0 0 0 1 . 4 1 4 2 −0.0000 −0.0000 1 . 4 1 4 2 4 . 0 0 0 0 −0.0000 0 −0.0000 −0.0000 4 . 0 0 0 0 >> f o r m a t s h o r t e >> T T =
6 . 0 0 0 0 e+00 9 . 4 2 0 8 e−16 −5.5511 e−17 −9.5075 e−16 6 . 9 5 7 0 e−18 4 . 0 0 0 0 e+00 3 . 9 9 8 3 e−29 −9.0478 e−16 −1.9914 e−50 −7.8505 e−17 4 . 0 0 0 0 e+00 8 . 6 8 6 0 e−14 0 −5.6281 e−30 8 . 6 5 3 9 e−14 2 . 0 0 0 0 e+00 >> eigs ’
a n s =
Vediamo in un secondo esempio che il metodo QR converge in una
matrice diagonale con alcuni ”blocchi” qualora la matrice A abbia due
autovalori diversi ma di uguale modulo.
>> D=d i a g( [ 1 2 −2 3 ] ) ; S=r a n d( 4 ) ; A=S∗D∗i n v( S ) ; >> [ H , Q ]= h o u s h e s s ( A ) ; >> [ T ,h i s t]= m e t o d o _ Q R ( H , 1 0 0 ) ; >> f o r m a t s h o r t e >> T T =
3 . 0 0 0 0 e+00 8 . 2 4 2 2 e+00 −2.8779 e+00 −3.8054 e+01 −1.3367 e−17 −1.8374 e+00 1 . 9 6 0 2 e+00 1 . 5 5 0 1 e+01 −3.8960 e−34 3 . 1 8 4 0 e−01 1 . 8 3 7 4 e+00 −3.6759 e+00 2 . 7 8 9 9 e−64 4 . 0 1 9 1 e−46 5 . 2 7 0 0 e−31 1 . 0 0 0 0 e+00 >>
