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 (obtained from 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}}_{[0]}$ via Euler:

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

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

${\begin{aligned}{\tilde {y}}_{[1]}&=y_{i}+{\frac {h}{2}}(f(t_{i},y_{i})+f(t_{i+1},{\tilde {y}}_{[0]})).\\{\tilde {y}}_{[2]}&=y_{i}+{\frac {h}{2}}(f(t_{i},y_{i})+f(t_{i+1},{\tilde {y}}_{[1]})).\\&{}\ \vdots \\{\tilde {y}}_{[n]}&=y_{i}+{\frac {h}{2}}(f(t_{i},y_{i})+f(t_{i+1},{\tilde {y}}_{[n-1]})).\end{aligned}}$

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

$|{\tilde {y}}_{[n]}-{\tilde {y}}_{[n-1]}|\leq e$

then use the final guess as the next step:

$y_{i+1}={\tilde {y}}_{[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

References

• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 17.6. Multistep, Multivalue, and Predictor-Corrector Methods". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.

External links

• Weisstein, Eric W. Methods.html "Predictor-Corrector Methods". MathWorld. {{cite web}}: Check |url= value (help)
• Predictor–corrector methods for differential equations