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 <<

* * * * *

ThatsMaths