Hack the derivative
codewords.recurse.com
Hack the derivative
1–10 of 36 posts
Re: Hack the derivative
#2Yay for functions which are analytic in some neighborhood. Here’s the original paper from the 60s about the idea in this post:
http://www.math.fsu.edu/~okhanmoh/media/Lyness,%20Moler,%20S...
The latest work on this general topic is http://arxiv.org/pdf/1404.2463.pdf which manages to compute extremely accurate high-order derivatives (“...even the 100th derivative of an analytic function can be computed with near machine precision accuracy using standard floating point arithmetic”!!!), see also http://www.chebfun.org/examples/cheb/Turbo.html
* * *
Anyhow, for folks trying to take derivatives of (or do various other operations to) arbitrary continuous functions, I recommend checking out Chebfun – http://www.chebfun.org – a Matlab library created by a group of applied mathematicians at Oxford.
Instead of just looking at a couple points near some point of interest, Chebfun approximates the continuous function over some interval to near machine precision by a high-degree polynomial, and then operates on that polynomial.
Operations like numerical differentiation are much more accurate when you make the right “global” (i.e. not just at one single point) approximation.
Also check out Nick Trefethen’s book Approximation Theory and Approximation Practice, the first 6 chapters of which are available online: http://www.chebfun.org/ATAP/atap-first6chapters.pdf
Re: Hack the derivative
#3I don't see any mention of automatic differentiation which I thought was the dominant technique in this area. Is there an advantage to the method described in OP (other than mathematical cuteness)?
Re: Hack the derivative
#4I don't see any mention of automatic differentiation which I thought was the dominant technique in this area. Is there an advantage to the method described in OP (other than mathematical cuteness)?
He did link to a book of papers largely about automatic differentiation, http://amzn.com/0898713854 (table of contents here http://bt.pa.msu.edu/cgi-bin/display.pl?name=sfbook)
Re: Hack the derivative
#5I DO think Python libraries can do this already.
Re: Hack the derivative
#6I don't see any mention of automatic differentiation which I thought was the dominant technique in this area. Is there an advantage to the method described in OP (other than mathematical cuteness)?
He did link to a book of papers largely about automatic differentiation, http://amzn.com/0898713854 (table of contents here http://bt.pa.msu.edu/cgi-bin/display.pl?name=sfbook )
I already know that a book on numerical analysis is likely to contain the answer I seek. The point of asking was to avoid a trip to the library since the working memory of someone who has been investigating differentiation techniques also likely contains the answer I seek.
Re: Hack the derivative
#7Earlier quoted context omitted.
He did link to a book of papers largely about automatic differentiation, http://amzn.com/0898713854 (table of contents here http://bt.pa.msu.edu/cgi-bin/display.pl?name=sfbook )
I already know that a book on numerical analysis is likely to contain the answer I seek. The point of asking was to avoid a trip to the library since the working memory of someone who has been investigating differentiation techniques also likely contains the answer I seek.
I don’t quite understand what your question is, so I’m going to assume you were trying to ask, “When would you not want to use automatic differentiation?” I think the main time you can’t get much out of automatic differentiation is when your function is a black box or approximation, e.g. it comes from measuring physical data, or is the output of some kind of simulation, etc. I’m not an expert though.
You can get a lot of hits if you google related keywords (e.g. a query with both terms "numerical differentiation" "automatic differentiation" in quotation marks). But here’s a start, http://alexey.radul.name/ideas/2013/introduction-to-automati...
You can probably get useful advice if you ask on http://scicomp.stackexchange.com or similar.
Re: Hack the derivative
#8Lost me a bit at
Im(f(x+ih))/h
Or is 'Im' just a fn returning the imaginary part of its argument?
EDIT: reading the code following, it's clear that Im is just that.
Re: Hack the derivative
#9Lost me a bit at Im(f(x+ih))/h near the end (that's a fancy I that android FF won't paste). Can anyone explain where 'm' came from? Or is 'Im' just a fn returning the imaginary part of its argument? EDIT: reading the code following, it's clear that Im is just that.
Im is for imaginary part of its argument as you say
Re: Hack the derivative
#10Yay for functions which are analytic in some neighborhood. Here’s the original paper from the 60s about the idea in this post: http://www.math.fsu.edu/~okhanmoh/media/Lyness,%20Moler,%20S... The latest work on this general topic is http://arxiv.org/pdf/1404.2463.pdf which manages to compute extremely accurate high-order derivatives (“...even the 100th derivative of an analytic function can be computed with near machi…
The paper by Lyness and Moler is nice, but if it's really "about the idea in this post" then the fact is somewhat hidden. It's mostly about using the Cauchy integral formula to turn derivatives into integrals, using the Poisson summation formula to relate those to finite sums, and using the Moebius inversion formula to get those relations into a form from which you can extract the derivatives.
Maybe taking a very short partial sum of one of the series in Theorem 2 gives you the result in the blog post here, but that seems rather sledgehammer-to-crack-a-nut-ish when (as the blog post says) all you need is the Cauchy-Riemann equations.
I think it's true that the Lyness-Moler idea of "numerical differentiation by numerical complex integration" was, historically, part of the chain of ideas that led to the very simple "complex-step approximation" discussed in the blog post. But that's a far cry from saying that their paper is "about the idea in this post"!
There's some discussion of the history here: http://blogs.mathworks.com/cleve/2013/10/14/complex-step-dif... where Moler (as in "Lyness and Moler") says "The complex step algorithm that I'm about to describe is much simpler than anything described in that 1967 paper. So, although we have some claim of precedence for the idea of using complex arithmetic on real functions, we certainly cannot claim to have invented today's algorithm."
And yes, Chebfun is very nice.