interpolation_jav_roman.pdf
TRANSCRIPT
Interpolare
Dr. István Blahota
1 Ce este interpolarea?
Interpolarea este un procedeu matematic, pe parcursul c ruia leg m punctecu o curb aparµinând unei clase de funcµii dat .
Întrucât punctele aparµin unei oarecare funcµii, curba de interpolare aprox-imeaz curba funcµiei date. Pentru a putea s aproxim m o funcµie, evidenttrebuie s dispunem de informaµii despre ea. În baza acestor informaµii putemobµine diverse procedee de aproximare a funcµiilor. Unul dintre acestea estedeci, interpolarea.
Interpolarea are nenum rate aplicaµii practice. Adesea este utilizat deexemplu pentru �netezirea� gra�celor �colµuroase� provenite din procedeele dee³antionare. Cu o tehnologie asem n toare acesteia se retu³eaz imaginilem rite, a³a cum putem observa în �gura 1.
2 Interpolarea
2.1 Noµiuni de baz
Notaµie: S reprezinte R mulµimea numerelor reale, P mulµimea numerelorîntregi pozitive ³i N mulµimea numerelor întregi nenegative.
De�niµie 1. Fie [a, b] ⊂ R un interval real. Funcµia L(x) rezultat din com-binaµia liniar arbitrar a a³a-numitelor funcµii elementare ψ1(x), . . . , ψn(x) :[a, b]→ R, o numim polinomul generalizat al funcµiilor elementare.
1
Figura 1: M rirea imaginii cu interpolare (în stânga) ³i f r
Observaµie: Noi ne vom ocupa exclusiv cu funcµii reale, respectiv cu combi-naµii liniare reale, deci în cazul nostru
L(x) =n∑k=1
ckψk(x), ck ∈ R.
Observaµie: Denumirea de �polinom� provine evident din faptul c alegereaψn(x) = xn−1 d polinoamele clasice.
Cu astfel de polinoame generalizate L(x) vrem s aproxim m o funcµief(x).
De�niµie 2. S consider m funcµia f(x) : [a, b]→ R, despre care ³tim doar,c în diferite puncte x1, . . . , xN ∈ [a, b] (în a³a-numitele noduri) se cunoscvalorile funcµiei. Pe parcursul interpol rii c ut m acele constante reale c1, . . . ,cn aparµin toare funcµiilor elementare �xate ψ1(x), . . . , ψn(x), care determin funcµia
L(x) =n∑k=1
ckψk(x),
undeL(xi) = f(xi), ∀i ∈ {1, . . . , N}.
În acest caz numim funcµia L(x), polinomul (generalizat) de interpolare afuncµiilor elementare.
2
Observaµie: Existenµa lui L(x) nu este evident , precum nici faptul c , dac exist o asemenea funcµie, atunci în ce condiµii este univoc acea funcµie.
Observaµie: Se poate întâmpla, c nu funcµia f(x) este cunoscut , ci doarsunt date puncte de abcise diferite în plan, la care am dori s tras m înanumite condiµii o curb . În acest caz putem folosi f r probleme în loc def(xi) pe yi, unde yi indic ordonata care aparµine lui xi.
Observaµie: Indexarea nodurilor nu înseamn neap rat ³i ordinea lor înfuncµie de m rime.
2.2 Rezolvabilitate, rezolvare
De�niµie 3. Spunem despre un sistem de funcµii elementare ψ1(x), . . . , ψn(x)c este de tip Cebî³ev, dac polinomul generalizat L(x) rezultat din el, ar-bitrar, dar nu identic nul, are cel mult n − 1 zerouri diferite pe intervalul[a, b].
Teorem 1. Dac un sistem de funcµii elementare este de tip Cebî³ev, atuncisistemul este liniar independent.
Demonstraµie. Trebuie s ar t m, c în cazul în care
L(x) =n∑k=1
ckψk(x) = 0, ∀x ∈ [a, b]
atuncic1 = · · · = cn = 0.
Deoarece, în caz contrar ar exista L(x) =∑n
k=1 ckψk(x) = 0, pentru ∀x ∈pe[a, b] nu doar cu coe�cienµi 0, ceea ce s-ar contrazice faptului, c L(x) arecel mult n− 1 zerouri diferite pe [a, b].
De acum, în partea ce urmeaz din curs, presupunem c num rul nodurilor³i num rul de funcµii a sistemului de baz corespund, adic N = n.
Teorem 2. Pentru o funcµie f(x) : [a, b] → R ³i pentru nodurile x1, . . . ,xn ∈ [a, b] alese arbitrar exist exact un polinom generalizat de interpolare,dac sistemul de funcµii elementare ψ1, . . . , ψn este de tip Cebî³ev pe [a, b].Dac aceast condiµie este îndeplinit , atunci polinomul de interpolare esteunivoc.
3
Demonstraµie. Egalit µile∑n
k=1 ckψk(xi) = f(xi), i ∈ {1, . . . , n} le putemscrie ³i sub form matriceal :
ψ1(x1) . . . ψn(x1). . .. . .. . .
ψ1(xn) . . . ψn(xn)
c1...cn
=
f(x1)...
f(xn)
,
sau ³i mai scurt: Ψc = f .Deoarece matricea Ψ care �gureaz în partea stâng este p trat , obµinem
univoc coe�cienµii c utaµi, dac determinantul ei Ψ nu este nul, notat scurt|Ψ| 6= 0.
Demonstr m c , condiµia |Ψ| 6= 0 ³i faptul c sistemul de funcµii ele-mentare ψ1, . . . , ψn este de tip Cebî³ev, sunt echivalente.
S presupunem mai întâi, c |Ψ| = 0. Atunci coloanele matricei Ψ suntliniar dependente, astfel exist coe�cienµi d1, . . . , dn nu toµi nuli, pentru careL(xi) =
∑nk=1 dkψk(xi) = 0, pentruorice ∀i ∈ {1, . . . , n}. Aceasta înseamn ,
c L(x) are cel puµin n zerouri, astfel ψ1, . . . , ψn nu este de tip Cebî³ev pe[a, b].
Pe de alt parte, dac ψ1, . . . , ψn nu este un sistem de funcµii elementarede tip Cebî³ev pe [a, b], atunci exist o funcµie L(x) =
∑nk=1 ckψk(x) cu
cel puµin un coe�cient ck diferit de zero, care are cel puµin n zerouri pe[a, b]. S alegem dintre zerouri n noduri, �e acestea x1, . . . , xn. Atunci∑n
k=1 ckψk(xi) = 0, i ∈ {1, . . . , n} este un sistem de ecuaµii liniar omogen,care are o soluµie netrivial . În acest caz îns |Ψ| = 0.
Iar faptul c polinomul de interpolare este univoc, rezult imediat din|Ψ| 6= 0.
Observaµie: S observ m, c pentru univocitatea soluµiei am ales ca num rulnodurilor ³i al funcµiilor sistemului de baz s �e acela³i. Dac alegem preamulte noduri, raportat la funcµiile sistemului de baz , se poate întâmpla, s nu se formeze un polinom de interpolare, pe când în caz invers, dac nodurilesunt prea puµine, putem obµine prea multe (in�nit de multe) soluµii.
Un exemplu pentru prima situaµie este, c prin trei puncte de poziµiegeneral , nu putem trasa o dreapt (în acest caz sistemul de baz const dinfuncµiile 1 ³i x), pe când pentru a doua situaµie rezult c prin dou punctepot trece in�nit de multe parabole (sistemul de baz este tripletul 1, x ³ix2).
Exerciµiu 1. Fie ψ1(x) = 1, ψ2(x) = x, ψ3(x) = 2x, ψ4(x) = sin(πx2
),
iar nodurile s �e x1 = −1, x2 = 0, x3 = 1, x4 = 2, de asemenea se mai
4
cunoa³te, c f(x1) = 1, f(x2) = −1, f(x3) = 1, f(x4) = 2. S scriemecuaµia polinomului generalizat de interpolare !
Rezolvare. Pentru scrierea sistemului de ecuaµii necesar rezolv rii exerciµiu-lui, vom aplica primii pa³i în demonstrarea teoremei 2. Deoarece
1 −1 2−1 sin(π·(−1)
2
)1 0 20 sin
(π·02
)1 1 21 sin
(π·12
)1 2 22 sin
(π·22
) =
1 −1 1
2−1
1 0 1 01 1 2 11 2 4 0
,
sistemul de ecuaµii va � urm torul:
c1 −c2 +12c3 −c4 = 1
c1 +c3 = −1c1 +c2 +2c3 +c4 = 1c1 +2c2 +4c3 = 2
.
Sistemul de ecuaµii obµinut se poate rezolva univoc, soluµia lui va � c1 = −9,c2 = −21
2, c3 = 8, c4 = 9
2, adic ecuaµia polinomului generalizat c utat va �:
L(x) = −9− 21
2x+ 8 · 2x +
9
2sin(πx
2
).
Se poate observa u³or, c L(−1) = 1, L(0) = −1, L(1) = 1, L(2) = 2, adic funcµia obµinut are chiar proprietatea dorit , a³a cum se ³i poate vedea în�gura 2.
−1 0 1 2
1
−1
2
Figura 2: Funcµia L(x) = −9− 21
2x+ 8 · 2x +
9
2sin(πx
2
)
5
3 Interpolarea polinomial
A³a cum am putut vedea în exerciµiul 1., prin alegerea special a funcµiilorelementare putem obµine o funcµie de interpolare concret .
Cel mai des interpol m cu polinoame clasice, adic ψ1(x) = 1, ψ2(x) =x, ψ3(x) = x2, . . . , ψn(x) = xn−1, pe scurt �e ψk(x) = xk−1, unde k ∈{1, . . . , n}. În cele ce urmeaz ne vom ocupa doar de acest caz, astfel dac vorbim de interpolare, atunci începând de acum ne gândim exclusiv la inter-polare polinomial .
Observaµie: Fie acum de�nit 00, ap rut în cazul k = 1 ³i x = 0, iar valoareasa s �e 1.
3.1 Unicitate ³i existenµ
Teorem 3. Sistemul de funcµii elementare ψk(x) = xk−1, k ∈ {1, . . . , n}este de tip Cebî³ev.
Demonstraµie. În cazul interpol rii polinomiale, polinomul de interpolareaparµin toare sistemului de funcµii elementare cu n elemente este de cel multgrad n− 1. Astfel în cazul în care acesta nu are funcµia identic nul , atunciconform teoremei fundamentale a algebrei nici num rul r d cinilor sale nupoate � mai mare de n − 1. Aceasta semni�c chiar a�rmaµia care trebuiedemonstrat .
Observaµie: Din aceasta rezult ( folosind teorema 2.), c în cazul interpol riipolinomiale întotdeauna exist polinom de interpolare, ³i acesta este univoc.
Observaµie: S observ m, c în cazul interpol rii polinomiale matricea Ψformat � s not m în cele ce urmeaz cu V (x1, . . . , xn) � îmbrac forma demai jos: 1 x1 . . . xn−11
......
. . ....
1 xn . . . xn−1n
.
De�niµie 4. Fie xk ∈ R, k ∈ {1, . . . , n}. Matricea V (x1, . . . , xn) o numimmatricea Vandermonde.
Teorem 4. Determinantul matricei Vandermonde va �
|V (x1, . . . , xn)| =∏
1≤j<i≤n
(xi − xj).
6
Demonstraµie. Demonstraµia o realiz m conform inducµiei complete referi-toare la n.
Întrucât n = 2, atunci
|V (x1, x2)| =∣∣∣∣ 1 x1
1 x2
∣∣∣∣ = x2 − x1,
ceea ce ne-am ³i dorit.S presupunem c determinantul Vandermonde pentru n − 1 are forma
corespunz toare, adic
|V (x1, . . . , xn−1)| =∏
1≤j<i≤n−1
(xi − xj).
S calcul m valoarea lui
|V (x1, . . . , xn)| =
∣∣∣∣∣∣∣1 x1 . . . xn−11...
.... . .
...1 xn . . . xn−1n
∣∣∣∣∣∣∣. Prima dat sc dem ultimul rând din toate cel lalte rânduri. Valoareadeterminantului nu se modi�c :
|V (x1, . . . , xn)| =
∣∣∣∣∣∣∣∣∣0 x1 − xn . . . xn−11 − xn−1n...
.... . .
...0 xn−1 − xn . . . xn−1n−1 − xn−1n
1 xn . . . xn−1n
∣∣∣∣∣∣∣∣∣ .Dezvoltând determinantul dup coloana întâi, obµinem
|V (x1, . . . , xn)| = (−1)n+1
∣∣∣∣∣∣∣∣∣x1 − xn . . . xn−11 − xn−1n
x2 − xn . . . xn−12 − xn−1n...
. . ....
xn−1 − xn . . . xn−1n−1 − xn−1n
∣∣∣∣∣∣∣∣∣ .Dac scoatem din primul rând pe (x1−xn), din al doilea pe (x2−xn), ³i a³amai departe, din ultimul pe (xn−1 − xn), rezult determinantul de mai jos:∣∣∣∣∣∣∣∣∣
1 x1 + xn x21 + x1xn + x2n . . . xn−21 + xn−31 xn + · · ·+ xn−2n
1 x2 + xn x22 + x2xn + x2n . . . xn−22 + xn−32 xn + · · ·+ xn−2n...
......
. . ....
1 xn−1 + xn x2n−1 + xn−1xn + x2n . . . xn−2n−1 + xn−3n−1xn + · · ·+ xn−2n
∣∣∣∣∣∣∣∣∣ .7
Iar din ultima coloan , din penultima coloan , ³i a³a mai departe pân la adoua coloan a acestuia, sc zând una dup alta coloana anterioar înmulµit cu xn, îl obµinem chiar pe |V (x1, . . . , xn−1)|. La pasul urm tor schimb mîntre ei membrii desc zuµi ³i membrii sc z tori existenµi între paranteze, apoiaplic m condiµia inducµiei:
|V (x1, . . . , xn)| = (x1 − xn) . . . (xn−1 − xn)(−1)n+1|V (x1, . . . , xn−1)|= (xn − x1) . . . (xn − xn−1)|V (x1, . . . , xn−1)|= (xn − x1) . . . (xn − xn−1)
∏1≤j<i≤n−1
(xi − xj)
=∏
1≤j<i≤n
(xi − xj).
Cu aceasta am terminat demonstraµia.
Observaµie: Deoarece nodurile noastre sunt diferite, determinantul matriceiVandermonde rezultat în cazul interpol rii polinomiale difer întotdeaunade zero. ³i din aceasta rezult deci, c în cazul interpol rii polinomiale în-totdeauna exist un polinom de interpolare de cel înalt grad n − 1, ³i acelpolinom este univoc.
3.2 Determinarea polinomului de interpolare
3.2.1 Metoda clasic
Polinomul de interpolare îl putem determina prin rezolvarea sistemuluiregulat de ecuaµii liniare obµinut. S numim aceast metoda clasic . Re-zolvarea sistemului de ecuaµii în sine se poate realiza utilizând o metod arbitrar cunoscut , de exemplu metoda de eliminare Gauss sau regula luiCramer.
Exerciµiu 2. S consider m nodurile x1 = −1, x2 = 0, x3 = 1, x4 = 2,respectiv, s presupunem c f(x1) = 1, f(x2) = −1, f(x3) = 1, f(x4) = 2.S determin m funcµia de interpolare!
Rezolvare. Deoarece1 −1 (−1)2 (−1)3
1 0 02 03
1 1 12 13
1 2 22 23
=
1 −1 1 −11 0 0 01 1 1 11 2 4 8
,
8
sistemul de ecuaµii va � urm torul:
c1 −c2 +c3 −c4 = 1c1 = −1c1 +c2 +c3 +c4 = 1c1 +2c2 +4c3 +8c4 = 2
.
Rezolvarea sistemului de ecuaµii c1 = −1, c2 = 56, c3 = 2, c4 = −5
6, adic
ecuaµia polinomului c utat va �:
L(x) = −1 +5
6x+ 2x2 − 5
6x3.
Putem observa, c L(−1) = 1, L(0) = −1, L(1) = 1, L(2) = 2, adic polinomul obµinut chiar dispune de propriet µile dorite, a³a cum se poatevedea pe �gura 3.
−1 0 1 2
1
−1
2
Figura 3: Funcµia L(x) = −1 +5
6x+ 2x2 − 5
6x3
3.2.2 Interpolare Lagrange
Cu ajutorul interpol rii Lagrange putem realiza o funcµie de interpolareprintr-o alt metod , mai constructiv .
Fie −∞ < a ≤ x1, . . . , xn ≤ b < ∞ noduri. În primul rând obµinemfuncµii lk(x), pentru care
lk(x) =
{1 dac x = xk0 dac x = xi, unde i ∈ {1, . . . n}, dar i 6= k.
9
Polinom de cel înalt grad n− 1 cu astfel de propriet µi, putem obµine înfelul urm tor:
lk(x) =(x− x1) . . . (x− xk−1)(x− xk+1) . . . (x− xn)
(xk − x1) . . . (xk − xk−1)(xk − xk+1) . . . (xk − xn)=
n∏i=1i 6=k
x− xixk − xi
.
Se poate observa u³or, c aceste funcµii au chiar propriet µile dorite.Deoarece în nodurile x1, . . . , xn se cunosc valorile funcµiei f(x) de aproxi-
mat, cu ajutorul funcµiilor lk(x) astfel de�nite putem obµine u³or acel polinomde cel înalt grad n− 1, notat cu L(x), care ia acelea³i valori în noduri, ca ³if(x), a³a cum am putut observa ³i în de�niµia 5.
De�niµie 5. Funcµia
L(x) =n∑k=1
f(xk)lk(x) =n∑k=1
f(xk)n∏i=1i 6=k
x− xixk − xi
îl numim polinomul de interpolare Lagrange corespunz tor nodurilor x1, . . . , xn.
Observaµie: Dac n = 1, atunci L(x) = f(x1).
Observaµie: S observ m, c în cazul unui num r de n noduri polinomul deinterpolare Lagrange va � un polinom de cel înalt grad n − 1, ba chiar a³acum se observ ³i din construcµia sa, trebuie s corespund cu polinomul deinterpolare adecvat.
Exerciµiu 3. S consider m nodurile x1 = −1, x2 = 0, x3 = 1, x4 = 2,respectiv s presupunem, c f(x1) = 1, f(x2) = −1, f(x3) = 1, f(x4) = 2.S determin m polinomul de interpolare Lagrange!
Rezolvare. S scriem prima dat funcµiile lk(x), k ∈ {1, 2, 3, 4}:
l1(x) =x(x− 1)(x− 2)
(−1− 0)(−1− 1)(−1− 2)= −x(x− 1)(x− 2)
6,
l2(x) =(x+ 1)(x− 1)(x− 2)
(0− (−1))(0− 1)(0− 2)=
(x+ 1)(x− 1)(x− 2)
2,
l3(x) =(x+ 1)x(x− 2)
(1− (−1))(1− 0)(1− 2)= −(x+ 1)x(x− 2)
2,
l4(x) =(x+ 1)x(x− 1)
(2− (−1))(2− 0)(2− 1)=
(x+ 1)x(x− 1)
6.
10
De aici
L(x) = 1 ·(−x(x− 1)(x− 2)
6
)+ 0 · (x+ 1)(x− 1)(x− 2)
2
−1 ·(−(x+ 1)x(x− 2)
2
)+ 2 · (x+ 1)x(x− 1)
6
= −1 +5
6x+ 2x2 − 5
6x3,
a³a cum era de a³teptat, deoarece nu puteam obµine alt rezultat, decât încazul exerciµiului 3.
3.2.3 Interpolarea iterativ a lui Neville
Punctul slab al metodelor prezentate pân acum, const în faptul c dac lu m un nod nou, trebuie s începem din nou toate calculele, calculeleparµiale formate anterior nu vor � de niciun folos.
Acest neajuns este remediat de metodele de interpolare iterativ . În celece urmeaz vom face cuno³tinµ cu una dintre ele, ³i anume interpolareaiterativ a lui Neville. O metod asem n toare a fost elaborat ³i de c treAitken.
Notaµie: Notaµi cu L(n1,...,nk)(x) polinomul de interpolare generat de nodurilexn1 , . . . , xnk
.Metoda lui Neville se bazeaz pe urm toarea identitate.
Teorem 5. Fie 1 ≤ k < n. Atunci
L(k,...,n)(x) =1
xn − xk
∣∣∣∣ L(k,...,n−1)(x) xk − xL(k+1,...,n)(x) xn − x
∣∣∣∣ .Demonstraµie. S not m expresia din partea dreapt a egalit µii cu L̃(k,...,n)(x).
S presupunem prima dat , c x = xl, unde k < l < n. Atunci
L̃(k,...,n)(x) =1
xn − xk
∣∣∣∣ f(xl) xk − xlf(xl) xn − xl
∣∣∣∣=
1
xn − xkf(xl)(xn − xk) = f(xl)
= L(xl).
11
Fie apoi x = xk. În acest caz
L̃(k,...,n)(x) =1
xn − xk
∣∣∣∣ f(xk) 0L(k+1,...,n)(xk) xn − xk
∣∣∣∣=
1
xn − xkf(xk)(xn − xk) = f(xk)
= L(xk).
În mod asem n tor, dac x = xn, atunci
L̃(k,...,n)(x) =1
xn − xk
∣∣∣∣ L(k,...,n−1)(xn) xk − xnf(xn) 0
∣∣∣∣=
1
xn − xk(−f(xn)(xk − xn)) = f(xn)
= L(xn).
Am demonstrat deci, c L̃(k,...,n)(xl) = f(xl), pentruorice ∀l ∈ {k, . . . , n}. Pede alt parte, deoarece L(k,...,n−1)(x) ³i L(k+1,...,n)(x) sunt polinoame de celmare grad n − k − 1, de aceea L̃(k,...,n)(x) este un polinom de cel mare gradn− k.
Rezumând toate acestea rezult c L̃(k,...,n)(x) datorit univocit µii nupoate � altul, decât un polinom de interpolare corespunz tor nodurilor xk, . . . ,xn, adic
L̃(k,...,n)(x) = L(k,...,n)(x).
Acest lucru am dorit s îl demonstr m.
Aplicând teorema de mai sus � înaintând de la un rând la alt rând ³iutilizând calculele anterioare � putem calcula pân la adâncimea dorit dateletabelului Neville de mai jos:
x1 x1 − x L(1)(x)x2 x2 − x L(2)(x) L(1,2)(x)x3 x3 − x L(3)(x) L(2,3)(x) L(1,2,3)(x)x4 x4 − x L(4)(x) L(3,4)(x) L(2,3,4)(x) L(1,2,3,4)(x)...
......
......
.... . .
Exerciµiu 4. S consider m nodurile x1 = −1, x2 = 0, x3 = 1, x4 = 2,respectiv s presupunem, c f(x1) = 1, f(x2) = −1, f(x3) = 1, f(x4) = 2.S determin m polinomul de interpolare utilizând metoda lui Neville!
12
Rezolvare. S complet m primele patru rânduri ale tabelului de tip Neville!Cu ocazia complet rii rândurilor de la stânga la dreapta s folosim atâtelementele rândului actual, cât ³i elementele rândurilor precedente!
Completarea primului rând este trivial :
−1 − 1− x 1.
Deoarece
L(1,2)(x) =1
x2 − x1
∣∣∣∣ L(1)(x) x1 − xL(2)(x) x2 − x
∣∣∣∣ =1
0− (−1)
∣∣∣∣ 1 −1− x−1 0− x
∣∣∣∣= −1− 2x,
al doilea rând se formeaz în felul urm tor:
0 0− x − 1 − 1− 2x.
Acum urmeaz L(2,3)(x) ³i L(1,2,3)(x):
L(2,3)(x) =1
x3 − x2
∣∣∣∣ L(2)(x) x2 − xL(3)(x) x3 − x
∣∣∣∣ =1
1− 0
∣∣∣∣ −1 0− x1 1− x
∣∣∣∣= −1 + 2x,
L(1,2,3)(x) =1
x3 − x1
∣∣∣∣ L(1,2)(x) x1 − xL(2,3)(x) x3 − x
∣∣∣∣=
1
1− (−1)
∣∣∣∣ −1− 2x −1− x−1 + 2x 1− x
∣∣∣∣= −1 + 2x2,
de aceea al treilea rând va �:
1 1− x 1 − 1 + 2x − 1 + 2x2.
Mai r mâne determinarea lui L(3,4)(x), L(2,3,4)(x) ³i L(1,2,3,4)(x):
L(3,4)(x) =1
x4 − x3
∣∣∣∣ L(3)(x) x3 − xL(4)(x) x4 − x
∣∣∣∣ =1
2− 1
∣∣∣∣ 1 1− x2 2− x
∣∣∣∣= x,
L(2,3,4)(x) =1
x4 − x2
∣∣∣∣ L(2,3)(x) x2 − xL(3,4)(x) x4 − x
∣∣∣∣ =1
2− 0
∣∣∣∣ −1 + 2x 0− xx 2− x
∣∣∣∣= −1 +
5
2x− 1
2x2
13
³i în sfâr³it
L(1,2,3,4)(x) =1
x4 − x1
∣∣∣∣ L(1,2,3)(x) x1 − xL(2,3,4)(x) x4 − x
∣∣∣∣=
1
2− (−1)
∣∣∣∣ −1 + 2x2 −1− x−1 + 5
2x− 1
2x2 2− x
∣∣∣∣= −1 +
5
6x+ 2x2 − 5
6x3.
Evident ³i în acest caz am obµinut acelea³i soluµii ca ³i în cazul exerciµiului2. ³i 3.
S scriem aici ³i al patrulea rând:
2 2− x 2 x − 1 +5
2x− 1
2x2 − 1 +
5
6x+ 2x2 − 5
6x3.
În �gura 4. putem vedea în prezentare animat polinoamele de interpo-lare: L(1)(x) corespunz tor punctului x1, L(1,2)(x) corespunz tor punctelorx1, x2, L(1,2,3)(x) corespunz tor punctelor x1, x2, x3 ³i L(1,2,3,4)(x) corespunz -tor punctelor x1, x2, x3, x4 (în varianta tip rit se poate vedea L(1)(x)).
Figura 4: Pa³ii interpol rii iterative
3.3 Estimarea erorilor, convergenµ
3.3.1 Noduri de poziµie general
Notaµie:
ω(x) =n∏k=1
(x− xk).
14
Teorem 6. Fie funcµia f(x) de n ori derivabil pe intervalul [a, b]. Atuncipentru ∀x ∈ [a, b] exist ∃ξ ∈ [a, b], astfel încât
f(x)− L(x) =f (n)(ξ)
n!ω(x).
Demonstraµie. Dac x = xk este îndeplinit pentru oarecare k ∈ {1, . . . , n},atunci f(xk) = L(xk) ³i ω(xk) = 0, astfel egalitatea de demonstrat esteîndeplinit .
Deci, s presupunem c x ∈ [a, b] nu este nod. Atunci ω(x) 6= 0, de aceeaputem de�ni funcµia de mai jos:
g(z) = f(z)− L(z)− ω(z)
ω(x)(f(x)− L(x)), z ∈ [a, b],
care datorit condiµiilor teoremei este de asemenea de n ori derivabil pe[a, b]. S observ m, c g(x1) = · · · = g(xn) = g(x) = 0, deci g(z) va avea celpuµin n+ 1 zerouri diferite pe [a, b].
Între zerourile funcµiei derivabile conform teoremei lui Rolle, întotdeaunaexist un punct în care derivata este nul . Aplicând aceasta pentru g(z)primim, c g′(z) are cel puµin n, apoi aplicând pentru g′(z) obµinem c g′′(z)are cel puµin n − 1, ³i a³a mai departe g(n)(z) are cel puµin un zerou ξ(bineînµeles dependent de x) pe [a, b].
Deoarece L(z) este cel mare grad n− 1, astfel L(n)(z) = 0. De asemenease observ u³or, c ω(z) este un polinom exact de grad n, al c rui coe�cientprincipal este 1, astfel este evident, c ω(n)(z) = n!. Rezumând toate acestearezult c
g(n)(z) = f (n)(z)− n!
ω(x)(f(x)− L(x)), z ∈ [a, b],
de unde prin substituµia z = ξ, obµinem
0 = g(n)(ξ) = f (n)(ξ)− n!
ω(x)(f(x)− L(x)).
Rearanjând egalitatea primit ajungem la a�rmaµia care trebuia demon-strat .
Exerciµiu 5. S d m o estimare cu ajutorul teoremei 6. pentru eroarea deaproximare prin interpolare luat în punctul cu abscisa 2 a funcµiei
√x, dac
am ales ca noduri punctele x1 = 1, x2 = 3625, x3 = 49
25, x4 = 64
25, x5 = 81
25, x6 =
4 !
15
Rezolvare. Deoarece (√x)(6) = − 945
64x112, de aceea în cazul în care x ≥ 1,
|(√x)(6)| ≤ 945
64, respectiv un calcul simplu arat , c ω(2) = − 12152
390625. Astfel,
în baza teoremei 6.
|√
2− L(2)| ≤94564
6!
12152
390625=
31899
50000000< 7 · 10−4.
Observaµie: Alegerea nodurilor poate � justi�cat prin faptul c , deoareceacestea sunt p trate ale numerelor raµionale, L(2) d aproximarea raµional a num rului iraµional
√2.
Notaµie: Fie Ln(x) o serie de funcµii de interpolare corespunz toare la seriilede noduri −∞ < a ≤ x
(n)1 , . . . , x
(n)n ≤ b < ∞. În acest caz, în loc de ω(x)
folosim expresia
ωn(x) =n∏k=1
(x− x(n)k ).
Observaµie: Bineînµeles, pentru noi sunt valoroase acele polinoame de in-terpolare, în cazul c rora este îndeplinit lim
n→∞Ln(x) = f(x) pentru noduri
x ∈ [a, b], unde dorim s estim m valorile f(x).Cel mai bine ar � bineînµeles, dac am reu³i s g sim asemenea condiµii,
pentru care convergenµa ar � îndeplinit pentru �ecare punct x ∈ [a, b].Despre asta (³i despre mai multe) este vorba în urm toarea teorem , careare mari a³tept ri de la f(x): presupunem despre ea, c este derivabil deori de câte ori pe întreg intervalul [a, b].
Teorem 7. Dac ∃M > 0, pentru care |f (n)(x)| ≤Mn este îndeplinit pentruorice ∀x ∈ [a, b] pentru orice ∀n ∈ N, atunci
limn→∞
maxx∈[a,b]
|f(x)− Ln(x)| = 0.
Demonstraµie. Aplicând teorema 6. obµinem
|f(x)− Ln(x)| = |f(n)(ξ)|n!
|ωn(x)| < Mn
n!(b− a)n =
cn
n!→ 0.
Maximul evident exist , deoarece funcµia |f(x) − Ln(x)| este continu peintervalul închis [a, b], astfel convergenµa nu va � doar pe noduri, ci ³i uni-form .
16
Observaµie: Deci teorema 7. o putem formula ³i în a³a fel încât, dac ∃M > 0, pentru care |f (n)(x)| ≤ Mn este îndeplinit pentru orice ∀x ∈ [a, b],atunci polinoamele de interpolare Ln(x) converg uniform la funcµia f(x) pe[a, b].
Observaµie: S observ m c despre noduri am presupus doar atât, c num rullor tinde c tre in�nit. Nu este necesar, ca ele s �e poziµionate uniform, leputem limita chiar ³i pe o mic porµiune a intervalului [a, b]. În subcapitolul3.3.2. vom vedea c , cu un sistem de noduri poziµionat special putem obµinepolinoame de interpolare care converg mai rapid.
Exerciµiu 6. S demonstr m, c polinoamele de interpolare converg uniformla funcµia f(x) = e2x, dac num rul nodurilor din intervalul [0, 1
2] este n →
∞! Care este situaµia, dac f(x) = 1x+1
? Ne ajut în deciderea acestuiateorema 7.?
Rezolvare. În cazul în care f(x) = e2x, se poate observa u³or c , f (n)(x) =2ne2x, astfel dac x ≤ 1
2, atunci ca urmare a monotoniei funcµiei exponenµiale
|f (n)(x)| ≤ 2ne < 6n,
din care rezult în baza teoremei 7. convergenµa uniform .Dac f(x) = 1
x+1, un calcul simplu arat c , f (n)(x) = (−1)nn!
(x+1)n+1 , de unde
datorit monotoniei lui f (n)(x) pentru orice ∀x ≥ 0 rezult c
n!(32
)n+1 ≤ |f(n)(x)|.
Pentru îndeplinirea condiµiilor teoremei 7. ar trebui s existe M > 0, pentrucare |f (n)(x)| ≤ Mn este îndeplinit pentru orice ∀x ∈ [0, 1
2]. Dac ar � un
astfel de M , atunci pentru acesta n!
( 32)
n+1 ≤ Mn, ³i astfel ³i n!
( 3M2 )
n ≤ 32ar �
adev rat, dar acest lucru nu este posibil pentru �ecare n, deoarece n!cn→∞.
Mai precis, aplicând teorema 7. nu putem decide în privinµa îndepliniriiconvergenµei uniforme.
S observ m c de fapt ³i aici exist convergenµa uniform . Deoarecedatorit lui f (n)(x) = (−1)nn!
(x+1)n+1 este îndeplinit ³i
|f (n)(x)| ≤ n!,
dac x ≥ 0. Iar de aici, datorit teoremei 6.
|f(x)− Ln(x)| = |f(n)(ξ)|n!
|ωn(x)| ≤ |ωn(x)| <(
1
2
)n→ 0.
17
Notaµie: Fieh = max
k∈{1,...,n−1}(xk+1 − xk),
respectiv în cazul unei serii de noduri
hn = maxk∈{1,...,n−1}
(x(n)k+1 − x
(n)k ).
Lem 1. Dac x ∈ [a, b], atunci
|ω(x)| ≤ hn(n− 1)!
4.
Demonstraµie. Dac x = xk este îndeplinit pentru oarecare k ∈ {1, . . . , n},atunci în acest caz inegalitatea de demonstrat este evident adev rat , deoareceω(xk) = 0.
Se observ u³or c , dac x ∈ (xk, xk+1), k ∈ {1, . . . , n−1}, atunci datorit inegalit µii aritmetice-geometrice
√(x− xk)(xk+1 − x) ≤ xk+1−xk
2, de unde
|x− xk||x− xk+1| = (x− xk)(xk+1 − x) ≤(xk+1 − xk
2
)2
≤ h2
4.
S folosim,|ω(x)| = |x− x1| . . . |x− xn|.
Astfel, dac x ∈ (x1, x2), atunci
|ω(x)| ≤ h2
4· 2h · 3h · . . . · (n− 1)h =
hn(n− 1)!
4,
dac x ∈ (x2, x3), atunci
|ω(x)| ≤ 2h · h2
4· 2h · 3h · . . . · (n− 2)h =
hn2!(n− 2)!
4,
dac x ∈ (x3, x4), atunci
|ω(x)| ≤ 3h · 2h · h2
4· 2h · 3h · . . . · (n− 3)h =
hn3!(n− 3)!
4,
³i a³a mai departe, dac x ∈ (xn−2, xn−1), atunci
|ω(x)| ≤ (n− 2)h · . . . · 2h · h2
4· 2h =
hn2!(n− 2)!
4,
18
respectiv, dac x ∈ (xn−1, xn), atunci
|ω(x)| ≤ (n− 1)h · . . . · 3h · 2h · h2
4=hn(n− 1)!
4.
Deoarece, în cazul în care 1 ≤ k ≤ n, k!(n−k)! ≤ (n−1)!, putem observa c funcµia |ω(x)| am estimat-o mai sus cu cea mai mare expresie, pentru primul³i ultimul interval. Aceasta ne d exact a�rmaµia care trebuie demonstrat .
Teorem 8. Pentru �ecare x ∈ [a, b], pentru care este îndeplinit |f (n)(x)| ≤Mn, exist
|f(x)− L(x)| ≤ Mnhn
4n.
Demonstraµie. În baza teoremei 6. ³i lemei 1. este evident, c
|f(x)− L(x)| = |f(n)(ξ)|n!
|ω(x)| ≤ Mn
n!
hn(n− 1)!
4=Mnh
n
4n.
Observaµie: A�rmaµia teoremei 8. puteam evident prezenta ³i ca
|f(x)− Ln(x)| ≤ Mnhnn
4n.
Exerciµiu 7. Vrem s determin m valorile funcµiei sinx pe intervalul [0, 1],cu exactitate de cel puµin 6 zecimale. În acest scop potrivim un polinom deinterpolare la capetele intervalului, respectiv la acele puncte, care se formeaz cu ocazia diviz rii intervalului în p rµi egale. Cel puµin câte noduri trebuies lu m în acest mod?
Rezolvare. Deoarece (sinx)(n) rezult din funcµiile ± sinx ³i ± cosx, de aceeapentru un x arbitrar |(sinx)(n)| ≤ 1. Pe de alte parte, atunci se formeaz npuncte de diviziune în modul dorit, dac diviz m intervalul [0, 1] în n−1 p rµiegale, de aceea distanµa dintre punctele de diviziune vecine va � frac1n− 1,adic hn = 1
n−1 .Astfel, aplicând teorema 8. obµinem
| sinx− Ln(x)| ≤1 ·(
1n−1
)n4n
=1
4n(n− 1)n.
Seria format în partea dreapt a inegalit µii este strict monoton descresc -toare, valoarea sa este mai mare pentru n = 6, decât 2 · 10−6, mai mic pentru n = 7, decât 2 · 10−7, astfel în baza teoremei 8. trebuie s lu m celpuµin 7 noduri în modul de�nit în exerciµiu pentru îndeplinirea exactit µiidorite.
19
3.3.2 Noduri Cebî³ev
De�niµie 6. Funcµia
Tn(x) = cos(n arccosx), x ∈ [−1, 1], n ∈ N
o numim polinom Cebî³ev de grad n.
Observaµie: Faptul c Tn(x) este polinom, ³i înc de grad n, nu este delocevident. Îns este adev rat, a³a cum a�rm ³i teorema 9.
Teorem 9. Funcµia Tn(x) este polinom de grad n pe [−1, 1], al c rui coe�-cient principal în cazul n ∈ P este 2n−1.
Demonstraµie. S introducem notaµia θ = arccosx. Atunci
Tn±1(x) = cos((n± 1)θ) = cos(nθ ± θ) = cos(θ) cos(nθ)∓ sin(θ) sin(nθ)
= xTn(x)∓ sin(θ) sin(nθ),
de undeTn−1(x) + Tn+1(x) = 2xTn(x),
adic Tn+1(x) = 2xTn(x)− Tn−1(x), pentru ∀x ∈ [−1, 1].
S ad ug m la aceasta, c T0(x) = cos 0 = 1, respectiv c T1(x) =cos(arccosx) = x, ³i am obµinut o formul recursiv pentru Tn(x). Din for-mula recursiv se poate deduce c Tn(x) este polinom pentru �ecare n, graduls u la �ecare pas cre³te cu unu, ³i c în cazul lui n ≥ 2 coe�cientul principalal �ec rui membru este dublul precedentului. Cu aceasta am demonstrata�rmaµiile teoremei.
De�niµie 7. Funcµia
T̃n(x) = 21−nTn(x), n ∈ P, T̃0(x) = 1, x ∈ [−1, 1]
o numim polinom Cebî³ev de grad n normat pe 1.
Observaµie: Denumirea este justi�cat de faptul ce rezult din teorema 9.,conform c reia funcµia T̃n(x) este polinom de grad n cu coe�cientul principal1.
Observaµie: Speci�cul, ³i în acela³i timp utilitatea polinoamelor Cebî³ev esteprezentat de c tre urm toarea teorem .
20
Teorem 10. Dintre polinoamele de grad n cu coe�cient principal 1, polino-mul Cebî³ev de grad n normat pe 1 va � cel a c rui valoare absolut va luacea mai mic valoare maxim pe intervalul [−1, 1].
Demonstraµie. Datorit propriet µilor funcµiei cosx, maximul lui Tn(x) va �1, minimul −1, respectiv va lua aceste valori alternativ în total de n + 1ori, �indc soluµiile ecuaµiilor cos(n arccosx) = ±1 vor � xk = cos kπ
n, unde
k ∈ {0, 1, . . . , n}. Evident ³i punctele de extrem a lui T̃n(x) vor � tot aici.S presupunem în mod indirect, c exist un polinom de grad n cu coe-
�cient principal 1 notat cu p(x), pentru care
maxx∈[−1,1]
|p(x)| < maxx∈[−1,1]
|T̃n(x)|.
În acest caz polinomul r(x) = p(x)− T̃n(x) este de cel mult gradul n−1, îns între punctele de extrem ar tebui s schimbe semnul, între cele n+ 1 punctede cel puµin n ori. Iar acesta este o contradicµie, deoarece un polinom de celmai mare grad n−1 doar atunci poate avea mai mult de n−1 r d cini, dac este nul, dar un polinom cu coe�cientul principal 1 nu poate � astfel.
Observaµie: Tot din propriet µile funcµiei cosx rezult c ,
−21−n ≤ T̃n(x) ≤ 21−n.
Observaµie: R d cinile polinomului Cebî³ev de grad n (care sunt ³i r d cinilepolinomului Cebî³ev de grad n normat la 1) sunt soluµiile ecuaµieicos(n arccosx) = 0. Atunci n arccosxk = π
2+ kπ, de unde (luând în consid-
erare, c 0 ≤ arccosx ≤ π) obµinem soluµia diferit n de mai jos:
xk = cos(2k − 1)π
2n, k ∈ {1, . . . , n}.
De�niµie 8. R d cinile polinomului Cebî³ev le numim nodurile Cebî³ev aintervalului [−1, 1].
Observaµie: n numere de noduri Cebî³ev le obµinem chiar din polinomulCebî³ev de grad n.
Teorem 11. S presupunem c , |f (n)(x)| ≤Mn este îndeplinit pentru orice∀x ∈ [−1, 1]. Dac nodurile interpol rii sunt de tip Cebî³ev, atunci pentruorice ∀x ∈ [−1, 1]
|f(x)− L(x)| ≤ Mn
2n−1n!.
21
Demonstraµie. Fie nodurile interpol rii de tip Cebî³ev. În acest caz ω(x) =T̃n(x), deoarece r d cinile lor sunt identice ³i ambele sunt polinoame de gradexact n, cu coe�cientul principal 1. Deoarece |T̃n(x)| ≤ 21−n, aplicând teo-rema 6. este îndeplinit
|f(x)− L(x)| = |f(n)(ξ)|n!
|ω(x)| ≤ Mn
2n−1n!
pentru orice ∀x ∈ [−1, 1].
Observaµie: Importanµa nodurilor Cebî³ev este dat de faptul c , (a³a cumse observ din teorema 10.) max
x∈[a,b]|ω(x)| cu ele va � cel mai mic, de aceea
cu ele se poate obµine cea mai bun estimare a aproxim rii uniforme a lui|f(x)− L(x)|. Deci, în cazul în care avem posibilitatea, merit s alegem canodurile s �e de tip Cebî³ev, evident pentru n noduri r d cinile polinomuluiCebî³ev de grad n.
Observaµie: În cazul în care în locul intervalului [−1, 1] interpol m pe uninterval real arbitrar [a, b], aplic m asupra nodurilor Cebî³ev aceia³i transfor-mare liniar , cu ajutorul c reia din [−1, 1] obµinem pe [a, b]. Nodurile astfelobµinute vor îndeplini pe [a, b] rolul nodurilor Cebî³ev.
În primul pas m rim intervalul [−1, 1] de lungime 2 la lungimea b− a. Înacest caz se formeaz intervalul [− b−a
2, b−a
2], care are deja lungimea corespun-
z toare, dar mai trebuie prelungit în a³a fel încât cap tul inferior s �e în a,adic la ambele capete a intervalului ad ug m a−
(− b−a
2
). Aplicând aceea³i
transformare pentru nodurile Cebî³ev, obµinem nodurile Cebî³ev aparµin -toare intervalului [a, b] :
xkb− a
2+ a−
(−b− a
2
)= xk
b− a2
+a+ b
2,
unde k ∈ {1, . . . , n}, respectiv am notat cu xk nodurile Cebî³ev a intervalului[−1, 1].
În baza acestora este justi�cat de�niµia 9.
De�niµie 9. Punctele
a+ b
2+b− a
2cos
(2k − 1)π
2n, k ∈ {1, . . . , n}
le numim nodurile Cebî³ev a intervalului [a, b].
22
Teorem 12. S presupunem c , |f (n)(x)| ≤Mn este îndeplinit pentru orice∀x ∈ [a, b]. Dac nodurile interpol rii sunt de tip Cebî³ev pe [a, b], atuncipentru orice ∀x ∈ [a, b]
|f(x)− L(x)| ≤ Mn(b− a)n
22n−1n!.
Demonstraµie. Notaµi cu x1, . . . , xn nodurile Cebî³ev a intervalului [−1, 1],respectiv cu ω[−1,1](x) a intervalului [−1, 1], iar cu ω[a,b](x) funcµia ω(x) gen-erat de nodurile Cebî³ev a intervalului [a, b]. Atunci
ω[a,b](x) =n∏k=1
(x− a+ b
2− b− a
2xk
)=
n∏k=1
((2x− a− bb− a
− xk)b− a
2
)=
(b− a
2
)nω[−1,1]
(2x− a− bb− a
),
de unde, datorit lui |ω[−1,1](x)| = |T̃n(x)| ≤ 21−n rezult
maxx∈[a,b]
|ω[a,b](x)| =(b− a
2
)nmaxx∈[−1,1]
|ω[−1,1](x)| ≤(b− a
2
)n21−n.
În �ne, datorit teoremei 6. este îndeplinit
|f(x)− L(x)| = |f(n)(ξ)|n!
|ω[a,b](x)| ≤ Mn(b− a)n
22n−1n!
pentru orice ∀x ∈ [a, b].
Exerciµiu 8. S rezolv m exerciµiul 7. cu noduri Cebî³ev! Observ m vreomodi�care a rezultatului?
Rezolvare. ³i în acest caz putem utiliza, c |(sinx)(n)| ≤ 1. Datorit teoremei12.
| sinx− Ln(x)| ≤ |Mn|(b− a)n
22n−1n!≤ 1
22n−1n!.
Seria format în partea dreapt a inegalit µii este strict monoton descresc -toare, valoarea ei este mai mare pentru n = 5, decât 10−5, mai mic pentrun = 6, decât 7 · 10−7, astfel, în baza teoremei 12. trebuie s lu m cel puµin6 noduri Cebî³ev (adic r d cinile polinomului Cebî³ev de grad 6) pentruîndeplinirea exactit µii dorite.
Mai precis, folosind noduri Cebî³ev va � îndeajuns cel puµin un nod pentruîndeplinirea condiµiilor exerciµiului, decât în cazul în care nodurile le-amobµinut divizând intervalul în p rµi egale.
23
Exerciµiu 9. S demonstr m c polinoamele de interpolare converg uniformla funcµia f(x) = 1
x+ cos(3x), în m sura în care num rul nodurilor Cebî³ev
pe intervalul [1, 3] este n→∞! Ajut oare la demonstraµie teorema 7.?
Rezolvare. Deoarece f (n)(x) este una dintre funcµiile − n!xn+1 ± 3n sin(3x) ³i
n!xn+1 ± 3n cos(3x), de aceea |f (n)(x)| ≤ n! + 3n = Mn, dac x ≥ 1. Astfel, înbaza teoremei 12.
|f(x)− Ln(x)| ≤ (n! + 3n)2n
22n−1n!=
1
2n−1+
2 ·(32
)nn!
→ 0,
ceea ce înseamn convergenµa uniform a seriei de polinoame. Pentru ilus-trare s privim �gura 5. !
Figura 5: Nodurile Cebî³ev a intervalului [1, 3], aparµin toare funcµiei f(x) =1x
+ cos(3x) ³i polinoamele de interpolare corespunz toare lor.
Deoarece f (4n)(1) = (4n)!+34n cos(1) ≥ (4n)!, de aceea condiµia teoremei7., adic f (n)(x) ≤ Mn, poate � îndeplinit pentru orice ∀x ∈ [1, 3], astfelteorema 7. nu poate � utilizat la acest exerciµiu.
Bibliogra�e
[1] Móricz Ferenc: Analiza numeric I-II. Nemzeti Tankönyvkiadó, Bu-dapesta, 1993.
[2] Szidarovszky Ferenc: Introducere în metodele numerice. Editura Eco-nomic ³i Juridic , Budapesta, 1974.
24
Cuprins
1 Ce este interpolarea? 1
2 Interpolarea 1
2.1 Noµiuni de baz . . . . . . . . . . . . . . . . . . . . . . . . . . 12.2 Rezolvabilitate, rezolvare . . . . . . . . . . . . . . . . . . . . . 3
3 Interpolarea polinomial 6
3.1 Unicitate ³i existenµ . . . . . . . . . . . . . . . . . . . . . . . 63.2 Determinarea polinomului de interpolare . . . . . . . . . . . . 8
3.2.1 Metoda clasic . . . . . . . . . . . . . . . . . . . . . . 83.2.2 Interpolare Lagrange . . . . . . . . . . . . . . . . . . . 93.2.3 Interpolarea iterativ a lui Neville . . . . . . . . . . . . 11
3.3 Estimarea erorilor, convergenµ . . . . . . . . . . . . . . . . . 143.3.1 Noduri de poziµie general . . . . . . . . . . . . . . . . 143.3.2 Noduri Cebî³ev . . . . . . . . . . . . . . . . . . . . . . 20
25