METODA COARDEI

Efectuat de către Botnarenco Veronica

DESCRIEREA METODEI La fel ca metoda înjumătățirii intervalului, metoda falsei poziții începe cu două

puncte a1 și b1 astfel încât f(a1) și f(b1) sunt de semne opuse, ceea ce înseamnă, conform teoremei valorilor intermediare că funcția continuă f are cel puțin un zero în intervalul [a1, b1].

Metoda constă în producerea unui șir descrescător de intervale [ak, bk] care conțin rădăcina funcției f. La pasul k, este calculat numărul

După cum se poate verifica, ck este abscisa intersecției dreptei care trece prin punctele al liniei prin (ak, f(ak)) și (bk, f(bk)) cu axa, absciselor. Dacă f(ak) și f(ck) au același semn, atunci punem ak+1 = ck și bk+1 = bk; altfel, punem ak+1 = ak și bk+1 = ck.

Dacă f(ak) și f(ck) au același semn, atunci punem ak+1 = ck și bk+1 = bk; altfel, punem ak+1 = ak și bk+1 = ck.

Acest proces se repetă până când se ajunge la o valoare a funcției suficient de aproape de zero.

Pentru a verifica corectitudinea algoritmului, considerăm numerele reale a și b. Construim dreapta care trece prin punctele (a, f(a)) și (b, f(b)), ca și în contra figura alăturată. Această dreaptă este o coardă a graficului funcției f. Ecuația acestei drepte se determină folosind formula ecuației dreptei care trece printr-un punct și are o pantă dată:

Se determină acum c, abscisa intersecției acestei drepte cu axa x

Rezolvarea ecuației de mai sus oferă ck.

Etapele successive ale

metodei falsi pe intervalul

[a1;b1]. Rădăcina funcţiei

este punctul marcat cu

culoarea roşie

CONVERGENȚĂ Dacă valorile inițiale a0 și b0 sunt luate încât f(a0) și f(b0) să fie de semne opuse,

sunt de semn opus, atunci metoda coardei converge la un zero al lui f. Într-adevăr, din modul de construcție al intervalelor an și bn, rezultă că an este un șir crescător, iar bn este un șir descrescător. Ambele șiruri sunt monotone și mărginite, deci convergente. Notând cu a* - limita șirului an, iar cu b* - limita șirului bn, rezultă că f(a*)<=0<=f(b*). Cel puțin unul din numerele f(a*) și f(b*) este egal cu 0, altfel pentru orice vecinătate a numărului c=(a*.f(b*)-b*.f(a*))/(f(b*)-f(a*)) ar exista un număr întreg N astfel încât pentru n>N, xn ar aparține acestei vecinătăți, iar f(a*)<=xn<=f(b*) pentru orice n>N, în contradicție cu convergența șirului de intervale.

Se demonstrează că dacă funcția f este strict monotonă și convexă sau concavă (  și   de semn constant), atunci viteza de convergență este superlineară, mai rapidă decât metoda îmjumătățirii.

Într-adevăr, presupunem fără a restrânge generalitatea că f(a)<0 și f(b)>0 (în caz contrar, înlocuim funcția f cu -f, iar ecuația f(x)=0 ar fi echivalentă cu -f(x)=0). Deci în acest caz, funcția f este strict crescătoare, iar f'>0.

Pentru a fixa ideile, mai presupunem că f>0 la fel ca în figura de mai sus (dacă f<0 ar urma un raționament asemănător).

Deci funcția f' este strict crescătoare. Conform formulei lui Taylor, există două numere x1 și x2, astfel încât a<x1<x<x2<b, iar:

si

Conform ipotezei inițiale, f'(x1)<f'(x2), de unde rezultă că

După calcule elementare, această diferență este egală cu

f'(x2) - f'(x1) = 

Conform relației de calcul a lui x, se poate verifica că acesta este egal cu

Rezultă că

 = 

Deoarece a<x<b, rezultă că f(x) este de semn opus cu f'(x2) - f'(x1). În ipoteza

suplimentară de convexitate, rezultă că f(x)<0.

Deci f(x) este de același semn cu f(a), iar algoritmul construiește șirul de

intervale închise [an,bn] astfel încât bn=b la fiecare pas.

Pentru superliniaritate, din modul de construcție al șirului xn, obținem

= . .

Notăm cu x* - soluția unică a ecuației. Cum xn tinde spre x* care este diferit de

b, rezultă că ultimele două fracții din membrul al doilea converg spre 1.

Deci limita șirului  este egală cu limita șirului 

= . .

Cum prima fracție din membrul al doilea converge spre f'(x*)>0, iar a doua fracție converge spre 1/f'(x*), rezultă că șirul   are aceeași limită

cu șirul  . Cum    =    - .  ,

rezultă că  = 1 -    .    a cărui limită este

1 - f'(x*).(b-x*)/(f(b)-f(x*)).

Se observă că acest număr este cuprins între 0 și 1.

PSEUDOCODʹ ʹ Nʹ ʹ ← 1 While ''N'' ≤ ''NMAX'‘ {ʹ ʹ c ʹ ʹ ← ʹ ʹ a ʹ ʹ - ʹ ʹ f(a) ʹ ʹ *( ʹ ʹ b ʹ ʹ - ʹ ʹ a ʹ ʹ)/(ʹ ʹ f(b) ʹ ʹ - ʹ ʹ f(a) ʹ ʹ) If (ʹ ʹ f ʹ ʹ(ʹ ʹ c ʹ ʹ) = 0 or (ʹ ʹ b ʹ ʹ –ʹ ʹa ʹ ʹ)/2 < ʹ ʹ TOL ʹ ʹ then { Output(ʹ ʹ c ʹ ʹ) Stop } ʹ ʹ N ʹ ʹ ← ʹ ʹ N ʹ ʹ + 1 If sign(ʹ ʹ f ʹ ʹ (ʹ ʹ c ʹ ʹ )) = sign(ʹ ʹ f ʹ ʹ(ʹ ʹ a ʹ ʹ)) then ʹ ʹ a ʹ ʹ ← ʹ ʹ c ʹ ʹ else ʹ

ʹ b ʹ ʹ ← ʹ ʹc ʹ ʹ } Output("Algoritmul nu determină soluția în numărul maxim de iterații.")

IN LIMBAJUL C#include<iostream.h>

#include<math.h>

#define eps 0.00000000001

#define iter 200 double f(double x)

{

return x*x*x-2*x*x*cos(x)+x-3;

}

void main()

{

unsigned char i;

double x,x0,x1,a,b,y;

cout<<"a=";cin>>a;cout<<"b=";cin>>b;

i=0;x0=a;x1=b;x=x0;y=f(x);

if (f(x0)*f(x1)<0)

{

while ( (i<=iter) && ((y<-eps) || (y>eps)) )

{

x=x0-f(x0)*(x1-x0)/(f(x1)-f(x0));

y=f(x);

if (f(x0)*y<0) x1=x;

else x0=x;

cout<<"\n\nf("<<x<<")="<<f(x)<<" la iteratia "<<(int)i;

i++;

}

if (i>iter) cout<<"problema nu se poate rezolva in nr.maxim de iteratii";

} else cout<<"interval invalid";

}