8.8. Implicit Methods: Adams-Moulton#

References:

Introduction#

So far, most methods we have seen give the new approximation value with an explicit formula for it in terms of previous (and so already known) values; the general explicit s-step method seen in Adams-Bashforth Multistep Methods was

\[U_{i} = \phi(U_{i-1}, \dots U_{i-s}, h), \quad s > 1\]

However, we briefly saw two implict methods back in Runge-Kutta Methods, in the process of deriving the explicit trapezoid and explicit midpoint methods: the implicit trapezoid method (or just the trapezoid method, as this is the real thing, before the further approximations were used to get an explicit formula)

\[U_{i+1} = U_i + h \frac{f(t_i, U_i) + f(t_{i+1}, U_{i+1}))}{2}\]

and the Implicit Midpoint Method

\[U_{i+1} = U_i + h f\left( t + h/2, \frac{U_i + U_{i+1}}{2} \right)\]

These are clearly not as simple to work with as explicit methods, but the equation solving can often be done. In particular for linear differential equations, these give linear equations for the unknown \(U_{i+1}\), so even for systems, they can be solved by the method seen earler in these notes.

Another strategy is noting that these are fixed point equations so that fixed point iterato can be used. The factor \(h\) at right helps; it can be shown that for small enough \(h\) (how small depends on the function \(f\)), these are contraction mappings and so fixed point iteration works.

This ide can be combined with linear multistep methods, and one important case is modifying the Adams-Bashforth method by allowing \(F_i = f(t_i, U_i)\) to appear at right: this gives the Adams-Moulton form

\[U_{i} = U_{i-1} + h (b_0 f(t_{i-s}, U_{i-s}) + \dots + b_{s} f(t_{i}, U_{i}))\]

where the only change from Adams-Bashforth methods is that \(b_s\) term.

The coefficients can be derived much as for those, by the method of undetermined coefficients; one valuable difference is that there at now \(s+1\) undetermined coefficients, so all error terms up to \(O(h^s)\) can be cancelled and the error made \(O(h^{s+1})\): one degree higher.

The \(s=1\) case is familiar:

\[U_{i} = U_{i-1} + h (b_0 f(t_{i-1}, U_{i-1}) + b_{1} f(t_{i}, U_{i}))\]

and as symmetry suggests, the solution is \(b_0 = b_1 = 1/2\), giving

\[U_{i} = U_{i-1} + h \frac{f(t_{i-1}, U_{i-1}) + f(t_{i}, U_{i})}{2}\]

which is the (implicit) trapzoid rule in the new shifted indexing.

This is much used for numerical solution of partial differential equations of evoluton type (after first approximating by large system of ordinary differnetial equations). In that context it is often known as the Crank-Nicholson method.

We can actualy start at \(s=0\); the first few Adams-Moulton methods are:

\[\begin{align*} s = 0: b_0 &= 1 \\ &U_{i} - h f(t_i, U_i)) = U_{i-1} \qquad &\text{The backward Euler method} \\ s = 1: b_0 &= b_1 = 1/2 \\ &U_{i} - \frac{h}{2} f(t_i, U_i) = U_{i-1} + \frac{h}{2} (F_{i-1} ) \qquad &\text{The (implicit) trapezoid method} \\ s = 2: b_0 &= -1/12, b_1 = 8/12, b_2 = 5/12 \\ &U_{i} - \frac{5h}{12}f(t_i, U_i) = U_{i-1} + \frac{h}{12} (-F_{i-2} + 8 F_{i-1}) \\ s = 3: b_0 &= 1/24, b_1 = -5/24, b_2 = 19/24, b_3 = 9/24 \\ &U_{i} - \frac{9h}{24}f(t_i, U_i) = U_{i-1} + \frac{h}{24}(F_{i-3} -5F_{i-2} + 19F_{i-1}) \end{align*}\]

The use of \(F_{i-k}\) notation emphasizes that these earlier values of \(F_{i-k} = f(t_{i-k}, U_{i-k})\) are known from a previous step, so can be stored for reuse.

The backward Euler method has not been mentioned before; it comes from using the backward counterpart of the forward difference approximation of the derivative:

\[u'(t) \approx \frac{u(t) - u(t-h)}{h}\]

Like Euler’s method it is only first order accurate, but it has excellent stability properties, which makes it useful in some situations.

Rather than implementing any of these, the next section introduces a strategy for deriving explicit methods of comparable accuracy, much as in Runge-Kutta Methods Euler’s method (Adams-Bashforth \(s=1\)) was combined with the trapezoid method (Adams-Moulton \(s=1\)) to get the explicit trapezoid method: an explicit method with the same order of accuracy as the latter of this pair.

Exercises#

Coming soon.