LECTIA 1

Interpolarea Lagrange.

Diferente divizate

1

1. Polinomul de interpolare al lui Lagrange

1. Punerea problemei. Sa presupunem cunoscute valorile functiei

f n n + 1 puncte distincte, xi, (i = 0, n) situate n intervalul [a, b]. Se

pune problema gasirii unui polinom de grad minim P astfel ca:

(1) P (xi) = f(xi), i = 0, n.

In (1) avem n + 1 conditii. Cum un polinom de grad k are k + 1

coeficienti, gradul minim al lui P este de asteptat sa fie n.

Un polinom P care verifica conditiile (1) spunem ca interpoleaza

functia f n punctele xi.

2. Existenta si unicitatea polinomului

de interpolare

Are loc urmatorul rezultat.

Teorema 1. Fiind date punctele distincte xi, i = 0, n exista un unic

polinom de grad n care interpoleaza functia f n punctele xi, i = 0, n.

Demonstratie. Mai ntai demonstram unicitatea unui astfel de poli-

nom si apoi aratam ca exista un polinom de grad n care verifica conditiile

de interpolare (1).

Fie P si Q doua polinoame de grad n care verifica conditiile deinterpolare (1), adica

(2) P (xi) = Q(xi) = f(xi), i = 0, n.

Din (2) rezulta ca polinomul R dat de

R = P Q

2

are n+ 1 radacini, acestea fiind punctele de interpolare xi, i = 0, n.

Pe de alta parte gradR n. De aici obtinem

R = 0

sau

P = Q.

Cu aceasta unicitatea este demonstrata.

Sa cautam polinomul P sub forma

(3) P (x) =ni=0

li(x)f(xi),

unde li n. Pentru ca P dat de (3) sa verifice conditiile de interpolare(1) este suficient ca polinomul li sa verifice conditiile

li(xk) = k,i, k, i = 0, n

unde

k,i =

{0, k 6= i1, k = i.

In adevar daca li verifica conditiile (4) atunci, din (3) obtinem

P (xk) =ni=0

li(xk)f(xi)

=ni=0

i,kf(xi)

= f(xk), k = 0, n.

Tinand seama de (4) li este dat de

(5) li(x) =(x x0) . . . (x xi1)(x xi+1) . . . (x xn)

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

3

Polinomul de interpolare P scris sub forma (3) se noteaza prin

Ln(f ;x0, . . . , xn) iar polinoamele li, i = 0, n se numesc polinoame funda-

mentale de interpolare. Prin urmare

(6) Ln(f ;x0, xn)(x) =ni=0

li(x)f(xi)

Sa observam ca polinoamele fundamentale pot fi scrise si sub forma

(7) li(x) =l(x)

x xi 1

l(xi), i = 0, n

unde l(x) =ni=0

(x xi) se numeste polinomul nodurilor de interpolare.

3. Relatii de recurenta pentru polinoamele

lui Lagrange

Fie xi, i = 0, n, n+ 1 puncte distincte fixate si sa notam prin

L(i)n1(f)(x) := Ln1(f ;x0, x1, . . . , xi1, xi+1, . . . , xn)(x),

Ln(f)(x) = Ln(f ;x0, x1, . . . , xn)(x).

Polinoamele

Ln(f) L(i)n1(f)Ln(f) L(j)n1(f)

i 6= j, sunt polinoame de grad n. Fie An = coefxnLn(f). Putem scrie

(8) Ln(f)(x) L(i)n1(f)(x)

= An(x x0) . . . (x xi1)(x xi+1) . . . (x xn)

4

(9) Ln(f)(x) L(j)n1(f)(x)

= An(x x0) . . . (x xj1)(x xj+1) . . . (x xn)Din (8) si (9) obtinem

(xj xi)Ln(f)(x) = (x xi)L(i)n1(f)(x) (x xj)L(j)n1(f)(x)

sau

(10) Ln(f)(x) =(x xi)L(i)n1(f)(x) (x xj)L(j)n1(f)(x)

xj xi

Formula de recurenta (10) se numeste formula lui Aitken.

Aceasta formula permite calculul valorilor polinomului de interpolare

al lui Lagrange de gradul n cu ajutorul polinoamelor de interpolare a lui

Lagrange de grad n 1.

4. Diferente divizate

Definitie. Fie xi, i = 0, n, n + 1 puncte distincte si f o functie

definita pe o multime ce contine aceste puncte. Se numeste diferenta

divizata de ordinul n pe punctele (xi)i=0,n a functiei f coeficientul lui

xn din polinomul de interpolare al lui Lagrange pe aceste puncte si se

noteaza prin

[x0, x1, . . . , xn; f ].

Din relatia (6) obtinem relatia

(11) [x0, x1, . . . , xn; f ] =ni=0

f(xi)

l(xi).

Exemple. a) [x0; f ] = f(x0)

5

b) [x0, x1; f ] =f(x1) f(x0)

x1 x0c) [x0, x1, x2; f ] =

f(x0)

(x0 x1)(x0 x2)

+f(x1)

(x1 x0)(x1 x2) +f(x2)

(x2 x0)(x2 x1) .

Din relatia (10), identificand coeficientii lui xn din cei doi membri

obtinem urmatoarea relatie de recurenta:

(12) [x0, x1, . . . , xn; f ] =[x0, x1, . . . , xn1; f ] [x1, x2, . . . , xn; f ]

x0 xnCu ajutorul relatiei de recurenta (12), pornind de la valorile functiei

f se poate calcula diferenta divizata pe cele n+ 1 puncte.

5. Polinomul de interpolare al lui Lagrange

sub forma lui Newton

Daca xi, i = 0, n sunt puncte distincte si f o functie definita pe o

multime ce contine aceste puncte atunci

(13) Li(f ;x0, x1, . . . , xi)(x) Li1(f ;x0, x1, . . . , xi1)(x)

= (x x0)(x x1) . . . (x xi1)[x0, . . . , xi; f ]i = 1, n. Din (13) obtinem

ni=1

[Li(f ;x0, . . . , xi)(x) Li1(f ;x0, . . . , xi1)(x)]

=ni=1

(x x0) . . . (x xi1)[x0, x1, . . . , xi; f ]

6

sau

(14) Ln(f ;x0, . . . , xn)(x)

= f(x0) +ni=1

(x x0) . . . (x xi1)[x0, x1, . . . , xi; f ]

Polinomul lui Lagrange scris sub forma (13) se numeste polinomul lui

Lagrange scris sub forma lui Newton si se noteaza adesea prin:

Nn(f ;x0, . . . , xn)(x)=f(x0)+ni=1

(x x0) . . . (x xi1)[x0, x1, . . . , xi; f ]

6. Formula de medie pentru diferente

divizate

Fie f C(n)[a, b] si fie xi [a, b], i = 0, n. Urmatoarea teoremageneralizeaza teorema lui Lagrange.

Teorema. (formula de medie a lui Cauchy).

Exista c (mini=0,n

xi,maxi=0,n

xi) astfel ncat sa avem

(15) [x0, x1, . . . , xn; f ] =f (n)(c)

n!

Formula de medie (15) este formula de medie a lui Cauchy pentru

diferente divizate.

Demonstratie. Vom exprima, mai ntai, diferenta divizata ca un cat

de doi determinanti.

Fie

Ln(f)(x) := Ln(f ;x0, . . . , xn)(x) = a0 + a1x+ + anxn.

7

Impunand conditiile de interpolare (1) obtinem sistemul

(16)

a0 + a1x0 + + anxn0 = f(x0)a1 + a1x1 + + anxn1 = f(x1). . . . . . . . . . . . . . . . . . . . . . . .

a0 + a1xn + + anxnn = f(xn)a0 + a1x+ + anxn = Ln(f)(x)

Conditia de compatibilitate pentru sistemul (16) se scrie:

(17)

1 x0 . . . xn0 f(x0)

1 x1 . . . xn1 f(x1)

. . . . . . . . . . . . . . .

1 xn . . . xnn f(xn)

1 x . . . xn Ln(f)(x)

= 0.

Conditia (17) se poate scrie sub forma

(18)

1 x0 . . . xn0 f(x0)

1 x1 . . . xn1 f(x1)

. . . . . . . . . . . . . . .

1 xn . . . xnn f(xn)

1 x . . . xn 0

+

1 x0 . . . xn0 0

1 x1 . . . xn1 0

. . . . . . . . . . . . . . .

1 xn . . . xnn 0

1 x . . . xn Ln(f)(x)

= 0

Din (18) obtinem

(19) Ln(f)(x) =

1 x0 . . . x

n0 f(x0)

. . . . . . . . . . . . . . .

1 xn . . . xnn f(xn)

1 x . . . xn 0

V (x0, . . . , xn)

8

Din (19) si din definitia diferentei divizate obtinem relatia:

(20) [x0, x1, . . . , xn; f ] =

1 x0 . . . x

n10 f(x0)

1 x1 . . . xn11 f(x1)

. . . . . . . . . . . . . . .

1 xn . . . xn1n f(xn)

V (x0, x1, . . . , xn)

Fie acum g : [a, b] R, definita prin

g(x) =

1 x0 . . . xn10 x

n0 f(x0)

1 x1 . . . xn11 x

n1 f(x1)

. . . . . . . . . . . . . . . . . .

1 xn . . . xn1n x

nn f(xn)

1 x . . . xn1 xn f(x)

Sa observam ca avem:

(21) g(x0) = g(x1) = = g(xn) = 0.

Functia g se anuleaza n (n+ 1) puncte distincte si g Cn+1[a, b].Din teorema lui Rolle, exista c (min

i=0,nxi,max

i=0,nxi) astfel ca

(22) g(n)(c) = 0.

Relatia (22) se scrie sub forma

(23)

1 x0 . . . xn10 x

n0 f(x0)

1 x1 . . . xn11 x

n1 f(x1)

. . . . . . . . . . . . . . . . . .

1 xn . . . xn1n x

nn f(xn)

0 0 . . . 0 n! f (n)(c)

= 0

9

Dezvoltand determinantul (23) dupa ultima linie obtinem

(24)f (n)(c)

n!=

1 x0 . . . x

n10 f(x0)

1 x1 . . . xn11 f(x1)

. . . . . . . . . . . . . . .

1 xn . . . xn1n f(xn)

V (x0, x1, . . . , xn)

Din relatiile (20) si (24) rezulta afirmatia teoremei.

Corolar. Fie k N. Avem:

[x0, x1, . . . , xn;xk] =

{0, daca 0 k n 11, daca k = n.

Rezultatul se obtine imediat din:

(xk)n =

{0, daca 0 k n 1n!, daca k = n.

Daca k n+1 din teorema de medie a lui Cauchy nu putem trage oconcluzie despre valoarea exacta a diferentei functiei xk.

Sa calculam [x0, . . . , xn;xn+1]. Pentru aceasta sa observam ca putem

scrie

(25) xn+1 Ln(xn+1;x0, . . . , xn)(x) = (x x0) . . . (x xn).Cum

(26) (x x0) . . . (x xn) = xn+1 S1xn + S2xn1 + + (1)n+1Sn+1,unde Sk este suma simetrica de ordinul k a numerelor x0, x1, . . . , xn:

S1 =ni=0

xi

S2 =i

Din relatiile (25) si (26) prin identificare obtinem:

[x0, x1, . . . , xn;xn+1] = S1

sau

[x0, x1, . . . , xn;xn+1] = S1.

Folosind aceeasi metoda sa calculam [x0, x1, . . . , xn;xn+2].

Pentru aceasta, sa observam ca polinomul de grad n+ 2 se anuleaza

n punctele xi, i = 0, n. De aici putem scrie:

(27) xn+2 Ln(xn+2;x0, . . . , xn)(x) = (x x0) . . . (x xn)(x ).

Din relatiile (26) si (27), prin identificare, obtinem sistemul

(28)

0 = x0 + x1 + + xn + [x0, x1, . . . , xn;xn+2] = (x0 + + xn) +

i

= l(t)[x0, x1, . . . , xn+1; f ]

Daca n egalitatea (29) punem t = xn+1 obtinem:

(30) f(xn+1) Ln(f ;x0, . . . , xn)(xn+1) = [x0, . . . , xn+1; f ]l(xn+1).

Am obtinut astfel urmatoarea:

Teorema. Pentru orice x [a, b] avem:

(31) f(x) Ln(f ;x0, . . . , xn)(x) = l(x)[x0, . . . , xn, x; f ].

Sa presupunem acum ca f Cn+1[a, b]. Din formula de medie a luiCauchy obtinem existenta unui punct = (x) [a, b] astfel ncat saavem:

(32) f(x) Ln(f ;x0, x1, . . . , xn)(x) = l(x)f(n+1)()

(n+ 1)!

Formula (32) exprima forma restului n cazul n care f Cn+1[a, b].Fie Mn+1 = f (n+1). Din (32) obtinem:

(33) |f(x) Ln(f ;x0, x1, . . . , xn)(x)| |l(x)| Mn+1(n+ 1)!

Formula (33) ne da o estimare a restului, daca cunoastem o delimitare

a normei f (n+1). Din (33) obtinem urmatoareaTeorema. Fie f C[a, b] si T = [xi,j] o matrice triunghiulara

infinita de noduri. Daca pentru linia de noduri

xn,0, xn,1, . . . , xn,n

consideram polinomul de interpolare al lui Lagrange

Ln(f ;xn,0, xn,1, . . . , xn,n)

12

si daca exista M > 0 astfel ca Mn+1 M , pentru orice n N, atunci(34) lim

nf Ln(f ;x0, x1, . . . , xn) = 0.

Demonstratie. Avem

|l(x)| Mn+1(n+ 1)!

(b a)n+1 Mn+1(n+ 1)!

Din (33) obtinem

(35) f Ln(f ;x0, . . . , xn) (b a)n+1 Mn+1(n+ 1)!

Cum limn

(b a)n+1 Mn+1(n+ 1)!

= 0, din relatia (35) obtinem egalitatea

(34) si teorema este demonstrata.

Observatie. Nu se poate renunta la conditia ca derivatele sa fie uni-

form marginite. Un exemplu n acest sens este exemplul dat de Runge.

Runge a considerat functia

f(x) =1

1 + 25x2, x [5, 5]

si nodurile echidistante

xn,i = 5 + 10ni, i = 0, n.

Atunci

limn

f Ln(f ;xn,0, . . . , xn,n) =.Incheiem cu prezentarea fara demonstratie a rezultatului negativ

obtinut de Faber si Bernstein.

Fie T o matrice triunghiulara infinita de noduri din intervalul [a, b]

T =

x0,0

x1,0 x1,1

. . . . . . . . .

xn,0 xn,1 . . . xn,n

. . . . . . . . . . . .

13

Teorema lui Faber si Bernstein afirma ca exista o functie con-

tinua definita pe [a, b] pentru care sirul de polinoame a lui Lagrange

(Ln(f ;xn,0, xn,1, . . . , xn,n))nN diverge.

Rezultatul de mai sus trebuie sa ne faca precauti atunci cand vrem

sa aproximam o functie cu un sir de polinoame de interpolare.

Probleme propuse

1. Fie (xi)iN puncte distincte din intervalul [a, b], x0 < x1 < x2 t

Sa se arate ca daca f Cn+1[a, b] atunci

f(x) Ln(f ;x0, x1, . . . , xn)(x) = ba

Kn(x, t)f(n+1)(t)dt.

3. Fie A : D[a, b] R o functionala liniara de forma

A(f) =n

k=0

ckf(xk),

unde D[a, b] este multimea tuturor functiilor f definite pe punctele

distincte xk, k = 0, n. Sa se arate ca

A(f) =n

k=0

ak[x0, x1, . . . , xk; f ]

14

unde

ak =n

j=k

cj(xj x0) . . . (xj xk1).

4. Fie Bn(f)(x) =n

k=0

(n

k

)xk(1 x)nkf

(k

n

). Sa se arate ca

Bn(f)(x) =n

k=0

k!

nk

(n

k

)[0,

1

n,2

n, . . . ,

k

n; f

]xk.

5. Fie xi, i = 0, n noduri distincte si 0 k < n, un numar naturalfixat. Sa se arate ca:

[x0, x1, . . . , xn; (xx0)(xx1) . . . (xxk)f ] = [xk+1, xk+2, . . . , xn; f ].

6. Fie x0, x1, . . . , xn, puncte distincte si y1, y2, . . . , ym puncte distincte

astfel ca yk 6= xi, i = 0, n, k = 1,m. Sa se arate ca[x0, x1, . . . , xn;

f

(x y1)(x y2) . . . (x ym)]

= [x0, x1, . . . , xn, y1, y2, . . . , ym; f ].

7. Folosind eventual ex. 6 sa se calculeze[x0, x1, . . . , xn;

1

ax+ b

], xi 6= xj, i 6= j, a 6= 0.

8. Fie f, g doua functii definite pe intervalul [a, b] si xi, i = 0, n puncte

distincte din acest interval. Sa se demonstreze egalitatea

[x0, x1, . . . , xn; fg] =n

k=0

[x0, x1, . . . , xk; f ][xk, xk+1, . . . , xn; g]

(Formula lui T. Popoviciu).

15

9. Sa se calculeze

[0, 1, . . . , n;

1

x2 + 1

].

10. Sa se calculeze

[0, 1, . . . , n;

xn+1

x+ 1

].

11. Sa se arate ca o functie f , f : [a, b] R, este convexa pe [a, b]daca si numai daca pentru orice puncte distincte x1, x2, x3 din [a, b]

avem

[x1, x2, x3; f ] 0.

12. Fie n+1 multimea polinoamelor de grad n + 1 avand coeficientul

dominant 1. Sa se arate ca pentru orice l n+1 avem:

maxx[1,1]

|l(x)| 12n

egalitatea fiind atinsa pentru polinomul lui Cebasev:

Tn+1 =1

2ncos[(n+ 1) arccos x].

16