# Linear Multistep methods¶

A linear multistep method computes the next solution value from the values at several previous steps:

$$\alpha_k y_{n+k} + \alpha_{k-1} y_{n+k-1} + ... + \alpha_0 y_n = h ( \beta_k f_{n+k} + ... + \beta_0 f_n )$$

Note that different conventions for numbering the coefficients exist; the above form is used in NodePy. Methods are automatically normalized so that $$\\alpha_k=1$$.

Examples:

>>> import nodepy.linear_multistep_method as lm
>>> ab3.order()
3
>>> bdf2=lm.backward_difference_formula(2)
>>> bdf2.order()
2
>>> bdf2.is_zero_stable()
True
>>> bdf7=lm.backward_difference_formula(7)
>>> bdf7.is_zero_stable()
False
>>> bdf3=lm.backward_difference_formula(3)
>>> bdf3.A_alpha_stability()
86
>>> ssp32=lm.elm_ssp2(3)
>>> ssp32.order()
2
>>> ssp32.ssp_coefficient()
1/2
>>> ssp32.plot_stability_region()
<matplotlib.figure.Figure object at 0x...>


## Instantiation¶

The follwing functions return linear multistep methods of some common types:

• backward_difference_formula(k)
• Optimal explicit SSP methods (elm_ssp2(k))

In each case, the argument $$k$$ specifies the number of steps in the method. Note that it is possible to generate methods for arbitrary $$k$$, but currently for large $$k$$ there are large errors in the coefficients due to roundoff errors. This begins to be significant at 7 steps. However, members of these families with many steps do not have good properties.

More generally, a linear multistep method can be instantiated by specifying its coefficients $$\\alpha,\\beta$$:

>> from nodepy import linear_multistep_method as lmm
>> my_lmm=lmm.LinearMultistepMethod(alpha,beta)


linear_multistep_method.Adams_Bashforth(k)

Construct the k-step, Adams-Bashforth method. The methods are explicit and have order k. They have the form:

$$y_{n+1} = y_n + h \sum_{j=0}^{k-1} \beta_j f(y_n-k+j+1)$$

They are generated using equations (1.5) and (1.7) from [hairer1993] III.1, along with the binomial expansion.

Examples:

>>> import nodepy.linear_multistep_method as lm
>>> ab3.order()
3

References:
#. [hairer1993]_


linear_multistep_method.Adams_Moulton(k)

Construct the k-step, Adams-Moulton method. The methods are implicit and have order k+1. They have the form:

$$y_{n+1} = y_n + h \sum_{j=0}^{k} \beta_j f(y_n-k+j+1)$$

They are generated using equation (1.9) and the equation in Exercise 3 from Hairer & Wanner III.1, along with the binomial expansion.

Examples:

>>> import nodepy.linear_multistep_method as lm
>>> am3.order()
4

References:
[hairer1993]

### Backward-difference formulas¶

linear_multistep_method.backward_difference_formula(k)

Construct the k-step backward differentiation method. The methods are implicit and have order k. They have the form:

$$\sum_{j=0}^{k} \alpha_j y_{n+k-j+1} = h \beta_j f(y_{n+1})$$

They are generated using equation (1.22’) from Hairer & Wanner III.1,
along with the binomial expansion.

Examples:

>>> import nodepy.linear_multistep_method as lm
>>> bdf4=lm.backward_difference_formula(4)
>>> bdf4.A_alpha_stability()
73

References:
#.[hairer1993]_ pp. 364-365

### Optimal Explicit SSP methods¶

linear_multistep_method.elm_ssp2(k)

Returns the optimal SSP k-step linear multistep method of order 2.

Examples:

>>> import nodepy.linear_multistep_method as lm
>>> lm10=lm.elm_ssp2(10)
>>> lm10.ssp_coefficient()
8/9


## Stability¶

### Characteristic Polynomials¶

LinearMultistepMethod.characteristic_polynomials()[source]

Returns the characteristic polynomials (also known as generating polynomials) of a linear multistep method. They are:

$$\rho(z) = \sum_{j=0}^k \alpha_k z^k$$

$$\sigma(z) = \sum_{j=0}^k \beta_k z^k$$

Examples:

>>> from nodepy import lm
>>> ab5 = lm.Adams_Bashforth(5)
>>> rho,sigma = ab5.characteristic_polynomials()
>>> print(rho)
5     4
1 x - 1 x

>>> print(sigma)
4         3         2
2.64 x - 3.853 x + 3.633 x - 1.769 x + 0.3486

References:
1. [hairer1993] p. 370, eq. 2.4

### Plotting The Stability Region¶

LinearMultistepMethod.plot_stability_region(N=100, bounds=None, color='r', filled=True, alpha=1.0, to_file=False, longtitle=False)[source]

The region of absolute stability of a linear multistep method is the set

$$\{ z \in C : \rho(\zeta) - z \sigma(zeta) \text{ satisfies the root condition} \}$$

where $$\rho(zeta)$$ and $$\sigma(zeta)$$ are the characteristic functions of the method.

Also plots the boundary locus, which is given by the set of points z:

$$\{z | z=\rho(\exp(i\theta))/\sigma(\exp(i\theta)), 0\le \theta \le 2*\pi \}$$

Here $$\rho$$ and $$\sigma$$ are the characteristic polynomials of the method.

References:
[leveque2007] section 7.6.1
Input: (all optional)
• N – Number of gridpoints to use in each direction
• bounds – limits of plotting region
• color – color to use for this plot
• filled – if true, stability region is filled in (solid); otherwise it is outlined