8
$\begingroup$

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?

$\endgroup$
  • 5
    $\begingroup$ 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$. $\endgroup$ – Brian Borchers Jun 11 '13 at 3:34
  • 1
    $\begingroup$ It would help if you could give a more concrete statement, or at least an exact reference (theorem and page), for this bound. $\endgroup$ – Christian Clason Jun 13 '13 at 22:42
1
+50
$\begingroup$

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)$$

$\endgroup$
  • $\begingroup$ Of course if $h\gg R$ then the truncation error of $O(h^2)$ becomes dominant in comparison to the term of $O(R/h)$ $\endgroup$ – SimonSciComp Nov 30 '14 at 19:42
  • $\begingroup$ ahh, I completely forgot about this bounty! Anyway this does seem to cover it pretty well. $\endgroup$ – David Z Dec 3 '14 at 12:11
-1
$\begingroup$

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$.

$\endgroup$
  • 2
    $\begingroup$ This gives you a bound on the value $|f'^-|$ of $f'^-$, not on the error $|f'^- - f'|$. $\endgroup$ – Christian Clason Jun 13 '13 at 10:46

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.