Spline
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é {{#ifeq:1|0|[splin]|[[Alphabet phonétique international|Modèle:Nobr]]}}, à 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.
- 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 {{#ifeq:1|0|[splaɪn]|[[Alphabet phonétique international|Modèle:Nobr]]}}, ce qui le distingue de « Modèle:Page h' » {{#ifeq:1|0|[spli:n]|[[Alphabet phonétique international|Modèle:Nobr]]}}. En français, on prononce le mot tel qu'il s'écrit : {{#ifeq:1|0|[splin]|[[Alphabet phonétique international|Modèle:Nobr]]}}.
Étymologie
Pierre Bézier écrit<ref>Modèle:Article.</ref> : Modèle:Citation bloc
The Oxford English Dictionnary 1989 donne les définitions suivantes pour le mot spline : Modèle:Citation étrangère bloc
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 Modèle:Math. 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 Modèle: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). Modèle:Gallery
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.
- Modèle:Math est la continuité minimum : les polynômes successifs passent bien par les points de jonction ;
- Modèle:Math 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 ;
- Modèle:Math 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 Modèle:Math, Modèle:Math et Modèle:Math 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 Modèle:Math. Il y a n-1 intervalles. Nous voulons donc déterminer les paramètres de n-1 polynômes du troisième degré, Modèle:Math.
Chaque polynôme Modèle:Mvar a une équation de la forme :
- <math>S = a_0 x^3 + a_1 x^2 + a_2 x + a_3</math>
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 Modèle:Math, Modèle:Math et Modèle:Math s'expriment de la façon suivante :
- Modèle:Math : chacun des n-1 polynômes passe par deux nœuds, soit 2n-2 conditions ;
- Modèle:Math : les polynômes ont les mêmes dérivées premières aux n-2 nœuds de jonction, soit n-2 conditions ;
- Modèle:Math : 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 Modèle:Mvar et Modèle:Mvar les abscisses et ordonnées de Modèle:Mvar nœuds, les abscisses étant classées par ordre croissant.
- 1. Calculer la matrice colonne Modèle:Math des largeurs des Modèle:Math intervalles entre nœuds :
- <math>\mathbf{h}_i = X_{i+1} - X_i</math>, pour Modèle:Mvar de 1 à Modèle:Math.
- 2. Calculer la matrice colonne Modèle:Math des Modèle:Math dérivées secondes aux nœuds :
- 2.1. Pour les nœuds 2 à Modèle:Math :
- <math>\mathbf{F}_i = \frac {Y_{i+1} - Y_i}{\mathbf{h}_i} - \frac {Y_i - Y_{i-1}}{\mathbf{h}_{i-1}}</math>, pour Modèle:Mvar de 2 à Modèle:Math.
- 2.2. Il faut de plus valoriser les dérivées secondes aux extrémités, Modèle:Math et Modèle:Math.
- Si l'on pose Modèle:Math et Modèle:Math, on obtient une spline naturelle ;
- si l'on possède des informations sur les extrémités, on affecte à Modèle:Math et/ou à Modèle:Math la valeur ad hoc.
- 2.2. Il faut de plus valoriser les dérivées secondes aux extrémités, Modèle:Math et Modèle:Math.
- 3. Construire la matrice carrée Modèle:Math, de dimensions Modèle:Math, telle que, Modèle:Mvar désigne l'indice des lignes et Modèle:Mvar celui des colonnes :
- 3.1 Mettre tous les éléments de la matrice Modèle:Math à 0.
- 3.2 Sur la première ligne, seul le premier élément n'est pas nul : Modèle:Math.
- 3.3 Sur la dernière ligne, seul le dernier élément n'est pas nul : Modèle:Math.
- 3.4 La sous-matrice de Modèle:Math de dimension Modèle:Math 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 :
- <math>\mathbf{R}_{i,i} = \frac{h_{i-1} + h_i}{3}</math> pour Modèle:Math.
- La diagonale supérieure vaut :
- <math>\mathbf{R}_{i,{i+1}} =\frac{h_i}{6}</math> pour Modèle:Math.
- La diagonale inférieure vaut :
- <math>\mathbf{R}_{i,{i-1}} =\frac{h_{i-1}}{6}</math> pour Modèle:Math.
- 4. Calculer la matrice colonne Modèle:Math de dimension Modèle:Mvar, telle que :
- <math>\mathbf{M} = \mathbf{R}^{-1} \times \mathbf{F}</math>.
- 5. Calculer les matrices colonnes Modèle:Math et Modèle:Math, de dimensions Modèle:Math, contenant respectivement les constantes d'intégration d'ordre 1 et 2 des Modèle:Math polynômes, de la façon suivante :
- Pour Modèle:Mvar de 1 à Modèle:Math :
- <math>\mathbf{C}_i = \frac{Y_{i+1} - Y_i}{\mathbf{h}_i} - \frac{\mathbf{h}_i}{6}(\mathbf{M}_{i+1} - \mathbf{M}_i)</math>
- <math>\mathbf{C'}_i = Y_i - \mathrm{M}_i \frac{\mathbf{h}_i^2}{6}</math>
- 6. Calcul d'une valeur d’interpolation pour une abscisse Modèle:Mvar située dans l'intervalle Modèle:Mvar, entre les nœuds d'abscisses Modèle:Mvark et Modèle:Math (avec Modèle:Mvar de 1 à Modèle:Math) :
- <math>\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}</math>
Exemple
Cet exemple présente l'approximation de la courbe Modèle:Math par une spline cubique naturelle pour laquelle on donne les cinq valeurs suivantes (5 nœuds) de la fonction :
- <math>n=5</math>
- <math>\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}</math>
- <math>\mathbf{h} = \begin{bmatrix} 0{,}5 \\
0{,}5 \\
0{,}5 \\
0{,}5 \\
\end{bmatrix} \text{ ; }</math><math>
\mathbf{F} = \left[ \begin{array}{r} 0{,}0000 \\
-0{,}2348 \\
-0{,}4120 \\
-0{,}4884 \\
0{,}0000 \\
\end{array} \right] \text{ ; }</math><math>
\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{ ; }</math>
- <math>\mathbf{M} = \left[ \begin{array}{r} 0{,}0000 \\
-0{,}5061 \\
-0{,}7928 \\
-1{,}2671 \\
0{,}0000 \\
\end{array} \right] \text{ ; }</math><math>
\mathbf{C} = \left[ \begin{array}{r} 1{,}0010 \\
0{,}7480 \\
0{,}3516 \\
-0{,}2820\\
\end{array} \right] \text{ ; }</math><math>
\mathbf{C'}= \left[ \begin{array}{r} 0{,}0000 \\
0{,}5005 \\
0{,}8745 \\
1{,}0503 \\
\end{array} \right]</math>
Commentaire sur l'exemple : La fonction <math>sin(i)</math> est bien représentée par son approximation par une spline naturelle à gauche du graphique parce que la dérivée seconde de <math>sin(i)</math> est bien nulle pour <math>i = 0</math>, 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 <math>sin(i)</math> n'est pas nulle pour <math>X_5 = 2{,}0</math> (elle vaut <math>-0,035</math>), 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 <math>f()</math> dont on connaît les valeurs aux nœuds <math>X_i</math>, l'expression générale pour la spline cubique de classe C2 en un point <math>x</math> dans <math>[X_{i-1}, X_i]</math> est la suivante :
- <math>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_ih_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)</math>
où
- <math>f(X_i^{})</math> est la valeur de <math>f()</math> au nœud i,
- <math>h_i^{}=X_i\;\text{-}\;X_{i-1}</math>,
- <math>z_i=f^{\prime\prime}(X_i)</math> est la dérivée seconde de <math>f()</math> au nœud i.
On vérifie facilement que <math>S_i(X_{i-1})=f(X_{i-1})</math> et <math>S_i(X_i)=f(X_i)</math>.
Mise en œuvre dans des logiciels
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
Utilisation de splines pour le lissage
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 Modèle:Page h' 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
Soit Modèle:Mvar valeurs connues (nœuds), dont les abscisses sont strictement croissantes, que l'on souhaite lisser. On relie ces Modèle:Mvar nœuds à une réglette flexible de raideur Modèle:Mvar par des ressorts ayant tous la même raideur Modèle:Mvar. 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
Chaque ressort Modèle:Mvar s'allonge d'une longueur Modèle:Mvar. L'énergie d'allongement d'un ressort élastique est proportionnelle au carré de l'allongement ; l'énergie d'allongement du ressort no Modèle:Mvar vaut :
- <math>w_i = ke_i^2</math> où Modèle:Mvar est la raideur du ressort.
L'énergie totale d'allongement des ressorts est la somme des énergies d'allongement des Modèle:Mvar ressorts :
- <math>W_R = \sum w_i= \sum k e_i^2</math> (en supposant que la raideur de tous les ressorts est identique et égale à Modèle:Mvar).
Énergie de déformation de la réglette
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 Modèle:Math 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 Modèle:Mvar et Modèle:Math vaut :
- <math>dW_C = r s(x)^2 dx</math> où Modèle:Mvar est la raideur de courbure élastique de la cerce.
L'énergie de déformation pour toute la réglette vaut :
- <math>W_C = \int r s(x)^2\,\mathrm{d}x</math> si l'on suppose qu'elle présente une raideur constante sur toute sa longueur.
Condition sur la forme prise par la réglette
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 :
- <math>W(s, \lambda) = \sum e_i^2 + \lambda \int s(x)^2dx</math>
- où Modèle:Mvar est le rapport entre la raideur Modèle:Mvar de la réglette et la raideur Modèle:Mvar des ressorts.
Spline cubique de lissage
Trouver la fonction Modèle:Mvar qui minimise Modèle:Math pour Modèle:Mvar 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 Modèle:Mvar valeurs (ou nœuds), il y a Modèle:Math intervalles et donc Modèle:Math polynômes du troisième degré définis chacun par quatre paramètres, soit au total Modèle:Math 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 :
- Modèle:Math : chacun des Modèle:Math polynôme est jointif au suivant, soit Modèle:Math conditions ;
- Modèle:Math : les polynômes ont même dérivée première aux Modèle:Math jonctions, soit Modèle:Math conditions ;
- Modèle:Math : et ces polynômes ont même dérivée seconde aux Modèle:Math jonctions, soit Modèle:Math conditions.
Soit Modèle:Math conditions.
La minimisation de Modèle:Math, où Modèle:Mvar est fixé, correspond à Modèle:Mvar conditions. Soit donc au total Modèle:Math conditions. Il manque deux conditions pour déterminer les Modèle:Math inconnues. On impose que les dérivées secondes aux extrémités soient nulles. L'ensemble de ces conditions conduit à Modèle:Math équations linéaires à Modèle:Math 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
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<ref name=Moulines>Modèle:Lien web.</ref>.
- Soit Modèle:Mvar et Modèle:Mvar les abscisses et ordonnées de Modèle:Mvar nœuds, les abscisses étant classées par ordre croissant Modèle:Math.
- 1. Calculer la matrice colonne h Modèle:Math Modèle:Math intervalles entre nœuds :
- <math>\mathbf{h}_i = X_{i+1} - X_i</math>, pour Modèle:Mvar de 1 à Modèle:Math.
- 2. Construire la matrice tridiagonale Modèle:Math (Modèle:Math) telle que toutes les valeurs de la matrice sont nulles, sauf :
- La diagonale centrale :
- <math>\mathbf{Q}_{i,{i-1}}=\frac{1}{h_{i-1}}+\frac{1}{h_i}</math>, pour Modèle:Math à Modèle:Math ;
- La diagonale supérieure :
- <math>\mathbf{Q}_{i,i}=-\frac{1}{h_i}</math>, pour Modèle:Math à Modèle:Math ;
- La diagonale inférieure :
- <math>\mathbf{Q}_{i,{i-2}}=-\frac{1}{h_{i-1}}</math>, pour Modèle:Math à Modèle:Mvar ;
- 3. Construire la matrice carrée tridiagonale Modèle:Math (Modèle:Math) telle que toutes les valeurs de la matrice sont nulles, sauf :
- La diagonale principale :
- <math>\mathbf{R}_{i,i}=\frac{h_i+h_{i+1}}{3}</math>, pour Modèle:Math à Modèle:Math ;
- La diagonale supérieure :
- <math>\mathbf{R}{i,{i+1}}=-\frac{h_i}{6}</math> pour Modèle:Math à Modèle:Math ;
- La diagonale inférieure :
- <math>\mathbf{R}{i,{i-1}}=-\frac{h_{i-1}}{6}</math> pour Modèle:Math à Modèle:Math ;
- 4. Calculer la matrice carrée Modèle:Math (Modèle:Math) :
- <math>\mathbf{K} = \mathbf{Q}\mathbf{R}^{-1}\mathbf{Q}^t</math>;
- 5. Soit <math>\mathbf{I}</math> la matrice unitaire Modèle:Math et <math>\lambda</math> le paramètre de lissage.
- On obtient les ordonnées Modèle:Math de la spline de lissage en chacun des Modèle:Mvar nœud d'abscisse Modèle:Math et d'ordonnée Modèle:Math pour la valeur <math>\lambda</math> du paramètre de lissage par :
- <math>\mathbf{s} = (\mathbf{I}+\lambda\mathbf{K})^{-1}\mathbf{Y}</math>.
- 6. On peut interpoler la valeur de la spline de lissage pour toute abscisse comprise entre les nœuds extrêmes Modèle:Math et Modèle:Math en appliquant l'algorithme d'interpolation des splines aux points d'abscisse Modèle:Math et d'ordonnée Modèle:Math.
Exemple :
Cet exemple présente le lissage des quatre nœuds de coordonnées Modèle:Math, figurés en rouge dans le graphique ci-dessus, par une spline cubique naturelle avec le paramètre de lissage Modèle:Math.
- <math>\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}</math> ;
- <math>\mathbf{h} = \begin{bmatrix} 1{,}0 \\
2{,}0 \\
2{,}0 \\
\end{bmatrix} \text{ ; }</math><math> \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{ ; }</math><math> \mathbf{R} = \begin{bmatrix}\begin{array}{rr}
1{,}0000 & -0{,}1667 \\
-0{,}1667 & 1{,}3333 \\
\end{array} \end{bmatrix}</math> ;
- <math>\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}</math> ;
- Modèle:Math étant la matrice unité Modèle:Math et avec le paramètre Modèle:Mvar, on calcule :
- <math>(\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 : }</math><math>(\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}</math>.
- d'où l'on calcule <math>\mathbf{s} = (\mathbf{I} + \lambda \mathbf{K})^{-1}\mathbf{Y}</math>
Paramètre de lissage
On suppose généralement que les ressorts qui tirent la cerce ont tous la même raideur Modèle:Mvar. 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 Modèle:Mvar, Le paramètre de lissage, noté souvent Modèle:Mvar, exprime le rapport entre la raideur élastique de la réglette et celle des ressorts. Modèle:Mvar peut varier entre 0 et Modèle:Math :
- si Modèle:Math, 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 Modèle:Mvar tend vers Modèle:Math, 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.
Pour mieux apprécier l'intensité du lissage, on utilise souvent le paramètre Modèle:Mvar, tel que :
- <math>p=\frac{1}{\lambda+1}</math>, c'est-à-dire :
- <math>\lambda=\frac{1-p}{p}</math>, où Modèle:Mvar varie entre 0 (exclu) et 1.
- Modèle:Math correspond à Modèle:Math : on obtient la spline naturelle passant par les nœuds ;
- Modèle:Math correspond à Modèle:Math : la spline obtenue tend vers la droite de régression.
Optimisation du paramètre de lissage
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 no Modèle:Mvar de la série des mesures et déterminons la spline de lissage de paramètre Modèle:Mvar avec ce nœud exclu du calcul. L'écart Modèle:Mvar pour le nœud no Modèle:Mvar 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 Modèle:Mvar, pour les Modèle:Mvar nœuds :
- l'indicateur <math>\sum \frac{\epsilon_i^2}{n}</math>
est une approximation de la variance de la prévision par spline de lissage sous condition du paramètre Modèle:Mvar. On appelle cet indicateur score de validation croisée Modèle:Math.
En réitérant cette procédure pour plusieurs valeurs de Modèle:Mvar, on peut rechercher la valeur du paramètre de lissage qui minimise ce score de validation croisée. Il n'est pas garanti que Modèle:Math 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 Modèle:Math sans effectuer le calcul des splines cubiques de lissage.
Calcul pratique des splines
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.
Modèle:Lien donne un algorithme qui utilise la factorisation de Cholesky pour réduire la taille des calculs.
Notes et références
Voir aussi
Articles connexes
Bibliographie (splines, B-splines, Dm-splines...)
- 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, Modèle:ISBN, EDP Sciences, 2019.
- Modèle:Ouvrage
- Modèle:Ouvrage.
Liens externes
- {{#invoke:Langue|indicationDeLangue}} 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 ;
- Modèle:Article ;
- Modèle:Lien web ;
- Modèle:Lien web.
.png){kind=link}
