Metoda bipartiiei

1. Generaliti

Ecuaiile reprezint expresii matematice care conin o variabil (necunoscut) i pot fi puse sub forma general

: , , , ( ) 0f D R D R D f x = . (1)

Egalitatea este valabil numai pentru o mulime finit i discret de valori ale lui x. Expresia ( )f x poate conine valori numerice, operatori aritmetici i funcii elementare. Rezolvarea analitic (pe baz de formule) este posibil numai n anumite cazuri particulare sau pentru ecuaii polinomiale de grad inferior. Rezolvarea numeric permite rezolvarea tuturor tipurilor de ecuaii cu aproximaii orict de bune. Fenomenul de aproximare nu este un impediment, deoarece, n final, soluia va fi exprimat cu un numr finit de cifre semnificative. Deci, metodele de rezolvare numeric sunt singurul instrument viabil pentru rezolvarea ecuaiilor. Trebuie ns menionat c rezolvarea global automat, adic pentru tot intervalul de variaie a variabilei x, este posibil numai pentru ecuaii polinomiale. Pentru celelalte tipuri de ecuaii, de tip transcendent, aplicarea corect a metodelor numerice este posibil numai dup ce au fost identificate intervalele care conin valorile soluiei. n plus, utilizarea metodelor numerice locale trebuie precedat de verificarea condiiilor n care acestea pot fi aplicate. Acestea, de obicei, se refer la proprietile funciei ( )f x , de exemplu continuitatea, sau la cele ale derivatelor funciei.

Separarea rdcinilor reale n cazul ecuaiilor neliniare reale

Vom considera ecuaia sub forma general dat de relaia (1) i trebuie s gsim soluia D . Prima dat se efectueaz separarea rdcinilor, adic trebuie s determinm intervalele din domeniul de definiie D, astfel nct n fiecare interval s fie o singur rdcin a ecuaiei.

Prima metod de acest gen este irul lui Rolle. Vom presupune c ( )1f C D , adic funcia f este derivabil pe D i are derivata continu. n aceste condiii se rezolv ecuaia

( ) 0,f x x D = . Dac 1 2, ,..., nx x x sunt rdcinile ecuaiei derivate, atunci se formeaz irul lui Rolle cu valorile ( ) ( ) ( )1 2, ,..., nf x f x f x . Orice schimbare de semn ce apare la doi termeni consecutivi ( ) ( )1,i if x f x + exprim existena unei rdcini unice n intervalul ( )1,i ix x + , conform teoremei lui Rolle.

Exemplu Fie ecuaia 3 22 9 12 4,5 0x x x + = . S gsim intervalele de separare ale rdcinilor. Sol. Vom considera funcia polinomial

3 2: , ( ) 2 9 12 4,5f R R f x x x x = + i ecuaia neliniar

( ) 0,f x x R= . n continuare atam ecuaia ( ) 0f x = , care este echivalent cu

2 26 18 12 0 3 2 0x x x x + = + = care are rdcinile 1 21, 2x x= = . Folosind irul lui Rolle scriem urmtorul tabel

x 1 2 +

( )f x ( )f = ( )1 0,5f = ( )2 0,5f = ( )f + = +

Observm c semnul valorilor lui ( )f x alterneaz, deci ecuaia ( ) 0f x = are trei rdcini reale n intervalele ( ),1 , ( )1,2 i ( )2,+ .

O a doua metod de separare a soluiilor ecuaiei (1) este folosind polinomul de interpolare al lui Lagrange sau al lui Newton. Dac n domeniul de definiie al funciei

: ,f D R D R se aleg punctele

1 2 nx x x< <

2a b+

. (3) Cele dou subintervale obinute sunt

, i ,2 2

a b a ba b+ +

, (4) iar soluia este ntr-unul dintre ele. Se calculeaz

2a bf +

(5)

i dac aceast valoare este zero atunci

2a b += (6)

este soluie exact. Altfel, pentru a gsi subintervalul n care se afl soluia vom evalua funcia la capetele acestor intervale. Deoarece funcia este continu, rezult c subintervalul pe care se face schimbarea de semn conine soluia cutat. Se va reine intervalul cu soluia, l vom nota 1 1[ , ]a b i n continuare acest interval este imprit la rndul lui n dou pari egale i analiza continu n acelai fel.

Dup un numr n de pai gsim fie soluia exact, fie un ir de segmente cuprinse unele n altele

1 1 2 2[ , ] [ , ] [ , ]n na b a b a b . (8) Astfel subintervalul care conine soluia este restrns pe parcursul aplicrii metodei. Algoritmul se oprete atunci cnd, pentru eroarea dat , la un anumit pas k are loc relaia

( )kf x < (8) sau echivalent

k kb a < . (9)

n cadrul acestei metode se construiesc dou iruri { } { } i n nn N n Na b (10)

n felul urmtor: se alege 0

0

,

,

a a

b b=

=

. (11)

Avem una din urmtoarele situaii

( ) 02

a bf a f +

(12) sau

( ) 02

a bf f b+

, (13) corespunztor crora se aleg

1

1

,

,

2

a a

a bb

=

+=

(14)

sau

1

1

,

2.

a ba

b b

+=

=

(15)

La pasul n avem intervalul [ , ]n na b n care se afl rdcina i prin urmare

( )12n n n

b a b a = . (16)

Observaie. irul { }n n Na este monoton cresctor i mrginit superior de b, iar irul { }n n Nb este monoton descresctor i mrginit inferior de a. Din teorema cletelui obinem

lim limn nn n

a b

= = . (17)

Teorema. Limita comun a celor dou iruri este soluia ecuaiei ( ) 0f x = . Dem. tim c f este o funcie continu, c ( ) ( ) 0n nf a f b < i c { }n n Na i { }n n Nb sunt convergente. Trecnd la limit avem

( ) ( ) ( )lim ( ) ( ) 0 lim lim 0n n n nn n n

f a f b f a f b

, (18) cu relaia (17) obinem

( ) ( ) ( ) ( )20 0 0f f f f = . (19) Adic este soluie a ecuaiei (1).

Observaie. Metoda este avantajoas deoarece este uor programabil, ns algoritmul converge lent.

Exemplu Folosind metoda bipartiiei s aflm rdcina ecuaiei algebrice transcendente 4 32 1 0x x x+ = aflat n intervalul [ ]0,1 , cu o eroare 110 < .

Soluie Aplicm metoda bipartiiei Notm 12)( 34 += xxxxf i 0, 1a b= = . Calculm valorile lui f la capetele intervalului

(0) 1f = , (1) 1f =

i observm c 0)1()0(

Determinm valoarea lui f n 0,5c = , adic (0,5) 0,06 0,25 0,5 1 1,19

( )1 0,859 0,875 0,8672

= + .

Aplicaie S rezolvm, cu o eroare 0,01 < , ecuaia 3 1 0x x+ = . Rezolvare Deoarece

( ) 2 3 1 0,f x x x R = + > rezult c ( )f x este strict cresctoare. Cum

( )( )

lim

limx

x

f xf x

+

=

= +

rezult c ( )f x are o singur rdcina real. Se observ c ( )0 1f = i ( )1 1f = , adic ( ) ( )0 1 0f f < deci rdcina se gasete ntre ( )0,1 .

Vom aplica metoda bipartiiei intervalului ( )0,1 .

Calculm mijlocul intervalului ( )0,1 i gsim 1 0,5c = . n acest punct, ( )0,5 0,375f = . Cum ( ) ( )0,5 1 0f f < , rdcina se gsete n intervalul ( ) 0,5; 1 .

Se continu procedeul iterativ, rezultnd 2 0,75c = . n acest punct, ( )0,75 0,1719f = ( ) ( )0,5 0,75 0f f < , deci intervalul s-a resticionat la ( )0,5; 0,75 .

Se continu procedeul iterativ, obinndu-se dup a aptea iteraie 7 0,6797c = , ( ) 0,6797 0,0063f , deci rdcina se gsete n intervalul ( )0,6797, 0,6875 .

Cum 0,6875 0,6797 0,0078 0,01= < , valoarea rdcinii obinute cu precizia cerut este 0,6836 = .