8

Suppose a function $f$ can be computed such that the bound on the relative error is $R$ i.e. $f^-(x) = f(x)(1+r)$ where $f^-$ and $f$ are respectively the computed and exact value $f$ and $|r| \leq R$

I want to bound the relative error of the following derivative approximations in terms of $h$ and $R$ for a general $f$

\begin{align*} f^{'}(x) &\approx \frac{f(x+h)-f(x-h)}{2h}\\ f^{''}(x)&\approx \frac{f(x+h)-2f(x)+f(x-h)}{h^2} \end{align*}

In Ralston and Rabinowitz the bounds are given to be $\frac{R}{h}$ and $\frac{4R}{h^2}$ respectively. But this has not been proven and has been mentioned in passing as part of an explanation about Richardson Extrapolation.

Any ideas on its proof?

smilingbuddha
  • 645
  • 5
  • 10
  • 5
    The formulas that you've given don't include both terms in the error- you can have error due to the inaccuracy in the evaluation of $f$ and also due to truncation error ($h$ is too large.) In the extreme case that $R=0$ (exact evaluation of the function), the formulas you've listed would give 0 errors, but there's still be truncation error to account for. It's a good exercise to derive the formulas for the truncation error and the error due to inaccurate function evaluations and then see how the total error varies with $h$. – Brian Borchers Jun 11 '13 at 03:34
  • 1
    It would help if you could give a more concrete statement, or at least an exact reference (theorem and page), for this bound. – Christian Clason Jun 13 '13 at 22:42

2 Answers2

1

This theorem has either been mis-interpreted by the question author or there is a mistake in the referenced book. Consider the following counter example:

$$f(x) = 100+x$$ $$h=0.01$$ $$R = 0.01$$

At $x=0$ the absolute error in each function evaluation is $100*0.01=1$, so we have $$f'^-(0) = \frac{f^-(h) - f^- (-h)}{2h} = \frac{(100+0.01)\pm 1 - ((100-0.01) \pm 1)}{0.02} $$ $$ \implies f'^-(0) = \frac{0.02}{0.02} \pm \frac{1}{0.02}\pm \frac{1}{0.02}$$ In the worst case scenario, the two error terms have the same sign and do not cancel out. The relative error of the derivative approximation can therefore be as much as $100$, which is much greater than $R/h = 1$.

As far as I can tell there is no bound on the relative error for a general $f$ since by choosing a function of the form $f(x) = n+x$, the relative error in the derivative approximation can always be increased simply by increasing $n$.

On the other hand we can calculate a bound dependent on $f$. The bound on the absolute error for sufficiently small $h$ and $R$ is: $$ f'^-(x) = \frac{f(x+h)-f(x-h)}{2h} \pm \frac{f(x)R}{h} $$ Proof: $$f^-(x+h) = (f(x)+hf'(x))(1 \pm R)$$ $$ \implies f^-(x+h) =f(x)+hf'(x)\pm Rf(x)$$ where we Taylor expand $f$ around $x$ and neglect terms of order $hR$ or $h^2$ or higher since both $h$ and $R$ are small. Similarly $$ f^-(x-h) = f(x) - hf'(x) \pm Rf(x)$$ Therefore $$f'^-(x) = \frac{2hf'(x) \pm Rf(x) \pm Rf(x)}{2h} $$ $$ \implies f'^-(x) =f'(x) \pm \frac{Rf(x)}{h}$$ where we once again consider the worst case scenario, in which the errors add up.

The bound on the relative error is therefore dependent on $f(x)$ and can be expressed as $$ f'^-(x) = f'(x)\left(1\pm\frac{Rf(x)}{hf'(x)}\right) $$

Similarly we have $$f''^-(x) = f''(x)\left(1 \pm \frac{4Rf(x)}{h^2f''(x)}\right)$$

SimonSciComp
  • 311
  • 2
  • 9
-1

To answer your direct question (and not cater for Brian Borchers comment re truncation error):

By the definition you have for $f^-$, its relative error $|(f^--f)/f|\leq R$, and your definition doesn't say it explicitly, but $r$ isn't constant, so the relative error in $|f^-(x+h)-f^-(x-h)| $ is $\leq 2R$.

This leads directly to the relative errors for $f^{'-}$ to be $R/h$ and similarly for $f^{''-}$ to be $4R/h^2$.

Mark Hurd
  • 103
  • 5