Curbele spline

În cele ce urmeaza vor fi prezentate problemele practice întâlnite la încercarile de implementare concreta a interpolarii si trasarii curbelor plane. Se va acorda atentie deosebita chestiunilor legate de calcule aritmetice efective necesare pentru implementarea algoritmilor-evitarea depasirilor aritmetice, limitarea erorilor de rotunjire cumulative pentru valorile calculate iterativ, etc. De asemenea se va urmari optimizarea algorimilor prezentati în vederea eficientei de executie; în acest scop se cauta a se micsora numarul de înmultiri si împartiri si micsorarea numarului operatiilor în virgula mobila, în favoare celor cu numere întregi.În prima parte se va face o prezentare teoretica a problemei interpolarii cu functii spline cubice pe portiuni, iar în sectiunea a doua se demonstreaza o proprietate extremala a acestor functii; concluzia este ca interpolarea cu functii spline da rezultatele cele mai naturale si ca acest tip de interpolare este cel mai indicat pentru modelarea fenomenelor reale.

Pentru implementarea practica a unui mecanism de interpolare trebuie rezolvate doua probleme majore si principal distincte:

- Calcularea parametrilor de interpolare, care definesc expresia analitica a curbei care trebuie trasata;

- Trasarea efectiva a curbei interpolate.

În cazul interpolarii cu functii spline cubice, curbele care trebuie trasate sunt reprezentate parametric prin polinoame de gradul 3(sau mai mic). În acest caz particular, algoritmul de trasare prin metoda înjumatatirii poate fi optimizat, astfel încât sa nu utilizeze înmultiri si împartiri, ci numa operatii simple de adunare si scadere si deplasare binara. Acest rezultat este foarte important din punct de vedere al implementarii; aceasta nu se datoreaza faptului ca eficienta procedurii de trasare este determinata pentru performantele globale ale programului de interpolare cu vizualizare.

Interpolare cu functii spline cubice

Problema teroretica clasica a interpolarii functiilor dupa date exacte, definite pe o multime discreta de puncte este rezolvata cu ajutorul polinoamelor interpolative ale lui Lagrange. Aceasta metoda asociaza unui set de n puncte din plan abscise diferite, o curba polinomiala de gradul n-1 care trece prin toate cele n puncte. Metoda are avantajul continuitatii tuturor derivatelor curbei interpolatoare. Totusi, curba interpolatoare Lagrange nu este naturala, în sensul ca oscileaza prea mult între punctele fixe; acest aspect este prohibitiv pentru dipozitivele grafice care utilizeaza operatii de interpolare pentru modelarea unor fenomene naturale.

O functie spline este de obicei polinomiala pe portiuni, adica o functie pentru care exista o diviziune a intervalului I de interpolare în subintervale, astfel încât în interiorul fiecarui subinterval al diviziunii functia reprezinta un polinom de un anumit grad m. În plus, functia este de regula continua pe I împreuna cu derivatele sale pâna la ordinul m-1 inclusiv, si are derivata de ordinul m cu patrat integrabil.

Cele mai utilizate functii spline s-au dovedit a fi polinoamele de gradul trei. În acest caz, curba interpolatoare este continua împreuna cu primele doua derivate, ceea ce este suficient pentru modelarea fenomenelor naturale. În plus, curba interpolatoare cu functii spline cubice are o proprietate extremala naturala care minimizeza oscilatia si asigura pentru curba aspectul cel mai natural cu putinta. În continuare, va fi prezentata problema teoretica a interpolarii cubice pe portiuni pentru functii de o variabila.

Fie o retea de functii în ale carei noduri sunt date valorile ale functiei f: numita functie interpolatoare, care sa îndeplineasca urmatoarele conditii:

- g(t) este de clasa adica este continua pe împreuna cu derivatele sale de ordin întâi si doi;

- pe fiecare interval functia g(t) este un polinom de gradul 3;

- În nodurile retelei sunt îndeplinite egalitatile: g( ) ; (1.1)

- satisface conditiile la limita : . (1.2)

Se va arata ca în conditiile de mai sus problema gasirii functiei interpolatoare cubice pe portiuni g(t) are solutie unica.

Deoarece derivata a doua a functiei g(t) este liniara pe fiecare interval , al retelei, se poate scrie pentru (1.3), unde am notat , pentru . Din conditia de continuitate a derivatei a doua în punctele , obtinem imediat : (1.4) egalitati pe care le completam definind

Integrând de doua ori ambii membri ai egalitatii (1.3) obtinem pentru :