Proof that the Trapezoidal Method for solving IVP is $O(h^3)$

Question

My question comes from Chapter 6 of the book Introduction to Numerical Analysis, 2nd edition, by Kendall Atkinson. In section 6.5, p.368-369, the author proves that the Trapezoidal method for solving the initial value problem $$ \begin{cases} Y'(x) = f(x,Y(x)) \\ Y(x_0) = Y_0 \end{cases} \quad \qquad (\text{IVP}) $$

has a local error of $O(h^3)$. The trapezoidal rule for numerical integration is given as

$$ Y(x_{n+1}) = Y(x_n) + \frac{h}{2}\left[f(x_n,Y(x_n)) + f(x_{n+1},Y(x_{n+1})) \right] - \frac{h^3}{12} Y^{(3)}(\xi_n) \hspace{2cm} (6.5.1) $$

for some $\xi_n \in [x_n,x_{n+1}]$. (Here, $x_0,x_1,\ldots$ are the nodes and $h > 0$ is the step size.) The trapezoidal method is given as $$ \quad y_{n+1} = y_n + \frac{h}{2}[f(x_n,y_n) + f(x_{n+1},y_{n+1})], \qquad n \geq 0 \hspace{3cm} (6.5.2) $$

where $y_n$ is the numerical approximation to the true solution $Y(x_n)$. The book's proof that the local error of (6.5.2) is $O(h^3)$ goes as follows [I have modified the numbering of some equations for convenience.]:

Let $u_n(x)$ denote the solution of $Y'(x) = f(x,Y(x))$ that passes through $(x_n,y_n)$: $$ u_n'(x) = f(x,u_n(x)), \qquad u_n(x_n) = y_n. $$

Applying the derivation that led to (6.5.1), we have $$ \quad u_n(x_{n+1}) = y_n + \frac{h}{2} \left[f(x_n,y_n) + f(x_{n+1},u_n(x_{n+1})) \right] - \frac{h^3}{12}u_n^{(3)}(\xi_n) \qquad (6.5.10) $$

for some $\xi_n \in [x_n,x_{n+1}]$. Let $\tilde{e}_{n+1} = u_n(x_{n+1}) - y_{n+1}$, which we call the local error in computing $y_{n+1}$ from $y_n$. Subtract (6.5.2) from the preceding to obtain \begin{align*} \tilde{e}_{n+1} &= \frac{h}{2}\left[f(x_{n+1},u_n(x_{n+1})) - f(x_{n+1},y_{n+1}) \right] - \frac{h^3}{12} u_n^{(3)}(\xi_n) && \quad (6.5.11) \\[5pt] &= \frac{h}{2}f_y(x_{n+1},y_{n+1}) \tilde{e}_{n+1} + O(h\tilde{e}_{n+1}^2) - \frac{h^3}{12} u_n^{(3)}(x_n) + O(h^4) && \quad (6.5.12) \end{align*} where we have twice applied the mean value theorem. It can be shown that for all sufficiently small $h$, $$ \tilde{e}_{n+1} = O(h^3). $$

More precisely, \begin{align*} \tilde{e}_{n+1} = \left[1 - \frac{h}{2} f_y(x_{n+1},y_{n+1}) \right]^{-1} \left[ - \frac{h^3}{12} u_n^{(3)}(x_n) + O(h^4) \right] \\[5pt] = -\frac{h^3}{12}u_n^{(3)}(x_n) + O(h^4) \hspace{2cm} (6.5.13) \end{align*}

---

My questions:

1. How exactly was (6.5.12) obtained from (6.5.11)? I do not see how the mean value theorem was applied.
   

2. In going from (6.5.12) to (6.5.13), the $O(h\tilde{e}_{n+1}^2)$ term was dropped. What allows us to do this?

In my attempt to obtain (6.5.12), I Taylor expanded the function $y \mapsto f(x_{n+1},y)$ about $y = y_{n+1}$ to get \begin{align*} f(x_{n+1},u_n(x_{n+1})) = f(x_{n+1},y_{n+1}) + f_y(x_{n+1},y_{n+1})(u_n(x_{n+1}) - y_{n+1}) + f_{yy}(x_{n+1},\zeta_{n+1})\frac{(u_n(x_{n+1})-y_{n+1})^2}{2!} \end{align*} for some $\zeta_{n+1}$ between $y_{n+1}$ and $u_n(x_{n+1})$. Therefore, \begin{align*} f(x_{n+1},u_n(x_{n+1})) - f(x_{n+1},y_{n+1}) = f_y(x_{n+1},y_{n+1}) \tilde{e}_{n+1} + O(\tilde{e}_{n+1}^2). \end{align*}

Now plugging this into (6.5.11) gives me \begin{align*} \tilde{e}_{n+1} = \frac{h}{2} f_y(x_{n+1},y_{n+1}) \tilde{e}_{n+1} + O(h \tilde{e}_{n+1}^2) - \frac{h^3}{12} u_n^{(3)}(\xi_n). \end{align*}

But this is missing the $O(h^4)$ term...So where did I go wrong? ...Or is the book wrong?

Answer 1

Figured it out, thanks to the help of my professor.

1. As I wrote in my post, Taylor's theorem applied to the function $y \mapsto f(x_{n+1},y)$ gives \begin{align*} f(x_{n+1},u_n(x_{n+1})) - f(x_{n+1},y_{n+1}) = f_y(x_{n+1},y_{n+1}) \tilde{e}_{n+1} + O(\tilde{e}_{n+1}^2). \end{align*}

It follows that \begin{align*} \tilde{e}_{n+1} = \frac{h}{2}f_y(x_{n+1},y_{n+1}) + O(h\tilde{e}_{n+1}^2) - \frac{h^3}{12} u_n^{(3)}(\xi_n). \end{align*}

Now by Taylor's theorem applied to the function $u_n^{(3)}$, we have $$ u_n^{(3)}(\xi_n) = u_n^{(3)}(x_n) + O(h). $$

Therefore, \begin{align*} \frac{h^3}{12} u_n^{(3)}(\xi_n) = \frac{h^3}{12} u_n^{(3)}(x_n) + O(h^4) \end{align*}

and hence \begin{align*} \tilde{e}_{n+1} = \frac{h}{2}f_y(x_{n+1},y_{n+1}) \tilde{e}_{n+1} + O(h\tilde{e}_{n+1}^2) - \frac{h^3}{12} u_n^{(3)}(x_n) + O(h^4), \end{align*}

as claimed. (I still do not see how the above could be obtained via the Mean Value Theorem. Oh well...)

2. Let $r \geq 0$ be the largest integer for which $\tilde{e}_{n+1} = O(h^r)$. It's easy to see that $r$ must be positive: If $r = 0$, then $\tilde{e}_{n+1}$ would just be a constant, and so taking the limit as $h \to 0$ in (6.5.12) would give $\tilde{e}_{n+1} = 0$ (for all $n$), which clearly cannot be true for an arbitrary IVP. Moreover, if $r = 1$ then the RHS of (6.5.12) is
\begin{align*} O(h^2) + O(h^3) + O(h^3) + O(h^4) = O(h^2) \end{align*}

and hence $\tilde{e}_{n+1} = O(h^2)$, which is a contradiction. Hence, $r \geq 2$ and so $2r + 1 \geq 5$. Therefore, $O(h\tilde{e}_{n+1}^2) = O(h^4)$, and so is aborbed by the $O(h^4)$ term.