Curs 2 Cap3 SerTaylor EvalPolin

Dumitru Dragomir Metode numerice C2,3 1

Cap. 3. Dezvoltri n serie. Evaluarea polinoamelor. Algoritmi iterativi 3.1. Dezvoltri n serie Metodele de calcul numeric sunt concepute s foloseasc numai operaiile aritmetice fundamentale ( + , - , , / ), pentru a realiza calculele prin algoritmi ct mai apropiai de operaiile elementare ale calculatorului. O bun parte dintre aceti algoritmi se bazeaz pe metoda dezvoltrilor n serie Taylor. Se cunoate c o funcie poate fi evaluat ntr-un punct x din vecintatea unui punct x0 utiliznd valorile funciei i derivatelor sale din punctul xo cu urmtoarea relaie:

( ) ( ) ( ) ( ) ( ) ( ) ...!2!1!

)()( 2001

00

00

00

][

+++== =

xxxfxxxfxfxxk

xfxfk

kk

(3.1)

unde f(k)(xo) reprezint derivata de ordin k a funciei f n punctul xo. Din punct de vedere numeric, dezvoltarea n serie infinit de termeni este imposibil. Fie n un numr natural. Evaluarea funciei f(x) se poate face aproximativ prin dezvoltare cu un numr finit n de termeni dup relaia:

( )f x f xk

x x E xk

k

k

n

n( )( )!

( )[ ]

= +=

0 00

(3.2)

unde limita maxim a erorii de metod este:

( )E x f cn

x xnn

n( )

( )( )!

[ ]

= + + +1

0

1

1 (3.3)

iar c este o valoare oarecare a argumentului, ntre xo i x. Pe baza celor artate mai sus, se pot deduce dezvoltrile n serie ale ctorva funcii uzuale:

sin( )! ! !

...x x x x x= + +3 5 7

3 5 7 x R (3.3.1)

cos( )! ! !

...x x x x= + +12 4 6

2 4 6

x R (3.3.2)

exp( )! !

...x x x x= + + + +12 3

2 3

x R (3.3.3) Orice evaluare numeric prin dezvoltare n serie este posibil numai dac respectiva serie este convergent, respectiv dac En(x) tinde la 0 (zero) cnd n tinde la (infinit). Considernd seria ca un ir de valori ai ( ao, a1, a2, ...), suficiena aproximrii se evalueaz prin determinarea celui mai mic numr de termeni din serie (cel mai mic n) care s respecte condiia: | an | < e (3.4) unde e este o eroare absolut impus i e > 0. Dac se consider acum

f x an ii

n

( ) ==

0

un criteriu similar cu cel dat de relaia (3.4) este:

( ) ( ) eaaaxfxf 1nn0i

1n

0iii1nn


a) f(x)=ex care, n vecintatea punctului x=1 se poate dezvolta n serie Taylor cu relaia:

( ) ( ) ( ) ( ) ( ) ...1!

...16

12

11

3

0

32 +

=++++= =k

kk

x xkexexexeexFe (3.6)

n care au fost reinui numai primii 4 termeni (rangurile de la 0 la 3). n figura 3.1 sunt reprezentate componentele de rang k ale sumei, funcia f(x) exact i

funcia F(x) dat de suma de aproximare. Obs.: prin simplificare cu e i nlocuirea lui x-1 cu x relaia (3.6) devine (3.3.3).

-4

-2

0

2

4

6

8

0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2

rang 0

rang 1

rang 2

rang 3

F(x)

f(x)

Fig. 3.1.

b) f(x)=x5 care, n vecintatea punctului x=1 se poate dezvolta n serie Taylor cu relaia:

( ) ( ) ( ) ( ) ...16601

2201

151 325 ++++= xxxxFx (3.7)

unde, pentru comparaie, au fost reinui numai termenii pn la rangul 3, ca i mai nainte. n figura 3.2 sunt reprezentate variaiile acelorai elemente ca i n cazul funciei anterioare.

-10

-5

0

5

10

15

20

25

30

35

0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2

rang 0

rang 1

rang 2

rang 3

F(x)

f(x)

Fig.3.2.

Dumitru lavrenteRectangle


e6540Calloutrang 0

e6540Calloutrang 1

e6540Calloutrang 2

e6540Calloutrang 3

e6540Rectangle

e6540Rectangle


Se poate observa c, n raport cu natura funciei aproximate, precizia de aproximare la acelai numr de termeni ai seriei poate varia, sau altfel spus, pentru o aceeai precizie de aproximare, diferite funcii pot necesita un numr diferit de termeni ai sumei de aproximare.

Pentru o funcie de mai multe variabile (x1,,xm), dezvoltarea n serie Taylor n jurul unui punct (x01,,x0m) se poate generaliza sub forma:

( ) ( ) ( )( )

=

++

=

=

0 ...1

...

1

0011

01

001

1

11

1...!!...

......,...,m

m

m

mm

n xxnm

n

nn

m

nmm

n

nm xx

fnn

xxxxxxf (3.8)

Pentru o funcie de dou variabile, m=2, x1=x, x2=y, n punctul x=a, y=b, seria Taylor este:

( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( )( ) ( ) ( ) ( )[ ] ...,,2,

!21

,,,,

22 +++++++=

bafbybafbyaxbafax

bafbybafaxbafyxf

yyxyxx

yx

(3.9)

Aa cum o sugereaz dezvoltarea n serie Taylor, diversele funcii din practica inginereasc pot fi aproximate prin sume polinomiale. n capitolele urmtoare vom ntlni diveri algoritmi bazai pe aceast idee.

3.2. Evaluarea polinoamelor

Dup cum se observ, dezvoltarea n serie a funciilor conduce la expresii de form polinomial. Evaluarea funciilor de tip polinomial reprezint una din problemele frecvent ntlnite n cadrul analizei numerice. Fie polinomul de grad n

P(x) = ao + a1x + a2x2 + ... + an-1xn-1 + anxn (3.10)

sau n form condensat:

P(x) = {A}T {X}

unde vectorul coeficienilor polinomului este:

{A}T ={ao a1 a2 ... an-1 an} cu A(i) = ai, i = 0 ... n

iar vectorul argumentului

{X}T = {1 x x2 ... xn-1 xn} cu X(i) = xi i = 0 ... n

Prin algoritmi recursivi care evit ridicrile directe la putere i minimizeaz numrul de operaii, se pot calcula:

a) Valoarea polinomului P(x0)

Scriind P(x) dat de relaia (3.10) n forma:

P(x) = a0+(a1+(a2+(...+(an-1+(an)x)x)...)x)x)x



se poate realiza un algoritm prin operaii succesive pornind de la an. Avantajul acestei scheme de calcul (care provine din schema lui Horner) este acela de a evita ridicrile la putere repetate folosind n locul lor numai nmuliri.

Algoritm - calculul valorii unui polinom Date: n, {A}, xo Rezultate: P = valoarea polinomului n xo

P = A(n) pentru i = n-1 la 0 calculeaz

P = A(i) + P xo

b) Valoarea derivatei dPdx n x = x0

Algoritm - calculul valorii derivatei unui polinom Date: n, {A}, xo Rezultate: DP valoarea derivatei n xo

DP = n A(n) pentru i = n-1 la 1 calculeaz

DP =i A(i) + DP xo

c) Valoarea integralei p x dxa

b

( )Algoritm - calculul integralei definite dintr-o funcie polinom

Date: n, {A}, a, b Rezultate: IP - valoarea integralei definite

IP1 = A(n) / (n+1) IP2 = IP1 pentru i = n la 1 calculeaz

IP1 = A(i-1) / i + IP1 a IP2 = A(i-1) / i + IP2 b

IP = IP2 b - IP1 a

Pentru algoritmii de calcul a derivatei i integralei definite, programarea este asemntoare cu programul de evaluare a valorii polinomului

Algoritmii prezentai de evaluarea polinoamelor au avantajul de a fi compaci dar au dezavantajul de a utiliza operaii recursive. Pentru grade nalte ale polinomului, caracterul recursiv al acestor algoritmi produce probleme serioase de propagare a erorilor (de exemplu, termenul A(i) poate fi ignorat la adunare, putnd fi mult mai mic dect P xo). O astfel de situaie poate fi eliminat prin urmtoarea secven de operaii:

- se genereaz separat toi termenii polinomului, rezultnd irul : {T} = {to, t1, ..tn}, unde ti = ai x0i, i = 0 ... n; - se ordoneaz cresctor irul {T}; - se nsumeaz termenii irului ordonat, suma efectuat de la termeni mici spre cei

mari reducnd propagarea erorilor de trunchiere. Deoarece algoritmii de ordonare a irurilor sunt frecvent utilizai, se prezint un astfel

de exemplu.

Scrie: 'valoarea polinomului este' P

Scrie: 'valoarea derivatei polinomului este' DP

DP(x) = a1 + 2a2x + 3a3x2... + n anxn-1

Scrie: 'valoare integrarii polinomului este' IP

IP(x) = a0 x+ a1x2/2+a2x3/3 + ... + anxn+1/(n+1)a

b

DP(x) = a1+(2a2+(...+(nan)x)x)...)x)x

IP(x) = (a0+(a1/2+(...+(an/(n+1))x)x)...)x)xa

b

Dumitru lavrenteLine

e6540Linie poligonal



e6540Line

e6540Line


Algoritm - ordonarea cresctoare a unui ir Date: n dimensiunea irului

t(i) i = 0...n irul de ordonat Rezultate: t(i) irul ordonat cresctor

pentru i = 0 la n-1 execut pentru j = i+1 la n execut

dac t(i) > t(j) atunci a = t(i) t(i) = t(j) t(j) = a

Obs.: Ordonarea descresctoare presupune numai schimbarea sensului inegalitii din testul de comparaie.

3.3 Algoritmi iterativi Un principiu fundamental al metodelor numerice l constituie iteratia. Procesul iterativ

este un proces care se repeta pna cnd un test de oprire impus este satisfacut. Tehnicile iterative se utilizeaz n principal la determinarea rdcinilor ecuatiilor algebrice i difereniale.

Pentru derularea unui algoritm iterativ este necesar cunoasterea unei reguli sau funcii g(x) i a unui punct de start po. Secvena de determinare a punctelor pi (i=1, 2 ...) se bazeaz pe relaia:

pi+1 = g(pi) i = 0, 1, ... (3.11)

O problema esentiala a oricrui algoritm iterativ o constituie convergenta acestuia, respectiv ca punctul de evaluare pi dat de relatia (3.11) sa ramn finit cnd i tinde la infinit.

Fie P un punct de evaluare astfel nct P = g(P). Dac funcia g(x) este continua si secventa generata de relatia (3.11) converge la P, acesta este punct fix al functiei g(x). Dac funciile g(x) si derivatele acestora g'(x) sunt continue pe intervalul [a,b] care conine punctul fix P i presupunnd ca punctul de start po este suficient de aproape de P, atunci conditia de convergenta a secventei (3.11) este:

| g'(P) | < 1 (3.12)

Interpretarea grafica a secventei (3.11) i a condiiei (3.12) sunt date n figura 3.3. Se constata usor ca punctul fix P se afla la intersectia dreptei y = x cu curba y = g(x).

n raport cu alura functiei g(x) n vecinatatea lui P, pot fi ntlnite situatii de convergenta (fig. 3.3.a) sau divergenta (fig 3.3.b). Convergenta (divergenta) pot fi monotone sau alternante dupa cum se produc de o parte sau de ambele parti ale functiei.

O alta problema a aplicarii algoritmilor iterativi o constituie criteriul de oprire al iteratiilor. n principiu, procesul iterativ va fi oprit atunci cnd pi constituie o "buna" aproximare a punctului P. Din pacate valoarea P este necunoscuta si ca atare nu poate fi folosita n stabilirea criteriilor de oprire. Pentru rezolvarea acestei probleme exista doua posibilitati care pot fi folosite separat sau mpreuna:

Scrie: 'sirul ordonat este' IP





a) convergenta b) divergenta

Fig. 3.3.

a) test de eroare asupra argumentului - consta n evaluarea distantei dintre doua puncte deevaluare pi i pi+1 consecutive. Pentru a evita influenta valorii absolute a argumentului, este indicata utilizarea erorii relative i nu a celei absolute. Pentru aceasta fie ex un numar pozitiv mic, acceptat ca limita superioara a erorii relative admisibile a procesului iterativ.

Procesul iterativ se poate considera finalizat cnd:

xi

ii ep

pp +

+11

(3.13)

si se accepta solutia P ~ pi+1. Testul dat de relatia (3.13) nu da ntotdeauna rezultate bune, pe de o parte datorita

posibilitatii de a ntlni forme de functii la care ntr-o anumita poriune relatia (3.13) sa fie ndeplinita departe de punctul fix P, iar pe de alta parte datorita modului arbitrar de alegere a valorii ex. Este putin probabil ca aceeasi valoare ex (de exemplu 0.000001) sa fie corecta n toate aplicatiile, iar pe de alta parte micsorarea exagerata a lui ex poate prin cresterea numarului de iteratii sa faciliteze propagarea erorilor de trunchiere si prin acestea imposibilitatea rezolvarii problemei. Pentru o eroare de 10-q, exponentul q va fi ales cu cel putin 2 mai mic dect numarul de cifre semnificative ale reprezentarii numerelor utilizate n calcule.

b) test de eroare asupra valorii functiei - daca n punctul fix P exista relatia P=g(P),atunci functia f(x) = x - g(x) va ndeplini conditia f(P) = 0. Prin acest rationament, se poate introduce o eroare ef asupra valorilor absolute ale functiei f(x), astfel nct procesul iterativ sa fie considerat ncheiat atunci cnd n punctul de evaluare pi se ndeplineste relatia:

| f(pi) | < ef (3.14)

Ca o observatie, n procesul iterativ dat de relatia (3.11), relatia (3.14) este echivalenta cu testul de eroare absoluta asupra argumentului. Nici acest test nu da rezultate bune ntotdeauna, relatia (3.14) putnd fi ndeplinita departe de P pentru functii plate n vecinatatea solutiei, iar pe de alta parte datorita alegerii arbitrare a erorii ef.

Ca o concluzie, se poate arata ca alegerea tipului de test si a valorii erorilor absolute sau relative reprezinta un punct sensibil al oricarui algoritm iterativ. Aceste optiuni trebuie analizate de la caz la caz, de ele depinznd n mare masura succesul aplicatiei.


Algoritm proces iterativ Date: g(x) - functia

ITMAX - numar maxim de iteratii admis ex,ef - erorile relative admise xo - punctul de start al iteratiilor

Rezultate: X - solutia procesului iterativ cod - cod de eroare al rezolvarii

0 - solutia satisface ambele teste de eroare 1 - solutia satisface numai eroarea asupra argumentului 2 - solutia satisface numai eroarea asupra functiei 3 - proces divergent

IT = 0gata = false x1 = g(x0)dx1 = | x1 - x0 | repeta IT = IT + 1 x2 = g(x1) dx2 = | x2 - x1 | daca dx2 >= dx1 atunci cod = 3 gata = true daca IT > ITMAX atunci cod = 3 gata = true daca | (x2-x1)/x2 | < ex atunci cod = 1 daca | x1 - g(x1) | < ef atunci cod = 2 daca ( | (x2-x1)/x2 | < ex ) si ( | x1 - g(x1) | < ef) atunci cod = 0 gata = true x1 = x2 dx1 = dx2 pn cnd gata=trueX = x2dupa cod executa 0: scrie ( Solutia X obtinuta dupa IT iteratii si satisface eroarea asupra argumentului si asupra functiei) 1: scrie ( Solutia X obtinuta dupa IT iteratii si satisface numai eroarea asupra argumentului ) 2: scrie ( Solutia X obtinuta dupa IT iteratii si satisface numai eroarea asupra functiei ) 3: scrie ( Proces divergent la iteratia IT)

e6540Polygonal Line

e6540Polygonal Line

e6540Polygonal Line

e6540Polygonal Line

e6540Polygonal Line

e6540Polygonal Line

e6540Polygonal Line

Algoritm - calculul integralei definite dintr-o func(ie polinom

Curs 2 Cap3 SerTaylor EvalPolin

Documents

Transcript of Curs 2 Cap3 SerTaylor EvalPolin