Cursul 6Metode aproximative de

rezolvare a sistemelor de ecuaţiirezolvare a sistemelor de ecuaţii liniare

Rezolvarea numerică a ecuaţiilor ţalgebrice

Convergenta metodelor Convergenta metodelor aproximative. Metoda iterativa a lui Jacobi Metoda iterativa a lui Jacobi, Gauss-Seidel.

Convergenta metodelor gaproximative:

Metodele exacte de rezolvare a sistemelorde ecuaţii liniare, având complexitate O(n3), au aplicabilitate limitată la ordine de sistemeau aplicabilitate limitată la ordine de sistemece nu depăşesc 1000.

Pentru sisteme de dimensiuni mai mari se ili ă d l i 2 îutilizează metode cu complexitate O(n2) într-

un pas de iteraţie. Acestea utilizează relaţii de recurenţă care Acestea utilizează relaţii de recurenţă, care

prin aplicare repetată furnizeazăaproximaţii cu precizie controlată a soluţiei sistemuluisoluţiei sistemului.

Convergenta metodelor aproximative:Sistemul Ax=b este adus la forma echivalentă

x=G.x+c.

Pornindu-se cu o aproximaţie iniţială x(0) a soluţiei se generează folosind o relaţiesoluţiei se generează, folosind o relaţieiterativă de forma:x(p+1)=G. x(p) +c

un şir de vectori: x(0),x(1),…,x(p),…

Matricea G reprezintă matricea de iteraţie, iarc - vectorul de iteraţie.

Aplicarea intr un pas a iteraţiei are Aplicarea, intr-un pas, a iteraţiei are complexitatea O(n2).

Convergenta metodelor aproximative:

Condiţiile în care şirul este convergent poartă numele de condiţii de stabilitate).

In ipoteza convergenţei şirului*)p(

pxxlim =

∞→

Relatia de recurenta este verificata de aceasta limita

p ∞→

cxGx ** +⋅=

scazand din relatia iterativa se obtine

( ),xxGxx *)1p(*)p( −⋅=− −( ).eGeGeGe

,)0(p)2p(2)1p()p( ⋅==⋅=⋅= −− L

Convergenta metodelor aproximative:

Pentru un sir convergent0esi0elim )0()p(

p≠=

∞→

0Glim pp

=∞→

Condiţia de stabilitate admite reprezentărileechivalente:

1G <

( ) .1Gρ,1G

<

<

în care ρ(G) reprezintă cea mai mare valoareproprie în valoare absolută a matricei de proprie în valoare absolută a matricei de iteraţie (raza spectrală).

Convergenta metodelor

Si l t t d i d l

aproximative:Sirul este convergent daca incepand cu rangul p

se verifica o conditie Cauchy)p()p()1p( <+

în unui număr maxim admis de iteraţii p<Maxl b ă dă l

)p()p()1p( xεxx ⋅<−+

Limita şirului trebuie să coincidă cu soluţia exactă a sistemului de ecuaţii liniare, adică

x*=x

relaţie cunoscută sub numele de condiţie de consistenţă.

O metodă stabilă şi consistentă este O metodă stabilă şi consistentă este convergentă.

Metodele iterative Jacobi:Se considera sistemul de ecuatii linearea

A·x=bd lSe descompune matricea sistemului

sub formaA=N-P

impunând condiţia ca matricea N sa impunând condiţia ca matricea N sa fie uşor de inversat.ş

Metodele iterative Jacobi:

( )bNxPNx

,bxPN11 ⋅+⋅⋅=

=⋅−−− .bNxPNx ⋅+⋅⋅=

Aceasta sugereaza adoptarea relatiei de t

bNxPNx 1)p(1)1p( ⋅+⋅⋅= −−+

recurenta:

Similara cu relatia de recurenta initiala, avand:

,PNG 1 ⋅= −

avand:

1 bNc 1 ⋅= −

Metodele iterative Jacobi:

Se partiţionează matricea A punândîn evidenţă o matrice diagonală D, în evidenţă o matrice diagonală D, o matrice strict inferior triunghiulară L (cu elementetriunghiulară L (cu elementediagonale nule) şi o matrice strict

i t i hi l ăsuperior triunghiulară UA=D-L-UU

Metodele iterative Jacobi:N=DP=L+U

1GJ=D-1(L+U)D.x(p+1)=(L+U).x(p)+b

Pentru componenta I se obtinen

ij,1j)p(

jiji)1p(

xab ∑≠=+

⋅−

ii

ij,1j)1p(i ax ≠+ =

Metodele iterative Jacobi:Pentru obtinerea conditiei de convergenta se

porneste de la matricea de iteratie GJ, care l t lare elementele

ijaδG −=ii

ijij aδG −=

an ijn∑∑ 1a

amaxgmaxG1j ii

iji1j

iji<== ∑∑

==∞

Metoda Jacobi converge daca A este diagonal dominanta.

N=D LMetoda Gauss-Seidel:N=D-LP=UG =(D-L)-1UGGS=(D-L) U(D-L)x(p+1)=Ux(p)+b

n1i−

ii

1ij)p(

jij)1p(

j1j

iji)1p(

i axaxab

x∑∑

+=

+

=+

⋅−⋅−=

Teorema: Metoda Gauss-Seidel este convergentă dacă matricea sistemului este di l d i tă li ii

iia

diagonal dominantă pe linii.Teorema: (Reich) Metoda Gauss-Seidel este

convergentă dacă matricea sistemului este convergentă dacă matricea sistemului este simetrică şi pozitiv - definită.

Metoda suprarelaxării:Pentru găsirea unei descompuneri cât mai

rapid convergente se introduce parametrul de relaxare w:

A=N-P=N-wN-P+wN=(1-w)N-(P-wN)==N(w)-P(w)cu N(w)=(1-w)N si P(w)=P-wNcu N(w)=(1-w)N si P(w)=P-wN

( )NPN)(P)(N)(G1

1−

− ( )NwPw1)w(P)w(N)w(G 1 ⋅−⋅−

=⋅=

IwG ⋅( ) w1IwGwG n

−⋅−

=

Metoda suprarelaxării:Dacă se notează cu λi valorile proprii

ale matricei G=N-1P , atunci,valorile proprii ale matricei G(w)vor fivor fi

wλ)w(λ i −= w1)w(λ i −=

C diti d t i

Metoda suprarelaxării:Conditia de convergenta impune ca:

( ) ( ) 1wλmax)w(Gρ ii<=

Se determina w* astfel ca:

i

sau

( )( ) ( )( )wGρminwGρw

* =

sau

( ) ( )wλmaxminwλmax i*

i =( ) ( )wλmaxminwλmax iiwi

i

wλmaxminwλmax i*

i −=

−w1maxminw1max

i1w*i −=

− =

Metoda suprarelaxării:In practică, metoda suprarelaxării ia

( ) LDw1wN −⋅=

( ) UD1w1wP +⋅⎟

⎠⎞

⎜⎝⎛ −=

⎠⎝

( ) ( )[ ]UwDw1LwDG 1w ⋅+⋅−⋅⋅−= −

Metoda suprarelaxării:Dacă Aii≠0, atunci

ρ(Gw)>w-1

şi condiţia de stabilitate impune ca 0 < w < 2.

Dacă matricea este tridiagonală şi pozitiv-definită, atunci valoarea optimă a parametrului de relaxare este

2w =( )2J

optim Gρ11w

−+=

Metoda suprarelaxării:

Relaţia de recurenţă are în acest caz forma

( ) ( ) bxwPxwN )k()1k( +⋅=⋅ +

bxUDww1xLDw

1 )k()1k( +⋅⎟⎠⎞

⎜⎝⎛ −⋅

−=⋅⎟

⎠⎞

⎜⎝⎛ +⋅ +

in

)k(jij

)k(iii

)1k(j

1iij

)1k(iii bxAxAw

w1xAxAw1

+−⋅−

=+⋅ ∑∑ +−

+

1ij1j ww +==

( ) i)k(j

n ij)k(i

)1k(j

1i ij)1k(i A

bwxAAwxw1xA

Awx +−−+−= ∑∑ +−

+

iij

1ij iij

1j ii AAA ∑∑+==