Extrapolation Methods
This module illustrates extrapolation methods for numerically solving
initial value problems for ordinary differential equations. A
numerical method for an ordinary differential equation (ODE) generates
an approximate solution step-by-step in discrete increments across the
interval of integration, in effect producing a discrete sample of
approximate values of the solution function. An extrapolation method
for solving an ODE applies a single-step method with various step sizes
and then computes a more accurate estimate for the solution by
extrapolating to a step size of zero based on the known dependence of
the error on the step size.
The user begins by selecting a differential equation from the
menu provided. A solution value for the selected ODE at the initial
time is marked in the left panel by a black dot. The exact solution
curve for the resulting initial value problem is drawn in the left
panel in black. Starting from the initial value, the user advances
the solution through successive steps using an extrapolation method
for each step. Each step of the extrapolation method is presented as
a six-stage process. Each stage is executed by clicking either
Next or the currently highlighted stage:
- From the menu provided, the user chooses which basic single-step method
— either the first-order Euler's method or the second-order
Heun's method — will serve as the basis for the extrapolation in
the next step. Using the slider, the user selects a step size, subject
to minimum and maximum allowed values. A red horizontal line in the
left panel indicates the length of the step that will be taken. The
user concludes this stage by clicking Choose Step Parameters or
Next, which makes the chosen parameters take effect, and changes
the line color from red to black, indicating that the length of the
step is now fixed.
- Use Full Step Size calculates the next approximate solution
value using one step of the selected basic method with the selected
step size. The calculated step is displayed in green in the left
panel, and the value of the new solution point obtained by the method
using the full step size is plotted as a green dot in the right panel.
- Use Half Step Size, computes the next approximate solution value
using two steps of the selected method with half the selected step size.
The two steps are drawn in the left panel in dark green, replacing the
solution calculated using the full step size. The value of the solution
point obtained by taking two steps with half step size is plotted as a
dark green dot in the right panel.
- Extrapolate uses the solution values of the previous two stages
to compute a more accurate solution value. The error is known to be
approximately linear for Euler's method and quadratic for Heun's
method, so the extrapolation is calculated by fitting the appropriate
polynomial to the two data points in the right panel and evaluating it
at zero. The fitted function and extrapolated solution value are
displayed in black in the right-hand panel, and in the left panel the
approximate solution generated by the extrapolation method, shown in
black, replaces the dark green approximate solution computed using two
steps of the basic method.
- The current step is concluded by clicking Take Step or
Next. The approximate and true solution values at the new point
are recorded in the table below and the exact solution to the ODE
passing through the new point is drawn in gray in the left panel.
- Preparation for another step is initiated by clicking Initialize
Next Step or Next. The panel on the right is cleared to
display the next extrapolation, and the panel on the left shows the
new step in red, ready to select parameters for the new step. The
default parameters for the new step are equal to the parameters of
the previous step, if possible.
Successive steps may be continued until the the interval has been
fully traversed.
Reference: Michael T. Heath, Scientific Computing,
An Introductory Survey, 2nd edition, McGraw-Hill, New York,
2002. See Section 9.3.7.
Developers: Evan VanderZee and Michael Heath
Department of Computer Science