Linear multistep method: Difference between revisions

Revision as of 16:42, 9 March 2015

Revision as of 15:03, 26 March 2015

Line 3:

== Definitions ==

Numerical methods for ordinary differential equations approximate solutions to [[initial value problemsproblem]]s of the form

: <math> y' = f(t,y), \quad y(t_0) = y_0. </math>

Line 21:

Sometimes an explicit multistep method is used to "predict" the value of <math> y_{n+s} </math>. That value is then used in an implicit formula to "correct" the value. The result is a [[predictor–corrector method]].

== Examples ==

Consider for an example the problem

Line 27:

The exact solution is <math> y(t) = \mathrm{e}^t </math>.

=== One-step Euler ===

A simple numerical method is Euler's method:

: <math> y_{n+1} = y_n + hf(t_n, y_n). \, </math>

Euler's method can be viewed as an explicit multistep method for the degenerate case of one step.

This method, applied with step size <math> h = \tfrac12tfrac{1}{2} </math> on the problem <math> y' = y </math>, gives the following results:

: <math> \begin{align}

y_1 &= y_0 + hf(t_0, y_0) = 1 + \tfrac12tfrac{1}{2}\cdot1 = 1.5, \\

y_2 &= y_1 + hf(t_1, y_1) = 1.5 + \tfrac12tfrac{1}{2}\cdot1.5 = 2.25, \\

y_3 &= y_2 + hf(t_2, y_2) = 2.25 + \tfrac12tfrac{1}{2}\cdot2.25 = 3.375, \\

y_4 &= y_3 + hf(t_3, y_3) = 3.375 + \tfrac12tfrac{1}{2}\cdot3.375 = 5.0625.

\end{align} </math>

===Two-step Adams–Bashforth===

Euler's method is a one-step method. A simple multistep method is the two-step Adams–Bashforth method

: <math> y_{n+2} = y_{n+1} + \tfrac32tfrac{3}{2} hf(t_{n+1},y_{n+1}) - \tfrac12tfrac{1}{2} hf(t_n,y_n). </math>

This method needs two values, <math> y_{n+1} </math> and <math> y_n </math>, to compute the next value, <math> y_{n+2} </math>. However, the initial value problem provides only one value, <math> y_0 = 1 </math>. One possibility to resolve this issue is to use the <math> y_1 </math> computed by Euler's method as the second value. With this choice, the Adams–Bashforth method yields (rounded to four digits):

: <math> \begin{align}

Line 51:

The exact solution at <math> t = t_4 = 2 </math> is <math> \mathrm{e}^2 = 7.3891\ldots </math>, so the two-step Adams–Bashforth method is more accurate than Euler's method. This is always the case if the step size is small enough.

== Families of multistep methods ==

Three families of linear multistep methods are commonly used: Adams–Bashforth methods, Adams–Moulton methods, and the [[backward differentiation formula]]s (BDFs).

=== Adams–Bashforth methods ===

The Adams–Bashforth methods are explicit methods. The coefficients are <math> a_{s-1}=-1 </math> and <math> a_{s-2} = \cdots = a_0 = 0 </math>, while the <math> b_j </math> are chosen such that the methods has order ''s'' (this determines the methods uniquely).

The Adams–Bashforth methods with ''s'' = 1, 2, 3, 4, 5 are ({{harvnb|Hairer|Nørsett|Wanner|1993|loc=§III.1}}; {{harvnb|Butcher|2003|p=103}}):

Line 61:

y_{n+1} &= y_n + hf(t_n, y_n) , \qquad\text{(This is the Euler method)} \\

y_{n+2} &= y_{n+1} + h\left( \frac{3}{2}f(t_{n+1}, y_{n+1}) - \frac{1}{2}f(t_n, y_n) \right) , \\

y_{n+3} &= y_{n+2} + h\left( \frac{23}{12} f(t_{n+2}, y_{n+2}) - \frac43frac{4}{3} f(t_{n+1}, y_{n+1}) + \frac{5}{12}f(t_n, y_n)\right) , \\

y_{n+4} &= y_{n+3} + h\left( \frac{55}{24} f(t_{n+3}, y_{n+3}) - \frac{59}{24} f(t_{n+2}, y_{n+2}) + \frac{37}{24} f(t_{n+1}, y_{n+1}) - \frac{3}{8} f(t_n, y_n) \right) , \\

y_{n+5} &= y_{n+4} + h\left( \frac{1901}{720} f(t_{n+4}, y_{n+4}) - \frac{1387}{360} f(t_{n+3}, y_{n+3}) + \frac{109}{30} f(t_{n+2}, y_{n+2}) - \frac{637}{360} f(t_{n+1}, y_{n+1}) + \frac{251}{720} f(t_n, y_n) \right) .

\end{align} </math>

The coefficients <math> b_j </math> can be determined as follows. Use [[polynomial interpolation]] to find the polynomial ''p'' of degree <math> s-1 </math> such that

:<math> p(t_{n+i}) = f(t_{n+i}, y_{n+i}), \qquad \text{for } i=0,\ldots,s-1. </math>

The [[Lagrange polynomial|Lagrange formula]] for polynomial interpolation yields

:<math> p(t) = \sum_{j=0}^{s-1} \frac{(-1)^{s-j-1}f(t_{n+j}, y_{n+j})}{j!(s-j-1)!h^{s-1}} \prod_{i=0 \atop i\ne j}^{s-1} (t-t_{n+i}). </math>

The polynomial ''p'' is locally a good approximation of the right-hand side of the differential equation <math> y' = f(t,y) </math> that is to be solved, so consider the equation <math> y' = p(t) </math> instead. This equation can be solved exactly; the solution is simply the integral of ''p''. This suggests taking

:<math> y_{n+s} = y_{n+s-1} + \int_{t_{n+s-1}}^{t_{n+s}} p(t)\,dt. </math>

The Adams–Bashforth method arises when the formula for ''p'' is substituted. The coefficients <math> b_j </math> turn out to be given by

:<math> b_{s-j-1} = \frac{(-1)^j}{j!(s-j-1)!} \int_0^1 \prod_{i=0 \atop i\ne j}^{s-1} (u+i) \,du, \qquad \text{for } j=0,\ldots,s-1. </math>

Replacing ''<math> f''(''t'', ''y'') </math> by its interpolant ''p'' incurs an error of order ''h''^''s'', and it follows that the ''s''-step Adams–Bashforth method has indeed order ''s'' {{harv|Iserles|1996|loc=§2.1}}

The Adams–Bashforth methods were designed by [[John Couch Adams]] to solve a differential equation modelling [[capillary action]] due to [[Francis Bashforth]]. {{harvtxt|Bashforth|1883}} published his theory and Adams' numerical method {{harv|Goldstine|1977}}.

=== Adams–Moulton methods ===

The Adams–Moulton methods are similar to the Adams–Bashforth methods in that they also have <math> a_{s-1} = -1 </math> and <math> a_{s-2} = \cdots = a_0 = 0 </math>. Again the ''b'' coefficients are chosen to obtain the highest order possible. However, the Adams–Moulton methods are implicit methods. By removing the restriction that <math> b_s = 0 </math>, an ''s''-step Adams–Moulton method can reach order <math> s+1 </math>, while an ''s''-step Adams–Bashforth methods has only order ''s''.

The Adams–Moulton methods with ''s'' = 0, 1, 2, 3, 4 are ({{harvnb|Hairer|Nørsett|Wanner|1993|loc=§III.1}}; {{harvnb|Quarteroni|Sacco|Saleri|2000}}):

Line 90:

\end{align} </math>

The derivation of the Adams–Moulton methods is similar to that of the Adams–Bashforth method; however, the interpolating polynomial uses not only the points ''t''<sub>''n''−1</submath> t_{n−1},\dots &hellip; ''t''<sub>''t_{n''−''-s''} </submath>, as above, but also <math> t_n </math>. The coefficients are given by

:<math> b_{s-j} = \frac{(-1)^j}{j!(s-j)!} \int_0^1 \prod_{i=0 \atop i\ne j}^{s} (u+i-1) \,du, \qquad \text{for } j=0,\ldots,s. </math>

Line 113:

If the method is consistent, then the next question is how well the difference equation defining the numerical method approximates the differential equation. A multistep method is said to have ''order'' ''p'' if the local error is of order <math>O(h^{p+1})</math> as ''h'' goes to zero. This is equivalent to the following condition on the coefficients of the methods:

:<math> \sum_{k=0}^{s-1} a_k = -1 \quad\text{and}\quad q \sum_{k=0}^s k^{q-1} b_k = s^q + \sum_{k=0}^{s-1} k^q a_k \text{ for } q=1,\ldots,p. </math>

The ''s''-step Adams–Bashforth method has order ''s'', while the ''s''-step Adams–Moulton method has order <math>s+1</math> {{harv|Hairer|Nørsett|Wanner|1993|loc=§III.2}}.