Interpolation quadratique inverse

En analyse numérique, l'interpolation quadratique inverse est un algorithme de recherche d'un zéro d'une fonction: c'est une méthode permettant de résoudre en x des équations du type f(x) = 0. L'idée est d'utiliser une interpolation quadratique afin d'approcher la fonction inverse de f. Cet algorithme est rarement utilisé seul, mais prend sa place dans la méthode de Brent.

La méthode

L'algorithme de l'interpolation quadratique inverse est donné par la relation de récurrence:

$x_{n+1}={\frac {f_{n-1}f_{n}}{(f_{n-2}-f_{n-1})(f_{n-2}-f_{n})}}x_{n-2}+{\frac {f_{n-2}f_{n}}{(f_{n-1}-f_{n-2})(f_{n-1}-f_{n})}}x_{n-1}$

${}+{\frac {f_{n-2}f_{n-1}}{(f_{n}-f_{n-2})(f_{n}-f_{n-1})}}x_{n},$

où f_k = f(x_k). Cette méthode nécessite donc trois valeurs initiales x₀, x₁ et x₂.

Explication de la méthode

On utilise les trois itérations précédentes x_n-2, x_n-1 et x_n, avec leur image, f_n-2, f_n-1 et f_n. En appliquant une Interpolation lagrangienne quadratique, on trouve l'approximation suivante de l'inverse de f

$f^{-1}(y)={\frac {(y-f_{n-1})(y-f_{n})}{(f_{n-2}-f_{n-1})(f_{n-2}-f_{n})}}x_{n-2}+{\frac {(y-f_{n-2})(y-f_{n})}{(f_{n-1}-f_{n-2})(f_{n-1}-f_{n})}}x_{n-1}$

${}+{\frac {(y-f_{n-2})(y-f_{n-1})}{(f_{n}-f_{n-2})(f_{n}-f_{n-1})}}x_{n}.$

On recherche une racine de f, donc on remplace y = f(x) = 0 dans la relation précédente et on obtient la relation souhaitée.

Comportement (analyse numérique)

Le comportement asymptotique est très bon: en général, les itérations x_n convergent rapidement vers la racine, une fois qu'elles en sont proches. Toutefois, les performances sont souvent assez pauvres si on part trop loin de la racine. Par exemple, si par malchance deux des images f_n-2, f_n-1 et f_n coïncident, les calculs via l'algorithme échouent complètement.

Comparaison avec d'autres méthodes

Comme indiqué plus haut, l'interpolation quadratique inverse est utilisée dans la méthode de Brent. Il existe d'autres liens avec d'autres méthodes:

• remplacer l'interpolation quadratique par une interpolation linéaire donne la méthode de la sécante;
• interpoler f plutôt que son inverse donne la méthode de Müller.

Références

• Cleve Moler, Numerical Computing with MATLAB, Section 4.5, Society for Industrial and Applied Mathematics (SIAM), 2004. (ISBN 0-89871-560-1).