2.3.2 Stiff Problems: Backward Differentiation Formulas

next up previous
Next: 2.3.3 The Code VODE Up: 2.3 Multi-Step Methods Previous: 2.3.1 The Adams-Bashforth and

2.3.2 Stiff Problems: Backward Differentiation Formulas

A problem is stiff if the numerical solution has its step size limited more severely by the stability of the numerical technique than by the accuracy of the technique. Frequently, these problems occur in systems of differential equations that involve several components that are decaying at widely differing rates. The reader is encouraged to consult the excellent survey article [6] by Shampine and Gear, ``A User's View of Solving Stiff Ordinary Differential Equations.''

A simple scalar example of stiffness is given by C.W. Gear [5]:

where is a smooth, slowly varying function. The solution,

has a component that will be insignificant compared to for sufficiently large. The numerical method, however, will always have its step size limited by the magnitude of for the entire integration.


In Gear's example above, choose . In Table 7 we tabulate the cost of integrating the IVP,

using RKSUITE for . The solution is . Relative and absolute error tolerances were taken to be .

Table 6: Solution of a stiff IVP using RKSUITE. View Table

Note that the smaller the solution component becomes, the harder RKSUITE works. Using a code designed specifically for stiff problems such as the code VODE presented in the next section, the number of function evaluations would have been approximately 120 for the range of -values considered.

A class of multi-step formulas which are highly effective in solving stiff problems are based on numerical differentiation. Again, we start by interpolating the previously computed solution values as well as the new one by a polynomial . The derivative of the solution at is then approximated by . The approximation is related to the differential equation by insisting that it satisfy the differential equation at :

Substituting for in this equation, we obtain the family of backward differentiation formulas, the BDFs:


These formulas were popularized by Gear, and are sometimes known as Gear's formulas. They are implicit like the Adams-Moulton formulas, but not as accurate for formulas of the same order and not stable for orders 7 and up. However, at the orders for which the formulas are stable, they are much more stable than the Adams-Moulton formulas. The formulas (52) cannot be evaluated by simple iteration because this restricts the step size just as much as stability does for much less stable formulas. In practice, a modified Newton iteration (Linear Algebra Chapter) is used to solve the nonlinear algebraic equations for ; this requires approximating partial derivatives and solving systems of linear equations.

As with Adams formulas, modern codes based on the BDFs vary the formula (the order used) as well as the step size. The solution of problems that are quite stiff are completely impractical with a method intended for non-stiff problems, such as an explicit Runge-Kutta method or an Adams-Moulton method evaluated by simple iteration

The simplest BDF is when is the straight line interpolating and . The derivative at is the constant slope of this line and setting it to results in

Once again we have derived the backward Euler formula! Although this case results in a one-step formula, the higher order BDFs do involve previously computed solution values. For example, when the step size is a constant , the backward differentiation formula of order two is

A code providing a highly efficient implementation of the Adam's formulas and the BDF formulas is given in the next section.

next up previous
Next: 2.3.3 The Code VODE Up: 2.3 Multi-Step Methods Previous: 2.3.1 The Adams-Bashforth and