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 ${\displaystyle y_{0}}$  and ${\displaystyle y_{1}}$  at times ${\displaystyle t_{0}}$  and ${\displaystyle t_{1}}$ . By fitting a cubic polynomial to the points and their derivatives (gotten through the differential equation), one can predict a point ${\displaystyle {\tilde {y}}_{2}}$  by extrapolating to a future time ${\displaystyle t_{2}}$ . Using the new value ${\displaystyle {\tilde {y}}_{2}}$  and its derivative there ${\displaystyle {\tilde {y}}_{2}^{'}}$  along with the previous points and their derivatives, one can then better interpolate the derivative between ${\displaystyle t_{1}}$  and ${\displaystyle t_{2}}$  to get a better approximation ${\displaystyle 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 = ${\displaystyle \Delta {t}}$ , ${\displaystyle t_{i+1}=t_{i}+\Delta {t}=t_{i}+h}$ 

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

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

${\displaystyle {\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.

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

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

...

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

${\displaystyle |{\tilde {y}}_{g+n}-{\tilde {y}}_{g+n-1}|<=e}$ 

then use the final guess as the next step:

${\displaystyle 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 ( ${\displaystyle \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