Metoda Newton (tangentei)

Metoda Newton (tangentei)

Fie o radacina a ecuatiei

f ( x ) = 0,

unde f : [a, b] → R , .

Vom aplica aceasta metoda impunand urmatoarele conditii:

1. este separata in [a, b];

2. f ' si f '' pastreaza acelasi semn in [a, b].

Fie x _n o valoare aproximativa a lui . Avem

= x _n + h _n (h _n foarte mic).

Dezvoltand dupa formula lui Taylor cu doi termeni avem

0 = f () = f (x _n + h _n) ≈ f (x _n) + h _n f '(x _n) .

Urmeaza

, pentru n = 0, 1, 2, .

Deci, introducand expresia lui h _n in expresia lui , inlocuind pe prin x _{n - 1} avem

, cu n = 0, 1, 2,

1 Argument teoretic

Metoda tangentei se aplica la capatul segmentului [a, b] (a sau b) dupa cum valoarea functiei in acel capat (punct) si valoarea derivatei a II-a in acelasi punct au acelasi semn (se vor vedea graficul de mai jos).

Sa demonstram acest fapt pentru cazul (B), adica pentru f (a) < 0, f (b) > 0, f' (a) >0 si f'' (a) > 0.

Sa demonstram prin inductie ca si in consecinta f (x_n) > 0. Punem

Aplicand formula lui Taylor avem

unde .

Deoarece f" (x) > 0 urmeaza ca

sau

Tinand cont de semnele lui f (x_n) si f'(x_n) rezulta ca

x _n+1 < x _n ( n = 0, 1, 2, .)

adica aproximatiile succesive

x₀ , x₁, ., x_n, .

formeaza un sir descrescator, marginit inferior de a, deci convergent.

Notam

Trecand la limita in egalitatea iteratiilor avem:

2 Interpretarea geometrica

Notam cu punctul initial in care aplicam metoda lui Newton.

Dupa repetarea procedeului obtinem succesiv punctele

, , . , .

Punctul imediat urmator A_n+1 il obtinem astfel:

scriem ecuatia unei drepte ce trece prin A_n si de coeficient unghiular f'(x_n), adica

intersectam aceasta dreapta cu axa Ox si obtinem pentru x = x_n+1

, pentru n = 0, 1, 2, .

3 Evaluarea erorii metodei Newton

Teorema 1 Fie f : [a, b] → R , iar o radacina a ecuatiei f (x) = 0 (adica f () = 0). Daca este o valoare aproximativa a lui, , iar

atunci avem

Demonstratie. Din teorema lui Lagrange avem:

deci

Teorema 2 Daca f satisface conditiile Teoremei 1, atunci eroarea celei de a n-a aproximatii va fi

Demonstratie. Folosind formula lui Taylor cu trei termeni avem

unde .

Deoarece din formula lui Newton, avem

Corolar 1 Din Teoremele 1 si 2 urmeaza

Teorema 3 Fie f : [a, b] → R , iar o radacina a ecuatiei f (x) = 0. Fie x_n si x_n+1 doua aproximatii ale lui obtinute prin procedeul Newton. In aceste conditii avem

unde m₁, M₂ au semnificatiile din Teoremele (1) si (2).

Demonstratie. Aplicam formula lui Taylor cu trei termeni si avem

unde

Deci

Observatie 1 Formula lui Newton asigura o convergenta rapida daca aproximatia initiala este aleasa astfel incat sa avem

Observatie 2 Daca in plus avem

atunci

Exemplu 1 Calculati radacina ecuatiei

x - 2x² + 3x - 1 = 0

situata in intervalul (0, (0,5)) cu ajutorul metodei lui Newton, folosind trei iteratii. Evaluati eroarea produsa.

Solutie.

Avem f (0) = -1, f (0,5) = 0,125, f ' (x) = 3x² - 4x + 3, f" (x) = 6x - 4.

Deci f ' (x) > 0 si f" (x) < 0, , prin urmare x₀ = 0.

Calculam

Eroarea o vom calcula astfel

Deci, pentru eroarea produsa, , avem

Programul pentru metoda tangentei

Programul prezentat mai jos determnina solutia unei ecuatii de forma (1.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 si derivata ei sunt definite prin proceduri de tip functie.

In cadrul programului nu se verifica semnul derivatelor. Pentru determinarea iteratiei urmatoare se parcurg urmatoarele etape:

se verifica valoarea derivatei functiei in punctul a; daca aceasta valoare este nenula se determina punctul de intersectie dintre tangenta la graficul functiei in punctul de coordonate (a, f (a)) si axa Ox;

daca punctul determinat se afla in interiorul intervalului (a, b), atunci acest punct reprezinta iteratia urmatoare;

daca valoarea derivatei functiei in punctul a este zero, se incearca determinarea iteratiei urmatoare pornind din punctul b;

daca nu se poate construi iteratia urmatoare (valorile derivatei functiei in capetele a si b sunt nule sau punctele de intersectie nu sunt in interiorul intervalului (a, b)) algoritmul se opreste: nu se poate aplica metoda tangentei pe intervalul [a, b];

daca s-a determinat iteratia urmatoare se pastreaza intervalul care contine solutia si se repeta procedeul.

Determinarea iteratiilor se opreste atunci cand modulul diferentei a doua iteratii consecutive este mai mic decat eroarea admisa epsilon. De asemenea, programul se opreste cand se determina o iteratie care este chiar solutia ecuatiei.

# include <iostream .h>

# include <math .h>

# include <conio .h>

double f (double x)

double df (double x)

void main (void)

else

}

}

if ( t = = 1)

if (df (b) = = 0)

t = 2;

else

else

}}}}

while ( ( t = = 0)&& (pas > eps) );

if ( t = = 3)

cout <<"Solutia este x ="<< c << endl;

if ( t = = 0)

cout <<"Solutia aproximativa este x ="<< c << endl;

if ( t = = 2)

cout <<"Nu se poate aplica metoda tangentei!"<<endl;}

getch ( );}