vignette|Exemple de spline quadratique.
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é , à 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
L'origine historique des splines se trouve dans la conception industrielle.
vignette|Spline ou cerce. 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
Prononciation
Spline est un mot anglais qui, dans cette langue, se prononce , ce qui le distingue de « » . En français, on prononce le mot tel qu'il s'écrit : .
Étymologie
Pierre Bézier écrit. :
The Oxford English Dictionnary 1989 donne les définitions suivantes pour le mot spline :
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 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 Soit une série de points de donnée, ou nœuds, de coordonnées . 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 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 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).
Continuité de la spline 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. est la continuité minimum : les polynômes successifs passent bien par les points de jonction ; 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 ; 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 , et conduit aux splines cubiques.
Spline d'interpolation 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 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
Considérons n nœuds de coordonnées . Il y a n-1 intervalles. Nous voulons donc déterminer les paramètres de n-1 polynômes du troisième degré, .
Chaque polynôme a une équation de la forme :
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 , et s'expriment de la façon suivante : : chacun des n-1 polynômes passe par deux nœuds, soit 2n-2 conditions ; : les polynômes ont les mêmes dérivées premières aux n-2 nœuds de jonction, soit n-2 conditions ; : 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 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.
Soit et les abscisses et ordonnées de nœuds, les abscisses étant classées par ordre croissant.
1. Calculer la matrice colonne des largeurs des intervalles entre nœuds :
, pour de 1 à .
2. Calculer la matrice colonne des dérivées secondes aux nœuds :
2.1. Pour les nœuds 2 à :
, pour de 2 à .
2.2. Il faut de plus valoriser les dérivées secondes aux extrémités, et . Si l'on pose et , on obtient une spline naturelle ; si l'on possède des informations sur les extrémités, on affecte à et/ou à la valeur ad hoc.
3. Construire la matrice carrée , de dimensions , telle que, désigne l'indice des lignes et celui des colonnes : 3.1 Mettre tous les éléments de la matrice à 0. 3.2 Sur la première ligne, seul le premier élément n'est pas nul : . 3.3 Sur la dernière ligne, seul le dernier élément n'est pas nul : .
3.4 La sous-matrice de de dimension 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 : pour .
La diagonale supérieure vaut : pour .
La diagonale inférieure vaut : pour .
4. Calculer la matrice colonne de dimension , telle que :
.
5. Calculer les matrices colonnes et , de dimensions , contenant respectivement les constantes d'intégration d'ordre 1 et 2 des polynômes, de la façon suivante :
Pour de 1 à :
6. Calcul d'une valeur d’interpolation pour une abscisse située dans l'intervalle , entre les nœuds d'abscisses et (avec de 1 à ) :
Exemple
Cet exemple présente l'approximation de la courbe par une spline cubique naturelle pour laquelle on donne les cinq valeurs suivantes (5 nœuds) de la fonction :
Commentaire sur l'exemple : La fonction est bien représentée par son approximation par une spline naturelle à gauche du graphique parce que la dérivée seconde de est bien nulle pour , 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 n'est pas nulle pour (elle vaut ), 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 Pour une fonction dont on connaît les valeurs aux nœuds , l'expression générale pour la spline cubique de classe C2 en un point dans est la suivante :
où est la valeur de au nœud i, , est la dérivée seconde de au nœud i.
On vérifie facilement que et .
Mise en œuvre dans des logiciels
vignette|B-splines (courbes de Bézier) utilisées dans Inkscape.