Predictor–corrector method

In mathematics, particularly numerical analysis, a predictor-corrector method is an algorithm that proceeds in two steps. First, the prediction step calculates a rough approximation of the desired quantity. Second, the corrector step refines the initial approximation using another means.

Example

In approximating the solution to a first-order ordinary differential equation, suppose one knows the solution points $y_{0}$ and $y_{1}$ at times $t_{0}$ and $t_{1}$. By fitting a cubic polynomial to the points and their derivatives (gotten through the differential equation), one can predict a point ${\tilde {y}}_{2}$ by extrapolating to a future time $t_{2}$. Using the new value ${\tilde {y}}_{2}$ and its derivative there ${\tilde {y}}_{2}^{'}$ along with the previous points and their derivatives, one can then better interpolate the derivative between $t_{1}$ and $t_{2}$ to get a better approximation $y_{2}$. The interpolation and subsequent integration of the differential equation constitute the corrector step.

Euler trapezoidal example

Example of an Euler - trapezoidal predictor-corrector method.

In this example h = $\Delta {t}$, $t_{i+1}=t_{i}+\Delta {t}=t_{i}+h$

$y'=f(t,y),\quad y(t_{0})=y_{0}.$

First calculate an initial guess value ${\tilde {y}}_{g}$ via Euler:

${\tilde {y}}_{g}=y_{i}+hf(t_{i},y_{i})$

Next, improve the initial guess through iteration of the trapezoidal rule. This iteration process normally converges quickly.

${\tilde {y}}_{g+1}=y_{i}+{\frac {h}{2}}(f(t_{i},y_{i})+f(t_{i+1},{\tilde {y}}_{g})).$

${\tilde {y}}_{g+2}=y_{i}+{\frac {h}{2}}(f(t_{i},y_{i})+f(t_{i+1},{\tilde {y}}_{g+1})).$

...

${\tilde {y}}_{g+n}=y_{i}+{\frac {h}{2}}(f(t_{i},y_{i})+f(t_{i+1},{\tilde {y}}_{g+n-1})).$

This iteration process is repeated until some fixed value n or until the guesses converge to within some error tolerance e :

$|{\tilde {y}}_{g+n}-{\tilde {y}}_{g+n-1}|\leq e$

then use the final guess as the next step:

$y_{i+1}={\tilde {y}}_{g+n}.$

Note that the overall error is unrelated to convergence in the algorithm but instead to the step size and the core method, which in this example is a trapezoidal, (linear) approximation of the actual function. The step size h ( $\Delta {t}$ ) needs to be relatively small in order to get a good approximation. See also stiff equation.

See also

• Backward differentiation formula
• Beeman's algorithm
• Heun's method
• Mehrotra predictor-corrector method
• Numerical continuation

External links

• Weisstein, Eric W. "Predictor-Corrector Methods". MathWorld.
• Predictor-corrector methods for differential equations