Spline

Nu confundați cu splină.

În matematică o spline este o funcție definită pe porțiuni prin polinoame. În problemele de interpolare, interpolarea spline este adesea preferată interpolării polinomiale deoarece produce rezultate bune, chiar și atunci când se utilizează polinoame de grad mic, evitând în același timp fenomenul Runge când se utilizează polinoame de grad mare.

În informatică, în proiectarea asistată de calculator și grafica digitală, termenul spline se referă de obicei la o curbă polinomială pe porțiuni (parametrică). Curbele spline sunt populare în aceste subdomenii datorită simplității obținerii lor, ușurinței și preciziei evaluării și capacității lor de a aproxima forme complexe prin aproximarea și proiectarea interactivă a curbelor.

Termenul „spline” provine de la riglele flexibile^⁠(d) (în engleză flat spline) folosite de constructorii de nave și desenatorii care realizau planurile cu forme curbe netede.

Istoric

După Gerald Farin, funcțiile B-spline^⁠(d) au fost explorate încă din secolul al XIX-lea de Nikolai Ivanovici Lobacevski la Universitatea Kazan din Rusia.^[1]

Înainte de apariția computerelor, calculele numerice se făceau manual. Deși se foloseau funcții definite pe porțiuni, cum ar fi funcția semn sau funcții constante pe porțiuni^⁠(d), polinoamele erau în general preferate deoarece erau mai ușor de lucrat cu ele. Prin apariția computerelor, funcțiile spline au câștigat importanță. Acestea au fost folosite în interpolare inițial ca înlocuitor pentru polinoame, apoi ca instrument pentru a construi forme netede și flexibile în grafica digitală.

Este acceptat în general că prima referință matematică la spline este lucrarea din 1946 a lui Isaac Jacob Schoenberg, care este probabil primul loc în care cuvântul „spline” este folosit în legătură cu aproximarea polinomială netedă, pe porțiuni. Totuși, ideile își au rădăcinile în industria aeronautică și navală. În prefața la Bartels et al., 1987,^[2] Robin Forrest descrie o tehnică utilizată în industria aeronautică britanică în timpul celui de Al Doilea Război Mondial pentru a face șabloane pentru avioane prin aranjarea unor șipci subțiri de lemn (numite „spline”) prin puncte așezate pe podeaua unei săli mari de trasaj, o tehnică împrumutată din proiectarea corpului navelor. Timp de ani de zile, practica proiectării navelor a folosit modele pentru a proiecta la scară mică. Designul reușit a fost apoi trasat pe hârtie milimetrică, iar punctele cheie ale graficului au fost retrasate pe hârtie caroiată mai mare la dimensiunea reală. Șipcile subțiri de lemn asigurau o interpolare a punctelor cheie cu curbe netede. Șipcile erau ținute fixe în punctele discrete cu greutăți, iar între aceste puncte puteau lua forme cu energie de deformare minimă. Forrest afirmă că un posibil impuls pentru un model matematic pentru acest proces a fost pierderea potențială a componentelor critice de proiectare pentru o întreagă aeronavă în cazul în care sala de trasaj ar fi fost lovită de o bombă inamică. Aceasta a dat naștere la aproximarea cu conice, care folosea secțiuni conice pentru a modela poziția curbei dintre punctele fixe. Aproximarea cu conice a fost înlocuită de ceea ce s-a numit „spline” la începutul anilor 1960, pe baza lucrărilor realizate de J. C. Ferguson la Boeing și (ceva mai târziu) de Malcolm Sabin la British Aircraft Corporation. Cuvântul „spline” a fost inițial un cuvânt dialectal din Anglia de est.

Utilizarea funcțiilor spline la modelarea caroseriilor automobilelor pare să aibă mai multe începuturi independente. Meritul este revendicat de Paul de Casteljau la Citroën, Pierre Bézier la Renault și Garrett Birkhoff, Garabedian și Carl R. de Boor la General Motors,^[3] toți pentru lucrări desfășurate la sfârșitul anilor 1950 și la începutul anilor 1960. Cel puțin una dintre lucrările lui de Casteljau a fost publicată, dar nu pe scară largă, în 1959. Munca lui De Boor la General Motors a dus la publicarea unui număr de lucrări la începutul anilor 1960, inclusiv unele dintre lucrările fundamentale despre B-spline.

Se lucra și la [[Pratt & Whitney |Pratt & Whitney Aircraft]î, unde au fost angajați doi dintre autorii lucrării^[4] – prima lucrare de tip carte despre spline – și la David Taylor Model Basin, de Feodor Theilheimer. Munca de la General Motors este detaliată în lucrările lui Birkhoff^[5] și Young^[6]. Davis^[7] rezumă o parte din acest material.

Descriere

Termenul „spline” este folosit pentru o clasă largă de funcții utilizate în aplicații care necesită interpolare și/sau netezire a datelor. Datele pot fi unidimensionale sau multidimensionale. Funcțiile spline pentru interpolare au în mod normal rolul de a minimiza unele aspecte, ca rugozitatea (de exemplu pătratul curburii totale), supuse constrângerilor de interpolare. Funcțiile spline de netezire pot fi considerate generalizări ale celor de interpolare, unde funcțiile sunt condiționate pentru a minimiza o combinație ponderată a erorii medii de aproximare la pătrat pentru datele observate și a măsurii de rugozitate. Pentru o serie de definiții semnificative ale măsurii rugozității, funcțiile spline sunt considerate a fi de natură finit dimensională, acesta fiind principalul motiv al utilității lor în calcule și reprezentare. În restul acestei secțiuni, termenul „spline” va fi folosit în sensul restrâns de spline polinomiale unidimensionale.

Definiție

Se începe cu limitarea discuției la polinoame de o singură variabilă. În acest caz, o spline este o funcție polinomială pe porțiuni. Această funcție, $S$ , are argumentele într-un interval $[a, b]$ și le aplică pe mulțimea numerelor reale, $ℝ :$

S : [a, b] \to ℝ

Pentru ca $S$ să fie definită pe porțiuni, fie ca intervalul $[a, b]$ să fie acoperit de $k$ subintervale consecutive disjuncte:

\begin{matrix} [t_{i}, t_{i + 1}], i = 0, \dots, k - 1 \\ [a, b] = [t_{0}, t_{1}) \cup [t_{1}, t_{2}) \cup \dots \cup [t_{k - 2}, t_{k - 1}) \cup [t_{k - 1}, t_{k}) \cup [t_{k}] \\ a = t_{0} \leq t_{1} \leq \dots \leq t_{k - 1} \leq t_{k} = b \end{matrix}

Pe fiecare din aceste $k$ "porțiuni" ale lui $[a, b]$ se poate defini un polinom, $P i$ :

P_{i} : [t_{i}, t_{i + 1}] \to ℝ

Pe al $i$ -lea subinterval al $[a, b]$ , $S$ este definită de $P i$ :

\begin{matrix} S (t) & = P_{0} (t), & t_{0} \leq t < t_{1} \\ S (t) & = P_{1} (t), & t_{1} \leq t < t_{2} \\ ⋮ \\ S (t) & = P_{k - 1} (t), & t_{k - 1} \leq t \leq t_{k} \end{matrix}

Cele $k + 1$ puncte $t i$ se numesc „noduri”. Vectorul $t = (t 0, \dots, t k)$ este „vectorul nodurilor” funcției spline. Dacă nodurile sunt distribuite echidistant în intervalul $[a, b],$ funcția spline este „uniformă”, altfel este „neuniformă”.

Dacă pe porțiuni polinoamele $P i$ sunt de gradul $\leq n$ , atunci funcția spline este de gradul $n$ (sau de ordinul $n + 1$ ).

Dacă $S \in C^{r_{i}}$ într-o vecinătate a lui $t i$ , atunci se spune că funcția spline are netezimea (de cel puțin) $C^{r_{i}}$ la $t i .$ Adică, la $t i$ cele două părți ale polinomului $P i -1$ și $P i$ au aceeași valoare a derivatelor cu derivata de ordinul 0 (valoarea funcției) până la derivata de ordinul al $r i -lea$ (cu alte cuvinte, cele două părți adiacente ale polinomului se conectează cu o „pierdere de netezime” de cel mult $n - r i$ )

\begin{matrix} P_{i - 1}^{(0)} (t_{i}) & = P_{i}^{(0)} (t_{i}) \\ P_{i - 1}^{(1)} (t_{i}) & = P_{i}^{(1)} (t_{i}) \\ ⋮ \\ P_{i - 1}^{(r_{i})} (t_{i}) & = P_{i}^{(r_{i})} (t_{i}) \end{matrix}

Un vector $r = (r 1, \dots, r k -1)$ astfel ca funcția spline să aibă netezimea $C^{r_{i}}$ în $t i$ pentru $i = 1, \dots, k - 1$ este „vectorul netezimii” funcției.

Având în vedere un vector al nodurilor $t$ , un grad $n$ și un vector al netezimii $r$ pentru $t$ , se poate considera mulțimea tuturor funcțiilor spline de gradul $\leq n$ având vectorul nodurilor $t$ și vectorul netezimii $r$ . Echipată cu operația de adunare a două funcții (adunare scalară) și luând multipli reali ai funcțiilor, această mulțime devine un spațiu vectorial real. Acest „spațiu spline” este notat de obicei cu $S_{n}^{𝐫} (𝐭) .$

În studiul matematic al funcțiilor spline polinomiale, întrebarea cu privire la ce se întâmplă atunci când două noduri, fie $t i$ și $t i +1$ , sunt luate aproape unul de celălalt, până la a coincide, are un răspuns simplu. Porțiunea polinomială $P i (t)$ dispare, iar porțiunile $P i -1 (t)$ și $P i +1 (t)$ se unesc cu suma pierderilor de netezime din $t i$ și $t i +1$ . Adică $S (t) \in C^{n - j_{i} - j_{i + 1}} [t_{i} = t_{i + 1}],$ unde $j i = n - r i .$ Asta duce la o înțelegere mai generală a unui vector de noduri. Pierderea de continuitate în orice punct poate fi considerată a fi rezultatul nodurilor multiple situate în acel punct, iar un tip de spline poate fi caracterizat complet prin gradul său $n$ și vectorul său de noduri extins.

(t_{0}, t_{1}, \dots, t_{1}, t_{2}, \dots, t_{2}, t_{3}, \dots, t_{k - 2}, t_{k - 1}, \dots, t_{k - 1}, t_{k})

unde $t i$ se repetă de $j i$ ori pentru $i = 1, \dots, k - 1.$

O curbă parametrică pe intervalul $[a, b]$

G (t) = (X (t), Y (t)), t \in [a, b]

este o curbă spline dacă ambele $X$ și $Y$ sunt funcții spline de același grad, cu aceiași vectori de noduri extinși pe acel interval.

Exemplu

Fie ca intervalul $[a, b]$ să fie $[0, 3],$ iar subintervalele sale să fie $[0, 1], [1, 2], [2, 3].$ Fie ca polinoamele pe porțiuni să fie de gradul al doilea, iar porțiunile $[0, 1]$ și $[1, 2]$ trebuie să se racordeze ca valoare și derivată de ordinul întâi (în $t = 1$ ), iar porțiunile $[1, 2]$ și $[2, 3]$ să se racordeze doar ca valoare (în $t = 2$ ). Acestea vor defini un tip de funcție spline $S (t)$ pentru care:

\begin{matrix} S (t) & = P_{0} (t) = - 1 + 4 t - t^{2} & 0 \leq t < 1 \\ S (t) & = P_{1} (t) = 2 t & 1 \leq t < 2 \\ S (t) & = P_{2} (t) = 2 - t + t^{2} & 2 \leq t \leq 3 \end{matrix}

va fi un membru de acest tip, și, de asemenea:

\begin{matrix} S (t) & = P_{0} (t) = - 2 - 2 t^{2} & 0 \leq t < 1 \\ S (t) & = P_{1} (t) = 1 - 6 t + t^{2} & 1 \leq t < 2 \\ S (t) & = P_{2} (t) = - 1 + t - 2 t^{2} & 2 \leq t \leq 3 \end{matrix}

va fi tot un membru de acest tip. (Notă: Deși piesa polinomială $2 t$ nu este de gradul al doilea, rezultatul se numește totuși o spline de gradul al doilea (pătratică). Aceasta demonstrează că gradul unei funcții spline este gradul maxim al părților sale polinomiale.)

Vectorul nodurilor extins pentru acest tip de spline ar fi $(0, 1, 2, 2, 3).$

Cea mai simplă spline are gradul 0 (funcție constantă pe porțiuni). Următoarea cea mai simplă spline are gradul 1 (spline liniară). O spline liniară închisă (adică primul nod și ultimul se suprapun) în plan este un poligon.

O spline comună este funcția spline cubică naturală. O spline cubică are gradul 3 cu continuitate $C 2,$ adică valorile funcției și derivatele de ordinul întâi și al doilea sunt continue. „Natural” înseamnă că derivatele de ordinul al doilea ale polinoamelor spline sunt zero la capetele intervalului de interpolare:

S^{″} (a) = S^{″} (b) = 0

Astfel, în afara intervalului graficul funcției spline este format din drepte, dar funcția este, totuși, netedă.

Note

↑ en Farin, G. E. (2002). Curves and surfaces for CAGD: a practical guide, Morgan Kaufmann, p. 119
↑ Bartels, Beatty, & Barsky, 1987
↑ Birkhoff & de Boor, 1964
↑ Ahlberg et al., 1967
↑ Birkhoff, 1990
↑ Young, 1997
↑ Davis, 1997

Bibliografie

en Ferguson, James C, Multi-variable curve interpolation, J. ACM, vol. 11, no. 2, pp. 221–228, Apr. 1964.
en Ahlberg, Nielson, and Walsh, The Theory of Splines and Their Applications, 1967.
en Birkhoff, Fluid dynamics, reactor computations, and surface representation, in: Steve Nash (ed.), A History of Scientific Computation, 1990.
en Bartels, Beatty, and Barsky, An Introduction to Splines for Use in Computer Graphics and Geometric Modeling, 1987.
en Birkhoff and de Boor, Piecewise polynomial interpolation and approximation, in: H. L. Garabedian (ed.), Proc. General Motors Symposium of 1964, pp. 164–190. Elsevier, New York and Amsterdam, 1965.
en Charles K. Chui, Multivariate Splines, SIAM, ISBN 978-0-898712261 (1987).
en Davis, B-splines and Geometric design, SIAM News, vol. 29, no. 5, 1996.
en Epperson, History of Splines, NA Digest, vol. 98, no. 26, 1998.
en Ming-Jun Lai, and Larry L. Schumaker, Spline Functions on Triangulations, Cambridge Univ. Press, ISBN 978-0-521-87592-9 (2007).
en Stoer & Bulirsch, Introduction to Numerical Analysis. Springer-Verlag. p. 93-106. ISBN 0387904204
en Schoenberg, Contributions to the problem of approximation of equidistant data by analytic functions, Quart. Appl. Math., vol. 4, pp. 45–99 and 112–141, 1946.
en Young, Garrett Birkhoff and applied mathematics, Notices of the AMS, vol. 44, no. 11, pp. 1446–1449, 1997.
en Chapra, Canale, Numerical Methods for Engineers 5th edition.
en Schumaker, Larry L., Spline Functions: Basic Theory, John Wiley, ISBN 0-47176475-2 (1981).
en Schumaker, Larry, Spline Functions: Computational Methods, SIAM, ISBN 978-1-61197-389-1 (2015).
en Schumaker, Larry, Spline Functions: More Computational Models, SIAM, ISBN 978-1-61197-817-9 (2024).

Legături externe

Utilitare online

en An Interactive Introduction to Splines (HTML5), ibiblio.org
en Symmetrical Spline Curves, an animation by Theodore Gray, The Wolfram Demonstrations Project, 2007.

Software

en pspline, czspline, ezspline - The current revision (2025) is in a private repository, this revision from 2019 is still available without requesting access.
en Sisl: Open source C-library for NURBS, SINTEF
en C++ cubic spline interpolation - A header-only library which supports cubic and cubic hermite splines

[1] Farin, G. E. (2002). Curves and surfaces for CAGD: a practical guide, Morgan Kaufmann, p. 119

[2] Bartels, Beatty, & Barsky, 1987

[3] Birkhoff & de Boor, 1964

[4] Ahlberg et al., 1967

[5] Birkhoff, 1990

[6] Young, 1997

[7] Davis, 1997

[1]

[2]

[3]

[4]

[5]

[6]

[7]