Metoda coardei

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare
Etapele successive ale metodei falsi pe intervalul [a1;b1]. Rădăcina funcţiei este punctul marcat cu culoarea roşie

În analiză numerică, metoda coardei (sau metoda falsei poziții, metoda falsi) este o metodă de determinare a rădăcinii unei funcții pe un interval.

Descrierea metodei[modificare | modificare sursă]

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

 c_k = a_k - \frac{a_k-b_k}{f(a_k)-f(b_k)} f(a_k)

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.

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ă:

 y - f(b) = \frac{f(b)-f(a)}{b-a} (x-b).

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

 f(b) + \frac{f(b)-f(a)}{b-a} (c-b) = 0.

Rezolvarea ecuației de mai sus oferă ck.

Convergență[modificare | modificare sursă]

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ă (f' și f'' 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:

 f'(x1) = \frac{f(x)-f(a)}{x-a} și  f'(x2) = \frac{f(b)-f(x)}{b-x}

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

 \frac{f(b)-f(x)}{b-x} - \frac{f(x)-f(a)}{x-a} < 0

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

f'(x2) - f'(x1) =  \frac{x.(f(b)-f(a)) + f(x).(a-b) - a.f(b) + b.f(a)}{(b-x).(x-a)}

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

 x = \frac{a.f(b) - b.f(a)}{(f(b)-f(a))}

Rezultă că

f'(x2) - f'(x1) =  \frac{f(x).(a-b)}{(b-x).(x-a)}

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

 \frac{x_{n+2} - x_{n+1}}{x_{n+1} - x_n} = \frac{f(x_{n+1})}{f(x_n)} .  \frac{f(b) - f(x_{n+1})}{f(b) - f(x_n)} . \frac{b - x_n)}{b-x_{n+1}}

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  \frac{x_{n+2} - x_{n+1}}{x_{n+1} - x_n} este egală cu limita șirului \frac{f(x_{n+1})}{f(x_n)} .

\frac{f(x_{n+1})}{f(x_n)} = \frac{f(x_{n+1}) - f(x*)}{x_{n+1}-x*} . \frac{x_n - x*)}{f(x_{n+1}) - f(x*)} . \frac{x_{n+1} - x*}{x_n - x*}

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 \frac{f(x_{n+1})}{f(x_n)} are aceeași limită cu șirul \frac{x_{n+1} - x*}{x_n - x*} . Cum x_{n+1} - x* = x_n - x* - f(x_n) . \frac{b - x_n}{f(b) - f(x_n)} , rezultă că

\frac{x_{n+1} - x*}{x_n - x*} = 1 - \frac{f(x_n) - f(x*)}{x_n - x*} . \frac{b - x_n}{f(b) - f(x_n)} 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.

Istorie[modificare | modificare sursă]

Cele mai vechi documente care atestă cunoașterea și înțelegerea metodei falsei poziții datează cu aproximație din anul 200 î.Hr. și 200 î.Hr.. Metoda a fost găsită într-un text antic chinez numit „Nouă capitole despre arta matematicii”. În acest text, cu toate acestea, exemple de probleme care aplică metoda falsei poziții sunt doar la ecuații liniare și soluțiile sunt atinse într-o singură etapă.

În Occident, această metodă a fost utilizat pe scară largă de către matematicienii Fibonacci, Luca Pacioli și Robert Recorde.

Pseudocod[modificare | modificare sursă]

 ''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";
}

Bibliografie[modificare | modificare sursă]

  • Constantin Ilioi, Probleme de optimizare și algoritmi de aproximare a soluțiilor, Editura Academiei Republicii Socialiste România, București, 1980.

Legături externe[modificare | modificare sursă]