Calcul Numeric

Cursul 9

2015

Anca Ignat

1

Teorema lui Gershgorin Fie in nA o valoare proprie oarecare a matricii A. Atunci:

0 0 0 0 0

0

01

1,2, , astfel nc t .n

i i i i i jjj i

i n a r r a

(Valoarea proprie se afl n cercul din planul complex de centru

0 0 0i razi i ia r .)

Demonstraie. Fie o valoare proprie a matricii A i u 0 un vector propriu asociat valorii proprii , .Au u Avem:

2

1 1( ) , 1, , .

n n

i ii i ij j ii i ij jj jj i j i

u a u a u a u a u i n

Fie i0 astfel ca

0max ; 1, , 0 0).i ku u u k n u

Vom avea:

innd seama c0 0 0 0 0

0 0 00 0

1 1, 1.

n nj jj

i i i j i j ij ji i ij i j i

u uua a a r

u u u

3

Observaie. Presupunem c matricea A are n vectori proprii liniar independeni 1 2, , , nu u u asociai valorilor proprii 1, 2, ..., n Fie 1 2 nU u u u . Datorit independenei vectorilor uk rezult c matricea U este nesingular i avem: diag 1 2, , , n 1 .U AU Considerm matricea perturbat:

.A A B 1 1U A U U BU C .

au aceleai valori proprii1( ) ( ) ( )iA U A U

1.

n

i ii ij ijj i

c c

4

Metoda puterii pentru matrici simetrice

Propoziie

Fie , .n n TA A A Atunci toate valorile proprii ale matricii A sunt numere reale. Demonstraie. Fie i , 0 .nu u Au u Considerm produsul scalar:

22, , .n nAu u u u u , , , , ,n n n nnTAu u u A u u Au Au u Au u

22

, nAu uu

.

5

Propoziie Fie , .n n TA A A Atunci exist o baz ortonormat de vectori proprii ai matricii A, {u1, u2,..., un} :

dac dac 1, 0ni j ij i ju u i j Echivalent, putem scrie ca exist vect. proprii {u1, u2,..., un}

asociai valorilor proprii reale {1, 2,..., n} atfel ca:

cu diag i matrice ortogonal1 21 2[ , , ..., ] [ ]

T

nn

AU U U AUU u u u

6

Definiie Se numete coeficient Rayleigh al vectorului nu pentru matricea A urmtoarea mrime scalar:

22

, ,( )

, || ||n n

n

T

T

Au u Au uu Aur uu u u u u

Se verific uor c dac nu este vector propriu al matricii A asociat valorii proprii atunci r(u)= . Fie , .n n TA A A Matricea are valori proprii reale 1, 2,..., n. Presupunem n plus c:

1 2| | | | | | 0n

7

Metoda puterii este un algoritm care aproximeaz valoarea proprie de modul maxim 1 i un vector propriu asociat. Se pornete de la un vector nenul de norm euclidian 1,

(0) nu , (0) 2|| || 1u i se construiete urmtorul ir de vectori de norm euclidian 1:

(0) (1) (0) (2) (1)(0) (1)

2 2

( ) ( 1)( 1)

2

1 1, , , ... ,|| || || ||

1 , ...|| ||

k kk

u u Au u AuAu Au

u AuAu

8

n anumite condiii acest ir converge la un vector propriu asociat valorii proprii 1, iar coeficienii Rayleigh corespunztori converg ctre 1. Teorem

Fie ,n n TA A A o matrice simetric pentru care valorile proprii ndeplinesc condiia:

1 2| | | | | | 0n . Dac (0) nu , (0) 2|| || 1u , (0) 1( , ) 0nu u (u1 vector propriu asociat lui 1) atunci:

vector propriu asociat lui ( ) (0) 1 1(0)2

( )1

1 ( )|| ||

( )

k kk

k

u A u uA u

r u

9

Demonstraie. Fie {u1, u2,..., un} vectori proprii asociai valorilor proprii {1, 2,..., n} care formeaz o baz ortonormat n n . Avem:

(0) 1 21 2 ,

nn iu a u a u a u a

Deoarece (0) 1( , ) 0nu u rezult c a1 0. Din construcia irului u(k) deducem c exist o constant ck astfel ca:

( ) (0)

1 21 2

1 21 1 2 2

1 221 1 2

1 1

( )

( )

k kk

k nk n

k k k nk n n

k kk nn

k n

u c A u

c A a u a u a u

c a u a u a u

c a u a u a u

10

Din aceast ultim relaie, din faptul c 1 este valoare proprie dominant i a1 0 deducem c pentru k suficient de mare vectorul u(k) se aliniaz dup vectorul propriu u1:

( ) 11 1

k kku c a u

11

i

(0) (0)2

( 1)

( )

2

( ) ( ) ( )

( ) ( )max

, || || 1;0;

;;

1 ;|| ||

( ) , ;

(|| || );n

n

k

k

k k kk

k kk

u ukdo

kw Au

u ww

r u Au u

while Au u k k

Metoda puterii

12

Metoda iteraiei inverse Considerm o matrice simetric ,n n TA A A i un numr real care nu este valoare proprie a matricii A. Vom folosi

metoda puterii pentru a aproxima valoarea proprie a matricii A

care este cea mai apropiat de i un vector propriu asociat.

valoare proprie 1det ( ) 0 ( )n nA I A I Fie {1, 2,..., n} valorile proprii reale ale matricii A.

Valorile proprii ale matricii (A-In)-1 sunt:

1 2

1 1 1, , ... ,( ) ( ) ( )n

13

Matricile A i (A-In)-1 au aceiai vectori proprii. S presupunem

c I este valoarea proprie cea mai apropiat de (i singura).

Atunci:

1 1| | | |I j

j I

Aceast relaie sugereaz ideea aplicrii metodei puterii

matricii (A - In)-1 pentru a aproxima valoarea proprie (I )-1 i

a unui vector propriu asociat. Algoritmul duce la aproximarea

valorii proprii cea mai apropiat de , I i a unui vector propriu

asociat acestei autovalori, uI.

14

Se rezolv sistemul

i

(0) (0)2

( 1)

( )

2

( ) ( ) ( )

( ) ( )max

, || || 1;0;

;( ) ;

1 ;|| ||

( ) , ;

(|| || );n

n

kn

k

k k kk

k kk

u ukdo

kA I w u

u ww

r u Au u

while Au u k k

Metoda iteraiei inverse