lucrarea 6 final

7/24/2019 Lucrarea 6 FINAL

1/20

UNIVERSITATEA POLITEHNICA BUCURESTI

FACULTATEA DE INGINERIE ELECTRIC

Interpolarea polinomiala a functiilor

reale

Referat pentru disciplina Metode numerice in inginerie electrica

Grupa: 121 B

Responsabil referat BARBIERU Raluca

NEAGU Cristian Andrei

ROSU Laura

SCARLAT Vasile Marius

TOFAN Maria Bianca

Data efecturii lucrrii: 20/11/2013

Data predrii referatului: 27/11/2013


2/20

Contributia studentilor la referat

BARBIERU Raluca Responsabil referat.

Asamblarea contributiilor primite de la colegi.

Redactarea paragrafelor 1.2.1 , 2.3

NEAGU Cristian Andrei Redactarea paragrafelor 1.1 ,2.1

ROSU Laura Redactarea paragrafelor 1.2.2, 2.2

SCARLAT Marius Redactarea paragrafelor 3, 2.4

TOFAN Maria Bianca Redactarea paragrafelor 1.2.3, 2.3


3/20

Cuprins

1 Interpolarea polinomiala a functiilor reale.................................................................................. 4

1.1 Scopul lucrarii ........................................................................................................................ 4

1.2 Chestiuni studiate .................................................................................................................. 4

1.2.1 Interpolarea polinomiala Uniforma/Cebisev ................................................................ 5

1.2.2 Analiza algoritmilor-erori.............................................................................................. 7

1.2.3 Analiza algoritmilor- timpi de calcul ........................................................................... 8

2 Studiu individual ........................................................................................................................ 10

2.1 Interpolarea NewtonMatlab ............................................................................................ 10

2.2 Exercitiu Interpolare ............................................................................................................ 11

2.3 Fenomenul Runge ................................................................................................................ 12

2.4 Exercitiu Interpolare ............................................................................................................ 15

3 Observatii si concluzii ................................................................................................................ 16

4 Bibliografie ................................................................................................................................. 20


4/20

1 Interpolarea polinomiala a functiilor reale

1.1

Scopul lucrariiIn lucrarea studiata Interpolarea polinomiala a functiilor reale se prezinta cele mai

eficiente metode de determinare a polinomului de interpolare. Interpolarea reprezintaaproximarea functiilor in alte puncte decat in cele in care ne sunt cunoscute valorile functiei. Inanaliza numerica, interpolarea polinomiala este o tehnica de interpolare a unui set de date sau aunei functii printr-un polinom. Cu alte cuvinte, fiind dat un set de puncte (obinut, de exemplu,ca urmare a unui experiment), vom cauta un polinom care trece prin toate aceste puncte.

Functiile reale se pot reprezenta in sisteme de calcul, prin doua metode principale si diferite:

Prin cod, cu ajutorul algoritmului care permite evaluarea functiei in orice punct aldomeniului de definitie.

Prin date, cu ajutorul unei retea de puncte, din domeniul de definitie, numite noduri.

Se presupune aproximarea functiei, in intervalele dintre nodurile retelei, in oricepunct al domeniului de definite. Una din cea mai simpla metoda de interpolare,consta in aproximarea functiei cu un polinom, evaluarea functiei reducandu-se laoperatii simple ca adunarea si inmultirea.

Exista trei metode cunoscute pentru determinarea polinomului de interpolare: Metoda Clasica:

-determinarea coeficientilor polinomului de interpolare prin rezolvarea unui sistem liniar

de ecuatii algebrice

-evaluarea polinomului interpolant, ordin n Metoda Lagrange:

-timpul necesar evaluarii polinomului de interpolare creste la n2

Metoda Newton:-algoritmul este relative stabil din punct de vedere numeric, avand erori acceptabilerezultatelor.

Observatie:Metodele prezentate mai sus ( Clasica, Lagrange, Newton), sunt metode deinterpolare globala. Cele trei metode cauta un polinom de gran n, ce trece prin cele n+1

puncte ale tabelului de date.

1.2 Chestiuni studiate

1. Interpolarea polinomiala uniforma si Cebisev;2. Analiza algoritmilor-erori;3. Analiza algoritmilor- timpi de calcul .


5/20

1.2.1 Interpolarea polinomiala Uniforma/Cebisev

Functiile f(x) care pot fi interpolate sunt: sin(x) exp(x) ln(|x|) th(x) Runge 1/(1 + x2) |x|

||

Se va studia interpolarea polinomiala pentru functia exponentiala si Runge, aratandu-se modul devariatie a celor doua tipuri de erorii ( Uniforma si Cebisev) , functie de numarul nodurilor deinterpolare ( de la 2 la 10).

Tabelul 1.1-Interpolare functia explonentiala

INTERPOLAREA POLINOMIALA PENTRU FUNCTIA EXPONENTIALA

Nr.

Noduri

Interpolar

e

2 3 4 5 6 7 8 9 10

Eroare

uniforma

2.132426

*10-1

2.714152

*10-2

3.048922

*10-3

3.036941

*10-4

2.674478

*10-5

2.164410

*10-6

1.568781

*10-7

1.007837

*10-8

6.035190

*10-10

Eroare

Cebisev

2.132426*10-1

2.957539*10-2

2.887325*10-3

2.428279*10-4

1.726124*10-5

1.071235*10-6

5.968391*10-8

2.942241*10-9

1.345275*10-10

Observatii: Odata cu cresterea numarului de noduri de interpolare ambele tipuri de erori scad,

ajungand la valori foarte mici. In cazul functiei exponentiale eroarea uniforma este mai mica decat eroarea Cebisev.

Tabelul 1.2-Interpolare functia Runge

INTERPOLARE POLINOMIALA PENTRU FUNCTIA RUNGE

Nr. Noduri

Interpolare 2 3 5 10 15 20

Eroare uniforma 0.645294 0.696815 0.423108 1.783233 2.094101 50.00874

Eroare Cebisev 0.645294 0.818663 0.628641 0.12912 0.093708 0.017552


6/20

Figura 1.1- Efectul Runge pentru cele doua tipuri de erori.-Excel

Figura 1.1.1Efectul Runge pentru cele doua tipuri de eroriMatlabScara Logaritmica


7/20

Observatii:

In cazul interpolarii polinomiale pentru functia Runge, eroarea uniforma, cresteodata cu cresterea numarului de noduri.

In cazul interpolarii polinomiale pentru functia Runge, eroarea Cebisev, scadeodata cu cresterea numarului de noduri

Apar oscilatii foarte mari intre nodurile retelei de discretizare (cand n creste) siavem o instabilitate numerica, atunci cand reteaua este uniforma rezultand un pas

constant.

1.2.2

Analiza algoritmilor-erori

Se determina eroarea de interpolare a functiei sin(x) pe o perioada, in cazulfolosirii metodelor de interpolare: clasica, Lagrange, Newton. Se vor introduce valoareainitiala, valoarea finala, si pasul pentru gradul polinomului de interpolare. Valorile reco-mandate pentru gradul polinomului sunt 1,2,3,4,5,6,7,8 (valoarea initiala 1, valoarea finala8, pas 1).Se vor nota erorile si se vor comenta rezultatele. Se va reprezenta grafic eroarea infunctie de gradul polinomului de interpolare.

Tabelul 1.3- Eroare metoda Newton

EROARE METODA NEWTON

N1 2 3 4 5 6 7 8

Eroare

metoda

Newton 0.999486 0.999486 0.254525 0.175797 0.026755 0.018735 0.001695 0.001201


8/20

Figura 1.2- Metoda Newton

Observatii:

In cazul celorlalte doua metode ( Clasica si Lagrange) valorile sunt identice,asadar, in tabel s-au intordus valori doar pentru o metoda ( Metoda Newton).

Se observa scaderea valorii erorii odata cu cresterea valorii lui n.

Algoritmul este relativ stabil din punct de vedere numeric, avand erori numericeacceptabile ale rezultatelor;

Prin marirea succesiva a gradului polinomului de interpolare pana la atingereapreciziei dorite, timpul de calcul este dependent de eroarea impusa, avand valorimari doar in cazurile in care se doreste o precizie ridicata;

1.2.3

Analiza algoritmilor- Timpi de calcul

Se determina timpul de calcul necesar interpolarii functiei sin(x) pe o perioada, in cazul folosiriimetodelor de interpolare: clasica, Lagrange, Newton. Singura data de intrare este numarul denoduri n din reteauade interpolare.Se va reprezenta grafic modul de varitie a timpului de calcul cu pregatire a celor trei medote

pentru nvariind de la 20 la 100, cu pas 20.

0

0.2

0.4

0.6

0.8

1

1.2

0 1 2 3 4 5 6 7 8 9

MetodaNewton

Numar Noduri

N


9/20

Tabelul 1.4- Timpi de calcul pentru cele trei metode

TIMPI DE CALCUL

Grad

Polinom

Timp 20 40 60 80 100

Lagrange Pregatire - - - - -Evaluare 0.0936006 0.265202 0.608404 1.10761 1.70041

Newton Pregatire 0 0 0.0312002 0.0156001 0.0312002Evaluare 0 0.0156001 0.0156001 0.0156001 0

Clasica Pregatire 0.0156001 0.0780005 0.234001 0.499203 1.01401Evaluare 0 0 0 0.0156001 0.0156001

Figura 1.3- Timpi de calcul

Observatii:

Metoda Lagrange nu are timp de pregatire; Pentru functia Lagrange se afiseaza doar timpul de evaluare; Timp de pregatire: la metoda clasica avem o hiperbola (n3); Timpul de calcul pentru metoda clasica creste foarte mult odata cu n; La metoda Newton avem o parabola (n2).

-0.2

0

0.2

0.4

0.6

0.8

1

1.2

0 20 40 60 80 100 120

Newton

Clasica


10/20

2 Studiu individual

2.1

Interpolarea Newton

Matlab

functionyk = interpl_Newton(x,y,xk)

n = length(y);

iflength(x)~=n,

error('x si y au lungimi diferite');

end

d = y(:);

forj=2:n

fori=n:-1:j

d(i) = (d(i)-d(i-1))/(x(i)-x(i-j+1));

end

end

yk = d(n);

fori=n-1:-1:1

yk = yk.*(xk-x(i)) + f(i);

end

Neagu Cristian[2]


11/20

2.2 Exercitiu Interpolare

Fie functia f(x)=y definita tabelar:

x 2 4 5

y 1 3 2

Se cer:a) Care este gradul polinomului de interpolare globala?

R: Pentru exemplul dat, functia y = f(x) are valori date in 3 noduri si in consecinta gradulpolinomului de interpolare este n = 2.

b) Care sunt conditiile de interpolare?

R: g(2)=1 , g(4)=3, g(5)=2;

c) Care este sistemul de ecuatii asamblat in metoda clasica de interpolare?

R: g(x)=c0+c1x+c2x2

c0+2c1+4c2=1c0+4c1+16c2=3c0+5c1+25c2=3

d) Care sunt polinoamele Lagrange asociate diviziunii [2 4 5] ?

R: lk(x)= 0

=0

;

l0(x)=()()(0)(0)

=(4)(5)(4)(5)

=9+0

6

l1(x)=(0)()(0)()

=()(5)(4)(45)

=7+0

l2(x)=(0)()(0)()

=()(4)(5)(54)

=6+8

3

e) Care este polinomul de interpolare Lagrange?

R: g(x)= ()=0 g(x) =y0l0(x)+y1l1(x)+y2l2(x)

g(x)= 1*9+0

6+3*

7+0

+2*6+8

3=

4+30386


12/20

f) Care este tabelul de diferente divizate?

R: f[x0,x1]=00

=34

=1

f[x1,x2]=

=3

54

=-1

f[x0,x1,x2]=[,][0,]

0=

5

=3

g) Care este polinomul de interpolare Newton?

R: g(x)= y0+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)

1+1*(x-2)+(-3)*(x-2)(x-4) -2x2+15x-19=0

Rosu Laura

2.3 Fenomenul Runge

n analiz numeric, fenomenul Runge este o problema de oscilaie la marginile de un intervalcare se produce la utilizarea polinomului de interpolare cu un grad ridicat. Acesta a fostdescoperit de ctre Carl David Tolm Runge atunci cnd explorarea comportamentul de eroriatunci cnd se utilizeaz polinomului de interpolare a aproximative anumite funcii. nexaminarea acestui aspect, matematicianulDavid Carle Runge Tolm a descoperit un rezultatcontrar intuiie: exist configuraii n care diferena maxim ntre funcia de interpolare i

converge spre infinit odat cun.

Curba roie este funcia Runge, curba albastr este polinom de interpolare de gradul 5 i curba verde estepolinom de interpolare de grad 9. Aproximarea este din ce n ce slab


13/20

Introducere

Teorema de aproximare a lui Weierstrass prevede c fiecare funcie continuf (x)definit pe uninterval [a, b] poate fi aproximat ca limita unui ir uniform convergent de polinoame deinterpolare:

Interpolarea cu puncte echidistante este o abordare natural i bine -cunoscut pentru a construipolinoame aproximare. Fenomenul Runge demonstreaz, totui, c aceast interpolare poatediverge.

Exemplu

Considerm urmtoarea funcie:

Avnd n vedere puncte uniform distribuite n segmentul :

n cele din urm, considerm polinomul de interpolare n punctele , care este polinomul

unic de grad mai mic sau egal cu n astfel nct pentru orice i. Se noteaz cu.

Runge a artat c eroarea de interpolare ntre i tinde la infinit ca n crete. Formal:

De fapt, atunci cnd creterea numrului de puncte, vom vedea c polinomul ncepe s oscilezeputernic ntre punctele de cu amplitudinea n cretere.

Explicatie

Aplicnd n mod repetat teorema lui Rolle, putem arta c n cazul interpolrii

celor puncte distribuite n mod egal, exist un punct n intervalul ncteroarea dintre funcia generatoare i polinomul de interpolare de grad neste dat de

pentru ntre (1,1).


14/20

Astfel,

Rezult c eroarea de aproximare crete la infinit odat cu n.

ntr-un context mai larg, polinomul de interpolare cu noduri echidistante nu este o metodstabil. ntr-adevr, notnd (li) , polinoamele Lagrange debazcorespunztoare elementelor (xi):

avem:

care ne conduce la urmtoarea estimare:

Constanta este numitconstanta Lebesgue asociat punctelor(xi)'. n caz de puncte echidistante, aceast constant poate fi estimat prin:

unde eeste numrul lui Euler n valoare de 2.7183 ... . Vedem c, n acest caz, constantaLebesgue tinde rapid la valori mari, mai repede dect poate converge la funcia polinomial deinterpolaref.

Solutii la fenomenul Runge

Fenomenul Runge demonstreaz c interpolarea polinomial nu este cea mai bun metod deinterpolare a funciilor.

Putem minimiza oscilaiile de polinoame de interpolare folosind polinomul Cebev de

interpolare n loc de puncte distribuite n mod egal pentru a interpola. n acest caz, putem arta

c eroarea de interpolare descrete.

O metod este utilizarea de noduri care sunt distribuite mult mai dens spre marginileintervalului.

O alt metod estemetoda celor mai mici ptrate.


15/20

O alt metod foarte des ntlnit este aproximarea cu funcii spline(acestea sunt polinoame peporiuni; n acest caz, pentru a mbunti aproximarea, vom crete numrul de buci i nugradul de polinoame).

Barbieru Raluca si Tofan Bianca [3]

2.4 Exercitiu Interpolare


x 1 3 5

y 4 1 3

Se cer:h) Care este gradul polinomului de interpolare globala?


i) Care sunt conditiile de interpolare?

R: g(1)=4 , g(3)=1, g(5)=3;

j) Care este sistemul de ecuatii asamblat in metoda clasica de interpolare?

R: g(x)=c0+c1x+c2x2

c0+c1+c2=1c0+3c1+9c2=3c0+5c1+25c2=2

k) Care sunt polinoamele Lagrange asociate diviziunii [1 3 5] ?

R: lk(x)= 0

=0

;

l0(x)=()()(0)(0)

=(3)(5)(3)(3)

=8+5

4

l1(x)=(0)()(0)()

=()(5)(3)(35)

=6+5

4

l2(x)=(0)()(0)()

=()(3)(5)(53)

=4+3

8


16/20

l) Care este polinomul de interpolare Lagrange?

R: g(x)= ()=0 g(x) =y0l0(x)+y1l1(x)+y2l2(x)

g(x)= 4*8+5

4+1*

6+54

+3*4+3

8=

978+98

m)Care este tabelul de diferente divizate?

R: f[x0,x1]=00

=43

=-3/2

f[x1,x2]=

=353

=1

f[x0,x1,x2]=[,][0,]

0=

5/

5=

5

8

n) Care este polinomul de interpolare Newton?


4-3/2*(x-1)+(-58)*(x-1)(x-3) 5x2+4x+7=0

Scarlat Marius Vasile

3 Observatii si concluzii

METODA CLASICA

Dezavantaje:

etapa de pregatire : O(2n3

/3), timpul necesar determinarii coeficientilor ck este foartemare pentru valori mari ale lui n;

pentru valori mari ale lui n,functiile de baza sunr asemanatoare intre ele, matricea

coeficientilor sistemului fiind slab conditionata;

apar erori mari de rotunjire;


17/20

METODA LAGRANGEAvantaje:

erori de rotunjire minime;

matrice bine structurata;

stabilitate numerica buna;

Dezavantaje:

timpul de avaluare creste cu un ordin de marime;

METODA NEWTONAvantaje:

termenii succesivi ai polinomului interpolarii Newton aproximeaza termini

corespunzatori din dezvoltarea in serie Taylor se poate controla eroarea detrunchiere,efortul de calcul putand fi adaptat preciziei impuse solutiei;

atunci cand se adauga un punct suplimentar in reteaua de interpolare se poate porni de lainterpolarea cu un grad mai scazut si trebuie doar adaugat un singur termen in suma ,nefiind necesara refacerea totala a calculelor ci doar evaluarea unui singur termensuplimentar;

Concluzii:

Metodele clasica, Lagrange si Newton dau teoretic acelasi rezultat pentru ca polinomul deinterpolare este unic.Metoda Newton este cea mai eficienta metoda din punct de vedere al timpului de pregatire cat sia celui de evaluare.

Avantajul major este insa acela ca metoda Newton permite controlul erorii de trunchiere.- La functia Runge apar oscilatii foarte mari intre nodurile retelei de discretizare (cand n

creste) si avem o instabilitate numerica, atunci cand reteaua este uniforma rezultand unpas constant.

Analiza experimentala a erorilor de interpolare- Eroarea scade, in timp ce n creste

Analiza experimentala a timpului de calcul- Pentru functia Lagrange se afiseaza doar timpul de evaluare- Timp de pregatire: la metoda clasica avem o hiperbola (n3); timpul de calcul pentru

metoda clasica creste foarte mult odata cu n; la metoda Newton avem o parabola (n 2)- Timp fara pregatire: la metoda Lagrange avem o parabola (n2), iar timpul de evaluare

creste foarte mult; la metodele Clasica, respectiv Newton avem o dreapta (n


18/20

Problema Rezolvata:


x 2 3 5

y 5 7 11

Se cer:a) Care este gradul polinomului de interpolare globala?


b) Care sunt conditiile de interpolare?

R: g(2)=5 , g(3)=7, g(5)=11;

c) Care este sistemul de ecuatii asamblat in metoda clasica de interpolare?

R: g(x)=c0+c1x+c2x2

c0+2c1+4c2=5c0+3c1+9c2=7c0+5c1+25c2=11

d) Care sunt polinoamele Lagrange asociate diviziunii [2 3 5] ?

R: lk(x)= 0

=0

;

l0(x)=()()(0)(0)

=(3)(5)(3)(5)

=8+5

4

l1(x)=(0)()(0)()

=()(5)(3)(5)

=7+0

3

l2(x)=(0)()(0)()=

()(3)(5)(53)=

5+66

e) Care este polinomul de interpolare Lagrange?

R: g(x)= ()=0 g(x) =y0l0(x)+y1l1(x)+y2l2(x)


19/20

g(x)= 5*8+5

4+7*

7+03

+11*5+6

6=2 1

f) Care este tabelul de diferente divizate?

R: f[x0,x1]=0

0=

75

3=2

f[x1,x2]=

=753

=2

f[x0,x1,x2]=[,][0,]

0=

5

=0

g) Care este polinomul de interpolare Newton?


5+2*(x-2)+0*(x-2)(x-3) 2z+1=0

h) In punctual x=4, polinomul de interpolare este

g(4)=2*4+1=9

i) In situatia in care tabelului de valori i se adauga un punct, metoda Newton este cea maiavantajoasa metoda deoarece aceasta permite refolosirea calculelor deja efectuate.Tabelul de diferente divizate se completeaza cu noua valoare astfel:

X Y ord.1

2

2

11/4

ord.2

o

-3/8

ord.3

3/8

2 5

3 7

5 11

1 0

Diferentele divizate care apar prin adaugarea punctului (1, 0) sunt:

f[x2,x3}=11/4f[x1,x2,x3]=-3/8f[x0,x1,x2,x3]=3/8

Polinomul de interpolare este:h(x)=3/8*x^3-15/4*x^2+109/8*x-41/4

Se observa ca nu este nevoie ca punctele diviziunii sa fie sortate. De asemenea, in cazul aplicariimetodei clasice sau Lagrange, efortul de calcul efectuat anterior s-ar fi pierdut.


20/20

STIATI CA?!

Fiind considerat cel mai mare matematician al sec al XVIII-

lea, Napoleon l-a supranumit pirmamida grandioasa a stiintelormatematice pe Joseph-Louis Lagrange ?

In analiza matematica Lagrange a fost cel care a dat formularestului pentru dezvoltari in serie Taylor,formula cresterilor finite si

forma de interpolare?

Newton a fost primul care a demonstrat ca legile naturii guverneaza atat miscarea

globului terestru, cat si a altor corpuri ceresti, intuind ca orbitele pot fi nu numai

eliptice,dar si hiperbolice sau parabolice? Isaac Newton a fost savantul aflat la originea teoriilor stiintifice care vor revolutiona

stiinta, in domeniul opticii,matematicii si in special mecanicii?

4

Bibliografie[1] Gabriela Ciuprina, Mihai Rebican, Daniel Ioan: Metode Numerice n Ingineria Electric.

ndrumar de laborator, Editua Printech, 2013, disponibil lahttp://mn.lmn.pub.ro/indrumar/indrumarLMN2013_20sept2013.pdf.

[2] Aproximarea numerica a functiilor in Matlabhttp://www.rasfoiesc.com/educatie/informatica/matlab/Aproximarea-numerica-a-functii45.php [3]http://ro.wikipedia.org/wiki/Fenomenul_Runge#cite_note-1
http://mn.lmn.pub.ro/indrumar/indrumarLMN2013_20sept2013.pdfhttp://mn.lmn.pub.ro/indrumar/indrumarLMN2013_20sept2013.pdfhttp://www.rasfoiesc.com/educatie/informatica/matlab/Aproximarea-numerica-a-functii45.phphttp://www.rasfoiesc.com/educatie/informatica/matlab/Aproximarea-numerica-a-functii45.phphttp://ro.wikipedia.org/wiki/Fenomenul_Runge#cite_note-1http://ro.wikipedia.org/wiki/Fenomenul_Runge#cite_note-1http://ro.wikipedia.org/wiki/Fenomenul_Runge#cite_note-1http://ro.wikipedia.org/wiki/Fenomenul_Runge#cite_note-1http://www.rasfoiesc.com/educatie/informatica/matlab/Aproximarea-numerica-a-functii45.phphttp://mn.lmn.pub.ro/indrumar/indrumarLMN2013_20sept2013.pdf

lucrarea 6 final

Documents