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.
__TOC__
== 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}_g via Euler:
: \tilde{y}_{g} = y_i + h f(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} | \le 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 ==
* 
* Predictor-corrector methods for differential equations
Category:Algorithms
Category:Numerical analysis