Finite difference approximation error

Question

I was reading Scientific Computin, An Introductory Survey, by Michael Heath. In the Example 1.11, he madr a Finite Difference Aproximation, with the usual approxination : $f’(x)\neq \frac{f(x+h)-f(x)}{h}$. He postules the following:

We want h to be small so that the approximation will be accurate, but if h is too small, then fl(x + h) may not differ from fl(x). Even if $fl(x + h)\neq fl(x)$, we might still have $fl(f(x + h)) = fl(f(x))$ if $f$ is slowly varying. In any case, we can expect some cancellation in computing the difference $f (x + h) − f (x).$ Thus, there is a trade-off between truncation error and rounding error in choosing the size of h. If the relative error in the function values is bounded by ε, then the rounding error in the approximate derivative value is bounded by $2ε|f(x)|/h$. The Taylor series expansion $$f (x + h) = f (x) + f ′ (x)h + f ′′ (x)h2 /2 + · · ·$$ gives an estimate of $Mh/2$ for the truncation error, where M is a bound for $|f′′(x)|.$

I would like to know how could he get both errors, I can’t get the results he is giving. Any idea would be great

Answer 1

Take the Taylor series and re-arrange it to be $$ f'(x) - \frac{f(x+h)-f(x)}{h} = - f''(x) \frac{h}{2} - f'''(x) \frac{h^2}{3!} - f^{(4)}(x) \frac{h^3}{4!} + \ldots $$

Assuming that $f^{(n)}(x)$ is not growing significantly faster than $h^{n}/n!$, then these terms are much smaller than the leading dominant term $f''(x)\frac{h}{2}$.

There is a way to mathematically formalize this using Big-O notation. We would say that

\begin{align} \left|f'(x) - \frac{f(x+h)-f(x)}{h}\right| &\le M \frac{h}{2} \left(|f''(x)| + \frac{2 h}{3!} |f'''(x)| + \ldots + \frac{2 h^{n-1}}{n!} |f^{(n)}(x)|\right) & \mathrm{for~all~}h \le h_0 \end{align}

However, since we are assuming the higher derivatives aren't growing fast compared to their leading coefficient, we can keep just the dominant term, leaving \begin{align} \left|f'(x) - \frac{f(x+h)-f(x)}{h}\right| &\le M \frac{h}{2} |f''(x)| & \mathrm{for~all~}h \le h_0 \end{align}

That is to say the finite difference approximation error grows similarly to the function $g(x) = h$. We then say the error is $O(h)$ because the leading dominant term scales with $h$, the one parameter we have some control over. This analysis of course assumes exact mathematics.

On the flip side, when we are trying to approximate the error on the low side we need to consider the floating point approximation error associated with performing any math operation.

Suppose we could analytically find the nearest floating point value to the mathematical $f(x)$. The largest possible difference between the nearest floating point to a value $f(x)$ is $\frac{\epsilon}{2} |f(x)|$ (since we don't know if the rounding was up or down to machine precision). We will now assume that $\mathrm{float}(f(x))$ and $\mathrm{float}(f(x+h))$ are separated by at most one ULP. The worse case floating point rounding scenario would then be something like this:

Thus we could say that within this 2 ULP region we really don't know how things will round without higher precision mathematics. Then attempting to take into consideration the division we end up with the error being bounded by $2 \epsilon |f(x)| / h$.