↑ arvau

Wikipedia / Numerical differentiation

In numerical analysis, numerical differentiation algorithms estimate the derivative of a mathematical function or subroutine using values of the function. Unlike analytical differentiation, which provides exact expressions for derivatives, numerical differentiation relies on the function's values at a set of discrete points to estimate the derivative's value at those points or at intermediate points. This approach is particularly useful when dealing with data obtained from experiments, simulations, or situations where the function is defined only at specific intervals.

Finite differences

The simplest method is to use finite difference approximations.

A simple two-point estimation is to compute the slope of a nearby secant line through the points and . Choosing a small number , represents a small change in This expression is Newton's difference quotient (also known as a first-order divided difference).

The slope of this secant line differs from the slope of the tangent line by an amount that is approximately proportional to . As approaches zero, the slope of the secant line approaches the slope of the tangent line and the error term vanishes. Therefore, the true derivative of at

Since immediately substituting 0 for indeterminate form, calculating the derivative directly can be unintuitive.

Equivalently, the slope could be estimated by employing positions and .

Another two-point formula is to compute the slope of a nearby secant line through the points and

This formula is known as the symmetric difference quotient. Hence for small values of this is a more accurate approximation to the tangent line than the one-sided estimation. However, although the slope is being computed at , the value of the function at is not involved.

. This error does not include the rounding error due to numbers being represented and calculations being performed in limited precision.

The symmetric difference quotient is employed as the method of approximating the derivative in a number of calculators, including TI-82, TI-83, TI-84, TI-85, all of which use this method with .

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, . To illustrate, consider the two-point approximation formula with error term:

denote the roundoff error and the third derivative

To reduce the truncation error, we must reduce . But as increases. Due to the need to divide by the small value , all the finite-difference formulae for numerical differentiation are similarly ill-conditioned.

and we assume the relative approximation error due to rounding is bounded by machine epsilon respectively it can be shown that: an estimate for the optimal step size can be found: is used giving a choice for , where the machine epsilon is typically of the order of 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

, after which the absolute error steadily increases as the roundoff errors dominate calcuations.For computer calculations the problems are exacerbated because, although necessarily holds a representable floating-point number in some precision (32 or 64-bit, etc.), almost certainly will not be exactly representable in that precision. This means that will be changed (by rounding or truncation) to a nearby machine-representable number, with the consequence that will not equal ; the two function evaluations will not be exactly 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 will not be a round number in binary; it is 0.000110011001100...2 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 and are the same. With C and similar languages, a directive that is a volatile variable will prevent this.

Three Point methods

is

gives

Multiplying identity () by 4 gives

Subtracting identity () from ( term:

which can be written as

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

which is called the three-point central difference formula which is called the three-point backward difference formula.

By a similar approach, the five point midpoint approximation formula can be derived as:

Numerical Example

Algorithms

The following pseudocode describes the various three point differentiation formulas.

Three-Point Forward Difference

input: 
Real valued function, f
The point at which to approximate the derivative, a
The step size, h
output:f'(a)
return ((-3/2)*f(a) + 2*f(a+h) - (1/2)*f(a+2*h)) / h

Three-Point Central Difference

input: 
Real valued function, f
The point at which to approximate the derivative, a
The step size, h
output:f'(a)
return ((-1/2)*f(a-h) + (1/2)*f(a+h)) / h

Three-Point Backward Difference

input: 
Real valued function, f
The point at which to approximate the derivative, a
The step size, h
output:f'(a)
return ((1/2)*f(a-2*h) - 2*f(a-h) + (3/2)*f(a)) / h

Higher derivatives

gives

. Adding these two equations gives

. The Intermediate Value Theorem. We can therefore write

.

Numerical Example

.

.

Arbitrary Derivatives

the following can be shown (for

Complex-variable methods

is a holomorphic function, real-valued on the real line, which can be evaluated at points in the complex plane, then there are stable methods. For example, the first derivative can be calculated by the complex-step derivative formula:

. This formula can be obtained by Taylor series

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.

A C++ implementation of multicomplex arithmetics is available.

In general, derivatives of any order can be calculated using Cauchy's integral formula: 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.

See also

References