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