Linear Multistep Methods

In these methods, a finite time step, h, is introduced and the continuous solution $y\left(t \right)$ is approximated by its values at the discrete times $t_1 = h, \ t_2 = 2h, \ldots t_n = nh$. The recursive formula for a general r-step LMM can be written as  

$$\sum_{i=0}^{r} \alpha_i y_{n+i} = h \sum_{j=1}^{r} \beta_j f \left( y_{n+j}, t_{n+j} \right), \ \ \alpha_r \ne 0.$$ (255)

If $\beta_r = 0$, then the LMM is called explicit since the value of y at a particular time step can be determined from the values of y corresponding only to the previous time steps. If $\beta_r \ne 0$, then the LMM is called implicit and one needs to use an iterative scheme, like Newton's method, to determine the solution.

The key issues in devising a LMM are its accuracy and stability. Its accuracy is dictated from the error made at each time step provided that the information used in all the pprevious time-steps was exact. The dominant dependence on h of that error can be easily found through a Taylor expansion of the LMM formula around the nth time-step solution. If this is of the order h^r+1 then the LMM is said to be of order r accuracy, the one less power of h accounting for the fact that as h decreases you need more steps taken to span a fixed distance in time during which the individual time-step errors can be expected at best to add up. However, this is only a good upper bound for the total approximation error if the error existing in the initial data as one time-step is advanced is not amplified by the recursive formula. This is dictated by the stability of the LMM method, a stable LMM being defined as the one that does not amplify the error from one step to the next. For a LMM to be convergent, it must be consistent, i.e., at least of first order accuracy, and must be zero-stable, i.e., stable in the limit $h \rightarrow 0$.Moreover, the stability of the method for a finite h must be known. Usually, the requirements of stability and accuracy conflict with each other, i.e., a method with high accuracy tends to have a small stability region.

Implicit methods involve more computational time due to the additional iterations that they require for convergence to be established. On the other hand, those are the only methods that involve an unbounded stability region (potentially including the whole left plane) in the complex space where the product of the time-step size h and the system's Jacobian eigenvalues are represented. Thus, if a system includes eigenvalues of large magnitude, albeit stable (i.e. with negative real part), an implicit method is recommended since use of an explicit one, as involving only a finite stability region, would have placed severe restrictions on the time-step size (stiff systems). For that purpose, a series of implicit schemes based on backward difference integration formulae (Gear) are used in the IMSL subroutines like IVPAG.