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 :

${\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 $(t_{i})_{0\leq i\leq N}$. Dans la suite, on notera $y_{i}$ la solution approchée au temps $t_{i}$ et $y(t_{i})$ la valeur exacte.

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

$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 :

$\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 :

${\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 :

$\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 :

$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 :

$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 :

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

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

$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 :

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

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

$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 :

• Prédiction

  ${\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) :

  $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.

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

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

• Correction :

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

$r$ $b_{0,r}$ $b_{1,r}$ $b_{2,r}$ $b_{3,r}$ 0 1 1 ${\tfrac {3}{2}}$ $-{\tfrac {1}{2}}$ 2 ${\tfrac {23}{12}}$ $-{\tfrac {16}{12}}$ ${\tfrac {5}{12}}$ 3 ${\tfrac {55}{24}}$ $-{\tfrac {59}{24}}$ ${\tfrac {37}{24}}$ $-{\tfrac {9}{24}}$	$r$ $m_{0,r}$ $m_{1,r}$ $m_{2,r}$ $m_{3,r}$ 0 1 1 ${\tfrac {1}{2}}$ ${\tfrac {1}{2}}$ 2 ${\tfrac {5}{12}}$ ${\tfrac {8}{12}}$ $-{\tfrac {1}{12}}$ 3 ${\tfrac {9}{24}}$ ${\tfrac {19}{24}}$ $-{\tfrac {5}{24}}$ ${\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.

• Prédiction

  ${\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 :

  $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, 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.

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