0
$\begingroup$

I want to get an intuitive understanding of Heun's method and why it has order of consistency 2, i.e. the error lies is in $O(h^{3})$ if $h$ is the stepwidth., I have read it everywhere, my professor says it without proving it. All the resources I have seen so far on the web either omit the proof as trivial, and the only one that does the proof does it wrong. I am at a loss. Can someone explain it to me in as much detail as possible?

$\endgroup$
4
  • 1
    $\begingroup$ You should be able to prove that by computing a Taylor expansion of the solution up to the 4-th order, with reference point $t_n$ and compare this expression obtained in $t_{n+1}$ with the actual Heun method final step, and see that the terms cancel out up.to the third order included. $\endgroup$
    – Laurent90
    Commented Nov 28, 2020 at 19:09
  • $\begingroup$ i have tried to do that, but failed. Can you explain it to me in détail? $\endgroup$ Commented Nov 28, 2020 at 19:17
  • $\begingroup$ I'll try to write an answer later ! $\endgroup$
    – Laurent90
    Commented Nov 28, 2020 at 19:18
  • $\begingroup$ Do you understand that/why the composite trapezoidal quadrature has order 2? Do you accept in some way that a method with a local truncation error of $O(h^{p+1})$ has (if at all) a global error order of $O(h^p)$? $\endgroup$ Commented Nov 29, 2020 at 9:14

2 Answers 2

2
$\begingroup$

I am assuming you mean the explicit method given by \begin{align} &k_1 = f(t_n, y_n) \\ &k_2 = f(t_n + h, y_n + hk_1) \\ &y_{n + 1} = y_n + \frac{h}{2}\left(k_1 + k_2\right) \end{align} To analyze truncation error, assume $y_n = y(t_n)$. From Euler's method we know $$y_n + hk_1 = y(t_n + h) + O(h^2)$$ Therefore by Taylor expanding the y argument to the first degree $$k_2 = f(t_n + h, y(t_n + h) + O(h^2)) = f(t_n + h, y(t_n + h)) + O(h^2)$$ Hence Heun's method is almost the trapezoid method for integration applied to $f$ to approximate $y(t_n + h) - y_n = \int_{t_n}^{t_n + h}f(t, y(t))\,dt$ except that it differs from it by $\frac{h}{2}O(h^2) = O(h^3)$. The trapezoid method is known to be $O(h^3)$ locally, so the error of Heun's method is $O(h^3)$ since it differs from the trapezoid method by $O(h^3)$.

Alternatively, Taylor expanding Heun's method and comparing it to the Taylor expansion of $y(t_n + h)$ will give you the result. This strategy can give the conditions for a Runge Kutta method to achieve a desired order.

For example for two stage methods of order 2:

Assume a method of the form \begin{align} &k_1 = f(t_n, y_n) \\ &k_2 = f(t_n + c_2h, y_n + ha_{21}k_1) \\ &y_{n + 1} = y_n + h(b_1k_1 + b_2k_2) \\ \end{align} Then Taylor expanding $k_2$ to $O(h^2)$ gives \begin{align} k_2 &= f + f_{t}c_2h + f_{y}ha_{21}k_1 + O(h^2) \\ &= f + (c_{2}f_{t} + a_{21}f_{y}f)h + O(h^2). \end{align} where the arguments $(t_n, y_n)$ are omitted. Hence \begin{align} y_{n + 1} = y_{n} + (b_1 + b_2)fh + (b_{2}c_{2}f_{t} + b_{2}a_{21}f_{y}f)h^2 + O(h^3). \end{align} On the other hand, \begin{align} y(t_n + h) = y_{n} + y'(t_n)h + \frac{y''(t_n)}{2}h^2 + O(h^3). \end{align} Since $y'(t) = f(t, y(t))$, we get \begin{align} &y'(t_n) = f \\ &y''(t_n) = f_t \cdot 1 + f_yy' = f_t + f_{y}f. \end{align} Therefore $$y(t_n + h) = y_n + fh + \frac{f_t + f_yf}{2}h^2 + O(h^3)$$ Matching terms gives \begin{align} &b_1 + b_2 = 1 \\ &b_2c_2 = \frac{1}{2} \\ &b_2a_{21} = \frac{1}{2}. \end{align} Heun's method is $c_2 = 1$, $b_1 = b_2 = \frac{1}{2}$, $a_{21} = 1$.

$\endgroup$
2
  • $\begingroup$ Could you elaborate.on that "taylor-expanding Heun's method and comparing it to the Taylor expansion" is exactly where I always fail. I always have one factor of 1/2 too many, and I don't know where it comes from. $\endgroup$ Commented Nov 28, 2020 at 19:51
  • $\begingroup$ @TheThinWhistler I've added the Taylor expansion derivation for the easiest case of two stage methods of order 2 (Heun's method is one of them). $\endgroup$
    – Mason
    Commented Nov 29, 2020 at 1:20
1
$\begingroup$

Here is my attempt at a proof of the order of the Heun's method using Taylor expansions.

Let's suppose $y(t)$ is the true solution of the autonomous ODE $d_t y = f(y)$ and assume $y$ is scalar for the sake of simplicity. Let's suppose we have $y_n = y(t_n)$. The value at time $t_{n+1}$ given by the Heun's method is:

$$y_{n+1} = y_n + \frac{\Delta t}{2} f(y_n) + \frac{\Delta t}{2} f\left( y_n + \Delta t f(y_n) \right)$$

Let's express the last term using a Taylor expansion: $$ f\left( y_n + \Delta t f(y_n) \right) = f(y_n) + (d_y f)(y_n) (\Delta t f(y_n)) + (d_{yy} f)(y_n) \frac{(\Delta t f(y_n))^2}{2} + (d_{yyy} f)(y_n) \frac{(\Delta t f(y_n))^3}{6} + O(\Delta t^4)$$

Inserting this expansion back into the first equation yields: $$y_{n+1} = y_n + \Delta t f(y_n) + (d_y f)(y_n) \dfrac{\Delta t^2 f(y_n)}{2} + (d_{yy} f)(y_n) \frac{\Delta t^3 f(y_n)^2}{4} + O(\Delta t^4)$$

Now let's perform a Taylor expansion of the true solution: $$y(t_{n+1}) = y_n +\Delta t (d_t y)(y_n) + \dfrac{\Delta t^2}{2} (d_{tt} y)(y_n) + \dfrac{\Delta t^3}{6} (d_{ttt} y)(y_n) + O(\Delta t^4)$$

which we can develop into:

$$y(t_{n+1}) = y_n +\Delta t f(y_n) + \dfrac{\Delta t^2}{2} (d_{y}f)f(y_n) + \dfrac{\Delta t^3}{6} ( (d_y f)^2 f + f^2 (d_{yy} f))(y_n) + O(\Delta t^4)$$

Comparing the terms of equal power of $\Delta t$ in the expressions of $y_{n+1}$ and $y(t_{n+1})$ we see that the local truncation error is is of order 3, therefore the method is of order 2.

The answer provided by @mason is more elegant, but here we see what the term in $O(\Delta t^3)$ is.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .