C06_Sisteme_e

8/2/2019 C06_Sisteme_e

1/38

1

METODENUM

ERICENINGINER

IE

TUDOR PAUNESCU

MN4

6.REZOLVAREAN

UMERICASISTEM

ELOR

GENERALITI DESPRE SISTEME DE ECUAII

METODE DE REZOLVARE NUMERIC A SISTEMELOR

BIBLIOGRAFIE

REZOLVAREA NUMERIC A SISTEMELOR N MATCAD


2/38

2

[MOR04] C. Morariu, T.Punescu. Informatic aplicat n inginerie. Mathcad 2001. Ed. Univ. Bv. 2004.

[SCH08] E. Scheiber. Analiz numeric. Brasov.

[POS94] M. Postolache. Metode Numerice. Ed. Sirius, Bucureti, 1994.

[BEU92] T.Beu. Analiz numeric n Pascal. Ed. Micro inf. Cluj-Napoca. 1992.

[SAL72] M.G.Salvadori, M.L.Baron. Metode numerice n tehnic. Edit. Tehnic, Bucureti, 1972.

[LAR89] D.Larionescu. Metode numerice.Ed. Tehnic, Bucureti, 1989.[MAR76] Gh. Marinescu. Probleme de analiz numeric rezolvarte cu calculatorul. Ed. Acad RSR, Bucureti, 1987.

[DOD76] Gh.Dodescu, M.Toma. Metode de calcul numeric. Ed. did. i pedag. Bucureti, 1976.

[LIX79] L.Gr. Lixaru. Metode numerice pentru ecuaii difereniale cu aplicaii. Ed. Acad RSR, Bucureti, 1979.

[MEM80 ] ***, Mic enciclopedie matematic, traducere din limba german. Edit. Tehnic,Bucureti, 1980.

[DOR76] W.S.Dorn, D.D.Mc.Cracken. Metode numerice cu programe in Fortran IV. Ed.Tehhnica. Buc. 76.

[HAU53] A.S.Hauseholder. Principles of Numerical Analysis. Mc Graw-Hill, New Zork, 1953.

[CON80] S.D.Conte- Elementary Numerical Analysis - An Algorithmic Approach, McGraw-Hill 3rd, 1980.

[PHI96] G. M. M. Phillips, P.J. Taylor. Theory and Applications of Numerical Analysis 2nd ed, Elsevier, 1996

[HOF01] J.F. Hoffman. Numerical Methods for Engineers and Scientists 2nd ed. Elsevier, 2001.

[NOC99] J.Nocedad. Numerical Optimization.Springer,1999.

BIBLIOGRAFIE


3/38

3

1. GENERALITI DESPRE SISTEME DE ECUAII

Funcie de natura ecuaiilorcomponente sistemele de ecuaii (SE) pot fi liniare (SEL) sau nu (SEN),

ultimele pot fi algebrice (SEAN) sau transcendente (SET).

SEAL

3x+5y=2

x-4y=8

SEAN

x2-x+y2=0

x2

-y2

-y=0

SET

ex+y=2

ey

-x=3

b

cFig. 1a.


4/38

4

Sisteme de ecuaii algebrice liniare

Un sistem de ecuaii liniare are forma:

coninndmecuaii cu n necunoscutexk

n formalism matriceal sistemul se mai poate scrie: A .X = B, unde A este matricea coeficienilor, X

iB sunt vectorii coloan ai necunoscutelor, respectiv ai termenilor liberi.

Dac sistemul admite cel puin o soluie este compatibil, n caz contrar incompatibil.

Dac admite o singursoluie se spune c este compatibil determinaticompatibil nedeterminatdac admite mai multe soluii.

n

k

hkhk bxa

1

n...1,km,...1h,

3x+2y -5z = 2

4x+y +7z = 0 2x+5y = -7


5/38

5

Regula lui CRAMER(PRE)

Dac m = ni D0 (determinant nenul) sistemul este compatibil determinat. Soluia sistemului este:

DDx kk / unde Dkeste determinantul obinut din D prin nlocuirea coloanei k cu B.

Sub form matriceal soluia se scrie: X = A-1 B.

Teorema KRONEKER-CAPELLI(PRE)

A1 este matricea obinut din A prin bordarea la dreapta cu coloana B.

a. Sistemul este compatibil daci numai dacAiA1 au acelai rangr.

Dr este determinantul principal, cel care d rangulr al sistemului.b. Dacn=r sistemul este compatibil determinat, se aplic regula Cramer.

c. Dac r < n sistemul se rezolv ca la b, n prealabil se trec n dreapta necunoscutele secundare.

Soluia depinde de valorile celor n-r necunoscute secundare, se spune c sistemul are n-rsoluii.

3x+2y -5z = 2

4x+y +7z = 0 2x+5y = -7


6/38

6

Fiind dat un sistem liniar de ecuaii,soluiile se pot ncadra n trei categorii: soluieunic (fig. 2a), sistemul

nu are soluie(fig. 2b), sistemul are o infinitate de soluii (fig. 2c).

bFig. 2a.

c


7/38

7

Sisteme de ecuaii algebrice liniare bine i ru condiionate

Deseori sistemele de ecuaii liniare

modeleaz fenomene a cror

caracteristici au fost msurate

experimental. n aceste situaii apar

inevitabil erori de msurare a

caracteristicilor care se reflect asupra

soluiilor. Dac mici variaii ale

coeficienilor sistemului au ca efect

variaii relativ mari ale valorilor

soluiilorspunem c sistemul este ru

condiionat.

Sistemul 2 este ru condiionat

deoarece la o mic variaie acoeficientului 6.917 la 6.912 variaiile

valorilor soluiilor sunt mult mai mari.

Se observ ca acest fapt se datoreaz

ecuaiilor foarte apropiate. Pt. astfel

de ecuaii metodele numerice pot da

erori relativ mari.

Exemplul 1 Salt la slide 13


8/38

8

Exemple de sisteme liniare perturbate la nivelul vectorului termenilor liberi i la nivelul coeficienilor variabilelor

Ex.2

Ex.3


9/38

9

Ex.4

Fie o matrice nesingulari II II o norm a matricei A.Numrul real

cond(A) = II A II . II A -1II (0)

Se numete numr de condiionare (NC) a maricei A. NC este prin definiie maximum posibil al

mrimii raportului dintre eroarea relativ a soluieii eroarea relativ a termenului liber.

Daccond(A) este mare atunci sistemul este rucondiionat (este sensibil la mici perturbaii), n caz

contrar este bine condiionat (este relativ insensibil la mici perturbaii).

Valori mari ale numrului de condiionareindic faptul c matricea este aproape singular, deci

precizia de calcul, a soluiilorsistemului de ecuaii algebrice liniare, este slab. Inversa unei matrice

ptrate care are un numrde condiionare mare este dificil de calculat, este afectat de erori.


10/38

10

(S)

(S)

(S)

(1)

(1)


11/38

11

Calculul normelor vectorilor i matricelor (S)

Normele sunt scalari care dau o msur a mrimii elementelor unei matrice sau vector. n biblioteca Mathcad exist patrutipuri de norme care se aplic unor matrice ptrate:- Funcia norm1(A) returneaz norma L1 a matricei A, calculnd cea mai mare sum a modulelor elementelor de pecoloan.

- Funcianorm2(A)returneaz norma L2 a matricei A, calculeaz cea mai mare valoaresingular a matricei A.- Funcianorme(A)returneaz normaeuclidian a matricei A.- Funcia normi(A) returneaz norma infinit a matricei A, calculnd cea mai mare sum a modulelor elementelor de pelinie.


12/38

12

Exemplul 5(S)


13/38

13

Se observc numerele de condiionare ale matricelor coeficienilorecuaiilor rucondiionate au valori

mari comparativ cu valorile asociate ecuaiilorbine condiionate.

Exemplul 6 de calcul a numerelor de condiionare disponibilen biblioteca de funcii Mathcad 14 pentru ex. 1.

Saltex.1


14/38

14

2. METODE DE REZOLVARE NUMERIC A SISTEMELOR DE ECUAII

Dup cum s-a amintit n cap.1 metodele de rezolvare a sistemelor de ecuaii liniare sunt directe sau iterative.

Pe de alt parte sistemele de ecuaii pot fi liniare (SEAL) sau neliniare (SEAN), n particular pentru ultimele

transcendente (SET).

Metodele directe permit rezolvarea SE, obinndu-se teoretic o soluie exact, practic una afectat de erorile

trunchiere, rotunjire ale sistemului de calcul utilizat. n general, metodele directe sunt ineficente pentru

rezolvarea SE mari, de unde a apruti necesitatea metodelor iterative, care dei n general nu ating soluia

exact, sunt mult mai eficiente dpdv a efortului de calcul, implementarea lor ntr-un limbaj de programare

este mult mai simpl.

Metodele directe urmresc transformarea sistemului ntr-unul echivalent a crui matrice a coeficienilor

variabilelor este o inferior sau superior triunghiular, uneori unitate, pentru care rezolvarea este banal.

Exemplu de rezolvare a unui SEAL 3x3 prin metoda eliminrii a lui Gauss

(4)


15/38

15

n continuare vor fi analizate metodele iterative de rezolvare a SEAL, SEAN i SET.

2.1. Metode de rezolvare iterativ a sistemelor de ecuaii algebrice liniare

2.1.1. Metoda iterativ Jacobi (S)[BEU92]

Fie SEAL la care se presupune c elementele diagonalei

matricei A sunt nenule.

Rezolvm prima ecuaie n raport cu x1, pe cea de a doua n

raport cu x2amd.

Dac se noteaz cu S=[sij]nn i cu T=[ti]n sistemul 6 poate fiscris sub forma:

X= T+S.X (7)

care este structura de baz a procesului iterativ de rezolvarea

SEAL.

(5)

(6)


16/38

16

Etape

Aproximaia de ordin zero este coloana termenilor liberi X(0) = T.

Aproximaia de ordin k este construit pe baza relaiei de recuren 7:

X(k)= T+S.X(k-1) (8)Dac irul X (0), X (1), ... , X (k), ... are o limit care este soluia sistemului 5.

Relaiile procesului iterativ sunt:

(9)

Se noteaz cu diferenele dintre soluii:

(10)

Considernd cmatricea diagonal S are elemente -1 relaiile 9 se scriu:

(11)


17/38

17

Procesul iterativnceteaz cnd eroarea absolutmaxim devine mai mic dect o eroare admisibil,

sau se poate folosi criteriul erorii relative:(12)

(13)

Convergenaiteraiilor

TeoremDac pentru sistemul redus 9 este satisfcut cel puin una din condiiile:

(14)

Atunci procesut iterativ converge ctre o soluieunic, indiferent de alegerea primei aproximaii.

n practic se utilizeaz metoda Gauss Seidel care are vitez de convergen superiar metodei

Gauss i n plus necesiti mai puin memorie.


18/38

18

2.1.2. Metoda iterativ Gauss - Seidel (S)[BEU92]

Metoda GS utilizeaz pentru calculul xi(k)

aproximaiei de ordin k asoluiei sistemului componentele x1 (k) ... xi-1 (k) spre deosebire de

metoda Jacobi care utiliza valorile din iteraia anterioar.

Se folosesc aceleainotaii ca la metoda Jacobi:

(15)Relaiile cu care se efectueaziteraiile sunt:

(16)

Procesul iterativ se poate opri dac se utilizeaz criteriul erorii

absolute sau relative (12, 13).

Teorema de convergen (14) i pstraz valabilitatea i pentru

metoda G-S.


19/38

19

2.2. Metode de rezolvare iterativ a sistemelor de ecuaii neliniare

Nu exist procedee generale directe de rezolvare a sistemelor de ecuaii neliniare, de aceea se

utilizeaz aproape exclusiv metodele iterative: Jacobi, Newton, Newton-Kantorovici, gradientului,

gadientului conjugat, Lovenberg-Marquardt, Gauss-Seidel neliniar.

(17)


20/38

20

(18)

(19)

(20)

Metoda Newton/tangentelor pentru rezolvarea iterativ a sistemelor de ecuaii neliniare este o generalizare

a metodei aplicate la rezolvarea ecuaiilorneliniare monovariabile (metoda Newton unidimensional vezi

C05 Ecuatii).Pentru nceput sconsiderm un sistem de douecuaii cu dou necunoscute (ecuaiile a dousuprafee

implicite) [LAR89]:

f(x,y)=0, g(x,y)=0

derivabile ntr-o anumitvecintate a punctului (x0, y0). Valorile de start ale algoritmului sunt determinate cel

mai uor n Mathcad prin reprezentarea grafic a celor doufuncii.n primul pas se nlocuiesc cele doufuncii neliniare cu planele tangente n vecintatea punctului iniiali se

ia ca aproximare urmtoare punctul n care drepta de intersecie a planelor taie planul z=0.

Ecuaiile planelor tangente n punctul (xk, yk) la suprafeelez=f(x,y), z=g(x,y) (dezvoltri n serie Taylor cu

reinerea doar a termenilor liniari)sunt:

S facem z=0 (intersecia planelor tangente cu planul XY) isnotmx-xk=hk, y-yk=rk.

Se obin astfel relaiile de recuren:

),()(),()(),(

),()(),()(),(

''

''

kkykkkxkkk

kkykkkxkkk

yxgyyyxgxxyxgzyxfyyyxfxxyxfz

kkk

kkk

ryy

hxx

1

1

2.2.1. Metoda Newton de rezolvare iterativ a sistemelor de ecuaii neliniare


21/38

21

Unde xki rksatisfac relaiile (obinute din relaiile 19 pentru z=0 ):

Sau scrise sub form matriceal:

Matricea 4x4 este matricea Jacobi a sistemului neliniar:

Dac nmulim la stnga cu J-1 ecuaia 23, cum J-1J=1 rezult:

Generaliznd rezult funcia de de iterare sub form vectorial:

Unde x este vectorul variabilelor, F(x) este matricea Jacobi, f(x) este vectorul funciilor sistemului.

),(,,

),(,,

''

''

kkkkykkkxk

kkkkykkkxk

yxgyxgryxgh

yxfyxfryxfh

(21)

(22)

),(

),(

,,

,,''

''

kk

kk

k

k

kkykkx

kkykkx

yxg

yxf

r

h

yxgyxg

yxfyxf

kkykkx

kkykkx

kk

kk

k

k

yxgyxg

yxfyxf

yxg

yxf

r

hJ

,,

,,J,

),(

),(''

''

(23)

),(

),(1

kk

kk

k

k

yxg

yxfJ

r

h(24)

xfxFxx 1)()( (25)


22/38

22

n consecin irul de iterare are forma:

Exemplul 7

Sistemul neliniar este: x=x2+y2, y=x2-y2. Pe lng soluia banal x=y=0 mai exist o soluie real n

vecintatea punctului P0(0.8, 0.4).

kkkk xfxFxx

1

1 )( (26)

S-au definit cele dou funcii implicite, a fost introdus ofuncie care calculeaz matricea Jacobi, s-au calculatnumerele de condiionare ale funciiilor liniarizate n

vecintateasoluiei nebanale, determinate grafic.

Exemplul 7.1


23/38

23

Exemplul 7.2Exemplul 7.1 continuare

Exemplul 7.2 are o generalitate mai mare decit cel din 7.1 in program a fostinclusa definirea matricei Jacobi si numele a doua functii oarecare f1, f2 caparametri formali.


24/38

24

(P) Scriei un program care s rezolve prin

metoda Newton sisteme cu oricte ecuaii

neliniare

Exemplul 7.3


25/38

25

(PRE)


26/38

26


27/38

27

2.2.2. Metoda de rezolvare iterativ a sistemelor de ecuaii neliniare (S)

Se consider sisteme de douecuaii cu dou necunoscute.

Teoria este identic cu cea a ecuaiilordac se nlocuieste R cu R2i valoarea absolut n R cu norma n R2.

0),(

0),(

2

1

yxf

yxf

).,(

),(

2

1

yxfyy

yxfxx

(27)

(28)

Lund Dyx ),(00

:

).,(

),(

00201

00101

yxfyy

yxfxx

iternd(29)

).,(),(

),(),(

221

111

nnnnnn

nnnnnn

yxgyxfyy

yxgyxfxx

Sub form matriceal ),( yxX ))(),(()( 21 XfXfXF ))(),(()( 21 XgXgXG )()(1 nnnn XGXFXX (30)

22 yxX cu norma


28/38

28

3. REZOLVAREA NUMERIC A SISTEMELOR N MATCAD

3.1. REZOLVAREA SISTEMELOR ALGEBRICE LINIARE N MATCAD

REZOLVAREA SISTEMELOR

ALGEBRICE LINIARE N

MATCAD

Rezolvare prin

metode directe

Rezolvare prin

metode iterative

Matricea invers

Funcia lsolve

Solve block

funciile findi minner


29/38

29

Funcia lsolve

Exemplul 8

Observaii

1. Coeficienii matricei A pot fi reali sau imginari

2. Verificai nainte de rezolvarea sistemului dac

acesta este bine sau ru condiionat prin calculul

numrului de condiionare(funciile cond1, cond2

etc)

Exemplul 9

Sistemul din exemplul 8 poate fi rezolvat i direct

prin introducerea n placeholder-ele funciei lsolve

a matricelor A i b.

Funcia Mathcad lsolve folosete o decompoziie LU i algoritmul Crout.


30/38

30

Exemplul 10

Sistemele liniare algebrice pot fi rezolvate i prin metodele iterative

permise de solve block

3.2. REZOLVAREA SISTEMELOR NELINIARE N MATCAD

Se utilizeaz notaiile folosite n relaia 17.

(31)I xixi-1I < TOL


31/38

31

(32)

Aceast eroare poate fi afiat utilizndu-se variabila predefinit ERR

DAC FUNCIA Find NU CONVERGE SPRE O SOLUIE SE POATE NCERCA CU FUNCIA minner CARE

ESTE POSIBIL S GSEASC UN REZULTAT APROXIMATIV


32/38

32

La clic dreapta pe numele funciei Find apare meniul din figura 3. Dac este bifat

opiuneaAutoSelect (implicit bifat) sistemul identific natura sistemului de ecuaii (liniar,

neliniar) i aplic mai muli algoritmi pn gsete unul s converg (succesiunea este

Levenberg-Marquardt Conjugate Gradient Quasi-Newton). Este posibil ca nici un

algoritm sreueascsgsesc o soluieaproximativ a sistemului de ecuaii.

Productorul indic faptul c uzual se lucreaz cu opiunea de autoselectare, dar esteposibili selectarea direct a unuia din cei trei algoritmi amintii (fig. 4). n acestvariant

pentru algoritmii Conjugate Gradient i Quasi-Newton este posibil s fie setai i ali

parametri (fig. 5), pentru amnunte vezi [MOR04] pg. 209.

Blocul solve poate rezolva sisteme cu 400 de variabile reale dac se utilizeaz metodele

Quasi-Newton sau Conjugate-Gradient. Dac se lucreaz n complex Mathcad consider

partea imaginari cea real ca variabile separate deci limita se njumtete. n cazul

algoritmului Levenberg-Marquardt numrul de variabile este limitat doar de memoria

disponibil a calculatorului. Sistemele liniare pot avea maximum 8192 de restricii, cele

neliniare 200.

Dup cum s-a mai amintit algoritmul curent se opretedac dousoluii succesive difer

cu mai puin de valoarea constantei predefinite TOL sau dac se atinge numrul maxim de

iteraii. Nu se recomant setarea TOL cu valori prea mici 10 -10 ... 10 -15 din cauza erorilor

de rotunjire.

Fig.3

Fig.4

Fig.5


33/38

33

n cazul sistemelor de ecuaii, spre deosebire de TOL care controleaz procesul iterativ prin diferenele a dou soluii

succesive, prin CTOL Constraint - TOLerance), n general, sunt controlate restriciile asociate Given, n particular pentru

sisteme liniare, restriciile egalitate AX=b.

Dacinegalitile dintr-un bloc solve au forma:

h(t) < ct

Mathcad evalueazdiferena dintre membrul stng i membrul drept al inegalitii, iar precizia de rezolvare este considerat

corespunztoaredac:

h(sol) ct < CTOL (33)

unde cu sol a fost notatsoluia.

Mesaje de eroare asociate funciilorfiindiminner


34/38

34

Valoarea variabilelor globale predefinite TOL iCTOL poate fi modificat n dou moduri:

- direct n foia de lucru: de exemplu TOL:=10 -6;

-prin meniul Tools WorksheetOptions tab-ul Built-in Variables.

Exemplul 11 [MOR04]

Etapa 1

Etapa 2

Dac sistemul de ecuaii neliniareare mai multe soluii, blocul solve

trebuie utilizat de mai multe ori


35/38

35

Exemplul 12 Exemplul 13

Sistemul de la exemplul 11 rezolvat simbolic Sistem cu soluii complexe


36/38

36

Exemplul 14

Sistem parametrizat, parametru a

Exemplul 15

O alternativ la rezolvarea ecuaiilor prin funciarooteste utilizarea funciilorFindsau minner

Exemplul 16

Rezolvarea simbolic a ecuaieipropuse la exemplul 15

VECTORIZARE

continuare


37/38

37

continuare

Solutii obtinute din rulari succesive

Exemplul 17


38/38

38

Exemplul 18

Rezolvarea ecuaiilor matriceale [MOR04]

C06_Sisteme_e

Documents

Transcript of C06_Sisteme_e