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]

Câțiva pași ai metodei înjumătățirii intervalului, aplicați pe intervalul inițial [a1;b1]. Punctul reprezentat cu culoarea roșie având cea mai mare dimensiune este rădăcina funcției.

Descrierea metodeiModificare

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 [ab], 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.

ExempluModificare

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.

Iteration        
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 metodeiModificare

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  

PseudocodModificare

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


BibliografieModificare

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

NoteModificare

Legături externeModificare