Functii spline

Functiile spline sunt functii care au anumite proprietati de continuitate derivabilitate astfel incat, asa cum se si numesc , curba care trece prin punctele de definitie este o curba neteda (are o variatie minima a pantei).

Functiile spline de ordin m sunt polinoame de grad m pe orice interval (si sunt notate de obicei ). Aceste functii spline sunt de clasa si derivata de ordin m este discontinua in nodurile . Daca sunt polinoame de gradul trei atunci functia definita de:

(1)

se numeste functie spline cubica. Coeficientii se pot determina din conditiile de continuitate si de interpolare in punctele diviziunii:

(2)

Impunand si conditiile de continuitate pentru derivatele functiilor spline cubice se determina:

(3)

unde si derivata de ordin doi calculata in punctul . Derivatele de ordinul 2 se calculeaza prin impunerea conditiei de continuitate a primei derivate pentru in capetele intervalului:

(4)

si se obtine un sistem de ecuatii liniare in :

(5)

unde coeficientii sunt dati de relatiile:

(6)

Se observa ca pentru calculul coeficientilor si trebuie sa se cunoasca derivatele si in extremitatile intervalului de tabelare. De cele mai multe ori nu exista informatii cu privire la aceste derivate si se foloseste intrepolarea Lagrange de unde:

(7)

(8)

In algoritmul de interpolare cu functii spline trebuie sa se afle valorile derivatelor de ordin 2 din sistemul de ecuatii (5) pe baza coeficientilor din relatiile (6) si mai apoi coeficientii interpolantului spline conform (3).

INTERPOLAREA CU FUNCTII SPLINE

Cuvantul 'spline' inseamna o rigla elastica de care daca se agata greutati poate fi facuta sa treaca prin diferite puncte dorite, cuprinse intre capetele riglei.

Consideram data o functie tabelata, reprezentata in tabelul 1.

Tabelul 1

Consideram si , fiind intervalul de definitie a functiei , iar abscisele x₁,x₂,,x_n o diviziune D a intervalului de definitie. Valorile functiei sunt

, (1)

Definitia 1. Se numeste functie spline de ordinul n relativ la diviziunea D

a intervalului o functie S: R de clasa C^m-1 ale carei restrictii S_i(x) pe fiecare interval al diviziunii sunt polinoame de ordinul m, adica:

daca , i =1,2,,(n-1) (2)

Functia S(x) este neteda pe portiuni deoarece are primele (m-1) derivate continue pe , iar derivata de ordinul m este discontinua in , i =1,2,,n. Gradul de netezire al functiei este m. Restrictiile functiei sunt polinoamele:

S_i(x)=A_ix^m + B_ix^m-1 + C_ix^m-2 + E_ix^m-3 + +R_i (3)

daca, , i =1,2,,(n-1)

Aceste functii sunt derivabile pana la (n-1) si sunt continue impreuna cu derivatele. Derivata de ordinul (n-1) si a lui S_i(x) pe intervalul este o functie liniara si trece prin punctele si unde, i =1,2,,n.

Rezulta ecuatia liniara:

(4)

unde h_i=x_i+1-x­_i , i =1,2,,(n-1)

Integrand de m-1 ori relatia ( ) se obtine:

(5)

(6)

(7) (8)

Pentru intreg intervalul rezulta un sistem liniar punand conditia ca S_i(x_i)=y_i , i=1,2,..,n si continuitatea celor (m-1) ecuatii in toate punctele x_i . In extremele si se scrie polinomul lui Lagrange, il derivam pana la m-1 si aflam corespunzator valorile derivatelor in si . Rezulta necunoscutele:

D_i , D_i+1 , C_1i ,, C_m-1,i pentru fiecare interval. In acest caz sunt n+(m-1)+ (n-1) necunoscute si n+(m-1)+(n-1) ecuatii. Sistemul fiind liniar se rezolva cu una din metodele din lucrarea 3.

In lucrare se considera restrictiile S_i polinoame de gradul 3.

In acest caz:

S_i(x)=A_ix³ + B_ix² + C_ix + E_i (9)

(10)

Din si rezulta:

Din identificarea relatiilor (9) si (10) rezulta :

; (11)

(12)

Din continuitatea primei derivate in punctul , rezulta:

(13)

Considerand derivata de ordinul intai in punctul si egale cu:

(14)

respectiv

(15)

rezulta sistemul tridiagonal in D_i

(16)

unde y₁ si y_n sunt date de expresiile (14), respectiv (15) .

Din sistemul (16) rezulta valorile lui D_i , i =1,2,,n. Din (11) rezulta coeficientii restrictiilor pe fiecare interval, restrictii care aproximeaza functia data. Daca se da in care trebuie calculata functia, se stabileste intervalul in care se gaseste si se calculeaza valoarea restrictiei functiei pe acest interval in punctul .

VILIGA NICOLETA

Functii spline cubice de clasa C

Se considera sistemul de noduri distincte in intervalul :

Functia S(x) asociata divizarii care indeplineste conditiile:

Polinoamele au gradul 3, i = 0, , n-1, se numeste functie spline cubica.

Data fiind o functie se considera functia spline cubica S(x) de interpolare ce satisface

Pentru determinarea functiei spline cubice de interpolare obsevam ca polinoamele:

implica determinarea a 4n necunoscute pentru care se impun:

n+1 conditii din relatiile de interpolare .

3(n-1) conditii de continuitate pentru in nodurile in total 4(n-2) conditii.

Se poate avea in vedere pentru adaugarea adoua conditii suplimentare urmatoarele abordari:

• Fixarea pantelor in extremitatile intervalului . Se presupune ca functia f este derivabila si se cunosc valorile S impun conditiile: ;
• Periodicitatea primelor doua derivate:

• Anularea derivatei secunde an capetele intervalului:

Functiile spline care indeplinesc aceste conditii se numesc functii spline cubice normale.

• Derivata de ordinul al treilea ale functiei S este continua in punctele

Aceasta inseamna ca polinoamele coincid. Acest tip de spline se numeste ,, not-a-knot,, si este utilizat in MATLAB.

Ne vom ocupa in continuare de determinarea functiei spline de interpolare in cazul in care sunt cunoscute valorile derivatei functiei f(x) in a si b.

Recapituland viom avea urmatoarele conditii:

Vom nota

Tinand seama de faptul ca functia este o functie liniara pe fiecare din intervalele rezultand ca, notand cu vom avea:

iar din rezulta:

Impunand conditiile de interpolare si de continuitate vom obtine:

Din aceste relatii determinam in functie de

Din conditia:

tinand seama de rezulta

(1)

Din conditia de continuitate a primei derivate a functiei spline cubice

tinand seama de:

Rezulta, utilizand valorile pentru deduse mai sus:

sau

(2)

In final din conditia:

obtinem:

(3)

Sistemul liniar (1), (2), (3) cu necunoscutele are forma:

Obervand ca matricea H este diagonal dominanta atat pe linii cat si pe coloane rezulta ca putem utiliza metoda Gauss-Seidel pentru rezolvarea sistemului

Tinand seama ca matricea H este simetrica si pozitiv definita rezulta de asemenea si convergenta metodei relaxarii.

In cazul functiei spline naturale avem iar pentru determinarea valorilor intervin numai conditiile (2).

Sistemul liniar pentru aceste valori are forma:

In care matricea se obtine din matricea H din care se suprima prima si ultima linie respective prima si ultima coloana, iar se obtine din vectorul f eliminand primul si ultimul element. Matricea are aceleasi proprietati ca si matricea H.

IOJIBAN CRISTINA

Interpolare cu functii spline

Curbele pot fi reprezentate in plan:

ecuatii explicite:De exemplu y = si y = reprezinta un cerc cu centrul in origine,de raza r

ecuatii implicite:

ecuatii parametrice: x(t)= r cos t si y(t) = r sin t

Reprezentarea prin ecuatii explicite,de forma y = f (x) si nici ecuatiile implicite nu asigura reprezentarea curbelor avand mai multe valori intr-un punct (nu sunt functii).

f (p) = f (x,y) =0 nu trateaza corect tangentele verticale la curba.

Forma parametrica :

p(t) =

este mult mai flexibila

permite reprezentarea de curbe care nu sunt functii (au mai multe valori intr-un punct)

este independenta de coordonate

Specificarea unei curbe se face prin:

puncte de control -multime de puncte care influenteaza forma curbei

noduri - puncte de control care se afla pe curba

Un spline este o curba parametrica definita prin puncte de control.

Un spline este o functie S :[a, b]R,definita local pe mai multe intervale prin

S (t) =(t) ,

S (t) =(t) ,

S (t) =(t) ,

Functiile sunt de regula polinoame de grad 3

Nodurile se aleg de obicei echidistante, definind un spline uniform

Daca in vecinatatea nodurilor ,S atunci spline-ul are netezimea .

(adica spline-urile au aceleasi derivate de ordin 0 pana la )

Splineul de grad 0 este splineul treapta,cel de ordin 1 este spline liniar si coincide cu poligonul punctelor de control.

Un spline utilizat - spline-ul cubic natural are gradul 3 si continuitate .In plus,la capete : s" (a) = s" (b) = 0.

Splineurile de grad n utilizate in analiza numerica au continuitate S (t) [a,b]

Splineurile utilizate in Adobe si PostScript au continuitatea S (t)

Pentru asigurarea continuitatii ,functiile spline trebuie sa aiba cel putin gradul 3

Functiile spline pot fi :

functii spline de interpolare - care trec prin toate punctele de control

functii spline de aproximare - care nu trec prin toate punctele de control

Functii spline de interpolare in clasa .

Vom alege polinoame de interpoale de grad mic,valabile pe subintervale

f (

si vom considera functii de interpolare liniare,locale pe subintervalele

si vom considera functii de interpolare liniare, locale pe subintervale

[

in care cei 2n parametri se determina din conditiile de interpolare:

si a conditiilor de racordare (continuitate in punctele interioare ):

i =0 : n-2

Interpolarea liniara prezinta dezavantajul discontinuitatii derivatelor in punctele interioare.

i = 0 :n -1

Prin alegerea unor functii de interpolare de gradul 3 se poate realiza o interpolare Hermite, care presupune si fixarea valorii derivatelor pe suportul interpolarii :

f ' ( (

O functie spline cubica se exprima sub forma :

sau parametric

in care s-a notat si s-a efectuau schimbarea de variabila:

Baza Bernstein:

reduce volumul de calcule necesar determinarii coeficientilor.

Avem 2n+2 conditii de interpolare de tip Hermite:

si 2n-n conditii de racodare(continuitate si derivabilitate in punctele interioare):

Eroarea interpolarii pentru functiile spline in clasa este:

E(x)=

E(x)=

E(x)

Functii spline de interpolare in clasa

Consideram numai n+1 conditii de interpolare de tip Lagrange:

rezulta:

Dispunem de mai multe grade de libertate pentru conditiile de racordare:continuitatea valorilor si a derivatelor de ordinul 1 si 2 in punctele interioare

i = 0 : n - 2

i = 0 : n - 2

Pe care o prelungim cu i = 0 : n - 1,introducand notatia

s-au obtinut astfel 4n-2 relatii , mai putem impune 2 conditii suplimentare

care definesc functiile spline naturale

pentru functii spline tensionate.

+

Functii spline de aproximare Hermite

Spline-ul Hermite este un spline cubic, deci impune 4 grade de libertate:

;

.

Vom impune ca restrictii valorile la capete si valorile derivatelor la capete

Definim vectorul de control:

p(0)=d

p(1)=a+b+c+d

In graficul functiei componentele vectorului de control apar ponderate cu functiile de imbinare(blending functions):

Spline cardinale.

Sunt spline Hermite, care nu folosesc derivate, care sunt inlocuite prin diferentele:

p(0)=

p(1)=

p

p'(1)=

p(t)=T(t)

p(t)=

p(t)=

Spline Catmull-Rom.

Sunt spline cardinale cu a=0.5 =0.5

Spline-ul Catmull-Rom are proprietatile

trece prin toate punctele de control (spline de interpolare)

este continuu

Spline Kochanek-Bartels

Sunt spline Hermite,folosite de 3d-Studio Max cu control mai bun asupra animatiei.

Calculul tangentelor se face cu relatiile: