Quand l'interpolation spline cubique est-elle meilleure qu'un polynôme interpolateur?

9

L'intrigue suivante est une légère variation d'un exemple dans un manuel. L'auteur a utilisé cet exemple pour illustrer qu'un polynôme interpolant sur des échantillons également espacés a de grandes oscillations près des extrémités de l'intervalle d'interpolation. Bien sûr, l'interpolation spline cubique donne une bonne approximation sur tout l'intervalle. Pendant des années, j'ai pensé que l'interpolation polynomiale d'ordre élevé sur des échantillons également espacés devait être évitée pour la raison illustrée ici.

entrez la description de l'image ici

Cependant, j'ai récemment trouvé de nombreux exemples de signaux à bande limitée où un polynôme interpolant d'ordre élevé donne moins d'erreur d'approximation que l'interpolation cubique-spline. Typiquement, un polynôme interpolant est plus précis sur tout l'intervalle d'interpolation lorsque la fréquence d'échantillonnage est suffisamment élevée. Cela semble valable lorsque les échantillons sont également espacés avec une fréquence d'échantillonnage au moins 3 fois supérieure à la fréquence de Nyquist du signal. De plus, l'avantage par rapport à l'interpolation spline cubique s'améliore à mesure que (fréquence d'échantillonnage) / (fréquence de Nyquist) augmente.

À titre d'exemple, je compare l'interpolation spline cubique avec un polynôme interpolateur pour une onde sinusoïdale avec une fréquence de Nyquist de 2 Hz et une fréquence d'échantillonnage de 6,5 Hz. Entre les points d'échantillonnage, le polynôme interpolateur a exactement la même apparence que le signal réel. entrez la description de l'image ici


Ci-dessous, je compare l'erreur dans les deux approximations. Comme dans le premier exemple, l'interpolation polynomiale est pire au début et à la fin de l'intervalle d'échantillonnage. Cependant, le polynôme interpolateur a moins d'erreur qu'une spline cubique sur tout l'intervalle d'échantillonnage. Le polynôme interpolateur a également moins d'erreur lors de l'extrapolation sur un petit intervalle. Ai-je découvert un fait bien connu? Si oui, où puis-je lire à ce sujet?

entrez la description de l'image ici

Ted Ersek
la source
Vous rapprochez une formule ou des données? Étant donné une formule, comme vous l'avez, vous pouvez toujours utiliser des splines plus avancées où les dérivées d'ordre supérieur sont également prises en compte. Vous devez également vérifier le fait que la spline cubique minimise une certaine fonction "énergie". Regardez wikipedia en.wikipedia.org/wiki/Spline_interpolation . Donc, dans un certain sens, la minimisation de la courbure, vous ne pouvez pas faire mieux. Une autre interprétation est que des splines cubiques ont été / sont utilisées pour l'ajustement; pas approximatif. "Ajuster" implique une certaine métrique à optimiser.
rrogers
@rrogers, je pensais qu'un polynôme interpolant serait une meilleure approche quand on veut estimer la fonction à partir d'échantillons mesurés et que la bande passante du signal est connue pour être inférieure à 1/6 du taux d'échantillonnage. Il
Ted Ersek
@TedErsek: Une considération qualitative: par leur nature, les fonctions polynomiales divergent vers tant que variable en abscisse . Cet effet est exacerbé lorsque l'ordre polynomial augmente. Notez que dans votre premier exemple, le signal à approximer se désintègre à zéro vers la fin de l'intervalle d'interpolation; cela est incompatible avec le comportement asymptotique de l'interpolant. Le deuxième tracé a une pente raide et des valeurs non nulles près des bords de l'intervalle, vous obtenez donc une meilleure approximation. Pas très théorique ici, juste une observation. ±
Jason R
@TedErsek En guise de pratique, abordant le commentaire de Ted Ersek; avez-vous essayé l'approximation polynomiale rationnelle. BTW: J'ai la copie gratuite d'un programme d'estimation de formule de courbe d'il y a un an qui fait vraiment du bien. Le programme est passé de la version bêta au paiement, je n'ai donc pas la version actuelle.
rrogers
@JasonR Je voulais vous adresser mon dernier commentaire. De retour sur le sujet, dans tous les cas, il y a en.wikipedia.org/wiki/Chebyshev_polynomials qui fournissent des approximations d'erreur uniforme (min / max) dans les polynômes si vous connaissez la fonction. Mais si vous connaissez la fonction, vous pouvez toujours synthétiser un "filtre adapté".
rrogers

Réponses:

4

Le phénomène discuté est le phénomène de Runge .

La valeur absolue maximale de la ième dérivée de est . Pour la fonction de Runge la valeur absolue maximale du dérivé e (même) est oùdésigne factorielle. C'est une croissance beaucoup plus rapide. Ce n'est que si les dérivées croissent trop rapidement en augmentant , qu'il est possible que l'erreur d'interpolation diverge lorsque l'ordre d'interpolation augmente. L'exponentielle en n'est pas encore trop rapide. Jetez un œil à: James F. Epperson, sur l'exemple de Runge , The American Mathematical Monthly , vol. 94, 1987, pp. 329-341.sin ( ω t ) ω n 1nsin(ωt)ωn n5nn! ,n! nn125t2+1n5nn!,n!nn

Si une fonction n'a que des dérivées continues, alors l'approche concurrente, l'interpolation spline polynomiale par morceaux converge toujours si un petit nombre fixe de ses premières dérivées est limité sur l'intervalle d'intérêt, voir l'article de Wikipedia sur l'interpolation linéaire comme exemple.

Si les deux méthodes convergent, l'interpolation polynomiale (non par morceaux) a l'avantage d'un degré polynomial plus élevé si de nombreux échantillons sont utilisés et peut fournir une meilleure approximation, comme vous l'avez vu dans votre exemple sinus. Vous pouvez également être intéressé par LN Trefethen, Deux résultats sur l'interpolation polynomiale en points également espacés , Journal of Approximation Theory Volume 65, Numéro 3, juin 1991, Pages 247-260. Citation:

[...] dans l'interpolation à bande limitée de fonctions exponentielles complexes l'erreur diminue à en si et seulement si est suffisamment petit pour fournir au moins six points par longueur d'onde.0 n αeiαx(αR),0nα

Vous avez 6,5 échantillons par longueur d'onde.

Olli Niemitalo
la source