Metoda bipartitiei

Metoda bipartitiei

Fie ecuatia

f (x) = 0 (4.1)

unde    f : [ a , b ] → R este continua iar f (a) f (b) < 0.

Impartim segmentul [ a , b ] in doua parti. Distingem urmatoarele cazuri:

1. si atunci este radacina cautata si oprim procedeul;

2. si in acest caz selectam din cele doua intervale si pe acela pentru care valorile functiei in capete au semne contrare.

Acest interval il notam [ a₁ , b₁ ] si apoi continuam procedeul.

Se obtine, fie radacina exacta, fie un sir de intervale inchise cuprinse unele in altele

astfel incat

pentru n = 1, 2,. (4.2)

Prin urmare avem

Capetele din stanga ale acestor intervale a_1, a₂, ., a_n,    . formeaza un sir crescator si marginit superior de b, iar capetele din dreapta b_1, b₂, ., b_n, . formeaza un sir descrescator si marginita inferior de a. Din teorema "clestelui" urmeaza

( fiind limita lor comuna). (4.3)

aratam ca numarul este radacina ecuatiei (4.1). Trecand la limita in (4.2) si tinand cont de continuitatea functiei f si de faptul ca sirurile si sunt convergente avem:

sau

si tinand cont de (4.3) rezulta

adica

Observatie 1.1.1 Metoda presupune ca    radacinile lui (4.1) au fost separate pe [a, b].

Observatie 1.1.2 Daca este o valoare aproximativa a lui la pasul n atunci avem

Observatie 1.1.3 Metoda este comoda pentru obtinerea unei estimari initiale a radacinii separate, pentru utilizarea ei in alte metode si este usor programabila pe calculator.

Observatie 1.1.4 Procedeul converge lent.

Observatie 1.1.5 In cazul in care radacinile nu au fost separate luam dupa caz o valoare foarte mica pentru a₁ (de exemplu -10 ⁿ cu n N si b₁ = 0 sau a₁ = 0 si b₁ = 10 ⁿ astfel incat sa avem f (a₁) f (b₁) < 0.

Observatie 1.1.6 In momentul opririi procedeului mai putem imbunatati precizia calculelor facand media aritmetica a ultimelor doua    valori a_n si b_n ( n N ^* ), adica

Exemplu 1.1.1 Sa determinam radacina functiei

cuprinsa in intervalul [0, 1].

Solutie:

Avem: f (0) = - 1, f (1) = 1

f (0,5) ≈ 0,125 - 2 ∙ 0,25 + 3 ∙ 0,5 - 1 = 0,1250.

Deci intervalul ales [ a₁ , b₁ ] este [0, (0,5)].    Continuam procedeul.

f (0,25) ≈ 0,0156 - 2 ∙ 0,0625 + 3 ∙ 0,25 - 1 = - 0,3594.

Deci intervalul ales [ a₂ , b₂ ] va fi [(0,25), (0,5)].

f (0,375) ≈ 0,0527 - 2 ∙ 0,1406 + 3 ∙ 0,375 - 1 = - 0,1035.

Intervalul ales [ a₃ , b₃ ] va fi [(0,375), (0,5)].

f

Intervalul ales [ a₄ , b₄ ] va fi [(0,375), (0,4375)].

f

Deci segmentul ales [ a₅ , b₅ ] va fi [(0,4063), (0,4375)].

f

Intervalul ales [ a₆ , b₆ ] va fi [(0,4219), (0,4375)].

f

Intervalul ales [ a₇ , b₇ ] va fi [(0,4297), (0,4375)].

f

Intervalul ales [ a₈ , b₈ ] va fi [(0,4297), (0,4336)].

f

Intervalul ales [ a₉ , b₉ ] va fi [(0,4297), (0,4317)].

f

Luam in final

Programul pentru metoda bipartitiei

Programul determina solutia unei ecuatii de forma (4.1) in urmatoarele ipoteze:

solutia este separata intr-un interval [a, b];

functia este continua pe intervalul [a, b].

Datele de intrare sunt: capetele intervalului in care se cauta solutia (a, b) si precizia dorita (epsilon). Functia este definita in cadrul programului.

#include<iostream.h>

#include<math.h>

#include<conio.h>

double f ( double x)

void main (void)

else

if (f(a) _* f(c) < 0)

b=c;

else

a=c;

}

while ( ( t = = 0) && (fabs (b-a) > eps) );

if ( t = = 0)

cout<<"Solutia aproximativa este x ="<< (a+b)/2<<endl;}

getch ( );}