Metoda tangentelor.

Ideea generală a metodei este următoarea: prin punctul (b,f(b)) se duce o dreaptă tangentă la graficul functiei . Se determină punctul c în care ea intersectează axa 0X. Acest punct se considera noua extremitate, prin care se duce tangenta. Procesul se repetă, până nu obţinem o apropiere suficientă de soluţia exactă. Pentru această metodă vom cere suplimentar, existenţa şi semnul constant al derivatei de ordin 2 pentru funcţia f(x) pe tot segmentul [a,b]. (pe segmentul dat funcţia să fie sau concavă sau convexă

Pentru a determina extremitatea din care pornim, trebuie să ţinem cont de următoarele cazuri posibile:
1) f’(x) > 0 f’’(x) > 0 2) f’(x) > 0 f’’(x) < 0
3) f’(x) < 0 f’’(x) > 0 4) f’(x) < 0 f’’(x) < 0

Este adevărată afirmaţia: Selectarea în calitate de punct iniţial al metodei tangentelor a extremităţii, pentru care se îndeplineşte relaţia f(x)*f’’(x) > 0 permite determinarea soluţiei cu orice grad de exactitate e
Vom cerceta cazul 1 – funcţia este convexă, crescătoare. (Celelalte cazuri se cercetează la fel)

Deoarece a doua derivată e mai mare ca 0, graficul funcţiei este superior coardei. Pornind din extremitatea în care funcţia este pozitivă vom obţine intersecţia cu axa 0x într-un punct interior al [a,b] Vom considera acest punct noua extremitate a intervalului. Repetând procedura vom obţine un şir de puncte interioare, care tind spre soluţia exactă. Dacă însă vom fixa extremitatea negativă, tangenta generată poate părăsi segmentul [a,b].
Deoarece funcţia este crescătoare, vom fixa extremitatea B

Teoremă
Dacă f(a)*f(b )<0, f’(x) şi f’’(x)  0 şi îşi păstrează semnul pe [a, b], atunci, pornind de lo o aproximare iniţială x0 [a, b] (f(x0)f’’(x0) > 0) soluţia unică a ecuaţiei  pe [a, b] poate fi calculată cu orice grad de exactitate .

Demonstraţie: fie f(a) < 0, f(b) >0, f’(x) > 0 f’’(x) > 0. considerăm x0 = b, f(x0)>0. Pentru demonstrare vom folosi metoda inducţiei matematice, verificând ipoteza, cum că toate valorile şirului xn sunt > ,  n.

n = 0. x0 = b, f(x0)>0. evident.

Fie, pentru un careva n ipoteza este adevărată, xn > , Considerăm  = xn + ( - xn), apoi aplicăm formula Tailor (pentru descompunerea funcţiei în sumă de polinoame) şi obţinem:

0 = f() = f(xn) + f’(xn) ( - xn) +1/2 f’’(cn) ( - xn)2 unde 
Deoarece f’’(x) > 0, rezultă f(xn) + f’(xn) ( - xn) < 0 sau f’(xn) ( - xn) < - f(xn)  ( - xn) < - f(xn)/ f’(xn)

  < xn - f(xn)/ f’(xn) = xn+1. ,

Din formula recurentă rezultă direct că x0 > x1 > … >xn …> 1 - limita xn.

Trecând la limită obţinem

1 = 1 – f(1)/ f’(1), de unde f(1) =0 deci 1 =  ceea ce şi trebuia de demonstrat.

Algoritmizarea metodei

0. Calculăm semnul derivatei 2 pe segmentul [a,b].
1. Fixăm punctul iniţial x0 conform formulei: f(x0)*f’’(x0)>0
2. Calculăm următoarea aproximaţie conform formulei:

3. Repetăm pasul 2 până nu obţinem soluţia cu exactitatea cerută.


Estimarea erorii.
Faptul că şirul aproximărilor succesive prin metoda tangentelor converge către soluţia exactă implică următoarea concluzie: cu cât mai multe iteraţii ale metodei vor fi realizate, cu atât mai bine va fi aproximată soluţia. Totuşi, am putea determina o formulă, care permite estimarea exactă a erorii de calcul, şi, prin urmare, exactitatea soluţiei obţinute.

Vom considera, că prima derivată a funcţiei f(x) este continuă pe segmentul [a,b].
Fie atunci m1 şi M1 două numere pozitive, pentru care are loc relaţia

0 < m1  | f’(x) |  M1 < + 


(exprimăm xn prin xn-1, ţinând cont de faptul că 0 = f(), îl adăugăm în partea stângă a egalităţii, apoi estimăm diferenţa între soluţia exactă şi cea aproximativă.
Pentru a deduce formula finală vom folosi
Teorema Lagrange Fie f:[a,b] R, continuă şi derivabilă pe [a,b] . Atunci  c(a, b) astfel încât:

f(b) –f(a) = (b -a) f’(c)

 fără demonstraţie 

Deci dacă e necesar să obţinem soluţia cu exactitate dată , vom repeta aproximările până la obţinerea inegalităţii
Aici xn şi xn+1 sunt două aproximaţii succesive iar M1 şi m1 corespunzător marginea superioară şi inferioară a f’(x) pe [a, b].

METODA BISECŢEI

Fie dată ecuaţia f(x) = 0 (1)

Vom considera cazul, când funcţia este continuă pe [a,b] şi f(a)*f(b) < 0. Suplimentar vom considera că pe [a,b] semnul derivatei 1 a funcţiei este constant, deci avem doar o singură soluţie.
Pentru determinarea soluţiei ecuaţiei (1) vom detecta mijlocul segmentului [a,b],  = (a+b)/2, şi vom calcula valoarea funcţiei în acest punct. Dacă f() = 0, atunci  este soluţia ecuaţiei. În caz contrar cercetăm segmentele [a, ] şi [, b].
Pentru aproximarea următoare vom selecta acel segment, pentru care valoarea funcţiei în extremităţi are semne opuse. Dacă sign(f(a)) = sign(f()), atunci vom continua cercetarea pe segmentul [a1, b1], unde a1 , b1b . În caz contrar extremităţile vor fi a1a, b1. Noul segment [a1, b1] iarăşi se divizează, apoi se repetă cercetarea semnelor valorilor funcţiei în extremităţi şi în mijlocul segmentului. Procedura se repetă până când nu se obţine soluţia exactă sau (în majoritatea absolută a cazurilor!) devierea soluţiei aproximative de la cea exactă nu devine suficient de mică.

În procesul de construcţie a segmentelor succesive obţinem consecutivitatea segmentelor
[a,b], [a1, b1], [a2, b2], [a3, b3], ... [an, bn]...

Pentru fiecare din ele are loc relaţia f(ai)*f(bi) < 0 , i=1,...,n... (2)
Deoarece lungimea fiecărui segment următor este egală cu ½ din lungimea celui precedent putem exprima lungimea oricărui segment prin cea a segmentului iniţial:

bi - ai = (½ )i * (b – a) (3)

Din construcţie şi proprietăţile funcţiei f(x), rezultă că şirul extremităţilor stângi a, a1, a2, ..., an , ... este monoton crescător, mărginit superior, iar şirul extremităţilor drepte b, b1, b2, ..., bn , ... este monoton descrescător, mărginit inferior. De aici rezultă convergenţa ambelor şiruri şi existenţa limitei pentru fiecare din ele.

Trecând la limită în egalitatea (3) obţinem:

Trecând la limită în inegalitatea (2) din continuitatea f(x) primim ( f())2  0. Prin urmare f()=0 deci  e soluţia ecuaţiei (1).

Deoarece  e un punct din segmentul [an, bn] rezultă

0   - an  1/2n(b - a)


În cazul când semnul derivatei întâi alternează pe segmentul [a, b] , adică rădăcinile ecuaţiei nu sunt separate, metoda permite determinarea doar a unei soluţii.



ALGORITMIZAREA METODEI.

Datorită simplităţii sale metoda este uşor de realizat în formă algoritmică:
0. Ecuaţia se aduce la forma y=f(x) (pentru o prezentare mai comodă în formă de funcţie în interiorul programului)

1. Se introduc valorile a, b – extremităţile segmentului şi e – exactitatea cu care trebuie obţinută soluţia
2. Se calculează c=(a+b)/2, f(a), f(b), f(c).
3. Dacă sign( f(a)) = sign( f(c)), atunci vom considera că a trece în c. În caz contrar
(sign( f(b) ) = sign( f(c) )) b va primi valoarea lui c.
4. Pentru noile valori a şi b repetăm paşii 2 –3 atât timp cât (b - a)  e
5. Afişăm în calitate de soluţie mijlocul ultimului segment [a,b].

Metoda secantelor.

Fie dată ecuaţia f(x) = 0

Pentru utilizarea metodei secantelor vom cere îndeplinirea aceloraşi condiţii asupra funcţiei f(x) ca şi pentru metoda precedentă
Ca şi la metoda precedentă în calitate de soluţie vom căuta un punct interior al intervalului, dar de această dată el nu va fi mijlocul segmentului, ci punctul intersecţiei dreptei ce trece prin punctele (a, f(a)) şi (b,f(b)) cu axa 0X.

Ideea generală a metodei este următoarea: prin punctele (a, f(a)) şi (b,f(b)) se duce o dreaptă. Se determină punctul c în care ea intersectează axa 0X. Apoi se determină semnul f(c). Extremitatea în care semnul funcţiei coincide cu semnul f(c), trece în c. Procesul se repetă, până nu obţinem o apropiere suficientă de soluţia exactă. Această interpretare a metodei o face să fie tot atât de lentă ca şi metoda bisecţiei.

Dacă însă suplimentar, vom cere existenţa şi semnul constant al derivatei de ordin 2 pentru funcţia f(x) pe tot segmentul [a,b]. ( pe segmentul dat funcţia să fie sau concavă sau convexă.), putem aplica o variaţie mai puternica a acestei metode:

Ecuaţia dreptei ce trece prin 2 puncte date este determinată de relaţia:


În cazul intersecţiei cu axa X y=0, deci putem calcula poziţia punctului c pe axa X:

Pentru a realiza calculul soluţiei vom crea şirul {xn} conform regulei:

La paşii următori valorile elementelor şirului se vor forma, ţinând cont de următoarele situaţii:

a) dacă funcţia este convexă (f’’(x) > 0 ) (secanta este plasată mai sus de graficul funcţiei) atunci extremitatea segmentului iniţial, în care valoarea funcţiei este pozitivă rămâne nemişcată (fixă), iar cealaltă extremitate trece de fiecare dată în punctul nou calculat.

b) dacă funcţia este concavă (f’’(x) < 0 ) (secanta este plasată mai jos de graficul funcţiei) atunci extremitatea segmentului iniţial, în care valoarea funcţiei este negativă rămâne nemişcată (fixă), iar cealaltă extremitate trece de fiecare dată în punctul nou calculat.

Cu alte cuvinte, metoda secantelor are un punct fix, celălalt se modifică de fiecare dată. Observăm, că fixă este extremitatea, pentru care are loc relaţia:
f(x) f’’(x) > 0.
Pentru a calcula cealaltă extremitate a noului segment, trebuie să ţinem cont de următoarele cazuri posibile:

1) f’(x) > 0 f’’(x) > 0 2) f’(x) > 0 f’’(x) < 0 3) f’(x) < 0 f’’(x) > 0 4) f’(x) < 0 f’’(x) < 0

Vom cerceta cazul 1 – funcţia este convexă, crescătoare. (Celelalte cazuri se cercetează la fel)
Deoarece a doua derivată e mai mare ca 0, graficul funcţiei este inferior coardei. Pornind din extremitatea în care funcţia este pozitivă vom obţine intersecţia cu axa 0x într-un punct interior al [a,b] (mai întâi se intersectează axa, apoi se ajunge la extremitatea opusă.) Repetând procedura vom obţine un şir de puncte interioare, care tind spre soluţia exactă. Dacă însă vom fixa extremitatea negativă, coarda generată la pasul 2 va intersecta mai întâi graficul, apoi axa 0X, ceea ce poate genera părăsirea segmentului [a,b].
Deoarece funcţia este crescătoare, vom fixa extremitatea B, luând în calitate de x0 extremitatea A.
Conform formulei pentru secantă

după care a  x1
Repetând procedura, obţinem:

Vom demonstra acum, că şirul de aproximări a= x0 , x1 , …, xn … converge către soluţia ecuaţiei f(x) = 0
Din formula recurentă

rezultă că xn+1 > xn  n (numitorul fracţiei este pozitiv deoarece funcţia este crescătoare, numărătorul – negativ, deoarece xn, este punctul de intersecţie a coardei cu 0X, iar graficul funcţiei în acest punct este inferior coardei, deci + negativ, (b - xn) – pozitiv, deci tot produsul este negativ, cu – în faţă, trece în +).
Aşa dar avem şirul x0 < x1 < … Şirul este crescător şi mărginit, deci există limita lui 1. Trecând la limită în formula recurentă, obţinem

sau, după înlocuire

de unde rezultă 0 = f(1). (numitorul fracţiei e diferit de 0, al doilea factor – la fel). Deci 1 este soluţia ecuaţiei iniţiale. 1 = , ceea ce şi trebuia de demonstrat.
Celelalte trei cazuri se demonstrează analogic.

Algoritmizarea metodei

1. Determinăm, care va fi extremitatea fixă a segmentului. Pentru aceasta calculăm punctul de intersecţie (x1) a coardei ce trece prin f(a)) şi (b,f(b)) cu axa 0X. Drept extremitate fixă vom lua acel punct pentru care semnul funcţiei diferă de semnul f(x1).
2. Extremitatea “flotantă” primeşte valoarea calculată x1.
3. Calculăm următoarea aproximaţie conform formulei:

4. Repetăm pasul 3 până nu obţinem soluţia cu exactitatea cerută.
Estimarea erorii.

Faptul că şirul aproximărilor succesive prin metoda coardelor converge către soluţia exactă implică următoarea concluzie: cu cât mai multe iteraţii ale metodei vor fi realizate, cu atât mai bine va fi aproximată soluţia. Totuşi, am putea determina o formulă, care permite estimarea exactă a erorii de calcul, şi, prin urmare, exactitatea soluţiei obţinute.

Vom considera, că prima derivată a funcţiei f(x) este continuă pe segmentul [a,b].
Fie atunci m1 şi M1 două numere pozitive, pentru care are loc relaţia

0 < m1  | f’(x) |  M1 < + 

Pentru simplitate, vom cerceta cazul, când aproximările succesive se fac după formula (2) (cazul, când e folosită formula (1) se demonstrează analogic). Aşa dar,


(exprimăm xn prin xn-1)

(Ţinând cont de faptul că 0 = f(), îl adăugăm la numărătorul fracţiei, apoi estimăm diferenţa între soluţia exactă şi cea aproximativă.


Pentru a deduce formula finală vom folosi următoarea teoremă (se demonstrează în cursul de analiză matematică)

Teorema Lagrange Fie f:[a,b] R, continuă şi derivabilă pe [a,b] . Atunci  c(a, b) astfel încât:

f(b) –f(a) = (b -a) f’(c)

 fără demonstraţie 

Vom aplica formula din teoremă aparte pentru partea stângă şi partea dreaptă a ultimei egalităţi.

Înlocuind, obţinem :

Deci dacă e necesar să obţinem soluţia cu exactitate dată , vom repeta aproximările până la obţinerea inegalităţii

Aici xn şi xn+1 sunt două aproximaţii succesive iar M1 şi m1 corespunzător marginea superioară şi inferioară a f’(x) pe [a, b].