Rezolvarea aproximativa a ecuatiilor algebrice si transcendente

Rezolvarea aproximativa a ecuatiilor algebrice si transcendente

1.1 Metoda bipartitiei

Fie ecuatia

f (x) = 0 (1.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,. (1.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). (1.3)

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

sau

si tinand cont de (1.3) rezulta

adica

Observatie 1.1.1 Metoda presupune ca radacinile lui (1.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 (0,4375) ≈ 0,0837 - 2 ∙ 0,1914 + 3 ∙ 0,4375 - 1 = 0,0134.

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

f (0,4063) ≈ 0,0671 - 2 ∙ 0,1651 + 3 ∙ 0,4063 - 1 = - 0,0442.

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

f (0,4219) ≈ 0,0751 - 2 ∙ 0,1780 + 3 ∙ 0,4219 - 1 = - 0,0152.

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

f (0,4297) ≈ 0,0793 - 2 ∙ 0,1846 + 3 ∙ 0,4297 - 1 = - 0,0008.

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

f (0,4336) ≈ 0,0815 - 2 ∙ 0,1880 + 3 ∙ 0,4336 - 1 = 0,0063.

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

f (0,4317) ≈ 0,0805 - 2 ∙ 0,1864 + 3 ∙ 0,4317 - 1 = 0,0028.

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

f (0,4307) ≈ 0,0799 - 2 ∙ 0,1855 + 3 ∙ 0,4307 - 1 = 0,0010.

Luam in final

Programul pentru metoda bipartitiei

Programul prezentat mai jos determina 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 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 ( );}

1.2 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.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:

1.2.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, .

1.2.3 Evaluarea erorii metodei Newton

Teorema 1.2.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:

Eseu: Raport de incercare Eseu: Detergenti .Sapunuri. Substante tensio-active - clasificare

deci

.

Teorema 1.2.2 Daca f satisface conditiile Teoremei 1.2.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.2.1 Din Teoremele 1.2.1 si 1.2.2 urmeaza

Teorema 1.2.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.2.1) si (1.2.2).

Demonstratie. Aplicam formula lui Taylor cu trei termeni si avem

unde

Deci

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

.

Observatie 1.2.2 Daca in plus avem

atunci

.

Exemplu 1.2.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 ( );}

1. 3 Metoda secantei (coardei)

1.3.1 Prezentarea metodei

Metoda coardei se aplica in capatul in care nu se aplica metoda Newton (unde f si f"au acelasi semn). Sunt posibile doua situatii: 1) f(a) < 0 si 2) f(а) > 0

Scriem ecuatia unei drepte ce trece prin punctul mobil (opus celui in care se aplica Newton), de exemplu in cazul (B).

I.         Daca f(a) < 0 avem:

si, pentru x = x₁, urmeaza:

sau in general

, n = 0, 1, 2, .

II.       Daca f(а) > 0 avem:

si, pentru x = x₁, urmeaza:

In general avem:

, n = 0, 1, 2, .

In primul caz sirul iteratiilor este crescator si marginit de b, adica

Avem:

Trecand la limita avem

Cum y = f (x) admite o singura radacina in [a, b], urmeaza .

1.3.2 Evaluarea erorii in metoda coardei (secantei).

Fie f : [a, b] → R , , f" si f' au semne constante, iar este marginit, adica

.

Sa consideram cazul extremitatii mobile b (varf fix a). Avem

Deoarece , urmeaza:

.

Aplicand Teorema lui Lagrange avem

.

Deci

.

Deci egalitatea de mai sus devine

adica

Deoarece avem si

adica

Observatie 1.3.1 Daca avem

Exemplu 1.3.1 Determinati radacina ecuatiei algebrice

cu o eroare mai mica de 0,001.

Solutie

Avem . Deci R si

iar .

Prin urmare ecuatia are o singura radacina reala si aceasta se afla in intervalul

(- ∞,(0,66666)]. Cum f (0) = -1 retinem intervalul [0, (0,66666)]. Alegem capatul fix a= 0 si x₀ = 0,66666.

Urmeaza

,

,

,

,

,

,

,

,

Deci radacina aproximativa cu precizia de 10^-3 este 0,43025.

Programul pentru metoda secantei (coardei)

Programul prezentat mai jos determina 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 este definita prin procedura de tip functie.

In cadrul programului nu se verifica semnul derivatelor.

Algoritmul care sta la baza programului este urmatorul:

se determina punctul c de intersectie a dreptei determinata de punctele (a, f(a)) si (b, f(b)) cu axa Ox folosind formula

se pastreaza intervalul care contine solutia, ([a, c] sau [b, c]), care reprezinta noul interval [a, b] pentru iteratia urmatoare si se determina modulul diferentei dintre iteratia curenta (c) si iteratia anterioara (a sau b).

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 <conio .h>

# include <math .h>

double f (double x)

void main (void)

else

}

if ( t = = 0)

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

else

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

}

getch ( );

}

1.4. Metoda combinata

Se aplica la un capat metoda tangentei iar la celalalt metoda coardei. In metoda coardei se utilizeaza in unul din capete, incepand cu iteratia x_1, valoarea iteratiei obtinute in cadrul aceluiasi pas prin metoda tangentei.

Sa luam cazul

. .

. .

. .

sau

Daca oprim procedeul.

In final mai facem o data media aritmetica a rezultatelor obtinute, adica

.

Exemplu 1.4.1 Calculati cu o precizie de 0,001 radacina ecuatiei

folosind metoda combinata.

Solutie

Avem . Deci R si

iar .

Prin urmare ecuatia are o singura radacina reala si aceasta se afla in intervalul

(- ∞,(0,66666)]. Cum f (0) = -1 retinem intervalul [0, (0,66666)].

Alegem , x₀ = 0,66666.

Urmeaza

Deci solutia aproximativa calculata cu o precizie mai buna de 0,001 este

Programul pentru metoda combinata

Programul prezentat mai jos determina 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.

Algoritmul care sta la baza programului urmareste determinarea unui interval [c,d] unde c se determina prin metoda tangentei, iar d se obtine prin metoda secantei. Daca s-au putut determina cele doua puncte ( t = 0 ) atunci intervalul [min(c,d), max(c,d)] devine noul interval [a, b] pentru iteratia urmatoare.

Determinarea iteratiilor se opreste atunci cand lungimea intervalului care contine solutia este mai mica decat eroarea admisa epsilon. Solutia aproximativa este .

De asemenea programul se opreste cand se determina o valoare pentru c sau d 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)

if ( t = = 1)

if (df (b) = =0)

t = 2;

else

if (t = =0)

else

if (c<d)

else

}

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

if ( t = = 3)

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

if ( t = = 0)

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

if ( t = = 2)

cout<<"Nu se poate aplica metoda combinate!"<<endl;

}

getch ( );

}

1.5. Metoda aproximatiilor succesive

Consideram ecuatia

f (x) = 0                          (1.4)

unde f : I → R, iar I este un interval al axei reale.

Sa inlocuim ecuatia (1.4) printr-o ecuatie echivalenta de forma

         (1.5)

Definitie 1.5.1 Radacinile ecuatiei (1.5) se numesc puncte fixe ale lui φ.

Construim sirul de iteratii

, pentru n = 0, 1, 2, .,               (1.6)

unde x₀ este o valoare aproximativa initiala a radacinii care se cauta.

Teorema 1.5.1 Daca φ : [a, b] → R (a, b R, a < b) si indeplineste urmatoarele conditii:

( α ) oricare ar fi rezulta

( β ) exista q [0, 1) astfel incat oricare ar fi u₁, u₂ [a, b] este indeplinita inegalitatea

,

atunci avem:

a)     daca sirul generat de relatia (1.6) este convergent;

b)     este unica radacina a ecuatiei (1.4) pe [a, b].

Demonstratie.

a) Pentru doua iteratii consecutive si , tinand cont de relatiile ( α ) si ( β ) avem:

(1.7)

Inegalitatea (1.7) are loc pentru n = 1, 2, . si aplicand-o succesiv pentru aceste valori avem:

, ( n = 1, 2, .). (1.8)

Seria

este absolut convergenta deoarece seria valorilor absolute ale termenilor sai este majorata de o serie geometrica de ratie q < 1, asa cum rezulta din relatia (1.8).

Fie S_n+1 suma partiala de ordin n+1 a seriei de mai sus. Rezulta ca

S_n+1 = x_n

Deoarece seria este convergenta, rezulta ca si sirul sumelor partiale este convergent, adica

Din conditia ( β ) rezulta continuitatea functiei φ pe [a, b]. Deci sunt justificate urmatoarele egalitati:

,

adica verifica (1.5) si implicit pe (1.4).

Deoarece este un interval inchis, pentru n = 0, 1, 2, ., rezulta ca .

b) Aratam, prin reducere la absurd, ca ecuatia (1.5) are solutie unica.

Fie x₁, x₂ doua solutii distincte ale ecuatiei (1.5). Din relatia ( β ) avem:

Ultima inegalitate este imposibila deoarece iar 1 - q > 0 ( din ( β)).

Observatie 1.5.1 Putem inlocui conditia (β), pentru functia φ derivabila, prin inegalitatea

.

(acest fapt rezulta din teorema de medie a lui Lagrange).

Observatie 1.5.2 Teorema 1.5.1 este adevarata si pentru .

Observatie 1.5.3 Teorema 1.5.1 ne arata ca sirul dat de egalitatea (1.6) converge oricum am alege pe , adica aceasta metoda este autocorectoare.

Teorema 1.5.2 Fie R φ avand semnificatia data de relatia (1.5). Daca φ satisface conditiile:

(γ) φ este derivabila in fiecare punct

(δ) ecuatia x = φ (x) are o radacina unde iar

(η) pentru orice

(σ)

atunci avem:

a)     toate elementele sirului apartin intervalului (a, b);

b)     sirul este convergent si ;

c)      este unica solutie a ecuatiei (1.5) pe (a, b).

Demonstratie.

a)     Vom demonstra, prin inductie, ca elementele sirului apartin intervalului (a, b). Deoarece , putem calcula si avem, utilizand Teorema lui Lagrange:

,

adica .

Presupunem ca si ca . Rezulta:

,

adica pentru n = 1, 2, . .

Observatie 1.5.4 Daca , sirul aproximatiilor succesive este monoton crescator sau descrescator dupa cum .

Daca , atunci sirul este oscilant in jurul radacinii .

Teorema 1.5.3 Evaluarea erorii sirului aproximatiilor succesive.

Daca ne situam in ipotezele Teoremei 1.5.1, atunci avem

.

Demonstratie. Fie p Є N si avem

Trecand la limita pentru p → ∞, avem:

Teorema 1.5.4 Fie δ Є R, δ > 0 si f : [x₀ -δ, x₀ + δ] → R o functie derivabila pe acest interval. Daca f satisface conditia ca unde

,

atunci ecuatia f (x) = 0 are o singura radacina in intervalul [x₀ -δ, x₀ + δ].

Demonstratie. Este suficient sa demonstram acest fapt pentru f (x₀) > 0, demonstratia pentru f (x₀) < 0 fiind similara.

Deoarece m ≠ 0 rezulta ca f are acelasi semn pe [x₀ -δ, x₀ + δ], deci f este monotona pe acest interval.

Prin urmare f isi atinge marginea inferioara exacta intr-un punct care este unul din capetele intervalului.

Din teorema lui Lagrange avem:

, unde ρ Є ( x₀ -δ, x₀ + δ ).

Tinand cont de faptul ca

rezulta ca

Deoarece

si

avem

sau .

Distingem doua cazuri: 1) daca , atunci ; 2) daca si din faptul ca rezulta ca exista astfel ca . (Teorema lui Cauchy).

In incheiere dam un procedeu de trecere de la ecuatia 1.4 la ecuatia 1.5 cu respectarea conditiei .

Sa presupunem ca f este strict crescatoare pe (α , β) adica pentru Daca f este strict descrescator, aplicam acelasi procedeu pentru functia - f.

Consideram functia

unde λ Є R este un parametru real ce urmeaza a fi determinat astfel ca

Fie m₁ si M₁ doua constante astfel incat

Avem

sau tinand cont de relatia de mai sus rezulta

Deci putem alege

si

Exemplu 1.5.1 Sa se determine radacina pozitiva a ecuatiei

cu precizia .