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:
où fk = f(xk). Cette méthode nécessite donc trois valeurs initiales x0, x1 et x2.
Explication de la méthode
On utilise les trois itérations précédentes xn-2, xn-1 et xn, avec leur image, fn-2, fn-1 et fn. En appliquant une Interpolation lagrangienne quadratique, on trouve l'approximation suivante de l'inverse de f
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 xn 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 fn-2, fn-1 et fn 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).
Portail de l'analyse