Complex Step Differentiation | Hacker News Reader

Complex Step Differentiation

blogs.mathworks.com

47 pointswfunction8 comments

This is very similar to dual numbers [1] which I find even easier to reason about.

There is an implementation of dual numbers in Julia [2] that is quite fun to play around with. The Optim.jl package [3] uses this to get better derivatives than finite differencing.

[1] http://en.wikipedia.org/wiki/Dual_number

[2] https://github.com/JuliaDiff/DualNumbers.jl

[3] https://github.com/JuliaOpt/Optim.jl

Complex step differentiation is a hack for environments that have built in complex numbers, but that don't allow additional numeric types to be implemented easily. But it's a pretty clever hack.

Ah that makes a lot of sense!

This general case of this method is sometimes called Lagrangian interpolation. As the article describes, there is one caveat with using these formulas: you can only decrease the step size so much before it backfires.

Because you are dividing by h, to decrease it from, say 1e-6, to 1e-8 introduces more error into the result than it removes. (Floating-point division with a numerator and denominator that have a big difference in magnitude is a problem.)

The example problem in the article just happened to be well conditioned because the sine and cosine, and their derivatives, are bound on [-1, 1], but most problems won't be and the complex step method won't help much then either.

To get better accuracy, rather than decrease the step size, you should use a higher-order formula. The three and five-point formulas are common. The Handbook of Mathematical Functions (Abramowitz & Stegun) has a table of coefficients for differentiation formulas up to the sixth order (Table 25.2): http://imgur.com/eRl8w8h

For fun, derive the 8-point formulas.

Not so. Roundoff errors happen because when you add a big number and a small number in finite precision, the result loses information that was in the small number. The magic of complex step differentiation is keeping the small part (the imaginary part) separate from the (potentially) large part (the value of the function evaluated at a real argument).

You can use a very small step size (and so get very high accuracy) with traditional finite difference differentiation at x=0 for functions with f(0) = 0. Complex step differentiation takes advantage of the fact that real valued functions of a real argument have 0 imaginary part everywhere on the real line.

> most problems won't be [well conditioned] and the complex step method won't help much then either

Try coming up with an example of this. You might be able to find one if there is a pole or branch cut very near the real line, but otherwise, complex step differentiation is very robust.

Under what circumstances does one choose an approximate solution over the exact solution especially given that both ways are of more or less the same complexity besides that you have to symbolically calculate the derivative once for the exact solution?

Except in Maple/Mathematica, it's generally not convenient to symbolically calculate the derivative.

This method will also work if, for example, you want to compute W'(z), Gamma'(z), or other special functions.

http://en.wikipedia.org/wiki/Lambert_W_function

http://en.wikipedia.org/wiki/Gamma_function

One nice thing about this technique is that its time complexity is essentially the same as evaluating the original function. This property is shared by dual number differentiation mentioned by iadunning above.

Try symbolically differentiating deeply nested functions, and you will see that you end up with n^2 terms, where n is the depth of the nesting. E.g. Try differentiating n = 10 for (i=0; i<n; i++) x = sin(x)

Then notice that evaluating this function with a complex argument is only O(n), not O(n^2).

Reply on news.ycombinator.com