A finite difference is a mathematical expression of the form f(x + b) − f(x + a). If a finite difference is divided by b − a, 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.
Recurrence relations can be written as difference equations by replacing iteration notation with finite differences.
Forward, backward, and central differences
Only three forms are commonly considered: forward, backward, and central differences.
A forward difference is an expression of the form
Depending on the application, the spacing h may be variable or constant.
A backward difference uses the function values at x and x − h, instead of the values at x + h and x:
Finally, the central difference is given by
Relation with derivatives
If h has a fixed (non-zero) value, instead of approaching zero, then the right-hand side is
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 continuously differentiable, the error is
The same formula holds for the backward difference:
However, the central difference yields a more accurate approximation. Its error is proportional to square of the spacing (if f is twice continuously differentiable):
The main problem with the central difference method, however, is that oscillating functions can yield zero derivative. If f(nh)=1 for n uneven, 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.
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'(x − h / 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:
2nd Order Central
Similarly we can apply other differencing formulas in a recursive manner. 2nd Order Forward
More generally, the nth-order forward, backward, and central differences are respectively given by:
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](x − h / 2) and δn[f](x + h / 2).
The relationship of these higher-order differences with the respective derivatives is very 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 a little linear algebra, one can fairly easily construct approximations, which sample an arbitrary number of points to the left and a (possibly different) number of points to the right of the center point, for any order of derivative. This involves solving a linear system such that the Taylor expansion of the sum of those points, around the center point, well approximates the Taylor expansion of the desired derivative.
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.
- For all positive k and n
Finite difference methods
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 respectively. 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.
The nth forward difference of a function f(x) is given by
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 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, namely the discrete analog of the continuum Taylor expansion,
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 also the formal correspondence of this result to Taylor's theorem; historically, this, as well as the Chu-Vandermonde identity, , following from it, is one of the observations that matured to the system of the umbral calculus.
To illustrate how one might use Newton's formula in actual practice, consider the first few terms of the Fibonacci sequence f = 2, 2, 4... One can thus find a polynomial that reproduces these values, by first computing a difference table, and then substituting the differences which 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, .
Carlson's theorem provides necessary and sufficient conditions for a Newton series to be unique, if it exists. However, a Newton series will 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 scaled forward differences.
In a compressed and slightly more general form and equidistant nodes the formula reads
Calculus of finite differences
where Th is the shift operator with step h, defined by Th[f](x) = f(x + h), and I is an identity operator.
The finite difference of higher orders can be defined in recursive manner as or, in operator notation, Another equivalent definition is
The difference operator Δh is a linear and satisfies a Leibniz rule. 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. Formally inverting the exponential suggests that
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(xTh−1).
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.
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 .
and so forth. Difference equations can often be solved with techniques very similar to those for solving differential equations.
The inverse operator of the forward difference operator, 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:
- Constant rule: If c is a constant, then
All of the above rules apply equally well to any difference operator, including as to Δ.
- Summation rules:
- A generalized finite difference is usually defined as
where is its coefficients vector. An infinite difference is a further generalization, where the finite sum above is replaced by an infinite series. Another way of generalization is making coefficients μk depend on point x : μk = μk(x), thus considering weighted finite difference. Also one may make step h depend on point x : h = h(x). Such generalizations are useful for constructing different modulus of continuity.
- Difference operator generalizes to Möbius inversion over a partially ordered set.
- As a convolution operator: Via the formalism of incidence algebras, difference operators and other Möbius inversion can be represented by convolution with a function on the poset, called the Möbius function μ; for the difference operator, μ is the sequence (1, −1, 0, 0, 0, ...).
Finite difference in several variables
Finite differences can be considered in more than one variable. They are analogous to partial derivatives in several variables.
Some partial derivative approximations are:
- Finite difference coefficients
- Newton polynomial
- Table of Newtonian series
- Sheffer sequence
- Umbral calculus
- Taylor series
- Numerical differentiation
- Five-point stencil
- Divided differences
- Modulus of continuity
- Time scale calculus
- Summation by parts
- Lagrange polynomial
- Gilbreath's conjecture
- ^ Newton, Isaac, (1687). Principia, Book III, Lemma V, Case 1
- ^ Richtmeyer, D. and Morton, K.W., (1967). Difference Methods for Initial Value Problems, 2nd ed., Wiley, New York.
- ^ Boole, George, (1872). A Treatise On The Calculus of Finite Differences, 2nd ed., Macmillan and Company. On-line:  Also, [Dover edition 1960]
- ^ Zachos, C. (2008). "Umbral Deformations on Discrete Space-Time". International Journal of Modern Physics A 23 (13): 2005–2014. doi:10.1142/S0217751X08040548.
- ^ Levy, H.; Lessman, F. (1992). Finite Difference Equations. Dover. ISBN 0-486-67260-3.
- ^ Ames, W. F., (1977). Numerical Methods for Partial Differential Equations, Section 1.6. Academic Press, New York. ISBN 0-12-056760-1.
- ^ Hildebrand, F. B. , (1968). Finite-Difference Equations and Simulations, Section 2.2, Prentice-Hall, Englewood Cliffs, New Jersey.
- ^ Flajolet, Philippe; Sedgewick, Robert (1995), "Mellin transforms and asymptotics: Finite differences and Rice's integrals", Theoretical Computer Science 144 (1–2): 101–124, doi:10.1016/0304-3975(94)00281-M, http://www-rocq.inria.fr/algo/flajolet/Publications/mellin-rice.ps.gz .
Wikimedia Foundation. 2010.
Look at other dictionaries:
finite difference — Math. difference (def. 9c). [1800 10] * * * … Universalium
finite difference — noun A difference between the value of a function evaluated at a number, and the value of the same function evaluated at a different number, a fixed distance from the first … Wiktionary
finite difference — noun : any of a sequence of differences of the general form f(x + nh) f(x + (n 1)h) obtained by incrementing successively the dependent variable of the function f(x) by the amount h ; especially : any of such differences obtained from a… … Useful english dictionary
finite difference — noun Date: 1807 any of a sequence of differences obtained by incrementing successively the dependent variable of a function by a fixed amount; especially any of such differences obtained from a polynomial function using successive integral values … New Collegiate Dictionary
Finite-difference time-domain method — Finite difference time domain (FDTD) is a popular computational electrodynamics modeling technique. It is considered easy to understand and easy to implement in software. Since it is a time domain method, solutions can cover a wide frequency… … Wikipedia
Finite Difference Time Domain — (FDTD, englisch für Finite Differenzen Methode im Zeitbereich) ist ein mathematisches Verfahren zur direkten Integration zeitabhängiger Differentialgleichungen. Vor allem zur Berechnung der Lösungen der Maxwell Gleichungen wird dieses Verfahren… … Deutsch Wikipedia
Finite difference method — In mathematics, finite difference methods are numerical methods for approximating the solutions to differential equations using finite difference equations to approximate derivatives. Intuitive derivation Finite difference methods approximate the … Wikipedia
Finite-difference frequency-domain — The finite difference frequency domain (FDFD) is a numerical solution for problems usually in electromagnetism. The method is, of course, based on finite difference approximations of the derivative operators in the differential equation being… … Wikipedia
finite difference method — A numerical method used to approximate the solution of partial differential equations  … Lexicon of Cave and Karst Terminology
Nonstandard finite difference scheme — Nonstandard finite difference schemes is a general set of methods in numerical analysis that gives numerical solutions to differential equations by constructing a discrete model. The general rules for such schemes are not precisely known. … … Wikipedia