Errors in our estimation of a function- and what does big-O notation have to do with it?

Question

We're given the function $f(x) =e^x$ and we're trying to estimate its second derivative at $x=0$. Here's the estimation formula. $$f''(x)\approx {f(x) - 2f(x+h) + f(x+2h)\over h^2}= P(x)$$ All three points are evenly spaced by a distance $h=0.1$. So I plugged in $x=0$ and everything was going great- I got an estimate for the second derivative at $x=0$. But when it comes to the error, $$f''(0)- P(0)$$ How should I prove that the error is no greater than $O(h)$? Does $O(h)$ make sense, or should it be $O(x)$? What does the big-O notation actually mean? Thanks!

Answer 1

I do not know if this is what you are expecting; so, forgive me if I am off-topic.

Using Taylor series around $h=0$, we have $$f(x+h)=f(x)+h f'(x)+\frac{1}{2} h^2 f''(x)+\frac{1}{6} h^3 f'''(x)+O\left(h^4\right)$$ Replacing $h$ by $2h$ in the previous expansion gives $$f(x+2h)=f(x)+2 h f'(x)+2 h^2 f''(x)+\frac{4}{3} h^3 f'''(x)+O\left(h^4\right)$$ So, replacing, $$f(x) - 2f(x+h) + f(x+2h)=h^2 f''(x)+h^3 f'''(x)+O\left(h^4\right)$$ $${f(x) - 2f(x+h) + f(x+2h)\over h^2}=f''(x)+h f'''(x)+O\left(h^2\right)$$

Answer 2

Formally, to say that the error is $O(h)$ means, in this example, that whenever $h$ is positive but sufficiently close to zero ($0 < h < \delta$, where $\delta$ is some positive constant), then $$ \lvert f''(0) - P(0) \rvert < kh, $$ where $k$ is a constant.

A little less formally, the idea that the error $f''(0) - P(0)$ is $O(h)$ means that there is some kind of upper bound on the size of the error (in either direction); the upper bound depends on $h$ in some way; and if we want to put a better bound on the error, we just need to choose a smaller $h$. For example, if we want half as much error (at most), choose $h$ half as large.

Now let's look at your formula, $$ f''(x)\approx \frac{f(x) - 2f(x+h) + f(x+2h)}{h^2}= P(x). $$ If we define $f(x) =e^x$, this means $$ P(x) = \frac{e^x - 2e^{x+h} + e^{x+2h}}{h^2} = e^x \left( \frac{1 - 2e^h + e^{2h}}{h^2} \right). $$

The usefulness of showing that this is $O(h)$ is that we can then get closer to the true value of $f''(x)$ by making $h$ closer to zero, and we have some idea of how "quickly" any given reduction in $h$ will reduce the error. There is no point really in showing that the error is $O(x)$, even if we could do so, because the idea here is that we were given a specific value of $x$ and asked to determine $f''(x)$ for that value; we do not have the option of making $x$ any closer to zero than the predetermined value we were given.

To prove that the error is $O(h)$ from first principles, without using the fact that the second derivative of $e^x$ is just exactly $e^x$, use a Taylor series to show that $$ P(x) = f''(x) + h f'''(x) + O\left(h^2\right), $$ as shown in the answer by Claude Leibovici, where the $O\left(h^2\right)$ term represents some function $R(h)$ that is $O\left(h^2\right)$. Clearly $h f'''(x)$ is $O(h)$. The sum of an $O(h)$ function and an $O(h^2)$ function is $O(h)$; the absolute value of an $O(h)$ function is $O(h)$; and therefore the error, $$ \lvert f''(0) - P(0) \rvert = \lvert h f'''(x) + O\left(h^2\right) \rvert , $$ is $O(h)$.

If the idea is to confirm that the error is $O(h)$ when we define $f(x) = e^x$, using knowledge of the exact second derivative of $e^x$, then $$ f''(x) - P(x) = e^x - e^x \left( \frac{1 - 2e^h + e^{2h}}{h^2} \right) = e^x \left( 1 - \frac{\left(e^h - 1\right)^2}{h^2} \right). $$ Expand $e^h - 1$ as a series and divide by $h$: \begin{align} \frac{1}{h} \left(e^h - 1\right) & = \frac{1}{h} \left(h + \frac{h^2}{2} + \frac{h^3}{6} + \cdots + \frac{h^n}{n!} + \cdots \right) \\ & = 1 + \frac{h}{2} + \frac{h^2}{6} + \cdots + \frac{h^n}{n!} + \cdots \\ & < 1 + \frac{h}{2} + \frac{h^2}{4} + \cdots + \frac{h^n}{2^n} + \cdots = 1+h; \end{align} therfore, as long as $0 < h < 1$, $ 1 < \dfrac{e^h - 1}{h} < 1 + h $ and $$ 1 < \frac{\left(e^h - 1\right)^2}{h^2} < 1 + 2h + h^2 < 1 + 3h. $$ For $0 < h < 1$, therefore, $$ \lvert f''(x) - P(x) \rvert = e^x \left(\frac{\left(e^h - 1\right)^2}{h^2} - 1 \right) < e^x ((1 + 3h) - 1) = \left(3e^x\right) h, $$ showing that the error is $O(h)$ and giving a specific function of the form $kh$ as the error bound. (With more effort, we could reduce the coefficient $k$ for $0 < h < 1$; but the main point of $O(h)$ is that some such constant coefficient exists.)

---

By the way, I would like to put in a plug for the approximation formula $$ f''(x)\approx \frac{f(x-h) - 2f(x) + f(x+h)}{h^2}= Q(x). $$ For $f(x) = e^x$, this evaluates to \begin{align} Q(x) &= \frac{e^{x-h} - 2e^x + e^{x+h}}{h^2} \\ &= \frac{e^x}{h^2} \left( e^{-h} - 2 + e^h \right) \\ &= \frac{e^x}{h^2} \left( 1 - h + \frac{h^2}{2} - \frac{h^3}{6} + \frac{h^4}{24} - + \cdots + (-1)^n\frac{h^n}{n!} + \cdots\right.\\ & \qquad\qquad {} - 2 \\ & \qquad\qquad \left. {} + 1 + h + \frac{h^2}{2} + \frac{h^3}{6} + \frac{h^4}{24} + \cdots + \frac{h^n}{n!} + \cdots\right) \\ &= \frac{e^x}{h^2} \left(h^2 + \frac{h^4}{12} + \cdots + \frac{2 h^{2m}}{(2m)!} + \cdots\right)\\ &= e^x \left(1 + \frac{h^2}{12} + \cdots + \frac{2 h^{2m-2}}{(2m)!} + \cdots\right)\\ \end{align} It follows that $$ \lvert f''(x) - Q(x) \rvert = Q(x) - e^x = \frac{e^x}{12} h^2 + O(h^4), $$ that is, $Q(x)$ is an $O(h^2)$ approximation of $f''(x) = e^x$ with a fairly low constant factor.