Méthodes prédicteur-correcteur

Les méthodes prédicteur-correcteur sont des méthodes d'analyse numérique d'approximation de solutions d'équations différentielles.

Ces méthodes reposent sur le principe de l'itération, c'est-à-dire qu'une première estimation de la solution est utilisée pour calculer une seconde estimation, qui sera retenue pour l'itération suivante.

Principe général

On considère la résolution du problème :

${\displaystyle {\mathrm {d} y \over \mathrm {d} t}=f(t,y),\quad y(t_{0})=y_{0}}$

que l'on va chercher à résoudre en un ensemble discret t₀ < t₁ < ... < t_N. Comme une solution explicite n'est pas toujours disponible, les méthodes prédicteur-correcteur permettent de déterminer une solution approchée aux points ${\displaystyle (t_{i})_{0\leq i\leq N}}$. Dans la suite, on notera ${\displaystyle y_{i}}$ la solution approchée au temps ${\displaystyle t_{i}}$ et ${\displaystyle y(t_{i})}$ la valeur exacte.

Ainsi, pour une solution exacte ${\displaystyle t\mapsto y(t)}$ du problème, on a

${\displaystyle y(t_{n+1})=y(t_{n})+\int _{t_{n}}^{t_{n+1}}f(t,y(t))\mathrm {d} t.}$

Le principe d'une méthode prédicteur-correcteur consiste à faire une première approximation explicite de l'intégrale :

${\displaystyle \int _{t_{n}}^{t_{n+1}}f(t,y(t))\mathrm {d} t\approx (t_{n+1}-t_{n})F_{p}(t_{n},y_{n}),}$

d'où l'étape de prédiction :

${\displaystyle {\tilde {y}}_{n+1}=y_{n}+(t_{n+1}-t_{n})F_{p}(t_{n},y_{n}),}$

puis une deuxième approximation implicite de l'intégrale :

${\displaystyle \int _{t_{n}}^{t_{n+1}}f(t,y(t))\mathrm {d} t\approx (t_{n+1}-t_{n})F_{i}(t_{n},y_{n},t_{n+1},y_{n+1}).}$

d'où l'étape de correction, qui utilisera le prédicteur :

${\displaystyle y_{n+1}=y_{n}+(t_{n+1}-t_{n})F_{i}(t_{n},y_{n},t_{n+1},{\tilde {y}}_{n+1}).}$

Exemples

Dans la suite, on notera :

${\displaystyle f_{i}=f(t_{i},y_{i}),{\tilde {f}}_{n}=f(t_{n},{\tilde {y}}_{n})}$

Schémas à un pas

Méthode prédicteur-correcteur d'Euler-Heun

On utilise le schéma d'Euler explicite pour la prédiction :

${\displaystyle {\tilde {y}}_{n+1}=y_{n}+(t_{n+1}-t_{n})f_{n},}$

puis la méthode du point milieu pour la correction :

${\displaystyle y_{n+1}=y_{n}+{\frac {(t_{n+1}-t_{n})}{2}}\left[f_{n}+{\tilde {f}}_{n+1}\right].}$

Méthode RK2

On utilise le schéma d'Euler explicite pour la prédiction :

${\displaystyle {\tilde {y}}_{n+1}=y_{n}+(t_{n+1}-t_{n})f_{n},}$

puis la méthode des trapèzes pour la correction :

${\displaystyle y_{n+1}=y_{n}+{\frac {(t_{n+1}-t_{n})}{2}}\left[f(t_{n},{\tilde {y}}_{n+1})+{\tilde {f}}_{n+1}\right].}$

On reconnait alors la méthode de Runge-Kutta d'ordre 2.

Schémas multi-pas

Méthode prédicteur-correcteur de Milne

En 1970, pour éviter des problèmes d'instabilité, William Edmund Milne utilise le schéma prédicteur-correcteur suivant ^[1],[2]:

• Prédiction

  ${\displaystyle {\tilde {y}}_{n+1}=y_{n-4}+{\frac {4(t_{n+1}-t_{n})}{3}}(2f_{n-3}-f_{n-2}+2f_{n-1}),\ \forall n\geqslant 4}$

• Correction (basée sur la méthode de Simpson) :

  ${\displaystyle y_{n+1}=y_{i-2}+{\frac {(t_{n+1}-t_{n})}{3}}({\tilde {f}}_{n}+4{\tilde {f}}_{n-1}+{\tilde {f}}_{n-2}),\ \forall n\geqslant 4}$

Les premiers pas sont calculés par des méthodes plus simples mais d'ordre élevé, comme une méthode RK4^[3].

Méthode d'Adams–Bashford–Moulton

Le schéma de prédiction repose sur une méthode d'Adams-Bashforth (explicite) et la correction, sur une méthode d'Adams-Moulton (implicite).

• Prédiction

  ${\displaystyle {\tilde {y}}_{n+1}=y_{n}+(t_{n+1}-t_{n})\sum _{i=0}^{r}f_{n-i}b_{i,r}}$

• Correction :

  ${\displaystyle y_{n+1}=y_{n}+(t_{n+1}-t_{n})\sum _{i=0}^{r}f_{n+1-i}m_{i+1,r}}$

${\displaystyle r}$ ${\displaystyle b_{0,r}}$ ${\displaystyle b_{1,r}}$ ${\displaystyle b_{2,r}}$ ${\displaystyle b_{3,r}}$ 0 1 1 ${\displaystyle {\tfrac {3}{2}}}$ ${\displaystyle -{\tfrac {1}{2}}}$ 2 ${\displaystyle {\tfrac {23}{12}}}$ ${\displaystyle -{\tfrac {16}{12}}}$ ${\displaystyle {\tfrac {5}{12}}}$ 3 ${\displaystyle {\tfrac {55}{24}}}$ ${\displaystyle -{\tfrac {59}{24}}}$ ${\displaystyle {\tfrac {37}{24}}}$ ${\displaystyle -{\tfrac {9}{24}}}$

${\displaystyle r}$ ${\displaystyle m_{0,r}}$ ${\displaystyle m_{1,r}}$ ${\displaystyle m_{2,r}}$ ${\displaystyle m_{3,r}}$ 0 1 1 ${\displaystyle {\tfrac {1}{2}}}$ ${\displaystyle {\tfrac {1}{2}}}$ 2 ${\displaystyle {\tfrac {5}{12}}}$ ${\displaystyle {\tfrac {8}{12}}}$ ${\displaystyle -{\tfrac {1}{12}}}$ 3 ${\displaystyle {\tfrac {9}{24}}}$ ${\displaystyle {\tfrac {19}{24}}}$ ${\displaystyle -{\tfrac {5}{24}}}$ ${\displaystyle {\tfrac {1}{24}}}$

Coefficients des schémas d'Adams-Bashford

Coefficients des schémas d'Adams-Moulton

Méthode de Hamming

Ce schéma est dérivé de celui de Milne, mais Hamming, en 1959, a remplacé le correcteur par une règle stable^[4].

• Prédiction

  ${\displaystyle {\tilde {y}}_{n}=y_{n-4}+{\frac {4(t_{n+1}-t_{n})}{3}}(2f_{n-3}-f_{n-2}+2f_{n-1}),\ \forall n\geqslant 4}$

• Correction :

  ${\displaystyle y_{n+1}={\frac {1}{8}}(9y_{n}-y_{n-2})+{\frac {3(t_{n+1}-t_{n})}{8}}(-{\tilde {f}}_{n-1}+2{\tilde {f}}_{n}-{\tilde {f}}_{n+1}),\ \forall n\geqslant 4}$

Intérêts

Chase a mis en évidence que le choix du correcteur est peut-être plus impactant sur la stabilité de la méthode que celui du prédicteur^[5], du moins dans la limite d'un pas d'intégration petit. Dans le cas général, les choix du prédicteur et du correcteur ont tous les deux une influence notable sur la stabilité de la méthode.

Dans le cas général, les méthodes de Runge-Kutta sont préférées aux schémas prédicteur-correcteur pour leur adaptabilité et leur mise en œuvre plus simple car totalement explicite. Cependant, pour des méthodes du même ordre de consistance, les méthodes de Runge-Kutta exigent plus d'évaluations de fonctions. Ainsi, dans les cas où on sait que la solution de l'équation n'est pas sujette à de brusques variations de la dérivée, on prendra une méthode de type prédicteur-correcteur mais, si le pas doit être adapté plus précisément, on préfèrera une méthode de Runge-Kutta.

Références

Articles connexes

• Méthode leapfrog
• Méthode de Runge-Kutta
• Résolution numérique des équations différentielles

Liens externes

• (en) Eric W. Weisstein, « Runge-Kutta Method », sur MathWorld
• (en) Eric W. Weisstein, « Milne's Method », sur MathWorld
• (en) Eric W. Weisstein, « Predictor-Corrector Methods », sur MathWorld

v · m Analyse numérique
Recherche de zéro	Méthode de Josephy-Newton Méthode de la sécante Méthode de Newton Point fixe
Transformations de matrice	Matrice de Hessenberg Décomposition LU Factorisation de Cholesky
Résolutions de systèmes	Méthode de Gauss-Seidel Méthode de surrelaxation successive (SOR) Méthode de Jacobi Décomposition QR Décomposition LU
Intégration numérique	Méthode du point médian Méthode des trapèzes Méthode de Simpson Méthodes de quadrature de Gauss Formule de Newton-Cotes Méthode de Romberg Méthode de Monte-Carlo
Équations différentielles	Méthode d'Euler (et semi-implicite) Méthodes de Runge-Kutta Intégration de Verlet Leapfrog Méthode multi-pas linéaire (en) (Adams-Bashforth, backward differentiation formula (en))
Interpolation numérique	Spline Interpolation polynomiale Interpolation lagrangienne Interpolation d'Hermite Suite de polynômes orthogonaux

• Portail de l'analyse