Laborator2 Ec. neliniare + sist. ec. nelin.

20
Lucrarea de laborator nr.2 Tema lucrării: Rezolvarea numerică a ecuaţiilor neliniare şi a sistemelor de ecuaţii neliniare II.1. ENUNŢUL LUCRĂRII Se consideră o ecuaţie neliniară(respectiv un sistem de ecuaţii neliniare) (1) , pentru care s-a separat o soluţie x*. Se cere să se determine această soluţie ca o eroare á priori impusă. Rezolvarea numerică se va face atât manual cât şi cu ajutorul calculatorului(utilizând programe de calcul realizate în Matlab). Se vor formula aprecieri comparative asupra metodelor utilizate prin prisma rezultatelor concrete obţinute. II.2. MODELUL MATEMATIC. METODE DE SOLUŢIONARE. II.2.1.CARACTERIZAREA METODELOR Pentru localizarea soluţiei x* Є [a,b](dacă ), (respective x*Є ) se vor utiliza următoarele categorii de metode: a) metode bazate pe secţionarea intervalului [a,b](metoda bisecţiei; regula „falsi”; metoda coardei; metoda secantei). b) metode ce folosesc derivatele funcţiei f(metoda Newton; metoda Newton simplificată). c) Metode ce se bazează pe exprimări explicite echivalente ale funcţiei f(metoda aproximaţiilor succesive şi variante ale acesteia). Rezolvarea numerică a ecuaţiei (1) (respectiv al sistemului de ecuaţii) constă în construirea unui şir(x (k) ) k [a,b], şir de aproximaţii ale soluţiei x*(i.e. (2)). Maniera în care este generat acest şir, printr-un proces recursiv, determină „calităţile” metodei de localizare(i.e. viteză de ; eroare numerică; efort de calcul; etc.)

Transcript of Laborator2 Ec. neliniare + sist. ec. nelin.

Lucrarea de laborator nr.2Tema lucrrii: Rezolvarea numeric a

ecuaiilor neliniare i a sistemelor de ecuaii neliniare

II.1. ENUNUL LUCRRII

Se consider o ecuaie neliniar(respectiv un sistem de ecuaii neliniare) (1) , pentru care s-a separat o soluie x*.

Se cere s se determine aceast soluie ca o eroare priori impus.

Rezolvarea numeric se va face att manual ct i cu ajutorul calculatorului(utiliznd programe de calcul realizate n Matlab).

Se vor formula aprecieri comparative asupra metodelor utilizate prin prisma rezultatelor concrete obinute.

II.2. MODELUL MATEMATIC. METODE DE SOLUIONARE.

II.2.1.CARACTERIZAREA METODELOR

Pentru localizarea soluiei x* [a,b](dac), (respective x*) se vor utiliza urmtoarele categorii de metode:a) metode bazate pe secionarea intervalului [a,b](metoda biseciei; regula falsi; metoda coardei; metoda secantei).b) metode ce folosesc derivatele funciei f(metoda Newton; metoda Newton simplificat).c) Metode ce se bazeaz pe exprimri explicite echivalente ale funciei f(metoda aproximaiilor succesive i variante ale acesteia). Rezolvarea numeric a ecuaiei (1) (respectiv al sistemului de ecuaii) const n construirea unui ir(x(k))k [a,b], ir de aproximaii ale soluiei x*(i.e. (2)).Maniera n care este generat acest ir, printr-un proces recursiv, determin calitile metodei de localizare(i.e. vitez de ; eroare numeric; efort de calcul; etc.) Procesul iterative se consider a fi ncheiat de ndat ce este obinut un termen al irului (x(k))k, astfel nct s fie satisfcute criteriile de aproximare.II.2.2.PRINCIPIUL METODELOR

II.2.2.1.METODA BISECIEI

Fie ecuaia f(x) = 0, unde f este o funcie continu pe .Presupunem c pe intervalul [a,b] s-a separat o unic rdcin real x* a ecuaiei(i.e. f(a) f(b) < 0 ).

irul aproximaiei (x(k))k se construiete astfel:

Pasul 0: a(0): = a, b(0): = b

Se testeaz:

Pasul k: Fie [a(k), b(k)], intervalul determinat la pasul anterior n care se afl x*.

Atunci

Se testeaz (3)

Criterii de evaluare a erorii de aproximare

1) pas cu pas (sau posteriori): (4)2) n funcie de datele iniiale(sau priori):

EMBED Equation.DSMT4 (5)Observaie: Dac evaluarea numeric se face manual, atunci este recomandat a se utiliza criteriul 2)(astfel : din < (6), eroarea impus, se determin k k (i.e. rangul ncepnd de la care termenii irului asigur aproximarea cu a lui x*).

n cazul n care se utilizeaz calculatorul, atunci evaluarea < , sau < 2 (7)

II.2.2.2.regula falsi ntruct viteza de convergen a metodei biseciei este destul de mic, a fost dezvoltat o metod de localizare mai rapid, ce acioneaz ntr-un contaxt similar anterior. Diferena ntre cele 2 metode const n valoarea raportului n care se mparte , la fiecare pas, intervalul n care se afl soluia x*: dac la metoda biseciei, raportul este egal , la regula falsi, este egal cu (8) Astfel , irul de aproximaii (x(k))k se obine:

Pasul 0: a(0): = a, b(0): = b

Se testeaz:

Pasul k:Se cunosc a(k), b(k)(de la pasul anterior), astfel nct x*[a(k), b(k)]. Se obine:

Se testeaz (9)

Criterii de evaluare a erorii de aproximare

Se pot utiliza criterii pas cu pas:

< (10), (eroarea impus) sau/i < ,(11)II.2.2.3.METODA COARDEI

Se consider ecuaia cu x* (1) soluie real n . Presupunem ca f satisface urmtoarele condiii:1.

2.

3. Condiia Fourier > 0, unde , aproximaie iniial,4. < 0, unde , aproximare iniial. n aceste ipoteze, se poate construi un ir (x(k))k, ce se dovedete a fi un ir de aproximaii pentru x*.Pasul 0: Conform condiiilor de convergen, alegerea aproximaiilor iniiale i se face astfel:

Se testeaz dac a sau b.

1. Dac satisfac condiia Fourier pentru unul din aceste capete, s zicem atunci va fi ales ca (sau invers).

2. Dac nu satisfac condiia Fourier pentru a nici b pentru unul din aceste capete,se continu testarea pentru punctele: , , , etc pn se depisteaz i .

Pasul 1: : se consider d1 , coarda ce unete i . Se intersecteaz d1 cu Ox i se noteaz abcisa punctului de intersecie cu . Astfel : ;

Pasul k: : se consider dk, coarda ce unete i . Se intersecteaz dk cu Ox se obine un punct a crui abcis se noteaz cu . Adic , (12)

Criterii de evaluare a erorii de aproximare

1. pas cu pas: (13),cu .Dac, dup ce l-am construit pe x(k), obinem c membrul drept al inegalitii anterioare este mai mic dect eroarea impus , atunci x(k) este aproximarea dorit; dac nu, procesul interativ continu, cu testri similare la fiecare pas.2. n funcie de datele iniiale:(14),unde

Se utilizeaz mai ales atunci cnd relaxarea numeric se face manual i cnd impunnd membrului drept al inegalitii s fie mai mic dect ,eroarea impus, se determin rangul k, ncepnd de la care termenii irului (x(k))k aproximeaz x* cu eroarea impus.

II.2.2.4. METODA SECANTEI

Aceast metod este asemntoare cu metoda coardei.

Presupunem c f satisface pe [a,b] intervalul n care a fost separat rdcina real x*, ipotezele de la metoda coardei i n plus :1.

2.

3. Condiia Fourier > 0, unde , aproximaie iniial,4. < 0, unde , aproximare iniial.5.

6. d < 1, d = max (L0 , L1( cu

atunci se va construi (x(k))k ,un ir de aproximaii pentru x* astfel:

Pasul 0: aproximaiile iniiale i se aleg conform aceleai proceduri ca la metoda coardei: conform condiiilor de convergen, alegerea aproximaiilor iniiale i se face astfel:

Se testeaz dac a sau b.

1. Dac satisfac condiia Fourier pentru unul din aceste capete, s zicem atunci va fi ales ca (sau invers).

2. Dac nu satisfac condiia Fourier pentru a nici b pentru unul din aceste capete,se continu testarea pentru punctele: , , , etc pn se depisteaz i .

Pasul 1: se obine la fel ca la metoda coardei: se consider d1 , coarda ce unete i . Se intersecteaz d1 cu Ox i se noteaz abcisa punctului de intersecie cu . Astfel : ; (15)

Pasul k: Pentru obinerea lui se intersecteaz dreapta d ce trece prin: se consider dk, coarda ce unete i cu Ox se obine un punct a crui abcis se noteaz cu . Deci: , (16)

Criterii de evaluare a erorii de aproximare

1. pas cu pas:

unde (17).

Se testeaz dac Lk-1,eroarea impus. Dac DA cu , dac NU se trece la pasul urmtor.2. n funcie de de datele iniiale cu p0 = p1 =1 i pk+1 = pk + pk-1 (irul Fibonacci)Dac, impunem ca < , atunci vom obine rangul k ncepnd de la care , x(k) aproximeaz cu eroarea impus , soluia x*. Viteza de convergen este . II.2.2.5. METODA TANGENTEI (SAU A LUI nEWTON)

Se consider , soluie real simpl separat a ecuaiei , unde f satisface pe [a,b] urmtoarele ipoteze:1.

2.

3. Condiia Fourier > 0, unde

Aceste condiii asigur convergena la soluia exact x* a irului (x(k))k, construit astfel:Pasul 0: Maniera de a alege pe este identic cu cea folosit la metoda coaredei: aproximaiile iniiale i se aleg conform aceleai proceduri ca la metoda coardei: conform condiiilor de convergen, alegerea aproximaiilor iniiale i se face astfel:

Se testeaz dac a sau b.

3. Dac satisfac condiia Fourier pentru unul din aceste capete, s zicem atunci va fi ales ca (sau invers).

4. Dac nu satisfac condiia Fourier pentru a nici b pentru unul din aceste capete,se continu testarea pentru punctele: , , , etc pn se depisteaz i .

Pasul 1: Fie , tangent la Gf n . Fie (20)

Pasul k: , unde

Atunci: , (21)

Obs.: Dac x* are ordinal m de multiciplitate,

atunci (22)

Criterii de evaluare a erorii de aproximare

1. pas cu pas: (23).2. n funcie de de datele iniiale Modul de utilizare este identic cu cel descrise anterior la celelalte metode de utilizare: n funcie de de datele iniiale cu p0 = p1 =1 i pk+1 = pk + pk-1 (irul Fibonacci)Dac, impunem ca < , atunci vom obine rangul k ncepnd de la care , x(k) aproximeaz cu eroarea impus , soluia x*. Viteza de convergen este .II.2.2.6. METODA aproximaei succesive

Se consider ecuaia cu , soluie separat. Se presupune c este derivabil pe [a,b] Construcia irului (x(k))k ale soluiei x* se bazeaz pe exprimarea echivalent a ecuaiei iniiale x = g(x), unde g satisface pe [a,b] urmtoarea ipotez:

n aceste condiii, alegnd o aproximaie iniial x(0) , n [a,b]( de regul:

sau o alt valoare (eventual indicat), construim irul conform formulei de recuren:

(25) Criteriii de evaluare a erorii de aproximare

Criterii de evaluare a erorii de aproximare

1. pas cu pas: (26).

2. n funcie de de datele iniiale

(27)Observaie: funcia g poate fi obinut n mai multe moduri:

Fie (28) unde este mrginit, atunci:

Pentru ca g s fie o contracie, alegerea lui h, respect condiia :

(29) .II.2.2.7. ACCELERAREA CONVERGENEI

Pentru a crete puterea de convergena unui ir de aproximaii (x(k))k ce converge liniar la soluia x*, se poate utiliza procedee de accelerare a convergenei.

Un astfel de procedeu este cel al lui Aitken ce conducela metoda lui Steffeensen..

n esen, procedeul de accelerare Aitken const n nlocuirea unui ir (x(k))k ce converge liniar la soluia x* (i cu ) i care satisface:

cu astfel nct (30), printr-un alt ir (y(k))k , ce converge la x* cu vitez superioar n sensul :

(31)

(y(k))k va fi definit astfel:

(32) unde

m este diferena finit progresivde ordinul m

(33)

Cnd procedeul de accelerare Aitken se aplic metodei aproximaiilor succesive i metodei secantei, se obine metoda Steffensen:

Fie , unde cu , o scriere echivalent pe a ecuaiei f(x) = 0, pentru care a fost separat soluia real n .

Fie , irul de aproximaii ale soluiei exacte , folosit n metoda aproximaiilor succesive(i.e. ,).Ideea metodei lui Steffensen: nlocuirea irului printr-un ir , ir de aproximaii ale lui , cu o vitez de convergen mai mare, combinnd metoda aproximaiilor succesive cu cea a secantei i anume: 2 itineraii cu metoda secantei aplicat funciei: .

Deci este definit astfel:

(34)

II.2.3. PSEUDOCODUL ALGORITMILOR

II.2.3.1.REZOLVAREA PRIN METODA BISECIEI

Metoda biseciei poate fi reprezent n pseudocod prin procedura biseciei (a, b, eps, nit)

real a,b ; domeniul de definiie al funciei f

real eps; eroare impus de soluie

ntreg nit; numr maxim de iteraii

ntreg k = 0; contor iteraii

repet

k = k + 1

xm = (a + b)/2

dac f(xm) f(a) > 0 atunci

a = xm

astfel

b = xm

pn cnd (b a) < eps sau k > nit

dac k nit

scrie xm ; soluie

retur

II.2.3.2.REZOLVAREA PRIN METODA TANGENTELOR

Metoda tangentelor poate fi reprezent n pseudocod prin procedura Newton (x0, eps, nit)

real x0 ; iniailizare soluie

real eps; eroare impus de soluie

ntreg nit; numr maxim de iteraii

ntreg k = 0; contor iteraii

real x vechi = x0; iniializerea soluiei

repet

k = k + 1

xnou = xvechi f(xvechi)/ f'(xvechi)

d = xnou - xvechi xvechi = xnou

pn cnd d < eps sau k > nit

dac k nit

scrie xnou

retur

II.2.3.3.REZOLVAREA PRIN METODA TANGENTELOR (MODIFICAT) SAU METODA TANGENTELOR PARALELE

Metoda tangentelor paralele este reprezentat n pseudocod astfel (x0, eps, nit)

real x0 ; iniailizare soluie

real eps; eroare impus de soluie

ntreg nit; numr maxim de iteraii

ntreg k = 0; contor iteraii

real x vechi = x0; iniializerea soluiei

real fd = f'(x0) ;valoarea derivatei lui f n x0

repet

k = k + 1

xnou = xvechi f(xvechi)/ fd

d = xnou - xvechi xvechi = xnou

pn cnd d < eps sau k > nit

dac k nit

scrie xnou

retur

II.2.3.4.REZOLVAREA PRIN METODA SECANTEI

Metoda secantei este reprezentat n pseudocod astfel (x0, eps, nit)

real a,b ; domeniul de definiie al funciei f

real eps; eroare impus de soluie

ntreg nit; numr maxim de iteraii

ntreg k = 0; contor iteraii

real xV = a ; iniializri ale soluiei

real xVV = b

repet

k = k + 1

xnou = xV (xV xVV) f(xV)/(f(xV) f(xVV)

d = xnou - xVxV = xVV

xV = xnou

pn cnd (b a) < eps sau k > nit

dac k nit

scrie xnou

retur

II.2.4. PROGRAM MATLAB

II.2.4.1. METODA BISECIEI

Pentru a aplica o rdcin real a ecuaiei f(x) = 0 n [a,b]

Se aplic metoda doar dac f C [a,b] i sgn[f(a)f(b)] = - 1

funcion [c,err, yc]= bisect ( f, a, b, delta )

%Input f este funcia definit ca un ir ' f '

% a este extremitatea stng i b este extremitatea dreapt

% delta este tolerana

%Output c este rdcina

% yc = f(c)

% err este eroarea estimat pentru c

ya = feval (f,a)

yb = feval (f,b)

if ya * yb > 0 ,break, end

maxi = 1 + round ((log(b a) log(delta))/log(2));

for k = 1 : maxi

c = (a + b)/2;

yc = feval (f,c);

if = = 0

a = c

b = c

elseif yb * yc > 0

b = c;

yb = yc;

else

a = c;

ya = yc;

end

if b a > delta ,break, end

end

c = (a + b)/2;

err = abs (b a);

yc = feval (f,c);

II.2.4.2. METODA TANGENTEI (NEWTON)

Pentru a aproxima o rdcin real a ecuaiei f(x) = 0, fiind dat o aproximaie iniial p0 i utiliznd iteraia:

function [p0, err, k, y]= newton (f, df, po, delta, epsilon, maxi)

%Input f este funcia obiect definit ca un ir 'f '

% df este derivata funciei f definit ca un ir 'df '

% po este aproximaia iniial a unei rdcini ale lui f

% delta este tolerana pentru po

% epsilon este tolerana pentru valorile funciei y

% maxi este numrul maxim de itineraii

%Output po este aproximarea Newton a rdcinii

% err este eroarea estimat pentru po

% k este numrul de itineraii

% y este valoarea funciei f(po)

for k = 1 : maxi

p1 = po feval(f,po)/feval(df,po);

err = abs(p1 po);

relerr = 2 * err/(abs(p1) + delta);

po = p1;

y = feval (f,po);

if (err < delta)/(reller < delta)/abs(y) < epsilon), break, end

II.2.4.3. METODA SECANTEI

Pentru a aproxima o rdcin real a ecuaiei f(x) = 0, fiind dat o aproximaie iniial p0 i p1, aproximaii iniiale i utiliznd iteraia:

function [p1, err, k, y]= secant (f, po, p1, delta, epsilon, maxi)

%Input f este funcia obiect definit ca un ir 'f '

% p0 i p1 sunt aproximaiile iniiale ale rdcinii

% delta este tolerana pentru p1

% epsilon este tolerana pentru valorile funciei y

% maxi este numrul maxim de itineraii

%Output p1 este aproximarea metodei secantei pentru rdcini

% err este eroarea estimat pentru p1

% k este numrul de itineraii

% y este valoarea funciei f(p1)

for k = 1 : maxi

p2 = p1 feval(f,p1)*(p1 po)/(feval(f,p1) feval(f,po));

err = abs(p2 p1);

relerr = 2 * err/(abs(p2) + delta);

po = p1;

p1 = p2;

y = feval (f,p1);

if (err < delta)/(reller < delta)/abs(y) < epsilon), break, end

II.2.4.4. METODA ACCELERAREA STEFFENSEN

Pentru a gsi mai repede o rdcin real a ecuaiei x = g(x), (g, contracie), dndu-se po, o aproximaie iniial, dac g, g sunt continue, g(x) < 1 i iteraia aproximaiilor succesive converge aproape liniar la p

function [p,Q]= steff (f, df, po, delta, epsilon, maxi)

%Input f este funcia obiect definit ca un ir 'f '

% df este derivata funciei f

% p0 este aproximaia iniial a unei rdcinii a lui f

% delta este tolerana pentru p0

% epsilon este tolerana pentru valorile funciei y

% maxi este numrul maxim de itineraii

%Output p este aproximaia Steffensen pentru rdcini

% Q este matricea coninnd irul lui Steffensen

%Iniializeaz matricea R

R = zeros (maxi, 3);

R (1,1) = po;

for k = 1: maxi

for j = 2:3

%Numitorul n metoda Newton este calculat

nrdenom = feval(df, R(k, j-1)

%Calculeaz aproximrile Newton

if nrdenom = = 0

mprirea prin 0 n metoda Newton

break

else

R(k, j) = R(k, j-1) feval(f,R(k, j-1))/nrdenum;

II.2.4.5. METODA MULLER

Pentru a gsi o rdcin a ecuiei f(x) = 0, tiind aproximrile iniiale p0, p1 i p2

funcion [p,y,err]= muler (f, p0, p1, p2, delta, epsilon, maxiX, Y )

%Input f este funcia obiect definit ca un ir 'f '

% p0, p1 i p2 sunt aproximaiile iniiale

% delta este tolerana pentru p0, p1 i p2

% epsilon este tolerana pentru valorile funciei y

% maxi este numrul maxim de itineraii

%Output p este aproximarea rdcinii lui f

% y este valoarea f(p)

% err este eroareaaproximrii prin p

%Iniializeaz matricile P i Y

P = [p0 p1 p2];

Y = feval(f,P);

%Calculez a i b n formul

for k = 1: maxi

h0 = p(1) - p(3) ;

h1 = p(2) - p(3);

e0 = Y(1) Y(3);

e1 = Y(1) Y(3);

C = Y(3);

denom = h1*h0^2-h0*h1^2;

a = (e0*h1-e1*h0)/denum;

b = (e1*h0^2-e0*h1^2)/denum;

%Suprim orice rdcin complex

if b^2-4*a*c>0

disc = sqrt(b^2-4*a*c);

else

disc = 0

end

%Numitorul n procesul de accelerare Aitken este calculat acdenom = R(k,3)-2*R(k,2)+R(k,1);

%Calculeaz aproximrile accelerrii Aitken

if acdenom = = 0

mprirea prin zero n accelerarea Aitken

break

else

R(k+1,1) = R(k,1)-(R(k,2)-R(k,1))^2/ ;

end

end

%Sfritul programului dac are loc mprirea cu zero

if (nrdenom = = 0) / (acdenom = = 0)

break

end

%Criteriile de oprire sunt evaluate

err = abs (R(k,1) R(k+1,1));

relerr = err/(abs(R(k+1,1));

if (err