Real Derivatives from Imaginary Increments

The solution of many problems requires us to compute derivatives. Complex step differentiation is a method of computing the first derivative of a real function, which circumvents the problem of roundoff error found with typical finite difference approximations.

Rounding error and formula error as functions of step size {h} [Image from Wikimedia Commons].

For finite difference approximations, the choice of step size {h} is crucial: if {h} is too large, the estimate of the derivative is poor, due to truncation error; if {h} is too small, subtraction will cause large rounding errors. The finite difference formulae are ill-conditioned and, if {h} is very small, they produce zero values.

Where it can be applied, complex step differentiation provides a stable and accurate method for computing {f^\prime(x)}.

Finite differences and derivatives

We define the derivative of a function {f(x)} as the limit

\displaystyle f^\prime(x) = \lim_{h\rightarrow 0}\left[\frac{f(x+h)-f(x)}{h}\right]

For finite {h}, we can use Taylor’s theorem to estimate the accuracy:

\displaystyle f(x+h) = f(x) + h f^\prime(x) + O(h^2)

which means that

\displaystyle f^\prime(x) = \left[\frac{f(x+h)-f(x)}{h}\right] + O(h) \,. \ \ \ \ \ \ \ \ \ \ \ (1)

By making {h} small, we can get a precise estimate of the derivative. But there is a problem: the limit on the precision of numbers in the computer means that, as {h} becomes smaller, the difference {f(x+h)-f(x)} looses precision and, ultimately, {f(x+h)} becomes indistinguishable from {f(x)}, giving a zero value for the approximation.

We may allow the step to be complex: taking a pure imaginary increment, we have

\displaystyle f(x+ih) = f(x) + ih f^\prime(x) - \textstyle{\frac{1}{2}}h^2 f^{\prime\prime}(x) + O(h^3)

Taking the imaginary part and dividing by {h} gives us

\displaystyle f^\prime(x) = \Im\left\{\frac{f(x+ih)}{h}\right\} + O(h^2) \ \ \ \ \ \ \ \ (2)

This yields a second order accuracy. Moreover, since no difference between function values is required, it is free from the roundoff errors that contaminate (1) for small {h}.

A Numerical Example

Log error of approximations to the derivative at {x=1} of {f(x)=x^3}. Dashed line: finite difference (1); Solid line: Complex step approximation (2).

In the figure, we show the logarithm of the error of approximations to the derivative, at {x=1}, of {f(x)=x^3}. The dashed red line is for the first-order finite difference approximation (1). For {h>10^{-8}} the error decreases linearly with {h} consistent with the first-order accuracy of (1). For {h<10^{-8}} the error actually gets larger as {h} decreases. This is due to roundoff errors in computing the difference {(f(x+h)-f(x))}.

The solid blue line in the figure is for the second-order complex step approximation (2). The error has a slope of 2, consistent with the second-order accuracy of (2). It decreases rapidly as the step size {h} is decreased. Since there is no difference calculation in (2), roundoff error is not a problem. For {h<10^{-8}}, the error is obliterated by rounding and the value of {f^\prime(x)} is exact. Rounding actually leads to an improvement in this case! For double precision floating point computing, with about 16 digits accuracy, we may choose {h=10^{-8}}, so that error is at the level of machine precision.

Cauchy-Riemann Equations

The magical formula (2) can be understood in terms of the theory of holomorphic functions. We can regard {f(x)} as the real part of a function {F(z)} of a complex variable {z = x+iy}:

\displaystyle F(z) = f(x+iy) + i g(x+iy)

We will be concerned with functions that are real for real {x}:

\displaystyle F(z) = f(x) \quad \mbox{for} \quad z=x\in\mathbb{R} \,.

If {F(z)} is holomorphic, the real and imaginary parts are related by the Cauchy-Riemann equations

\displaystyle \frac{\partial f}{\partial x} = \frac{\partial g}{\partial y} \,, \qquad \frac{\partial f}{\partial y} = -\frac{\partial g}{\partial x} \,.

Since {F(z)} is real-valued on the real line, {g(x)=0} and {\partial g/\partial x = 0}. Therefore, {\partial f/\partial y = 0} on the real line, and also {F(z)=f(x)} so that {\partial F/\partial x=\partial f/\partial x} for real {z}. Thus,

\displaystyle \frac{\partial f}{\partial x} = \frac{\partial g}{\partial y} = \Im\left\{\frac{\partial F}{\partial y}\right\} \quad\mbox{on the real line.}

We approximate {\partial F/\partial y} by taking a finite step {ih}, noting that {\Im\{F(x)\}=0}, whence

\displaystyle \frac{\partial F}{\partial x} \approx \Im\left\{\frac{F(x+ih)}{h}\right\} \,,

which is consistent with (2).

Conclusion

In cases where we can easily calculate {F(z)} but have no simple expression for {F^\prime(z)}, the complex step approximation gives us an accurate and numerically robust means of computing the derivative. It has been applied with great effect in a wide variety of circumstances.

Sources

{\bullet} Higham, N. J., 2018: Differentiation With(out) a Difference. SIAM News, 51 (5), p. 2. URL.

{\bullet} Squire, William and George Trapp, 1998: Using complex variables to estimate derivatives of real functions, SIAM Review 40, 110–112.

{\bullet} Wikipedia article: Numerical differentiation.

* * * * *

That’s Maths II: A Ton of Wonders

by Peter Lynch now available.
Full details and links to suppliers at
http://logicpress.ie/2020-3/

>>  Review in The Irish Times  <<

* * * * *


Last 50 Posts

Categories