Metoda înjumătățirii intervalului

În analiză numerică, metoda înjumătățirii intervalului este un algoritm de determinare a rădăcinilor, care pornește de la un interval inițial de determinare a rădăcinii unei funcții și apoi selectează un subinterval în care se află rădăcina. Este o metodă foarte simplă și robustă, dar relativ lentă. Metoda se mai numește și metoda căutării binare sau metoda dihotomiei.^[1]

Descrierea metodei[modificare | modificare sursă]

Metoda este aplicabilă atunci când rezolvăm ecuația f(x) = 0 pentru variabila reală x, unde f este o funcție continuă definită pe intervalul [a, b], iar f(a) și f(b) au semne opuse. În acest caz, teorema valorii intermediare garantează că există o rădăcină a funcției f în intervalul (a, b).

La fiecare pas, metoda împarte intervalul în două, calculând jumătatea intervalului c = (a+b) / 2 și valoarea funcției f(c) în acest punct. În afară de cazul în care c este însăși rădăcina funcției, mai există două posibilități: ori f(c) este de semn opus cu f(a), ori este de semn opus cu f(b). Metoda selectează subintervalul (a,c) în primul caz sau (c,b) în al doilea caz, iar acest subinterval devine noul interval în care urmează să fie căutată rădăcina funcției. În acest fel, interval care conține o rădăcină a funcției f este redus în lățime cu 0.5, la fiecare pas.Procesul se continuă până când intervalul este suficient de mic.

Exemplu[modificare | modificare sursă]

Considerăm funcția polinomială

f(x)=x^{3}-x-2\,.

Pentru început, considerăm două numere $a$ și $b$ astfel încât $f(a)$ și $f(b)$ au semne opuse. De exemplu, $a=1$ și $b=2$ satisfac aceste criterii:

f(1)=(1)^{3}-(1)-2=-2

și

f(2)=(2)^{3}-(2)-2=+4\,.

Deoarece funcția este continuă, există o rădăcină în intervalul [1, 2].

În prima iterație, $a_{1}=1$ și $b_{1}=2$ , iar mijlocul intervalului este

c_{1}={\frac {2+1}{2}}=1.5

Valoarea funcției la mijlocul intervalului: $f(c_{1})=(1.5)^{3}-(1.5)-2=-0.125$ . Deoarece $f(c_{1})$ este negativ, $a=1$ este înlocuit cu $a=1.5$ pentru următoarea iterație, pentru a respecta condiția ca $f(a)$ și $f(b)$ să aibă semne opuse. După un număr finit de pași, intervalul $(a,b)$ va avea lățimea tinzând spre 0, iar valorile funcției în acest interval vor converge spre rădăcina funcției. În tabelul următor se poate observa evoluția funcției.

Iteration	$a_{n}$	$b_{n}$	$c_{n}$	$f(c_{n})$
1	1	2	1.5	−0.125
2	1.5	2	1.75	1.6093750
3	1.5	1.75	1.625	0.6660156
4	1.5	1.625	1.5625	0.2521973
5	1.5	1.5625	1.5312500	0.0591125
6	1.5	1.5312500	1.5156250	−0.0340538
7	1.5156250	1.5312500	1.5234375	0.0122504
8	1.5156250	1.5234375	1.5195313	−0.0109712
9	1.5195313	1.5234375	1.5214844	0.0006222
10	1.5195313	1.5214844	1.5205078	−0.0051789
11	1.5205078	1.5214844	1.5209961	−0.0022794
12	1.5209961	1.5214844	1.5212402	−0.0008289
13	1.5212402	1.5214844	1.5213623	−0.0001034
14	1.5213623	1.5214844	1.5214233	0.0002594
15	1.5213623	1.5214233	1.5213928	0.0000780

După 15 iterații, se determină rădăcina funcției, care ia valoarea 1.521.

Analiza metodei[modificare | modificare sursă]

Metoda are convergența garantată dacă f este o funcție continuă pe intervalul [a, b] iar f (a) și f (b) au semne opuse. Eroarea absolută este înjumătățită la fiecare pas, astfel metoda converge liniar.

Numărul de iterații n necesar pentru a obține soluția cu precizia ε, este dat de: $n=\log _{2}\left({\frac {\epsilon _{0}}{\epsilon }}\right)={\frac {\log \epsilon _{0}-\log \epsilon }{\log 2}},$

unde $\epsilon _{0}=b-a.$

Astfel, convergența liniară este exprimată de $\epsilon _{n+1}={\text{constant}}\times \epsilon _{n}^{m},\ m=1.$

Pseudocod[modificare | modificare sursă]

 ''N'' ← 1
 While ''N'' ≤ ''NMAX'' 
{ 
   ''c'' ← (''a'' + ''b'')/2 
   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+x1)/2;
		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";
}

In limbajul PASCAL:

Program Dihotomie;

const 
    eps := 0.00000000001;
    iter:=200;

var i : char,
    x , x0 , x1 , a , b , y : real;

function f(x:real):real;
    begin
        f:=(sqr(x)*x)-(2*sqr(x)*cos(x))+(x-3);
    end;

begin
    write('a= '); read(a);
    write('b= '); read(b);
    x0 := a; x1 := b; x := x0; y := f(x);
    if ( f(x0) * f(x1) < 0) then
        begin
            while ( (i <= iter) and ((y < -eps) or (y > eps))) do
                begin
                    x := (x0+x1)/2;
                    y := f(x);
                    if (f(x0)*y < 0) then x1 := x 
                                     else x0 := x;
                    writeln();
                    writeln('f(',x,')=',f(x) ,'la iteratia ',i);
		            i := i + 1;
                end;
            if (i > iter) then writeln('problema nu se poate rezolva in nr.maxim de iteratii')
                          else writeln('interval invalid');
        end;
end.