metode numerice

77
METODE NUMERICE 1 1. Numere aproximative 1.1. Erori aproximative si erori absolute Daca A este valoarea exacta a unei cantitati si a este o aproximatie cunoscuta a acesteia, atunci eroarea absoluta a aproximatiei a se considera de obicei a fi marimea a care satisface relatia (1.1) Pentru scopuri practice este convenabil sa se ia pentru a valoarea cea mai mica pentru care este satisfacuta inegalitatea de mai sus sub circumstantele date.. Numarul exact A poate si scris atunci (1.2) Eroarea relativa a a unui numar aproximativa este egala cu raportul dintre eroarea absoluta a a numarului si valorea sa absoluta: (1.3) Uneori, eroarea relativa se defineste ca raportul A a , cu A valoarea exacta insa necunoscuta. Introducand a din (1.3) in (1.2), rezulta limite pentru numarul exact A: (1.4) Exemplu: Fie numarul aproximativ a = 3.14, utilizat in locul numarului exact π = A . Avand in vedere ca 3.14 < π < 3.15, rezulta ca 01 . 0 a < π - si se poate lua eroarea absoluta a =0.01. Corespunzator avem eroarea relativa a δ = 0.01/3.14 = 0.003 si deci putem scrie π = 3.14(1 ± 0.003). a A a - a a A ± = ) 0 a ( a a a = δ ) 1 ( a A a δ ± =

Upload: nanaciteste

Post on 28-Oct-2015

205 views

Category:

Documents


6 download

DESCRIPTION

exercitii

TRANSCRIPT

Page 1: Metode Numerice

METODE NUMERICE

1

1. Numere aproximative

1.1. Erori aproximative si erori absolute

Daca A este valoarea exacta a unei cantitati si a este o aproximatie cunoscuta aacesteia, atunci eroarea absoluta a aproximatiei a se considera de obicei a fi marimea

a∆ care satisface relatia

(1.1)

Pentru scopuri practice este convenabil sa se ia pentru a∆ valoarea cea maimica pentru care este satisfacuta inegalitatea de mai sus sub circumstantele date..Numarul exact A poate si scris atunci

(1.2)

Eroarea relativa a∂ a unui numar aproximativa este egala cu raportul dintre

eroarea absoluta a∆ a numarului si valorea sa absoluta:

(1.3)

Uneori, eroarea relativa se defineste ca raportul Aa∆

, cu A valoarea exacta insa

necunoscuta. Introducand a∆ din (1.3) in (1.2), rezulta limite pentru numarul exactA:

(1.4)

Exemplu:

Fie numarul aproximativ a = 3.14, utilizat in locul numarului exact π=A .

Avand in vedere ca 3.14 < π < 3.15, rezulta ca 01.0a <π− si se poate lua eroarea

absoluta a∆ =0.01.

Corespunzator avem eroarea relativa aδ = 0.01/3.14 = 0.003 si deci putem

scrie π = 3.14(1 ± 0.003).

aAa ∆≤−

aaA ∆±=

)0a(aa

a ≠∆

)1(aA aδ±=

Page 2: Metode Numerice

METODE NUMERICE

2

1.2. Sursele si clasificarea erorilor

Erorile care apar în rezolvarea numeric a problemelor matematice se împart, înesen , în cinci categorii: erori de problema, erori de metod , erori ini iale, erori derotunjire i erori de trunchiere.

Erorile de problem sunt cauzate de faptul c nu totdeauna formularea matematicdescrie exact procesul modelat, deoarece de multe ori, pentru a reduce complexitateaformul rii, suntem forta i s accept m conditii simplificatoare.

Erorile de metod se datoreaz faptului c uneori este dificil , dac nu chiarimposibil rezolvarea formul rii exacte a problemei. In aceste cazuri, problema esteînlocuit cu o problem aproximativ , pentru care exist tehnici adecvate de rezolvaresi care are un rezultat foarte apropiat. Metodele numerice sunt în majoritateacontextelor în care sunt utilizate metode de aproximare.

Erorile initiale (inerente) sunt erori în valorile datelor, cauzate de incertitudini însur tori sau de natura inerent aproximativ a reprezent rii numerelor cu ajutorul

unui num r finit de cifre.

Erorile de rotunjire sunt cauzate de reprezentarea numerelor (date ini iale saurezultate ale unor calcule) cu un num r finit de cifre semnificative exacte.

De exemplu:reprezentarea rezultatului opera iei 1/3 sub forma 0.333 implic o eroare de

trunchiere de aproximativ 3x10-4. Erorile de rotunjire depind de particularit ilehardware ale calculatorului, de modul de reprezentare intern al diferitelor tipuri dedate utilizate în calcule. Erorile de rotunjire se acumuleaz prin cre terea num rului decalcule, mai ales al celor care implic sc derea unor valori aproximativ egale.

Erorile de trunchiere (reziduale) provin din natura infinit a unor procese utilizateîn descrierea solutiei problemelor matematice. Faptul c , practic, aceste procesetrebuie întrerupte dup un num r finit de paji, introduce o eroare de trunchiere.Considerand exemplul dezvolt rii func iilor în serie, însumarea trebuie întrerupt la unanumit termen, trunchiind seria i introducand o anumit eroare de trunchiere.

Metodele numerice permit, în principiu, controlul erorilor de rotunjire i al celorde trunchiere, cu condi ia transcrierii adecvate a algoritmului. Astfel, în cazul erorilorde rotunjire, trebuie considerat acea form a expresiilor matematice, în care suntevitate operatiile care introduc acest tip de erori. In ceea ce prive te erorile detrunchiere, acestea se afl sub controlul deplin al programatorului, care îns trebuie sfie preocupat de construirea unor algoritmi fini i i eficien i. Dac finitudineaalgoritmului este obligatorie pentru convergenta rezultatelor, eficienta este o reflectaredirect a experien ei i stilului de programare.

Page 3: Metode Numerice

METODE NUMERICE

3

1.3 Reprezentarea numerelor. Cifre semnificative exacte.

Orice num r pozitiv poate fi reprezentat în baza 10 sub forma

ΚΚ +•α++•α+•α= +−+−

−−

1nm1nm

1m1m

mm 101010a (1.5)

unde iα , sînt cifrele num rului a, cu 0m ≠α .

De exemplu:

314.15 = 3*102 + 1*101 + 4*100 + 1*10-1 + 5*10-2.

Situa iile concrete implic utilizarea unor numere aproximative cu un num r finitde cifre. Toate cele n cifre zecimale re inute iα , i = m, m-1, . . ., m-n+1 , se numesccifre semnificative. Unele dintre cifrele semnificative pot fi egale cu zero, cu excep iaprimei cifre, mα .

De exemplu, în num rul 0.00208 = 0*10-3 + 0*10-4 + 8*10-5, primele treizerouri nu sunt cifre semnificative, deoarece ele servesc numai pentru fixarea pozi ieipunctului zecimal în scrierea zecimal a num rului.

Defini ie. Spunem c un num r aproximativ a are n cifre semnificative exacte,1nm1mm ,,, +−− ααα Κ dac , eroarea absolut a num rului nu dep este jum tate de

unitate în pozi ia n , num rand de la stînga la dreapta, adic

(1.6)

De exemplu, num rul a = 36.00 este în raport cu num rul exact A = 35.97 oaproxima ie cu trei cifre semnificative exacte. Intr-adev r, avînd în vedere ca |a - A|=0.03 < 1/2*10-1, rezult m-n+1 = -1, de unde n=3 (m=1).

Termenul "n cifre semnificative exacte" nu trebuie luat ad literam, deoarece nueste obligatoriu ca într-un num r aproximativ a avînd n cifre exacte, primele n cifresemnificative coincid cu cifrele corespunz toare ale num rului exact A. Deexemplu, num rul a = 9.995 este o aproxima ie cu trei cifre corecte a num rului exactA=10 i totu i are toate cifrele diferite.

Teorem . Dac un num r pozitiv a are n cifre exacte, eroarea relativ aδ a acestuinum r satisface inegalitatea

(1.7)

1nma 10

21 +−•≤∆

)1n(

ma 10

21 −−•α

≤δ

Page 4: Metode Numerice

METODE NUMERICE

4

unde mα este prima cifr semnificativ a num rului a.

Intr-adev r,

)1n(

m1m1m

mm

1nma

a 102

1

1010

10)2/1(a

−−−

+−•

α≤

+•α+•α

•≤

∆=δ

Κ

Num rul de cifre semnificative exacte corespunz tor unei erori relative aδ dateeste conform relatiei (1.7).

(1.8)

De exemplu, num rul aproximativ a = 3.15, utilizat în locul num rului exact

A= π , are n <= 2.72 , adic dou cifre exacte.Num rul aproximativ a = 3.14 va avea n <= 3.29, adic trei cifre exacte.

Pentru num rul de cifre semnificative exacte, se poate ob ine o estimaregrosier îns foarte util în practic , considerînd c eroare relativ are forma

pa 10−≈δ si 5m ≈α :

(1.9)

Acest criteriu poate fi utilizat în situa iile în care, cunoscîndu-se eroarea relativa unui num r, se impune estimarea rapid îns nu neap rat foarte precis a num ruluide cifre exacte ale acestuia.

1.4 Erori ale operatiilor elementare

1.4.1 Eroarea sumei

Teorem . Eroarea absolut pentru suma algebric a mai multor numereaproximative nu dep te suma erorilor absolute ale numerelor.

Intr-adev r, considerînd suma algebric a numerelor aproximative a1, a2, . . . ,an :

n21 aaaa ±±±±= Κ

avem în mod evident

)2(log1n ma10 αδ−≤

pn ≈

Page 5: Metode Numerice

METODE NUMERICE

5

n21 aaaa ∆±±∆±∆±=∆ Κsi deci,

n21 aaaa ∆++∆+∆≤∆ Κ

Pentru eroarea absolut a sumei avem, prin urmare,

na2a1aa ∆++∆+∆≤∆ Κ (1.10)

iar pentru eroarea absolut limit ,

na2a1aa* ∆++∆+∆=∆ Κ (1.11)

Din aceast relatie rezult c eroarea absolut limit nu poate fi mai mic decateroarea absolut a celui mai pu in exact termen din sum

),,,max( na2a1aa* ∆∆∆≥∆ Κ (1.12)

In consecint , ceilal i termeni, cu grad de precizie mai mare (cu erori absolutemai mici) nu pot ameliora precizia rezultatului.

Teorem . Dac toti termenii unei sume au acela i semn, eroarea relativ (limit ) asumei nu dep te cea mai mare eroare relativ a termenilor.

1.4.2 Eroarea diferen ei

Consider m diferen a a doua numere aproximative a = a1 – a2

Conform rela iei (1.11), eroarea absolut limit a diferen ei este egal cu suma erorilorabsolute ale celor doi termeni

2a1aa* ∆+∆=∆

si eroarea relativ limit a diferen ei va fi

21

2a1aa*

a*

AAA −

∆+∆=

∆=δ

unde A este valoarea exact a modulului diferen ei.

Page 6: Metode Numerice

METODE NUMERICE

6

Dac numerele aproximative a1 i a2 sunt foarte apropiate ca valoare, atunci

diferen a exact A este mic i, chiar în condi iile în care erorile relative 1aδ i 2aδ

sunt mici, eroarea relativ limit a diferen ei, a*δ , poate fi foarte mare.

Pentru a exemplifica cele ar tate mai sus, consider m numerele aproximativea1=47.132 i a2=47.111 , fiecare avînd cinci cifre semnificative exacte, adic o eroareabsolut de cel mult 0.0005. Diferen a a=47.132 -47.1 11 = 0.021 are doar dou cifresemnificative exacte, iar eroarea absolut limit a diferen ei este

a*∆ =0.0005+0.0005 =0.001

si vom avea urm toarele erori relative limit

00001.0132.47

0005.01a ≈=δ , 00001.0

111.470005.0

2a ≈=δ , 05.0021.0001.0

a* ≈=δ

Dup cum se observ , eroarea relativ limit a diferen ei este de aproximativ5000 de ori mai mare decat erorile relative ale termenilor. Este de aceea de dorit, ca încalcule numerice s se rescrie expresiile care implic sc derea unor numereaproximativ egale.

Page 7: Metode Numerice

METODE NUMERICE

1

2. Rezolvarea numeric a ecua iilor algebrice i transcendente

Exist numeroase situa ii în care avem de rezolvat ecua ii polinomiale saunepolinomiale (transcendente) cu o singur variabil de forma 0=)x(f ale c ror solu ii nu sepot determina prin metodele algebrice cunoscute. Pentru rezolvarea acestor ecua ii estenecesar mai întâi s se identifice printr-o anumit metod intervalele în care se afl exact o

cin a ecua iei.Pentru ca ecua ia s aib o solu ie în acest interval [ ]b,a este necesar ca func ia )x(f

fie continu , strict monoton , adic )x(f ′ s aib acela i semn pe intervalul [ ]b,a i func ia prezinte schimbarea de semn: 0<⋅ )b(f)a(f . Aceste condi ii pentru determinarea solu iilor

sunt echivalente cu urm toarele ipoteze:Ø [ ] Rb,a:f → este o func ie continu i derivabil (func ie Rolle);

Ø

<>><

<⋅0000

0)b(f,)a(f)b(f,)a(f

)b(f)a(f ;

Ø )x(f are numai o singur solu ie pe [ ]b,a .

Metodele cele mai utilizate în calculul numeric aproximativ al solu iilor unei ecua ii caresatisface ipotezele de mai sus sunt:1. Metoda înjum irii intervalului (bisec iei);2. Metoda coardei (secantei);3. Metoda tangentelor de ordinul I (Newton Raphson);4. Metoda tangentelor de ordinul II (Newton)5. Metoda parabolelor (Blumenfeld)6. Metoda iterativ : x=g(x)

Pentru extragerea r cinii de ordinul k dintr-un num r N se poate folosi una din metodelelui Newton (tangentelor de ordinul I sau II).

În continuare sunt prezentate aceste metode i modul de aplicare al lor pentru unexemplu concret.

2.1. Metoda înjum irii intervalului (bisec iei)

Este cea mai simpl metod de determinare a r cinii unei ecua ii 0=)x(f care seafl în intervalul [ ]b,a . Pentru aplicarea acestei metode se verific dac :

Ø [ ] Rb,a:f → este o func ie continu i derivabil ;

Ø 0<⋅ )b(f)a(f

Metoda înjum irii intervalului sau a bisec iei se bazeaz pe urm torul algoritm:1. se calculeaz valoarea func iei f(x) la capetele intervalului i într-un punct situat la mijlocul

intervalului:2

bacx +==

Page 8: Metode Numerice

METODE NUMERICE

2

2. Se verific semnele func iei în cele trei puncte ale intervalului (a, c, b) i subintervalul încare func ia prezint schimbarea de semn; acest subinterval este noul interval în care afl

cina. Sunt posibile urm toarele variante prezentate în tabelul urm tor :

Tabelul 1F(a) f(b) f(c) cina ξ

- + + ( )c,a∈ξ

- + - ( )b,c∈ξ

+ - + ( )b,c∈ξ

+ - - ( )c,a∈ξ

Pentru noul interval se procedeaz analog calculând valorile func iei la capele lui i lamijloc, din semnele func iei în cele trei puncte rezultând subintervalul pentru care are locschimbarea de semn;

Procesul este iterativ i se încheie atunci când se ob ine o eroare mai mic decâtprecizia impus r cinii : ε<− ba

Exemplu se afle r cina ecua iei algebrice:

0143 2 =−−+ xxxln ,cu o eroare mai mic de 0,02 tiind c se afl în intervalul [ ]21,

Pentru determinarea solu iei ecua iei se aplic algoritmul prezentat mai sus: rezultvalorile din tabelul 2: Tabelul 2

Nr a c b f(a) f(c) f(b)1. 1 1,5 2 -2 0,155465 3,693

2. 1 1,25 1,5 -2 -1,089 0,1554653. 1,25 1,375 1,5 -1,089 -0,50967 0,155465

4. 1,375 1,4375 1,5 -0,50967 -0,1878 0,1554655. 1,4375 1,46875 1,5 -0,1878 -0,0189 0,1554656. 1,46875 1,484375 1,5 -0,0189 0,0676 0,155465

7. 1,46875 1,4765625 1,484375 -0,0189 0,0241772

Se observ din rezultatele ob inute c aceast metod este slab convergent . Solu iaaproximativ a ecua iei este ξ=1,4765625 calculat cu o eroare: ε = 1,4765625-1,46875=0,0078125

x=a

x

yy=f(x)

O

Fig. 1

21ba

c+

=

x=b

211

2bac +

=

Page 9: Metode Numerice

METODE NUMERICE

3

Implementare in C++:

/*

Rezolvarea numerica a ecuatiilor algebrice si transcedentale

1. Metoda bisectiilor (metoda injumatatirii)

*/#include<iostream.h>#include<conio.h>#include<math.h>#include<stdlib.h>

float a,b,c,eps;int i,n;

float functie(float x) return ( log(x) + 3*x*x - 4*x - 1);void bisectie(float a, float b) if( ( functie(a) < 0 ) && ( functie(b) > 0) ) n=ceil(log((b-a)/eps)/log(2))+1;// cout<<"Tabelul cu aproximarile succesive"<<endl;// cout<<"| a | c | b | f(a) | f(c) | f(b) |"<<endl; for(i=1;i<=n;i++) c=(a+b)/2; if( functie(c) < 0) a=c; else b=c;// cout<<"-------------------------------------------------------"<<endl;//cout<<"|"<<a<<"|"<<c<<"|"<<b<<"|"<<functie(a)<<"|"<<functie(c)<<"|"<<functie(b)<<"|"<<endl;// getch(); cout<<"solutia : "<<c<<endl; else cout<<"Nu se incadreaza in ipoteza f(a)<0 si f(b)>0"; return;

void main(void) clrscr(); cout<<" a = ";cin>>a; cout<<" b = ";cin>>b; cout<<"Dati precizia de calcul eps = ";cin>>eps; bisectie(a,b); getch();

Page 10: Metode Numerice

METODE NUMERICE

4

2.2. Metoda coardei sau secantei

Fie o func ie continu i derivabil f(x) având pe intervalul [a, b] o singur r cin( )b,a∈ξ . Deoarece 0<⋅ )b(f)a(f , se poate aproxima r cina cu abscisa punctului de

intersec ie a coardei (secantei) care trece prin punctele A(a, f(a)) i B(b, f(b)) cu axa Ox (fig.1.2.1). Ecua ia acestei coarde este:

( )ab

)a(f)b(fax)a(fy

abax

)a(f)b(f)a(fy

−−

−=−

⇔−−

=−

Pentru primul interval [a,b] se poate scrie aceast abscis astfel :

)a(f)b(fab)a(fax

−−

−=1

Dac 01 <⋅ )x(f)a(f atunci noul subinterval [a,x1] va cuprinde solu ia ecua iei.Procedeul de aproximare se repet în acela i mod pentru noul subinterval. Presupunând cpentru subintervalul [xn-1, xn] este îndeplinit condi ia:

01 <⋅− )x(f)x(f nn ,

atunci pentru determinarea solu iei aproximative xn+1 este valabil rela ia de recuren ametodei coardei sau secantei:

)x(f)x(fxx)x(fxx

nn

nnnnn

1

11

−+ −

−−=

Din punct de vedere geometric determinarea solu iei aproximative se realizeaz cuajutorul intersec iilor succesive ale secantelor la graficul func iei f(x) cu axa Ox , duse prinpunctele:Ø An+1[xn+1, f(xn+1)] , An[(xn, f(xn)] pentru cazul 01 <⋅+ )x(f)x(f nn , respectiv

Ø An-1[xn-1, f(xn-1)] , An[xn, f(xn)], pentru cazul 01 <⋅− )x(f)x(f nn .

Exemplu

se afle r cina ecua iei algebrice: 0143 2 =−−+ xxxln , cu o eroare 020,≤ε tiind se afl în intervalul [ ]21, .

Pentru ecua ia de mai sus se aplic rela ia de recuren (1.2.3) care conduce succesivla valorile din tabelul 3:

x=a

xx2

y

y=f(x)

O

Fig.1.2.1

x1

x=bξ

A

B

Page 11: Metode Numerice

METODE NUMERICE

5

Tabelul 3Pas xn-1 xn xn+1 f(xn-1) f(xn) f(xn+1)1. 1.000000 2.000000 1.351300 -2.000000 3.693147 -0.6261002. 1.351300 2.000000 1.445332 -0.626100 3.693147 -0.1460333. 1.445332 2.000000 1.466431 -0.146033 3.693147 -0.0316354. 1.466431 2.000000 1.470962 -0.031635 3.693147 -0.0067425. 1.470962 2.000000 1.471926 -0.006742 3.693147 -0.0014326. 1.471926 2.000000 1.472131 -0.001432 3.693147 -0.0003047 1.472131 2.000000 1.472174 -0.000304 3.693147 -0.0000648 1.472174 2.000000 1.472184 -0.000064 3.693147 -0.000014

Se observ c i aceast metod este slab convergent .Deci solu ia aproximativ a ecua iei calculat prin metoda coardei sau secantei este:

ξ=1, 47176 cu o eroare ε = 0,02824 .

Implementare in C++:

Sa se determine solutia ecuatiei 05x7x5 =++ continuta in intervalul [-1,0].

Se observa cu usurinta ca metoda se poate aplica functiei f :[-1,0]->R, f(x)=x5+7x+5. Derivatafunctiei f este f’(x)=5x4+7, deci valoarea minima, respectiv maxima a modulului derivatei peintervalul [-1,0] este 7 (notam cu m1) si 12 (notam cu m2).

/*

Rezolvarea numerica a ecuatiilor algebrice si transcedentale

2. Metoda coardei (metoda secantei) varianta cu estimarea erorii*/#include<iostream.h>#include<conio.h>#include<math.h>#include<stdlib.h>

float a,b,cn,cn_1,eps,m1,m2;int i;

float functie(float x) return ( log(x) + 3*x*x - 4*x + 1 );void coarda(float a, float b, float eps) m1=4;m2=9.5; i=1; cn_1=a; cn=(a*functie(b) - b*functie(a))/(functie(b)-functie(a)); while(fabs(cn-cn_1)*m2/m1 > eps) cn_1=cn;

Page 12: Metode Numerice

METODE NUMERICE

6

if( functie(cn) < 0) a=cn; else b=cn; i++; cout<<cn<<" an = "<<a<<" bn = "<<b<<" iteratia = "<<i<<endl; cn=(a*functie(b) - b*functie(a))/(functie(b)-functie(a)); return;

void main(void) clrscr(); cout<<" a = ";cin>>a; cout<<" b = ";cin>>b; cout<<"Dati precizia de calcul eps = ";cin>>eps; coarda(a,b,eps); getch();

Page 13: Metode Numerice

METODE NUMERICE

1

3. Rezolvarea numeric a ecua iilor algebrice i transcendente

3.1. Metoda tangentelor de ordinul I(sau prima metod a lui Newton sau Newton-Raphson)

Fie o func ie continu i derivabil f(x) pe intervalul [a, b], care satisfacecondi ia 0<⋅ )b(f)a(f i are o singur r cin pe intervalul [a, b].

Dac se dezvolt în serie Taylor func ia f(x) în jurul punctului x=a se ob ine:

( ) ( ) ( ) ( ) ( ) ...af!axaf

!axafxf +′′−

+′−+=

21

2 (3.1)

Re inând doar primii doi termeni ai dezvolt rii (3.1) se ob ine o rela ie aproximativ decalcul a lui f(x) în func ie de f(a) i f’(a):

( ) ( ) ( ) ( ) ( ) ( ).bf!bxbfxfsauaf

!axafxf ′−

+≅′−+≅

11 (3.2)

Aceast func ie reprezint tangenta la graficul func iei f(x) în punctul A[a, f(a)]respectiv în punctul B[b, f(b)], conform figurii 3.1. Punând condi ia ( ) 0=xf se ob ineintersec ia cu axa Ox i rezult o solu ie aproximativ de forma:

( )( )

( )( )

( )( )

( )( )bfbfbx

bfbfbx:sau

afafax

afafax

′−=⇒

′−=−

′−=⇒

′−=−

2

1

(3.3)

Alegerea lui a sau b trebuie s se fac astfel încât s nu se ob in o valoare a lui x2 înafara intervalului [a, b] a a cum rezult din figura 3.3 pentru x1=a.

Folosind aceast rela ie rezult formula de recuren a metodei tangentelor deordinul I (prima formul a lui Newton sau Newton-Raphson):

( )( )n

nnn xf

xfxx′

−=+1 (3.4)

a

xx2

y

y=f(x)

O

Fig.1.3.1

b

x3x4

A

B

x1

Page 14: Metode Numerice

METODE NUMERICE

2

Exemplu se afle r cina ecua iei algebrice: 0143 2 =−−+ xxxln , cu o eroare mai mic de

0,00001 tiind c se afl în intervalul [ ]21, .

Dac not m 143 2 −−+= xxxln)x(f , atunci derivata func iei )x(f este:

461−+=′ x

x)x(f (3.5)

Pentru determinarea solu iei aproximative prin metoda Newton Raphson se aplicrela ia de recuren (3.4) i se ob in succesiv valorile din tabelul 3.1

Tabelul 3.1Pas xn f(xn) f '(xn) xn+1 f(xn+1)1. 2 3.693147 8.5 1.565512 0.5386492. 1.565512 0.538649 6.031841 1.476211 0.0222323. 1.476211 0.022232 5.534677 1.472194 4.47E-054. 1.472194 4.47E-05 5.512424 1.472186 1.82E-10

Se observ c aceast metod este rapid convergent .O solu ie aproximativ a ecua iei este ξ=1, 472186 calculat cu o eroare ε =0,00001.

Aplicatie:

Se considera ecuatia x – sin x – 0.25 = 0. Vom construi trei functii:1. Functia denumita functie() care returneaza functia pentru care aproximam solutia intr-unanumit interval.2. Functia denumita deriv() care returneaza derivata functiei date.3. Functia denumita newton() care aplica metoda lui Newton asupra functiei date.In aceasta functie consideram in numar dat de iteratii, in variabila imax, o eroare notata eps,variabilele dx pentru functia data si df pentru derivata corespunzatoare.

Valoarea initiala a lui x va fi 0, iar dupa mai multe iteratii vom obtine valoareaarpoximativa a lui x = 1.7123.

Implementare in C++

#include<stdio.h>#include<iostream.h>#include<math.h>#include<stdlib.h>#include<conio.h>float x,dx;

float functie(float x) return(x - sin(x) - 0.25);float deriv(float x) return(1 - cos(x));

Page 15: Metode Numerice

METODE NUMERICE

3

void newton(float x, float dx) float eps=0.0000000001; int imax = 25; float f,df; int i; i=0; do i=i+1; dx=functie(x); df=deriv(x); if(abs(df) >eps) dx = dx/df; x = x - dx; if(x!=0) dx = dx / x; cout<<x<<" dx "<<dx<<" iteratia i = "<<i<<endl; while( abs(dx<=eps) && i<=imax ); return;int main(void) clrscr(); cout<<"dati x = "; cin>>x; newton(x,dx);

getch();

3.2. Metoda iterativ x=g(x)(metoda aproximatiilor successive, metoda contractiilor)

Fie o func ie continu i derivabil f(x) pe intervalul [a, b]. Deoarece 0<⋅ )b(f)a(f ,presupunem c ecua ia f(x)=0 are o singur r cin ( )b,a∈ξ . O r cin aproximativ aecua iei f(x)=0 se poate ob ine dac aceasta se poate scrie o rela ie de recuren echivalentx=g(x). Aceast metod nu conduce întotdeauna la rela ii iterative convergente.

Rela ia de recuren a metodei se scrie:

xn+1=g(xn) (3.2.1)

Exemplul 1

se g seasc r cina ecua iei: 0143 4 =−+ xx , cu o precizie de 0,001 dac se aflîn intervalul (0, 1).

1430143 34 =+⇔=−+ )x(xxx (3.2.2)

Page 16: Metode Numerice

METODE NUMERICE

4

Dac se consider 43 3 += x)x(g atunci ecua ia (3.2.2) se scrie sub forma echivalent :

4313 +

=x

x (3.2.3)

Cu ajutorul rela iei(1.6.3) se ob ine rela ia de recuren :

431

31+

=+n

n xx (3.2.4)

Plecând de la x1=0 avem succesiv valorile din de mai jos:Pas xn xn+1

1. 0 0,25

2. 0,25 0,2471

3. 0,2471 0,2472

Se observ c aceast metod este rapid convergent .

O solu ie aproximativ a ecua iei calculat cu o eroare ε = 0,0001 este: ξ=0,22472

Exemplul 2

se g seasc r cina ecua iei: 014 =−− xx (1.6.5)cu o precizie de 0,001 dac se afl în intervalul (1, 2).

Dac 4 1 x)x(g += atunci ecua ia de mai sus se scrie: 4 1 xx +=

Se ob ine deci rela ia de recuren : 41 1 nn xx +=+ (1.6.6)

Plecând de la x1=1 avem succesiv valorile din tabelul 1.6.2:

Pas xn xn+1 Tabelul 1.6.21. 1 1,1892

2. 1,1892 1,21638

3. 1,21638 1,220145

4. 1,220145 1,22066

Se observ c aceast metod este rapid convergent .O solu ie aproximativ a ecua iei calculat cu o eroare ε = 0,00052 este: ξ=1,2206.

Aplicatie:

Se considera ecuatia x – sin x – 0.25 = 0. Vom construi doua functii:1. Functia denumita functie() care returneaza functia pentru care aproximam solutia intr-unanumit interval.2. Functia denumita contractii() care aplica metoda contractiilor (aproximarilor succesive)asupra functiei date.

In aceasta functie consideram in numar dat de iteratii, in variabila imax, o eroarenotata eps, variabila dx pentru functia data.

Valoarea initiala a lui x va fi 0, iar dupa mai multe iteratii vom obtine valoarea

Page 17: Metode Numerice

METODE NUMERICE

5

aproximativa a lui x = 1.7123.

Implementare in C++

#include<stdio.h>#include<iostream.h>#include<math.h>#include<stdlib.h>#include<conio.h>float x,dx;int zero;

float functie(float x) return(x - sin(x) - 0.25);

void contractii(float x, float dx, int zero) float eps=0.0000000001; int imax = 25; float f; int i; i=0; zero=1; do i=i+1; dx=functie(x); x = x - dx; if(x!=0) dx = dx / x; cout<<x<<" dx "<<dx<<" iteratia i = "<<i<<endl; while( abs(dx<=eps) && i<=imax ); return;int main(void) clrscr(); cout<<"Dati x = "; cin>>x; contractii(x,dx,zero); if( zero==1 ) cout<<"x = "<<x<<" dx = "<<dx; getch();

Page 18: Metode Numerice

METODE NUMERICE

1

4. Rezolvarea sistemelor de ecua ii algebrice liniare

Metodele de rezolvare a sistemelor de ecuatii liniare, se pot imparti in douacategorii:

1. Metode exacte(directe) – care sunt algoritmi finiti pentru calculul solutiilorsistemelor de ecuatii liniare:Ø Metoda lui Cramer, bazata pe calculul determinantilorØ Metoda eliminarilor succesive (metoda lui Gauss)

2. Metode iterative – care permit gasirea solutiei sistemelor liniare cu o anumitaprecizie, intr-un numar finit de pasi:Ø Metoda lui JacobiØ Metoda Gauss-Seidel

4.1.1. Metoda lui Cramer

Consideram urmatorul sistem de n ecuatii liniare cu n necunoscute :

Conform notiunilor de algebra din liceu, daca un sistem liniar cu n ecuatii si nnecunoscute are determinantul principal nenul, atunci el are solutie unica, determinatprin regula lui Cramer, si anume :

unde, se obtin prin inlocuirea in ∆ a coloanei corespunzatoarenecunoscutei xi, prin coloana termenilor liberi. Rezolvarea efectiva a sistemului de n ecuatii cu n necunoscute se face princalculul a n +1 determinanti.

Deci, trebuie sa construim un algoritm de calcul numeric al determinantilor :Sa presupunem, de exemplu, ca avem un determinant de ordin 3, in forma

generala :

=++++

=++++=++++=++++

nnnn33n22n11n

3nn3333232131

2nn2323222121

1nn1313212111

bxaxaxaxa

bxaxaxaxabxaxaxaxabxaxaxaxa

ΚΚΚΚΚΚΚΚΚΚΚΚ

ΚΚΚ

∆= 1x

1x∆

∆= 2x

2x∆

∆= nx

nxΚΚΚ

nx2x1x ,,, ∆∆∆ Κ

Page 19: Metode Numerice

METODE NUMERICE

2

Daca elementul a11 este diferit de zero, atunci cautam sa ajungem la undeterminant care sa contina pe prima coloana numai pe zero, cu exceptia elementuluia11. Acesta se poate obtine succesiv inmultind prima linie cu

11

21aa

− si adunand rezultatul

la linia a doua. De asemenea inmultind prima linie cu11

31aa

− si adunand la linia a treia se

ajunge la un determinant, cu aceeasi valoare ca cel initial, dar care are pe primacoloana un singur element nenul. Deci determinatul devine :

In continuare, daca '22a este diferit de zero, putem, fara a afecta valoarea

determinatului, sa inmultim linia a doua cu'22

'32

a

a− si sa adunam la a treia; vom obtine :

Evident valoarea acestui determinant este egala cu 11a '22a ''

33a .

Inainte, de a generaliza acest procedeu, trebuie sa vedem ce se intampla daca,de exemplu, la primul pas, a11=0.

ü In aceasta situatie, daca pe prima coloana toate elementele sunt nuleatunci determinantul este zero.

ü Daca exista, totusi un element nenul pe prima coloana, atunci putempermuta linia care contine acel element nenul, cu prima linie. Obtinem unnou determinant, avand semnul schimbat fata de cel anterior.

Procedeul poate fi aplicat in continuare ca mai sus, cu singura observatie cadeterminantul isi schimba semnul de fiecare data cand se efectueaza o permutare dedoua linii.

In, general, pentru calculul unui determinant de ordin n putem folosi metoda demai sus. Astfel, avem :

333231

232221

131211

aaaaaaaaa

'33

'32

'23

'22

131211

aa0

aa0

aaa

''33

'23

'22

131211

a00

aa0

aaa

Page 20: Metode Numerice

METODE NUMERICE

3

Pentru rezolvarea sistemului de n ecuatii cu n necunoscute vom construi ofunctie de calcul a determinantului conform metodei de mai sus, pe care o vom apela,prima data pentru calcului determinantului principal al sistemului ( ∆ ), si apoi de n oripentru calculul celor n determinanti corespunzatori celor n necunoscute :

Solutia in limbajul C++ :

#include<iostream.h>#include<conio.h>#include<stdlib.h>float a[10][10],b[10],x[10],save[10],dp;int i,j,n;

float determinant(float a[10][10], int n) int i,j,k,l,t,iv; float temp,d=1; for(j=1;j<=n-1;j++) iv=j; t=1; while( (iv<=n) && (t==1) ) if(a[iv][j] == 0) iv=iv+1; else t=0; if(t==1) return 0; if(j!=iv) d=-d; for(k=j;k<=n;k++) temp=a[j][k]; a[j][k]=a[iv][k]; a[iv][k]=temp; for(l=j+1;l<=n;l++) for(k=j+1;k<=n;k++) a[l][k]=a[l][k] - a[j][k] * a[l][j] / a[j][j]; for(j=1;j<=n;j++) d=d*a[i][j]; return d;

nn3n2n1n

n3333231

n2232221

n1131211

aaaa

aaaaaaaaaaaa

ΚΚΚΚΚΚ

ΚΚΚ

nx2x1x ,,, ∆∆∆ Κ

Page 21: Metode Numerice

METODE NUMERICE

4

void main(void) clrscr(); cout<<"Dati numarul de ecuatii ";cin>>n; cout<<"Dati matricea A "<<endl; for(i=1;i<=n;i++) for(j=1;j<=n;j++) cout<<"a["<<i<<"]["<<j<<"]= "; cin>>a[i][j]; cout<<"Dati termenul liber"<<endl; for(i=1;i<=n;i++) cout<<"b["<<i<<"]= "; cin>>b[i];

dp=determinant(a,n); if(dp==0) cout<<"Nu se poate rezolva cu regula lui Cramer"<<endl; exit(0); for(j=1;j<=n;j++) for(i=1;i<=n;i++) save[i]=a[i][j]; a[i][j]=b[i]; x[j]=determinant(a,n) / dp; cout<<x[j]<<endl; for(i=1;i<=n;i++) a[i][j]=save[i];

4.1.2. Metoda eliminarilor succesive (metoda lui Gauss)

Metoda eliminarilor succesive porneste de la o observatie foarte simpla facutaasupra metodei de calcul a determinantilor, prezentata anterior. Este vorba de faptulca daca folosim asa numita metoda a reducerii, prin eliminarea necunoscutei x1, dinecatiile 2,3,…,n nu facem altceva decat sa aplicam primul pas din procedeul de calculal determinantilor. Astfel, daca sistemul urmator este compatibil si determinat (adicadeterminantul principal este nenul) :

=++++

=++++=++++=++++

nnnn33n22n11n

3nn3333232131

2nn2323222121

1nn1313212111

bxaxaxaxa

bxaxaxaxabxaxaxaxabxaxaxaxa

ΚΚΚΚΚΚΚΚΚΚΚΚ

ΚΚΚ

Page 22: Metode Numerice

METODE NUMERICE

5

Atunci, se transforma intr-un sistem echivalent, de forma :

Daca, iteram, procesul, eliminand necunoscutele xi, din ecuatiile i+1, …, n (undei = 2, …, n-1 ), vom obtine in final un sistem de forma :

Acest sistem, numit sistem triunghiular superior, se poate rezolva, incepandcu valoarea lui xm care se determina din ultima ecuatie. Cu xn, cunoscut de determinaxn-1 din penultima ecuatie, s.a.m.d.

Solutia in limbajul C++, se aseamana foarte mult cu cea de la metoda luiCramer, doar ca cateva mici modificari :

#include<iostream.h>#include<conio.h>#include<stdlib.h>float a[10][10],b[10],x[10],dp;int i,j,n,iv,t,k,l;float temp;

void main(void) clrscr(); cout<<"Dati numarul de ecuatii ";cin>>n; cout<<"Dati matricea A "<<endl; for(i=1;i<=n;i++) for(j=1;j<=n;j++) cout<<"a["<<i<<"]["<<j<<"]= "; cin>>a[i][j]; cout<<"Dati termenul liber"<<endl; for(i=1;i<=n;i++) cout<<"b["<<i<<"]= "; cin>>b[i];

=+++

=+++=+++=++++

nnnn33n22n

3nn3333232

2nn2323222

1nn1313212111

bxaxaxa

bxaxaxabxaxaxabxaxaxaxa

ΚΚΚΚΚΚΚΚΚΚ

ΚΚΚ

β=α

β=α++αβ=α++α+α

=++++

nnnn

3nn3333

2nn2323222

1nn1313212111

x

xxxxx

bxaxaxaxa

ΚΚΚΚΚΚΚΚΚΚ

Page 23: Metode Numerice

METODE NUMERICE

6

for(j=1;j<=n-1;j++) iv=j; t=1; while( (iv<=n) && (t==1) ) if(a[iv][j] == 0) iv=iv+1; else t=0; if(t==1) cout<<"Determinantul pricipal este nul "; exit(0); if(j!=iv) for(k=j;k<=n;k++) temp=a[j][k]; a[j][k]=a[iv][k]; a[iv][k]=temp; // schimbam si elementul corespunzator liniei k al termenului liber temp=b[j]; b[j]=b[iv]; b[iv]=temp; for(l=j+1;l<=n;l++) for(k=j+1;k<=n;k++) a[l][k]=a[l][k] - a[j][k] * a[l][j] / a[j][j]; // calcul pt. termenul liber b[l]=b[l] - b[j] * a[l][j] / a[j][j]; if(a[n][n]==0) cout<<"Deterninantul principal este nul"; exit(0); // calculul lui xn x[n]=b[n] / a[n][n]; for(i=n-1;i>=1;i--) temp = b[i]; for(j=i+1;j<=n;j++) temp = temp - a[i][j] * x[j]; x[i] = temp / a[i][i]; for(i=1;i<=n;i++) cout<<"x["<<i<<"]= "<<x[i]<<endl; getch();

Page 24: Metode Numerice

METODE NUMERICE

1

5. Rezolvarea sistemelor de ecua ii algebrice liniareMetode iterative

2. Metode iterative – permit gasirea solutiei sistemelor liniare cu o anumita precizie,intr-un numar finit de pasi:Ø Metoda lui JacobiØ Metoda Gauss-Seidel

5.1 Metoda lui Jacobi

Consideram urmatorul sistem de n ecuatii liniare cu n necunoscute :

care se poate scrie: Ax = b, unde A=(aij)i=1,n ;j=1,m este matricea sistemului, iar b estevectorul termenilor liberi :

Definitie :Numim norma unui vector x, pe care o notam cu ||x||, un numar real definit

astfel :

Numim norma unei matrice A cu n lini si m coloane, pe care o notam ||A||,un numar real definit astfel :

=++++

=++++=++++=++++

nnnn33n22n11n

3nn3333232131

2nn2323222121

1nn1313212111

bxaxaxaxa

bxaxaxaxabxaxaxaxabxaxaxaxa

ΚΚΚΚΚΚΚΚΚΚΚΚ

ΚΚΚ

in

1ixmaxx

==

∑==

=m

1jij

n

1iamaxA

n

2

1

b

bb

Μ

Page 25: Metode Numerice

METODE NUMERICE

2

Teorema :

Daca numarul q = || I - A || are proprietatea )1,0(q ∈ , atunci, sistemul de ecuatiiAx = b,are o solutie unica, x, iar sirul xm, definit :

x0 = 0, xm+1 = (I- A) xm + b, converge la x.

In plus, sunt adevarate inegalitatile :

Determinarea aproximativa a solutiei sistemului Ax=b ca limita a sirului xm,poata numele de metoda Jacobi.

Exemplu:

Consideram urmatorul system de trei ecuatii cu trei necunoscute:

Daca notam cu A matricea sistemului si cu b vectorul de termeni liberi, atunciavem :

Deci

rezulta ca || I-A || = max 0.5, 0.5, 0.7 = 0.7. Ceea ce inseamna ca seindeplineste conditia teoemei, si anume q= || I-A || sa fie din intervalul (0,1).

In plus, || b || = max 1, 0.9, 1,1 = 1.1.Consideram aproximarea cu trei zecimale exacte eps = 0.001.

bq1

qxx

q11

xxm

m1mm −≤−

−≤− +

=+−−−=++

=−+

1.1xx6.0x1.09.0xxx4.01x2.0x3.0x

321

321

321

16.01.01.014.02.03.01

A−−

−=

06.01.01.004.0

2.03.00

16.01.01.014.02.03.01

100010001

AI −−−

=−−

−−=−

Page 26: Metode Numerice

METODE NUMERICE

3

Astfel, putem rezolva inecuatia:

Cea mai mica solutie a acestei inecuatii este:

Prezentam in continuare solutia exemplului dat mai sus, cu precizarea ca pentrua putea generaliza metoda lui Jacobi, trebuie scrise cate o functie de calcul a normeiunui vector, respectiv, o functie de calcul a normei unei matrice.

Solutia in limbajul C++ :

/* rezolvarea sistemelor de ecuatii liniare metoda JACOBI*/#include<iostream.h>#include<stdlib.h>#include<conio.h>#include<math.h>

double a[10][10],x[10],b[10],temp[10];// a este matricea sistemului// x vectorul de necunoscute ale sistemului// b vectorul de termeni liberi// temp un vector pentru calcul al unor valori temporaredouble q,eps,nb,s;// q numar egal cu norma matricei I-A ( adica q = |I - A| )// eps eroarea de calcul aproximativ al solutiilor sistemului// nb numar egal cu norma vectorului B ( adica nb = |B| )int n,m,j,i,iteratii;

void main(void) clrscr(); cout<<"Intoduceti nr. de linii si de coloane ale matricei sistemului "; cin>>n; for(i=1;i<=n;i++) for(j=1;j<=n;j++) cout<<"a["<<i<<","<<j<<"]= "; cin>>a[i][j]; cout<<"Introduceti elementele termenului liber "<<endl; for(i=1;i<=n;i++) cout<<"b["<<i<<"]= "; cin>>b[i];

001.0bq1

qm<

1qln

b)q1(001.0ln

m +

=

Page 27: Metode Numerice

METODE NUMERICE

4

cout<<"Sistemul initial este :"<<endl; for(i=1;i<=n;i++) cout<<a[i][1]<<" x"<<1; for(j=2;j<=n;j++) cout<<" + "<<a[i][j]<<" x"<<j; cout<<" = "<<b[i]<<endl; cout<<"are solutiile :"<<endl; eps=0.0001;/*

caz particular pentru sistemul : x1 + 0.3x2 - 0.2x3 = 1 0.4x1 + x2 + 0.1x3 =-0.9 -0.1x1 - 0.6x2 + x3 = 1.1*/ nb=1.1; q=0.7;

m=(int)(log(eps * (1-q) / nb ) / log(q) + 1); for(i=1;i<=n;i++) x[i]=0.0; for(iteratii=1;iteratii<=m;iteratii++) for(i=1;i<=n;i++) s=0.0; for(j=1;j<=n;j++) s+=a[i][j] * x[j]; temp[i]=x[i] - s + b[i]; for(i=1;i<=n;i++) x[i]=temp[i]; for(i=1;i<=n;i++) cout<<"x["<<i<<"]= "<<x[i]<<endl; getch();

Dupa executia programului, se vor obtine solutiile x = 0.63, 0.54, 1.04.

5.2. Metoda Gauss-Seidel

Consideram urmatorul sistem de n ecuatii liniare cu n necunoscute :

=++++

=++++=++++=++++

nnnn33n22n11n

3nn3333232131

2nn2323222121

1nn1313212111

bxaxaxaxa

bxaxaxaxabxaxaxaxabxaxaxaxa

ΚΚΚΚΚΚΚΚΚΚΚΚ

ΚΚΚ

Page 28: Metode Numerice

METODE NUMERICE

5

Metoda Gauss-Seidel este o varianta a metodei Jacobi, in scopul de a cresteconvergenta sirului de solutii xm.

Definitie :Un sistem liniar Ax=b se numeste normal daca matricea coeficientilor A este

simetrica, adica aij = aji, si daca forma patratica corespunzatoare

este pozitiv definita.

Teorema :Daca ambii membri ai sistemului liniar Ax=b, cu matricea A nesingulara, sunt

inmultiti la stanga cu transpusa AT, atunci sistemul rezultant ATA x = AT b estenormal.

Prezentam in continuare, o procedura Gauss_Seidel care rezolva un sistem deecuatii liniare cu ajutorul metodei Gauss-Seidel.

Vom avea matricea A, vectorul b al termenilor liberi si la sfarsitul functiei vomobtine in vectorul b solutia aproximativa si in variabila eroare eroarea relativa maximaa componentelor solutiei.

/* rezolvarea sistemelor de ecuatii liniare metoda GAUSS-SEIDEL

caz particular pentru sistemul :

x1 + 0.3x2 - 0.2x3 = 1 0.4x1 + x2 + 0.1x3 =-0.9 -0.1x1 - 0.6x2 + x3 = 1.1

*/#include<iostream.h>#include<stdlib.h>#include<conio.h>#include<math.h>

double a[10][10],x[10],b[10];// a este matricea sistemului// x vectorul de necunoscute ale sistemului// b vectorul de termeni liberiint n,m,j,i,eroare;

void gauss_seidel(double a[10][10], double x[10], int n) int imax=20; int eps=0.0000000001; int i,j,k; double t,tt[10]; // se genereaza elementele rezultate prin impartirea fiecarui elem. de pe linie cu // elem. de pe diagonala principala

∑∑= =

=n

1i

n

1jjiij xxau

Page 29: Metode Numerice

METODE NUMERICE

6

for(i=1;i<=n;i++) t=-1.0/a[i][i]; tt[i]=b[i]/a[i][i]; for(j=1;j<=n;j++) a[i][j]=a[i][j] * t; k=0; for(i=1;i<=n;i++) b[i]=tt[i]; do k++; eroare=0.0; for(i=1;i<=n;i++) t = tt[i]; for(j=1;j<=n;j++) t = t + a[i][j] * b[j]; b[i] = b[i] + t; if(b[i] != 0.0) t = t / b[i]; if(fabs(t)>eroare) eroare = fabs(t); while((eroare<eps) || (k==imax) );

return;void main(void) clrscr(); cout<<"Introduceti nr. de linii si de coloane ale matricei sistemului "; cin>>n; for(i=1;i<=n;i++) for(j=1;j<=n;j++) cout<<"a["<<i<<","<<j<<"]= "; cin>>a[i][j]; cout<<"Introduceti elementele termenului liber "<<endl; for(i=1;i<=n;i++) cout<<"b["<<i<<"]= "; cin>>b[i]; cout<<"Sistemul initial este :"<<endl; for(i=1;i<=n;i++) cout<<a[i][1]<<" x"<<1; for(j=2;j<=n;j++) cout<<" + "<<a[i][j]<<" x"<<j; cout<<" = "<<b[i]<<endl; cout<<"are solutiile :"<<endl; gauss_seidel(a,b,n); for(i=1;i<=n;i++) cout<<"x["<<i<<"]= "<<b[i]<<endl; cout<<"Eroarea relativa maxima este "<<eroare<<endl; getch();

Page 30: Metode Numerice

METODE NUMERICE

1

6. Evaluarea functiilor

1. Evaluarea polinoamelor. Schema lui Horner2. Evaluarea functiilor analitice3. Aproximarea functiilor. Polinoame de interpolare

6.1. Evaluarea polinoamelor. Schema lui Horner

Presupunem ca avem un polinom de grad n:

cu coeficienti reali ai, i=0,1,2,…,n.

Presupunem ca se cere gasirea valorii acestui polinom pentru x = .

Calculul se realizeaza cel mai convenabil punand P( ) sub forma:

Algoritmul calculului lui P( ) conform schemi lui Horner revine la evaluareasuccesiva a numerelor

b0=a0

bi=bi-1 + ai, i=1,2,…,n

si avem P( ) = bn.

Schema lui Horner imbina simplitatea formularii algoritmice cu eficientacalculului numeric, prin transformarea operatiilor de ridicare la putere in operatii deinmultire, care se efectueaza mai rapid si mai precis.

Programul urmator prezinta implementarea in C++ a schemei lui Horner. Seobserva ca nu este necesarea memorarea numerelor bi in timpul calculului, intr-unvector, si de aceea se utilizeaza o singura variabila b.

// ---------- calculul valorii unui polinom folosind SCHEMA lui HORNER----------------------

#include <iostream.h>double a[100],x;int n,i;double polinom(double a[100], double x, int n) double b;

nnnn axaxaxaxP ++++= −

−1

110)( Κ

nn aaaaaP +++++= − ξξξξξ )))((()( 1210 ΚΚ

Page 31: Metode Numerice

METODE NUMERICE

2

int i; b=a[0]; for(i=1;i<=n;i++) b=b*x + a[i]; return b;void main(void) cout<<"dati gradul polinomului n = ";cin>>n; for(i=0;i<=n;i++) cout<<"a["<<i<<"]= "; cin>>a[i]; cout<<"Dati valoarea pt. care se calculeaza x= ";cin>>x; cout<<"Valoarea polinomului in pct. "<<x<<" este: "<<polinom(a,x,n)<<endl;

6.2. Evaluarea functiilor analitice

O functie reala f(x) se numeste analitica in punctual . Daca intr-o vecinatate |x - |< R a cestui punct, ea poate fi dezvoltata intr-o serie de puteri (serie Taylor)

Pentru =0 obtinem seria MacLaurin

Suma partiala de ordinal n a seriei Taylor se numeste polinom Taylor de ordinuln.

Consideram exemplul functiei exponentiale din dezvoltarea sa in serie:

al carei interval de convergenta este ).,( +∞−∞ Polinomul Taylor de ordinal n este

∑∞

=

−=+−+−+=0

)(2

'''

)(!

)()(!2

)()(!1

)()()(i

ii

xi

fxfxffxf ξξ

ξξ

ξξ

ξ Κ

∑∞

=

=0

)(

!)0()(

i

ii

xi

fxf

∑ ∑= =

=−=n

i

n

ii

ii

n xtxi

fxF0 0

)(

)()(!

)()( ξξ

∑=

=+++=n

i

ix

ixxxe

0

2

!!21 Κ

Page 32: Metode Numerice

METODE NUMERICE

3

in acest caz:

Avand in vedere relatia dintre doi termini succesivi, este convenabil sa seefectueze calculul polinomului lui Taylor utilizand schema recurenta:

t0=1, F0=1

, Fi=Fi-1+ti, i = 1,2,…, n,…

Procesul iterativ se continua pana cand eroarea relativa devine mai mica decat ovaloare prescrisa , adica

| tn / Fn | .

Programul urmator prezinta implementarea in C++ a seriei Taylor aplicatafunctiei exponentiale.

// ----------------- calculul seriei TAYLOR pt. functia exponentiala ----------------------------#include <iostream.h>#include <math.h>double x;const eps=1e-10;int n,i;

double expn(double x) double f=1,t=1; int i=0; while( fabs(t/f) > eps ) i++; t = x/i * t; f = f + t; return f;

void main(void) cout<<"dati x = ";cin>>x; cout<<"expn("<<x<<")="<<expn(x)<<endl; cout<<" exp("<<x<<")="<<exp(x);

∑=

=n

iin xtxF

0

),()(!

)(ixxt

i

i =

1−= ii tixt

Page 33: Metode Numerice

METODE NUMERICE

4

6.3. Aproximarea functiilor. Polinoame de interpolare

Se cunoaste din materia de liceu ca putem avea urmatoarele tipuri de probleme:

1. Sa se determine functia de gradul I al carei grafic trece prin punctele de coordonate(1,5) si (3,-1).

Solutia problemei porneste de la forma generala a ecuatiei de gradul I:

Apoi determinam valorile a si b astfel incat sa indeplineasca conditiile:f(1)=5 si f(3)=-1.

Deci, obtinem:

f(1)=a*1+b=5 si f(3)=3*a+b=-1

Prin rezolvarea sistemului de doua ecuatii cu doua necunoscute, obtinem: a=-3si b=8.

Asadar, am obtinut functia de gradul I: f(x) = -3x + 8

2. Sa se determine functia de gradul II al carei grafic trece prin punctele decoordonate: (-1,-1), (2,5) si (3,11).

Solutia problemei porneste de la forma generala a ecuatiei de gradul II:

Apoi determinam valorile a, b si c din conditiile:f(1)= a – b + c = -1f(2)= 4*a + 2*b + c = 5f(3)= 9*a + 3*b + c = 11

Prin rezolvarea sistemului de trei ecuatii cu trei necunoscute (adica valorile a, b

bax)x(f,RR:f +=→

−=+=+

⇒1ba3

5ba

cbxax)x(f,RR:f 2 ++=→

=++=++−=+−

⇒11cb3a95cb2a41cba

Page 34: Metode Numerice

METODE NUMERICE

5

si c), obtinem a=1, b=1 si c=-1:

Asadar am obtinut functia de gradul al doilea f(x) = x2 + x - 1.

Putem generaliza cele doua probleme de mai sus, astfel:

Se dau m (m>=1) puncte din plan, (xi,yi), xi ≠ xj , .mj,i1,ji ≤≤≠∀ Sa sedetermine functia polinomiala, asociata unui polinom de gradul m-1, al careigrafic sa contina punctele date.

Exemplu: Daca avem 6 puncte in plan si trebuie sa determinam un polinom degradul 5 al carui grafic sa contina aceste puncte.

Teorema. Fiind date m puncte (m>=1) puncte in plan, (xi,yi), i = 1, 2, …, m,xi ≠ xj , ji ≠∀ , exista un polinom P, unic, avand gradul cel mult m-1 si pentru caregraficul functiei polinomiale asociate contine punctele date.

Definitie: Polinomul P, a carui existenta si unicitate sunt asigurate de teoremade mai sus, se numeste polinomul de interpolare al punctelor (xi,yi), i = 1, 2, …, m.

O situatie particulara care prezinta interes este aceea in care punctele deinterpolare sunt puncte care apartin graficului unei functii f, adica f(xi)=yi, mi1 ≤≤ . Inaceasta situatie polinomul de interpolare satisface conditiile P(xi)=f(xi), mi1 ≤≤ sispunem ca polinomul interpoleaza fucntia f prin punctele (x1, f(x1)), (x2,f(x2)), …,(xm,f(xm)).

Page 35: Metode Numerice

METODE NUMERICE

1

7. Aproximarea functiilorPolinoame de interpolare (I)

1. Polinomul LAGRANGE

Una dintre cele mai cunoscute formule de interpolare este construita de Lagrange subforma unui polinom de interpolare.

Sa presupunem ca in intervalul [a,b] sunt specificate n valori ale argumentului x1, x2, . . . ,xn, si valorile corespunzatoare ale unei functii f(x)

f(xi)=yi, i=1,2,…,n

Se cere construirea unui polinom Lm(x) care ia in punctele specificate xi aceleasi valori ca sifunctia f(x)

Lm(xi)=yi, i=1,2,…,n (1)

Pentru aceasta sa construim mai intai un polinom pi(x) pentru care

(2)

Deoarece polinomul cautat, pi(x), se anuleaza in cele (n-1) puncte x1, …, xi-1, xi+1, …, xn, elare expresia

unde Ci este uncoefficient constant, iar

Luind x=xi si avand in vedere ca pi(xi)=1 obtinem ∏=i ii )x(/1C . Cu acestea, gasim

pentru polinomul pi(x) care satisface conditiile (2)

(3)

Revenind acum la problema initiala a construirii polinomului Lm(x) caresatisface conditiile (1), acesta poate fi scris sub forma

(4)

≠=

=δ=ijdaca,0ijdaca,1

)x(p ijji

∏=−−−−= +− iin1i1i1ii )x(C)xx()xx)(xx()xx(C)x(p ΚΚ

∏ ∏≠

−=i

ijj)xx()x(

∏∏

=i i

ii )x(

)x()x(p

i

n

1iim y)x(p)x(L ∑

=

=

Page 36: Metode Numerice

METODE NUMERICE

2

Intr-adevar, deoarece polinoamele pi(x), sunt de ordinul (n-1), si Lm(x) este de ordinul (n-1) si satisface conditiile (1)

Inlocuind expresia (3) a polinoamelor pi(x) in (4) rezulta formula de interpolare a luiLagrange

Vom crea o fucntie numita Lagrange cu cinci parametri :ni – numarul de punctelor de interpolarexi si yi – tablouri care contin coordonatele punctelor de interpolarex – argumentul pentru care se calculeaza valoarea polinomului Lagrange de interpolarey – valoarea de iesire a functiei

Programul urmator prezinta implementarea in C++ a polinomului Lagrange intr-un punctdat x.

/* Polinomul de interpolare Lagrange*/#include<iostream.h>float xi[20], yi[20], x, y;int ni;

float lagrange(float xi[], float yi[], int ni, float x) int i, j; float p, y; for(i=1;i<=ni;i++) p=1; for(j=1;j<=ni;j++) if(j!=i) p=p*(x-xi[j])/(xi[i]-xi[j]); y=y+p*yi[i]; return y;

void main(void) cout<<" n = ";cin>>ni; cout<<" Vector x = "<<endl; for(int i=1;i<=ni;i++) cout<<"x["<<i<<"]= ";

∑ ∑= =

− ==δ==n

1i

n

1ijiijijij1n n,...,2,1j,yyy)x(p)x(L

∑ ∑ ∏

∏∏

= =≠

≠−

==n

1i

n

1ii

ijji

ijj

ii i

i1n y

)xx(

)xx(

y)x(

)x()x(L

Page 37: Metode Numerice

METODE NUMERICE

3

cin>>xi[i]; cout<<" Vector y = "<<endl; for(i=1;i<=ni;i++) cout<<"y["<<i<<"]= "; cin>>yi[i]; cout<<"Dati valoarea punctului pt. care se calculeaza polinomul =";

cin>>x; y=lagrange(xi,yi,ni,x); cout<<"Valoarea pentru "<<x<<" este "<<y<<endl;

Executia programului :

n=4vector x = -2, 1, 2, 4vector y = 25, -8, -15, -13valoarea punctului pt. care se calculeaza polinomul = 3Valoarea pentru 3 este 17.22221

2. Polinomul AITKEN

Schema de interpolare Aitken porneste de la polinomul Lagrange in mai multe puncte : x0,x1, x2, . . . , xn.

Se considera expresia

Acesta este un polinom de gradul intai in x.

Efectuand calculele, obtinem :

care este tocmai expresia polinomului Lagrange construit pe nodurile x0, x1.

Deoarece polinomul de gradul intai in punctele x0 si x1 ; respectiv valorile y0 si y1 este unic,

01

11

00

01 xxxxyxxy

)x(L−

−−

=

.yxxxx

yxxxx

yxxxx

yxxxx

xx)xx(y)xx(y

)x(L 101

00

10

11

01

00

01

1

01

011001 −

−+

−−

=−−

+−−

=−

−−−=

;y)x(L;y)x(L 11010001 ==

Page 38: Metode Numerice

METODE NUMERICE

4

acest lucru inseamna ca L01(x) rezolva problema interpolarii pentru nodurile x0, x1 (x0 < x1).In mod analog se construiesc polinoamele de interpolare liniare :

L12(x), L23(x), …,Ln-1,n(x)

; . . . . ;

Putem considera acum

care este un polinom de gradul doi in x.

Se verifica imediat ca L012(x0)=y0 ; L012(x1)=y1 ; L012(x2)=y2 ;si L012(x) este chiar polinomul de interpolare Lagrange construit pe nodurile x0 < x1 < x2, si careare in aceste puncte valorile y0, y1, y2.

In general, avem :

care va fi polinomul de interpolare Lagrange pentru nodurile x0 < x1 < . . . <xn, si care arein aceste puncte valorile y0, y1, . . . , yn.

Se observa ca L012…n(x) se obtine din L012…n-1(x) si L12…n(x) la fel cum L01(x) s-a obtinut diny0 si y1, dupa aceeasi schema.

Acesta schema este urmatoarea :

Aceasta schema ramane utila si la adaugare de noi valori x si y :

xi yi xi-x Li-1,i Li-2,i-1,i Li-3,i-2,i-1,i

x0 y0 x0-xx1 y1 x1-x L01(x)x2 y2 x2-x L12(x) L012(x)x3 y3 x3-x L23(x) L123(x) L0123(x)… … … … … …

xi xi-x yi Li-1,i Li-2,i-1,i Li-3,i-2,i-1,i

x0 x0-x y0 L01(x) L012(x) L0123(x)x1 x1-x y1 L12(x) L123(x) …x2 x2-x y2 L23(x) …x3 x3-x y3 …… … …

12

22

11

12 xxxxyxxy

)x(L−

−−

=1nn

nn

1n1n

n,1n xxxxyxxy

)x(L−

−−

− −

−−

=

02

221

001

012 xxxx)x(Lxx)x(L

)x(L−

−−

=

0n

n21

01n01

n012 xx

xx)x(nLxx)x(L

)x(L−

−−

=

−Κ

Κ

Κ

Page 39: Metode Numerice

METODE NUMERICE

5

Exemplu :

Se cere Ln(3) , deci a = 3.

Rezulta ca L3(3) = 17.22Aceeasi valoare se obtine si calculand cu polinomul Lagrange :

L3(a)= . . . . = -17.22

Programul urmator prezinta implementarea in C++ a schemei Aitken intr-un punct dat x.

/* Schema AITKEN*/

#include<iostream.h>float x[10], y[10], xa[10], d[10][20], a;int n;void citire(float z[]) for(int i=0;i<=n;i++) cin>>z[i]; return;void tipar() cout<<endl<<" Schema Aitken "<<endl; cout<<"-------------------------------------------"<<endl; cout<<" x x-a y I II III "<<endl; cout<<"-------------------------------------------"<<endl; int n1=n,j,i; for(i=0;i<=n;i++) cout<<x[i]<<" "<<xa[i]<<" "; for(j=0;j<=n1;j++) cout<<d[i][j]<<" "; n1--; cout<<endl; return;

void aitken() int i;

x -2 1 2 4f 25 -8 -15 -13

xi xi-a yi Li-1,i Li-2,i-1,i Li-3,i-2,i-1,i

-2 -5 25 -30 -20 -17.221 -2 -8 -22 -16.672 -1 -15 -144 1 -13

Page 40: Metode Numerice

METODE NUMERICE

6

for(i=0;i<=n;i++) xa[i]=x[i]-a; for(i=0;i<=n;i++) d[i][0]=y[i]; int n1,k=1,j; for(j=1;j<=n;j++) n1=n-j; for(i=0;i<=n1;i++) d[i][j]=(d[i][j-1] * xa[i+k] - d[i+1][j-1] * xa[i]) / (x[i+k]-x[i]); k++; return;void main(void) cout<<" n = ";cin>>n; cout<<" a = ";cin>>a; cout<<" vector x = "; citire(x); cout<<" vector y = "; citire(y); aitken(); tipar(); cout<<"valoarea pentru a este "<<d[0][n]<<endl;

Page 41: Metode Numerice

METODE NUMERICE

1

8. Aproximarea functiilorPolinoame de interpolare (II)

3. Polinom CEBISEV

Polinoamele Cebisev, utilizate frecvent pentru dezvoltarea unor functii, satisfac urmatoarearelatie de recurenta:

Programul urmator prezinta implementarea in C++ a polinomului Cebisev intr-un punct datx.

/*Polinomul CEBISEV

*/#include<iostream.h>#include<conio.h>void main(void) double t0,t1,tk,x; int n,k; clrscr(); cout<<"Introduceti datele polinomului:"<<endl; cout<<" x = "; cin>>x; cout<<"Dati gradul polinomului CEBISEV n = "; cin>>n; t0 = 1.0; t1 = x; for(k=2; k<=n; k++) tk =1.0/k * (2 * x * t1 - t0 ); t0 = t1; t1 = tk; cout<<"Polinomul Cebisev este :"<<endl; cout<<"\t\t\t"<<tk; getch();

4. Polinom LAGUERRE

Polinoamele Laguerre ortogonale, cu ),0( +∞∈x satisfac urmatoarea relatie de recurenta:

0)x(T)x(xT)x(T 1ii1i =+− −+

x)x(T,1)x(T 10 ==

xxPxP −== 1)(,1)(0

Page 42: Metode Numerice

METODE NUMERICE

2

Programul urmator prezinta implementarea in C++ a polinomului Laguerre intr-un punctdat x.

/*Polinomul LAGUERRE

*/#include<iostream.h>#include<conio.h>void main(void) double p0,p1,pk,x; int n,k; clrscr(); cout<<"Introduceti datele polinomului:"<<endl; cout<<" x = "; cin>>x; cout<<"Dati gradul polinomului n = "; cin>>n; p0 = 1.0; p1 = 1 - x; for(k=2; k<=n; k++) pk =1.0/k * ( (k*2-1) * p1 - (k-1) * p0 ); p0 = p1; p1 = pk; cout<<"Valoarea polinomului LAGUERRE este : "<<endl; cout<<"\t\t\t\t\t"<<pk<<endl; getch();

Programul urmator prezinta implementarea in C++ a polinomului Laguerre intr-o multimede valori x.

/*Polinoamele LAGUERRE in mai multe puncte

*/#include<iostream.h>#include<conio.h>void main(void) double x[100], y[100]; double p0,p1,pk; int m,n,k,i; clrscr(); cout<<"Introduceti datele polinomului:"<<endl; cout<<"Dati gradul polinomului LAGUERRE n = "; cin>>n; cout<<" In cate puncte se face calculul m = "; cin>>m; for(i=1;i<=m;i++)

( )[ ] .,...,3,2,)()1()(121)( 21 nkpentruxPkxPkk

xP kkk =−−−= −−

Page 43: Metode Numerice

METODE NUMERICE

3

cout<<"Punctul x_"<<i<<" "; cin>>x[i-1]; cout<<"======== Rezultate ========"<<endl; for(i=1;i<=m;i++) p0 = 1.0; p1 = 1 - x[i-1]; for(k=2; k<=n; k++) pk =1.0/k * ( (k*2-1) * p1 - (k-1) * p0 ); p0 = p1; p1 = pk; y[i-1] = pk; cout<<x[i-1]<<"\t\t"<<y[i-1]<<endl; getch();

5. Polinom LEGENDRE

Polinoamele Legendre, cu ),0( +∞∈x satisfac urmatoarea relatie de recurenta:

Programul urmator prezinta implementarea in C++ a polinomului Legendre intr-un punctdat x.

/*Polinomul LEGENDRE

*/#include<iostream.h>#include<conio.h>void main(void) double p0,p1,pk,x; int n,k; clrscr(); cout<<"Introduceti datele polinomului:"<<endl; cout<<" x = "; cin>>x; cout<<"Dati gradul polinomului LEGENDRE n = "; cin>>n; p0 = 1.0; p1 = x; for(k=2; k<=n; k++)

( )[ ] .,...,3,2,)()1()(121)( 21 nkpentruxPkxPkk

xP kkk =−−−= −−

xxPxP == )(,1)(0

Page 44: Metode Numerice

METODE NUMERICE

4

pk =1.0/k * ((k * 2 - 1) * x * p1 - (k - 1) * p0 ); p0 = p1; p1 = pk; cout<<"Polinomul Legendre este :"<<endl; cout<<"\t\t\t"<<pk; getch();

6. Polinom HERMITE

Polinoamele Hermite ortogonale, cu Rx ∈ satisfac urmatoarea relatie de recurenta:

Programul urmator prezinta implementarea in C++ a polinomului Hermite intr-un punct datx.

/*Polinomul HERMITE

*/#include<iostream.h>#include<conio.h>void main(void) double p0,p1,pk,x; int n,k; clrscr(); cout<<"Introduceti datele polinomului:"<<endl; cout<<" x = "; cin>>x; cout<<"Dati gradul polinomului HERMITE n = "; cin>>n; p0 = 1.0; p1 = 2 * x; for(k=2; k<=n; k++) pk = 2 * x * p1 - (k - 1) * 2 * p0 ; p0 = p1; p1 = pk; cout<<"Polinomul Hermite este :"<<endl; cout<<"\t\t\t"<<pk; getch();

.,...,3,2),()1(2)(2)( 21 nkpentruxPkxxPxP kkk =−−= −−

xxPxP 2)(,1)(0 ==

Page 45: Metode Numerice

METODE NUMERICE

1

9. Integrarea numerica a functiilor

Fie o func ie [ ] Rb,a:f → i F(x) o primitiv a sa. Atât f(x) cât i F(x) sunt func iicontinue. Conform formulei Newton-Leibnitz:

)a(F)b(F)x(Fdx)x(fb

a

b

a−==∫ , (9.1)

În cele mai multe cazuri este foarte greu uneori chiar imposibil de determinat formaprimitivei F(x). Integrala (9.1) se poate calcula cu aproxima ie folosind metodelenumerice prin care se aproximeaz func ia f(x) definit pe intervalul [a, b] cu o func ieg(x) astfel încât:

∫∫ ≈b

a

b

a

dx)x(gdx)x(f (9.2)

Pentru aceasta se utilizeaz urm toarea schem de calcul:1. se realizeaz o împ ire a intervalului [a, b] în n-1 subintervale cu ajutorul punctelor

de diviziune xi, i=1, 2, 3, ..., n;2. se scrie func ia de integrat sub forma: f(x) = g(x) + r(x), (9.3)

unde g(x) este o func ie de aproximare i r(x) o func ie rest;3. se integreaz rela ia (9.3):

∫∫∫ +=b

a

b

a

b

adx)x(rdx)x(gdx)x(f

(9.4)

Dac aproximarea func ie f(x) se face prin interpolare cu func ia polinomial

∑=

=n

kkk )x(qa)x(g

1 atunci formula de calcul a integralei (9.4) devine:

∫∑∫

∑ ∫∫ ∑∫∑∫

==

===

=

===

b

akk

n

kkk

b

a

n

k

b

akk

b

a

n

k

b

akk

n

kkk

b

a

dx)x(qI,Iadx)x(gdeci

dx)x(qadx)x(qadx)x(qadx)x(g

1

111

(9.5)

4. se caut o posibilitate de minimizare a erorii: ∫=δb

a

dx)x(r (9.6)

Page 46: Metode Numerice

METODE NUMERICE

2

1. Formule de integrare Newton-Cotes (cu interval inchis)

Aceste formule utilizeaz i valorile func iei de la capetele intervalului de integrare:y1=f(a) i y2=f(b) i polinomul de interpolare Lagrange.

În general pentru aproximarea func iei f(x) se utilizeaz diferite polinoame deinterpolare (preferându-se polinoame de grad mic, de obicei func ii spline continue degradul I sau II - fig. 9.1) i un num r cât mai mare de subintervale. Polinomul de interpolare Lagrange Ln(x) are expresia:

[ ]i

n

i

nin

n y)iq()!in(!i

q)()x(L)x(g ∑=

+−

−−−

==0

11 (9.7)

unde:[ ] ( )( ) ( )nq...qqqq n −−−=+ 211

;nqbxx;qaxx

hdqdx;hdxdq

hxx

haxq

n =⇒===⇒==

==⇒−

=−

=

00

0

(9.8)

Integrala (9.2) se scrie:

[ ]hdqy

)iq()!in(!iq)(dx)x(f

dx)x(Ldx)x(gdx)x(f

n n

ii

ninb

a

b

an

b

a

b

a

∫ ∑∫

∫∫ ∫

−−−

=≈

=

+−

0 0

11 (9.9)

x

y

y=f(x)

O

Fig.7.1.1

xi+1 xi+2

yi+1

xi

yi

yi+1

Func iispline

Page 47: Metode Numerice

METODE NUMERICE

3

Dac se noteaz : ( ) n/abh −= rezult formula Newton Cotes:

[ ]dq

)iq(q

)!in(!iy)(

n)ab(dx)x(f

n nb

a

iinn

i∫∫ ∑ −−

−−=

+−

= 0

1

0

11 (9.10)

care se mai scrie: ( )∑∫=

−=n

iii

b

ayHabdx)x(f

0 (9.11)

unde:

[ ]dq

)iq(q

)!in(!in)(H

n nin

i ∫ −−⋅−

=+−

0

11 (9.12)

se numesc coeficien ii Cotes.

Cazuri uzuale ale formulei Newton Cotes

Aplica iile formulei de integrare aproximativ Newton Cotes pentru diferite diviziuniale intervalului [a, b] sunt:

Ø pentru n=2 puncte de diviziune rela ia (9.11) se scrie:

( )[ ]∫ +−=b

a

yHyHabdx)x(f 1100 (9.14)

unde coeficien ii Cotes H0 i H1 au valorile:

21

211

0111

21

21

1011

1

0

21

01

1

0

21

00

==−−

⋅⋅=

=−=−

⋅⋅−=

qdqq

)q(q!!

H

qqdqq

)q(q!!

H

(9.15)

Înlocuind în rela ia (9.14) se ob ine formula trapezelor:

[ ]∫ +=b

ayyhdx)x(f 102 (9.16)

Page 48: Metode Numerice

METODE NUMERICE

4

Ø pentru n=3 puncte de diviziune (dou subintervale) rela ia (9.11) se scrie:

( )[ ]∫ ++−=b

ayHyHyHabdx)x(f 221100 (9.17)

unde coeficien ii Cotes H0 , H1 i H2 au valorile:

61

32411

0221

32

3212

1121

61

3232

4121

2021

2

0

322

02

2

0

32

2

01

2

0

322

00

=

+−=−

⋅⋅=

=

+−−=−

⋅⋅−=

=

+−=−−

⋅⋅=

qqdq)q(q!!

H

qqdq)q(q!!

H

qqqdq)q)(q(!!

H

(9.18)

Notând: hab 2=− se ob ine formula 1/3 a lui Simpson:

[ ]∫ ++=b

ayyyhdx)x(f 210 4

3 (9.19)

Prezentam in continuare implementarea in C++ a metodei trapezelor:Am nota cu ls valoarea lui a si cu ld valoarea lui b.

#include<iostream.h> #include<stdio.h> #include<conio.h> #include<math.h>

double f(double x) return (x*x+5);

double i_trapez(double ls,double ld,int n) double h,sum; int i; h=(ld-ls)/n; sum=(f(ls)+f(ld))/2;

Page 49: Metode Numerice

METODE NUMERICE

5

for(i=1;i<=n-1;i++) sum=sum+h*f(ls+i*h); return sum; void main() double ls,ld; int n; clrscr(); cout<<"Dati limita stanga ls = ";cin>>ls; cout<<"Dati limita dreapta ld = ";cin>>ld; cout<<"Dati numarul de puncte n = ";cin>>n; cout<<"Valoarea integralei prin formula trapezelor este"<<i_trapez(ls,ld,n)<<endl; getch();

Prezentam in continuare implementarea in C++ a metodei lui Simpson:

#include<iostream.h> #include<stdio.h> #include<conio.h> #include<math.h>

double f(double x) return(x*x+5);

double i_simpson(double ls,double ld,int n) double h,sum; int i; h=(ld-ls)/n; sum=h*(1/3)*(f(ls)+f(ld)); for(i=1;i<=n-1;i++) if(i==1+i%2) sum=sum+(2/3)*h*f(ls+i*h); else sum=sum+(4/3)*h*f(ls+i*h); return sum;

void main() double ls,ld,h; int n; clrscr(); cout<<"Dati limita stanga ls = ";cin>>ls; cout<<"Dati limita dreapta ld = ";cin>>ld; cout<<"Dati numarul de puncte n = ";cin>>n; cout<<"Valoarea integralei prin formula lui Simpson este"<<i_simpson(ls,ld,n)<<endl; getch();

Page 50: Metode Numerice

1

Obiective curs. • Crearea, analiza şi implementarea de algoritmi pentru rezolvarea problemelor din matematica

continuă • Analiza complexităţii, analiza şi propagarea erorilor, condiţionarea problemelor şi stabilitatea

numerică a algoritmilor problemelor numerice • Prezentarea metodelor numerice clasice şi a celor moderne de rezolvare a problemelor ştiinţifice

şi inginereşti • Alegerea celor mai potrivite metode numerice pentru o problemă dată

Conţinut curs.

• Reprezentare în virgulă mobilă. Standardul IEEE 754 pentru numere reale. Condiţionarea problemelor şi stabilitatea numerică a algoritmilor.

• Rezolvarea sistemelor de ecuaţii liniare prin metode gaussiene. Pivotare parţială şi totală. Factorizare LU.

• Propagarea erorilor în rezolvarea sistemelor de ecuaţii liniare.

• Metode iterative de rezolvare a sistemelor de ecuaţii liniare

• Interpolare polinomială. Polinom de interpolare Lagrange. • Diferenţe divizate. Polinom Newton. Eroarea interpolării.

• Interpolare cu funcţii spline. Interpolare trigonometrică.

• Aproximare uniformă. Polinoame Cebâşev. Algoritmii lui Remes. • Aproximare continuă şi discretă în sensul celor mai mici pătrate.

• Rezolvarea sistemelor în sensul celor mai mici pătrate. Factorizare QR. • Metodele Householder, Givens, Gram-Schmidt

• Integrare numerică. Metode Newton-Cotes. Metoda Romberg. • Integrare gaussiană. Polinoame ortogonale. Integrale improprii.

• Integrarea ecuaţiilor diferenţiale ordinare. Metode Runge-Kutta.

• Metode multipas explicite şi implicite. Predictor-corector. • Convergenţa metodelor multipas

• Valori proprii şi vectori proprii. Metodele puterii • Algoritmul QR cu deplasare explicită. Descompunerea valorilor singulare

Page 51: Metode Numerice

2

Aplicaţii ale calculului numeric.

1. Determinarea curenţilor într-un circuitul electric în regim staţionar:

conduce prin aplicarea legilor lui Kirchhoff la un sistem de ecuaţii liniare:

⎪⎩

⎪⎨

=+=+=−+

184310420

32

31

321

II

II

III

cu soluţia I1=1, I2=2, I3=3

2. Modelul Leontieff consideră economia formată din n sectoare independente: S1,S2,…, Sn. Fiecare sector consumă bunuri produse de celelalte sectoare (inclusive cele produse de el însuşi). Introducem notaţiile: mij = numărul de unităţi produse de sectorul Si necesare sectorului Sj să producă o unitate pi = nivelul producţiei sectorului Si mijpj = numărul unităţilor produse de Si şi consumate de Sj Numărul total de unităţi produs de Si este: p1mi1+p2mi2+…+pnmin Într-un system închis (autarhic) dacă economia este echilibrată, tot ce se produce trebuie consumat, adică:

⎪⎩

⎪⎨

=+++

=+++

nnnnnn

nn

ppmpmpm

ppmpmpm

L

L

L

2211

11212111

Adică sistemul: M.p = p sau (I-M).p=0, care pentru soluţii nenule, conduce la o problemă de valori şi vectori proprii.

Într-un model deschis de economie, unele sectoare îşi satisfac unele cerinţe din exterior, adică: pi = mi1p1+mi2p2+…+minpn+di

care conduce la sistemul liniar de ecuaţii: p = M.p + d

cu soluţia: p = (I-M)-1.d

Page 52: Metode Numerice

3

3. Coeficienţii care apar în reacţiile chimice se obţin aplicând legea conservării masei ecuaţiei de echilibru chimic. Astfel arderea etanului: xC2H6 + yO2 → zCO2 + tH2O

dă sistemul de ecuaţii liniare:

⎪⎩

⎪⎨

+===

tzy

tx

zx

2226

2

care are o soluţie întreagă: x=2, y=7, z= 4, t=6.

deci ecuaţia chimică este:

2C2H6 + 7O2 → 4CO2 + 6H2O.

O problemă având o natură fizică oarecare poate fi studiată experimental sau prin simulare. Aceasta poate fi transformată, utilizând legile fundamentale ale fizicii într-o problemă de natură matematică MP . Vom spune că problema este bine pusă dacă admite o soluţie unică.

Ca exemplu, vom considera următoarea problemă fizică:

PF: Să se studieze propagarea temperaturii într-o bară AB de lungime l cunoscând -temperaturile la momentul iniţial în orice punct M al barei ( ) [ ]l,x,x 00 ∈θ -temperaturile la cele două capete ( )tAτ şi ( )tBτ în orice moment [ ]10 t,t ∈

)(tAτ ( )tBτ( )M0θ

Page 53: Metode Numerice

4

Problema matematică corespunzătoare este:

PM : Să se determine funcţia:

( )

[ ] [ ] Rt,l,

)t,x(t,x:

→×θ→θ100

care satisface următoarele condiţii:

tx ∂∂θ⋅=

∂θ∂ K1 2

20 ecuaţia lui Fourier

)()0,(2 00 xx θ=θ condiţiile iniţiale

)(),0(30 tt Aτ=θ condiţiile pe frontieră )(),(40 ttl Bτ=θ

S∈θ05 , S = spaţiul funcţiilor de 2 ori derivabile pe [ ] [ ]1,0,0 tl ×

În acest moment intervine analiza numerică şi furnizează metodele de calcul, care în urma unui număr finit ( )ε,, txN de operaţii elementare furnizează pentru soluţia ( )tx,θ o aproximaţie ( )tx,θ′ efectiv calculabilă, astfel că: ε<θ′−θ ),(),( txtx . Prezintă interes metodele de calcul în timp finit, cu: 10 tt << care furnizează aproximaţii uniforme: ( ) ( )ε=ε NtxN ,, .

Problema continuă PM este transformată într-o problemă asemănătoare Ph prin discretizare. În acest scop se selectează un număr finit de puncte ( )tnxi ΔΔ , din domeniul compact [ ] [ ]1,0,0 tl × folosind o reţea de discretizare cu paşii:

Ml

x =Δ ,

Nt

t1

=Δ .

şi se notează: ),( tnxini ΔΔθ=θ

Dacă se aproximează derivatele parţiale cu diferenţele finite:

211

2

2

1

2x

)tn,xi(x

t)tn,xi(

tni

ni

ni

ni

ni

Δθ+θ⋅−θ

=ΔΔ∂θ∂

Δθ−θ

=ΔΔ∂θ∂

−+

se obţine următoarea problemă discretizată: Ph:

Să se determine niθ cu Nn,Mi <<<< 01 , care satisface condiţiile:

211

10 21

)x(K

t

ni

ni

ni

ni

ni

Δθ+θ⋅−θ

⋅=Δθ−θ −+

)(2 000 xii Δθ=θ

)(3 00 tnA

n Δτ=θ )(40 tnB

nM Δτ=θ

Page 54: Metode Numerice

5

Kx

t

⋅≤

ΔΔ

21

)(5 2

0

Problema discretizată Ph constă în rezolvarea succesivă a N sisteme de ecuaţii liniare tridiagonale. Diferenţa: n

itnxi θ−ΔΔθ ),( evaluează apropierea între soluţia problemei discretizate hP şi a modelului

matematic MP în fiecare punct al discretizării. Soluţia problemei discretizate hP trebuie să tindă spre soluţia problemei continue MP dacă 0→h (h reprezintă pasul de discretizare – în cazul problemei considerate avem paşii 0,0 →Δ→Δ tx sau

∞→∞→ MN , ); vom spune că trebuie satisfacută o condiţie de consistenţă:

Mh

h PP =→0

lim .

O altă condiţie importantă o reprezintă stabilitatea; aceasta impune ca soluţia θ′ a problemei perturbate MP (manifestată prin perturbarea parametrilor θ′, Aτ′ , Bτ′ ,K′ ) să fie apropiată de soluţia θ a

modelului matematic MP . Pe baza modelului matematic discretizat se va proiecta un algoritm, care va fi analizat prin prisma:

- eficienţei (resurse folosite: timp de calcul şi memorie), - convergenţei către soluţia modelului matematic continuu, - efectului propagării erorilor.

Etapele enumerate evidenţiază urmatoarele tipuri de erori: - erori deproblemă (inerente) care apar la trecere de la modelul fizic FP la cel matematic MP , - erori de metodă introduse prin discretizarea modelului matematic, - erori de trunchere provin din natura infinită a unor procese care descriu soluţia problemei - erori de rotunjire specifice rezolvării problemei pe calculatorul numeric, care utilizează aritmetica în virgulă mobilă mobilă

Page 55: Metode Numerice

6

Reprezentarea în virgulă mobilă.

fl(x) = ±0.a1a2...at × βe reprezentare normalizată 1 ≤ a1 < β şi 0 ≤ ai < β, i=2:t L ≤ e ≤ U

• Sistemul de reprezentare în virgulă mobilă F(β, t, L, U) cuprinde: • baza β • precizia reprezentării t • limitele (superioară şi inferioară ale) exponentului L şi U • reprezentarea lui zero Exemplu: F(10, 1, 0, 1)= ±0.a1×10e∪0 cu a1∈1:9 şi e∈0,1, în total 37 de numere. • 2(β-1)βt-1(U-L+1) valori distincte • a1 poate lua β-1 valori distincte, • restul de t-1 cifre poate lua fiecare β valori diferite, deci βt-1, • exponentul ia U-L+1, şi • semnul două). Cel mai mare număr reprezentabil Ω, (realmax) are forma: Ω = 0.(β-1)(β-1)...(β-1)× βU = = [(β-1)/β1+(β-1)/β2+...+(β-1)/βt] ×βU

Page 56: Metode Numerice

7

= (β-1)/β(1-β-t)/(1-β-1)×βU = βU(1-β-t) Ω = βU(1-β-t)

• Cel mai mic număr pozitiv reprezentabil ω numit şi realmin este:

ω = 0.10...0×βL=βL/β=βL-1 ω =βL-1

Surse de erori. Un număr real x∈F se reprezintă exact, dacă suma se termină înainte de t termeni şi exponentul este cuprins între limite. Altfel, numărul real x se aproximează printr-o valoare fl(x)∈F Aproximarea numărului real x=(0.a1a2... )βe=(a1β-1+a2β-2+...+atβ-t+at+1β-t-1 +...)βe se poate face prin trunchiere sau prin rotunjire. • Aproximarea prin trunchiere ignoră cifrele numărului real din dreapta poziţiei t. fl(x)=(0.a1a2...at )βe=(a1β-1+a2β-2 +... +atβ-t)βe

• Aproximarea prin rotunjire consideră: fl(x)=(0.a1a2...at+1 )βe dacă at+1 ≥ β/2 fl(x)=(0.a1a2...at )βe dacă at+1 < β/2 O depăşire superioară apare dacă e>U. Ea declanşează o eroare la execuţie, care conduce la întreruperea calculelor. O depăşire inferioară apare dacă e<L; ea duce la înlocuirea numărului prin zero. • Epsilon maşină (notat eps în Matlab sau μ) reprezintă cel mai mic număr pozitiv cu proprietatea că: fl(1+μ) > 1 De exemplu în F(10, 4, -3, 3) cu rotunjire prin tăiere (trunchiere):

• fl(1+0.0009)=fl(1.0009)=1 • fl(1+0.0010)=fl(1.0010)=1.001 > 1 aşadar μtr=0.001=10-3 >ω=10-4.

• Dacă se foloseşte rotunjire, atunci: fl(1+0.0004)=fl(1.0004)=1 fl(1+0.0005)=fl(1.0005)=1.001 > 1 cu μrot=0.0005=1/2.10-3 =1/2.μtr

• Eroarea absolută la rotunjirea prin trunchiere:

ex = x-fl(x)=(a1/β1+ a2/β2+...+ at/βt+at+1/βt+1+...)βe

– (a1/β1+ a2/β2+...+ at/βt)βe

ex = (at+1/β1+ at+2/β2+...)βe-t

|ex|≤|(β-1)/β1+(β-1)/β2+...|βe-t= (β-1)βe-t (1/β1+1/β2+...) ≤ (β-1)βe-t/(β-1)= βe-t

|ex| ≤ βe-t

Dacă se foloseşte rotunjirea atunci eroarea absolută este şi mai mică:

|ex|≤ 1/2. βe-t

• Eroarea relativă este: εx = |ex|/|x| = |x-fl(x)|/|x| ≤ βe-t/(0.a1...at...βe)

Page 57: Metode Numerice

8

εx ≤ βe-t/(0.10...0βe)= β1-t εx ≤ β1-t la trunchiere εx ≤ 1/2. β1-t la rotunjire În general:

|x-fl(x)|/|x| ≤ μ

de unde deducem:

fl(x) =x(1+ε), |ε| ≤ μ=K β-t

• De exemplu F(10,4,-20,20),Ω=1020(1-10-4) =9.999×1019, • ω=10-20-1=1.0×10-21, μr=1/2.10-4+1=5×10-4

Propagarea erorilor.

• numere aproximative -operaţii exacte • operaţii aproximative - date exacte

1.Rezultatul exact al adunării a două numere x şi y, dacă operaţiile se execută exact este x+y.

În realitate, se lucrează cu valorile inexacte x şi y, în care:

ex=|x-x| şi ey=|y-y| x+y=x+y±ex+y =x±ex+y±ey=x+y±(ex+ey) ex+y=ex+ey εx+y=ex+y/|x+y|=(ex+ey)/|x+y|=(|x|εx+|y|εy)/|x+y| εx+y=|x|/|x+y|εx+|y|/|x+y|εy=kxεx+kyεy

Pentru scădere:

x-y=x-y±ex-y=x±ex-(y±ey)=x-y±(ex+ey)

de unde: ex-y=ex+ey εx-y=|x|/|x-y|εx+|y|/|x-y|εy=kxεx+kyεy

În acest caz coeficienţii de ponderare:

kx=|x|/|x-y| şi ky=|y|/|x-y|

pot lua valori foarte mari dacă x≈y, deci în cazul scăderii numerelor apropiate ca ordin de mărime se pot comite erori foarte mari

În cazul înmulţirii:

xy=xy±exy=(x±ex)(y±ey)=xy±xey±yex+exey≈xy±(xey+yex) exy=xey+yex εxy=εx+εy

2. Dacă operaţiile se reprezintă aproximativ, iar numerele sunt reprezentate exact, adunarea a două numere x=fx.bex şi y=fy.bey presupune aducerea celui mai mic (fie acesta y) la exponentul celui mai mare, producându-se o denormalizare fl(x+y)=fl(fxbex+fyb-(ex-ey)bex)=fl[(fx+ fyb-(ex-ey ) ) bex] fl(x+y)=fl[(fx+fy(1+μ))bex]=fl[x+(1+μ)y]

Page 58: Metode Numerice

9

Rezultatul operaţiei este normalizat:

fl(x+y)=[x+(1+μ)y](1+μ)

Denormalizarea unuia dintre termeni poate fi evitată dacă se păstrează rezultatul intermediar într-un acumulator cu lungimea 2t (acumulator dublu) În acest caz numai rezultatul final va fi afectat de trunchiere la t cifre semnificative şi normalizare, deci:

fl2(x+y)=(x+y)(1+μ)

Anularea catastrofală.

• La scăderea a două numere apropiate ca ordin de mărime, cifrele semnificative se anulează reciproc, rezultând o eroare relativă mare.

fl(x)=0.a1a2...ap-1ap...at× βe

fl(y)=0.a1a2...ap-1bp...bt× βe

fl(y)-fl(y)=0.0 0 ...0 cp...ct× βe =0.cp...ct× βe-p • Iniţial avem o singură cifră inexactă, în poziţia t, cu eroarea relativă β1-t

• După scădere, bitul inexact trece în poziţia t-p cu eroarea relativă β1-(t-p)adică amplificată de βp ori.

Să considerăm scăderea numerelor x=0.120 şi y=-0.119 în sistemul F(10,2,-10,10): fl(x)=-fl(y)=0.120 ε=|((x+y)-fl(x+y))/(x+y)|=(0.001-0)/0.001=1 ! eroarea este de 100% ! Se evită scăderea numerelor apropiate ca ordin de mărime prin: •înmulţire cu conjugatul, •dezvoltare în serie Taylor, •rearanjarea termenilor etc . Prin rearanjarea termenilor evităm adunarea numerelor foarte diferite ca ordin de mărime. Astfel în sistemul F(10, 3,-10,10) cu rotunjire suma: 1+0.002+0.002+0.002 calculată

• fl(fl(fl(1+0.002)+0.002)+0.002)=1 în timp ce asocierea: • fl(1+fl(0.002+fl(0.002+0.002)))=1.01. În aritmetica în virgulă mobilă, asociativitatea nu se mai păstrează. Astfel:

fl(fl(x+y)+z)≠fl(x+fl(y+z)).

De exemplu:

fl(fl(1+μ/2)+ μ/2)= fl(1+μ/2)=1, în timp ce: fl(1+fl(μ/2+μ/2))= fl(1+μ) > 1

Reprezentarea numerelor reale (standardul IEEE 754).

Permite reprezentarea realilor în: 1) precizie simplă F(2, 24, -126, 127), folosind 32 biţi 2) precizie dublă F(2, 53, -1022, 1023); se folosesc 64 biţi: 3) precizie extinsă F(2, 65, -16382, 16382); se folosesc 80 biţi: Întrucât a1=1, acesta nu se mai reprezintă (este ascuns), câştigându-se astfel precizie suplimentară. Bitul ascuns este evidenţiat în reprezentarea: fl(x)=(-1)s2e.(1.+.f)

Page 59: Metode Numerice

10

Precizie simplă • reprezentare pe 32 biţi • baza β= 2 • precizie t= 24 biţi (numerele normalizate păstrează numai 23 biţi) • Numărul real este păstrat prin 3 componente:

– semnul: 1 bit – exponentul: 8 biţi – mantisa: 23 biţi (logic24)

• Cei 8 biţi permit: 28 = 256 valori diferite. Domeniul [0, 255] este transformat în [-127, 128]

• La exponentul (pozitiv sau negativ) se adaugă o valoare constantă care duce la un exponent deplasat sau caracteristică pozitivă. Factorul de deplasare pentru precizie simplă este127.

• Domeniul deplasat [0-255] reprezintă exponenţi în domeniul [-127, 128] exponent_deplasat = exponent + 127

Valoarea numărului este: V=(-1)s.2e.(1.+.f)

• 1=(-1)0.20.(1.+.0) 0+127

0 01111111 00000000000000000000000 S e(8) f(23) 0 011 1111 1000 0000 0000 0000 0000 0000

3 F 8 0 0 0 0 0 • -6.5=(-1)1.22.(1.+0.625) 2+127 1 10000001 10100000000000000000000 S e(8) f(23) 1 100 0000 1 101 0000 0000 0000 0000 0000 C 0 D 0 0 0 0 0

Un număr mai mare decât cel mai mare număr reprezentabil M (cunoscut sub numele de modulul reprezentării) se obţine în urma unei depăşiri superioare (de regulă o împărţire prin 0: 1/0 = ∞, -1/0 = -∞) va fi desemnat prin infinit – Inf, iar nedeterminările 0/0, ∞/∞ etc, vor fi desemnate ca NaN (Not a Number). Pentru toate acestea se rezervă în reprezentare cel mai mare exponent posibil 128 (adică exponentul deplasat 255).

Precizie simplă

S E (8biti) E-127 H F (23biti) Valoare NaN 0 11111111 128 1 ≠0 +Inf 0 11111111 128 1 000 …000 (-1)02128 0x7F800000 Ω 0 11111110 127 1 111 …111 (-1)02127(2-2-23)≈3.4E38 0x7F7FFFFF . . .

1+ε 0 01111111 0 1 000 …001 (-1)020(1+2-23) ε =2-23≈1.92E-7

0x3F800001

Page 60: Metode Numerice

11

1 0 01111111 0 1 000 …000 (-1)020=1 0x3F800000 ω 0 00000001 -126 1 000 …000 (-1)02-126=2-126≈1.175E-38 0x00FFFFFF

MaxD 0 00000001 -126 0 111 …111 (-1)02-126(1-2-23)=2-126-2-149 . . .

MinD 0 00000001 -126 0 000 …001 (-1)02-1262-23=2-149≈1.4E-45 0x00000001 +0 0 00000000 -127 1 000 …000 (-1)02-127=2-127 0x00000000

• Cel mai mic număr normalizat ω = 2-126 ≈1.175E-38 • Cel mai mic număr denormalizat este .00…1 * 2-126 = 2-149≈1.4E-45 • Infinit rezultă din calcule precum: 1/0 = ∞, -1/0 = -∞

Se reprezintă cu exponentul deplasat 255, (nedeplasat 128), şi fracţia 0. … 0 • Cel mai mare număr Ω = 1.111…1*2127 ≈ 3.4E38 • NaN (“not a number”) apare când se încearcă o operaţie nelegală (ca sqrt dintr-un număr

negativ) • Orice expresie care conţine un termen NaN este evaluată ca NaN

– Există cazuri în care apariţia unui NaN nu declanşează nici o întrerupere (excepţie) NaN este “liniştit” (QNaN)

– Un NaN semnalizat (SNaN)declanşează o excepţie (de exemplu o valoare neiniţializată) • sqrt(număr negativ) • 0 * ∞ 0 / 0 ∞ / ∞

• x % 0 ∞ % x ∞ - ∞

Precizie dublă

S E(11b) E-1023 H f(52biti) Valoare NaN 0 11…11 1024 1 ≠0 +Inf 0 11…11 1024 1 000 …000 (-1)021024 Ω 0 11…10 1023 1 111 …111 (-1)021023(2-2-52)≈1.8E308

1+ε 0 01…01 0 1 000 …001 (-1)020(1+2-52) ε=2-52≈1.1E-161 0 01…01 0 1 000 …000 (-1)020=1 ω 0 00…01 -1022 1 000 …000 (-1)02-1022=2-1022≈2.2E-308

MaxD 0 00…01 -1022 0 111 …111 (-1)02-1022(1-2-52)=2-1022-2-1074 MinD 0 0…001 -1022 0 000 …001 (-1)02-10222-52=2-1074≈5E-324

+0 0 0…000 -1023 1 000 …000 (-1)02-1023=2-1023

Condiţionarea problemelor.

• Condiţionarea unei probleme caracterizează sensibilitatea soluţiei în raport cu erorile din datele de intrare.

• O problemă este bine condiţionată dacă erori mici în date produc de asemeni erori mici în rezultate. • Condiţionarea este o proprietate a problemei, independentă de soluţia aleasă. • O problemă rău condiţionată este „aproape nerezolvabilă” în practică (chiar dacă problema este

rezolvată exact, soluţia poate fi lipsită de semnificaţie). • De exemplu, la evaluarea funcţiei y=f(x), o perturbare a datelor x+Δx produce o perturbare a

soluţiei y+Δy = f(x+Δx), în care:

• eroarea absolută ( ) xx'fy Δ⋅≈Δ

Page 61: Metode Numerice

12

• eroarea relativă ( )( ) x

xx

xf

xf

yy Δ

⋅⋅′

≈Δ

• Problema este rău condiţionată dacă factorul Lipschitz ( )( )

xxf

x'fL ⋅= este mare.

Stabilitatea numerică a algoritmilor

• Stabilitatea numerică caracterizează erorile numerice introduse de algoritm, în ipoteza unor date de intrare exacte. Se referă la precizia algoritmului.

• Un algoritm este instabil dacă erorile de rotunjire produc erori mari în rezultate. • Un algoritm numeric stabil nu introduce o sensibilitate suplimentară la perturbaţii. • Un algoritm stabil dă rezultate apropiate de soluţia exactă pentru o problemă bine condiţionată. • Un algoritm stabil nu poate rezolva o problemă rău condiţionată, dar un algoritm instabil poate da

soluţii slabe chiar pentru o problemă bine condiţionată.

Dacă f: X → Y este o problemă şi f∼: X → Y este un algoritm, atunci acesta este numeric stabil dacă pentru ∀x∈X, ∃x∼∈X, astfel încât:

( ) ( ) ( )mOxfxf ε=− −− şi ( )mOxx ε=− −

Algoritmul f∼

destinat rezolvării problemei f este numeric stabil, dacă este îndeplinită una din condiţiile: 1. f∼(x)≅ f(x), adică soluţia calculată aproximează bine soluţia exactă∼ 2. există x∼ apropiat de x astfel încât f∼(x)=f(x∼) – soluţia calculată de algoritm cu date de

intrare exacte este soluţia exactă cu date uşor perturbate. Exemple de algoritmi instabili: • inversarea de matrice folosind determinanţi • rezolvarea sistemelor liniare prin factorizare LU fără pivotare • utilizarea factorizării Cholesky în metoda celor mai mici pătrate (rezultate mult mai bune furnizează

factorizarea QR). • calculul valorilor proprii ca rădăcini ale polinomului caracteristic

Bibliografie.

• V.Iorga, B.Jora “Metode Numerice”,Ed.Albastră,2005 • C.Popeea, B.Jora, B.Dumitrescu “Calcul Numeric – Algoritmi fundamentali”, Ed.ALL • C.Moler “Numerical Computing with Matlab” • V.Iorga, F.Pop “Metode Numerice –Îndrumar de laborator”

Page 62: Metode Numerice

a.ch. – Octombrie 2008

1

CURS 2

METODE NUMERICE PENTRU SISTEME DE ECUAŢII NELINIARE

------------------------------------------------------------------------------------------------------------

0. Preliminarii: Norma unui vector si norma unei matrici (rapel).

1. Sisteme de ecuaţii neliniare. Definiţii.

2. Metoda punctului fix.

3. Metoda Newton; metode cvasi-Newton.

0 Norma unui vector şi norma unei matrici

Fie V un spaţiu vectorial: în cazul de faţă, V este nR sau nC .

Norma unui vector V∈x este aplicaţie +→ RV||:.|| , satisfăcând axiomele:

1. || x || ≥ 0, şi || x || = 0 ⇔ x = 0.

2. |||||||||| xx ⋅=⋅ λλ , scalar=∀λ ( CR ∈∈ λλ sau ).

3. |||||||||||| yxyx +≤+

Exemple de norme ale unui vector:

||max||||,1

ini

x=

∞ =x … norma-∞ (norma maximum)

∑=

=n

i

ix1

1 |||||| x … norma-1

2/1

1

22 ||||||

= ∑

=

n

i

ixx … norma-2 (norma euclidiană)

Fie nA este mulţimea matricilor nn × cu elemente scalare (reale, complexe).

Norma unei matrici nA∈A este o aplicaţie +→ RnA||:.|| , care satisface axiomele

1 – 3, şi în plus, următoarele:

4. |||||||||||| BABA ⋅≤⋅

5. |||||||||||| xAxA ⋅≤⋅

În axiomele 4-5, nA∈B , iar x este un vector. Normele care satisfac 5 se zic

compatibile cu norma vectorului.

Page 63: Metode Numerice

a.ch. – Octombrie 2008

2

Observaţie

Definiţia normei unei matrici, indusă de norma vectorului, este:

||||

||||sup||||

0 x

xAA

⋅=

≠x

Pentru detalii privind norma unui vector şi norma unei matrici, vezi Capitolul 4-I

Exemple de norme ale unei matrici:

∑=∞j

iji

a ||max|||| A - norma liniilor

∑=i

ijj

a ||max|||| 1A - norma coloanelor

[ ] 2/1

2 )(|||| AAA ⋅= ∗ρ - norma euclidiană,

în care: TAA =∗ ( A – conjugat transpus); ||max jj

λρ = , unde njj ,1, =λ sunt

valorile proprii ale matricii A. ρ se zice rază spectrală.

1 Definiţii

Fie sistemul de ecuaţii neliniare

0),...,,(

0),...,,(

21

211

=

=

nn

n

xxxf

xxxf

KK

Acesta se scrie vectorial

0xf =)( (1)

unde nRIf →: , nRI ⊂ . Explicit:

=

nx

x

x

.

.2

1

x ,

=

0

.

.

0

0

0 ,

=

)(

.

.

)(

)(

)(2

1

x

x

x

xf

nf

f

f

,

O soluţie a sistemului (1) se va nota cu αααα, adică: 0αf =)( .

Page 64: Metode Numerice

a.ch. – Octombrie 2008

3

Pentru rezolvarea prin metoda punctului fix, sistemul (1) se va considera pus sub

forma:

)(xgx = (2)

în care nRIg →: , nRI ⊂ ,

O soluţie a lui (2) se va nota αααα, adică: )(αgα = .

În ceea ce urmează, se presupun cunoscute noţiunile de normă a unui vector |||| x , şi

normă a unei matrici pătratice |||| A . În particular, norma-∞ este:

||max|||| ii

x=∞x ; ∑=∞j

iji

a ||max|||| A .

2 Metoda punctului fix

Ecuaţii de forma )(xgx = .

Metoda

Metoda constă în construirea şirului:

T

nxxx ]...[ )0()0(2

)0(1

)0( =x - aproximaţia iniţială, dată;

0),( )()1( ≥=+ nnn xgx

A nu se confunda indicele superior (n) (indicele iteratei) cu ordinul n al sistemului

(indice inferior al coordonatei )(k

nx ).

Convergenţa procesului iterativ este asigurată de următoarele condiţii:

(1) g este contractantă – pe o vecinătate I a rădăcinii: pentru Iyx ∈∀ ,

||||||)()(|| yxygxg −⋅≤− M , M < 1.

(2) Aproximaţia iniţială Ix ∈)0( este suficient de apropiată de rădăcina αααα.

Observaţie

Dacă CCg →: şi nRC ⊂ este un compact (mulțime mărginită și închisă), atunci

procesul converge pentru Cx ∈∀ )0( .

Page 65: Metode Numerice

a.ch. – Octombrie 2008

4

Teorema 1

Presupunem:

1. )(xgx = are o rădăcină αααα.

2. g este continuă şi are derivate parţiale de ordinul 1 continue, pe I definit de:

ρ≤− ∞|||| αx .

3. Derivatele satisfac condiţia:

1)(

max <≤∂

∂∑ λ

j j

i

i x

g x, Ix ∈∀ .

Atunci, Ix ∈∀ )0( :

(a) Iteratele Ix ∈)(n .

(b) Şirul αx →)(n .

(c) αααα este unica rădăcină în I

Intervalul I din Condiția (2).

1x

2x

ξξξξ

y αααα

x

ρ

ρ

Page 66: Metode Numerice

a.ch. – Octombrie 2008

5

Sumarul demonstraţiei:

Fie x, y ∈ I: ρ≤− ∞|||| αx , ρ≤− ∞|||| αy . Din desvoltarea Taylor, se arată că avem:

∞∞ −⋅≤− ||||||)()(|| yxygxg λ

Rezultă:

ρρλλ <⋅≤−⋅≤−=− ∞∞∞+ ||||||)()(|||||| )()()1(

αxαgxgαx nnn

şi prin inducţie:

ρλ ⋅≤− ∞nn |||| )(

αx

Cum λ < 1, rezultă 0→nλ , sau αx →)(n .

Concluzia (c) se demonstrează prin contradicţie

Observaţii

1) Matricea jacobian a funcţiei g:

Introducem jacobianul G a lui g, prin:

x

x

xG

=

∂=

n

nnn

n

j

i

x

g

x

g

x

g

x

g

x

g

x

g

x

g

...

.....................

...

)(

21

1

2

1

1

1

Cu definiţia normei ∑=∞j

iji

a ||max|||| A , condiţia 3 se scrie:

3'. 1||)(|| <≤∞ λxG , Ix ∈∀

G(x) joacă rolul lui )(xg ′ pentru o funcţie scalară.

2) Convergenţa liniară:

În condiţiile din Teorema 1, cu λ > 0, convergenţa este liniară, conform relaţiei:

∞∞+ −⋅≤− |||||||| )()1(

αxαx nn λ .

Page 67: Metode Numerice

a.ch. – Octombrie 2008

6

3) Convergenţa de ordinul 2 (pătratică)

Să presupunem că în rădăcina αααα, avem:

0)( =∂

∂⇔=

α

OαGj

i

x

g; i, j = 1, 2, …, n

unde O este matricea nulă, şi că ji xg ∂∂ / sunt continue pe o vecinătate a lui αααα.

Atunci, 0>∃ρ astfel încât condiţia 3 sau 3' este satisfăcută. Dacă, în plus, derivatele

de ordinul 2 există şi sunt mărginite pe ρ≤− ∞|||| αx , adică:

1

2

,,max M

xx

g

kj

i

kji≤

∂∂

∂,

atunci din formula Taylor rezultă:

2||||||)()(|| ∞∞ −⋅≤− αxαgxg M ,

unde 12

2

1MnM ⋅⋅= ,

Cu )(nxx = , )1()( )( += nn xxg , rezultă:

2)()1( |||||||| ∞∞+ −⋅≤− αxαx nn

M

care arată că convergenţa este de ordinul 2

2.2 Procedură explicită de punct fix

Considerăm sistemul dat sub forma 0xf =)( şi vrem să-l transformăm într-un sistem

echivalent de forma )(xgx = .

Fie )]([)( xxA ija= o matrice nn × , nesingulară pe o vecinătate a lui αααα. Definim:

)()()( xfxAxxg ⋅−=

Este evident că, A fiind nesingulară, avem:

Page 68: Metode Numerice

a.ch. – Octombrie 2008

7

0xfxgx =⇔= )()( .

Exemplu – 1: ‘Iterare cu matrice constantă’

A(x) = A , unde A = matrice constantă (aij = constant) şi nesingulară.

)()( xfAxxg ⋅−=

Se verifică imediat că, jacobianul lui g este dat de:

)()( xFAIxG ⋅−= ,

unde I este matricea unitate, iar F(x) este jacobianul lui f,

x

xF

∂=

k

j

x

f)( .

Explicit:

x

x

xF

=

∂=

n

nnn

n

j

i

x

f

x

f

x

f

x

f

x

f

x

f

x

f

...

.....................

...

)(

21

1

2

1

1

1

Conform Teoremei 2, iteraţia va converge dacă elementele matricii G(x) sunt

suficient de mici, şi )0(x este suficient de apropiat de αααα.

Pentru o convergenţă mai rapidă, să cerem – v. Observaţia 3:

OαG =)( .

Rezultă IαFA =⋅ )( , sau

[ ] 1)( −= αFA . (3)

Cum αααα nu este cunoscut, luăm de exemplu, )0(xα ≈ , rezultă:

[ ] 1)0( )(−

= xFA . (4)

Iteraţia va fi definită de

Page 69: Metode Numerice

a.ch. – Octombrie 2008

8

)( )()()1( nnn xfAxx ⋅−=+ , (5)

unde A este definită de (4).

Procedura se zice iterare cu matricea constantă A, şi este analoagă cu metoda coardei

pentru o funcţie scalară

2.3 Schema practică de iterare

Procedeul practic, care evită inversarea matricii )( )0(xF , este următorul. Punem:

)()1()1( nnn xxx −= ++δ ,

şi rezultă:

≥+=

−=++

+

0)((

)1()()1(

)()1()0(

nnnn

nn

xxx

xfxxF

δ

δ (6)

Procedeul revine la determinarea corecţiei )1( +nxδ prin rezolvarea sistemului liniar din

prima ecuație (6). Iteraţia se opreşte prin testele

epsn ≤+ |||| )1(xδ , (7a)

n +1 ≤ lnit (7b)

unde toleranţa eps şi numărul limită de iteraţii lnit, sunt alese dinainte. Procedeul este

util mai ales dacă actualizăm A după un număr de paşi, conform Observaţiei 1.

Codul Fortran care implementează această schemă, cu actualizarea matricii A după 3

paşi, este dat în ANA – Fix_Sys.

Exemplu – 2: ‘Metoda Newton’

Să presupunem că, pentru a avea [ ] 1)( −= αFA , actualizăm matricea A din (4,5), la

fiecare pas. Iteraţia (5) devine:

[ ] )()( )(1)()()1( nnnn xfxFxx ⋅−=−+ .

Aceasta reprezintă metoda Newton pentru sistemul f(x) = 0 – v. în continuare

Page 70: Metode Numerice

a.ch. – Octombrie 2008

9

3 Metoda Newton

Ecuaţii de forma 0xf =)( .

Metoda

Considerăm ecuaţia echivalentă )(xgx = , unde )()()( xfxAxxg ⋅−= .

Căutăm )(xA , astfel ca metoda punctului fix pentru g să aibă ordinul doi. Condiţia

este – v. mai sus, OαG =)( , sau

0=∂

=αxk

i

x

g, i, k = 1, 2, .., n .

Se verifică faptul că aceasta conduce la condiţia [ ] 1)()( −= αFαA .

Atunci, presupunem că:

- f este continuă şi cu derivate parţiale de ordinul 1 continue, pe o vecinătate a lui

rădăcinii αααα.

- Jacobianul lui f este nesingular în αααα:

0))(det( ≠αF .

Determinantul fiind funcţie continuă de elementele jacobianului, 0>∃ρ astfel că

pentru ρ≤− |||| αx să avem

0))(det( ≠xF .

Alegem atunci

[ ] 1)()( −= xFxA , ρ≤− |||| αx ,

care asigură [ ] 1)()( −= αFαA . Rezultă:

[ ] )()()( 1xfxFxxg ⋅−=

Metoda Newton este atunci:

[ ] )()( )(1)()()1( nnnn xfxFxx ⋅−=−+ (8)

Conform Teoremei 1 şi Observaţiei 3, rezultă următoarea

Page 71: Metode Numerice

a.ch. – Octombrie 2008

10

Propoziţie

Dacă f are derivate parţiale de ordinul 2, mărginite pe ρ≤− |||| αx , şi )0(x este

suficient de apropiat de αααα, atunci metoda Newton are convergenţă pătratică

În propoziţia de mai sus, şi în relaţiile anterioare, || . || este ∞||.|| .

Notă

Ipotezele de mai sus, în particular 0))(det( ≠αF , se poate înlocui cu altele – v . Cap.

3-IV, 3.1, Teorema 3. Astfel, metoda se poate aplica şi în cazul 0))(det( =αF . În

acest caz, convergenţa este liniară.

3.2 Schema practică de iterare

Schema practică de iterare este cea de la 2.3, evitându-se inversarea matricii )( )(nxF ,

şi anume:

≥+=

−=⋅++

+

0)()(

)1()()1(

)()1()(

nnnn

nnn

xxx

xfxxF

δ

δ (9)

Corecţia )1( +nxδ se calculează prin rezolvarea sistemului liniar din prima ecuație (9).

Iteraţia se opreşte prin testul

epsn ≤+ |||| )1(xδ , (10a)

unde toleranţa eps este aleasă dinainte. Obişnuit, se adaugă şi testul:

Număr de iteraţii ≤ lnit, (10b)

unde lnit este numărul limită prescris de iteraţii.

Codul Fortran care implementează această schemă se dă în ANA – Newton_Sys.

3.3 Calculul numeric al derivatelor parţiale

Evaluarea jacobianului )( )(kxF , la pasul k, cere evaluarea a n2 funcţii ki xf ∂∂ / . Chiar

dacă acestea se pot calcula analitic, pentru n mare efortul de calcul este mare. Alteori,

)(xif sunt date numeric. În astfel de cazuri, derivatele se calculează numeric, prin

diferenţe divizate:

Page 72: Metode Numerice

a.ch. – Octombrie 2008

11

)()(

),...,,...,(),...,,...,( 11

kkh

xxxfxhxxf

x

f njinji

j

i

xx

−+=

∂,

unde || h este ‘mic’. Creşterea h poate constantă, sau poate fi variată de la un pas la

altul (luând )(khh = ). h nu se ia excesiv de mic, pentru a nu conduce la erori de

rotunjire mari. Se arătă că, pentru a menţine convergenţa pătratică, h trebuie să

satisfacă condiţia (la pasul k):

||)(|||| )(kCh xf≤ ,

unde C este o constantă pozitivă, fixată dinainte (Ralston & Rabinowitz (1978)).

3.4 Metode cvasi-Newton

Metoda Newton este metoda descrisă de formula de iterare (6), care utilizează

jacobianul evaluat la fiecare pas )(nx (analitic, sau numeric).

Dacă jacobianul )( )(nxF este înlocuit cu o aproximaţie a acestuia, metodele se zic

metode Newton-modificate sau metode cvasi-Newton.

Pentru a reduce efortul de calcul se procedează la înlocuirea jacobianului )( )(kxF de

la pasul k, cu o aproximaţie a acestuia, fie aceasta )(kA , după una din următoarele

scheme:

- Jacobianul nu se actualizează după fiecare pas, ci după un număr m de paşi:

)( )()( kl xFA = - pentru )1(,, −+= mkkl K .

Această schemă reduce viteza convergenţei, dar este economică la o rulare lungă.

- Aproximaţia jacobianului la pasul k+1 se generează din cea de la pasul k, fără

evaluări suplimentare de funcţii. Această schemă este mai bună decât precedenta.

Pentru modalităti de generare a lui )1( +kA - v. Ralston & Rabinowitz (1978).

Cu modificările precedente, formula de iterare (8) devine:

)(][ )(1)()()1( kkkk xfAxx ⋅−= −+ (9)

Page 73: Metode Numerice

a.ch. – Octombrie 2008

12

Nota 1: Metoda Newton prin liniarizarea ecuaţiilor

Fie ecuaţia neliniară 0xf =)( , sau explicit, sistemul

nif i ,,2,1,0)( K==x

Dacă )0(x este în vecinătatea rădăcinii, considerăm desvoltarea Taylor a lui )(xif în

jurul lui )0(x :

∑=

+−∂

∂+=

n

j

jj

j

i

ii xxx

fff

1

)0(

)0(

)0( )()()( K

x

xx

unde termenii nescrişi sunt de ordin mai mare sau egal cu doi în )( )0(jj xx − .

Presupunem că aceştia sunt neglijabili în raport cu termenii de orinul întâi, şi avem

∑=

−∂

∂+≈

n

j

jj

j

i

ii xxx

fff

1

)0(

)0(

)0( )()()(x

xx

Notăm j

ii

jx

fF

∂= elementele jacobianului F al lui f, adică

=

∂∂∂∂

∂∂∂∂

=n

n

n

n

nnn

n

FF

FF

xfxf

xfxf

L

LLL

L

L

LLL

L

1

111

1

111

//

//

)(xF

Desvoltarea devine

∑=

−+≈n

j

jj

i

jii xxFff1

)0()0()0( ))(()()( xxx ,

Sau, matriceal,

⋅+=

0

022

011

21)0(

)0(][)()(

nn

i

n

ii

ii

xx

xx

xx

FFFffM

Kx

xx

Page 74: Metode Numerice

a.ch. – Octombrie 2008

13

Ecuaţiile scrise pentru ni ,,2,1 K= , dau:

))(()()( )0()0()0( xxxFxfxf −+≈

Rezolvăm aproximativ sistemul 0xf =)( , înlocuind )(xf prin expresia sa liniarizată

(în membrul doi al relaţiei precedente; punem semnul = în loc de ≈).

Rezultă:

)()( )0()0( xfxxF −=δ , (11)

unde s-a pus

)0(xxx −=δ .

Relaţia (11) este formula schemei de iterare în metoda Newton.

Soluţia xxx δ+= )0()1( este o aproximaţie a rădăcinii (este soluţia sistemului

liniarizat).

Presupunând că aproximaţia )1(x este mai bună decât )0(x , atunci metoda constă în

aplicarea repetată a formulei (10), înlocuind, la pasul următor, )0(x cu )1(x .

Astfel, în general, metoda Newton este:

K,1,0),()( )()1()1( =−=++ kkkk xfxxF δ

unde )()1()1( kkk xxx −= ++δ

Problema constă acum, în a proba că şirul αx →)(k .

Nota 2: Interpretare geometrică pentru cazul n = 2

Să punem ),(1 yxfz = , ),(2 yxfz = . Acestea sunt ecuaţiile a două suprafeţe, fie

acestea 1S şi 2S .

Ecuaţia 0),(1 =yxf , revine la 0=z , adică la intersecţia suprafeţei 1S cu planul x-y:

aceasta este o curbă 1C . Soluţia sistemului 0),(,0),( 21 == yxfyxf , revine la

intersecţia curbelor 1C şi 2C .

Page 75: Metode Numerice

a.ch. – Octombrie 2008

14

Funcţia liniarizată este:

)(),(

)(),(

),( )0()0()0(

)0()0()0(

)0()0(jj

i

jj

i

i yyy

yxfxx

x

yxfyxfz −

∂+−

∂+≈

Aceasta reprezintă ecuaţia planului tangent în ),( )0()0( yx , la suprafaţa iS .

Deci, metoda revine la înlocuirea suprafeţei, în vecinătatea rădăcinii, prin planul

tangent

(Analog, cu metoda Newton pentru o ecuaţie scalară 0)( =xf , unde graficul se

înlocuieşte cu tangenta la grafic).

Intersecţiile planelor tangente cu planul x-y vor fi două drepte – care aproximează

curbele 1C şi 2C . Intersecţia dreptelor este aproximaţia rădăcinii.

Exemplu

Fie sistemul de două ecuaţii neliniare:

05),( 221 =−+≡ yxyxf , 01),(2 =−−≡ xeyyxf .

Aproximaţiile iniţiale se iau:

)1,2()0( −=x , şi )2,5.0()0( =x .

De exemplu, acestea se pot găsi analizând intersecţia graficelor curbelor

522 =+ yx , 1+= xey .

Page 76: Metode Numerice

a.ch. – Octombrie 2008

15

Matricea jacobian este:

⋅⋅=

1

22),(

xe

yxyxF .

Luăm eps = 1E-6. Calculul este efectuat în simplă precizie. Soluţia calculată (x, y),

numărul de iteraţii, şi valorile lui f în soluţie, sunt date în tabelele de mai jos.

1) Metoda punctului fix, iterare cu matricea constantă )( )0(xFA = , cu actualizare

după 3 paşi:

Page 77: Metode Numerice

a.ch. – Octombrie 2008

16

)0(x Nr. iteraţii x y f1(x, y) f2(x, y)

(-2,1) 5 -1.919 684 1.146 653 -2.761 E-7 -2.995 E-8

(0.5, 2) 17 0.2043 374 2.226 712 7.210 E-8 -4.654 E-8

Observaţii

Derivatele parţiale ale funcţiilor if sunt calculate numeric , cu h = 0.001. Numărul

de iteraţii pentru a doua rădăcină este mai mare decât cel pentru prima rădăcină,

întrucât aproximaţia iniţială (0.5, 2) este mai îndepărtată de rădăcină. Cu aproximaţia

)0(x = (0.2, 2.2), se găseşte aceeaşi soluţie în 8 iteraţii.

2) Metoda Newton:

)0(x Nr. iteraţii x y f1(x, y) f2(x, y)

(-2,1) 4 -1.919 684 1.146 653 -2.761 E-7 -2.995 E-8

(0.5, 2) 5 0.2043 374 2.226 712 5.384 E-8 8.289 E-9

Notă: Derivatele parţiale sunt calculate cu matricea jacobian F(x, y)

Exerciţiu

Să se rezolve sistemul:

=−−

=+−−

=−

7

4

222

2

zee

yxxyz

zxy

yx

Să se găsească rădăcinile din vecinătatea punctelor )1,2,2(0 −=w şi )1,1,1(0 =w .