Interactive Educational Modules in
Scientific Computing

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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