Nicolae Danet Curs an 2004

257
ANALIZ ¼ A NUMERIC ¼ A Cu aplica¸tii rezolvate în Mathcad Nicolae D¼ ane¸t Universitatea Tehnic¼ a de Construc¸tii Bucure¸ sti Catedra de Matematic¼ a Octombrie, 2004

Transcript of Nicolae Danet Curs an 2004

  • ANALIZA NUMERICACu aplicatii rezolvate n Mathcad

    Nicolae DanetUniversitatea Tehnica de Constructii Bucuresti

    Catedra de Matematica

    Octombrie, 2004

  • ii

  • Cuprins

    Prefata la editia electronica v

    Prefata editiei tiparite n 2002 vii

    1 INTERPOLAREA FUNCTIILOR 11.1 Interpolare polinomiala . . . . . . . . . . . . . . . . . . . . . . . . 3

    1.1.1 Polinomul de interpolare Lagrange . . . . . . . . . . . . . 41.1.2 Algoritmul lui Aitken . . . . . . . . . . . . . . . . . . . . . 121.1.3 Diferente divizate.

    Polinomul Newton cu diferente divizate . . . . . . . . . . . 151.1.4 Diferente nite.

    Polinomul Newton cu diferente nite . . . . . . . . . . . . 251.1.5 Evaluarea erorii n interpolarea polinomiala . . . . . . . . 31

    1.2 Polinoamele Bernstein . . . . . . . . . . . . . . . . . . . . . . . . 361.3 Curbe Bzier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391.4 Problema aproximarii functiilor . . . . . . . . . . . . . . . . . . . 421.5 Interpolare Hermite . . . . . . . . . . . . . . . . . . . . . . . . . . 431.6 Interpolare polinomiala pe portiuni . . . . . . . . . . . . . . . . . 501.7 Functii spline cubice . . . . . . . . . . . . . . . . . . . . . . . . . 541.8 Functii B-spline cubice . . . . . . . . . . . . . . . . . . . . . . . . 61

    2 DERIVARE NUMERICA 652.1 Derivare bazata pe polinomul Lagrange . . . . . . . . . . . . . . . 662.2 Derivare bazata pe polinomul Newton . . . . . . . . . . . . . . . . 73

    3 INTEGRARE NUMERICA 773.1 Formula trapezelor . . . . . . . . . . . . . . . . . . . . . . . . . . 793.2 Formula lui Simpson . . . . . . . . . . . . . . . . . . . . . . . . . 833.3 Formula Newton-Ctes . . . . . . . . . . . . . . . . . . . . . . . . 883.4 Formula lui Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . 913.5 Calculul integralelor duble . . . . . . . . . . . . . . . . . . . . . . 983.6 Calculul integralelor improprii . . . . . . . . . . . . . . . . . . . . 107

    iii

  • iv CUPRINS

    4 INTEGRAREA ECUATIILOR DIFERENTIALE 1154.1 Teorema de existenta si unicitate . . . . . . . . . . . . . . . . . . 1154.2 Metoda Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1164.3 Metoda Taylor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1234.4 Metode de tip Runge-Kutta . . . . . . . . . . . . . . . . . . . . . 1264.5 Metode multipas . . . . . . . . . . . . . . . . . . . . . . . . . . . 1294.6 Metoda Adams-Bashforth-Moulton . . . . . . . . . . . . . . . . . 130

    5 SISTEME DE ECUATII LINIARE 1395.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1395.2 Metode de descompune LU . . . . . . . . . . . . . . . . . . . . . 1415.3 Metoda Crout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1455.4 Matrice pozitiv denite . . . . . . . . . . . . . . . . . . . . . . . . 1485.5 Descompunerea Cholesky . . . . . . . . . . . . . . . . . . . . . . . 1555.6 Sisteme tridiagonale . . . . . . . . . . . . . . . . . . . . . . . . . 1585.7 Metoda lui Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . 1605.8 Norme pentru vectori si matrice . . . . . . . . . . . . . . . . . . . 1665.9 Numarul de conditionare al unei matrice . . . . . . . . . . . . . . 1735.10 Contractii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1785.11 Metoda aproximatiilor succesive . . . . . . . . . . . . . . . . . . . 181

    6 SISTEME DE ECUATII NELINIARE 1936.1 Metoda aproximatiilor succesive . . . . . . . . . . . . . . . . . . . 1936.2 Metoda lui Newton . . . . . . . . . . . . . . . . . . . . . . . . . . 202

    7 PROBLEME CU CONDITII LA LIMITA 2097.1 Metoda diferentelor nite . . . . . . . . . . . . . . . . . . . . . . 2107.2 Metoda colocatiei . . . . . . . . . . . . . . . . . . . . . . . . . . . 2137.3 Metoda lui Galerkin . . . . . . . . . . . . . . . . . . . . . . . . . 216

    8 ECUATII CU DERIVATE PARTIALE 2218.1 Ecuatia caldurii . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2218.2 Ecuatia corzii vibrante . . . . . . . . . . . . . . . . . . . . . . . . 2318.3 Ecuatia Laplace . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238

  • Prefata la editia electronica

    Prezenta versiune electronica reproduce continutul partii nti a cartii tipariteAnaliza numerica - Cu aplicatii rezolvate n Mathcad, care a aparut n anul2002 la editura Matrix Rom Bucuresti. La ea am adaugat doua noi sectiuni:Polinoamele Bernstein si Curbe Bzier, iar alte sectiuni au fost completatecu unele metode noi pe care le-am dezvoltat pe baza calculul simbolic si numericdin Mathcad. Asa au aparut: calculul matriceal al diferentelor divizate (sub-sectiunea 1.1.3) si al diferetelor nite (subsectiunea 1.1.4); calculul integralelorduble pe domenii oarecare folosind formula lui Simpson sau formula lui Gauss(sectiunea 3.5). Alte metode numerice au primit o abordare noua corespunza-toare posibilitatilor oferite de mediul Mathcad (a se vedea, de exemplu, modulde obtinere a formulei lui Gauss pentru calculul unei integrale simple din secti-unea 3.4). Pentru toate aceste completari teoretice am elaborat si noi programeMathcad.

    n cursul anului 2003, folosind sierele Mathcad care au stat la baza tipaririipartii a doua a lucrarii mentionate mai sus si noile siere create pentru com-pletarile facute, am realizat o carte electronica n Mathcad1 intitulataAnaliza numerica - Probleme rezolvate cu Mathcad. Aceasta a fost folositan cursul anului universitar 2003-2004 n cadrul aplicatiilor practice aferentecursului de Analiza numerica pe care l-am predat studentilor din anul doi dela Facultatea Cai Ferate, Drumuri si Poduri din cadrul Universitatii Tehnicede Constructii Bucuresti.

    Publicarea cartii electronice Analiza numerica - Probleme rezolvate cu Math-cad se face n doua variante. Una este varianta originara n Mathcad, care aretoate calitatile unei carti electronice, dar care nu poate folosita dect n mediulMathcad 2001 sau n variantele ulterioare ale acestuia. Pentru cei care nu dis-pund de Mathcad se ofera o varianta n limbajul HTML, care ilustreaza modul ncare se poate folosi mediul Mathcad pentru rezolvarea unor probleme de analizanumerica.

    1Avantajele utilizarii cartilor electronice scrise cu Mathcad sunt prezentate n lucrarea au-torului Crearea si utilizarea cartilor electronice n Mathcad, aparuta n lucrarile simpozionuluiTehnologii educationale pe platforme electronice n nvatamntul ingineresc, 9-10 mai 2003,Universitatea Tehnica de Constructii Bucuresti, Editura Conspress, Bucuresti, 2003, p.301-312.Lucrarea se aa pe acest CD n catalogul Lucrari.

    v

  • vi PREFATA LA EDITIA ELECTRONICA

    Pentru ntelegerea algoritmilor care au fost implementati n Mathcad am con-siderat necesar publicarea pe acelasi CD si a partii teoretice corespunzatoare.Acesta apare n mod compact, sub forma de sierului de fata, sau fragmentatcorespunzator ecarui algoritm. Accesarea fragmentului care corespunde unuialgoritm se face din cartea electronica dnd clic pe cuvintele cheie subliniate.

    Octombrie 2004 Nicolae [email protected]

  • Prefata editiei tiparite n 2002

    Cui se adreseaza aceasta carte?Lucrarea de fata este un text introductiv n ceea ce se numeste, de regula,

    Analiza numerica n programa de studii a viitorilor ingineri. Ea are ca punctde plecare cursul cu acelasi nume predat de autor ncepnd cu anul 1996 laFacultatea de Cai Ferate, Drumuri si Poduri din cadrul Universitatii Tehnicede Constructii Bucuresti. Cartea se adreseaza tuturor celor care vor sa utilizezemetode numerice n rezolvarea unor probleme de matematica, dar n primul rndstudentilor din anul doi de studii din universitatile tehnice.

    Ce contine?n lucrare sunt descrise metode numerice pentru rezolvarea unor probleme din

    urmatoarele domenii:1. Interpolarea functiilor2. Derivare numerica3. Integrare numerica4. Integrarea ecuatiilor diferentiale5. Sisteme de ecuatii liniare6. Sisteme de ecuatii neliniare7. Probleme cu conditii la limita8. Ecuatii cu derivate partialeContinutul n detaliu al ecarui capitol se poate vedea la Cuprins.

    Diversitatea capitolelor abordate provine din necesitatea de a respecta princi-palele directii ale programei analitice.

    Stuctura lucrariiLucrarea este mpartita n doua parti. n prima parte sunt prezentate as-

    pectele teoretice ale rezolvarii problemelor abordate si sunt date exemple simplepentru ntelegerea algoritmilor folositi. La sfrsitul ecarei sectiuni sunt pro-puse cteva probleme de rezolvat pe baza cunostintelor din sectiunea respectiva.Modelele de rezolvare sunt prezentate n sierele Mathcad2 ale caror nume suntindicate la sfrsitul ecarei sectiuni.

    2Mathcad este marca nregistrata a rmei MathSoft, Inc., 101 Main Street, Cambridge, MA02142, USA, http://www.mathcad.com.

    vii

  • viii PREFATA EDITIEI TIPARITE N 2002

    Partea a doua contine un numar de 49 programe Mathcad care ilustreazaalgoritmii prezentati n prima parte.

    De ce Mathcad?Pentru rezolvarea aplicatiilor numerice s-a ales pachetul de programe Mathcad

    din doua motive esentiale.Primul motiv este cel didactic: n Mathcad formulele matematice se scriu cu

    mare usurinta, la fel cum se scriu pe tabla sau pe foaia de hrtie. Aceasta faci-litate face ca Mathcad-ul sa poata nvatat din mers, o data cu cunostintelede Analiza numerica, n cele 28 de ore dedicate activitatilor practice la aceastadisciplina.

    Al doilea motiv este cel economic: o licenta pentru folosirea Mathcad-uluiare un cost mult mai mic n comparatie cu cel al altor pachete de programe decalcul numeric. Aceste doua argumente au prevalat n fata celor de performantade calcul.

    Dupa experienta autorului, majoritatea programelor Mathcad prezentate npartea a doua a cartii pot realizate de studenti concomitent cu nvatarea uti-lizarii Mathcad-ului. O minima introducere n principiile de lucru cu Mathcadeste totusi binevenita. n cadrul Facultatii de Cai Ferate, Drumuri si Poduriea este facuta n anul nti de studii, la cursul de Utilizarea calculatoarelor,prin patru-cinci cursuri consacrate principiilor generale de lucru n Mathcad si autilizarii posibilitatilor grace ale acestuia.

    Conventii folosite n sierele MathcadPentru claritatea programelor Mathcad3 n ecare dintre acestea au fost intro-

    duse multiple zone de text explicativ asupra calculelor care urmeaza a se efectua.n economia unui program zonele de text au numai un rol explicativ. Ele nu con-tribuie cu nimic la partea de calcul si de aceea pot lipsi. Pentru a distinge zonelede text de cele de calcul textele au fost scrise cu caractere italice.

    Cele 49 de programe Mathcad acopera majoritatea tipurilor de probleme acaror prezentare teoretica a fost facuta n prima parte a catii. Cu mici modicarievidente ele pot rezolva ntreaga clasa de probleme pentru care au fost create. nsubsolul paginii ecarui sier Mathcad apare numele sau cu care este mentionatn textul din partea nti.

    Mathcad-ul a fost folosit pentru realizarea pas cu pas a algoritmilor descrisin prima parte a lucrarii si nu ca o cutie neagra. De cele mai multe oris-au folosit instructiuni elementare pentru rezolvarea problemelor. S-a ales aceastacale, n detrimentul folosirii unei singure functii Mathcad care putea realiza ace-lasi lucru, deoarece s-a urmarit n primul rnd ntelegerea algoritmului folosit.S-a considerat ca cine ntelege algoritmul descris pe larg v-a capabil apoi sa

    3Pentru realizarea programelor din aceasta carte se recomanda folosirea versiunii Mathcad2000 sau 2001. Un sier creat cu Mathcad 2001 nu este deschis de Mathcad 2000, cu exceptiacazului n care a fost salvat cu optiunea de Mathcad 2000.

  • ix

    constate singur, folosind Help-ul programului, ca acel algoritm se putea face nMathcad folosind un numat redus de instructiuni.

    Analiza numerica aziPe ntreaga durata de elaborare a acestei lucrari autorul si-a pus multe pro-

    bleme (unele nerezolvate nca) despre cum trebuie predata aceasta disciplinamatematica astazi, cnd calculatorul personal a devenit o realitate cotidiana.Iata unele dintre ele.

    Din multimea de algoritmi consacrati rezolvarii unei clase de probleme, careau fost creati n decursul timpului, la diferite stagii de cunoastere teoretica si dedezvoltarea a tehnicii de calcul, care algoritmi trebuie predati astazi? Cei simplude nteles, dar uneori neperformanti n procesul de calcul, sau cei mai performantinumeric, dar cteodata mai dicil de nteles?

    Cum trebuie folosite pachetele de programe de calcul ca Mathcad-ul sau altelesimilare lui? Ca o cutie neagra? nvatndu-i pe studenti ca pentru rezolvareaacestei probleme se foloseste comanda aceasta, ca datele de intrare se scriu astfeliar datele de iesire se citesc astfel? Sau este mai bine ca sa se faca o rezolvarepas cu pas, cu un control al calculului la ecare etapa, pentru a ntelege mai binecum lucreaza algoritmul respectiv si apoi trecerea la rezolvarea compacta folosindmaximul de performanta al programului respectiv? Dar este timp pentru acestmod de abordare?

    Autorul considera ca astazi predarea separata a metodelor numerice de celeanalitice nu se mai justica. Tratarea unitara este mai adecvata si mai eco-nomica ca timp. Trebuie renuntat la modul traditional de a scoate rezolvareanumerica a unei probleme de la o disciplina si amnata predarea ei un an sauun an si jumatate pna se ajunge la Analiza numerica cnd, de regula, tre-buie reluate premizele teoretice. Metodele numerice trebuie predate la ecaredisciplina matematica nsotite de rezolvarea lor concreta cu ajutorul unui pachetde programe de calcul. n locul unei lucrarii ca Analiza numerica cu Math-cad ar trebui sa apara Algebra liniara cu Mathcad sau Ecuatii diferentiale cuMathcad, etc.

    Cum poate mbunatatita aceasta editie?Constient de o serie de nempliniri ale aceste lucrarii, autorul si propune

    corectarea lor ntr-o viitoare editie. Cteva din dezideratele editiei viitoare ar :a) o analiza teoretica mai amanuntita a tuturor tipurilor de erorii care apar nprocesele de calcul; b) cresterea numarului de exemple care nsotesc prezentareateoretica; c) alegerea unor exemple practice concrete, adevarate studii de caz pen-tru clasa de probleme a caror rezolvare teoretica a fost prezentata; d) includereaunor indicatii si a raspunsurilor la problemele propuse (desi acestea se pot re-zolva usor folosind sierul Mathcad indicat ca model la sfrsitul ecarei sectiuni)pentru a face lucrarea mai accesibila celor interesati de a o folosi ca manual deautoinstruire.

  • x PREFATA EDITIEI TIPARITE N 2002

    Realizarea tehnica a lucrariiLucrare a fost realizata n ntregime de autor. Textul primei parti a fost

    tehnoredactat n LaTeX. Desenele au fost create n Mathcad si ncorporate apoin text. Prin urmare, toate desenele sunt create pe baza unor formule matematicesi nu desenate artistic. Partea a doua este scrisa n ntregime n Mathcad.Pentru tiparirea lucrarii s-au folosit fonduri din contractul de grant 45181/2000,cod CNFIS 68.

    August 2002 Nicolae [email protected]

  • Capitolul 1

    INTERPOLAREAFUNCTIILOR

    Ce nseamna a interpola o functie?

    Se dau n+1 numere reale distincte, x0 < x1 < < xn; situate ntr-un interval[a; b]; numite puncte de interpolare sau noduri, si valorile n aceste puncte ale uneifunctii f :

    f(x0) = f0; f(x1) = f1; : : : ; f (xn) = fn:

    Functia f este necunoscuta. Se cunosc doar valorile sale n punctele de interpo-lare.

    Problema interpolarii functiei f consta n a determina o functie F , numitafunctie de interpolare, care sa satisfaca urmatoarele conditii:

    a) n punctele de interpolare xi functia F ia aceleasi valori ca si functia f; i.e.,

    F (x0) = f0; F (x1) = f1; : : : ; F (xn) = fn:

    b) F apartine unei clase de functii date.

    A apartine unei clase de functii date nseamna, de exemplu:

    1) F este o functie polinomiala pe intervalul [a; b], i.e.,

    F (x) = a0 + a1x+ + amxm; x 2 [a; b];

    unde m este un numar natural si a0; a1; : : : ; am sunt constante reale. n acestcaz interpolarea se numeste interpolare polinomiala. Daca notam cu P ([a; b])multimea functiilor polinomiale denite pe [a; b]; atunci aceasta conditie se scriesimbolic sub forma F 2 P([a; b]):

    2) F este o functie continua pe intervalul [a; b]; i.e.,

    F 2 C([a; b]) = ff : [a; b]! R j f continua pe [a; b]g:

    1

  • 2 CAPITOLUL 1. INTERPOLAREA FUNCTIILOR

    3) F este o functie de clasa C 1 pe intervalul [a; b]; i.e.,

    F 2 C1([a; b]) = ff : [a; b] ! R j f derivabila cu derivata continua [a; b]g:

    La ce serveste functia de interpolare?

    Functia de interpolare F se foloseste pentru a aproxima valorile functiei ne-cunoscute f n puncte x diferite de punctele de interpolare x0; x1; : : : ; xn; i.e.,

    f (x) = F (x); x 6= xi:PuncteleMi(xi; fi); i = 0; 1; : : : ; n; se numesc datele problemei de interpolare saupunctele suport ale problemei de interpolare (xi abscisele suport, fi ordonatelesuport).

    Punctele suport ale problemei de interpolare

    Interpretarea geometrica a problemei de interpolare

    Din punct de vedere geometric, a interpola o functie f nseamna a determinao curba de ecuatie y = F (x); numita curba de interpolare, care sa treaca prinpunctele suport Mi(xi; fi); i = 0; 1; : : : ; n; si care sa apartina unei anumite clasede curbe.

    Curba de interpolare

  • 1.1. INTERPOLARE POLINOMIALA 3

    Pusa sub forma generala problema interpolarii unei functii poate sa nu aibasolutie, sa aiba o singura solutie sau mai multe. n continuare ne vom ocupa deinterpolarea polinomiala.

    1.1 Interpolare polinomiala

    Se considera n+1 numere reale distincte, x0 < x1 < < xn; numite punctede interpolare sau noduri, si valorile n aceste puncte ale unei functii f :

    f(x0) = f0; f(x1) = f1; : : : ; f (xn) = fn:

    Prin interpolare polinomiala se ntelege determinarea unui polinom

    P (x) = a0 + a1x+ a2x2 + + amxm;

    care n punctele de interpolare x0 < x1 < < xn sa ia valorile f0; f1; : : : ; fn:Mai precis,

    P (xi) = fi; i = 0; 1; : : : ; n: (1.1)

    n mod resc se pun ntrebarile: Exista un astfel de polinom? Care estegradul sau? Daca exista, este unic? Cu ce formula se determina P (x) n functiede datele problemei de interpolare? Toate aceste ntrebari vor primi raspuns ncele ce urmeaza.

    Polinomul P (x) depinde de m + 1 parametrii independenti a0; a1; : : : ; am:Deoarece conditiile (1.1) sunt n numar de n + 1, este natural sa consideramm = n pentru a avea un numar de parametrii egal cu numarul de conditii.

    Teorema urmatoare arata ca problema interpolarii polinomiale are solutieunica.

    Teorema 1.1.1 (de existenta si unicitate a polinomului de interpolare) Daten + 1 puncte de interpolare x0 < x1 < < xn si n + 1 valori f0; f1; : : : ; fn;exista un unic polinom Pn(x); de grad mai mic sau egal cu n; astfel nct

    Pn(xi) = fi; i = 0; 1; : : : ; n:

    Demonstratie. A determina polinomul

    Pn(x) = a0 + a1x + a2x2 + + anxn

    astfel nct acesta sa verice conditiile Pn(xi) = fi; i = 0; 1; : : : ; n; revine la adetermina coecientii a0; a1; : : : ; an din sistemul de ecuatii8>>>:

    a0 + a1x0 + a2x20+ + anxn0 = f0;a0 + a1x1 + a2x21+ + anxn1 = f1;......................................................a0 + a1xn + a2x2n + + anxnn = fn:

    (1.2)

  • 4 CAPITOLUL 1. INTERPOLAREA FUNCTIILOR

    Sistemul (1.2) este un sistem liniar de n + 1 ecuatii cu n + 1 necunoscutea0; a1; : : : ; an, care are determinantul de tip Vandermonde

    =

    1 x0 x20 : : : x

    n0

    1 x1 x21 : : : xn1

    ......

    ......

    ...1 xn x

    2n xnn

    =

    Y0j

  • 1.1. INTERPOLARE POLINOMIALA 5

    Conditiile anterioare arata ca polinomul cautat, Li(x); se anuleaza n punctelex0; : : : ; xi1; xi+1; : : : ; xn. Prin urmare, conform teoremei lui Bzout, Li(x) sedivide cu produsul (x x0) (x xi1)(x xi+1) (x xn): (n cazul i = 0punctele sunt x1; x2; : : : ; xn: Vom folosi aceasta conventie peste tot n cele ceurmeaza.) Cum acest produs este un polinom de gradul n iar Li(x) trebuie sa eun polinom de grad maxim n, rezulta ca Li(x) are forma

    Li(x) = ci(x x0) (x xi1)(x xi+1) (x xn) = cinYj=0j 6=i

    (x xj);

    unde ci este o constanta. Conditia Li(xi) = 1 permite determinarea constanteici; si anume

    ci =1

    (xi x0) (xi xi1)(xi xi+1) (xi xn) =1Qn

    j=0j 6=i(xi xj):

    Prin urmare, polinomul special cautat care verica conditiile (1.4) este

    Li(x) =(x x0) (x xi1)(x xi+1) (x xn)(xi x0) (xi xi1)(xi xi+1) (xi xn) ; (1.5)

    sau

    Li(x) =nYj=0j 6=i

    x xjxi xj :

    Polinoamele Li(x), i = 0; 1; : : : ; n; se numesc polinoamele fundamentale Lagrange.

    Etapa 2: Determinarea polinomului Lagrange

    Pentru rezolvarea problemei generale de interpolare consideram polinomulPn(x) de forma

    Pn(x) = f0L0(x) + f1L1(x) + + fnLn(x); (1.6)

    unde L0(x); L1(x); : : : ; Ln(x) sunt polinoamele fundamentale Lagrange determi-nate n etapa nti.Pn(x) este un polinom de grad cel mult n deoarece ecare polinom Li(x) are

    gradul n; dar, dupa efectuarea sumei, este posibil sa se obtina coecientul lui xn

    egal cu zero. n plus, Pn(x) satisface conditiile de interpolare (1.3). ntr-adevar,

    Pn(xj) =nXi=0

    fiLi(xj) =nXi=0

    fiij = fj; j = 0; 1; : : : ; n:

  • 6 CAPITOLUL 1. INTERPOLAREA FUNCTIILOR

    n baza unicitatii polinomului de interpolare data de teorema 1.1.1 acesta estepolinomul cautat.

    nlocuind polinoamele fundamentale Lagrange Li(x) n relatia (1.6) obtinem

    Pn(x) =nXi=0

    fi(x x0) (x xi1)(x xi+1) (x xn)(xi x0) (xi xi1)(xi xi+1) (xi xn); (1.7)

    sau, sub o forma utila n programele de calcul,

    Pn(x) =nXi=0

    fi

    0BB@ nYj=0j 6=i

    x xjxi xj

    1CCA : (1.8)Polinomul de interpolare dat de formulele (1.7) sau (1.8) se numeste polinomulde interpolare Lagrange sau, pe scurt, polinomul Lagrange.

    Observatia 1.1.2 Dupa cum se poate observa cu usurinta din formula (1.7),coecientul lui xn din polinomul Lagrange Pn(x) este dat de formula

    an =nXi=0

    fi(xi x0) (xi xi1)(xi xi+1) (xi xn) :

    Vom utiliza aceasta exprimare a coecientului an putin mai trziu, cnd vomintroduce notiunea de diferenta divizata.

    Observatia 1.1.3 Pentru o scriere mai simpla a polinoamelor fundamentale deinterpolare Lagrange (1.5), consideram polinomul

    w(x) = (x x0)(x x1) (x xn);

    numit polinomul punctelor de interpolare sau polinomul nodurilor. Derivata aces-tui polinom are expresia

    w(x) = (x x1)(x x2) (x xn) ++(x x0)(x x2) (x xn) + +(x x0) (x xi1)(x xi+1) (x xn) + +(x x0)(x x1) (x xn1):

    Calculata n x = xi aceasta suma se reduce la un singur termen si anume

    w0(xi) = (xi x0) (xi xi1)(xi xi+1) (xi xn):

  • 1.1. INTERPOLARE POLINOMIALA 7

    Cu aceste notatii polinoamele fundamentale (1.5) se scriu sub forma

    Li(x) =w(x)

    (x xi)w0(xi):

    Atunci polinomul Lagrange are expresia

    Pn(x) = w(x)nXi=0

    fi1

    (x xi)w0(xi) : (1.9)

    Exemplul 1.1.4 n cazul n = 1 polinomul Lagrange are forma

    P1(x) = f0x x1x0 x1

    + f1x x0x1 x0

    ;

    iar curba de interpolare y = P1(x) reprezinta dreapta care trece prin punctelesuport M0(x0; f0); M1(x1; f1): n gura de mai jos este reprezentat polinomulLagrange care trece prin punctele suport M0(2,1) si M1(4,5).

    0 2 4 6

    2

    4

    6

    Polinom Lagrange de gradul unu

    Exemplul 1.1.5 n cazul n = 2 polinomul Lagrange are expresia

    P2(x) = f0(x x1)(x x2)(x0 x1)(x0 x2) + f1

    (x x0)(x x2)(x1 x0)(x1 x2) + f2

    (x x0)(x x1)(x2 x0)(x2 x1);

    iar curba de interpolare y = P2(x) reprezinta parabola care trece prin punctelesuport M0(x0; y0); M1(x1; y1); M2(x2; y2): De exemplu, polinomul de interpolareLagrange care trece prin punctele M0(1; 2); M1(2; 5); M2(4; 3) are expresia

    P2(x) = 2 (x 2)(x 4)(1 2)(1 4) + 5

    (x 1)(x 4)(2 1)(2 4) + 3

    (x 1)(x 2)(4 1)(4 2)

    = 43x2 + 7x 11

    3:

  • 8 CAPITOLUL 1. INTERPOLAREA FUNCTIILOR

    Valoarea sa n x = 3 este P2(3) =16

    3: Reprezentarea graca a acestui polinom

    este data n gura de mai jos. Micul patrat de pe curba reprezinta valoareapolinomului n x = 3:

    0 1 2 3 4 5

    2

    4

    6

    Polinom Lagrange de gradul doi

    ntr-o problema de interpolare ne intereseaza de cele mai multe ori valoareapolinomului ntr-un punct x si mai putin expresia n sine a polinomului de inter-polare. De aceea calculele se fac sub forma prezentata n exemplu urmator.

    Exemplul 1.1.6 Se da functia f(x) prin tabelulxi : 1 2 4fi : 2 5 3

    : Se cere

    valoarea polinomului de interpolare Lagrange n punctul x = 3:Conform tabelului dat punctele de interpolare sunt x0 = 1; x1 = 2; x2 = 4; iar

    valorile functiei n aceste puncte sunt f0 = 2;f1 = 5;f3 = 4: Calculam mai ntipolinoamele fundamentale Lagrange n x = 3 :

    L0(x) =(x x1)(x x2)(x0 x1)(x0 x2); L0(3) =

    (3 2)(3 4)(1 2)(1 4) =

    1

    3;

    L1(x) =(x x0)(x x2)(x1 x0)(x1 x2)

    ; L1(3) ==(3 1)(3 4)(2 1)(2 4) = 1;

    L2(x) =(x x0)(x x1)(x2 x0)(x2 x1); L2(3) ==

    (3 1)(3 2)(4 1)(4 2) =

    1

    3:

    Polinomul de interpolare Lagrange n cazul n = 2 este

    P2(x) = f0L0(x) + f1L1(x) + f2L2(x):

  • 1.1. INTERPOLARE POLINOMIALA 9

    Pentru x = 3 obtinem

    P2(3) = 2 L0(3) + 5 L1(3) + 3 L2(3) = 2 (13 ) + 5 1 + 3 1

    3=16

    3:

    Avantajele folosirii polinomului de interpolare sub forma lui Lagrange sunt:a) Punctele de interpolare x0 < x1 < < xn sunt arbitrare. (Nu trebuie sa

    e echidistante cum se cere n alte metode de interpolare.)b) n expresia polinomului Lagrange valorile functiei f0; f1; : : : ; fn apar ex-

    plicit sub forma liniara. (A se vedea formulele (1.6), (1.7), (1.8), (1.9).) Deaceea utilizarea polinomului de interpolare sub forma lui Lagrange este recoman-data atunci cnd se rezolva mai multe probleme de interpolare pentru aceleasinoduri, dar cu seturi diferite de valori pentru functie.

    Dezavantajele utilizarii polinomului Lagrange:a) Constructia polinomului Lagrange necesita utilizarea tuturor punctelor de

    interpolare, ceea ce poate un impediment major n cazul n care n are valorimari. De aceea, n practica, pentru valori mari ale lui n, se prefera alte forme alepolinomului de interpolare dect forma lui Lagrange.

    b) Nu exista o relatie explicita ntre doua polinoame Lagrange de grade succe-sive. ( O relatie exista totusi, dar nu explicita si mai greu de utilizat. Mai precis,daca notam cu P01:::n(x) polinomul Lagrange construit folosind toate nodurilex0; x1; : : : ; xn; cu P12:::n(x) polinomul Lagrange construit folosind nodurilex1; x2; : : : ; xn; si cu P01:::n1(x) polinomul Lagrange construit folosind nodurilex0; x1; : : : ; xn1; atunci ntre cele trei polinoame exista relatia

    P01:::n(x) =(x x0)P12:::n(x) (x xn)P01:::n1(x)

    xn x0data de Propozitia 1.1.12. Pentru modul n care se poate folosi aceasta relatiepentru determinarea polinomului Lagrange a se vedea sectiunea 1.1.2)

    Cazul punctelor de interpolare echidistante

    Polinomul de interpolare Lagrange este important din punct de vedere teoreticdeoarece sta la baza obtinerii altor metode numerice. De exemplu, este folositpentru obtinerea formulelor de integrare si derivare numerica. n aceste cazuripunctele de interpolare sunt, de regula, echidistante. Ce nseamna aceasta? Seconsidera un interval [a; b] al axei reale pe care-l partim n n parti egale cu ajutorulpunctele de diviziune a = x0 < x1 < x2 < : : : < xn = b: Lungimea unui interval

    al diviziunii, numita pasul diviziunii, este egala cu h =b an: Cu aceasta notatie

    punctele diviziunii se scriu sub forma

    xi = x0 + ih; i = 0; 1; : : : ; n:

  • 10 CAPITOLUL 1. INTERPOLAREA FUNCTIILOR

    Efectuam schimbarea de variabila t =x x0h

    , de unde rezulta x = x0 + th:

    (t indica pozitia relativa a lui x fata de x0: De exemplu, daca t = 2, x estepunctul x2; iar daca t = 2; 5; x este punctul situat la mijlocul distantei dintre x2si x3:) Folosind variabila t avem

    x xj = (t j)h;xi xj = (i j)h:

    Atunci polinoamele fundamentale Lagrange (1.5), dupa amplicarea cu x xi,capata forma

    Li(x) =(x x0) (x xi1)(x xi)(x xi+1) (x xn)(xi x0) (xi xi1)(x xi)(xi xi+1) (xi xn)

    =t(t 1) (t n)hn+1

    i(i 1) 1 (t i) (1)(2) (i n)hn+1

    = (1)ni t(t 1) (t n)i!(n i)!(t i) :

    n consecinta, expresia polinomului Lagrange n cazul punctelor de interpolareechidistante este

    Pn(x) =nXi=0

    (1)ni fii!(n i)!

    t(t 1) (t n)(t i) ; (1.10)

    sau, ntr-o forma utila pentru programele de calcul,

    Pn(x) =

    nYj=0

    (t j)!

    nXi=0

    (1)ni fii!(n i)!(t i) ; (1.11)

    unde t =x x0h

    :

    Datele problemei de interpolare vor introduse n programele de calcul subforma unor vectori care au drept componente punctele de interpolare, respectivvalorile functie f n aceste puncte. n acest scop vom nota cu x vectorul care arecomponentele x0; x1; : : : ; xn si cu f vectorul de componete f0; f1; : : : ; fn: Deci

    x =

    26664x0x1...xn

    37775 ; f =26664f0f1...fn

    37775 :De multe ori, pentru a realiza o economie de spatiu, vom scrie vectorii sub formatranspusa x = (x0; x1; : : : ; xn)T ; f = (f0; f1; : : : ; fn)T :

  • 1.1. INTERPOLARE POLINOMIALA 11

    Punctul n care se calculeaza polinomul de interpolare va notat cu z: Aceastaschimbare de notatie se impune datorita faptului ca s-a notat cu x vectorulpunctelor de interpolare. n cazul n care se cere calcularea valorilor polino-mului de interpolare n mai multe puncte z0; z1; : : : ; zm aceste date se introducsub forma unui vector z = (z0; z1; : : : ; zm)T :

    Exercitiul 1.1.7 Fie x vectorul punctelor de interpolare si f vectorul valorilorunei functii n aceste puncte

    x =

    26666664

    111314181921

    37777775 ; f =26666664

    134222102758585068789282

    37777775 :

    Folosind polinomul de interpolare Lagrange, determinati valoarea functiei f npunctul z = 15:

    Exercitiul 1.1.8 Fie x vectorul punctelor de interpolare

    x = (0; 05; 0; 15; 0; 20; 0; 25; 0; 35; 0; 40; 0; 50; 0; 55)T

    si f vectorul valorilor unei functii n aceste puncte

    f = (0; 9512; 0; 8607; 0; 8187; 0;7788; 0; 7047; 0; 6703; 0; 6065; 0; 5769)T:

    Calculati f (0; 45).

    Exercitiul 1.1.9 Fie x vectorul punctelor de interpolare

    x = (1; 50; 1; 54; 1; 56; 1; 60; 1; 63; 1; 70)T

    si f vectorul valorilor unei functii n aceste puncte

    f = (3; 873; 3; 924; 3; 950; 4; 000; 4; 087; 4; 123)T:

    Folosind polinomul de interpolare Lagrange, determinati valorile functiei date npunctele:

    a) 1; 52; b) 1; 55; c) 1; 58; d) 1; 61; e) 1; 67.

    Exercitiul 1.1.10 n tabelul de mai jos se dau valorile unei functii f n punctelede interpolare xi, i = 0; 1; : : : ; 6:

    xi 2; 0 2; 3 2; 5 3; 0 3; 5 3; 8 4; 0fi 5; 848 6; 127 6; 300 6; 694 7; 047 7; 243 7; 368

    Folosind polinomul de interpolare Lagrange calculati valorile functiei n punctele

    a) 2; 22; b) 2; 41; c) 2; 78; d) 3; 34; e) 3; 75; f) 3; 88:

  • 12 CAPITOLUL 1. INTERPOLAREA FUNCTIILOR

    Exercitiul 1.1.11 Functile f si g sunt date mai jos indicndu-se punctele deinterpolare n vectorul x si valorile corespunzatoare ale acestor functii n vectoriif , respectiv g:

    x =

    266666666666666664

    0; 000; 050; 100; 150; 200; 250; 300; 350; 400; 450; 50

    377777777777777775; f =

    266666666666666664

    0; 280810; 312700; 345490; 379040; 413180; 447740; 482550; 517450; 552260; 586820; 62096

    377777777777777775; x =

    266666666666666664

    1; 501; 511; 521; 531; 541; 551; 561; 571; 581; 591; 60

    377777777777777775; g =

    266666666666666664

    0; 511830; 506240; 500640; 495030; 489400; 483760; 478110; 472450; 466780; 461100; 45540

    377777777777777775Folosind polinomul lui Lagrange pentru noduri echidistante calculati:

    1) Valorile functiei f n punctele: a) 0; 01928; b) 0; 01392; c) 0; 02475;d) 0; 02713; e) 0; 47113; f) 0; 47531; g) 0; 48398; h) 0; 48675.

    2) Valorile functiei g n punctele: a) 1; 50911; b) 1; 50820; c) 1; 50253;d) 1; 50192; e) 1; 59513; f) 1; 59575; g) 1; 59514; h) 1; 59728.

    Exemple de probleme de interpolare Lagrange rezolvate cu Mathcad suntprezentate n sierul Interpolare Lagrange.mcd.

    1.1.2 Algoritmul lui Aitken

    n cazul interpolarii cu un numar mare de puncte se poate ncerca mai ntirezolvarea problemei cu un numar redus de puncte de interpolare si apoi obtinereasolutiei pentru problema generala. Un dezavantaj major al polinomului Lagrangeeste absenta unei relatii explicite ntre polinoamele obtinute atunci cnd se trecede la n 1 la n puncte de interpolare. O relatie totusi exista si aceasta va studiata n continuare.

    Fie (xi; fi); i = 0; 1; : : : ; n; o multime de puncte suport pentru o problema deinterpolare polinomiala. Notam cu Pi0i1:::ik(x) acel polinom de grad cel mult kcare satisface conditiile

    Pi0i1 :::ik(xij ) = fij ; j = 0; 1; : : : ; k:

    Propozitia 1.1.12 Polinoamele Pi0i1:::ik(x) satisfac relatia de recurenta:

    Pi0i1:::ik(x) =1

    xik xi0

    Pi0i2:::ik1(x) xi0 xPi1i2:::ik(x) xik x

    ; (1.12)

  • 1.1. INTERPOLARE POLINOMIALA 13

    unde s-a notat

    Pi(x) = fi: (1.13)

    Demonstratie. Pentru a demonstra (1.12), notam cuQ(x) polinomul din mem-brul drept al acestei relatii si demonstram ca el satisface conditiile din denitiapolinomului de interpolare Pi0i1 :::ik(x):

    Evident, Q(x) are gradul mai mic sau egal cu k: Conform denitiilor poli-noamelor Pi0i1 :::ik1(x) si Pi1i2 :::ik(x) avem

    Q(xi0 ) = Pi0i1:::ik1 (xi0 ) = fi0;

    Q(xik) = Pi1i2:::ik(xik) = fik ;

    Q(xij ) =1

    xik xi0

    fij xi0 xijfij xik xij

    = fij ; j = 1; 2; : : : ; k 1:

    Atunci, n baza unicitatii polinomului de interpolare (teorema 1.1.1),Q(x) = Pi0i1:::ik(x):

    n practica ne intereseaza, de regula, valoarea polinomului de interpolarentr-un anumit punct x si mai putin expresia analitica n sine a polinomului. Deaceea, pe baza relatiilor de mai sus, se construiste un algoritm pentru calcululvalorii polinomului Lagrange n punctul x; numit algoritmul lui Aitken.

    Date punctele suport (xi; fi); i = 0; 1; : : : ; n; ale unei probleme de interpolare,pentru determinarea valorii Pn(x) se calculeaza succesiv:

    Pi;i+1(x) =1

    xi+1 xi

    fi xi xfi+1 xi+1 x

    ; i = 0; 1; : : : ; n 1;

    Pi;i+1;i+2(x) =1

    xi+2 xi

    Pi;i+1(x) xi xPi+1;i+2(x) xi+2 x

    ; i = 0; 1; : : : ; n 2;

    Pi;i+1;i+2;i+3(x) =1

    xi+3 xi

    Pi;i+1;i+2(x) xi xPi+1;i+2;i+3(x) xi+3 x

    ;

    i = 0; 1; : : : ; n 3, etc.Valoarea polinomului de interpolare Lagrange n punctul x este atunci

    Pn(x) = P01:::n(x) =1

    xn x0

    P01:::n1(x) x0 xP12:::n(x) xn x

    :

  • 14 CAPITOLUL 1. INTERPOLAREA FUNCTIILOR

    Pentru sistematizarea calculelor se construieste tabelul

    xi fi xi x Pi1;i(x) Pi2;i1;i(x) Pi3;i2;i1;i(x) : : :x0 f0 x0 xx1 f1 x1 x P01(x)x2 f2 x2 x P12(x) P012(x)x3 f3 x3 x P23(x) P123(x) P0123(x) : : :...

    ......

    ......

    ......

    unde

    P01(x) =1

    x1 x0

    f0 x0 xf1 x1 x

    ;

    P12(x) =1

    x2 x1

    f1 x1 xf2 x2 x

    ;

    P23(x) =1

    x3 x2

    f2 x2 xf3 x3 x

    ;

    P012(x) =1

    x2 x0

    P01(x) x0 xP12(x) x2 x

    ;

    P123(x) =1

    x3 x1

    P12(x) x1 xP23(x) x3 x

    ;

    P0123(x) =1

    x3 x0

    P012(x) x0 xP123(x) x3 x

    ; etc.

    Exemplul 1.1.13 Se considera functia f(x) data prin tabelul

    xi : 1 0 2 4fi : 5 1 3 1

    Pentru calculul valorii polinomului Lagrange n x = 3 vom folosii algoritmulAitken. Pe baza formulelor de mai sus, construim tabelul

    xi fi xi 3 Pi1;i(x) Pi2;i1;i(x) Pi3;i2;i1;i(x)1 5 40 1 3 192 3 1 5 134 1 1 2 114

    245

    Valoarea polinomului n x = 3 este24

    5:

  • 1.1. INTERPOLARE POLINOMIALA 15

    1.1.3 Diferente divizate.Polinomul Newton cu diferente divizate

    Fie (xi; fi); i = 0; 1; : : : ; n, punctele suport ale unei probleme de interpo-lare polinomiala. Se numesc diferente divizate de ordinul nti ale functiei f nnodurile xi; xi+1 si se noteaza cu f[xi; xi+1] expresiile

    f [xi; xi+1] =fi+1 fixi+1 xi ; i = 0; 1; : : : ; n 1:

    Cu ajutorul diferentelor divizate de ordinul nti se denesc diferentele divizatede ordinul doi ale functiei f n nodurile xi; xi+1; xi+2 prin relatiile

    f[xi; xi+1; xi+2] =f[xi+1; xi+2] f[xi; xi+1]

    xi+2 xi; i = 0; 1; : : : ; n 2:

    n general, diferentele divizate de ordinul k (k 2) ale functiei f n nodurilexi; xi+1; : : : ; xi+k1;xi+k (k +1 noduri) se denesc prin relatia de recurenta

    f[xi; xi+1; : : : ; xi+k1; xi+k] =f[xi+1; : : : ; xi+k] f [xi; : : : ; xi+k1]

    xi+k xi ;i = 0; 1; : : : ; n k:

    Pentru ca formula de mai sus sa se poata scrie si pentru k = 1 se face conventia caprin diferente divizate de ordin zero, notate f[xi]; sa se nteleaga valorile functieif n nodurile xi; adica

    f [xi] = fi:

    Ce reprezinta diferenta divizata de ordinul n?

    Rezultatul urmator pune n evidenta legatura dintre diferentele divizatedenite mai sus si coecientii polinomului Lagrange. Faptul ca sunt consideratetoate nodurile x0; x1; : : : ; xn nu este o limitare a generalitatii deoarece oricarealte noduri ar luate ele pot numerotate astfel.

    Propozitia 1.1.14 Diferenta divizata de ordinul n a functiei f n nodurilex0; x1; : : : ; xn este egala cu coecientul lui xn din polinomul de interpolare La-grange. Mai precis, avem egalitatea

    f[x0; x1; : : : ; xn] =nXi=0

    fi(xi x0) (xi xi1)(xi xi+1) (xi xn)

    : (1.14)

  • 16 CAPITOLUL 1. INTERPOLAREA FUNCTIILOR

    Demonstratie. Vom demonstra formula (1.14) prin inductie matematica dupan: Pentru n = 0 formula este adevarata, deoarece ambii membrii sunt egali cu f0:

    Pentru n = 1 avem

    f[x0; x1] =f1 f0x1 x0 =

    f0x0 x1 +

    f1x1 x0 :

    Deoarece polinomul Lagrange de gradul unu construit cu punctele suport (x0; f0)si (x1; f1) are expresia

    P1(x) = f0x x1x0 x1 + f1

    x x0x1 x0

    =

    f0

    x0 x1 +f1

    x1 x0

    x+

    f0x1 f1x0x1 x0 ;

    rezulta ca formula (1.14) este adevarata si n acest caz.Presupunem formula (1.14) adevarata pentru n si demonstram ca ramne

    adevarata pentru n + 1. Conform denitiei avem egalitatea

    f[x0; x1; : : : ; xn+1] =f[x1; : : : ; xn+1] f [x0; x1; : : : ; xn]

    xn+1 x0 :

    Atunci, folosind ipoteza de inductie avem

    f[x0; x1; : : : ; xn+1]

    =1

    xn+1 x0

    "n+1Xi=1

    fi(xi x1) (xi xi1)(xi xi+1) (xi xn+1)

    nXi=0

    fi(xi x0) (xi xi1)(xi xi+1) (xi xn)

    #:

    Regrupnd termenii putem scrie

    f[x0; x1; : : : ; xn+1]

    =1

    xn+1 x0

    "nXi=1

    fi(xi x1) (xi xi1)(xi xi+1) (xi xn)

    1

    xi xn+1 1

    xi x0

    +

    +fn+1

    (xn+1 x1) (xn+1 xi1)(xn+1 xi+1) (xn+1 xn)

    f0(x0 x1) (x0 xi1)(x0 xi+1) (x0 xn)

    :

  • 1.1. INTERPOLARE POLINOMIALA 17

    n nal obtinem

    f [x0; x1; : : : ; xn+1]

    =f0

    (x0 x1) (x0 xi1)(x0 xi+1) (x0 xn)(x0 xn+1)

    +nXi=1

    fi(xi x0) (xi xi1)(xi xi+1) (xi xn+1)

    +

    +fn+1

    (xn+1 x0)(xn+1 x1) (xn+1 xi1)(xn+1 xi+1) (xn+1 xn)

    =n+1Xi=0

    fi(xi x0) (xi xi1)(xi xi+1) (xi xn+1) :

    Corolarul 1.1.15 Diferentele divizate sunt invariante la o permutare anodurilor.

    Demonstratie. Daca xi0; xi1; : : : ; xin este o permutare a punctelor de interpo-lare x0; x1; : : : ; xn; atunci are loc egalitatea

    nXi=0

    fiQnj=0j 6=i(xi xj)

    =nXk=0

    fikQnj=0j 6=k(xik xij )

    ;

    deoarece suma a doua este numai o rearanjare a primei sume. Prin urmare

    f[x0; x1; : : : ; xn] = f [xi0; xi1; : : : ; xin ];

    ceea ce nseamna ca diferenta divizata nu se modica daca se face o permutare apunctelor de interpolare.

    Polinomul de interpolare sub forma lui Newton

    Principalul inconvenient al folosirii polinomului de interpolare sub forma luiLagrange este lipsa unei relatii explicite ntre doua polinoamele de interpolare degrade succesive. O astfel de relatie este utila pentru alegerea gradului optim alpolinomului de interpolare utilizat pentru realizarea aproximatiei dorite.

    Fie (xi; fi); i = 0; 1; : : : ; n, punctele suport ale unei probleme de interpolarepolinomiala. Notam cu Pn(x) = P01:::n(x) polinomulul de interpolare construitfolosind toate cele n + 1 noduri date x0; x1; : : : ; xn si cu Pn1(x) = P01:::n1(x)polinomul construit numai cu nodurile x0; x1; : : : ; xn1: Conform proprietatilorecarui polinom de interpolare avem

    Pn(xi) = Pn1(xi) = fi; i = 0; 1; : : : ; n 1;Pn(xn) = fn:

  • 18 CAPITOLUL 1. INTERPOLAREA FUNCTIILOR

    Fie C(x) factorul de corectie necesar pentru a avea o relatie de forma

    Pn(x) = Pn1(x) + C(x): (1.15)

    C(x) este un polinom de grad mai mic sau egal cu n; deoarece grad(Pn) n sigrad(Pn1) n 1. Mai mult dect att, coecientul lui xn din polinomul C(x)este acelasi cu coecientul lui xn din polinomul Pn(x). n plus, C(x) se anuleazan punctele x0; x1; : : : ; xn1; pentru ca ambele polinoame Pn(x) si Pn1(x) iauaceleasi valori n aceste noduri. ntr-adevar,

    C(xi) = Pn(xi) Pn1(xi) = fi fi = 0; i = 0; 1; : : : ; n 1:

    Prin urmare, polinomul C(x) de grad cel mult n se divide cu produsul(x x0)(x x1) (x xn1) care este un polinom de grad n: Exista atunciun numar real c astfel nct

    C(x) = c(x x0)(x x1) (x xn1):

    (Constanta c este unica si se determina din conditia Pn(xn) = fn: Relatia (1.15)

    implica c =fn Pn1(xn)

    (xn x0)(xn x1) (xn xn1) ; dar aceasta exprimare pentru cnu este utila n cele ce urmeaza.) Conform celor observate anterior, coecientullui xn din polinomul C(x) este egal cu an; coecientul lui xn din polinomul deinterpolare Pn(x):Deci c = an:Deoarece polinomul de interpolare este unic putemconsidera pentru Pn(x) forma lui Lagrange. n baza propozitiei 1.1.14, coecientulan este egal cu diferenta divizata asociata functiei f si nodurilor x0; x1; : : : ; xn.Prin urmare,

    c = f[x0; x1; : : : ; xn]:

    Atunci egalitatea (1.15) se scrie sub forma

    Pn(x) = Pn1(x) + f[x0; x1; : : : ; xn](x x0)(x x1) (x xn1): (1.16)

    Relatia (1.16) obtinuta mai sus arata legatura dintre polinoamele de interpolarePn(x) si Pn1(x) construite folosind nodurile x0; x1; : : : ; xn1; respectivx0; x1; : : : ; xn1; xn:

    Folosind relatia (1.16) putem obtine o alta expresie analitica pentru polino-mul de interpolare Pn(x): Pentru aceasta scriem relatia (1.16) pentru n egal cu1; 2; : : : ; n 1; n: Avem

  • 1.1. INTERPOLARE POLINOMIALA 19

    P1(x) = P0(x) + f[x0; x1](x x0)

    P2(x) = P1(x) + f[x0; x1; x2](x x0)(x x1):::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

    Pn1(x) = Pn2(x) + f[x0; x1; : : : ; xn1](x x0)(x x1) (x xn2)

    Pn(x) = Pn1(x) + f[x0; x1; : : : ; xn](x x0)(x x1) (x xn1):

    Daca adunam relatiile de mai sus, reducem termenii asemenea si tinem seama caP0(x) = f0; obtinem

    Pn(x) = f0 + f [x0; x1](x x0) + f[x0; x1; x2](x x0)(x x1) + (1.17)

    +f [x0; x1; : : : ; xn](x x0)(x x1) (x xn1):

    Aceasta este expresia polinomului de interpolare sub forma lui Newton cudiferente divizate.

    Notatia diferentei divizate de ordinul k sub forma f[xi; xi+1; : : : ; xi+k] areavantajul ca pune n evidenta nodurile care intervin n calculul ei, dar este prealunga pentru a folosita n mod curent n programele de calcul. De aceea vomprefera notatia

    Dkfi = f[xi; xi+1; : : : ; xi+k]; i = 0; 1; : : : ; n k:

    Cu aceste notatii formulele pentru calculul diferentelor divizate devin:

    D1fi =fi+1 fixi+1 xi ; i = 0; 1; : : : ; n 1;

    D2fi =D1fi+1 D1fixi+2 xi

    ; i = 0; 1; : : : ; n 2;

    D3fi =D2fi+1 D2fixi+3 xi ; i = 0; 1; : : : ; n 3;

    :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

    Dkfi =D(k 1)fi+1 D(k 1)fi

    xi+k xi ; i = 0; 1; : : : ; n k:

    Pentru ca formula generala sa functioneze si pentru k = 1 folosim conventiaD0fi = fi:

  • 20 CAPITOLUL 1. INTERPOLAREA FUNCTIILOR

    Algoritm pentru calculul diferentelor divizate si a valoriipolinomului Newton ntr-un punct

    Date de intrare:

    x =

    26664x0x1...xn

    37775 ; f =26664f0f1...fn

    37775 ; z,unde:x este vectorul punctelor de interpolare.f este vectorul valorilor functiei n aceste puncte. Pentru simplicarea notatiei

    vom scrie de multe ori n acest text vectorii sub forma transpusax = (x0; x1; : : : ; xn)

    T ; respectiv f = (f0; f1; : : : ; fn)T :z este punctul n care se calculeaza polinomul Newton. (Aceasta schimbare

    de notatie se impune datorita faptului ca s-a notat cu x vectorul punctelor de in-terpolare.) n cazul n care se cere calcularea valorilor polinomului de interpolaren mai multe puncte z0; z1; : : : ; zm aceste date se introduc sub forma unui vectorz = (z0; z1; : : : ; zm)T :

    Se calculeaza:

    D1f = (D1f0; D1f1; : : : ; D1fn1)T ; vectorul diferentelor divizate de ordinulnti ale carui componentele D1fi sunt date de relatiile

    D1fi =fi+1 fixi+1 xi ; i = 0; 1; : : : ; n 1:

    D2f = (D2f0; D2f1; : : : ; D2fn2)T , vectorul diferentelor divizate de ordinul doi,unde

    D2fi =D1fi+1 D1fixi+2 xi

    ; i = 0; 1; : : : ; n 2:

    n general,

    Dkf = (Dkf0; Dkf1; : : : ; Dkfnk)T

    este vectorul diferentelor divizate de ordinul k, unde

    Dkfi =D(k 1)fi+1 D(k 1)fi

    xi+k xi ; i = 0; 1; : : : ; n k:

    Procedeul se continua pna cnd diferentele divizate devin practic constante.(La etapa urmatoare diferentele ar practic zero.) n acest fel se stabileste

  • 1.1. INTERPOLARE POLINOMIALA 21

    gradul polinomului de interpolare Newton care se foloseste pentru rezolvareaproblemei respective.

    Cu aceste notatii, expresia polinomului de interpolare Newton de gradul k cudiferente divizate este

    Pk(x) = f0 +D1f0 (x x0) +D2f0 (x x0)(x x1) + : : :

    +Dkf0 (x x0)(x x1) : : : (x xk1);

    unde k n este acel numar natural pentru care diferentele divizate devin prac-tic constante. Pentru utilizare n programele de calcul formula de mai sus sescrie sub forma

    Pk(x) = f0 +kXi=1

    Dif0

    i1Yj=0

    (x xj)!:

    Avantajele folosirii polinomului de interpolare sub forma lui Newton sunt:a) Exista o relatie explicita ntre polinoamele de interpolare Newton de grade

    succesive.

    b) Se poate realiza o buna interpolare folosind mai putine puncte de interpo-lare dect numarul total de puncte.

    Exemplul 1.1.16 Fie x vectorul punctelor de interpolare si f vectorul valorilorfunctiei n aceste puncte, unde

    x =

    26666664

    x0x1x2x3x4x5

    37777775 =26666664

    00; 20; 30; 40; 70; 9

    37777775 ; f =26666664

    f0f1f2f3f4f5

    37777775 =26666664

    132; 651148; 877157; 464166; 375195; 112216; 000

    37777775Calculati valoarea functiei n punctul z = 0; 35:

    Pentru a stabili gradul polinomului Newton care va folosit pentru rezolvareaproblemei se calculeaza diferentele divizate ale functiei f pna cnd acestea devinpractic constante.

  • 22 CAPITOLUL 1. INTERPOLAREA FUNCTIILOR

    Diferentele divizate de ordinul nti:

    D1f0 =f1 f0x1 x0

    =148; 877 132; 651

    0; 2 0 = 81; 13

    D1f1 =f2 f1x2 x1

    =157; 464 148; 877

    0; 3 0; 2 = 85; 87

    D1f2 =f3 f2x3 x2 =

    166; 375 157; 4640; 4 0; 3 = 89; 11

    D1f3 =f4 f3x4 x3 =

    195; 112 166; 3750; 7 0; 4 = 95; 79

    D1f4 =f5 f4x5 x4 =

    216; 000 195; 1120; 9 0; 7 = 104; 44

    Diferentele divizate de ordinul doi

    D2f0=D1f1 D1f0x2 x0

    =85; 87 81; 130; 3 0 =15,8

    D2f1=D1f2 D1f1x3 x1

    =89; 11 85; 870; 4 0; 2 =16,2

    D2f2=D1f3 D1f2x4 x2 =

    95; 79 89; 110; 7 0; 3 =16,7

    D2f3=D1f4 D1f3x5 x3 =

    104; 44 95; 790; 9 0; 4 =17,3

    Diferentele divizate de ordinul trei

    D3f0=D2f1D2f0x3 x0 =

    16; 2 15; 80; 4 0 =1

    D3f1=D2f2D2f1x4 x1 =

    16; 7 16; 20; 7 0; 2 =1

    D3f2=D2f3D2f2x5 x2 =

    17; 3 16; 70; 9 0; 3 =1

    Deoarece diferentele divizate de ordinul trei sunt constante, polinomul deinterpolare sub forma lui Newton cu diferente divizate are forma

  • 1.1. INTERPOLARE POLINOMIALA 23

    P (z) = f0 +D1f0 (z x0) +D2f0 (z x0)(z x1)

    +D3f0 (z x0)(z x1)(z x2):

    Atunci valoarea functiei f n z = 0; 35 se aproximeaza cu valoarea polinomuluiNewton

    P (0; 35) = 132; 651 + 81; 13 (0; 35 0) + 15; 8 (0; 35 0) (0; 35 0; 2)

    +1 (0; 35 0) (0; 35 0; 2) (0; 35 0; 3)

    = 161; 616

    O constructie matriceala a diferentelor divizate

    Scrierea polinomului de interpolare sub forma lui Lagrange este simpla, darare dezavantajul ca la adaugarea unui nod nu se pot utiliza rezultatele anterioaresi tot procesul de calcul trebuie reluat de la capat. Pentru a se nlatura acestneajuns, n locul bazei Lagrange L = fLn;0; Ln;1; : : : ; Ln;ng a spatiului Pn[a; b]se foloseste baza Newton, N = fNn;0;Nn;1; : : : ; Nn;ng; formata din urmatoarelepolinoame 8>>>>>>>>>:

    Nn;0(x) = 1;Nn;1(x) = x x0;Nn;2(x) = (x x0)(x x1);...Nn;n(x) = (x x0)(x x1) (x xn1):

    Pentru simplicarea notatiei vom scrie polinoamele bazei Newton sub forma

    Nn;0(x) = 1;

    Nn;i(x) =Qi1k=0(x xk); i = 1; 2; : : : ; n:

    n baza Newton polinomul de interpolare Pn(x) se scrie sub forma

    Pn(x) = d0Nn;0(x) + d1Nn;1(x) + + dnNn;n(x);

    unde coecientii di sunt diferentele divizate de ordinul i n nodurile x0; x1; : : : ; xi,i.e. di = f[x0; x1; : : : ; xi]; i = 0; 1; : : : ; n:

    Constructia diferenetelor divizate n mod recursiv este adecvata mai multcalculului manual. Evident, acest proces recursiv poate scris ntr-un limbaj deprogramare, dar scrierea programului poate ridica de multe ori probleme utiliza-torului obisnuit care este interesat numai de folosirea polinomului Newton. De

  • 24 CAPITOLUL 1. INTERPOLAREA FUNCTIILOR

    aceea, n cele ce urmeaza, vom propune o metoda matriceala de constructie adiferentelor divizate.

    Se observa mai nti ca functiile bazei Newton n nodurile de interpolaresatisfac urmatoarele relatii:

    Nn;0(xj) = 1; j = 0; 1; : : : ; n;

    si, pentru i = 1; 2; : : : ; n

    Nn;i(xj) =

    0; j = 0; 1; : : : ; i 1;Qi1

    k=0(xj xk); j = i; i +1; : : : ; n:Transpusa matricei formata cu aceste elemente o notam cuN si o numim matriceaNewton. Deci

    N = [Nn;i(xj)]T ;

    sau, scrisa dezvoltat,

    N =

    26666641 0 0 01 x1 x0 0 01 x2 x0 (x2 x0)(x2 x1) 0...

    ...... . . .

    ...1 xn x0 (xn x0)(xn x1) (xn x0) (xn xn1)

    3777775Determinantul acestei matrice este egal cu produsul elementelor de pe diagonalaprincipala,

    det(N) =Y

    0jin(xi xj) 6= 0;

    ceea ca arata ca N este o matrice inversabila. Inversa matricei N este26666664

    1 0 0 0 01

    x0x11

    x1x0 0 0 01

    (x0x1)(x0x2)1

    (x1x0)(x1x2)1

    (x2x0)(x2x1) 0 0...

    ......

    .... . . ...

    1Qnj=0j 6=0

    (x0xj)1Qn

    j=0j 6=1

    (x1xj)1Qn

    j=0j 6=2

    (x2xj)1Qn

    j=0j6=3

    (x3xj) 1Qnj=0j 6=n

    (xnxj)

    37777775

    (Folosind calculul simbolic din Mathcad se poate determina inversa matricei New-ton pna la ordinul patru inclusiv).

    Notam cu f vectorul valorilor functiei n noduri, i.e., f = (f0; f1; : : : ; fn)T si cud vectorul ale carui componente sunt diferentele divizate d0 = f[x0];

  • 1.1. INTERPOLARE POLINOMIALA 25

    d1 = f [x0; x1]; d2 = f[x0; x1; x2]; : : : ; dn = f [x0; x1; x2 : : : xn]: Deoarece, conformpropozitiei 1.1.14, diferentele divizate se pot calcula pe baza formulei

    f[x0;x1; : : : ; xk] =kXi=0

    fiQkj=0j 6=i

    (xi xj); k = 0; 1; : : : ; n;

    avem egalitatea

    d = N1f:

    Pentru constructia polinomului Newton cu diferente divizate folosind Matcada se vedea sierul Interpolare Newton diferente divizate.mcd.

    1.1.4 Diferente nite.Polinomul Newton cu diferente nite

    Daca functia f (x) este cunoscuta numai prin valorile sale fi = f (xi) ntr-unsistem de puncte echidistante x0 < x1 < : : : < xn; denite de relatiile xi = x0+ih;i = 0; 1; : : : ; n; cu h > 0; atunci n locul diferentelor divizate se folosesc diferentelenite al caror calcul este mai simplu.

    Se numesc diferente nite (progresive) de ordinul nti si se noteaza cu 1fiexpresiile

    1fi = fi+1 fi; i = 0; 1; : : : ; n 1:

    Diferentele nite de ordinul doi se denesc prin relatiile

    2fi = 1fi+1 1fi; i = 0; 1; : : : ; n 2:

    n general, pentru k numar natural, 2 k n, diferentele nite de ordinul k sedenesc prin formulele de recurenta

    kfi = (k 1)fi+1 (k 1)fi; i = 0; 1; : : : ; n k: (1.18)

    Prin conventie, diferentele nite de ordinul zero sunt egale cu valorile functiei nnoduri, deci

    0fi = fi; i = 0; 1; : : : ; n:

    Calculul diferentelor nite se face recursiv, pe baza relatiilor de mai sus, pnacnd acestea devin practic constante.

    Ce relatie exista ntre diferentele nite si diferentele divizate?

  • 26 CAPITOLUL 1. INTERPOLAREA FUNCTIILOR

    Dupa cum este de asteptat, ntre diferentele nite si diferentele divizate existao anumita relatie care este pusa n evidenta n lema ce urmeaza.

    Lema 1.1.17 ntre diferenta divizataDkfi si diferenta nitakfi are loc relatia

    Dkfi =kfik! hk : (1.19)

    Demonstratie. Demonstratia se face prin inductie dupa k. Daca k = 0;egalitatea (1.19) este evidenta, ambii membrii ind egali cu fi: Pentru k = 1egalitatea (1.19) este de asemenea adevarata pe baza denitiilor

    D1fi =fi+1 fixi+1 xi

    =1fih:

    Presupunem formula (1.19) adevarata pentru k si o demonstram pentru k+1.Folosind relatiile de recurenta din denitia diferentelor divizate, respectiv a celornite, obtinem

    D(k + 1)fi =Dkfi+1Dkfixi+k+1 xi

    =1

    (k + 1)h

    kfi+1k! hk

    kfik! hk

    =

    1

    (k + 1)! hk+1 (kfi+1 kfi)

    =(k + 1)fi(k + 1)! hk+1 :

    Polinomul de interpolare Newton cu diferente nite

    Polinomul de interpolare sub forma lui Newton cu diferente nite se obtinedin cel cu diferente divizate (1.17) folosind relatiile anterioare dintre diferenteledivizate si cele nite. Pentru aceasta, la fel ca n cazul polinomului Lagrange

    pentru noduri echidistante, se noteaza cu t =x x0h

    : Folosind aceasta notatieavem

    x xj = (t j)h; j = 0; 1; : : : n;

    (x x0)(x x1) (x xk) = t(t 1) (t k)hk+1:nlocuind diferentele divizate cu cele nite n formula (1.17) si folosind relatiilede mai sus obtinem expresia polinomului Newton cu diferente nite

    Pn(x) = f0 + 1f0 t+2f02!

    t (t 1) + + nf0n!

    t(t 1) (t n +1);(1.20)

  • 1.1. INTERPOLARE POLINOMIALA 27

    unde t =x x0h

    :

    Pentru retinerea cu usurinta a acestei formule, se noteaza

    Ckt =t(t 1) (t k + 1)

    k!:

    Daca t este un numar natural si t k; Ckt reprezinta numarul combinarilor de telemente luate cte k: n general, Ckt este doar o notatie pentru o formula care areaceeasi expresie cu aceea a combinarilor. Cu aceasta notatie polinomul Newtoncu diferente nite se scrie sub forma usor de retinut

    Pn(x) = f0 + C1t 1f0 + C2t 2f0+ + Cnt nf0; (1.21)

    unde t =x x0h

    :

    Algoritm pentru calculul diferentelor nite si a valoriipolinomului Newton ntr-un punct

    Date de intrare:x = (x0; x1; : : : ; xn)T ; vectorul punctelor de interpolare.f = (f0; f1; : : : ; fn)

    T ; vectorul valorilor functiei n punctele de interpolare.z; punctul n care se calculeaza polinomul Newton. n cazul n care se cere

    calcularea valorilor polinomului de interpolare n mai multe puncte z0; z1; : : : ;zmaceste date se introduc sub forma unui vector z = (z0; z1; : : : ; zm)T:h; pasul retelei de puncte echidistante.

    Se calculeaza:1f = (1f1;1f2; : : : ;1fn1)T; vectorul diferentelor nite de ordinul nti

    ale carui componentele 1fi sunt date de relatiile

    1fi = fi+1 fi; i = 0; 1; : : : ; n 1:

    2f = (2f1;2f2; : : : ;2fn2)T; vectorul diferentelor nite de ordinul doi,unde

    2fi = 1fi+1 1fi; i = 0; 1; : : : ; n 2:

    n general, kf = (kf0;kf1; : : : ;kfnk)T ; este vectorul diferentelor -nite de ordinul k, unde

    kfi = (k 1)fi+1 (k 1)fi; i = 0; 1; : : : ; n k:

    Procedeul se continua pna cnd diferentele nite devin practic constante.n acest fel se stabileste gradul polinomului de interpolare Newton cu diferentenite care se foloste pentru rezolvarea problemei respective.

  • 28 CAPITOLUL 1. INTERPOLAREA FUNCTIILOR

    Se determina noua variabila: t =z x0h

    :

    Cu notatiile de mai sus, expresia polinomului de interpolare Newton cu difer-ente nite este

    Pk(t) = f0 +1f0 t+ 2f02! t(t 1) +3f03!

    t(t 1)(t 2) + : : :

    +kf0k!

    t(t 1) (t k +1);

    unde k n este acel numar natural pentru care diferentele nite de ordinul ksunt practic constante. Pentru utilizare n programele de calcul formula de maisus se scrie sub forma

    Pk(t) = f0+kXi=1

    if0i!

    "i1Yj=0

    (t j)#!:

    Exemplul 1.1.18 Fie x vectorul punctelor de interpolare si f vectorul valorilorfunctiei n aceste puncte, unde

    x =

    266664x0x1x2x3x4

    377775 =2666643; 503; 553; 603; 653; 70

    377775 ; f =266664f0f1f2f3f4

    377775 =26666433; 11534; 81336; 59838; 47540; 447

    377775Calculati valoarea functiei n punctul z = 3; 57:

    Examinnd datele problemei de interpolare se observa ca nodurile sunt echidis-tante. Se alege pentru aproximarea valorii functiei n punctul dat folosirea poli-nomului Newton cu diferente nite deoarece acestea sunt mai usor de calculatdect diferentele divizate.

    Diferentele nite de ordinul nti:

    1f0 = f1 f0 = 34; 813 33; 115 = 1; 698

    1f1 = f2 f1 = 36; 598 34; 813 = 1; 785

    1f2 = f3 f2 = 38; 475 36; 598 = 1; 877

    1f3 = f4 f3 = 40; 447 38; 475 = 1; 972

    Diferentele nite de ordinul doi:

  • 1.1. INTERPOLARE POLINOMIALA 29

    2f0 = 1f1 1f0 = 1; 785 1; 698 = 0; 087

    2f1 = 1f2 1f1 = 1; 877 1; 785 = 0; 092

    2f2 = 1f3 1f2 = 1; 972 1; 877 = 0; 095Diferentele nite de ordinul trei:

    3f0 = 2f1 2f0 = 0; 092 0; 087 = 0; 005

    3f1 = 2f2 2f1 = 0; 095 0; 092 = 0; 003Deoarece diferentele nite de ordinul trei sunt practic constante, pentru

    calculul valorii aproximative a functiei f n punctul dat se poate folosi polinomulNewton de gradul trei

    P3(z) = f0 + 1f0 t+ 2f0 t(t 1)2!

    +3f0 t(t 1)(t 2)3!

    ;

    unde

    t =z x0h

    =3; 57 3; 50

    0; 5= 1; 4:

    Atunci f(3; 57) se aproximeaza cu

    P3(3; 57) = 33; 115 + 1; 698 1; 4 + 0; 087 1; 4 (1; 4 1)2

    +

    +0; 005 1; 4 (1; 4 1) (1; 4 2)6

    = 35; 516

    O constructie matriceala a diferentelor nite

    Polinomul Newton cu diferente divizate se scrie sub forma

    Pn(x) = d0Nn;0(x) + d1Nn;1(x) + + dnNn;n(x);unde fNn;0; Nn;1; : : : ; Nn;ng este baza Newton a spatiului Pn[a; b] formata dinpolinoamele 8>>>>>>>>>:

    Nn;0(x) = 1;Nn;1(x) = x x0;Nn;2(x) = (x x0)(x x1);...Nn;n(x) = (x x0)(x x1) (x xn1);

  • 30 CAPITOLUL 1. INTERPOLAREA FUNCTIILOR

    iar coecientii di sunt diferentele divizate de ordinul i n nodurile x0; x1; : : : ; xi,i.e., di = f [x0; x1; : : : ; xi]; i = 0; 1; : : : ; n: Dupa cum s-a demonstrat n cadrullemei 1.1.17, daca nodurile sunt echidistante, avem egalitatiile

    di = f[x0; x1; : : : ; xi] =if0i!hi

    ; i = 0; 1; : : : ; n:

    Efectund schimbarea de variabila t =x x0h

    ; functiile bazei Newton (pentru

    i = 1; 2; : : : ; n) capata forma

    Ni(x) =Qi1k=0(x xk) = hi

    Qi1k=0(t k); i = 1; 2; : : : ; n:

    Notam ~Nn;0(t) = 1;~Ni(t) =

    Qi1k=0(t k); i = 1; 2; : : : ; n;

    Cu aceste notatii polinomul Newton cu diferente divizate devine

    Pn(x) = d0 +nPi=1diNn;i(x) = 0f0 +

    nPi=1

    if0i!hi

    hi ~Nn;i(t):

    Daca notam i =if0i!; i = 0; 1; : : : ; n; obtinem expresia polinomului Newton cu

    diferente nite

    Pn(t) = 0 +nPi=1

    i ~Nn;i(t);

    sau

    Pn(t) = 0 + 1t+ 2t(t 1) + 3t(t 1)(t 2) + + nt(t 1) (t n + 1):(1.22)

    Pentru calculul coecientilor i; i = 0; 1; : : : ; n; procedeam la fel ca n cazuldiferentelor divizate. Denim matricea Newton

    ~N =h~Nn;i(j)

    iT;

    unde

    ~Nn;0(j) = 1; j = 0; 1; : : : ; n;

    iar pentru i = 1; 2; : : : ; n

    ~Nn;i(j) =

    0; j = 0; 1; : : : ; i 1;Qi1

    k=0(j k) = Aij; j = i; i + 1; : : : ; n:

  • 1.1. INTERPOLARE POLINOMIALA 31

    (Aij = j(j 1)(j 2) (j i + 1) nseamna aranjamente de j luate cte i). nacest caz, matricea Newton este o matrice numerica care arata astfel

    ~N =

    266666664

    1 0 0 0 01 1! 0 0 01 A12 2! 0 01 A13 A

    23 3! 0

    ......

    ...... . . .

    ...1 A1n A

    2n A

    3n n!

    377777775Fie = (0; 0; : : : ; n)T vectorul coecientiilor polinomului Newton scris subforma (1.22) si f = (f0; f1; : : : ; fn)T vectorul valorilor functiei. Cu aceste notatiiavem egalitatea

    = ~N1f:

    Pentru constructia polinomului Newton cu diferente nite folosind Mathcada se vedea sierul Interpolare Newton diferente nite.mcd.

    1.1.5 Evaluarea erorii n interpolarea polinomiala

    Fie f o functie data si fi = f (xi) valorile sale n punctele de interpolarea < x0 < x1 < : : : < xn < b: Exista atunci un unic polinom de interpolare degrad cel mult n; notat Pn(x), care satisface conditiile

    Pn(xi) = fi; i = 0; 1; : : : ; n:

    n punctele x; diferite de punctele de interpolare xi; vom aproxima valoareafunctiei f(x) cu Pn(x): Pentru a stabili ct de buna este aceasta aproximare,notam

    En(f; x) = f(x) Pn(x):En(f; x) este eroarea care se face atunci cnd n locul valorii functiei f(x) sefoloseste valoarea data de polinomul de interpolare Pn(x):

    Evaluarea erorii cu ajutorul diferentelor divizate

    Folosind polinomul de interpolare sub forma lui Newton cu diferente divizatese poate obtine o formula pentru evaluarea erorii de interpolare fara a impuneconditii asupra functiei f:

    Teorema 1.1.19 Eroarea care se face cnd se nlocuieste valoarea functiei f(x)cu valoarea Pn(x) data de polinomul de interpolare Newton cu diferente divizateeste data de formula

    En(f; x) = f[x0; x1; : : : ; xn; x](x x0)(x x1) (x xn1)(x xn)| {z }polinomul nodurilor

    : (1.23)

  • 32 CAPITOLUL 1. INTERPOLAREA FUNCTIILOR

    Demonstratie. Fie t un numar real diferit de punctele de interpolarex0; x1; : : : ; xn: Scriem polinomul Newton cu diferente divizate pentru nodurilex0; x1; : : : ; xn si t :

    Pn+1(x) = f0 + f[x0; x1](x x0) + f [x0; x1; x2](x x0)(x x1) +

    +f [x0; x1; : : : ; xn](x x0)(x x1) (x xn1)

    +f [x0; x1; : : : ; xn; t](x x0)(x x1) (x xn1)(x xn):

    Tinnd seama de relatia de recurenta dintre polinoamele Newton, formula de maisus se scrie sub forma

    Pn+1(x) = Pn(x) + f[x0; x1; : : : ; xn; t](x x0)(x x1) (x xn1)(x xn):

    Daca n aceasta relatie i dam lui x valoarea t si tinem seama ca Pn+1(t) = f (t)(pentru ca t este un nod cu ajutorul caruia s-a construit polinomul Pn+1(x)) avemegalitatea

    f (t) Pn(t) = f [x0; x1; : : : ; xn; t](t x0)(t x1) (t xn1)(t xn):

    nlocuind n formula de mai sus pe t cu x obtinem

    En(f; x) = f(x) Pn(x)= f[x0; x1; : : : ;xn; x](x x0)(x x1) (x xn1)(x xn)

    si teorema este demonstrata.

    Evaluarea erorii cu ajutorul derivatelor

    Vom nota cu Cn+1([a; b]) multimea functiilor reale denite pe intervalul [a; b]care au derivate continue pe [a; b] pna la ordinul n + 1 inclusiv. Se spune cafunctia f este de clasa Cn+1 pe intervalul [a; b] daca f 2 Cn+1([a; b]):

    n cazul n care functia f este de clasaCn+1 pe intervalul [a; b] se obtine pentrueroarea de interpolare o formula n expresia caruia apare derivata de ordinul n+1:

    Teorema 1.1.20 Daca f 2 Cn+1([a; b]); atunci, pentru orice x 2 [a; b]; exista unpunct 2 (a; b) (care depinde de x si n) astfel nct are loc egalitatea

    En(f; x) = f(x) Pn(x) = f(n+1)()

    (n +1)!(x x0)(x x1) : : : (x xn): (1.24)

  • 1.1. INTERPOLARE POLINOMIALA 33

    Demonstratie. Daca x este egal cu unul din punctele de interpolare, egalitateadin enunt este adevarata deoarece ambii membrii sunt egali cu zero.

    Vom demonstra formula (1.24) pentru x 6= xi: Pentru aceasta consideramfunctia auxiliara F : [a; b] ! R denita prin formula

    F (t) =

    w(t) En(f; t)w(x) En(f; x)

    ; t 2 [a; b];

    unde w(x) = (x x0)(x x1) : : : (x xn) este polinomul nodurilor. Deoarecew(xi) = En(f; xi) = 0; rezulta F (xi) = 0; i = 0; 1; : : : ; n: n plus, F (x) = 0; deciF (t) are cel putin n+2 radacini distincte n intervalul [a; b]si anume x0; x1; : : : ; xn;x: n baza teoremei lui Rolle, aplicata succesiv, F 0(t) are cel putin n+1 radacinidistincte n (a; b); F 00(t) are cel putin n; si asa mai departe. n nal, F (n+1)(t) arecel putin o radacina 2 (a; b). Deci F (n+1)() = 0: Deoarece derivata de ordinuln + 1 a functiei F este

    F (n+1)(t) =

    (n+ 1)! f

    (n+1)(t)

    w(x) En(f; x)

    ;

    obtinem (n +1)! f

    (n+1)()

    w(x) En(f; x)

    = 0;

    de unde rezulta expresia erorii

    En(f; x) =f (n+1)()

    (n + 1)!w(x):

    Teorema este demonstrata. Pentru f 2 C([a; b]) notam cu kfk norma uniforma a functiei f, i.e.,

    kfk = maxx2[a;b]

    j f(x) j :

    Cu aceasta notatie obtinem pentru valoarea absoluta a erorii calculat n punctulx o evaluare pusa n evidenta n corolarul de mai jos.

    Corolarul 1.1.21 Daca f 2 Cn+1([a; b]); atunci

    j En(f; x) j j (x x0)(x x1) : : : (x xn) j(n + 1)!

    kf(n+1)k; (1.25)

    pentru orice x 2 [a; b]:

  • 34 CAPITOLUL 1. INTERPOLAREA FUNCTIILOR

    Sa notam acum cu h = max0in

    (xi+1 xi): Se poate demonstra ca, pentru oricex 2 [x0; xn]; are loc inegalitatea

    j (x x0)(x x1) : : : (x xn) j n!hn+1

    4:

    (Se utilizeaza faptul ca daca x 2 [xi; xi+1]; atunci este adevarata inegalitatea

    j(x xi)(x xi+1)j (xi xi+1)2

    4 h

    2

    4:

    Aceasta rezulta folosind maximul functiei de gradul doi x2(xi+xi+1)x+xixi+1:)Folosind aceasta estimare n formula (1.25) obtinem pentru estimarea erorii

    fornula

    kf Pnk kf(n+1)khn+14(n+ 1)

    care arata ca eroarea scade odata cu h:

    Tinnd seama de denitia normei uniforme, inegalitatea (1.25) poate scrisasub forma

    kf Pnk kwk(n + 1)!

    kf(n+1)k: (1.26)

    Aceasta formula arata ca eroarea de interpolare En(f; x) va minima pe totintervalul [a; b] atunci cnd polinomul nodurilor w(x) are norma uniforma cea maimica. Apare astfel problema: care sunt punctele de interpolare x0; x1; : : : ; xn dinintervalul [a; b] pentru care norma uniforma a polinomului w(x) este minima?Rezolvarea acestei probleme se face cu ajutorul polinoamelor Cebsev de spetanti care vor studiate ulterior. Rezultatul care se poate demonstra este enuntatn teorema de mai jos.

    Teorema 1.1.22 Fie x0; x1; : : : ; xn puncte distincte din intervalul [a; b]: Poli-nomul nodurilor w(x) = (x x0)(x x1) (x xn) are cea mai mica normauniforma pe [a; b] atunci cnd nodurile xk sunt date de formulele

    xk =b+ a

    2+b a2

    cos(2k +1)

    2(n +1); k = 1; 2; : : : ; n:

    n acest caz, evaluarea erorii de interpolare pentru o functie f 2 Cn+1([a; b]) estedata de formula

    kf Pnk (b a)n+1

    22n+1(n + 1)!kf (n+1)k:

  • 1.1. INTERPOLARE POLINOMIALA 35

    Exemplul 1.1.23 Pentru a vedea cu ce precizie se calculeazap115 daca se

    considera punctele de interpolare x0 = 100; x1 = 121; x2 = 144; consideramfunctia f(x) =

    px si calculam deriatele sale

    f 0(x) =1

    2x

    12 ; f 00(x) = 1

    4x

    23 ; f 000(x) =

    3

    8x

    52 ; f(4)(x) = 15

    16x

    72 :

    Deoarece f(4)(x) < 0; pentru orice x 2 [100; 144]; f 000(x) este strict descresca-toare pe [100; 144]. n consecinta, f 000(x) si atinge valoarea maxima pe intervalul[100; 144] n x = 100: Prin urmare

    kf 000k = maxx2[100;144]

    j f 000(x) j= 38

    1p1005

    =3

    8105:

    n baza formulei (1.25) avem

    jp115 P2(115) j j (115 100)(115 121)(115 144) j

    3! 38105 = 0; 0016:

    Polinomul Lagrange de gradul doi calculat n punctul x = 115 este

    P2(115) = 10 (115 121)(115 144)(100 121)(100 144) + 11 (115 100)(115 144)(121 100)(121 144)

    +12 (115 100)(115 121)(144 100)(144 121)

    = 10; 72275:

    Atuncip115 ' P2(115) = 10; 72275; unde, conform estimarii facute anterior pen-

    tru eroare, doar primele doua zecimale sunt exacte. Pentru comparatie calculamp115 folosind Mathcad. Valoarea obtinuta este

    p115 = 10; 72381:

    Relatia dintre diferentele divizate, nite si derivatele functiei

    n cazul n care functia f 2 Cn+1([a; b]), comparnd formula erorii data de(1.23) cu formula (1.24), obtinem

    f [x0; x1; : : : ; xn; x] =f(n+1)()

    (n+ 1)!; 2 (a; b): (1.27)

    Din cele de mai sus rezulta ca este adevarata urmatoarea propozitie.

    Propozitia 1.1.24 Daca f 2 Cn([a; b]) si x0 < x1 < : : : < xn sunt puncte dinintervalul [a; b]; atunci

    f [x0; x1; : : : ; xn] =f (n)()

    n!; 2 (a; b): (1.28)

  • 36 CAPITOLUL 1. INTERPOLAREA FUNCTIILOR

    Formula (1.28) arata legatura dintre diferentele divizate si derivatele functieif; n cazul unei functii f de clasa Cn pe intervalul [a; b]: Ea se numeste formulade medie pentru diferentele divizate.

    n conditiile propozitiei de mai sus, daca punctele de interpolare sunt echidis-tante, n baza formulei (1.19), care stabileste legatura dintre diferentele divizatesi cele nite, obtinem o relatie ntre derivatele de ordinul n si diferentele nite deordinul n ale functiei f

    f(n)() =nf0hn

    ; 2 (a; b): (1.29)

    Observatia 1.1.25 Fie f o functie continua pe intervalul nchis [x0; x1] si deri-vabila pe intervalul deschis (x0; x1): Pentru n = 1 formula (1.28) conduce la

    f [x0; x1] = f0(); 2 (x0; x1): (1.30)

    Pe de alta parte, conform denitie diferentei divizate, avem

    f[x0; x1] =f(x1) f(x0)x1 x0 :

    Din cele doua egalitatii de mai sus rezulta ca exista 2 (x0; x1) astfel ca

    f (x1) f(x0)x1 x0 = f

    0():

    Aceasta egalitate nu este altceva dect formula de medie data de teorema luiLagrange. Prin urmare, formula (1.28) generalizeaza acest rezultat clasic, deunde provine si denumirea ei de formula de medie pentru diferentele divizate.

    1.2 Polinoamele Bernstein

    n acesta sectiune vom introduce polinoamele Bernstein pe intervalul [0; 1],vom studia unele proprietati ale acestora si utilizarea lor n teoria interpolarii.

    Polinoamele

    Bn;i(t) = Cin(1 t)niti; i = 0; 1; : : : ;n; t 2 [0; 1];

    se numesc polinoamele Bernstein. Ele apar n mod natural n dezvoltarea bino-miala

    1 = ((1 t) + t)n =nPi=0

    Cin(1 t)niti:

    Polinoamele Bernstein au urmatoarele proprietati:

  • 1.2. POLINOAMELE BERNSTEIN 37

    1. Bn;i(t) 0; 8t 2 [0; 1]:2.

    Pni=0Bn;i(t) = 1; 8t 2 [0; 1]:

    3. Bn;i(t) = Bn;ni(1 t).4. Polinoamele Berstein satisfac urmatoarea relatie de recurenta

    Bn;i(t) = (1 t)Bn1;i(t) + tBn1;i1(t):

    ntr-adevar, folosind relatia cunoscuta dintre combinari C in = Cin1 +C

    i1n1

    avem

    Bn;i(t) = Cin(1 t)niti = Cin1(1 t)niti + Ci1n1(1 t)niti

    = (1 t)C in1(1 t)n1iti + tCi1n1(1 t)nit= (1 t)Bn1;i(t) + tBn1;i1(t):

    5. Polinomul Bernstein Bn;i(t) are pe t = 0 ca radacina de ordinul i si pe t = 1ca radacina de ordinul n i:

    6. Polinomul Bernstein Bn;i(t) are un singur punct de maxim n punctul de

    abscisa t =i

    n: Armatia rezulta imediat din expresia derivatei

    B 0n;i(t) = Cin(1 t)n1iti1(nt+ i):

    7. Multimea polinoamelor Bernstein fBn;0; Bn;1; : : : ; Bn;ng formeaza o baza aspatiului Pn[0; 1]:

    Polinoamele Bernstein de gradul trei

  • 38 CAPITOLUL 1. INTERPOLAREA FUNCTIILOR

    Polinoamele Bernstein pe un interval oarecare [a; b] sunt

    bBn;i(x) = Bn;i(x ab a ) = C in(b a)n (b x)ni(x a)i; x 2 [a; b]:Deoarece ele formeaza o baza a spatiului Pn[a; b] orice polinom care aparatineacestui spatiu se scrie ca o combinatie liniara unica a polinamelor Bernstein

    Pn(x) = b0 bBn;0(x) + b1 bBn;1(x) + + bn bBn;n(x); x 2 [a; b]:Coecientii b0; b1; : : : :bn se numesc coecientii Bzier ai polinomului Pn(x):

    Fie (xj; fj), j = 0; 1; : : : ; n; punctele suport ale unei probleme de interpolare,unde a = x0 < x1 < < xn = b: Pentru determinarea coecientilor Bzierpunem conditiile de interpolare Pn(xj) = fj si obtinem sistemul liniar de n + 1ecuatii cu n + 1 necunoscute b0; b1; : : : ; bn8>>>>>:

    b0 bBn;0(x0) + b1 bBn;1(x0) + + bn bBn;n(x0) = f0;b0 bBn;0(x1) + b1 bBn;1(x1) + + bn bBn;n(x1) = f1;

    b0 bBn;0(xn) + b1 bBn;1(xn) + + bn bBn;n(xn) = fn;

    pe care-l scriem sub forma matriceala26664bBn;0(x0) bBn;1(x0) bBn;n(x0)bBn;0(x1) bBn;1(x1) bBn;n(x1)

    ...... . . .

    ...bBn;0(xn) bBn;1(xn) bBn;n(xn)

    3777526664b0b1...bn

    37775 =26664f0f1...fn

    37775 :Notam b = (b0; b1; : : : ; bn)T ; vectorul coecientilor Bezier, f = (f0; f1; : : : ; fn)T ;vectorul valorilor functiei si B matricea sistemului. Se observa ca

    B =h bBn;i(xj)iT :

    Matricea B se numeste matricea Bernstein. Cu aceste notatii, pentru deter-minarea vectorului coecientiilor Bzier avem egalitatea

    b = B1f:

  • 1.3. CURBE BZIER 39

    1.3 Curbe Bzier

    ncepem aceasta sectiune prin a stabili notatiile folosite.

    Un punct P din R2 de coordonate (x; y) va scris sub forma P =xy

    ; sau

    P = (x; y)T: Curbele plane din R2 vor denite prin ecuatiile lor parametricex = x(t)y = y(t)

    ; t 2 I;

    unde I este un interval al axei reale. Folosind notatiile

    r =

    xy

    , r(t) =

    x(t)y(t)

    ;

    putem scrie ecuatia unei curbe plane sub forma r = r(t); t 2 I:Pentru ntelegerea ideilor care stau la baza constructiei curbelor Bzier n-

    cepem prin prezentarea urmatorului exemplu.

    Exemplul 1.3.1 Fie P0; P1; P2; P3 patru puncte din R2 si t un parametru real.Denim curbele plane

    r1;0(t) = (1 t)P0+ tP1;r1;1(t) = (1 t)P1+ tP2;r1;2(t) = (1 t)P2+ tP3:

    r1;0(t) reprezinta dreapta care trece prin punctele P0 si P1; r1;1(t) reprezintadreapta ce trece prin punctele P1 si P2; iar r1;2(t) reprezinta dreapta care treceprin punctele P2 si P3: Pentru t 2 [0; 1] se obtin segmentele de dreapta care aucapetele n aceste puncte. Cele trei segmente formeaza o linie poligonala caretrece prin cele patru puncte date.

    Continuam procedeul de constructie de mai sus si denim recursiv curbeleplane

    r2;0(t) = (1 t)r1;0(t) + tr1;1(t);r2;1(t) = (1 t)r1;1(t) + tr1;2(t):

    Aceaste curbe sunt parabole care, scrise n raport de punctele initiale, au urma-toarele ecuatii

    r2;0(t) = (1 t)2P0 + 2(1 t)tP1+ t2P2;r2;1(t) = (1 t)2P1 + 2(1 t)tP2+ t2P3:

    Pentru t 2 [0; 1] prima reprezimnta un arc de parabola care uneste punctele P0si P2; iar a doua reprezinta arcul de parabola ce uneste punctele P1 si P3:

  • 40 CAPITOLUL 1. INTERPOLAREA FUNCTIILOR

    Denim n continuare, n acelasi stil, curba plana

    r3;0(t) = (1 t)r2;0(t) + tr2;1(t); t 2 [0; 1]:n functie de punctele initiale, ecuatia acestei curbe se scrie sub forma

    r3;0(t) = (1 t)3P0 +3(1 t)2tP1 + 3(1 t)t2P2+ t3P3:Dupa cum se observa din denitiile de mai sus, curbele de la pasul doi sunt

    scrise n functie de polinoamele Bernstein de gradul doi

    B2;0(t) = (1 t)2; B2;1(t) = 2(1 t)t; B2;2(t) = t2;iar curba de la pasul trei este scrisa n functie de polinoamele Bernstein de gradultrei

    B3;0(t) = (1 t)3; B3;1(t) = 3(1 t)2t; B3;2(t) = 3(1 t)t2; B3;3(t) = t3:

    Toata constructia de mai sus este ilustrata grac n gura urmatoare:

    Trecem acum la prezentarea considerentelor generale.

    Fie P0;P1; : : :; Pn, n + 1 puncte din R2: Pentru uniformizarea scrierii notamr0;i(t) = Pi; i = 0; 1; : : : ; n: Denim apoi recursiv

    rk;i(t) = (1 t)rk1;i(t) + trk1;i+1(t);pentru k = 1; 2; : : : ; n si i = 0; 1; : : : ; n k:

  • 1.3. CURBE BZIER 41

    Denitia 1.3.2 Curbele rk;i(t) se numesc curbe Bzier partiale de ordinul k:Punctele Pi; : : :; Pi+k; care apar n denitia curbei rk;i(t); se numesc punctele decontrol ale curbei Bzier partiale rk;i(t):

    Curba nala rn(t) = rn;0(t) 2 Pn[0; 1] se numeste curba Bzier. PuncteleP0;P1; : : :; Pn se numesc punctele de control ale curbei, iar poligonul denit depunctele P0;P1; : : :; Pn se numeste poligonul de control al curbei Bzier rn(t):

    Proprietati ale curbelor Bzier:

    Curbele Bzier sunt situate n acoperirea convexa a punctelor lor de con-trol. Acest fapt rezulta din modul de constructie al curbelor Bzier ca ocombinatie convexa a curbelor Bzier de grad mai mic.

    Curba Bzier nala rn(t) uneste punctul P0 cu punctul Pn; deoarece rn(0) =P0 si rn(1) = Pn:

    Curbele Bzier si polinoamele Bernstein

    Dupa cum s-a observat n exemplul 1.3.1, curbele Bzier pot denite cuajutorul polinoamelor Bernstein. Scopul teoremei care urmeaza este de a arataca aceasta este o proprietate generala a curbelor Bzier.

    Teorema 1.3.3 Curbele Bzier partiale de ordinul k; rk;i(t); se scriu n raportde polinoamele Bernstein sub forma

    rk;i(t) =kXj=0

    Pi+jBk;j(t);

    unde k = 0;1; 2; : : : ; n si i = 0; 1; : : : ; n k:n particular, pentru i = 0 si k = n; se obtine relatia pe care o verica curba

    Bzier nala

    rn(t) =nXj=0

    PjBn;j(t):

    Demonstratia este elementara si se face prin metoda inductiei matematice.

    Proprietati:

    Deoarece Pnj=0Bn;j(t) = 1; valorile polinoamelor Bernstein sunt coordonatebaricentrice pentru rn(t):

    Tinnd seama ca, n plus, Bn;j(t) 0; rezulta ca rn(t) se aa n combinatiaconvexa al punctelor de control P0;P1; : : :; Pn: (Acest fapt a fost remarcatsi mai sus, deoarece rezulta imediat din modul de constructie recursiva acurbelor Bzier.)

  • 42 CAPITOLUL 1. INTERPOLAREA FUNCTIILOR

    1.4 Problema aproximarii functiilor

    Fie f : [a; b] ! R o functie de clasa C1 pe [a; b] (aceasta nseamnaca f este de clasa Cn pe intervalul [a; b]; pentru orice numar natural n) si ea = x0 < x1 < : : : < xn = b o diviziune a intervalului [a; b] formata din puncte

    echidistante xi = x0+ ih; i = 0; 1; : : : ; n; unde h =b an: Consideram polinomul

    de interpolare Pn(x) care satsiface conditiile P (xi) = f(xi); i = 0; 1; : : : ; n: Sepune atunci ntrebarea reasca: daca n ! 1; polinoamele Pn aproximeaza dince n ce mai bine functia f ? Mai precis, Pn(x) ! f (x) pentru un punct x dinintervalul [a; b], x diferit de noduri. Sau, mai mult, sirul de polinoame (Pn)n 1tinde la functia f n raport cu norma uniforma? Aceasta ar nseamna ca

    kf Pnk = maxx2[a;b]

    j f(x) Pn(x) j ! 0; pentru n ! 1:

    Raspunsul este: nu ntotdeauna. Exista functii sucient de simple pentru careconvergenta nu are loc. Enumeram mai jos cteva exemple celebre.

    Exemplul 1.4.1 Exemplul lui S.N.Bernstein. Fie functia f (x) = jxj; x 2[1; 1]; si punctele de interpolare echidistante x(n)i = 1 +

    2i

    n; i = 0; 1; : : : ; n: S.

    N. Bernstein a demonstrat ca limn!1

    Pn(x) 6= f (x) pentru x =2 f1; 0; 1g:

    Se ntmpla acest lucru pentru ca functia modul nu este derivabila norigine? Raspunsul este nu. Exista si functii indenit derivabile pentru caresirul (Pn(x))n1 nu converge la f(x): Un astfel de exemplu a fost dat de CarlRunge.

    Exemplul 1.4.2 Exemplul lui Carl Runge. Functia

    f(x) =1

    1 + x2; x 2 [5; 5];

    este de clasa C1 pe intervalul [5; 5]. Se considera nodurile echidistante

    x(n)i = 5 +10i

    n; i = 0; 1; : : : ; n;

    si se construiesc polinoamele de interpolare Pn(x): Se poate demonstra ca

    limn!1

    Pn(x) = f (x); daca jxj c;

    limn!1

    Pn(x) 6= f (x); daca c < jxj < 5;

    unde c = 3:6334:

  • 1.5. INTERPOLARE HERMITE 43

    n desenul de mai jos curba continua reprezinta gracul functiei f(x) =1

    1 + x2pe intervalul [5; 5]; iar curba punctata este gracul polinomului de interpolareLagrange P15(x): Se observa ca daca ne apropiem de capatele intervalului [5; 5]gracul polinomului de interpolare se departeaza de gracul functiei interpolate.

    4 2 0 2 4

    0.5

    0.5

    1

    1.5

    2

    1

    1 x2+

    P z( )

    x z,

    Mai mult dect att, S. N. Berstein a aratat ca pentru orice sistem de punctede interpolare x(n)i ; i = 0; 1; : : : ; n; din intervalul [a; b]; date anterior, exista ofunctie continua f : [a; b] ! R astfel nct sirul polinoamelor de interpolare(Pn)n1 care interpoleaza functia f n aceste noduri nu converge uniform la f pe[a; b]:

    1.5 Interpolare Hermite

    Problema interpolarii Hermite consta n a determina un polinom P (x) care sainterpoleze functia f(x) si, n plus, derivatele polinomului P (k)(x) sa interpolezederivatele functiei f(k)(x):

    n cele ce urmeaza vom rezolva cea mai simpla problema de interpolareHermite. Date numerele reale x0 < x1 < : : : < xn si valorile functiei f(x) si alederivatei sale f

    0(x) n aceste puncte, i.e.,

    fi = f(xi); f0i = f

    0(xi); i = 0; 1; : : : ; n;

    sa se determine un polinom P (x) care verica conditiile Hermite

    P (xi) = fi; P0(xi) = f 0i i = 0; 1; : : : ; n: (1.31)

  • 44 CAPITOLUL 1. INTERPOLAREA FUNCTIILOR

    Deoarece avem 2n + 2 conditii vom cauta polinomul P (x) de gradul 2n + 1;

    P (x) = a0+ a1x+ + a2n+1x2n+1;ceea ce nseamna determinarea a 2n + 2 parametrii a0; a1; : : : ; a2n+1:

    Pentru demonstrarea existentei si unicitatii unui polinom P (x) care vericaconditiile de mai sus vom folosi o tehnica asemanatoare cu aceea utilizata laconstructia polinomului Lagrange.

    Dupa cum se stie, polinomul Lagrange care verica conditiile P (xi) = fi;i = 0; 1; : : : ; n; are expresia

    Pn(x) =nXi=0

    fiLi(x);

    unde Li(x) sunt polinoamele fundamentale Lagrange

    Li(x) =(x x0) (x xi1)(x xi+1) (x xn)(xi x0) (xi xi1)(xi xi+1) (xi xn) ; i = 0; 1; : : : ; n;

    care satisfac conditiile: Li(xi) = 1 si Li(xj) = 0 pentru j = 0; 1; : : : ; n;j 6= i: Pentru simplicarea scrierii vom nota produsul de la numitorul polino-mului fundamental Lagrange

    Qnj=0j 6=i(xixj) cu i: Atunci

    Qnj=0j 6=i(xxj) = iLi(x):

    Vom cauta polinomul P (x) care sa satisfaca conditiile Hermite (1.31) subforma

    P (x) =nXi=0

    fi ai(x) +nXi=0

    f 0i bi(x); (1.32)

    unde ai(x) si bi(x) sunt polinoame de grad 2n +1 care verica conditiile

    ai(xj) =

    1 daca j = i0 daca j 6= i ; a

    0i(xj) = 0; i; j = 0; 1; : : : ; n;

    bi(xj) = 0; b0i(xj) =

    1 daca j = i0 daca j 6= i i; j = 0; 1; : : : ; n:

    Deoarece pentru j = 0; 1; : : : ; n; j 6= i; avem ai(xj) = a0i(xj) = 0; nodurilexj sunt radacini duble ale polinomului ai(x); deci ai(x) se divide cu produsulQnj=0j 6=i(x xj)2: Cum acest produs este un polinom de gradul 2n; iar ai(x) are

    gradul 2n+ 1; rezulta ca polinoamele ai(x) trebuie sa e de forma

    ai(x) = [Ai(x xi) + Bi]nYj=0j 6=i

    (x xj)2;

  • 1.5. INTERPOLARE HERMITE 45

    unde Ai si Bi sunt doua constante care se determina din conditiile ramase

    ai(xi) = 1; a0i(xi) = 0: (1.33)

    Polinomul de gradul unu a fost scris sub forma Ai(x xi) +Bi pentru usurintacalculelor n continuare. Scriem polinomul ai(x) folosind polinoamele Lagrangefundamentaale

    ai(x) = 2i [Ai(x xi) + Bi] [Li(x)]2

    si calculam derivata

    a0i(x) = 2i

    Ai [Li(x)]

    2 + [Ai(x xi) + Bi] 2Li(x)L0i(x):

    Folosind conditiile (1.33) determinam constantele Ai si Bi:

    ai(xi) = 1) 2i Bi = 1) Bi =1

    2i;

    a0i(xi) = 0) 2i [Ai +Bi 2L0i(xi)] = 0) Ai = Bi 2L0i(xi) = 2

    2iL0i(xi):

    Obtinem astfel pentru ai(x) expresia

    ai(x) = [1 2 (x xi)L0i(xi)] [Li(x)]2:

    Un rationament analog cu cel de mai sus arata ca polinoamele bi(x) trebuiesa e de forma

    bi(x) = 2i [Ci(x xi) +Di] [Li(x)]2 :

    Atunci derivata are expresia

    b0i(x) = 2i

    Ci [Li(x)]

    2 + [Ci(x xi) +Di] 2Li(x)L0i(x):

    Constantele Ci si Di se determina din conditiile

    bi(xi) = 0) Di = 0;

    b0i(xi) = 1) 2i Ci = 1 ) Ci =1

    2i:

    Atunci

    bi(x) = (x xi) [Li(x)]2 :

    Vom numi polinoamele ai(x) si bi(x) polinoame fundamentale Hermite.

  • 46 CAPITOLUL 1. INTERPOLAREA FUNCTIILOR

    Introducem aceste polinoame n formula (1.32). Obtinem astfel un polinomcare verica conditiile de interpolare (1.31), numit polinomul Hermite si notat cuH2n+1(x). Expresia acestui polinom este

    H2n+1(x) =nXi=0

    fi [1 2 (x xi)L0i(xi)] [Li(x)]2 +nXi=0

    f 0i (x xi) [Li(x)]2:(1.34)

    Pentru demonstrarea unicitatii acestui polinom presupunem ca ar mai ex-ista un polinom Q2n+1(x) de grad 2n + 1 care verica conditiile Hermite(1.31). Notam R(x) = H2n+1(x) Q2n+1(x) si observam ca R(xi) = R0(xi) = 0;i = 0; 1; : : : ; n: Aceasta nseamna ca polinomul R(x) de grad 2n + 1 are n+ 1radacini duble, x0; x1; : : : ; xn; ceea ce nseamna n total 2n + 2 radacini. Acestlucru nu este posibil dect daca R(x) este polinomul identic nul. Deci R(x) 0;ceea ce nseamna H2n+1(x) Q2n+1(x). Prin urmare H2n+1(x) este unicul poli-nom de grad 2n + 1 care verica conditiile Hermite (1.31).Exemplul 1.5.1 Pentru n = 1 problema de interpolare Hermite are urmatoareaformulare: sa se determine un polinom de grad cel mult trei care verica conditiile

    P (x0) = f0; P (x1) = f1; P0(x0) = f 00; P

    0(x1) = f 01:

    n acest caz, polinoamele fundamentale Lagrange si derivatele lor sunt

    L0(x) =x x1x0 x1

    ; L1(x) =x x0x1 x0

    :

    L00(x) =1

    x0 x1 ; L01(x) =

    1

    x1 x0 :

    Formula (1.34) devine

    H3(x) = f0 [1 2(x x0)L00(x0)] [L0(x)]2

    +f1 [1 2(x x1)L01(x1)] [L1(x)]2

    +f 00 (x x0) [L0(x)]2 + f 01 (x x1) [L1(x)]2;de unde, prin nlocuirea polinoamelor fundamentale Lagrange si a derivatele aces-tora cu expresiile lor, rezulta

    H3(x) = f0

    1 2 x x0

    x0 x1

    x x1x0 x1

    2+ f1

    1 2 x x1

    x1 x0

    x x0x1 x0

    2+f 00 (x x0)

    x x1x0 x1

    2+ f 01 (x x1)

    x x0x1 x0

    2:

  • 1.5. INTERPOLARE HERMITE 47

    Expresia polinomului Hermite cu diferente divizate

    Dupa cum se vede din exemplul anterior determinarea polinomului Hermite,chiar pentru un numar mic de noduri, este o operatie anevoioasa. Pentru aobtine o expresie a polinomului Hermite mai convenabila pentru calcule, pornindde la nodurile distincte x0 < x1 < : : : < xn, denim un nou sir de noduriz0; z1; : : : ; z2n+1 prin

    z0 = z1 = x0; z2 = z3 = x1; : : : z2n = z2n+1 = xn:

    Scriem apoi formal polinomul de interpolare pentru functia f(x) cu nodurilez0; z1; : : : ; z2n+1 folosind forma lui Newton cu diferente divizate.

    P2n+1(x) = f(z0) + f [z0; z1](x z0) + f[z0; z1; z2](x z0)(x z1) +

    +f[z0; z1; z2; z3](x z0)(x z1)(x z2)(1.35)

    +f[z0; z1; z2; z3; z4](x z0)(x z1)(x z2)(x z3) +

    +f[z0; z1; : : : ; z2n+1](x z0)(x z1) (x z2n):Deoarece nodurile z2isi z2i+1 sunt egale cu xi; diferentele divizate f[z2i; z2i+1] nu se

    pot deni prin formula cunoscuta f [z2i; z2i+1] =f2i+1 f2iz2i+1 z2i

    . Relatia

    f [xi; xi+1] = f0(), unde 2 (xi; xi+1); obtinuta n observatia 1.1.25, sugereaza ca

    o nlocuire rezonabila pentru valoarea diferentei divizate de acest tip ar valoareainitiala a derivatei n nodul xi: Deci, vom deni

    f [z2i; z2i+1] = f0 (z2i) = f 0(xi) = f 0i:

    Prin urmare, la constructia diferentelor divizate de ordinul nti vom folosi datelede intrare f 00;f

    01; : : : ;f

    0n n locul diferentelor divizate

    f[z0; z1]; f [z2; z3]; : : : ; f[z2n; z2n+1]:

    Celelalte diferente divizate se vor calcula prin procedeul obisniut.Expresia polinomului P2n+1(x) data de relatia (1.35) se scrie sub forma

    H2n+1(x) = f(x0) + f[x0; x0](x x0) + f [x0; x0; x1](x x0)2+

    +f [x0; x0; x1; x1](x x0)2(x x1) +(1.36)

    +f [x0; x0; x1; x1; x2](x x0)2(x x1)2 +

    +f [x0; x0; : : : ; xn; xn](x x0)2 (x xn1)2(x xn);

  • 48 CAPITOLUL 1. INTERPOLAREA FUNCTIILOR

    unde pentru calculul diferentelor divizate de ordinul unu s-au folosit valorile datepentru derivata

    f[x0; x0] = f00; f[x1; x1] = f

    01; : : : f [xn; xn] = f

    0n:

    Evident, acesta este un polinom de grad 2n + 1: Folosind proprietatile dederivabilitate ale diferentelor divizate se poate demonstra ca acesta este polinomulde interpolare Hermite, ceea ce justica notatia folosita pentru el, H2n+1(x); nloc de P2n+1(x):

    Aceasta metoda de constructie a polinomuluiHermite are avantajul ca permiteobtinerea unei formule pentru eroarea de interpolare. Deoarece formula erorii deinterpolare n cazul polinomului (1.35) e