INTERPOLARE

Se dau punctele P0 , P1 , . . ., Pn in plan sau in spatiu, numite noduri si avand vectorii de

pozitie ~r0 , ~r1 , . . ., ~rn .
Problemă. Să se găsească o curbă (dintr-o anumită familie) care să treacă prin punctele
date in ordinea precizată.
Observaţie. Evident că se preferă curbe cât mai simple şi având proprietăţi cât mai bune.
Un bun candidat este clasa funcţiilor polinomiale. De ce?

Polinoame Lagrange.
Fie ~ri = (xi , yi ). Un polinom (funcţie polinomială) de grad arbitrar k se scrie
L(x) = a0 + a1 x + . . . + ak xk .

Condiţia de interpolare se scrie

(1) L(xi ) = yi , i = 0, 1, . . . , n.

Prin urmare alegem k = n şi astfel obţinem un sistem de (n + 1) ecuaţii liniare cu n + 1

necunoscute (coeficienţii polinomului).
Se obţine soluţie unică. (Avem un sistem Cramer, determinantul este de tip Vandermonde.)
Acest polinom se numeşte polinomul Lagrange corespunzător problemei propuse.

Definim polinoamele Lagrange de bază prin condiţiile

(2) Li (xj ) = δij , i, j = 0, . . . , n.

Prin urmare putem scrie

n
X
L(x) = yi Li (x).
i=0

Se arată că
n
(x − x0 ) · · · (x\ − xi ) · · · (x − xn ) Y x − xj
(3) Li (x) = = .
(xi − x0 ) · · · (xi − xi−1 )(xi − xi+1 ) · · · (xi − xn ) j=0,j6=i xi − xj

Inconveniente:
• gradul devine foarte mare pentru un număr mare de puncte;
• precizia poate fi mica, aparând oscilaţii mari faţă de funcţia iniţială care trebuie
aproximată);
1
Geometrie Computaţională 2016-2017 C1, C2
• modificarea unei coordonate intr-un nod (datorată unei măsurători greşite, de exem-
plu) are ca efect modificarea globală a polinomului; (nu pot face o ”reparaţie lo-
cală”).

Exerciţiu. Să se studieze interpolarea Lagrange pentru n ≥ 3 puncte coliniare.

Idee de demonstraţie: Se demonstrează următoarele identităţi:
n
X n
X
Li (x) = 1, xi Li (x) = x,
i=0 i=0

pentru orice x.

Problema gradului mare al polinomului Lagrange ar putea fi rezolvată reconsiderând pro-

blema interpolării pe porţiuni; secvenţa de noduri se divide in sub-secvenţe mai mici şi
se consideră polinoamele Lagrange pe aceste sub-secvenţe. Apare ı̂nsă o altă problemă şi
anume cea a racordării arcelor succesive in punctele de joncţiune.
De exemplu, se dau nodurile P0 , . . ., P6 .
Se consideră sub-secvenţele:
(I) P0 , P1 , P2 , P3 care conduce la polinomul L(x), de grad 3;
(II) P3 , P4 , P5 , P6 care conduce la polinomul L̄(x), de grad 3.
Evident avem racordare (i.e. continuitate) deoarece L(x3 ) = y3 = L̄(x3 ).
Totuşi, un calcul simplu ne arată că nu avem diferenţiabilitate nici măcar de clasă C 1 in
x3 .

Interpolare Hermite.
Pentru a avea control şi asupra valorilor derivatelor (d.p.d.v. cinematic controlăm vitezele)
pornim cu cele (n+1) puncte (noduri) insă precizăm şi valorile vitezelor (adică a derivatelor)
ı̂n punctele corespunzătoare. Cu alte cuvinte considerăm datele iniţiale
P0 (x0 , y0 ; v0 ), P1 (x1 , y1 ; v1 ), . . . , P0 (xn , yn ; vn ).

Scopul este de a găsi funcţii polinomiale H cu proprietăţile

H(xi ) = yi , H 0 (xi ) = vi , ∀i = 0, . . . , n.

Întrucât avem 2(n + 1) condiţii, polinomul H are gradul 2n + 1.

Observaţie: Se rezolvă astfel problema racordării (avem diferenţiabilitate şi ı̂n punctele de
joncţiune) ı̂nsă gradul s-a mărit considerabil.

La fel ca ı̂n cazul interpolării Lagrange, determinăm polinoamele Hermite de bază, notate
cu Hi şi H̄i , i = 0, . . . , n caracterizate de condiţiile
(4) Hi (xj ) = δij , Hi0 (xj ) = 0, H̄i (xj ) = 0, H̄i0 (xj ) = δij , i, j = 0, . . . , n.
2
Geometrie Computaţională 2016-2017 C1, C2

Polinomul de interpolare Hermite este determinat de relaţia

n
X n
X
(5) H(x) = yi Hi (x) + vi H̄i (x).
i=0 i=0

Să analizăm ecuaţiile (3): Fixăm i.

Pentru j 6= i avem Hi (xj ) = 0 şi Hi0 (xj ) = 0.
Prin urmare (x − xj )2 divide Hi (x) pentru orice j 6= i.
Rezultă că
Y
(x − xj )2 divide Hi (x).
j6=i
Y
Dar polinomul (x − xj ) este, până la o constantă multiplicativă, polinomul Lagrange de
j6=i
bază Li (x).
Prin urmare
Hi (x) = (polinom de grad 1) L2i (x), ∀i = 0, . . . , n.
Analog se arată că

H̄i (x) = (polinom de grad 1) L2i (x), ∀i = 0, . . . , n.

Obţinem imediat că

Hi (x) = [1 − 2L0i (xi )(x − xi )] L2i (x)

(
(6)
H̄i (x) = (x − xi )L2i (x), i = 0, . . . , n.

Pentru n = 1 avem:
(3x0 −x1 −2x)(x−x1 )2
H0 (x) = (x0 −x1 )3
(3x1 −x0 −2x)(x−x0 )2
H1 (x) = (x1 −x0 )3
(x−x0 )(x−x1 )2
H̄0 (x) = (x0 −x1 )2
(x−x1 )(x−x0 )2
H̄1 (x) = (x1 −x0 )2
√
Problemă: (a) Fie funcţia f : [1, 9] → (0, ∞), f (x) = x. Să se reprezinte grafic funcţia
f . (b) Se consideră apoi valorile: x0 = 1, x1 = 4, x2 = 9, y0 = 1, y1 = 2, y2 = 3, v0 = 1/2,
v1 = 1/4 şi v2 = 1/6. Să se determine polinomul de interpolare Hermite (n = 2) pentru
valorile considerate. Să se reprezinte ı̂n acelaşi sistem de coordonate funcţia polinomială
corespunzătoare. (c) Pe intervalele [x0 , x1 ], respectiv [x1 , x2 ] să se determine polinoamele
Hermite (n = 1) şi să se reprezinte grafic funcţiile polinomiale corespunzătoare. Să se
compare cele trei grafice.
3
Geometrie Computaţională 2016-2017 C1, C2

Curbe parametrizate Ferguson

Să considerăm următoarea problemă: Fie P0 şi P1 două puncte ı̂n plan sau ı̂n spaţiu. Fie
~r0 şi ~r1 vectorii de poziţie respectiv ai celor două puncte, iar ~v0 şi ~v1 vectorii vitezelor
ı̂n punctele iniţial, respectiv final (vectorii tangenţi ı̂n capete). Să se determine o curbă
polinomială de gradul al treilea (cubică)
r : [0, 1] → E2 sau E3 ,
care verifică
dr dr
r(0) = ~r0 , r(1) = ~r1 , (0) = ~v0 , (1) = ~v1 .
du du
Curba r, dacă există, are expresia
r(u) = a + 0 + u a1 + u2 a2 + u3 a3 , u ∈ [0, 1],
unde a0 , a1 , a2 şi a3 sunt vectori constanţi.
Condiţiile solicitate pentru r se rescriu:
a0 = ~r0
a0 + a1 + a2 + a3 = ~r1
a1 = ~v0
a1 + 2a2 + 3a3 = ~v1 .
Deducem imediat că
r(u) = (1 − 3u2 + 2u3 )~r0 + (3u2 − 2u3 )~r1 + (u − 2u2 + u3 )~v0 + (u3 − u2 )~v1 .

Să observăm polinoamele Hermite de bază pentru n = 1, u0 = 0 şi u1 = 1.

Mai precis avem
r(u) = H0 (u)~r0 + H1 (u)~r1 + H̄0 (u)~v0 + H̄1 (u)~v1 .

Observaţie: Faptul că am considerat drept mulţime de definiţie a curbei r intervalul [0, 1]
nu reprezintă o restrângere a generalităţii. Reamintim că avem ı̂ntotdeauna o bijecţie afină
de la un interval oarecare [a, b] la intervalul [0, 1], dată de
x−a
ϕ : [a, b] → [0, 1], ϕ(x) = , ϕ−1 : [0, 1] → [a, b], ϕ−1 (u) = (1 − u)a + u b.
b−a

4
Geometrie Computaţională 2016-2017 C1, C2

Avem şi o scriere matricială pentru curba r, anume r(u) = U CR, unde
U = (1 u u2 u3 )
 
1 0 0 0
 0 0 1 0 
C= −3

3 −2 −1 
2 −2 1 1
 
~r0
 ~r1 
R=  ~v0  .

~v1