5
$\begingroup$

The LTE of an implicit Euler method is $O(h^2)$ because the method has order $O(h)$, but I'm not sure where to get started in proving this arithmetically. Any help would be appreciated. Thank you!

$\endgroup$
  • $\begingroup$ How are the sequence $(y_k)$ and the function $y(t)$ related? $\endgroup$ – LutzL Apr 19 '16 at 21:50
  • $\begingroup$ I believe $y_k$ is y at time $t_k$. Is that correct? $\endgroup$ – mil10 Apr 19 '16 at 22:57
  • $\begingroup$ You should be able to verify that in a proper definition of the local error. Now use that $f(t_{k+1},y(t_{k+1})) = y'(t_{k+1})$ to establish a Taylor formula. $\endgroup$ – LutzL Apr 19 '16 at 23:08
3
$\begingroup$

Part one

Before you read further, remember this golden rule:

Compute error by expanding in Taylor series.

Unfortunately, there are two competing definitions of truncation error. Your textbook (or class) appears to use one of them. I'll address this issue later. Your textbook/class definition of $\tau_{n+1}$ is

$$h \tau_{n+1} := LHS - RHS$$

assuming that the exact solution $y$ is used. Here by $LHS$ and $RHS$, I mean the left-hand side and right-hand side of the finite-difference method. This gives you the first equation they have, which is

$$ h \tau_{n+1} = y_{n+1} - y_n - h f(t_{n+1}, y_{n+1})$$

From here, you have to decide what you want to expand in Taylor series. Because $f(t_{n+1}, y_{n+1}) = y'(t_{n+1})$, it makes sense that we should expand a Taylor series around the point $t_{n+1}$. Since $y_{n+1} = y(t_{n+1})$, there's nothing to expand around $t_{n+1}$, so it follows that we should be expanding $y_n$ around $t_{n+1}$. Then, by Taylor's theorem,

$$y(t_n) = y(t_{n+1}) + y'(t_{n+1})(t_{n} - t_{n+1}) + \frac{1}{2}y''(\xi) (t_n - t_{n+1})^2 $$

for some $\xi \in (t_n, t_{n+1})$. This simplifies to

$$y_n = y_{n+1} - h f(t_{n+1}, y_{n+1}) + \frac{h^2}{2} y''(\xi) $$

Plug this in to your expression for $\tau_{n+1}$ to obtain the result they wanted.

Part two

This is an optional part of my answer, because of a pet peeve I have. The answer I gave above assumes that the truncation error is defined in the way that you gave in your original question. However, this is not how the truncation error should be defined, in my opinion. The correct definition should be

$$ h\tau_{n+1} = y_{n+1} - \Phi(t_n, y_n),$$

where $\Phi(t_n, y_n)$ is the approximate value of $y_{n+1}$ obtained assuming we have the exact value of the true solution $y_n = y(t_n)$. For an explicit method, this definition gives the same truncation error computation as with the first definition. However, for an implicit method, the results differ, though to lowest-order the two definitions will still coincide.

Using this second (and, in my opinion, better) definition, we have

$$ h \tau_{n+1} = y_{n+1} - y_n - h f(t_{n+1}, \Phi(t_n, y_n))$$

Applying Taylor series as before to $y_n$, we obtain

$$ h \tau_{n+1} = h f(t_{n+1}, y_{n+1}) - h f(t_{n+1}, \Phi(t_n, y_n)) - \frac{h^2}{2} y''(\xi)$$

We then expand $f(t_{n+1}, \Phi(t_n, y_n))$ around the point $(t_{n+1}, y_{n+1})$, which yields

\begin{align*} h \tau_{n+1} & = f_y(t_{n+1}, \psi) (y_{n+1} - \Phi(t_n, y_n)) - \frac{h^2}{2} y''(\xi) \\ & = h^2 f_y(t_{n+1}, \psi) \tau_{n+1} - \frac{h^2}{2} y''(\xi), \end{align*}

where $\psi$ is some unknown value between $y_{n+1}$ and $\Phi(t_n, y_n)$, and $f_y$ indicates the partial derivative of $f$ with respect to the second variable. Solving for $\tau$ yields

$$ \tau_{n+1} = - \left(\frac{h}{2}\right) \frac{ y''(\xi) }{1 - h f_y(t_{n+1}, \psi)} $$

To lowest-order in $h$ this expression is still the same as the previous result for $\tau_{n+1}$ using the other definition, since we can expand the denominator via geometric series and the first terms coincide.

$\endgroup$
  • $\begingroup$ I believe there is a small mistake in last step where you solve for $\tau$. The $h$ should be removed from the denominator. $\endgroup$ – Jeroen van Riel Oct 20 '18 at 16:18
  • $\begingroup$ @JeroenvanRiel Thank you, it has been fixed. $\endgroup$ – Christopher A. Wong Oct 30 '18 at 8:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.