Numerical differentiation

Step size

An important consideration in practice when the function is calculated using floating-point arithmetic of finite precision is the choice of step size, h. To illustrate, consider the two-point approximation formula with error term:

$${\displaystyle f^{\prime }(x)=\frac{f(x+h)-f(x-h)}{2h}-\frac{f^{(3)}(c)}{6}{h}^2}$$

where ${\displaystyle c}$ is some point between ${\displaystyle x-h}$ and ${\displaystyle x+h}$. Let ${\displaystyle e(x)}$ denote the roundoff error encountered when evaluating the function ${\displaystyle f(x)}$ and ${\displaystyle \hat{f}(x)}$ denote the computed value of ${\displaystyle f(x)}$. Therefore, $${\displaystyle f(x)=\hat{f}(x)+e(x).}$$ The total error in the approximation is $${\displaystyle f^{\prime }(x)-\frac{\hat{f}(x+h)-\hat{f}(x-h)}{2h}=\underset{\text{Roundoff error}}{\underbrace{\frac{e(x+h)-e(x-h)}{2h}}}-\underset{\text{Truncation error}}{\underbrace{\frac{f^{(3)}(c)}{6}{h}^2}}.}$$ Assuming that the roundoff errors are bounded by some number ${\displaystyle \epsilon >0}$ and the third derivative of ${\displaystyle f(x)}$ is bounded by some number ${\displaystyle M>0}$, we get $${\displaystyle \left|f^{\prime }(x)-\frac{\hat{f}(x+h)-\hat{f}(x-h)}{2h}\right|\le \frac{\epsilon }{h}+\frac{h^2}{6}M.}$$

To reduce the truncation error ${\displaystyle \frac{h^2}{6}M}$, we must reduce h. But as h is reduced, the roundoff error ${\displaystyle \frac{\epsilon }{h}}$ increases. Due to the need to divide by the small value h, all the finite-difference formulae for numerical differentiation are similarly ill-conditioned.

If instead the derivative is approximated using ${\displaystyle f^{\prime }(x)=\frac{f(x+h)-f(x)}{h}}$ and we assume the relative approximation error due to rounding is bounded by machine epsilon and the values ${\displaystyle |f^{″}(x)|}$ and ${\displaystyle |f(x)|}$ are bounded on ${\displaystyle [x_0,x_0+h]}$ by ${\displaystyle M_1}$and ${\displaystyle M_2}$ respectively it can be shown that:$${\displaystyle \left|f^{\prime }(x_0)-\frac{\hat{f}(x_0+h)-\hat{f}(x_0)}{h}\right|\le \frac{h}{2}{M}_1+\frac{2\epsilon }{h}{M}_2}$$By minimizing this upper bound an estimate for the optimal step size can be obtained. However, employing this method would require the knowledge of the bounds ${\displaystyle M_1}$ and ${\displaystyle M_2}$. Instead, if an approximate upper bound is used - one where ${\displaystyle M_1}$and ${\displaystyle M_2}$ are replaced by ${\displaystyle |f^{″}(x_0)|}$ and ${\displaystyle |f(x_0)|}$ the error can be estimated as:$${\displaystyle e(h)=\frac{h}{2}|f^{″}(x_0)|+\frac{2\epsilon }{h}|f(x_0)|}$$By minimizing ${\displaystyle e(h)}$ an estimate for the optimal step size h can be found: $${\displaystyle h=2\sqrt{\epsilon \left|\frac{f(x)}{f^{″}(x)}\right|}}$$(though not when ${\displaystyle f^{″}(x)=0}$). If no information about the function ${\displaystyle f}$ is known, sometimes the approximation ${\displaystyle \sqrt{\left|\frac{f(x)}{f^{″}(x)}\right|}\approx x}$ is used giving a choice for h that is small without producing a large rounding error: ${\displaystyle \sqrt{\epsilon }x}$, where the machine epsilon ε is typically of the order of 2.2×10⁻¹⁶ for double precision. In practice, one cannot compute the value that minimizes the above error bounds and therefore cannot compute an approximation of the optimal step size without information about higher-order derivatives.

Example

To demonstrate this difficulty, consider approximating the derivative of the function $${\displaystyle f(x)=\frac{2x}{1+\sqrt{x}}}$$ at the point ${\displaystyle x_0=9}$. In this case, we can calculate $${\displaystyle f^{\prime }(x)=\frac{2+\sqrt{x}}{(1+\sqrt{x}{)}^2}}$$ which gives $${\displaystyle f^{\prime }(9)=\frac{2+\sqrt{9}}{(1+\sqrt{9}{)}^2}=\frac{2+3}{(1+3{)}^2}=\frac{5}{16}=\mathrm{0.3125.}}$$ Using 64-bit floating point numbers, the following approximations are generated with the two-point approximation formula and increasingly smaller step sizes. The smallest absolute error is produced for a step size of ${\displaystyle {10}^{-4}}$, after which the absolute error steadily increases as the roundoff errors dominate calcuations.

For computer calculations the problems are exacerbated because, although x necessarily holds a representable floating-point number in some precision (32 or 64-bit, etc.), x + h almost certainly will not be exactly representable in that precision. This means that x + h will be changed (by rounding or truncation) to a nearby machine-representable number, with the consequence that (x + h) − x will not equal h; the two function evaluations will not be exactly h apart. In this regard, since most decimal fractions are recurring sequences in binary (just as 1/3 is in decimal) a seemingly round step such as h = 0.1 will not be a round number in binary; it is 0.000110011001100...₂ A possible approach is as follows:

h := sqrt(eps) * x; xph := x + h; dx := xph - x; slope := (F(xph) - F(x)) / dx;

However, with computers, compiler optimization facilities may fail to attend to the details of actual computer arithmetic and instead apply the axioms of mathematics to deduce that dx and h are the same. With C and similar languages, a directive that xph is a volatile variable will prevent this.

Three Point methods

To obtain more general derivative approximation formulas for some function ${\displaystyle f(x)}$, let ${\displaystyle h>0}$ be a positive number close to zero. The Taylor expansion of ${\displaystyle f(x)}$ about the base point ${\displaystyle x}$ is

Replacing ${\displaystyle h}$ by ${\displaystyle 2h}$ gives

Multiplying identity (1) by 4 gives

Subtracting identity (1') from (2) eliminates the ${\displaystyle h^2}$ term:

$${\displaystyle f(x+2h)-4f(x+h)=-3f(x)-2h{f}^{\prime }(x)+\frac{4h^3}{3!}{f}^{‴}(x)+...}$$

which can be written as

$${\displaystyle f(x+2h)-4f(x+h)=-3f(x)-2h{f}^{\prime }(x)+O(h^3).}$$

Rearranging terms gives $${\displaystyle f^{\prime }(x)=\frac{-3f(x)+4f(x+h)-f(x+2h)}{2h}+O(h^2),}$$

which is called the three-point forward difference formula for the derivative. Using a similar approach, one can show

$${\displaystyle f^{\prime }(x)=\frac{f(x+h)-f(x-h)}{2h}+O(h^2)}$$ which is called the three-point central difference formula, and $${\displaystyle f^{\prime }(x)=\frac{f(x-2h)-4f(x-h)+3f(x)}{2h}+O(h^2)}$$ which is called the three-point backward difference formula.

By a similar approach, the five point midpoint approximation formula can be derived as: $${\displaystyle f^{\prime }(x)=\frac{-f(x+2h)+8f(x+h)-8f(x-h)+f(x-2h)}{12h}+O(h^4).}$$

Numerical Example

Consider approximating the derivative of ${\displaystyle f(x)=x\sin x}$ at the point ${\displaystyle x_0=\frac{\pi }{4}}$.

Since ${\displaystyle f^{\prime }(x)=\sin x+x\cos x}$, the exact value is $${\displaystyle f^{\prime }\left(\frac{\pi }{4}\right)=\sin \left(\frac{\pi }{4}\right)+\frac{\pi }{4}\cos \left(\frac{\pi }{4}\right)=\frac{1}{\sqrt{2}}+\frac{\pi }{4\sqrt{2}}\approx \mathrm{1.2624671484563432.}}$$

Algorithms

The following pseudocode describes the various three point differentiation formulas.

Three-Point Forward Difference

<b id="mwAco">input:</b> Real valued function, <i id="mwAcs">f</i> The point at which to approximate the derivative, <i id="mwAcw">a</i> The step size, <i id="mwAc0">h</i> <b id="mwAc4">output:</b> An approximation of <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt229" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"f'(a)"}}' id="mwAc8"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle f'(a)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>f</mi> <mo>′</mo> </msup> <mo stretchy="false">(</mo> <mi>a</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f'(a)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d98c61769b4906b6c0bd72f9de874410c7bf0d3f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.044ex; height:3.009ex;" alt="{\displaystyle f'(a)}"/></span> <b id="mwAdA">return</b> ((-3/2)*<i id="mwAdE">f</i>(<i id="mwAdI">a</i>) + 2*<i id="mwAdM">f</i>(<i id="mwAdQ">a</i>+<i id="mwAdU">h</i>) - (1/2)*<i id="mwAdY">f</i>(<i id="mwAdc">a</i>+2*<i id="mwAdg">h</i>)) / <i id="mwAdk">h</i>

Three-Point Central Difference

<b id="mwAdw">input:</b> Real valued function, <i id="mwAd0">f</i> The point at which to approximate the derivative, <i id="mwAd4">a</i> The step size, <i id="mwAd8">h</i> <b id="mwAeA">output:</b> An approximation of <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt230" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"f'(a)"}}' id="mwAeE"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle f'(a)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>f</mi> <mo>′</mo> </msup> <mo stretchy="false">(</mo> <mi>a</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f'(a)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d98c61769b4906b6c0bd72f9de874410c7bf0d3f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.044ex; height:3.009ex;" alt="{\displaystyle f'(a)}"/></span> <b id="mwAeI">return</b> ((-1/2)*<i id="mwAeM">f</i>(<i id="mwAeQ">a</i>-<i id="mwAeU">h</i>) + (1/2)*<i id="mwAeY">f</i>(<i id="mwAec">a</i>+<i id="mwAeg">h</i>)) / <i id="mwAek">h</i>

Three-Point Backward Difference

<b id="mwAew">input:</b> Real valued function, <i id="mwAe0">f</i> The point at which to approximate the derivative, <i id="mwAe4">a</i> The step size, <i id="mwAe8">h</i> <b id="mwAfA">output:</b> An approximation of <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt231" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"f'(a)"}}' id="mwAfE"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle f'(a)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>f</mi> <mo>′</mo> </msup> <mo stretchy="false">(</mo> <mi>a</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f'(a)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d98c61769b4906b6c0bd72f9de874410c7bf0d3f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.044ex; height:3.009ex;" alt="{\displaystyle f'(a)}"/></span> <b id="mwAfI">return</b> ((1/2)*<i id="mwAfM">f</i>(<i id="mwAfQ">a</i>-2*<i id="mwAfU">h</i>) - 2*<i id="mwAfY">f</i>(<i id="mwAfc">a</i>-<i id="mwAfg">h</i>) + (3/2)*<i id="mwAfk">f</i>(<i id="mwAfo">a</i>)) / <i id="mwAfs">h</i>

Higher derivatives

Using Taylor Series, it is possible to derive formulas to approximate the second (and higher order) derivatives of a general function. For a function ${\displaystyle f(x)}$ and some number ${\displaystyle h>0}$, expanding it about ${\displaystyle x+h}$ and ${\displaystyle x-h}$ gives

$${\displaystyle f(x+h)=f(x)+f^{\prime }(x)h+\frac{1}{2}{f}^{″}(x)h^2+\frac{1}{6}{f}^{‴}(x)h^3+\frac{1}{24}{f}^{(4)}({\xi }_1)h^4}$$ and $${\displaystyle f(x-h)=f(x)-f^{\prime }(x)h+\frac{1}{2}{f}^{″}(x)h^2-\frac{1}{6}{f}^{‴}(x)h^3+\frac{1}{24}{f}^{(4)}({\xi }_2)h^4}$$ where ${\displaystyle x-h<{\xi }_2<x<{\xi }_1<x+h}$. Adding these two equations gives

$${\displaystyle f(x+h)+f(x-h)=2f(x)+f^{″}(x)h^2+\frac{1}{24}\left[f^{(4)}({\xi }_1)+f^{(4)}({\xi }_2)\right]h^4.}$$

If ${\displaystyle f^{(4)}}$ is continuous on ${\displaystyle [x-h,x+h]}$, then ${\displaystyle \frac{1}{2}\left[f^{(4)}({\xi }_1)+f^{(4)}({\xi }_2)\right]}$ is between ${\displaystyle f^{(4)}({\xi }_1)}$ and ${\displaystyle f^{(4)}({\xi }_2)}$. The Intermediate Value Theorem guarantees a number, say ${\displaystyle \xi }$, between ${\displaystyle {\xi }_1}$ and ${\displaystyle {\xi }_2}$. We can therefore write

$${\displaystyle f^{″}(x)=\frac{1}{h^2}\left[f(x-h)-2f(x)+f(x+h)\right]-\frac{h^2}{12}{f}^{(4)}(\xi ).}$$

where ${\displaystyle x-h<\xi <x+h}$.

Numerical Example

Consider approximating the second derivative of the function ${\displaystyle f(x)=e^x\sin x}$ at the point ${\displaystyle x_0=\frac{\pi }{4}}$.

Since ${\displaystyle f^{″}(x)=2e^x\cos x}$, the exact value is ${\displaystyle f^{″}(\frac{\pi }{4})=\sqrt{2}{e}^{\frac{\pi }{4}}\approx 3.1017663}$.

Arbitrary Derivatives

Using Newton's difference quotient, $${\displaystyle f^{\prime }(x)=\underset{h\to 0}{lim}\frac{f(x+h)-f(x)}{h}}$$ the following can be shown (for n > 0): $${\displaystyle f^{(n)}(x)=\underset{h\to 0}{lim}\frac{1}{h^n}\sum _{k=0}^n(-1{)}^{n-k}(\genfrac{}{}{0ex}{}{n}{k})f(x+kh)}$$

Complex-variable methods

The classical finite-difference approximations for numerical differentiation are ill-conditioned. However, if ${\displaystyle f}$ is a holomorphic function, real-valued on the real line, which can be evaluated at points in the complex plane near ${\displaystyle x}$, then there are stable methods. For example, the first derivative can be calculated by the complex-step derivative formula: $${\displaystyle f^{\prime }(x)=\frac{\mathrm{\Im }(f(x+\mathrm{i}h))}{h}+O(h^2),{\mathrm{i}}^2:=-1.}$$

The recommended step size to obtain accurate derivatives for a range of conditions is ${\displaystyle h={10}^{-200}}$. This formula can be obtained by Taylor series expansion: $${\displaystyle f(x+\mathrm{i}h)=f(x)+\mathrm{i}h{f}^{\prime }(x)-\frac{1}{2!}{h}^2{f}^{″}(x)-\frac{\mathrm{i}}{3!}{h}^3{f}^{(3)}(x)+\cdots .}$$

The complex-step derivative formula is only valid for calculating first-order derivatives. A generalization of the above for calculating derivatives of any order employs multicomplex numbers, resulting in multicomplex derivatives. $${\displaystyle f^{(n)}(x)\approx \frac{{\mathcal{C}}_{n^2-1}^{(n)}(f(x+{\mathrm{i}}^{(1)}h+\cdots +{\mathrm{i}}^{(n)}h))}{h^n}}$$ where the ${\displaystyle {\mathrm{i}}^{(k)}}$ denote the multicomplex imaginary units; ${\displaystyle {\mathrm{i}}^{(1)}\equiv \mathrm{i}}$. The ${\displaystyle {\mathcal{C}}_k^{(n)}}$ operator extracts the ${\displaystyle k}$th component of a multicomplex number of level ${\displaystyle n}$, e.g., ${\displaystyle {\mathcal{C}}_0^{(n)}}$ extracts the real component and ${\displaystyle {\mathcal{C}}_{n^2-1}^{(n)}}$ extracts the last, "most imaginary" component. The method can be applied to mixed derivatives, e.g. for a second-order derivative $${\displaystyle \frac{{\mathrm{\partial }}^{2}f(x,y)}{\mathrm{\partial }x\mathrm{\partial }y}\approx \frac{{\mathcal{C}}_3^{(2)}(f(x+{\mathrm{i}}^{(1)}h,y+{\mathrm{i}}^{(2)}h))}{h^2}}$$

A C++ implementation of multicomplex arithmetics is available.

In general, derivatives of any order can be calculated using Cauchy's integral formula: $${\displaystyle f^{(n)}(a)=\frac{n!}{2\pi i}{\oint }_{\gamma }\frac{f(z)}{(z-a{)}^{n+1}}\mathrm{d}z,}$$ where the integration is done numerically.

Using complex variables for numerical differentiation was started by Lyness and Moler in 1967. Their algorithm is applicable to higher-order derivatives.

A method based on numerical inversion of a complex Laplace transform was developed by Abate and Dubner. An algorithm that can be used without requiring knowledge about the method or the character of the function was developed by Fornberg.

Differential quadrature

Differential quadrature is the approximation of derivatives by using weighted sums of function values. Differential quadrature is of practical interest because its allows one to compute derivatives from noisy data. The name is in analogy with quadrature, meaning numerical integration, where weighted sums are used in methods such as Simpson's rule or the trapezoidal rule. There are various methods for determining the weight coefficients, for example, the Savitzky–Golay filter. Differential quadrature is used to solve partial differential equations. There are further methods for computing derivatives from noisy data.