Metode Mumerice 06-07

1METODE NUMERICEMETODE NUMERICESI PROGRAMRE LINIARA SI PROGRAMRE LINIARA 0606--0707

FACULTATEA DE INGINERIE FACULTATEA DE INGINERIE AEROSPATIALAAEROSPATIALA

DERIVAREA NUMERICADERIVAREA NUMERICA

O formul pentru derivarea numeric a funcO formul pentru derivarea numeric a funciei iei f(x)f(x) se obse obine utiliznd o aproximant ine utiliznd o aproximant g(x)g(x) i i restul restul R(x)R(x) corespunztor corespunztor, sub forma:, sub forma:

n relan relaia ia de de maimai sussus, , va furniza expresia va furniza expresia efectiv de calcul numeric al derivatei efectiv de calcul numeric al derivatei aproximative, iar aproximative, iar va fi utilizat la va fi utilizat la evaluarea erorii de derivare.evaluarea erorii de derivare.

df dg dRdx dx dx

dgdx

dRdx


Spre deosebire de integrarea Spre deosebire de integrarea numericnumeric, opera, operaie ie n care exist o n care exist o tendintendin de atenuare a erorii de atenuare a erorii, , derivarea numeric are o tendinderivarea numeric are o tendin de de amplificare a erorii.amplificare a erorii.


De aceea, De aceea, n cazul derivrii numerice se n cazul derivrii numerice se recomand luarea unor msuri de precaurecomand luarea unor msuri de precauie, ie, cum ar fi:cum ar fi:

evitarea utilizrii aproximantelor evitarea utilizrii aproximantelor g(x)g(x) care care au oscilaau oscilaii ii n zona de calcul; n zona de calcul; n particular,n particular, se prefer polinoame de interpolare de grad se prefer polinoame de interpolare de grad mic (1,2, cel mult 3);mic (1,2, cel mult 3);

punctul de calcul s fie centrat punctul de calcul s fie centrat, , n raport n raport cu diviziunile utilizate;cu diviziunile utilizate;

calculul derivatei prin dou sau mai multe calculul derivatei prin dou sau mai multe ci diferite ci diferite i compararea rezultatelor.i compararea rezultatelor.


Cazul interpolrii polinomialeCazul interpolrii polinomiale..n acest caz, aproximanta n acest caz, aproximanta g(x)g(x) este un este un polinom. Presupunnd polinom. Presupunnd cazulcazul diviziunidiviziunilorloregale, de pas egale, de pas hh, vom nota cu , vom nota cu pprr,,ii--11polinomul Newton cu diferenpolinomul Newton cu diferene finite de e finite de gradul gradul rr , cu punctul de plecare , cu punctul de plecare xxii--11


Introducnd variabila adimensional Introducnd variabila adimensional definitdefinit, prin rela, prin relaiaia::

se obse obine aproximantaine aproximanta::

cu restulcu restul dat dedat de::

1ix x h

1, 1 1 1 1... rr i i i ig x p y C y C y 11 1, 1 1 1 1, , .rr rr i i i iR x R h C f x x

2DERIVAREA NUMERICADERIVAREA NUMERICA

reprezintreprezint coeficien coeficienii binomiali ii binomiali (generaliza(generalizai), iar i), iar este operatorul este operatorul diferendiferen finit la dreapta finit la dreapta. .

Introducnd Introducnd n relan relaia ia de de derivarederivare iniiniialial expresiilexpresiilee de mai sus de mai sus, r, rezult derivataezult derivata::

, 1, 2...rC r

1, 1' 1 11 (1)rr i r r idpdf dy h C fdx h d d


DinDin relarelaiaia anterioaranterioar, s, se observ c e observ c eroarea la derivare are ordinul de eroarea la derivare are ordinul de mrime mrime OO ((h h rr ), fa), fa de interpolare de interpolare care are o eroare de ordinul care are o eroare de ordinul OO ((h h r+1r+1). ). Pentru reducerea erorii la derivare Pentru reducerea erorii la derivare avem la dispoziavem la dispoziie 2 parametri: gradul ie 2 parametri: gradul rr al polinomului al polinomului i punctul de start i punctul de start xxii--11 ; cu ultimul parametru putem ; cu ultimul parametru putem realiza centrarea.realiza centrarea.


Derivata polinomului are expresia:Derivata polinomului are expresia:

Pentru Pentru rr = 1, = 1, , se ob, se obine:ine:

, 1 21 1 1

1 1 1 ...2

rr i r

i i i

dp dCy y yh d h d

0,1

' 2 "1 1 ( 2)i iy dy h C fh d


n particular, n particular, din din relarelaiaia anterioaranterioar, se pot , se pot obobine derivatele ine derivatele n n xxii--11 (pentru(pentru ) ) i i n n xxii(pentru(pentru ):):

Rezult cRezult c, la interpolarea cu , la interpolarea cu rr = = 1, 1, derivatele derivatele sunt egale, cusunt egale, cu o marj de eroare de ordinul o marj de eroare de ordinulOO ((hh).).

' " ' '11 1 1 1, , (3)2i ii i i i iy y hy f x xh ' " " "1 1 1 1, , ( 4)2i ii i i i iy y hy f x xh

0 1


Pentru Pentru rr = = 22, , , se ob, se obine ine derivata derivata yy sub forma:sub forma:

0, 2

' 2 2 3 "1 1 11 1 (5)2i i idy y y h C fh d


n nodurile n nodurile xxii--11 , , xxii , se ob, se obin derivatele de in derivatele de ordinul ordinul nti, avnd expresiile:nti, avnd expresiile:

Se observ c eroarea este mai mic pentru Se observ c eroarea este mai mic pentru derivata derivata (circa (circa jumtatejumtate, , n modul), n modul), deoarece punctul deoarece punctul xxii este centrat este centrat n intervalul n intervalul

21 11 13 4 0 , (6)2 3i i ii iy y y hy fh

21 1 1' 1 . (7 )2 6i ii iy y hy fh 'iy

1 1, .i ix x

3DERIVAREA NUMERICADERIVAREA NUMERICA

Pentru a obPentru a obine derivata de ordinul 2, ine derivata de ordinul 2, yy , e, este ste necesar interpolarea cu un polinom de grad cel punecesar interpolarea cu un polinom de grad cel puin in 2 (2 (rr 2).2).

Lund Lund rr = = 33 i derivnd expresia i derivnd expresia nc o datnc o dat, se , se obobin urmtoarele in urmtoarele relarelaiiii pentru derivatele pentru derivatele n nodurile n nodurile xxii--11 i i xxii ::

2 3421 1

1 12 2

421 1 212

11 012 (8)

2 5 4 11 012

i ii i

i i i ii

y yy h fh hy y y y h f

h

2 2 24 41 1 11 12 221 1 . (9)12 12i i i ii i iy y y yh hy f fh h


Comparnd expresiile (Comparnd expresiile (88) ) i (i (99), ), se observ se observ c precizia derivatei de ordinul c precizia derivatei de ordinul 2 e2 este cu un ste cu un ordin de mrime mai bun ordin de mrime mai bun n punctul n punctul centrat centrat xxii , de, dei valorile numerice i valorile numerice (aproximative) sunt egale.(aproximative) sunt egale.

Expresii similare pentru derivate se obExpresii similare pentru derivate se obin in utiliznd utiliznd i alte aproximante i alte aproximante g(x)g(x) : : polinoame mini polinoame mini max sau polinoame de max sau polinoame de aproximare aproximare n sensul celor mai mici ptraten sensul celor mai mici ptrate, , etc.etc.


Exemplu de calculExemplu de calcul S se calculeze derivatele S se calculeze derivatele yy i i yy ale funcale funciei:iei: n punctul n punctul xx00 = = 2.5. 2.5. S se studieze influenS se studieze influena pasului a pasului i a i a pozipoziionrii punctului faionrii punctului fa de re de reeaua eaua de noduri aleas pentru de noduri aleas pentru rr = 1 = 1 i i rr = 2.= 2.

2 ,x

y e


RezolvareRezolvare::Se consider intervalele Se consider intervalele [2; [2; 44] cu pasul ] cu pasul 0.50, 0.50, i apoi [2.25; 3i apoi [2.25; 3.25.25] c] cu pasul 0u pasul 0.25 .25 . S. Se utilizeaz formulele e utilizeaz formulele (4) pentru (4) pentru rr = 1, = 1, i (6) i (6) -- (9) pentru (9) pentru rr = = 33. . Rezultatele calculelor sunt date Rezultatele calculelor sunt date n n Tabelul Tabelul urmurmtortor..


0.872590.873720.858231.745171.749721.735181.640500.25

0.872590.877140.806381.745171.763411.701121.544120.50

Exact(9)(8)

Exact(7)(6)(4)

y, formula:y, formula:

h

Calculul derivatelor numerice


Valorile din Valorile din ttabelul abelul anterioranterior confirm confirm aateptrile teoretice cu privire la teptrile teoretice cu privire la ordinul de mrime al erorii ordinul de mrime al erorii n funcn funcie ie de gradul polinomului de interpolare de gradul polinomului de interpolare ((rr ) ) i de centrarea punctului de i de centrarea punctului de calcul.calcul.

4CURS 07CURS 07 Rezolvarea numeric a ecuaRezolvarea numeric a ecuaiilor iilor algebrice algebrice i transcendentei transcendente n continuare, n continuare, vomvom oferioferi metode metode

numerice pentru gsirea rdcinilor numerice pentru gsirea rdcinilor unor funcunor funcii de variabil realii de variabil real. V. Vom om arta cum pot fi calculate rdcinile arta cum pot fi calculate rdcinile reale dintrreale dintr--un interval dat [un interval dat [aa, , bb], ], cu o cu o precizie satisfctoareprecizie satisfctoare; ; n cazul n cazul polinoamelor cu coeficienpolinoamelor cu coeficieni reali se pot i reali se pot da da i metode pentru gsirea i metode pentru gsirea rdcinilor complexerdcinilor complexe..

Rezolvarea numeric a ecuaRezolvarea numeric a ecuaiilor iilor algebrice algebrice i transcendentei transcendente ExistenExistena rdcinilor realea rdcinilor reale..

Fie Fie o funco funcie de variabil ie de variabil real xreal x, d, definit pe intervalul efinit pe intervalul [a, [a, b], b], continu continu i derivabili derivabil. D. Dac ac este o rdcin real a funceste o rdcin real a funciei F(x), iei F(x), avem, prin definiavem, prin definiie:ie:

, ,F x x a b

,a b

0F

Rezolvarea numeric a ecuaRezolvarea numeric a ecuaiilor iilor algebrice algebrice i transcendentei transcendente Pentru a verifica existenPentru a verifica existena rdcinii a rdcinii

reale, reale, , vom diviza intervalul [, vom diviza intervalul [aa, , bb] ] n n NN pr pri prin punctele de diviziune i prin punctele de diviziune

, echidistante, cu pasul , echidistante, cu pasul hh. . Vom nota:Vom nota:

, 1,ix i N

0 1; , 1, , ;i i Nb ax a x x h i N x b hN

Rezolvarea numeric a ecuaRezolvarea numeric a ecuaiilor iilor algebrice algebrice i transcendentei transcendente Se calculeaz apoi produseleSe calculeaz apoi produsele::

Admitem c cel puAdmitem c cel puin unul din produse, fie in unul din produse, fie acesta acesta ppkk , e, este negativ, aste negativ, adicdic::

Ca urmare, Ca urmare, n intervalul (n intervalul (xxkk--11, , xxkk) e) exist cel xist cel pupuin o rdcin realin o rdcin real..

1 , 1,i i ip F x F x i N

1 0.k k kp F x F x

Rezolvarea numeric a ecuaRezolvarea numeric a ecuaiilor iilor algebrice algebrice i transcendentei transcendente Determinarea rdciniiDeterminarea rdcinii cu o precizie dorit cu o precizie dorit

se face prin cutarea se face prin cutarea n intervalul de n intervalul de existenexisten ((xxkk--11, , xxkk) a) a unui numr unui numr , astfel , astfel nct, pentru nct, pentru suficient de mici suficient de mici (corespun(corespunztor unei precizii impuseztor unei precizii impuse), ), s s avem:avem:

Pentru realizarea obiectivului propus avem Pentru realizarea obiectivului propus avem la dispozila dispoziie mai multe metode, ie mai multe metode, treitrei dintre dintre ele fiind prezentate ele fiind prezentate n continuare.n continuare.

1,2 0

1 1 1 2, , ,k k k kF x x x x

5Rezolvarea numeric a ecuaRezolvarea numeric a ecuaiilor iilor algebrice algebrice i transcendentei transcendente Metoda Metoda njumtnjumtirii intervaluluiirii intervalului

Este o metod simpl Este o metod simpl i sigur care i sigur care necesit doar continuitatea funcnecesit doar continuitatea funciei iei F(x)F(x).. Se calculeaz mijlocul Se calculeaz mijlocul xxmm al al intervalului intervalului n care sn care s--a detectat a detectat o o schimbare de semnschimbare de semn..

1

2k k

mx xx

Rezolvarea numeric a ecuaRezolvarea numeric a ecuaiilor iilor algebrice algebrice i transcendentei transcendente Mai departe, sMai departe, se calculeaz e calculeaz FF ((xxmm ); ); dac dac

, vom avea una din situa, vom avea una din situaiile:iile:

n oricare din situan oricare din situaiiii problema sproblema s--a redus la a redus la situasituaia precedentia precedent, a, adic rdcina se gsedic rdcina se gsete te pe un interval de lungime redus la jumtatepe un interval de lungime redus la jumtate. . n primul cazn primul caz se se nlocuienlocuiete te ; ; n al n al doilea caz, se face schimbarea doilea caz, se face schimbarea i se i se revine larevine la o o nouanoua injuminjumttire.ire.

mF x 10 sau 0m k m kF x F x F x F x

01 km xFxF

1k mx x k mx x

Rezolvarea numeric a ecuaRezolvarea numeric a ecuaiilor iilor algebrice algebrice i transcendentei transcendente Procedeul se repet de Procedeul se repet de nn ori (funcori (funcie deie de

) p) pn cnd sunt satisfcute condin cnd sunt satisfcute condiiileiile de de atingereatingere a a precizieipreciziei, , sub forma:sub forma:

1,2

1 1 2; ;m k k mF x x x x

Rezolvarea numeric a ecuaRezolvarea numeric a ecuaiilor iilor algebrice algebrice i transcendentei transcendente MetodaMetoda secantei (a coardei)secantei (a coardei)Viteza de convergenViteza de convergen cre crete fate fa de de

procedeul de procedeul de njumtnjumtire a intervalului ire a intervalului lund punctul de interseclund punctul de intersecie, ie, xxss , cu axa , cu axa OXOX a secantei (a coardei) care unea secantei (a coardei) care unete te punctele punctele .. 1 1, , ,k k k kA x F x B x F x

Rezolvarea numeric a ecuaRezolvarea numeric a ecuaiilor iilor algebrice algebrice i transcendentei transcendente MetodaMetoda secanteisecantei

Rezolvarea numeric a ecuaRezolvarea numeric a ecuaiilor iilor algebrice algebrice i transcendentei transcendenteEcuaEcuaia dreptei (ia dreptei (ABAB ) este:) este:

IntersecIntersecia dreptei (ia dreptei (ABAB ) cu ) cu OXOX ne d ne d punctul cu coordonatele punctul cu coordonatele yy = 0, = 0, xx = = xxss, , unde:unde:

1 1 11 1 ; 0k k

k kk k k k

y F x x xAB F x F xF x F x x x

1 11 11 ; 0k k k

s k k kk k

F x x xx x F x F x

F x F x

6Rezolvarea numeric a ecuaRezolvarea numeric a ecuaiilor iilor algebrice algebrice i transcendentei transcendente SSe calculeaz e calculeaz FF ((xxss)): : dac dac se ia se ia ;; dac dac se se nlocuienlocuiete te i se revine la relai se revine la relaia ia de de calculcalcul xxss ntrntr--o o nou iteranou iteraie;ie; dac dac , se , se nlocuienlocuietetei se trece la o nou iterai se trece la o nou iteraie, folosind ie, folosind relarelaia ia de de calculcalcul xxss ..

1,sF x sx 0,s kF x F x 1k sx x

1 0k sF x F x k sx x

Rezolvarea numeric a ecuaRezolvarea numeric a ecuaiilor iilor algebrice algebrice i transcendentei transcendente Metoda tangentei Metoda tangentei (Metoda Newton (Metoda Newton -- Raphson)Raphson)Pornind de la schimbarea de semn care ne Pornind de la schimbarea de semn care ne

asigur existenasigur existena unei rdcini a unei rdcini n n intervalul intervalul , , dac dac F(x)F(x) este este derivabilderivabil, e, exist tangenta la curba xist tangenta la curba yy = = F(x),F(x), n intervalul precizat.n intervalul precizat.

1,k kx x

Rezolvarea numeric a ecuaRezolvarea numeric a ecuaiilor iilor algebrice algebrice i transcendentei transcendente Construim tangenta la curb Construim tangenta la curb n unul din n unul din

capetele intervalului, capetele intervalului, sau sau , , i cutm punctul de i cutm punctul de

intersecintersecie ie xxtt al tangentei alese cu axa al tangentei alese cu axa OXOX. Condi. Condiia iniia iniial este ca ial este ca

1 1,k kA x F x ,k kB x F x 1, .t k kx x x

Rezolvarea numeric a ecuaRezolvarea numeric a ecuaiilor iilor algebrice algebrice i transcendentei transcendente Dac acest lucru nu se Dac acest lucru nu se ntmpl pentru ntmpl pentru

nici una din cele dou tangentenici una din cele dou tangente, s, se aplic e aplic metoda metoda njumtnjumtirii intervalului sau irii intervalului sau metoda secantei metoda secantei i se duce tangenta i se duce tangenta n n unul din punctele unul din punctele sausau . . ,m mx F x ,s sx F x

Rezolvarea numeric a ecuaRezolvarea numeric a ecuaiilor iilor algebrice algebrice i transcendentei transcendente MetodaMetoda Newton Newton -- RaphsonRaphson

Rezolvarea numeric a ecuaRezolvarea numeric a ecuaiilor iilor algebrice algebrice i transcendentei transcendente Se calculeaz Se calculeaz F(xF(xtt )) i, i, dac dac , s, se e

repet procedeul pentru repet procedeul pentru Coordonata Coordonata xxtt a punctului de interseca punctului de intersecie ie

cu cu OXOX a tangentei se oba tangentei se obine folosind ine folosind ecuaecuaia dreptei tangenteiia dreptei tangentei,, tangent tangent ( ( T T ) ) n punctul n punctul BB ::

tF x k tx x

'k k kT y F x F x x x

7Rezolvarea numeric a ecuaRezolvarea numeric a ecuaiilor iilor algebrice algebrice i transcendentei transcendente LuLund nd yy = 0,= 0, pentrupentru xx = = xxtt nn ecuaecuaia ia

dreptei tangentei rezultdreptei tangentei rezult::

AceastAceast eexpresixpresiee se numese numete te iiformula iterativ Newton formula iterativ Newton RaphsonRaphson..

'1 ' , 0.kt k k kk

F xx x x F x

F x

Rezolvarea numeric a ecuaRezolvarea numeric a ecuaiilor iilor algebrice algebrice i transcendentei transcendente Viteza de convergenViteza de convergen a unei metode a unei metode

interative se defineinterative se definete calculnd, te calculnd, la la limitlimit, raportul:, raportul:

11, 1 convergenta liniara

lim 0; , 1,2 , convergenta superliniara2, convergeta patratica

kmk

k

mx

mx m

Rezolvarea numeric a ecuaRezolvarea numeric a ecuaiilor iilor algebrice algebrice i transcendentei transcendente Spre exemplu, metoda Spre exemplu, metoda njumtnjumtirii irii

intervalului are vitez de convergenintervalului are vitez de convergen liniarliniar; m; metoda secantei (coaretoda secantei (coardei) ardei) are e vitez de convergenvitez de convergen superliniar superliniar. . n n continuare, vom acontinuare, vom arta c metoda rta c metoda NewtonNewton--Raphson are viteza de Raphson are viteza de convergenconvergen ptratic ptratic (meto(metod de d de ordinul 2). ordinul 2).

Rezolvarea numeric a ecuaRezolvarea numeric a ecuaiilor iilor algebrice algebrice i transcendentei transcendente n acest scop,n acest scop, vom presupune c este vom presupune c este

derivabil de dou oriderivabil de dou ori, , i vom aplica i vom aplica formula lui Taylor, sub forma:formula lui Taylor, sub forma:

LuLund nd ( ( rdcin realrdcin real ), se ), se obobine:ine:

2

' '' , ,2

kk k k k k k

x xF x F x x x F x F x x

2

' "02

kk k k k

xF x x F x F

x

Rezolvarea numeric a ecuaRezolvarea numeric a ecuaiilor iilor algebrice algebrice i transcendentei transcendente innd cont de formula iterativ innd cont de formula iterativ

Newton Newton RaphsonRaphson obobineinem:m:

SSe confirm c metoda Newtone confirm c metoda Newton--Raphson are convergenRaphson are convergen ptratic ptratic. .

2'' ' ''

1 ' , 0,2k

k k k kk

xx F F x F

F x

Rezolvarea numeric a ecuaRezolvarea numeric a ecuaiilor iilor algebrice algebrice i transcendentei transcendente Notnd mai departe cu:Notnd mai departe cu:

FolosindFolosind relarelaiaia anterioaranterioar se deduce:se deduce:

''

',

sup , , ,2k k

kk k

x k

FM x a b

F x

21 , 0,1,2,.......k kx M x k

8Rezolvarea numeric a ecuaRezolvarea numeric a ecuaiilor iilor algebrice algebrice i transcendentei transcendente

Plecnd cu o valoare iniPlecnd cu o valoare iniial ial xx0 0 n interan interaia 1 se ia 1 se obobine:ine:

iar iar n interan interaia ia (k+1)(k+1)::

se deduce c o se deduce c o condicondiie suficient ie suficient pepentruntruconvergenconvergena a irului irului xxk+1k+1 ctre rdcina ctre rdcina este:este:

122 11 0 0 , ,x M x M M x M

1211 0 ,kkx M M x M

0 1M x

Rezolvarea numeric a ecuaRezolvarea numeric a ecuaiilor iilor algebrice algebrice i transcendentei transcendente

PrinPrin urmareurmare, , metoda Newtonmetoda Newton--Raphson Raphson converge converge doardoar dac plecm dintrdac plecm dintr--o o vecintate suficient de micvecintate suficient de mic a rdcinii a rdcinii. . Se spune c metoda are Se spune c metoda are convergenconvergen locallocal..

Metode Mumerice 06-07

Documents

Transcript of Metode Mumerice 06-07