Section 4.4.7: Euler is not the Only Method

Euler gives exact solution if and only if exact solution is linear function of time.
More sophisticated methods match exact solution to higher orders:

Can use larger step sizes for specified accuracy, but still shorter than smallest time constant.

Graph suggests two possible approaches:

1.
Secant slope is well approximated by average of slopes m0 and m1 at start and end of step:

\begin{displaymath}\frac{1}{2} (\frac{dx}{dt}\vert _{t_n} + \frac{dx}{dt}\vert _{t_{n+1}}) \approx \frac{x(n+1) - x(n)}{h} \end{displaymath}

2.
Secant slope is good approximation to slope half way across step:

\begin{displaymath}\frac{dx}{dt}\vert _{t_{n+\frac{1}{2}}} \approx \frac{x(n+1) - x(n)}{h} \end{displaymath}

Explicit second order methods - 1

Solve

\begin{displaymath}\frac{dx}{dt} = f(x,t) \end{displaymath}

  1. Calculate f(n) = f(x(n),t(n)), slope at start of step
  2. Explicit Euler to give first order estimate, `Stage I':
    x(I) = x(n) + h f(n)
  3. Stage I derivative estimate at end of step:
    f(I) = f(x(I),tn+1)
  4. Stage II derivative estimate :average of f(n), f(I):
    $ f(II) = \frac{1}{2} (f(I) + f(n)) $

  5. Improved Euler step:
    x(n+1) = x(n) + h f(II)

Explicit second order methods - 2

Another possibility - take the first order step (explicit Euler) half way across the step and estimate a derivative for the full step.

  1. $ x(I) = x(n) + \frac{1}{2} h f(n) $
  2. Stage I derivative estimate at the half step:
    $ f(I) = f(x(I),t(n)+\frac{1}{2}h) $
  3. Use this derivative estimate for the Modified Euler step:
    x(n+1) = x(n) + h f(I)

Accuracy

General second order explicit method - section 4.4.7.1
Local error
$ e_n = \frac{1}{6} (hk)^3 x(n)$ for linear ODE

Case 1: for initial local error = 0.01 x(0)
Euler step: $\frac{1}{2} (hk)^2 = 0.01$, or
$ hk = \sqrt{0.02} = 0.1414$
2nd order step: $\frac{1}{6} (hk)^3 = 0.01$, or
$ hk = \sqrt[3]{0.06} = 0.3915$

Two function evaluations per step, but more than twice the step size ($\times$ 2.77).

Case 2: for initial local error = 0.0001 x(0)
Euler step: $\frac{1}{2} (hk)^2 = 0.0001$, or
$ hk = \sqrt{0.0002} = 0.01414$
2nd order step: $\frac{1}{6} (hk)^3 = 0.0001$, or
$ hk = \sqrt[3]{0.0006} = 0.08434 $

2nd order has nearly six times the step, so nearly three times as efficient overall.

Stability

$1 - h k + \frac{1}{2} (h k)^2$ has a minimum at h k = 1, value $= \frac{1}{2}$

For h k > 2, $1 - h k + \frac{1}{2} (h k)^2$ exceeds 1.

Stability limit at h k = 2, same as explicit Euler.

Similar limits for all higher order explicit methods (usually limiting h k in a range around 2 - 4).

Simultaneous ODEs

Apply each stage in the time step to all equations at the same time.

Example

\begin{eqnarray*}\frac{dx_1}{dt} = f_1(x_1,x_2) \\ \frac{dx_2}{dt} = f_2(x_1,x_2) \end{eqnarray*}


Modified Euler:

  1. Calculate

    \begin{eqnarray*}x_1(I) = x_1(n) + \frac{1}{2} h f_1(n) \\ x_2(I) = x_2(n) + \frac{1}{2} h f_2(n) \\ \end{eqnarray*}


    where $f_i(n) = f_i({\bf x}(n)) $.
  2. Stage I derivative:

    \begin{eqnarray*}f_1(I) = f_1({\bf x}(I)) \\ f_2(I) = f_2({\bf x}(I)) \end{eqnarray*}


  3. Full step:

    \begin{eqnarray*}x_1(n+1) = x_1(n) + h f_1(I) \\ x_2(n+1) = x_2(n) + h f_2(I) \end{eqnarray*}


    Runge-Kutta methods

    Extend the idea of the 2nd order explicit methods. Exactly match higher degree polynomials by making more estimates of the derivatives at suitably chosen fractions of the time step and averaging them with appropriate weights.

    Up to order 4 or 5 are commonly used.

    Number of function evaluations per step is usually equal to or greater than the order. But overall efficiency is better than 2nd order.

    Some methods contain built-in error estimates, for only a little extra work (1 or 2 more function evaluations per step.)

    Explicit RK methods all have limited stability ( $hk \leq 3 - 4$).

    Multistep methods

    Another way of getting higher order polynomial approximations is to use information from previous steps.

    Use only one function evaluation or (for implicit methods) NLAE solution at each time step, like Euler.

    BDF methods are popular. Good stability. More efficient than RK, BUT they need help getting started. Euler must be used initially, then 2nd order and so on. Also, changing step size is less flexible than with RK.

    Summary


    Next - Section 4.4.8: Applications of ODE's
    Return to Section 4.4 Index
    Return to Section 4 Index

    Course Organiser
    Last modified: Wed Aug 5 14:50:36 BST