lucrarea de laborator nr. 6 - ucb sustine …metode numerice - lucrarea de laborator 6 1 lucrarea de...

Metode Numerice - Lucrarea de laborator 6

1

Lucrarea de laborator nr. 6

I. Scopul lucrării

Aproximarea funcţiilor. Polinoame de interpolare.

II. Conţinutul lucrării

1. Polinom de interpolare. Definiţie. Eroarea de interpolare.

2. Polinomul Lagrange de interpolare.

3. Eroarea de interpolare în cazul nodurilor echidistante

4. Eroarea de interpolare în cazul nodurilor Cebîşev

III. Prezentarea lucrării

III.1. Polinom de interpolare. Definiţie. Eroarea de interpolare.

Fie f : [a, b] R o funcţie. Se pune problema determinării unei funcţii F care

să aproximeze funcţia f. O asfel de aproximaţie este necesară în următoarele situaţii:

1) Când nu se cunoaşte expresia analitică a lui f, ci doar valorile sale într-un

număr finit de puncte x0, x1, …, xn din intervalul [a, b].

2) Când expresia analitică a lui f este prea complicată şi calculele efectuate cu

ajutorul acesteia ar fi prea dificile.

F trebuie să fie o funcţie simplă, uşor de evaluat, de diferenţiat şi de integrat. În cele ce

urmează F va fi un polinom.

Definiţie. Fie x0, x1, …, xn n+1 puncte distincte două câte două din intervalul

[a, b] (numite noduri), şi fie yi = f(xi) pentru orice i = 0,1,…n. Se numeşte polinom de

interpolare asociat nodurilor x0, x1, …, xn şi valorilor y0=f(x0), y1= f(x1), …, yn=f(xn)

un polinom Pn care îndeplineşte următoarele condiţii

Mădălina Roxana Buneci Metode Numerice –Laborator - 2019

2

grad(Pn) n

Pn(xi) = yi, i = 0, 1, …, n .

Polinomul determinat de condiţiile anterioare există şi este unic.

Teorema următoare stabileşte eroarea maximă cu care polinomul Pn

aproximează funcţia f:

Teoremă. Fie f : [a, b] R o funcţie de clasă Cn+1. Fie x0, x1, …, xn n+1

puncte distincte din intervalul [a, b], şi yi = f(xi) pentru orice i = 0,1,…n. Fie Pn

polinomul de asociat nodurilor x0, x1, …, xn şi valorilor y0=f(x0), y1= f(x1), …, yn=f(xn).

Atunci oricare ar fi x [a, b], avem:

| f(x) – Pn(x) |

n 1

t a,b

f tsup

n 1 !

|(x – x0) (x – x1) … (x – xn)|.

III.2. Polinomul Lagrange de interpolare.

Fie f : [a, b] R o funcţie, fie x0, x1, …, xn n+1 puncte distincte din intervalul

[a, b], şi yi = f(xi) pentru orice i = 0,1,…n. Se numesc polinoame Lagrange cele n+1

polinoame li, i =0, 1, ...n cu proprietăţile

grad (li) = n

li(xj) = ij = 1, dacă i = j

0, dacă i j

Pentru orice i =0, 1, ...n, deoarece li are gradul n şi admite drept rădăcini pe x0,

x1, ..., xi-1, xi+1, ..., xn, rezultă că

li(X) = Ai(X – x0) (X – x1) …(X – xi-1) (X – xi+1) ... (X – xn).

Cum li(xi) = 1, rezultă

Ai = i 0 i 1 i i 1 i i 1 i n

1

x x x x .... x x x x ... x x ,

şi ca urmare


3

li(x) =

0 1 i 1 i 1 n

i 0 i 1 i i 1 i i 1 i n

x x x x .... x x x x ... x x

x x x x .... x x x x ... x x

Forma Lagrange a polinomului de interpolare este:

Ln(x) = y0l0(x) + y1l1(x) + … + ynln(x)

Se observă uşor că

Ln(xi) = y0l0(xi) + y1l1(xi) + … + ynln(xi) = yili(xi) = yi

pentru orice i = 0, 1, …, n şi că grad(Ln) n. Aşadar Ln este polinomul de interpolare

asociat nodurilor x0, x1, …, xn şi valorilor y0, y1, …, yn.

În consecinţă, polinomul de interpolare asociat nodurilor x0, x1, …, xn şi

valorilor y0, y1, …, yn poate fi scris sub forma

Ln(x) =

n0 1 i 1 i 1 n

ii 0 i 1 i i 1 i i 1 i ni 0

x x x x .... x x x x ... x xy

x x x x .... x x x x ... x x

numită formă Lagrange.

Algoritm pentru determinarea polinomului Lagrange

Date de intrare:

n – numărul de puncte distincte din [a, b] este n +1

x – listă ce conţine cele n+1 puncte distincte din intervalul [a, b],

y – listă ce conţine valorile corespunzătoare ale funcţiei.

x0 x1 … xn

y0 y1 … yn

a – punctul în care se evaluează polinomul.

Date de ieşire:

v - valoarea polinomului în x


4

v : =0;

pentru i = 0,n,1 execută

t : =yi;

pentru j = 0,i - 1,1 execută

t: = t * (a – xj)/ (xi – xj)

sfârșit pentru

pentru j = i + 1,n,1 executa

t: = t * (a– xj)/ (xi – xj)

sfârșit pentru

v : = v + t;

sfârșit pentru

Procedură MAPLE pentru calculul valorii polinomului Lagrange

> PLagrange:=proc(x,y,a)

local n,v,t,i,j;

n:=nops(x);v:=0;

for i from 0 to n-1 do

t:=y[i+1];

for j from 0 to i-1 do

t:=t*(a-x[j+1])/(x[i+1]-x[j+1]) end do;

for j from i+1 to n-1 do

t:=t*(a-x[j+1])/(x[i+1]-x[j+1]) end do;

v:=v+t;

end do;

return v

end proc;

Exemple

> PLagrange([1,-1,3],[2,-5,-1],2);


5

> PLagrange([1,-1,3],[2,-5,-1],-1);

> expand(PLagrange([1,-1,3],[2,-5,-1],X));

Considerăm funcţia f1: R R definită prin f1(x) = xcos(x) şi nodurile x0=0,

x1= 2

3

, x2 =

4

3

şi x3 = 2. Vom aplica procedura PLagrange pentru a determina

polinomul de interpolare P3 asociat nodurilor x0=0, x1= 2

3

, x2 =

4

3

şi x3 = 2 şi

valorilor y0 = f1(x0), y1 = f1(x1), y2 = f1(x2), y3 = f1(x3). De asemenea vom reprezenta

grafic funcţia f1 şi polinomul asociat pe intervalul [0, 2], şi apoi pe intervalul [-

,3].

> f1:=x->x*cos(x);

> x1:=[seq(2*Pi/3*i,i=0..3)];

> y1:=[seq(f1(2*Pi/3*i),i=0..3)];

> expand(PLagrange(x1,y1,X));

> plot([f1(a),PLagrange(x1,y1,a)],a=0..2*Pi);

7

4

-5

5

4X2 7

2X

1

4

:= f1 x x ( )cos x

:= x1

, , ,0

2

3

4

32

:= y1

, , ,0

3

2

32

27 X3

16 2

27 X2

8 X


6

> plot([f1(a),PLagrange(x1,y1,a)],a=-Pi..3*Pi);

III.3. Eroarea de interpolare în cazul nodurilor echidistante

Fie f : [a, b] R o funcţie şi fie x0, x1, …, xn n+1 noduri echidistante din

intervalul [a, b]:

xi = a + ih, i = 0, 1, ...n, h = b a

n

Fie Pn polinomul de asociat nodurilor x0, x1, …, xn şi valorilor y0=f(x0), y1=

f(x1), …, yn=f(xn). Atunci oricare ar fi x [a, b], avem:


7

| f(x) – Pn(x) |

n 1

t a,b

f tsup

n 1 !

|(x – x0) (x – x1) … (x – xn)|.

Pentru orice x [a, b] există i astfel încât x [xi, xi+1] şi ca urmare

|(x – xi) (x – xi+1) h

2

h

2 =

2h

4.

De asemenea se poate arăta că

|(x – xj) (j – i + 1) h pentru i j

|(x – xj) (i – j ) h pentru j+1 i

şi ţinând seama că (j+1)!(n-j)! n! se obţine

|(x – x0) (x – x1) … (x – xn)| n 1h

4

n!,

şi deci eroarea de interpolare satisface:

| f(x) – Pn(x) | n 1h

4(n 1)

n 1

t a,b

f tsup

.

Considerăm funcţia f2: R R definită prin f2(x) = cos(x) + sin(x). Se poate

observa uşor că f(k)(x) 2 pentru orice xR şi orice kN. Vom considera intervalul

[0,2] şi nodurile echidistante corespunzătoare lui n = 3. Eroarea de interpolare este

dominată de 4h

162, unde h =

2

3

> f2:=x->sin(x)+cos(x);

> x2:=[seq(2*Pi/3*i,i=0..3)];

> y2:=[seq(f2(2*Pi/3*i),i=0..3)];

> expand(PLagrange(x2,y2,X));

:= f2 x ( )sin x ( )cos x

:= x2

, , ,0

2

3

4

32

:= y2

, , ,1

3

2

1

2

3

2

1

21


8

> plot({f2(a),PLagrange(x2,y2,a)},a=0..2*Pi);

III.4. Eroarea de interpolare în cazul nodurilor Cebîşev

Pentru n N dat, se numesc noduri Cebîşev (rădăcini ale polinomului Cebîşev

de grad n+1) numerele reale:

xi = 2i 1

cos2n 2

, 0 i n.

Nodurile Cebîşev au proprietatea că

|(x – x0) (x – x1) … (x – xn)| n

1

2

pentru orice x [-1, 1]. Se poate arăta că pentru oricare alte noduri ci, i=0, ...,n.

x [ 1,1]

sup

|(x – c0) (x – c1) … (x – cn)| n

1

2.

Nodurile Cebîşev pot fi scalate şi translatate pentru a putea fi folosite pe un interval

oarecare [a, b]:

27 X2

16 2

27 X

8 1

27 X3 3

16 3

81 X2 3

16 2

27 X 3

8


9

xi = b a

2

2i 1cos

2n 2

+

b a

2

, 0 i n.

Astfel în cazul nodurilor Cebîşev eroarea de interpolare este

| f(x) – Pn(x) | n 1

2n 1

(b a)

2 (n 1)!

n 1

t a,b

f tsup

.

Considerăm funcţia f3: R R definită prin f3(x) = 2

1

1 x. Vom reprezenta

grafic funcţia şi polinoamele de interpolare corespunzătoare nodurilor echidistante,

respectiv nodurilor Cebîşev pentru n = 3 pe intervalul [-1, 1]:

> f3:=x->1/(1+x^2);

> x4:=[seq(-1+2*i/3,i=0..3)];

> y4:=[seq(evalf(f3(-1+2*i/3)),i=0..3)];

> plot([f3(a),PLagrange(x4,y4,a)],a=-1..1);

> x5:=[seq(evalf(cos((2*i+1)/(2*3+2)*Pi)),i=0..3)];

> y5:=[seq(evalf(f3(cos((2*i+1)/(2*3+2)*Pi))),i=0..3)];

:= f3 x1

1 x2

:= x4

, , ,-1

-1

3

1

31

:= y4 [ ], , ,0.5000000000 0.9000000000 0.9000000000 0.5000000000

:= x5 [ ], , ,0.9238795325 0.3826834325 -0.3826834325 -0.9238795325


10

> plot([f3(a),PLagrange(x5,y5,a)],a=-1..1);

> plot([f3(a),PLagrange(x4,y4,a),PLagrange(x5,y5,a)],a=-1..1);

Reprezentăm grafic funcţia şi polinoamele de interpolare corespunzătoare

nodurilor echidistante, pentru n = 3, 6, 9 pe intervalul [-5, 5]:

> x_3:=[seq([seq(-5+10*i/(3*j),i=0..3*j)],j=1..3)];

> y_3:=[seq([seq(evalf(f3(-5+10*i/(3*j))),i=0..3*j)],j=1..3)];

:= y5 [ ], , ,0.5395042867 0.8722604187 0.8722604187 0.5395042867

:= x_3

, ,

, , ,-5

-5

3

5

35

, , , , , ,-5

-10

3

-5

30

5

3

10

35

, , , , , , , , ,-5

-35

9

-25

9

-5

3

-5

9

5

9

5

3

25

9

35

95


11

> plot([f3(a),seq(PLagrange(x_3[j],y_3[j],a), j=1..3)],a=-5..5);


nodurilor Cebîşev pentru n = 3, 6, 9 pe intervalul [-5, 5]:

> x_c3:=

[seq([seq(evalf(5*cos((2*i+1)/(6*j+2)*Pi)),i=0..3*j)],j=1..3)];

> y_c3:=

[seq([seq(evalf(f3(5*cos((2*i+1)/(6*j+2)*Pi))),i=0..3*j)],j=1..3)];

y_3 [ ], , ,0.03846153846 0.2647058824 0.2647058824 0.03846153846 [,[ :=

0.03846153846 0.08256880734 0.2647058824 1. 0.2647058824 0.08256880734, , , , , ,

0.03846153846] 0.03846153846 0.06202143951 0.1147308782 0.2647058824, , , ,[,

0.7641509434 0.7641509434 0.2647058824 0.1147308782 0.06202143951, , , , ,

0.03846153846] ]

x_c3 [ ], , ,4.619397662 1.913417162 -1.913417162 -4.619397662 4.874639561,[,[ :=

3.909157412 2.169418697 0. -2.169418697 -3.909157412 -4.874639561, , , , , ] [,

4.938441703 4.455032621 3.535533905 2.269952498 0.7821723260, , , , ,

-0.7821723260 -2.269952498 -3.535533905 -4.455032621 -4.938441703, , , , ] ]

y_c3 [ ], , ,0.04476509230 0.2145386291 0.2145386291 0.04476509230 [,[ :=

0.04038427927 0.06141935837 0.1752425253 1. 0.1752425253 0.06141935837, , , , , ,

0.04038427927] 0.03938836726 0.04796780633 0.07407407407 0.1625306849, , , ,[,

0.6204268538 0.6204268538 0.1625306849 0.07407407407 0.04796780633, , , , ,

0.03938836726] ]


12

> plot([f3(a),seq(PLagrange(x_c3[j],y_c3[j],a), j=1..3)],a=-5..5);


nodurilor echidistante, respectiv nodurilor Cebîşev pentru n = 9 pe intervalul [-5, 5]:

> plot([f3(a),PLagrange(x_3[3],y_3[3],a),

PLagrange(x_c3[3],y_c3[3],a)],a=-5..5);


13


nodurilor echidistante, pentru n = 5, 10, 15 pe intervalul [-5, 5]:

> x_5:=[seq([seq(-5+10*i/(5*j),i=0..5*j)],j=1..3)];

> y_5:=[seq([seq(evalf(f3(-5+10*i/(5*j))),i=0..5*j)],j=1..3)];

> plot([f3(a),seq(PLagrange(x_5[j],y_5[j],a), j=1..3)],a=-5..5);


nodurilor Cebîşev pentru n = 5, 10, 15 pe intervalul [-5, 5]:

x_5 [ ], , , , ,-5 -3 -1 1 3 5 [ ], , , , , , , , , ,-5 -4 -3 -2 -1 0 1 2 3 4 5, ,

:=

, , , , , , , , , , , , , , ,-5

-13

3

-11

3-3

-7

3

-5

3-1

-1

3

1

31

5

3

7

33

11

3

13

35

y_5 0.03846153846 0.1000000000 0.5000000000 0.5000000000 0.1000000000, , , , ,[[ :=

0.03846153846] 0.03846153846 0.05882352941 0.1000000000 0.2000000000, , , ,[,

0.5000000000 1. 0.5000000000 0.2000000000 0.1000000000 0.05882352941, , , , , ,

0.03846153846] 0.03846153846 0.05056179775 0.06923076923 0.1000000000, , , ,[,

0.1551724138 0.2647058824 0.5000000000 0.9000000000 0.9000000000, , , , ,

0.5000000000 0.2647058824 0.1551724138 0.1000000000 0.06923076923, , , , ,

0.05056179775 0.03846153846, ] ]


14

> x_c5:=

[seq([seq(evalf(5*cos((2*i+1)/(10*j+2)*Pi)),i=0..5*j)],j=1..3)];

>

> y_c5:=

[seq([seq(evalf(f3(5*cos((2*i+1)/(10*j+2)*Pi))),i=0..5*j)],j=1..3)];

> plot([f3(a),seq(PLagrange(x_c5[j],y_c5[j],a), j=1..3)],a=-5..5);

x_c5 4.829629132 3.535533905 1.294095226 -1.294095226 -3.535533905, , , , ,[[ :=

-4.829629132] 4.949107210 4.548159976 3.778747872 2.703204086, , , ,[,

1.408662782 0. -1.408662782 -2.703204086 -3.778747872 -4.548159976, , , , , ,

-4.949107210] 4.975923634 4.784701678 4.409606322 3.865052266, , , ,[,

3.171966420 2.356983682 1.451423384 0.4900856985 -0.4900856985, , , , ,

-1.451423384 -2.356983682 -3.171966420 -3.865052266 -4.409606322, , , , ,

-4.784701678 -4.975923634, ] ]

y_c5 0.04110943251 0.07407407407 0.3738761582 0.3738761582, , , ,[[ :=

0.07407407407 0.04110943251, ] 0.03922543546 0.04611321154, ,[,

0.06544958589 0.1203758761 0.3350834928 1. 0.3350834928 0.1203758761, , , , , ,

0.06544958589 0.04611321154 0.03922543546, , ] 0.03882015305,[,

0.04185261408 0.04891260454 0.06274065346 0.09040470686 0.1525466423, , , , ,

0.3218922278 0.8063319688 0.8063319688 0.3218922278 0.1525466423, , , , ,

0.09040470686 0.06274065346 0.04891260454 0.04185261408 0.03882015305, , , , ]

]


15


nodurilor echidistante, respectiv nodurilor Cebîşev pentru n = 15 pe intervalul [-5, 5]:

> plot([f3(a),PLagrange(x_5[3],y_5[3],a),

PLagrange(x_c5[3],y_c5[3],a)], a=-5..5);


16

lucrarea de laborator nr. 6 - ucb sustine …metode numerice - lucrarea de laborator 6 1 lucrarea de...

Documents