# Preface

This section discusses a completely different strategy to solve an
initial value problem for a single first-order differential equation
\( y' = f(x,y) , \quad y(x_0 )= y_0 . \)
In order to calculate an approximate value of the solution
φ(*t*_{n+1}) at the next mesh point
*t = t*_{n+1}, the values of the calculated
solution at some previous mesh points are used. The numerical methods
that use information at more than the last mesh point are referred to as
**multistep methods**. This section presents two types of multistep
methods: Adams methods and backward differentiation methods. Different levels
of accuracy can be achieved with each type of methods.

Return to computing page for the second course APMA0340

Return to Mathematica tutorial for the second course APMA0340

Return to the main page for the course APMA0330

Return to the main page for the course APMA0340

Return to Part III of the course APMA0330

## Glossary

# Multistep Methods

The methods of Euler, Heun, Runge--Kutta, and Taylor are called **single-step methods** (or one-step methods) because they use only the information from one previous point to compute the successive point; that is, only the initial point *(x*_{0}*, y*_{0}*)* is used to compute *(x*_{1}*, y*_{1}*)* and, in general, *y*_{k} is needed to compute *y*_{k+1}. After several points have been found, it is feasible to use several prior points in the calculation. methods that use information at more than the last mesh point are referred to as **miltistep methods**. More precisely, a method is called a multistep *k*-step method if the computation of the next approximate solution *y*_{n+1} is based on the last approximate solutions
\( y_n, y_{n-1} , \ldots , y_{n-k+1} . \)

In this section, we discuss two types of multistep methods: Adams methods and backward differentiation methods. For simplicity, we assume throughout our exposition that the step length *h* is constant.

*y*

_{n+1}, yet large enough so that unnecessary and time-consuming calculations are eliminated. Using the combination of a predictor and corrector requires only two slope function evaluations compared to six evaluations required by RKF45. The predictor-corrector forms are among the most efficient known integration methods in terms of speed and accuracy. As a class of integration methods, the multistep sets are among the best, but individually as a predictor-corrector set, the choice for the best method varies depending on the application.

## I. Adams Method

To integrate the initial value problem \( y' = f(x,y) , \quad y(x_0 ) = y_0 , \) on the mesh interval \( \left[ x_n , x_{n+1} \right] , \) we rewrite the problem in integral form:

*f(t,y(t))*by a polynomial

*P*

_{k}

*(t)*of degree

*k*and to use the polynomial to evaluate the integral on the right side of the above integral equation. John Couch Adams (1819--1892), an English mathematician and astronomer, is most famous as codiscoverer, with Joseph Leverrier, of the planet Neptume in 1846. He was associated with Cambridge University for most of his life, as student (1839--1843), fellow, Lowdean Professor, and director of the Observatory. Adams was extremely skilled at computation; his procedure for numerical integration of differential equations appeared in 1883 in a book with Francis Bashforth on capillary action.

Francis Bashforth (1819--1912), English mathematician and Anglican priest, was a classmate of J.C. Adams at Cambridge. He was particularly interested in ballistic and invented the Bashforth chronograph for measuring the velocity of artillery projectiles.

The polynomial *P*_{k}*(t)* of degree *k* contains *k+1* coefficients that are determined from previously calculated data points. For example, suppose that we wish to use a first degree polynomial \( P_1 (t) =at+b . \) Then we need only the two data points \( (x_n , y_n ) \quad\mbox{and} \quad (x_{n-1} , y_{n-1}) . \) For *P*_{1} to be an approximation to the slope function, we require that

*a*and

*b*, we obtain

*y*

_{n}and

*y*

_{n-1}is called Adams--Bashforth. It has a local truncation error proportional to

*h*

^{3}. However, this value

*p*

_{n+1}is used as a predicted value of

*y*

_{n+1}that approximates the actual solution \( y = \phi (x) \) at the mesh point

*x*

_{n+1}. This value

*p*

_{n+1}is utilized in Adams--Moulton correction formula, which is our next topic. Forest Ray Moulton (1872--1952), an American astronomer and administrator of science, was for many years professor of astronomy at the University of Chicago. During World War I, he was in charge of the Ballistics Branch of the U.S. Army at Aberdeen (MD) Proving Ground. In the course of calculating ballistics trajectories he devised substantial improvements in the Adams formula.

Actually, the predictor formulas are based on Newton's backward difference interpolation formula:

*n*-th falling factorial of

*m*. Since the derivative of

*y*is known, we obtain

## II. Backward Differentiation Formula

Another type of multistep method uses a polynomial

*P*

_{k}(

*t*) of degree

*k*to approximate the actual solution \( y = \phi (x) \) of the considered initial value problem rather than its derivative \( y' = \phi' (x) , \) as in the Adams method. We then differentiate

*P*

_{k}

*(t)*and set \( P'_k (x_{n+1}) \) equal to \( f \left( x_{n+1} , y_{n+1} \right) \) to obtain an implicit formula for

*y*

_{n+1}. These algorithms are called backward differentiation formulas. These methods became widely used in the 1970s because of the work of C. William Gear (born in 1935, London, UK) on so called stiff differential equations, whose solutions are very difficult to approximate by discussed so far methods. A British-American mathematician C.W. Gear is well-known for his contributions in numerical analysis and computer science.

The simplest case uses a first degree polynomial \( P_1 (t) =at+b . \) The coefficients are chosen to match the computed values of the solution *y*_{n} and *p*_{n+1}

*a*and

*b*must satisfy

*a*comes from subtracting the first equation from the second, which gives

*a*, we get the first order backward differentiating formula

## III. Predictor-corrector Formula

If the Adams formula is used as a precition, which is then used in backward formula, we arrive at the

**predictor-corrector formula**, credited to Nyström:

By using higher order polynomials and corresponding more data points, we can obtain backward differentiation formulas of any order. The second order Adams-Moulton formula is

## Adomian Decomposition Method

## Modified Decomposition Method

Return to Mathematica page

Return to the main page (APMA0330)

Return to the Part 1 (Plotting)

Return to the Part 2 (First Order ODEs)

Return to the Part 3 (Numerical Methods)

Return to the Part 4 (Second and Higher Order ODEs)

Return to the Part 5 (Series and Recurrences)

Return to the Part 6 (Laplace Transform)

Return to the Part 7 (Boundary Value Problems)