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.

Descrierea metodei 
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 
Considerăm funcția polinomială

Pentru început, considerăm două numere  și  astfel încât  și  au semne opuse. De exemplu,  și  satisfac aceste criterii: 

și

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

În prima iterație,  și , iar mijlocul intervalului este

Valoarea funcției la mijlocul intervalului: . Deoarece  este negativ,   este înlocuit cu  pentru următoarea iterație, pentru a respecta condiția ca  și  să aibă semne opuse. După un număr finit de pași, intervalul  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.

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

Analiza metodei
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:

unde 

Astfel, convergența liniară este exprimată de

Pseudocod 

 ''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.

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

Note

Legături externe 
 www.utgjiu.ro/math/mbuneci/book/mn2009.pdf
 http://cs.upm.ro/~bela.finta/.files/carti/Numerika.pdf 

 Algoritmi de determinare a rădăcinilor ecuațiilor
Î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 . Descrierea metodei 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 ) /ș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 cu5 , la fiecare pas.Procesul se continuă până când intervalul este suficient de mic . Exemplu Considerăm funcția polinomială Pentru început , considerăm două numere și astfel încât și au semne opuse . De exemplu , și satisfac aceste criterii : și Deoarece funcția este continuă , există o rădăcină în intervalul [ 1 , . În prima iterație , și , iar mijlocul intervalului este Valoarea funcției la mijlocul intervalului : \ . Deoarece este negativ , este înlocuit cu pentru următoarea iterație , pentru a respecta condiția ca și să aibă semne opuse . După un număr finit de pași , intervalul va avea lățimea tinzând spre 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 . Dupăiterații , se determină rădăcina funcției , care ia valoarea521 . Analiza metodei 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 : unde Astfel , convergența liniară este exprimată de Pseudocod ''N'' ← 1 While ''N'' ≤ ''NMAX'' { ''c'' ← ( ''a'' + ''b'')/2 If ( ''f' ' (''c'' ) =or ( ''b'' – ''a'')/2 < ''TOL'' then { Output(''c'' ) Stop } ''N'' ← ''N' ' + 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 eps00000000001 #define iter 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\:=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 ) <then begin while ( ( i <= iter ) and ( ( y < -eps ) or ( y > eps ) ) ) do begin x\ : = ( x0+x1)/2 ; y\ : = f( x ) ; if ( f( x0)*y <then x1\ : = x else x0\ : = x ; writeln ( ) ; writeln('f( ',x, ')=',f( x),'la iteratia ',i ) ; i\ : = i + end ; if ( i > iter ) then writeln('problema nu se poate rezolva in nr.maxim de iteratii' ) else writeln('interval invalid' ) ; end ; end . Bibliografie Constantin Ilioi , Probleme de optimizare și algoritmi de aproximare a soluțiilor , Editura Academiei Republicii Socialiste România , București , Note Legături externe www.utgjiu.ro/math/mbuneci/book/mn2009.pdf http://cs.upm.ro/ ~ bela.finta/.files/carti/Numerika.pdf Algoritmi de determinare a rădăcinilor ecuațiilor