Interactive Educational Modules in
Scientific Computing

BDF Methods

This module illustrates BDF (backward differentiation formula) 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. BDF (backward differentiation formula) methods are implicit linear multistep methods that depend on multiple previous solution points to generate a new approximate solution point. In a BDF method of order n, the solution is advanced at each step by interpolating n previous solution points along with the as yet unknown new solution point, differentiating that interpolant, and requiring the derivative to match the ODE at the new point. Specifically, for an ODE y′ = f(t, y) and approximate solution points (tk−n+1, yk−n+1),…,(tk, yk), the approximate solution value yk+1 at time tk+1 = tk + hk is determined by solving the implicit equation p′(tk+1) = f(tk+1, yk+1) for yk+1, where p(t) is the unique polynomial of degree n that interpolates (tk−n+1, yk−n+1),…,(tk, yk), (tk+1, yk+1). BDF methods have relatively large stability regions, so they are particularly suitable for solving stiff ODEs.

The user begins by selecting a differential equation and a specific order BDF method from the menus provided. The last four differential equations in the menu match those in the stiffness module and illustrate how effective BDF methods can be even for stiff problems. A solution value for the selected ODE at an initial time is marked with a black dot, and the exact solution curve for the resulting initial value problem is drawn in black. Next the user selects the number of steps to be taken over the interval of integration, determining the primary step size used to solve the problem.

A BDF method of order greater than one requires multiple previous solution values, so some other method must be used to generate sufficiently many solution values for the desired method to become applicable. This module uses lower-order BDF methods to generate the necessary starting values for its higher-order methods. Since the accuracy of methods generally decreases along with the order, the step size is reduced by half for each decrease of one in the order. Starting with the first-order method and a correspondingly reduced step size, the next higher-order method (with doubled step size) is used as soon as there are enough solution points for it to become applicable, until the method of desired order and the primary step size are reached. Because of this starting procedure, the actual number of steps taken over the interval may exceed the selected number of steps. A red arrow indicates the specific BDF method that is being used at each step.

Each BDF method step is presented as a three-stage process. Each stage is executed by clicking either Next or the currently highlighted stage:

  1. Begin Step takes the value of the current solution point as an initial guess for the next solution value and displays the predicted solution point as a red dot.
  2. The next stage is to solve the implicit equation of the BDF method. The user performs one or more iterations of Newton's method by clicking Iterate as many times as desired. The approximate new solution value indicated by the red dot is updated with each iteration. The residual (i.e., the difference between the right and left sides of the implicit equation) is printed as a measure of convergence. Convergence can also be observed graphically from the movement of the new solution point with each iteration. After performing the desired number of iterations, the user clicks Solve Equation or Next, which changes the color of the new solution point from red to black, indicating that its location is now fixed.
  3. 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 draw in gray.

Reference: Michael T. Heath, Scientific Computing, An Introductory Survey, 2nd edition, McGraw-Hill, New York, 2002. See Section 9.3.8.

Developers: Evan VanderZee and Michael Heath