Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

What is the best method for 1D numeric differentiation? Something as glorious as Gaussian quadrature for numeric integration.

Maybe differential quadrature is such a method? What is its accuracy?

I'm well aware that it is really easy to have symbolic differentiation in the program (automatic differentiation or truly symbolic algorithm). However to use such methods it is necessary to rewrite all functions to be differentiated. Thus one can't differentiate functions imported from libraries.

I need differentiation almost with the machine precision.

share|improve this question
1  
J.M. has already supplied some excellent ways of performing numerical differentiation, including methods like Cauchy's formula. There is a simple method that I use that gets me first derivatives at near machine precision levels. It is the complex step derivative: $f'(x) = \mathrm{Im}(\frac{x + ih}{h})$, where $h$ can be chosen to be the machine epsilon (see citeseerx.ist.psu.edu/viewdoc/… for guidance). It is trivial to implement in any language with a complex number datatype (e.g. Fortran). –  Gilead May 8 '11 at 16:23
    
Ok, I see that J.M. has linked to this method (due to Squire and Trapp) in one of the references. –  Gilead May 8 '11 at 16:24
    
@Gilead: The only reason why I linked to it in the comments instead of my answer is that even though I know it's good, I haven't extensively experimented with it. –  J. M. May 8 '11 at 17:07
    
BTW... I trust that you only want first derivatives? The higher the derivative order, the less likely any of the proposed methods become successful... –  J. M. May 8 '11 at 18:03
add comment

1 Answer 1

up vote 11 down vote accepted

If your function is badly behaved (e.g. noisy, very oscillatory), no method will perform properly (differentiation is numerically very unstable). That being said, for "nice functions", I have good experience with polynomial (Richardson) extrapolation methods. This paper and this paper give hints on how you might write your own implementation. I will note that this is the method implemented in the NAG numerical libraries (with of course a few wrinkles of their own).

There are two possible alternatives if for some reason you don't want to use Richardsonian methods. One is to use Cauchy's differentiation formula:

$$f^\prime(x)=\frac1{2\pi i}\oint_\gamma \frac{f(t)}{(t-x)^2}\mathrm dt$$

where it is up to you to choose a suitable counterclockwise contour $\gamma$ (a circle is customary); the other is to use the "Lanczos derivative":

$$f^\prime(x)=\lim_{h\to 0}\frac{3}{2h^3}\int_{-h}^h t\;f(x+t)\mathrm dt$$

where you either will have to experiment with an appropriate step size $h$, or use some extrapolative procedure.

You will have to experiment with your computing environment to choose.

share|improve this answer
    
This algorithm from the ACM might also be of interest: dx.doi.org/10.1145/362759.362820 (@Netlib: netlib.org/toms/413). See also dx.doi.org/10.1137/0704019 , ams.org/journals/mcom/1968-22-102/S0025-5718-1968-0230468-5/… , dx.doi.org/10.1137/S003614459631241X , and dx.doi.org/10.1145/838250.838251 . You've quite a lot to choose from, if you are able to evaluate your function to differentiate at complex arguments (as with using the Cauchy differentiation formula). –  J. M. May 8 '11 at 16:04
    
Thank you very much for the respond, now I'm studying the techniques connected to Lanczos derivative, at least at the moment they look promising for me. I will report later on the results. As for using complex numbers I don't actually see the point in it. I can't use them to find derivatives of already implemented functions of type $\text{Double} \to \text{Double}$. If I was to reimplement these functions I would rather use dual numbers to have exact (i.e. exact as symbolical ones) derivatives. –  Yrogirg May 8 '11 at 17:41
    
"As for using complex numbers I don't actually see the point in it." - the differentiation problem tends to be a bit more stable if you do complex evaluation versus constraining yourself to evaluating only at real values, but that's why I gave the Richardson and Lanczos methods since I do know that sometimes you can only evaluate at reals... –  J. M. May 8 '11 at 17:57
    
At the end I have abandoned all the numeric techniques and decided to stick to symbolic differentiation. I had to rewrite the program but now at least I have exact differentiation. May be later I will have to return to the issue. –  Yrogirg May 10 '11 at 15:18
    
@Yrogirg: As I said, they're definitely not foolproof, and the process of numerical differentiation itself is unstable to begin with; what I've listed are some of the best ones you can do even with this severe handicap. But indeed having symbolic derivatives is much better than any of my proposals. –  J. M. May 10 '11 at 16:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.