sisteme de ecuatii algebrice liniare - metode iterative...

1/56

IntroducereMetoda gradientilor conjugati

PreconditionareReferinte

Sisteme de ecuatii algebrice liniare - metodeiterative nestationare (semiiterative)

Prof.dr.ing. Gabriela Ciuprina

Universitatea "Politehnica" Bucuresti, Facultatea de Inginerie Electrica,Departamentul de Electrotehnica

Suport didactic pentru disciplina Algoritmi Numerici, 2016-2017

Gabriela Ciuprina Sisteme de ecuatii algebrice liniare - metode semiiterative

2/56



Cuprins

1 IntroducereFormularea problemeiMetode stationareIdeea metodei gradientilor conjugati

2 Metoda gradientilor conjugatiMetoda gradientuluiMetoda directiilor conjugateMetoda gradientilor conjugati

3 Preconditionare

4 Referinte


3/56



Formularea problemeiMetode stationareIdeea metodei gradientilor conjugati

Formularea problemei

Sistem de n ecuatii algebrice liniare cu n necunoscute:

a11x1 + a12x2 + · · ·+ a1nxn = b1,a21x1 + a22x2 + · · ·+ a2nxn = b2,· · ·an1x1 + an2x2 + · · ·+ annxn = bn.

(1)


4/56




Formularea problemei

Se da matricea coeficientilor

A =

a11 a12 · · · a1n

a21 a22 · · · a2n

· · ·an1 an2 · · · ann

∈ IRn×n (2)

si vectorul termenilor liberi

b =[

b1 b2 · · · bn]T

∈ IRn, (3)

se cere sa se rezolve sistemul

Ax = b, (4)

unde x este solutia

x =[

x1 x2 · · · xn]T

∈ IRn. (5)


5/56




Buna formulare matematica

Problema este bine formulata din punct de vedere matematic(solutia exista si este unica)⇔matricea A este nesingulara (are determinantul nenul).Se scrie formal:

”x = A−1b”

trebuie citita ca:"x este solutia sistemului algebric liniar Ax = b"si NU "se calculeaza inversa matricei A care se înmulteste cuvectorul b".


6/56




Clasificarea metodelor

1 Metode directe - gasesc solutia teoretica a problemeiîntr-un numar finit de pasi. (Gauss, factorizare LU)

2 Metode iterative - genereaza un sir de aproximatii alesolutiei care se doreste a fi convergent catre solutiaexacta.

stationare: Jacobi, Gauss-Seidel, SOR, SSORnestationare (semiiterative): gradienti conjugati (GC),reziduu minim (MINRES), reziduu minim generalizat(GMRES), gradienti biconjugati (BiGC), etc.


7/56




Ideea metodelor stationare

Ax = b

A = B − C

Bx (k+1) = Cx(k) + b. (6)

B(x(k+1) − x(k)) = b − Ax (k). (7)

Reziduul la iteratia k

r(k) = b − Ax (k), (8)

x(k+1) = x(k) + B−1r(k), (9)Stationaritatea se refera la faptul ca reziduul este întotdeauna înmultitcu matricea B−1, aceeasi pe parcursul tuturor iteratiilor:Jacobi: B = D; Gauss-Seidel: B = D + L; SOR: B = ω−1(D + ωL).Nu se face inversarea propriu zisa, ci se rezolva un sistem algebricliniar.


8/56




Algoritmul general al metodelor stationare

procedur a metoda_iterativa_stationara(n, B, A, b, x0, er, maxit, x)· · ·xv = x0 ; initializeaza sirul iteratiilork = 0 ; initializare contor iteratiirepet a

r = b − A · xv ; calculeaza reziduumetoda_directa (n, B, r, z)d = ‖z‖x = xv + zxv = x ; actualizeaza solutia vechek = k + 1

cât timp d > er si k ≤ maxitretur

Metodele iterative

+ sunt eficiente pentru matrici rare deoarece ele nugenereaza umpleri.

- s-ar putea sa nu fie convergente.


9/56




Clasa de probleme

Este o metoda iterativa nestationara, pentru rezolvarea unorsisteme de ecuatii algebrice de forma

Ax = b, (10)

unde A este simetrica si pozitiv definita.

Algoritmul metodei gradientilor conjugati (GC) este eficientpentru matrice rare.

⇒ Pseudocodurile vor fi descrise simplificat, evidentiindoperatii de algebra liniara, presupuse a fi implementate tinândcont de raritatea structurilor de date.


10/56




Forma patratica

Metoda GC este simplu de înteles daca ea este formulata ca oproblema de minimizare.Fie o forma patratica

f : IRn → IR

f (x) =12

xT Ax − bT x + c, (11)

unde A ∈ IRn×n, x, b ∈ IRn×1, c ∈ IR.

Teorema

Daca A este simetrica si pozitiv definita, atunci functia f (x) datade (11) este minimizata de solutia ecuatiei Ax = b .


11/56




Forma patratica

Justificarea teoremei:

f (x) =12

xT Ax − bT x + c (12)

∇f (x) =12

AT x +12

Ax − b. (13)

În punctul de minim gradientul este zero

∇f (x) = 0 ⇒12(AT + A)x = b. (14)

Daca AT = A (matrice simetrica) atunci (14) ⇔ Ax = b.⇒ solutia ecuatiei Ax = b este punct critic pentru f .Daca în plus, A pozitiv definita, atunci pct.critic este un minim.


12/56




Matrice pozitiv definita - intuitiv

−40−20

020

40

−40

−20

0

20

40−2000

0

2000

4000

6000

8000

10000

x1

A = [3 , 1.41 ; 1.41 , 4]

x2

f = x

T A

x −

bT x

Functia patratica asociata unei matrice pozitiv

definite. Minimul functiei coincide cu solutia

sistemului. GC functioneaza.

−40−20

020

40

−40

−20

0

20

40−10000

−8000

−6000

−4000

−2000

0

2000

x1

A = [−3 , 1.41 ; 1.41 , −4]

x2

f = x

T A

x −

bT x

Functia patratica asociata unei matrice negativ

definite. Maximul functiei coincide cu solutia

sistemului. Algoritmul GC poate fi modificat cu

usurinta pentru a putea functiona.


13/56




Matrice pozitiv semidefinita/indefinita - intuitiv

−10−5

05

10

−20

−10

0

10

20−500

0

500

1000

1500

x1

A = [1 , 2 ; 2 , 4]

x2

f = x

T A

x −

bT x

Functia patratica asociata unei matrice singulare,

pozitiv semidefinite. Minimul este atins într-o

infinitate de valori. Sistemul are o infinitate de solutii

(problema prost formulata matematic).

−20−10

010

20

−20

−10

0

10

20−1000

−500

0

500

1000

x1

A = [−1 , 1.73 ; 1.73 , 1]

x2

f = x

T A

x −

bT x

Functia patratica asociata unei matrice indefinite.

Solutia sistemului este punct sa pentru f . GC nu

functioneaza.


14/56



Metoda gradientuluiMetoda directiilor conjugateMetoda gradientilor conjugati

Metoda celei mai rapide coborâri (a gradientului)

Ax = b, (15)

f (x) =12

xT Ax − bT x + c (16)

∇f (x) =12

AT x +12

Ax − b = Ax − b. (17)

Ideea: cautarea pe directii care corespund ratei celei mai maride schimbare a functiei.Pentru aproximatia x(k), directia celei mai rapide coborâri:

−∇f (x(k)) = b − Ax (k). (18)

Se definesc:

e(k) = x(k) − x, (19)

r(k) = b − Ax (k). (20)

e(k) - eroarea la iteratia kGabriela Ciuprina Sisteme de ecuatii algebrice liniare - metode semiiterative

15/56





e(k) = x(k) − x, (21)

r(k) = b − Ax (k). (22)

r(k) = b − A(e(k) + x) = b − Ae(k) − Ax .Legatura între eroare si reziduu:

r(k) = −Ae(k). (23)

∇f (x) = Ax − b.

−∇f (x(k)) = b − Ax (k). (24)

Reziduul este directia celei mai rapide coborâri:

r(k) = −∇f (x(k)). (25)


16/56




Metoda celei mai rapide coborâri (a gradientului)Corectia primei iteratii: dupa directia reziduului initializarii:

x(1) = x(0) + αr(0). (26)

α se va alege a.î. pe directia respectiva functia sa fie minima.g(α) = f (x(1)) minima, ⇒

dg

dα(x(1)) = 0 ⇒ (∇f (x(1)))T ·

dx(1)

dα= 0. (27)

Din (25) ⇒ ∇f (x(1)) = −r(1) ;Din (26) ⇒ dx(1)/dα = r(0) .(27) ⇒

(r(1))T · r(0) = 0,

(b − Ax (1))T· r(0) = 0,

[b − A(x(0) + αr(0))]T

r(0) = 0,

(b − Ax (0)− αAr (0)))T · r(0) = 0,

(b − Ax (0))T· r(0) − α(Ar (0))T r(0) = 0,

(r(0))T r(0) = α(r(0))T AT r(0).

A simetrica ⇒

α =(r(0))T r(0)

(r(0))T Ar (0). (28)


17/56




Metoda celei mai rapide coborâri (a gradientului)Corectia iteratiei k + 1:

x(k+1)= x(k) + αk r(k). (29)

αk se va alege a.î.:

g(αk ) = f (x(k+1)) minima, ⇒

dg

dα(x(k+1)

) = 0 ⇒ (∇f (x(k+1)))

T·

dx(k+1)

dαk= 0. (30)

Din (25) ⇒ ∇f (x(k+1)) = −r(k+1) ;

Din (29) ⇒ dx(k+1)/dαk = r(k) .(30) ⇒ ortogonalitatea reziduurilor:

(r(k+1))T· r(k) = 0,

(b − Ax (k+1))T· r(k) = 0,

[b − A(x(k) + αr(k))]T

r(k) = 0,

(b − Ax (k)− αAr (k)))T · r(k) = 0,

(b − Ax (k))T· r(k) − α(Ar (k))T r(k) = 0,

(r(k))T r(k) = α(r(k))T AT r(k).

A simetrica ⇒

α =(r(k))T r(k)

(r(k))T Ar (k). (31)


18/56





Algoritm - varianta 0

procedur a metoda_gradientului_v0(n,A,b, x0,er ,maxit , x)· · ·xv = x0 ; initializeaza sirul iteratiilork = 0 ; initializare contor iteratiir = b − A · xv ; calculeaza reziduucât timp ‖r‖ > er si k ≤ maxit

α = rT r/(rT Ar)x = xv + αrr = b − A · xvxv = x ; actualizeaza solutia vechek = k + 1

•retur

Efortul cel mai mare: produsului matrice - vector. (2/iter.).Gabriela Ciuprina Sisteme de ecuatii algebrice liniare - metode semiiterative

19/56





x(k+1) = x(k) + αk r(k), (32)

Înmultim la stânga cu −A si adunam b ⇒

r(k+1) = r(k) − αkAr (k), (33)


20/56





procedur a metoda_gradientului(n,A,b, x0,er ,maxit , x)· · ·xv = x0 ; initializeaza sirul iteratiilork = 0 ; initializare contor iteratiir = b − A · xv ; calculeaza reziduue = ‖r‖cât timp e > er si k ≤ maxit

m = A · rα = rT r/(rT m)e = ‖r‖x = xv + αrxv = x ; actualizeaza solutia vechek = k + 1r = r − αm

•retur


21/56





Observatii:

1 singur produs matrice vector pe iteratie;

Reziduul se calculeaza recursiv. Se pot acumula erori derotunjire. Este bine ca periodic r(k) = b − Ax (k).


22/56





Analiza convergentei acestei metode se face pe bazanumarului de conditionare spectrala

κ =maxλi

minλi≥ 1. (34)

Metoda poate converge rapid, într-un singur pas, dacapunctul de start este ales pe axele elipsoidului sau dacaforma patratica este sferica (ceea ce corespunde cazului încare toate valorile proprii sunt egale).


23/56





În rest, convergenta depinde de numarul de conditionare κsi de initializare.

Se poate demonstra ca eroarea la fiecare iteratie i estemarginita de

‖e(i)‖ ≤

(

κ− 1κ+ 1

)i

‖e(0)‖ (35)


24/56





−100 −50 0 50 100−100

−80

−60

−40

−20

0

20

40

60

80

100

−100 −50 0 50 100−100

−80

−60

−40

−20

0

20

40

60

80

100

−100 −50 0 50 100−100

−80

−60

−40

−20

0

20

40

60

80

100

κ = 10 κ = 10 κ = 1Convergenta metodei gradientului depinde de initializare si de numarul de conditionare spectrala. O problema care

are numarul de conditionare spectrala κ = 1 (toate valorile proprii sunt egale, iar forma patratica este sferica)

converge într-un singur pas.


25/56




Metoda directiilor conjugate

Metoda gradientului converge atât de încet deoarece directiilede cautare sunt ortogonale si se întâmpla ca pe parcursuliteratiilor directiile de cautare sa se repete.Ar fi de dorit sa existe exact n directii de cautare,d(0), d(1), . . . , d(n−1) astfel încât solutia sa fie gasita dupa exactn pasi.


26/56





La fiecare pas nou

x(k+1) = x(k) + αkd(k), (36)

iar αk se va alege astfel încât eroarea e(k+1) sa fie ortogonalape d(k) si, în consecinta, nici o alta corectie sa nu se mai facaîn directia lui d(k):

(d(k))T e(k+1) = 0. (37)

OBS: În cazul particular în care directiile d(k) sunt reziduurile,se obtine exact metoda celei mai rapide coborâri.


27/56





x(k+1) = x(k) + αkd(k), (38)

Scadem solutia exacta din ambii termeni ⇒

e(k+1) = e(k) + αkd(k), (39)

Din(d(k))T e(k+1) = 0. (40)

(d(k))T (e(k) + αkd(k)) = 0. (41)

αk = −(d(k))T e(k)

(d(k))T d(k). (42)

Nu este utila deoarece eroarea nu este cunoscuta.


28/56





Solutia consta în a face directiile de cautare A-ortogonale si nuortogonale:

(d(k))T Ad (j) = 0. j < k . (43)

Noua cerinta: e(k+1) sa fie A-ortogonal pe d(k)

(echivalent cu gasirea unui punct de minim de-a lungul directiei d(k), ca la metoda gradientului).

ddα

f (x(k+1)) = 0,

(∇f (x(k+1)))T ddα

(x(k+1)) = 0,

−(r(k+1))T d(k) = 0,

(d(k))T Ae(k+1) = 0. (44)


29/56





Rezulta(d(k))T A(e(k) + αkd(k)) = 0

de unde

αk = −(d(k))T Ae(k)

(d(k))T Ad (k)=

(d(k))T r(k)

(d(k))T Ad (k), (45)

expresie ce se poate calcula.


30/56





Teorema

Metoda directiilor conjugate calculeaza solutia în exact n pasi.Pentru demonstratie consultati [Shewchuk94].

Gasirea unui set de directii A-ortogonale d(k) se realizeazausor cu ajutorul procedurii Gram-Schmidt conjugate.

Se porneste de la o multime de n vectori liniarindependenti u(0), u(1), . . . , u(n−1)

d(0) = u(0). (46)

A doua directie porneste de la al doilea vector la care seadauga un vector orientat pe directia anterioara, scalat a.î.rezultatul sa fie A-ortogonal pe directia anterioara.


31/56





d(1) = u(1) + β10d(0), (47)

unde β10 se alege astfel încât

(d(1))T Ad (0) = 0. (48)

Aceasta relatie este echivalenta cu

(u(1) + β10d(0))T Ad (0) = 0, (49)

de unde

β10 = −(u(1))T Ad (0)

(d(0))T Ad (0). (50)


32/56





Similar, urmatoarea directie este

d(2) = u(2) + β20d(0) + β21d(1), (51)

unde β20 si β21 se aleg astfel încât

(d(2))T Ad (0) = 0 si (d(2))T Ad (1) = 0, (52)

de unde rezulta

β20 = −(u(2))T Ad (0)

(d(0))T Ad (0), β21 = −

(u(2))T Ad (1)

(d(1))T Ad (1). (53)


33/56





În general

d(k) = u(k) +

k−1∑

j=0

βkjd(j), (54)

unde βkj , definiti pentru k > j , sunt dedusi din conditiile deA-ortogonalitate impuse directiilor, rezultând

βkj = −(u(k))T Ad (j)

(d(j))T Ad (j). (55)

Dificultate: toate directiile de cautare trebuie memorate pentrua construi o directie de cautare noua.


34/56




Metoda gradientilor conjugati

Metoda gradientilor conjugati este metoda directiilor conjugateîn care directiile de cautare sunt construite prin conjugareareziduurilor:

u(k) = r(k). (56)


35/56





Justificarea acestei alegeri:1 Intuitiv, inspirat de metoda celei mai rapide coborâri, în

care directiile de cautare erau directiile reziduurilor.2 Proprietatea reziduului de a fi ortogonal pe directiile de

cautare anterioare si pe reziduurile anterioare.

(dk )T r(i) = 0, k < i , (57)

(rk )T r(i) = 0, k < i . (58)


36/56





De asemenea, reziduul rk este o combinatie liniara dintrereziduul anterior si produsul Ad (k−1):

r(k) = −Ae(k) = −A(e(k)+αkd(k)) = r(k−1)−αk−1Ad (k−1). (59)


37/56





Coeficientii β

βkj = −(r(k))T Ad (j)

(d(j))T Ad (j). (60)

Pentru a explicita termenul de la numarator, vom înmulti relatia(59) la stânga cu (r(i))T :

(r(i))T r(k+1) = (r(i))T r(k) − αk (r(i))T Ad (k), (61)

de unde

αk (r(i))T Ad (k) = (r(i))T r(k) − (r(i))T r(k+1). (62)


38/56





Pentru i 6= k , membrul drept al acestei relatii este nenul doarpentru cazul i = k + 1, când valoarea lui este −(r(i))T r(i)/αi−1.Rezulta ca valorile β sunt nenule doar daca i = k + 1:

βkj =

{

(r(k))T r(k)

αk−1(d(k−1))T Ad (k−1) k = i − 1,

0 k < i − 1(63)


39/56





Nu mai este necesar ca valorile β sa fie notate cu doi indici.Vom renota

βk = βk ,k−1 =

=(r(k))T r(k)

αk−1(d(k−1))T Ad (k−1)=

=(r(k))T r(k)

(d(k−1))T r(k−1)=

=(r(k))T r(k)

(r(k−1))T r(k−1). (64)


40/56





În concluzie, metoda gradientilor conjugati se bazeaza peurmatoarele sase relatii:

d(0) = r(0) = b − Ax (0)

αk =(r(k))T r(k)

(d(k))T Ad (k)

x(k+1) = x(k) + αkd(k)

r(k+1) = r(k) − αkAd (k)

βk+1 =(r(k+1))T r(k+1)

(r(k))T r(k)

d(k+1) = r(k+1) + βk+1d(k)


41/56





Algoritmul este complet dupa n iteratii.

−100 −50 0 50 100−100

−80

−60

−40

−20

0

20

40

60

80

100

−100 −50 0 50 100−100

−80

−60

−40

−20

0

20

40

60

80

100

Convergenta metodei gradientului depinde de initializare si de numarul de conditionare spectrala (stânga). Metoda

gradientilor conjugati converge în exact n pasi, indiferent de initializare si de numarul de conditionare spectrala

(dreapta).


42/56





procedur a metoda_gradientilor_conjugati(n, A, b, x0, er, maxit, x)· · ·xv = x0 ; initializeaza sirul iteratiilork = 0 ; initializare contor iteratiir = b − A · xv ; calculeaza reziduucât timp ‖r‖ > er si k ≤ maxit

dac a k = 0d = r

altfel

β = rT r/(rvT · rv)d = r + βdv

•

α = rT r/(dT Ad)x = xv + αdrv = rr = rv − αAdxv = xdv = dk = k + 1

•retur

Algoritmul se poate îmbunatati, calculând la o iteratie o singura data produsul matrice - vector Ad si produsul scalar

rT r.


43/56





Algoritmul este complet dupa n iteratii. Din acest motiv, semai spune ca metoda este semi-iterativa, sirul iteratiilor nutinde catre solutia exacta atunci când numarul iteratiilortinde la infinit, ci, într-o aritmetica exacta, solutia exacta seobtine dupa exact n iteratii.

În practica însa metoda este folosita pentru probleme atâtde mari încât nu ar fi fezabil sa se execute toate cele niteratii. De aceea, iteratiile în algoritm sunt executateîntr-un ciclu cu test si nu într-un ciclu cu contor.


44/56



Preconditionare

Preconditionare

Preconditionare = transformarea problemei initiale într-unaechivalenta care are proprietati îmbunatatite considerabil.Preconditionare la stânga

Ax = b (65)

M−1Ax = M−1b, (66)M matrice nesingulara, numita matrice de preconditionare saupreconditionator.

Convergenta depinde de proprietatile matricei M−1A.

M−1A nu se calculeaza explicit, ci se rezolva My = A

Cazurile extreme: M = I si M = A - nu exista nici un câstig.

O conditie puternica pentru un bun preconditionator este cavalorile proprii ale matricei M−1A sa fie apropiate de 1 si canorma ‖M−1A − I‖2 sa fie mica [Trefethen97].


45/56



Preconditionare

Preconditionare

Preconditionare la dreapta

AM−1y = b, (67)

unde x = M−1y.Se pot folosi ambele tipuri de preconditionare simultan.Preconditionare matricelor simetrice si pozitiv definitePreconditionarea se face astfel încât sa se pastreze aceastaproprietate.Fie M = CCT - simetrica si pozitiv definita.

[

C−1AC−T]

CT x = C−1b, (68)

unde C−T = (C−1)T = (CT )−1, iar matricea din parantezadreapta este simetrica si pozitiv definita.


46/56



Preconditionare

Preconditionare

Metode de preconditionare celebre

1 Preconditionarea Jacobi (sau scalarea diagonala):M = diag(A), nesingulara. Generalizare: M = diag(c), undec ales convenabil.

2 Factorizarea incompleta Cholesky sau LU în care se aplicaprocedura de factorizare, dar factorii nu sunt calculaticomplet, valorile care ar umple matricea nu sunt luate înconsiderare. Matricea de preconditionare se obtine caprodusul acestor factori incompleti.


47/56



Preconditionare

Preconditionare

Aceste doua exemple de preconditionatori nu fac nicioreferire la problema initiala care a generat sistemul (65).

Cel mai bun sfat general: de a încerca sa se construiascapreconditionatorul pe baza unei versiuni mai simple aproblemei. Pe aceasta idee se bazeaza metodele multigridcare se bazeaza si pe preconditionatori obtinuti din Jacobisi SSOR.


48/56



Referinte

Minimal:[AN] Gabriela Ciuprina,Algoritmi numerici pentru calcule stiintifice în ingineria electricaEditura MatrixROM, 2013, pag. 106-120.Alte recomand ari:[Shewchuk94] J.R. Shewchuk, An Introduction to the ConjugateGradient Method Without the Agonizing Pain, Online[Saad03] Y. Saad, Iterative Methods for Sparse Linear Systems,SIAM, 2003.[Barrett94] R. Barrett, M. Berry, T.F. Chan, J. Demmel, J.M.Donato,J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. Van der Vorst,Templates for the Solution of Linear Systems: Building Blocks forIterative Methods, SIAM 1994.[Trefethen97] Lloyd N. Trefethen, David Bau III Numerical LinearAlgebra, SIAM 1997.


http://lmn.pub.ro/~gabriela/books/AlgNr_MatrixRom2013.pdf

http://www.cs.cmu.edu/~./quake-papers/painless-conjugate-gradient.pdf

49/56



Referinte

Biblioteci existente:[Dongarra2016] Freely Available Software for Linear Algebra(September 2016),http://www.netlib.org/utk/people/JackDongarra/la-sw.html[Eijkhout97] Overview of Iterative Linear System SolverPackages http://www.netlib.org/utk/papers/iterative-survey/BDDCML, BILUM, BlockSolve95, CERFACS, DUNE/ISTL, GMM++, HIPS, HYPRE, IML++, ITL, ITPACK, ITSOL,

Lis, PARALUTION, pARMS, PETSc, PIM, QMRPACK, SLAP, SOL, SPARSKIT, SPLIB, Templates, Trilinos


http://www.netlib.org/utk/people/JackDongarra/la-sw.html

http://www.netlib.org/utk/papers/iterative-survey/

50/56



Referinte


51/56



Pe scurt

Fiti atenti la astfel de informatii (capturi din LTSPICE).Consultati documentatia pentru detalii!


52/56



Pe scurt

Fiti atenti la astfel de informatii (capturi din LTSPICE).Consultati documentatia pentru detalii!


53/56



Pe scurt

Fiti atenti la astfel de informatii (capturi din COMSOL)


54/56



Pe scurt

Fiti atenti la astfel de informatii (capturi din COMSOL)


55/56



Pe scurt


56/56



Tema 4 (din categoria "examen")

1 Analizati functiile Matlab disponibile pentru rezolvarea sistemelor de ecuatii algebrice liniare: directe(mldivide , lu , chol , luinc , cholinc ), semiiterative (pcg , cgs , gmres , etc.).

2 Implementati algoritmul general al metodelor iterative. Procedura implementata va avea în plus unparametru care sa permita selectarea metodei (Jacobi, Gaiss-Seidel sau SOR, în acest din urma caz vaexista ca parametrul factorul de relaxare ω). Procedura va trebui sa foloseasca tehnici de matrice rare.

3 Experimentati metodele de rezolvare (cele din biblioteca Matlab si cea pe care ati implementat-o la punctul

anterior) pe o problema din urmatoarea lista:

gallery - din Matlab;http://math.nist.gov/MatrixMarket/

http://www.cise.ufl.edu/∼davis/welcome.html - UF sparse matrix collection

4 Studiati comportarea metodelor pe sistemul de ecuatii generat pentru rezolvarea circuitului din capitolul 3 alcartii cu exercitii. Studiati prin experimente numerice complexitatea metodelor utilizate. Realizati graficeilustrative.

Scrieti un raport care sa rezolve punctele de mai sus. Este obligatoriu ca raportul sa aiba: o pagina de titlu, un

cuprins generat automat, o lista de referinte. Dati o structura coerenta raportului.


sisteme de ecuatii algebrice liniare - metode iterative...

Documents