Spline — Wikipédia

En mathématiques appliquées et en analyse numérique, une spline est une fonction définie par morceaux par des polynômes.

Spline est un terme anglais qui, lorsqu'il est utilisé en français, est généralement prononcé [splin], à la française. Il désigne une réglette de bois souple appelée cerce en français. Toutefois, dans l'usage des mathématiques appliquées, le terme anglais spline est généralisé et le mot français cerce ignoré.

Dans les problèmes d'interpolation, la méthode des splines est très souvent préférée à l'interpolation polynomiale. Les splines sont également utilisées dans les problèmes de lissage de données expérimentales ou de statistiques.

Les splines sont utilisées pour représenter numériquement des contours complexes. Leur mise en œuvre est simple. Elles sont fréquemment employées dans les logiciels de dessin ou de conception graphique ; leur usage y a été généralisé par Pierre Bézier avec les B-splines.

Historique[modifier | modifier le code]

L'origine historique des splines se trouve dans la conception industrielle.

Autrefois, avant l'existence des outils numériques, la conception industrielle était fondée sur la géométrie et le dessin. Les concepteurs d'une pièce de machine, par exemple, définissaient graphiquement les quelques points, ou nœuds, par lesquels devait nécessairement passer le contour de la pièce (dessin technique). Le travail du dessinateur industriel consistait à relier ces nœuds par des courbes aussi lisses que possible afin d'éviter les discontinuités, sources de faiblesses mécaniques et de ruptures. Ces courbes devaient être « agréables à l'œil » : il y a un rapport direct entre la notion subjective d'« agrément » et la notion mathématique de classe de régularité d'une fonction, c'est-à-dire de ses propriétés de continuité et de dérivation.

Pour le tracé graphique des contours, on utilisait une réglette de bois élastique, appelée spline en anglais et cerce en français. À l'aide de tenons, on faisait passer la réglette par les nœuds et on traçait entre ceux-ci la courbe prise par la réglette. Les propriétés mécanique d'une réglette de bois sont telles que celle-ci prend, sous déformation, une forme qui a des dérivées continues à un ordre élevé (la dérivée première est continue, la dérivée seconde aussi, etc.)

Sur le terme spline[modifier | modifier le code]

Prononciation[modifier | modifier le code]

Spline est un mot anglais qui, dans cette langue, se prononce [splaɪn], ce qui le distingue de « spleen » [spli:n]. En français, on prononce le mot tel qu'il s'écrit : [splin].

Étymologie[modifier | modifier le code]

Pierre Bézier écrit^[1] :

« Le mot anglais spline a malencontreusement prévalu, alors qu'il se traduit en français par les substantifs latte ou baguette. »

The Oxford English Dictionnary 1989 donne les définitions suivantes pour le mot spline :

« A long narrow, and relatively thin piece or strip of wood, metal, etc.; a slat. A flexible strip of wood or hard rubber used by draftsmen in laying out broad sweeping curves, especially in railroad work. »

« Une pièce longue, étroite et relativement mince de bois, de métal, etc., une latte. Une bande flexible de bois ou de caoutchouc dur utilisée par les dessinateurs industriels dans le tracé de larges courbes, en particulier dans les travaux ferroviaires. »

Les menuisiers, charpentiers et escaliéteurs nommaient cet outil cerce, latte souple de bois bien de fil servant à tracer des courbes « quelconques » (courbes harmonieuses passant par un certain nombre de points et qui ne peuvent être tracées à l'aide du compas).

Approximation mathématique des splines[modifier | modifier le code]

La description de la forme prise par la réglette de bois, fondée sur les lois de l'élasticité, est mathématiquement compliquée. On obtient toutefois une approximation acceptable pour les usages pratiques en représentant la forme de la réglette par une spline, c'est-à-dire une fonction définie par morceaux par un polynôme sur chaque intervalle entre nœuds.

Ces polynômes peuvent être calculés en posant des conditions de continuité : ils passent par les nœuds, la pente du contour est continue, c'est-à-dire que les polynômes à droite et à gauche du nœud ont même dérivée première ; de même, en chaque nœud, la courbure est continue, c'est-à-dire que les polynômes à droite et à gauche ont même dérivée seconde. Une solution est donnée par des morceaux de polynômes du troisième degré. C'est le degré minimum des polynômes pour que la fonction, sa pente et sa courbure soient continues à chaque nœud. Cette courbe par morceaux s'appelle spline.

Les splines cubiques sont les plus utilisées dans la pratique. Elles sont plus faciles à utiliser que l'interpolation polynomiale et n'ont pas en général de comportements aberrants. Dans quelques cas particuliers, on peut être conduit à utiliser des polynômes du quatrième degré ; toutefois cet usage résulte de la pratique des analystes mais nullement de considérations théoriques.

D'autres familles de fonctions splines (obtenues par minimisation d'une fonctionnelle d'énergie) ont également été développées dans le cadre de l'approximation de données.

Définition[modifier | modifier le code]

Soit une série de points de donnée, ou nœuds, de coordonnées $(X i, Y i)$ . On appelle spline d'interpolation la fonction par morceaux constituée d'un polynôme sur chaque intervalle entre nœuds.

Le degré de la spline est défini par le polynôme de plus haut degré utilisé : si on joint simplement les nœuds par des droites, c'est-à-dire si la spline est constituée de polynômes du premier degré, la spline est de degré 1, etc. Si tous les polynômes ont même degré, on parle de spline uniforme. Si tous les polynômes sont du troisième degré, on parle de spline cubique.

Exemples[modifier | modifier le code]

Voici l'exemple de splines d'interpolation de degré 1, d'une part, et de degré 3, d'autre part, fondées sur les quatre mêmes nœuds (les points rouges des graphiques ci-dessous.

À gauche, la spline de degré 1 relie les quatre nœuds par des polynômes de degré 1, c'est-à-dire par des droites. La spline est continue, mais la pente n'est pas continue (elle passe brutalement d'une valeur à une autre). Les polynômes, des fonctions linéaires, permettent, entre les nœuds, des interpolations linéaires.

À droite, une spline cubique dans laquelle les nœuds sont reliés par des polynômes du 3^e degré auxquels on a imposé des conditions pour rendre la spline continue au premier degré (les pentes varient de façon continue) et au second degré (la courbure de la spline, plus précisément sa dérivée seconde, varie de façon continue).

Exemples de splines

Exemple de spline de degré 1 pour quatre nœuds.

Exemple de spline de degré 3 pour quatre nœuds.

Continuité de la spline[modifier | modifier le code]

Comme les polynômes sont continus, indéfiniment dérivables et que leurs dérivées successives sont continues, la continuité de la spline dépend des conditions de continuité qu'on impose en chaque nœud. La continuité définit les caractéristiques de la jonction entre chaque intervalle. Cela correspond au degré de correspondance entre deux polynômes successifs aux points de jonction.

$C 0$ est la continuité minimum : les polynômes successifs passent bien par les points de jonction ;
$C 1$ est la continuité des tangentes : les polynômes successifs ont des dérivées premières (c'est-à-dire des pentes) égales aux points jonction ;
$C 2$ est la continuité de la courbure : les polynômes successifs ont de plus des dérivées secondes (des courbures) égales aux points jonction ;

L'application des conditions

C 0

,

C 1

et

C 2

conduit aux splines cubiques.

Spline d'interpolation[modifier | modifier le code]

Lorsqu'on a déterminé les éléments de la spline, c'est-à-dire les paramètres des polynômes qui joignent chacun des points donnés (les nœuds), on peut calculer l'ordonnée d'un point situé entre deux nœuds : c'est la valeur du polynôme pour l'abscisse correspondante. La spline permet donc d'interpoler les valeurs comprises entre les nœuds.

Inconvénients des splines[modifier | modifier le code]

Quoiqu'elles soient plus stables que d'autres méthodes d'interpolation, les splines n'en présentent pas moins quelques inconvénients:

l'évaluation des paramètres de la spline peuvent diverger si la pente entre deux nœuds varie fortement d'un intervalle au suivant ;
la spline dépend du choix du système de coordonnées, elle ne possède donc pas de propriété d’invariance géométrique (cas d'une rotation par exemple) ; toutefois, elle reste insensible à une homothétie sur l'un des axes ;
on ne peut utiliser l'interpolation par spline si la courbe à représenter n'est pas une fonction, c'est-à-dire s'il y a plus d'une valeur pour une abscisse donnée (courbes qui « reviennent en arrière » comme les ellipses, les cercles, etc.) Dans ce cas, on utilise des généralisations des splines (B-splines, NURBS).

Calcul des éléments d'une spline cubique[modifier | modifier le code]

Considérons n nœuds de coordonnées $(X 1, Y 1), ..., (X n, Y n)$ . Il y a n-1 intervalles. Nous voulons donc déterminer les paramètres de n-1 polynômes du troisième degré, $S 1, ..., S n -1$ .

Chaque polynôme $S$ a une équation de la forme :

S=a_{0}x^{3}+a_{1}x^{2}+a_{2}x+a_{3}

Il faut donc déterminer quatre coefficients par polynôme, soit au total 4n-4 inconnues, pour lesquelles on doit poser autant de conditions.

Les conditions $C 0$ , $C 1$ et $C 2$ s'expriment de la façon suivante :

$C 0$ : chacun des n-1 polynômes passe par deux nœuds, soit 2n-2 conditions ;
$C 1$ : les polynômes ont les mêmes dérivées premières aux n-2 nœuds de jonction, soit n-2 conditions ;
$C 2$ : et ces polynômes ont la même dérivée seconde aux n-2 nœuds de jonction, soit n-2 conditions.

Au total on a ainsi 4n-6 conditions. Il manque donc deux conditions pour déterminer les 4n-4 inconnues. On adjoint deux conditions supplémentaires en imposant la valeur des dérivées secondes à chaque nœud extrême. Si on impose que les dérivées secondes soient nulles à chaque extrémité, on obtient une spline cubique naturelle. On peut disposer toutefois d'informations supplémentaires qui permettent de fixer de façon plus précise la dérivée seconde aux extrémités.

On obtient ainsi un système de 4n-4 équations linéaires à 4n-4 inconnues.

Algorithme de calcul[modifier | modifier le code]

On trouvera ci-dessous un algorithme de calcul d'une spline cubique d'interpolation, naturelle ou non. Cet algorithme est présenté en langage naturel et mathématique, sans référence à quelque langage de programmation que ce soit. Il peut être mis en œuvre avec un simple tableur.

Algorithme de calcul d'une spline d'interpolation

Soit

X i

et

Y i

les abscisses et ordonnées de

n

nœuds, les abscisses étant classées par ordre croissant.

1. Calculer la matrice colonne

h

des largeurs des

n -1

intervalles entre nœuds :

\mathbf {h} _{i}=X_{i+1}-X_{i}

, pour

i

de 1 à

n -1

.

2. Calculer la matrice colonne

F

des

n -2

dérivées secondes aux nœuds :

2.1. Pour les nœuds 2 à

n -1

:

\mathbf {F} _{i}={\frac {Y_{i+1}-Y_{i}}{\mathbf {h} _{i}}}-{\frac {Y_{i}-Y_{i-1}}{\mathbf {h} _{i-1}}}

, pour

i

de 2 à

n -1

.

2.2. Il faut de plus valoriser les dérivées secondes aux extrémités,

F 1

et

F n

.

Si l'on pose

F 1 = 0

et

F n = 0

, on obtient une spline naturelle ;

si l'on possède des informations sur les extrémités, on affecte à

F 1

et/ou à

F n

la valeur ad hoc.

3. Construire la matrice carrée

R i, j

, de dimensions

n \times n

, telle que,

i

désigne l'indice des lignes et

j

celui des colonnes :

3.1 Mettre tous les éléments de la matrice

R

à 0.

3.2 Sur la première ligne, seul le premier élément n'est pas nul :

R 1,1 = 1

.

3.3 Sur la dernière ligne, seul le dernier élément n'est pas nul :

R n, n = 1

.

3.4 La sous-matrice de

R

de dimension

(n -2) \times n

en excluant la première et la dernière ligne est tridiagonale. Tous ses éléments sont nuls, sauf :

La diagonale centrale de la sous-matrice vaut :

\mathbf {R} _{i,i}={\frac {h_{i-1}+h_{i}}{3}}

pour

i = 2, ..., n -1

.

La diagonale supérieure vaut :

\mathbf {R} _{i,{i+1}}={\frac {h_{i}}{6}}

pour

i = 2, ..., n -1

.

La diagonale inférieure vaut :

\mathbf {R} _{i,{i-1}}={\frac {h_{i-1}}{6}}

pour

i = 2, ..., n -1

.

4. Calculer la matrice colonne

M

de dimension

n

, telle que :

\mathbf {M} =\mathbf {R} ^{-1}\times \mathbf {F}

.

5. Calculer les matrices colonnes

C

et

C'

, de dimensions

n -1

, contenant respectivement les constantes d'intégration d'ordre 1 et 2 des

n -1

polynômes, de la façon suivante :

Pour

i

de 1 à

n -1

:

\mathbf {C} _{i}={\frac {Y_{i+1}-Y_{i}}{\mathbf {h} _{i}}}-{\frac {\mathbf {h} _{i}}{6}}(\mathbf {M} _{i+1}-\mathbf {M} _{i})

\mathbf {C'} _{i}=Y_{i}-\mathrm {M} _{i}{\frac {\mathbf {h} _{i}^{2}}{6}}

6. Calcul d'une valeur d’interpolation pour une abscisse

x

située dans l'intervalle

k

, entre les nœuds d'abscisses

X

_k et

X k +1

(avec

k

de 1 à

n -1

) :

{\begin{array}{lcl}y&=&\mathbf {M} _{k}{\frac {(X_{k+1}-x)^{3}}{6\mathbf {h} _{k}}}\\&+&\mathbf {M} _{k+1}{\frac {(x-X_{k})^{3}}{6\mathbf {h} _{k}}}\\&+&\mathbf {C} _{k}(x-X_{k})\\&+&\mathbf {C'} _{k}\end{array}}

Exemple

Cet exemple présente l'approximation de la courbe $y = sin x$ par une spline cubique naturelle pour laquelle on donne les cinq valeurs suivantes (5 nœuds) de la fonction :

n=5

{\begin{array}{rrr}i&X_{i}&Y_{i}\\1&0{,}0&0{,}0000\\2&0{,}5&0{,}4794\\3&1{,}0&0{,}8415\\4&1{,}5&0{,}9975\\5&2{,}0&0{,}9093\\\end{array}}

\mathbf {h} ={\begin{bmatrix}0{,}5\\0{,}5\\0{,}5\\0{,}5\\\end{bmatrix}}{\text{ ; }}

\mathbf {F} =\left[{\begin{array}{r}0{,}0000\\-0{,}2348\\-0{,}4120\\-0{,}4884\\0{,}0000\\\end{array}}\right]{\text{ ; }}

\mathbf {R} =\left[{\begin{array}{rrrrr}1{,}0000&0&0&0&0\\0{,}0833&0{,}3333&0{,}0833&0&0\\0&0{,}0833&0{,}3333&0{,}0833&0\\0&0&0{,}0833&0{,}3333&0{,}0833\\0&0&0&0&1{,}0000\\\end{array}}\right]{\text{ ; }}

\mathbf {M} =\left[{\begin{array}{r}0{,}0000\\-0{,}5061\\-0{,}7928\\-1{,}2671\\0{,}0000\\\end{array}}\right]{\text{ ; }}

\mathbf {C} =\left[{\begin{array}{r}1{,}0010\\0{,}7480\\0{,}3516\\-0{,}2820\\\end{array}}\right]{\text{ ; }}

\mathbf {C'} =\left[{\begin{array}{r}0{,}0000\\0{,}5005\\0{,}8745\\1{,}0503\\\end{array}}\right]

Commentaire sur l'exemple : La fonction $sin(i)$ est bien représentée par son approximation par une spline naturelle à gauche du graphique parce que la dérivée seconde de $sin(i)$ est bien nulle pour $i=0$ , comme le suppose le calcul de la spline naturelle. En revanche, à droite du graphique, l'approximation par une spline naturelle est moins exacte, en effet, la dérivée seconde de $sin(i)$ n'est pas nulle pour $X_{5}=2{,}0$ (elle vaut $-0,035$ ), valeur différente de l'hypothèse de nullité posée pour la détermination de la spline naturelle.

Forme explicite d'une spline cubique[modifier | modifier le code]

Pour une fonction $f()$ dont on connaît les valeurs aux nœuds $X_{i}$ , l'expression générale pour la spline cubique de classe C² en un point $x$ dans $[X_{i-1},X_{i}]$ est la suivante :

S_{i}(x)={\frac {z_{i}(x-X_{i-1})^{3}}{6h_{i}}}+{\frac {z_{i-1}(X_{i}-x)^{3}}{6h_{i}}}+\left[{\frac {f(X_{i})}{h_{i}}}-{\frac {z_{i}h_{i}}{6}}\right](x-X_{i-1})+\left[{\frac {f(X_{i-1})}{h_{i}}}-{\frac {z_{i-1}h_{i}}{6}}\right](X_{i}-x)

où

$f(X_{i}^{})$ est la valeur de $f()$ au nœud i,
$h_{i}^{}=X_{i}\;{\text{-}}\;X_{i-1}$ ,
$z_{i}=f^{\prime \prime }(X_{i})$ est la dérivée seconde de $f()$ au nœud i.

On vérifie facilement que $S_{i}(X_{i-1})=f(X_{i-1})$ et $S_{i}(X_{i})=f(X_{i})$ .

Mise en œuvre dans des logiciels[modifier | modifier le code]

B-splines (courbes de Bézier) utilisées dans Inkscape.

Les splines sont souvent intégrées dans des logiciels de dessin, que ce soient des logiciels généralistes, comme les fonctions de dessin des suites de logiciels de bureautique (Microsoft Office, LibreOffice…), des logiciels de dessin et de traitement d'image (Inkscape, GIMP…) ou bien des logiciels de dessin ou de conception assistés par ordinateur. Ces logiciels utilisent le plus souvent des B-splines.

Spline de lissage[modifier | modifier le code]

Utilisation de splines pour le lissage[modifier | modifier le code]

Les données de mesure sont généralement affectées d'aléas, que ce soit dans les sciences physiques ou dans les sciences humaines (économie, démographie, sociologie, etc.) Pour approcher empiriquement une fonction inconnue dont les mesures sont perturbées par des aléas, on pratique souvent le lissage. L'idée heuristique sous-jacente est que les fonctions qui représentent les phénomènes physique ou en sciences humaines sont généralement très continues : le lissage a donc pour objet de substituer des valeurs continues à des valeurs de mesure dispersées à cause des aléas. Ce problème se pose en particulier pour des mesures d'une grandeur évoluant dans le temps (série chronologique).

Il existe de nombreuses méthodes empiriques de lissage, telles que les moyennes mobiles, le lissage exponentiel simple ou double, etc. Les splines de lissage font partie de ces méthodes empiriques.

Considérons des données de mesure dont les abscisses sont strictement croissantes (ce sont souvent des données chronologiques).

L'idée conduisant aux splines de lissage repose sur l'utilisation de la même réglette flexible que celle qui est à l'origine des splines d'interpolation (voir : Conception industrielle ci-avant). Toutefois, au lieu d'imposer à la réglette de passer par les nœuds (les valeurs de mesure), on suppose qu'on relie ceux-ci à la cerce par des ressorts. La réglette décrit alors une fonction très continue qui minimise l'énergie totale de déformation des ressorts et de la réglette.

Forme d'équilibre d'une fonction de lissage[modifier | modifier le code]

Soit $n$ valeurs connues (nœuds), dont les abscisses sont strictement croissantes, que l'on souhaite lisser. On relie ces $n$ nœuds à une réglette flexible de raideur $r$ par des ressorts ayant tous la même raideur $k$ . La forme d'équilibre est celle qui minimise l'énergie totale d'allongement des ressorts et de courbure de la réglette.

Énergie d'allongement des ressorts[modifier | modifier le code]

Chaque ressort $i$ s'allonge d'une longueur $e i$ . L'énergie d'allongement d'un ressort élastique est proportionnelle au carré de l'allongement ; l'énergie d'allongement du ressort n^o $i$ vaut :

w_{i}=ke_{i}^{2}

où

k

est la raideur du ressort.

L'énergie totale d'allongement des ressorts est la somme des énergies d'allongement des $n$ ressorts :

W_{R}=\sum w_{i}=\sum ke_{i}^{2}

(en supposant que la raideur de tous les ressorts est identique et égale à

k

).

Énergie de déformation de la réglette[modifier | modifier le code]

L'énergie élastique de courbure d'une cerce élastique est proportionnelle en tout point au carré de la courbure en ce point. On approxime la courbure par la dérivée seconde de la fonction $s (x)$ représentant la forme de la réglette. Cette approximation est admissible en pratique si la pente de la fonction n'est pas trop grande (>>1). Alors l'énergie de courbure entre $x$ et $x + dx$ vaut :

dW_{C}=rs''(x)^{2}dx

où

r

est la raideur de courbure élastique de la cerce.

L'énergie de déformation pour toute la réglette vaut :

W_{C}=\int rs''(x)^{2}\,\mathrm {d} x

si l'on suppose qu'elle présente une raideur constante sur toute sa longueur.

Condition sur la forme prise par la réglette[modifier | modifier le code]

La forme prise par la réglette est celle qui minimise l'énergie totale de déformation, c'est-à-dire l'énergie d'allongement des ressorts et l'énergie de courbure de la réglette. C'est la fonction qui minimise l'expression :

W(s,\lambda )=\sum e_{i}^{2}+\lambda \int s''(x)^{2}dx

où

λ

est le rapport entre la raideur

r

de la réglette et la raideur

k

des ressorts.

Spline cubique de lissage[modifier | modifier le code]

Trouver la fonction $s$ qui minimise $W (s, λ)$ pour $λ$ donné se simplifie si l'on suppose que cette fonction est une spline cubique : courbe par morceaux constituée de polynômes du troisième degré. Si l'on doit lisser $n$ valeurs (ou nœuds), il y a $n -1$ intervalles et donc $n -1$ polynômes du troisième degré définis chacun par quatre paramètres, soit au total $4 n -4$ paramètres à déterminer.

On impose à ces fonctions polynomiales d'être continues à chaque jonction, d'y avoir une pente (dérivée première) et une dérivée seconde continue, soit :

$C 0$ : chacun des $n -1$ polynôme est jointif au suivant, soit $n -2$ conditions ;
$C 1$ : les polynômes ont même dérivée première aux $n -2$ jonctions, soit $n -2$ conditions ;
$C 2$ : et ces polynômes ont même dérivée seconde aux $n -2$ jonctions, soit $n -2$ conditions.

Soit $3 n -6$ conditions.

La minimisation de $W (s, λ)$ , où $λ$ est fixé, correspond à $n$ conditions. Soit donc au total $4 n -6$ conditions. Il manque deux conditions pour déterminer les $4 n -4$ inconnues. On impose que les dérivées secondes aux extrémités soient nulles. L'ensemble de ces conditions conduit à $4 n -4$ équations linéaires à $4 n -4$ inconnues. (Si l'on dispose d'informations supplémentaires pour les courbures aux points extrêmes, on peut utiliser ces valeurs connues au lieu de la valeur 0.)

Algorithme de calcul[modifier | modifier le code]

On trouvera ci-dessous un algorithme de calcul d'une spline cubique de lissage. Cet algorithme est présenté en langage naturel et mathématique, sans référence à quelque langage de programmation que ce soit. Il peut être mis en œuvre avec un simple tableur.

Algorithme de calcul d'une spline cubique de lissage

Algorithme de calcul d'une spline cubique de lissage^[2].

Soit

X i

et

Y i

les abscisses et ordonnées de

n

nœuds, les abscisses étant classées par ordre croissant

(n > 2)

.

1. Calculer la matrice colonne h

des largeurs des

n -1

intervalles entre nœuds :

\mathbf {h} _{i}=X_{i+1}-X_{i}

, pour

i

de 1 à

n -1

.

2. Construire la matrice tridiagonale

Q

(

n \times (n -2)

) telle que toutes les valeurs de la matrice sont nulles, sauf :

La diagonale centrale :

\mathbf {Q} _{i,{i-1}}={\frac {1}{h_{i-1}}}+{\frac {1}{h_{i}}}

, pour

i = 2

à

n -1

;

La diagonale supérieure :

\mathbf {Q} _{i,i}=-{\frac {1}{h_{i}}}

, pour

i = 1

à

n -2

;

La diagonale inférieure :

\mathbf {Q} _{i,{i-2}}=-{\frac {1}{h_{i-1}}}

, pour

i = 3

à

n

;

3. Construire la matrice carrée tridiagonale

R

(

(n -2)\times(n -2)

) telle que toutes les valeurs de la matrice sont nulles, sauf :

La diagonale principale :

\mathbf {R} _{i,i}={\frac {h_{i}+h_{i+1}}{3}}

, pour

i = 1

à

n -2

;

La diagonale supérieure :

\mathbf {R} {i,{i+1}}=-{\frac {h_{i}}{6}}

pour

i = 1

à

n -3

;

La diagonale inférieure :

\mathbf {R} {i,{i-1}}=-{\frac {h_{i-1}}{6}}

pour

i = 2

à

n -2

;

4. Calculer la matrice carrée

K

(

n \times n

) :

\mathbf {K} =\mathbf {Q} \mathbf {R} ^{-1}\mathbf {Q} ^{t}

;

5. Soit

\mathbf {I}

la matrice unitaire

n \times n

et

\lambda

le paramètre de lissage.

On obtient les ordonnées

s

de la spline de lissage en chacun des

n

nœud d'abscisse

X

et d'ordonnée

Y

pour la valeur

\lambda

du paramètre de lissage par :

\mathbf {s} =(\mathbf {I} +\lambda \mathbf {K} )^{-1}\mathbf {Y}

.

6. On peut interpoler la valeur de la spline de lissage pour toute abscisse comprise entre les nœuds extrêmes

X 1

et

X n

en appliquant l'algorithme d'interpolation des splines aux points d'abscisse

X

et d'ordonnée

s

.

Exemple :

Cet exemple présente le lissage des quatre nœuds de coordonnées $(X i, Y i)$ , figurés en rouge dans le graphique ci-dessus, par une spline cubique naturelle avec le paramètre de lissage $λ = 1,5$ .

{\begin{array}{rrr}i&X_{i}&Y_{i}\\1&0{,}0&0{,}0\\2&1{,}0&6{,}0\\3&3{,}0&5{,}0\\4&5{,}0&0{,}0\\\end{array}}

;

\mathbf {h} ={\begin{bmatrix}1{,}0\\2{,}0\\2{,}0\\\end{bmatrix}}{\text{ ; }}

\mathbf {Q} ={\begin{bmatrix}{\begin{array}{rr}-1{,}0000&0{,}0000\\1{,}5000&-0{,}5000\\-0{,}5000&1{,}0000\\0{,}0000&-0{,}5000\\\end{array}}\end{bmatrix}}{\text{ ; }}

\mathbf {R} ={\begin{bmatrix}{\begin{array}{rr}1{,}0000&-0{,}1667\\-0{,}1667&1{,}3333\\\end{array}}\end{bmatrix}}

;

\mathbf {K} =\mathbf {Q} \mathbf {R} ^{-1}\mathbf {Q} ^{t}={\begin{bmatrix}{\begin{array}{rrrr}1{,}0213&-1{,}4681&0{,}3830&0{,}0638\\-1{,}4681&2{,}2979&-0{,}9255&0{,}0957\\0{,}3830&-0{,}9255&0{,}8936&-0{,}3511\\0{,}0638&0{,}0957&-0{,}3511&0{,}1915\\\end{array}}\end{bmatrix}}

;

I

étant la matrice unité

n \times n

et avec le paramètre

λ

, on calcule :

(\mathbf {I} +\lambda \mathbf {K} )={\begin{bmatrix}{\begin{array}{rrrr}2.53191&-2.20213&0.57447&0.09574\\-2.20213&4.44681&-1.38830&0.14362\\0.57447&-1.38830&2.34043&-0.52660\\0.09574&0.14362&-0.52660&1.28723\\\end{array}}\end{bmatrix}}{\text{, et : }}

(\mathbf {I} +\lambda \mathbf {K} )^{-1}={\begin{bmatrix}{\begin{array}{rrrr}0.7051&0.3583&0.0206&-0.0840\\0.3583&0.4599&0.1843&-0.0026\\0.0206&0.1843&0.5800&0.2152\\-0.0840&-0.0026&0.2152&0.8714\\\end{array}}\end{bmatrix}}

.

d'où l'on calcule

\mathbf {s} =(\mathbf {I} +\lambda \mathbf {K} )^{-1}\mathbf {Y}

Paramètre de lissage[modifier | modifier le code]

On suppose généralement que les ressorts qui tirent la cerce ont tous la même raideur $k$ . Leur donner des raideurs différentes revient à pondérer les nœuds en considérant que certains sont plus ou moins importants, ou plus ou moins "attractifs" que d'autres. C'est l'expérience des analystes qui permet d'établir ces pondérations.

Si tous les ressorts ont même coefficient de raideur $k$ , Le paramètre de lissage, noté souvent $λ$ , exprime le rapport entre la raideur élastique de la réglette et celle des ressorts. $λ$ peut varier entre 0 et $+\infty$ :

si $λ = 0$ , les ressorts sont "infiniment" durs par rapport à la cerce. Dans ce cas, la spline passe par les nœuds et l'on obtient une spline naturelle ;
si $λ$ tend vers $+\infty$ , cela revient à supposer que la cerce devient "infiniment" raide par rapport aux ressorts. Dans ce cas, la spline de lissage tend vers la droite de régression des nœuds.

Exemples de splines de lissage cubiques

Lissage de quatre nœuds avec une spline cubique de lissage de paramètre λ = 0,3.

Lissage de quatre nœuds avec une spline cubique de lissage de paramètre λ = 1,5.

Pour mieux apprécier l'intensité du lissage, on utilise souvent le paramètre $p$ , tel que :

p={\frac {1}{\lambda +1}}

, c'est-à-dire :

\lambda ={\frac {1-p}{p}}

, où

p

varie entre 0 (exclu) et 1.

p = 1

correspond à

λ = 0

: on obtient la spline naturelle passant par les nœuds ;

p \to 0 +

correspond à

λ \to +\infty

: la spline obtenue tend vers la droite de régression.

Optimisation du paramètre de lissage[modifier | modifier le code]

Lorsqu'on étudie de nombreuses données de mesure bruitées, l'objectif du lissage est de fournir une estimation non bruitée de la mesure. Si l'on peut estimer la variance du bruit, la variance des écarts entre données brutes et les données lissées comparée à la variance du bruit peut guider le choix du paramètre de lissage.

On applique ce procédé de façon plus systématique de la façon suivante :

Le paramètre de lissage étant donné, supprimons le nœud n^o $i$ de la série des mesures et déterminons la spline de lissage de paramètre $λ$ avec ce nœud exclu du calcul. L'écart $ε i$ pour le nœud n^o $i$ entre la valeur brute et la valeur de la spline de lissage mesure l'erreur de prévision pour ce nœud. Réitérons cette opération, avec le même paramètre $λ$ , pour les $n$ nœuds :

l'indicateur

\sum {\frac {\epsilon _{i}^{2}}{n}}

est une approximation de la variance de la prévision par spline de lissage sous condition du paramètre $λ$ . On appelle cet indicateur score de validation croisée $CV(λ)$ .

En réitérant cette procédure pour plusieurs valeurs de $λ$ , on peut rechercher la valeur du paramètre de lissage qui minimise ce score de validation croisée. Il n'est pas garanti que $CV$ n'aie pas des minimums locaux. Les calculs nécessaires peuvent donc être volumineux et la recherche laborieuse. Heureusement, on dispose d'un algorithme qui permet de déterminer $CV(λ)$ sans effectuer le calcul des splines cubiques de lissage.

Calcul pratique des splines[modifier | modifier le code]

Que ce soit pour l'interpolation ou le lissage, le calcul met en jeu, si les nœuds sont nombreux, de très grosses matrices qui peuvent poser problème lors de la mise en œuvre du calcul. Les matrices utilisées sont très creuses, c'est-à-dire que tous leurs éléments, sauf ceux de trois diagonales principales, sont nuls. Il existe des logiciels mettant en œuvre des méthodes efficaces de stockage de matrices creuses. Néanmoins, les calculs peuvent être longs.

Reinsch (de) donne un algorithme qui utilise la factorisation de Cholesky pour réduire la taille des calculs.

Notes et références[modifier | modifier le code]

↑ Pierre Bézier, « Courbes et surfaces pour la CFAO », Techniques de l'ingénieur Applications des mathématiques, vol. TIB102DUO, n^o a1440,‎ 1992 (lire en ligne, consulté le 25 décembre 2017).
↑ E. Moulines, « Étude de cas de régression non paramétrique » [PDF].

Voir aussi[modifier | modifier le code]

Sur les autres projets Wikimedia :

spline, sur le Wiktionnaire

Articles connexes[modifier | modifier le code]

Bibliographie (splines, B-splines, Dm-splines...)[modifier | modifier le code]

Outre les travaux initiaux de De Casteljau et Bézier, les ouvrages de références sont ceux de Pierre Jean Laurent (Approximation et optimisation, Hermann, Paris, 1972), Carl de Boor (A Practical Guide to Splines, Springer Verlag, Berlin-Heidelberg, 1978).
D.G. Schweikert, An interpolation curve using a spline in tension, J. Math. and Phys., vol 45, pp. 312-317, 1966.
L.L. Schumaker, Fitting surfaces to scattered data, Approximation Théorie II, G.G. Lorentz, C.K. Chui et L.L. Schumaker (éditeurs), Academic Press, 203-269, (1976).
M. Atteia, Fonctions "spline" définies sur un ensemble convexe, Numer. Math., 12, 192-210, 1968.
R. Arcangéli, Some Applications of Discrete D^{m} Splines, Mathematical Methods in Computer Aided Geometric Design, T. Lyche et L.L. Schumaker (Editeurs), Academic Press, 35-44, 1989.
R. Arcangéli, M. C. López-de-Silanes, and J. J. Torrens, Multidimensional minimizing splines. Theory and applications, Grenoble Sciences, pp.1-4020, 2004.
J. Duchon, Splines Minimizing Rotation- Invariant Semi- Norms in Sobolev Spaces, Lecture Notes in Math., 571, 85-100, Springer, 1977.
C. Gout, Z. Lambert and D. Apprato, Data approximation : mathematical modelling and numerical simulations, (ISBN 978-2-7598-2367-3), EDP Sciences, 2019.
G. Demengel et J. P. Pouget, Modèles de Bézier, des B-splines et des NURBS, Ellipses, 1998, 286 p. (ISBN 978-2-7298-9806-9)
Michelle Schatzman, Analyse numérique : : Approche mathématique, Paris, Dunod, coll. « Sciences Sup », juillet 2004, 480 p. (ISBN 978-2-10-048732-5).

Liens externes[modifier | modifier le code]

(en) Richard Bartels, John C. Beatty, Brian A. Barsky, An Introduction to the Use of Splines in Computer Graphics, TR CS-83-09, Introduction à l'usage des splines en dessin par informatique, Université de Waterloo, Canada ;
(en) Christian H. Reinsch, « Smoothing by Spline Functions », Numerische Mathematik, vol. 10,‎ 1967, p. 177-183 (lire en ligne, consulté le 14 janvier 2018) ;
J-P Croisille, « INTERPOLATION SPLINE » [PDF], master de mathématiques M1, année 2008-2009, sur http://www.iecl.univ-lorraine.fr/, Institut Élie Cartan de Lorraine, 2008 (consulté le 14 janvier 2018) ;
Frédéric PLANCHET, « Méthodes de lissage et d’ajustement » [PDF], MODÈLES DE DURÉE - Support de cours 2017-2018, sur http://www.ressources-actuarielles.net/, Institut de science financière et d'assurance, août 2017 (consulté le 14 janvier 2018), p. 4.

Portail de l'analyse

[1] Pierre Bézier, « Courbes et surfaces pour la CFAO », Techniques de l'ingénieur Applications des mathématiques, vol. TIB102DUO, n^o a1440,‎ 1992 (lire en ligne, consulté le 25 décembre 2017).

[Moulines-2] E. Moulines, « Étude de cas de régression non paramétrique » [PDF].

[1]

[2]

v · m Analyse numérique
Recherche de zéro	Méthode de Josephy-Newton Méthode de la sécante Méthode de Newton Point fixe
Transformations de matrice	Matrice de Hessenberg Décomposition LU Factorisation de Cholesky
Résolutions de systèmes	Méthode de Gauss-Seidel Méthode de surrelaxation successive (SOR) Méthode de Jacobi Décomposition QR Décomposition LU
Intégration numérique	Méthode du point médian Méthode des trapèzes Méthode de Simpson Méthodes de quadrature de Gauss Formule de Newton-Cotes Méthode de Romberg Méthode de Monte-Carlo
Équations différentielles	Méthode d'Euler (et semi-implicite) Méthodes de Runge-Kutta Intégration de Verlet Leapfrog Méthode multi-pas linéaire (en) (Adams-Bashforth, backward differentiation formula (en))
Interpolation numérique	Spline Interpolation polynomiale Interpolation lagrangienne Interpolation d'Hermite Suite de polynômes orthogonaux