Predictor-Corrector Methods

Date: 09/07/2002 at 04:08:38
From: Jen
Subject: Predictor-Corrector Methods

Could you please explain what a predictor-corrector method is, 
possibly using Euler's and Huen's methods as examples? Please.

Thank you so much,
Jen

Date: 09/07/2002 at 09:05:35
From: Doctor Fenton
Subject: Re: Predictor-Corrector Methods

Hi Jen,

Thanks for sending your question to Dr. Math. The idea of
predictor-corrector methods is the following:

To solve  y' = f(x,y)  with y(x0) = y0, and perhaps some additional 
values of y known:

                      x1
                     /
     y(x1) - y(x0) = | f(x,y(x)) dx
                     /
                     x0

If we  use a numerical method to compute the integral on the right,
then we will have a value for y(x1).

Numerical integration formulas are of two types: open formulas, which 
compute the integral

       b
      /
      | f(x) dx
      /
      a

by evaluating f at points in the interval (a,b), i.e. not using the 
value of f at the endpoints; and closed formulas, which use the value 
of f at the endpoints to compute the integral.

An example of an open formula is the Midpoint Rule:

     b
    /
    | f(x)dx ~ f((a+b)/2) (b-a)
    /
    a

where you approximate the integral by the product of the value of f at 
the midpoint times the length of the interval. When a and b are very 
close, this isn't a bad approximation: you are approximating the area 
between the x-axis and the graph of f, which is a "quadrilateral" with 
three straight sides, and the fourth side the graph of f, by a 
rectangle whose height is the height of the curve at the midpoint.

Over a very short interval, the graph of f will be almost straight, so 
the "quadrilateral" will be nearly a trapezoid, and the approximation 
is very good (it is exact for a true trapezoid).

An example of a closed formula is the Trapezoid Rule. Over one 
interval, you use

    b
   /          (b-a)
   | f(x)dx ~ ----- (f(a) + f(b))
   /            2
   a

Back to the DE: suppose we know y(x0) and have computed y(x1) by some 
method (e.g. Euler's Method). Then we can first approximate the 
integral on the right in

                      x2
                     /
     y(x2) - y(x0) = | f(x,y(x)) dx
                     /
                     x0

with the Midpoint Rule (where x1 is the midpoint of x0 and x2) so that

     y(x2) = y(x0) + (x2-x0)*f(x1,y(x1))  .

The right side is an explicit formula which can easily be computed.
However, since the Midpoint Rule isn't as accurate as the Trapezoid 
Rule, we will regard the value of y(x2) on the left as a preliminary 
value called a "predictor," which I will denote by y_p(x2).

If we had tried to use the Trapezoid Rule initially, we would have

                    (x2-x0)
    y(x2) = y(x0) + ------- (y(x0)+y(x2))
                       2

which is an implicit equation, since y(x2), the unknown, occurs on 
both sides of the equation. An implicit equation requires us to solve 
for the unknown, rather than just evaluate an expression, which is 
inconvenient.

However, since we have a value of y(x2) from the "predictor," we can 
make this equation explicit by using the predicted value on the right 
side:

                    (x2-x0)
    y(x2) = y(x0) + ------- (y(x0)+y_p(x2))    .
                       2

That is, we use the predicted value y_p(x2) on the right to make it 
easier to solve for a more accurate value of y(x2), which is now 
called a "corrector," y_c(x2). One can iterate, using the "corrected" 
value again on the right side to compute a second new "corrected" 
value, etc. However, it is generally best to use the corrector formula 
only one or two times. If the results aren't accurate enough, use a 
smaller step size.

Predictor-Corrector methods require a "starting" method to compute the 
additional initial values for the open integral formula. If you decide 
to decrease the step size in the middle of the computation, you have 
to "re-start" the method. Accurate predictor-corrector methods often 
use a single step method such as Runge-Kutta to get started. They also 
use very accurate numerical integration formulas. See a numerical 
analysis text for more details; Conte and de Boor's _Elementary 
Numerical Analysis_ is fairly easy to read.

If you have any questions, please write back.

- Doctor Fenton, The Math Forum
  http://mathforum.org/dr.math/