Interpolation

L'interpolation linéaire entre deux points $(x_0, y_0)$ et $(x_1, y_1)$ donne :

$f(x) \approx y_0 + \frac{y_1 - y_0}{x_1 - x_0}(x - x_0) = \frac{(x_1 - x)\,y_0 + (x - x_0)\,y_1}{x_1 - x_0}$

Erreur : $O(h^2)$ où $h = x_1 - x_0$ — exacte pour les fonctions linéaires.

C'est la méthode la plus simple : relier les points par des segments de droite. Rapide mais peut produire des angles aux points de données (non dérivable aux nœuds).

Le polynôme de Lagrange est le polynôme de degré $\leq n$ qui passe exactement par $n+1$ points $(x_0, y_0), \ldots, (x_n, y_n)$ :

$L(x) = \sum_{i=0}^{n} y_i \cdot \ell_i(x)$

où les polynômes de base de Lagrange sont :

$\ell_i(x) = \prod_{\substack{j=0 \\ j \neq i}}^{n} \frac{x - x_j}{x_i - x_j}$

Propriété : $\ell_i(x_j) = \delta_{ij}$ (vaut 1 si $i=j$, 0 sinon).

Existence et unicité : il existe un unique polynôme de degré $\leq n$ passant par $n+1$ points distincts.

Phénomène de Runge : interpoler avec un polynôme de degré élevé sur des nœuds uniformément espacés peut produire de grandes oscillations aux bords de l'intervalle — même si la fonction interpolée est parfaitement lisse.

Exemple canonique : la fonction $f(x) = \dfrac{1}{1+25x^2}$ sur $[-1, 1]$. Avec $n+1$ nœuds équidistants :

• Pour $n = 4$ : approximation acceptable
• Pour $n = 10$ : oscillations visibles aux bords
• Pour $n = 20$ : oscillations dépassant 10 en amplitude, alors que $f \leq 1$ partout

Cause mathématique : l'erreur d'interpolation est proportionnelle au produit $\prod_{i=0}^{n}(x - x_i)$. Pour des nœuds uniformes, ce produit croît très vite aux bords — les nœuds sont trop écartés là où la fonction varie le plus.

Solution — Nœuds de Chebyshev : utiliser les zéros du polynôme de Chebyshev de degré $n+1$ sur $[-1,1]$ :

$x_i = \cos\!\left(\frac{2i+1}{2(n+1)}\pi\right), \quad i = 0, 1, \ldots, n$

Ces nœuds sont plus denses aux bords qu'au centre. Ils minimisent $\max_{x \in [-1,1]}\prod|x - x_i|$, ce qui garantit la convergence de l'interpolation pour les fonctions continues.

Résultat : avec des nœuds de Chebyshev, l'interpolation polynomiale converge pour la fonction de Runge, là où les nœuds uniformes divergent.

Plutôt qu'un seul polynôme de degré élevé sur tout l'intervalle, les splines cubiques raccordent des polynômes de degré 3 sur chaque sous-intervalle $[x_i, x_{i+1}]$, avec des conditions de régularité aux nœuds.

Conditions imposées sur chaque nœud intérieur $x_i$ :

1. Continuité de $f$ : les morceaux adjacents se rejoignent
2. Continuité de $f'$ : pas d'angle (tangentes identiques des deux côtés)
3. Continuité de $f''$ : courbure continue (la spline est de classe $C^2$)

Ces $3(n-1)$ conditions intérieures, combinées aux $2(n+1)$ coefficients des $n$ polynômes cubiques (4 coefficients chacun), nécessitent 2 conditions supplémentaires aux bords.

Conditions aux bords (choix courants) :

• Spline naturelle : $S''(a) = S''(b) = 0$ — courbure nulle aux extrémités
• Spline "not-a-knot" : continuité de $f'''$ aux deux premiers et deux derniers nœuds (défaut dans NumPy/SciPy)
• Spline périodique : $S'(a) = S'(b)$ et $S''(a) = S''(b)$ — pour les données périodiques

Résolution : le système résultant est tridiagonal et se résout en $O(n)$ par l'algorithme de Thomas.

Erreur : $O(h^4)$ pour $f \in C^4[a,b]$ — même ordre que Simpson.

Avantages des splines cubiques :

• Évite complètement le phénomène de Runge
• Lisse ($C^2$) : courbe visuellement agréable sans angle ni discontinuité de courbure
• Standard industriel en CAO, animation 3D, typographie (courbes de Bézier, B-splines)

L'interpolation trouve des applications directes dans les pipelines de machine learning :

1. Resampling de séries temporelles

Les séries temporelles mesurées à des fréquences irrégulières doivent souvent être ramenées à une grille temporelle uniforme :

• Données de capteurs avec timestamps irréguliers → spline pour uniformiser
• Fusion de sources à fréquences différentes (10 Hz et 100 Hz) → rééchantillonnage
• Imputation de valeurs manquantes dans une série temporelle

2. Feature engineering

Transformer des données discrètes en features continues et lisses pour améliorer la généralisation d'un modèle :

• Encodage d'une variable ordinale (âge) en courbe de risque continue par spline
• Lissage de signaux bruités avant extraction de features
• Normalisation de courbes à longueurs variables (DTW, interpolation sur grille commune)

3. Augmentation de données

Interpoler entre des exemples d'entraînement pour créer des exemples synthétiques — technique Mixup :

$\tilde{x} = \lambda\, x_i + (1-\lambda)\, x_j, \quad \tilde{y} = \lambda\, y_i + (1-\lambda)\, y_j, \quad \lambda \sim \text{Beta}(\alpha, \alpha)$

Variante SMOTE (Synthetic Minority Over-sampling) : interpolation linéaire dans l'espace des features entre voisins proches de la classe minoritaire.

4. Encodage positionnel dans les transformers

Les embeddings positionnels peuvent être interpolés pour généraliser à des séquences de longueurs non vues à l'entraînement (RoPE, ALiBi utilisent des formes d'interpolation).