Scientific Computing - Quiz 1 - Question 8

Problem:

Derive the Adams-Moulton scheme and Adams-Bashforth scheme that uses $y_{n+1}, y_{n}, f_{n-1}$ and $y_{n}, f_{n-1}, f_{n-2}$ respectively.

Solution:

To approximate a polynomial with three points, we use the Lagrange's polynomial.

$ \begin{eqnarray*} p(t) &=& f_n\frac{(t - (n-1)\Delta t)(t - (n-2)\Delta t)}{(n \Delta t - (n-1)\Delta t)(n \Delta t - (n-2)\Delta t)} + f_{n-1}\frac{(t - n\Delta t)(t - (n-2)\Delta t)}{((n - 1)\Delta t - n\Delta t)((n - 1)\Delta t - (n-2)\Delta t)} + f_{n-2}\frac{(t - n\Delta t)(t - (n-1)\Delta t)}{((n - 2)\Delta t - n\Delta t)((n - 2)\Delta t - (n-1)\Delta t)} \\ &=& f_n\frac{(t - (n-1)\Delta t)(t - (n-2)\Delta t)}{2 \Delta t^2} + f_{n-1}\frac{(t - n\Delta t)(t - (n-2)\Delta t)}{-\Delta t^2} + f_{n-2}\frac{(t - n\Delta t)(t - (n-1)\Delta t)}{2\Delta t^2} \\ &=& \frac{1}{2\Delta t^2} (f_n(t - (n-1)\Delta t)(t - (n-2)\Delta t) - 2f_{n-1}(t - n\Delta t)(t - (n-2)\Delta t) + f_{n-2}(t - n\Delta t)(t - (n-1)\Delta t)) \\ \end{eqnarray*} $

Note that while the expression is long, it is simply a quadratic polynomial with a lot of awful looking constants. To simplify things, let $ u = t - n\Delta t $

$ \begin{eqnarray*} p(u) &=& \frac{1}{2\Delta t^2} (f_n(u + \Delta t)(u + 2\Delta t) - 2f_{n-1}(u)(u + 2\Delta t) + f_{n-2}(u)(u + \Delta t)) \\ &=& \frac{1}{2\Delta t^2} (f_n(u^2 + 3u\Delta t + 2\Delta t^2) - 2f_{n-1}(u^2 + 2u\Delta t) + f_{n-2}(u^2 + u\Delta t)) \\ &=& \frac{1}{2\Delta t^2} (u^2(f_n - 2f_{n-1} + f_{n-2}) + u\Delta t(3f_n - 4f_{n-1} + f_{n-2}) + 2f_n\Delta t^2) \\ \end{eqnarray*} $

Ugly as is, we can integrate now.

$ \begin{eqnarray*} y_{n + 1} - y_{n} & = & \int\limits_{t_n}^{t_{n+1}}{f(t,y)dt} \\ y_{n + 1} & = & y_{n} + \int\limits_{t_n}^{t_{n+1}}{f(t,y)dt} \\ & \approx & y_{n} + \int\limits_{t_n}^{t_{n+1}}{p(t)dt} \\ & \approx & y_{n} + \int\limits_{0}^{\Delta t}{p(u)du} \\ & \approx & y_{n} + \int\limits_{0}^{\Delta t}{\frac{1}{2\Delta t^2} (u^2(f_n - 2f_{n-1} + f_{n-2}) + u\Delta t(3f_n - 4f_{n-1} + f_{n-2}) + 2f_n\Delta t^2)du} \\ & \approx & y_{n} + \frac{1}{2\Delta t^2} \int\limits_{0}^{\Delta t}{(u^2(f_n - 2f_{n-1} + f_{n-2}) + u\Delta t(3f_n - 4f_{n-1} + f_{n-2}) + 2f_n\Delta t^2)du} \\ & \approx & y_{n} + \frac{1}{2\Delta t^2} (\frac{u^3}{3}(f_n - 2f_{n-1} + f_{n-2}) + \frac{u^2}{2}\Delta t(3f_n - 4f_{n-1} + f_{n-2}) + 2uf_n\Delta t^2) |_{0}^{\Delta t} \\ & \approx & y_{n} + \frac{1}{2\Delta t^2} (\frac{\Delta t^3}{3}(f_n - 2f_{n-1} + f_{n-2}) + \frac{\Delta t^3}{2}(3f_n - 4f_{n-1} + f_{n-2}) + 2\Delta t^3f_n) \\ & \approx & y_{n} + \frac{\Delta t}{2} (\frac{1}{3}(f_n - 2f_{n-1} + f_{n-2}) + \frac{1}{2}(3f_n - 4f_{n-1} + f_{n-2}) + 2f_n) \\ & \approx & y_{n} + \frac{\Delta t}{12} (2(f_n - 2f_{n-1} + f_{n-2}) + 3(3f_n - 4f_{n-1} + f_{n-2}) + 12f_n) \\ & \approx & y_{n} + \frac{\Delta t}{12} (23f_n - 16f_{n-1} + 5f_{n-2}) \\ \end{eqnarray*} $

This is the Adam-Bashforth scheme - I will skip the Adam Moulton scheme, derivation like this is best leave to the computer...

We have the correct answer at https://en.wikipedia.org/wiki/Linear_multistep_method, and it is great to see the answer matches (to be honest to my future self, I did spend great time to fix the derivation to match the solution, the very detailed derivation does help me a lot to fix the bug without redoing everything)