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?
If you don't know the symbolic representation of a function, then you can still compute the numerical derivative. Additionally, evaluating the the function at a point is much more efficient than parsing the terms (which you might not know) symbolically.
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).
I use finite differences methods frequently, because its efficiency in functional programming. For single-variables, this is easily better in all situations.
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.
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.
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
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.
10 comments
[ 13.2 ms ] story [ 359 ms ] threadThis 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
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).
I use finite differences methods frequently, because its efficiency in functional programming. For single-variables, this is easily better in all situations.
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
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.
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.