Finite difference

Last updated

A finite difference is a mathematical expression of the form f(x + b) − f(x + a). If a finite difference is divided by ba, one gets a difference quotient. The approximation of derivatives by finite differences plays a central role in finite difference methods for the numerical solution of differential equations, especially boundary value problems.

Contents

Certain recurrence relations can be written as difference equations by replacing iteration notation with finite differences.

Today, the term "finite difference" is often taken as synonymous with finite difference approximations of derivatives, especially in the context of numerical methods. [1] [2] [3] Finite difference approximations are finite difference quotients in the terminology employed above.

Finite differences were introduced by Brook Taylor in 1715 and have also been studied as abstract self-standing mathematical objects in works by George Boole (1860), L. M. Milne-Thomson (1933), and Károly Jordan (1939). Finite differences trace their origins back to one of Jost Bürgi's algorithms (c.1592) and work by others including Isaac Newton. The formal calculus of finite differences can be viewed as an alternative to the calculus of infinitesimals. [4]

Basic types

The three types of the finite differences. The central difference about x gives the best approximation of the derivative of the function at x. Finite difference method.svg
The three types of the finite differences. The central difference about x gives the best approximation of the derivative of the function at x.

Three basic types are commonly considered: forward, backward, and central finite differences. [1] [2] [3]

A forward difference is an expression of the form

Depending on the application, the spacing h may be variable or constant. When omitted, h is taken to be 1: Δ[f](x) = Δ1[f](x).

A backward difference uses the function values at x and xh, instead of the values at x + h and x:

Finally, the central difference is given by

Relation with derivatives

Finite difference is often used as an approximation of the derivative, typically in numerical differentiation.

The derivative of a function f at a point x is defined by the limit.

If h has a fixed (non-zero) value instead of approaching zero, then the right-hand side of the above equation would be written

Hence, the forward difference divided by h approximates the derivative when h is small. The error in this approximation can be derived from Taylor's theorem. Assuming that f is differentiable, we have

The same formula holds for the backward difference:

However, the central (also called centered) difference yields a more accurate approximation. If f is twice differentiable,

The main problem[ citation needed ] with the central difference method, however, is that oscillating functions can yield zero derivative. If f(nh) = 1 for n odd, and f(nh) = 2 for n even, then f′(nh) = 0 if it is calculated with the central difference scheme. This is particularly troublesome if the domain of f is discrete. See also Symmetric derivative

Authors for whom finite differences mean finite difference approximations define the forward/backward/central differences as the quotients given in this section (instead of employing the definitions given in the previous section). [1] [2] [3]

Higher-order differences

In an analogous way, one can obtain finite difference approximations to higher order derivatives and differential operators. For example, by using the above central difference formula for f′(x + h/2) and f′(xh/2) and applying a central difference formula for the derivative of f at x, we obtain the central difference approximation of the second derivative of f:

Second-order central

Similarly we can apply other differencing formulas in a recursive manner.

Second order forward
Second order backward

More generally, the nth order forward, backward, and central differences are given by, respectively,

Forward

or for h = 1,

Backward
Central

These equations use binomial coefficients after the summation sign shown as (n
i
)
. Each row of Pascal's triangle provides the coefficient for each value of i.

Note that the central difference will, for odd n, have h multiplied by non-integers. This is often a problem because it amounts to changing the interval of discretization. The problem may be remedied taking the average of δn[f](xh/2) and δn[f](x + h/2).

Forward differences applied to a sequence are sometimes called the binomial transform of the sequence, and have a number of interesting combinatorial properties. Forward differences may be evaluated using the Nörlund–Rice integral. The integral representation for these types of series is interesting, because the integral can often be evaluated using asymptotic expansion or saddle-point techniques; by contrast, the forward difference series can be extremely hard to evaluate numerically, because the binomial coefficients grow rapidly for large n.

The relationship of these higher-order differences with the respective derivatives is straightforward,

Higher-order differences can also be used to construct better approximations. As mentioned above, the first-order difference approximates the first-order derivative up to a term of order h. However, the combination

approximates f′(x) up to a term of order h2. This can be proven by expanding the above expression in Taylor series, or by using the calculus of finite differences, explained below.

If necessary, the finite difference can be centered about any point by mixing forward, backward, and central differences.

Arbitrarily sized kernels

Using linear algebra one can construct finite difference approximations which utilize an arbitrary number of points to the left and a (possibly different) number of points to the right of the evaluation point, for any order derivative. This involves solving a linear system such that the Taylor expansion of the sum of those points around the evaluation point best approximates the Taylor expansion of the desired derivative. Such formulas can be represented graphically on a hexagonal or diamond-shaped grid. [5]

This is useful for differentiating a function on a grid, where, as one approaches the edge of the grid, one must sample fewer and fewer points on one side.

The details are outlined in these notes.

The Finite Difference Coefficients Calculator constructs finite difference approximations for non-standard (and even non-integer) stencils given an arbitrary stencil and a desired derivative order.

Properties

In differential equations

An important application of finite differences is in numerical analysis, especially in numerical differential equations, which aim at the numerical solution of ordinary and partial differential equations. The idea is to replace the derivatives appearing in the differential equation by finite differences that approximate them. The resulting methods are called finite difference methods.

Common applications of the finite difference method are in computational science and engineering disciplines, such as thermal engineering, fluid mechanics, etc.

Newton's series

The Newton series consists of the terms of the Newton forward difference equation, named after Isaac Newton; in essence, it is the Newton interpolation formula, first published in his Principia Mathematica in 1687, [6] namely the discrete analog of the continuous Taylor expansion,

which holds for any polynomial function f and for many (but not all) analytic functions (It does not hold when f is exponential type . This is easily seen, as the sine function vanishes at integer multiples of ; the corresponding Newton series is identically zero, as all finite differences are zero in this case. Yet clearly, the sine function is not zero.). Here, the expression

is the binomial coefficient, and

is the "falling factorial" or "lower factorial", while the empty product (x)0 is defined to be 1. In this particular case, there is an assumption of unit steps for the changes in the values of x, h = 1 of the generalization below.

Note the formal correspondence of this result to Taylor's theorem. Historically, this, as well as the Chu–Vandermonde identity,

(following from it, and corresponding to the binomial theorem), are included in the observations that matured to the system of umbral calculus.

To illustrate how one may use Newton's formula in actual practice, consider the first few terms of doubling the Fibonacci sequence f = 2, 2, 4, ... One can find a polynomial that reproduces these values, by first computing a difference table, and then substituting the differences that correspond to x0 (underlined) into the formula as follows,

For the case of nonuniform steps in the values of x, Newton computes the divided differences,

the series of products,

and the resulting polynomial is the scalar product, [7]

.

In analysis with p-adic numbers, Mahler's theorem states that the assumption that f is a polynomial function can be weakened all the way to the assumption that f is merely continuous.

Carlson's theorem provides necessary and sufficient conditions for a Newton series to be unique, if it exists. However, a Newton series does not, in general, exist.

The Newton series, together with the Stirling series and the Selberg series, is a special case of the general difference series, all of which are defined in terms of suitably scaled forward differences.

In a compressed and slightly more general form and equidistant nodes the formula reads

Calculus of finite differences

The forward difference can be considered as an operator, called the difference operator, which maps the function f to Δh[f]. [8] [9] This operator amounts to

where Th is the shift operator with step h, defined by Th[f](x) = f(x + h), and I is the identity operator.

The finite difference of higher orders can be defined in recursive manner as Δn
h
≡ Δhn − 1
h
)
. Another equivalent definition is Δn
h
= [ThI]n
.

The difference operator Δh is a linear operator, as such it satisfies Δh[αf + βg](x) = α Δh[f](x) + β Δh[g](x).

It also satisfies a special Leibniz rule indicated above, Δh(f(x)g(x)) = (Δhf(x)) g(x+h) + f(x) (Δhg(x)). Similar statements hold for the backward and central differences.

Formally applying the Taylor series with respect to h, yields the formula

where D denotes the continuum derivative operator, mapping f to its derivative f. The expansion is valid when both sides act on analytic functions, for sufficiently small h. Thus, Th = ehD, and formally inverting the exponential yields

This formula holds in the sense that both operators give the same result when applied to a polynomial.

Even for analytic functions, the series on the right is not guaranteed to converge; it may be an asymptotic series. However, it can be used to obtain more accurate approximations for the derivative. For instance, retaining the first two terms of the series yields the second-order approximation to f ′(x) mentioned at the end of the section Higher-order differences.

The analogous formulas for the backward and central difference operators are

The calculus of finite differences is related to the umbral calculus of combinatorics. This remarkably systematic correspondence is due to the identity of the commutators of the umbral quantities to their continuum analogs (h → 0 limits),

A large number of formal differential relations of standard calculus involving functions f(x) thus map systematically to umbral finite-difference analogs involving f(xT−1
h
)
.

For instance, the umbral analog of a monomial xn is a generalization of the above falling factorial (Pochhammer k-symbol),

so that

hence the above Newton interpolation formula (by matching coefficients in the expansion of an arbitrary function f(x) in such symbols), and so on.

For example, the umbral sine is

As in the continuum limit, the eigenfunction of Δh/h also happens to be an exponential,

and hence Fourier sums of continuum functions are readily mapped to umbral Fourier sums faithfully, i.e., involving the same Fourier coefficients multiplying these umbral basis exponentials. [10] This umbral exponential thus amounts to the exponential generating function of the Pochhammer symbols.

Thus, for instance, the Dirac delta function maps to its umbral correspondent, the cardinal sine function,

and so forth. [11] Difference equations can often be solved with techniques very similar to those for solving differential equations.

The inverse operator of the forward difference operator, so then the umbral integral, is the indefinite sum or antidifference operator.

Rules for calculus of finite difference operators

Analogous to rules for finding the derivative, we have:

All of the above rules apply equally well to any difference operator, including as to Δ.

or

See references. [12] [13] [14] [15]

Generalizations

Multivariate finite differences

Finite differences can be considered in more than one variable. They are analogous to partial derivatives in several variables.

Some partial derivative approximations are:

Alternatively, for applications in which the computation of f is the most costly step, and both first and second derivatives must be computed, a more efficient formula for the last case is

since the only values to compute that are not already needed for the previous four equations are f(x + h, y + k) and f(xh, yk).

See also

Related Research Articles

Derivative Operation in calculus

In mathematics, the derivative of a function of a real variable measures the sensitivity to change of the function value with respect to a change in its argument. Derivatives are a fundamental tool of calculus. For example, the derivative of the position of a moving object with respect to time is the object's velocity: this measures how quickly the position of the object changes when time advances.

Laplaces equation Second order partial differential equation

In mathematics and physics, Laplace's equation is a second-order partial differential equation named after Pierre-Simon Laplace who first studied its properties. This is often written as

Dirac delta function Pseudo-function δ such that an integral of δ(x-c)f(x) always takes the value of f(c)

In mathematics, the Dirac delta function is a generalized function or distribution introduced by physicist Paul Dirac. It is called a function, although it is not a function. It is used to model the density of an idealized point mass or point charge as a function equal to zero everywhere except for zero and whose integral over the entire real line is equal to one. As there is no function that has these properties, the computations made by theoretical physicists appeared to mathematicians as nonsense until the introduction of distributions by Laurent Schwartz to formalize and validate the computations. As a distribution, the Dirac delta function is a linear functional that maps every function to its value at zero. The Kronecker delta function, which is usually defined on a discrete domain and takes values 0 and 1, is a discrete analog of the Dirac delta function.

In mathematics, the Laplace operator or Laplacian is a differential operator given by the divergence of the gradient of a function on Euclidean space. It is usually denoted by the symbols , , or . In a Cartesian coordinate system, the Laplacian is given by the sum of second partial derivatives of the function with respect to each independent variable. In other coordinate systems, such as cylindrical and spherical coordinates, the Laplacian also has a useful form. Informally, the Laplacian Δf(p) of a function f at a point p measures by how much the average value of f over small spheres or balls centered at p deviates from f(p).

Riemann sum Approximation technique in integral calculus

In mathematics, a Riemann sum is a certain kind of approximation of an integral by a finite sum. It is named after nineteenth century German mathematician Bernhard Riemann. One very common application is approximating the area of functions or lines on a graph, but also the length of curves and other approximations.

In mathematics before the 1970s, the term umbral calculus referred to the surprising similarity between seemingly unrelated polynomial equations and certain shadowy techniques used to 'prove' them. These techniques were introduced by John Blissard (1861) and are sometimes called Blissard's symbolic method. They are often attributed to Édouard Lucas, who used the technique extensively.

In vector calculus, Green's theorem relates a line integral around a simple closed curve C to a double integral over the plane region D bounded by C. It is the two-dimensional special case of Stokes' theorem.

Product rule Formula for the derivative of a product

In calculus, the product rule is a formula used to find the derivatives of products of two or more functions. For two functions, it may be stated in Lagrange's notation as

In the calculus of variations, a field of mathematical analysis, the functional derivative relates a change in a Functional to a change in a function on which the functional depends.

In mathematics, a Green's function is the impulse response of an inhomogeneous linear differential operator defined on a domain with specified initial conditions or boundary conditions.

Euler equations (fluid dynamics)

In fluid dynamics, the Euler equations are a set of quasilinear hyperbolic equations governing adiabatic and inviscid flow. They are named after Leonhard Euler. The equations represent Cauchy equations of conservation of mass (continuity), and balance of momentum and energy, and can be seen as particular Navier–Stokes equations with zero viscosity and zero thermal conductivity. In fact, Euler equations can be obtained by linearization of some more precise continuity equations like Navier–Stokes equations in a local equilibrium state given by a Maxwellian. The Euler equations can be applied to incompressible and to compressible flow – assuming the flow velocity is a solenoidal field, or using another appropriate energy equation respectively. Historically, only the incompressible equations have been derived by Euler. However, fluid dynamics literature often refers to the full set – including the energy equation – of the more general compressible equations together as "the Euler equations".

In mathematics, the Hessian matrix or Hessian is a square matrix of second-order partial derivatives of a scalar-valued function, or scalar field. It describes the local curvature of a function of many variables. The Hessian matrix was developed in the 19th century by the German mathematician Ludwig Otto Hesse and later named after him. Hesse originally used the term "functional determinants".

In mathematics, the directional derivative of a multivariate differentiable function along a given vector v at a given point x intuitively represents the instantaneous rate of change of the function, moving through x with a velocity specified by v. It therefore generalizes the notion of a partial derivative, in which the rate of change is taken along one of the curvilinear coordinate curves, all other coordinates being constant.

In mathematics, the discrete Laplace operator is an analog of the continuous Laplace operator, defined so that it has meaning on a graph or a discrete grid. For the case of a finite-dimensional graph, the discrete Laplace operator is more commonly called the Laplacian matrix.

In differential geometry, the Laplace–Beltrami operator is a generalization of the Laplace operator to functions defined on submanifolds in Euclidean space and, even more generally, on Riemannian and pseudo-Riemannian manifolds. It is named after Pierre-Simon Laplace and Eugenio Beltrami.

Used in hydrogeology, the groundwater flow equation is the mathematical relationship which is used to describe the flow of groundwater through an aquifer. The transient flow of groundwater is described by a form of the diffusion equation, similar to that used in heat transfer to describe the flow of heat in a solid. The steady-state flow of groundwater is described by a form of the Laplace equation, which is a form of potential flow and has analogs in numerous fields.

Finite difference method

In numerical analysis, finite-difference methods (FDM) are a class of numerical techniques for solving differential equations by approximating derivatives with finite differences. Both the spatial domain and time interval are discretized, or broken into a finite number of steps, and the value of the solution at these discrete points is approximated by solving algebraic equations containing finite differences and values from nearby points.

In calculus, the differential represents the principal part of the change in a function y = f(x) with respect to changes in the independent variable. The differential dy is defined by

In theoretical physics, Hamiltonian field theory is the field-theoretic analogue to classical Hamiltonian mechanics. It is a formalism in classical field theory alongside Lagrangian field theory. It also has applications in quantum field theory.

Discrete calculus or the calculus of discrete functions, is the mathematical study of incremental change, in the same way that geometry is the study of shape and algebra is the study of generalizations of arithmetic operations. The word calculus is a Latin word, meaning originally "small pebble"; as such pebbles were used for calculation, the meaning of the word has evolved and today usually means a method of computation. Meanwhile, calculus, originally called infinitesimal calculus or "the calculus of infinitesimals", is the study of continuous change.

References

  1. 1 2 3 Paul Wilmott; Sam Howison; Jeff Dewynne (1995). The Mathematics of Financial Derivatives: A Student Introduction . Cambridge University Press. p.  137. ISBN   978-0-521-49789-3.
  2. 1 2 3 Peter Olver (2013). Introduction to Partial Differential Equations. Springer Science & Business Media. p. 182. ISBN   978-3-319-02099-0.
  3. 1 2 3 M Hanif Chaudhry (2007). Open-Channel Flow. Springer. p. 369. ISBN   978-0-387-68648-6.
  4. Jordán, op. cit., p. 1 and Milne-Thomson, p. xxi. Milne-Thomson, Louis Melville (2000): The Calculus of Finite Differences (Chelsea Pub Co, 2000) ISBN   978-0821821077
  5. Fraser, Duncan C. (January 1, 1909). "On the Graphic Delineation of Interpolation Formulæ". Journal of the Institute of Actuaries. 43 (2): 235–241. doi:10.1017/S002026810002494X . Retrieved April 17, 2017.
  6. Newton, Isaac, (1687). Principia, Book III, Lemma V, Case 1
  7. Richtmeyer, D. and Morton, K.W., (1967). Difference Methods for Initial Value Problems, 2nd ed., Wiley, New York.
  8. Boole, George, (1872). A Treatise On The Calculus of Finite Differences, 2nd ed., Macmillan and Company. On line. Also, [Dover edition 1960]
  9. Jordan, Charles, (1939/1965). "Calculus of Finite Differences", Chelsea Publishing. On-line:
  10. Zachos, C. (2008). "Umbral Deformations on Discrete Space-Time". International Journal of Modern Physics A. 23 (13): 2005–2014. arXiv: 0710.2306 . Bibcode:2008IJMPA..23.2005Z. doi:10.1142/S0217751X08040548. S2CID   16797959.
  11. Curtright, T. L.; Zachos, C. K. (2013). "Umbral Vade Mecum". Frontiers in Physics. 1: 15. arXiv: 1304.0429 . Bibcode:2013FrP.....1...15C. doi:10.3389/fphy.2013.00015. S2CID   14106142.
  12. Levy, H.; Lessman, F. (1992). Finite Difference Equations. Dover. ISBN   0-486-67260-3.
  13. Ames, W. F., (1977). Numerical Methods for Partial Differential Equations, Section 1.6. Academic Press, New York. ISBN   0-12-056760-1.
  14. Hildebrand, F. B., (1968). Finite-Difference Equations and Simulations, Section 2.2, Prentice-Hall, Englewood Cliffs, New Jersey.
  15. Flajolet, Philippe; Sedgewick, Robert (1995). "Mellin transforms and asymptotics: Finite differences and Rice's integrals" (PDF). Theoretical Computer Science. 144 (1–2): 101–124. doi:10.1016/0304-3975(94)00281-M..