Spline

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Icône de paronymie Cet article possède un paronyme, voir Spleen.
Exemple de spline quadratique.

En mathématique 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 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.

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 par lesquels devait nécessairement passer le contour de la pièce (dessin technique), ou nœuds. Le travail du dessinateur industriel consistait à relier les 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, 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éfinition[modifier | modifier le code]

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ômes 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 poins 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 3e 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.

  • 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[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[2] :

  • l'évaluation des paramètres de la spline peuvent diverger si la pente entre deux nœuds est beaucoup plus grande que 1 ;
  • 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 ;
  • 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 . 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 S 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 C0, C1 et C2 s'expriment de la façon suivante :

  • C0 : chacun des n-1 polynômes passe par deux nœuds, soit 2n-2 conditions ;
  • C1 : les polynômes ont même dérivée première aux n-2 nœuds de jonction, soit n-2 conditions ;
  • C2 : et ces polynômes ont 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.

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, The 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 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).

Principe du lissage par spline : des ressorts lient les nœuds à la réglette qui décrit la courbe lissée ; la forme de celle-ci minimise l'énergie totale de déformation.

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 valeurs connues (nœuds), dont les abscisses sont strictement croissantes, que l'on souhaite lisser. On relie ces nœuds à une réglette flexible de raideur par des ressorts ayant tous la même raideur . 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 s'allonge d'une longueur . L'énergie d'allongement d'un ressort élastique est proportionnelle au carré de l'allongement ; l'énergie d'allongement du ressort n° vaut :

est la raideur du ressort.

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

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

É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 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 et vaut :

est la raideur de courbure élastique de la cerce.

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

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 :

est le rapport entre la raideur de la réglette et la raideur des ressorts.

Spline cubique de lissage[modifier | modifier le code]

Trouver la fonction qui minimise 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 valeurs (ou nœuds), il y a intervalles et donc polynômes du troisième degré définis chacun par quatre paramètres, soit au total 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 :

  •  : chacun des polynôme est jointif au suivant, soit conditions ;
  •  : les polynômes ont même dérivée première aux nœuds, soit conditions ;
  •  : et ces polynômes ont même dérivée seconde aux nœuds, soit conditions.

Soit : conditions.

La minimisation de , où est fixé, correspond à conditions. Soit donc au total conditions. Il manque deux conditions pour déterminer les inconnues. On impose que les dérivées secondes aux extrémités soient nulles. L'ensemble de ces conditions conduit à équations linéaires à inconnues.

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.

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 . 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 , 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  :

  • si , 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 , 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 , tel que :

, c'est-à-dire :
, où varie entre 0 (exclu) et 1.
correspond à  : on obtient la spline naturelle passant par les nœuds ;
correspond à  : 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 sur 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° 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 pour le nœud n° 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œuds :

l'indicateur

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 .

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 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 sans effectue le calcul des splines cubiques de lissage résultant de l'élimination successive de chacun des nœuds. On lira l'algorithme de calcul détaillé de dans la référence[3].

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. Les logiciels mettent 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. Voir le document en lien externe.

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

  1. Pierre Bézier, « Courbes et surfaces pour la CFAO », Techniques de l'ingénieur Applications des mathématiques, vol. TIB102DUO, no a1440,‎ (lire en ligne).
  2. a, b et c Gianluca Bontempi, Souhaib Ben Taieb, Catharina Olsen, Département Informatique, Université libre de Bruxelles [1].
  3. a et b E. Moulines, « Étude de cas de régression non paramétrique » [PDF].

Voir aussi[modifier | modifier le code]

Sur les autres projets Wikimedia :

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • Gilbert Demengel et Jean-Pierre Pouget, Modèles de Bézier, des B-splines et des NURBS, Ellipses, , 286 p. (ISBN 978-2-72989-806-9)
  • Michelle Schatzman, Analyse numérique : : Approche mathématique, Paris, Dunod, coll. « Sciences Sup », , 480 p. (ISBN 9782100487325).

Liens externes[modifier | modifier le code]