Finite difference: Wikis

Advertisements
  

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Encyclopedia

Advertisements

From Wikipedia, the free encyclopedia

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.

Contents

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

 \Delta_h[f](x) = f(x + h) - f(x). \

Depending on the application, the spacing h may be variable or held constant.

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

 \nabla_h[f](x) = f(x) - f(x-h). \

Finally, the central difference is given by

 \delta_h[f](x) = f(x+\tfrac12h)-f(x-\tfrac12h). \

Relation with derivatives

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

 f'(x) = \lim_{h\to0} \frac{f(x+h) - f(x)}{h}.

If h has a fixed (non-zero) value, instead of approaching zero, then the right-hand side is

 \frac{f(x + h) - f(x)}{h} = \frac{\Delta_h[f](x)}{h}.

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

 \frac{\Delta_h[f](x)}{h} - f'(x) = O(h) \quad (h \to 0).

The same formula holds for the backward difference:

 \frac{\nabla_h[f](x)}{h} - f'(x) = O(h).

However, the central difference yields a more accurate approximation. Its error is proportional to square of the spacing (if f is twice continuously differentiable):

 \frac{\delta_h[f](x)}{h} - f'(x) = O(h^{2}) . \!

The main problem with the central difference method, however, is that oscillating functions can yield zero derivative. If h(nh)=1 for n uneven, and h(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.

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:

 f''(x) \approx \frac{\delta_h^2[f](x)}{h^2} = \frac{f(x+h) - 2 f(x) + f(x-h)}{h^{2}} .

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

\Delta^n_h[f](x) = \sum_{i = 0}^{n} (-1)^i \binom{n}{i} f(x + (n - i) h),
\nabla^n_h[f](x) = \sum_{i = 0}^{n} (-1)^i \binom{n}{i} f(x - ih),
\delta^n_h[f](x) = \sum_{i = 0}^{n} (-1)^i \binom{n}{i} f\left(x + \left(\frac{n}{2} - i\right) h\right).

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

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

\frac{d^n f}{d x^n}(x) = \frac{\Delta_h^n[f](x)}{h^n}+O(h) = \frac{\nabla_h^n[f](x)}{h^n}+O(h) = \frac{\delta_h^n[f](x)}{h^n} + O(h^2).

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

 \frac{\Delta_h[f](x) - \frac12 \Delta_h^2[f](x)}{h} = - \frac{f(x+2h)-4f(x+h)+3f(x)}{2h}

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.

Properties

  • For all positive k and n
\Delta^n_{kh} (f, x) = \sum\limits_{i_1=0}^{k-1} \sum\limits_{i_2=0}^{k-1} ... \sum\limits_{i_n=0}^{k-1} \Delta^n_h (f, x+i_1h+i_2h+...+i_nh).
\Delta^n_h (fg, x) = \sum\limits_{k=0}^n \binom{n}{k} \Delta^k_h (f, x) \Delta^{n-k}_h(g, x+kh).

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.

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

Calculus of finite differences

The forward difference can be considered as a difference operator, which maps the function f to Δh[f]. This operator satisfies

\Delta_h = T_h-I, \,

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

Finite difference of higher orders can be defined in recursive manner as \Delta^n_h(f,x):=\Delta_h(\Delta^{n-1}_h(f,x), x) or, in operators notation, \Delta^n_h:=\Delta_h(\Delta^{n-1}_h). Another possible (and equivalent) definition is \Delta^n_h = [T_h-I]^n.

The difference operator Δh is linear and satisfies Leibniz rule. Similar statements hold for the backward and central difference.

Applying Taylor's theorem with respect to h gives the formula

 \Delta_h = hD + \frac12 h^2D^2 + \frac1{3!} h^3D^3 + \cdots = \mathrm{e}^{hD} - 1,

where D denotes the derivative operator, mapping f to its derivative f'. Formally inverting the exponential suggests that

 hD = \log(1+\Delta_h) = \Delta_h - \frac12 \Delta_h^2 + \frac13 \Delta_h^3 + \cdots. \,

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

 hD = -\log(1-\nabla_h) \quad\mbox{and}\quad hD = 2 \, \operatorname{arsinh}(\tfrac12\delta_h).

The calculus of finite differences is related to the umbral calculus in combinatorics.

The inverse operator of the forward difference operator is the indefinite sum.

In mathematics, a difference operator maps a function, ƒ(x), to another function, ƒ(x + b) − ƒ(x + a).

The forward difference operator

\Delta f(x)=f(x+1)-f(x)\,

occurs frequently in the calculus of finite differences, where it plays a role formally similar to that of the derivative, but used in discrete circumstances. Difference equations can often be solved with techniques very similar to those for solving differential equations. This similarity led to the development of time scale calculus. Analogously we can have the backward difference operator

\nabla f(x)=f(x)-f(x-1)\,

When restricted to polynomial functions f, the forward difference operator is a delta operator, i.e., a shift-equivariant linear operator on polynomials that reduces degree by 1.

n-th difference

The nth forward difference of a function f(x) is given by

\Delta^n [f](x)= \sum_{k=0}^n {n \choose k} (-1)^{n-k} f(x+k)

where {n \choose k} is the binomial coefficient. 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.

Newton series

The Newton series or Newton forward difference equation, named after Isaac Newton, is the relationship

f(x+a)=\sum_{k=0}^\infty\frac{\Delta^k [f](a)}{k!}(x)_k = \sum_{k=0}^\infty {x \choose k} \Delta^k [f](a)

which holds for any polynomial function f and for some, but not all, analytic functions. Here, the expression

{x \choose k} = \frac{(x)_k}{k!}

is the binomial coefficient, as

(x)_k=x(x-1)(x-2)\cdots(x-k+1)

is the "falling factorial" or "lower factorial" and the empty product (x)0 defined to be 1. Note also the formal similarity of this result to Taylor's theorem; this is one of the observations that lead to the idea of umbral calculus.

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

Rules for calculus of finite difference operators

Analogous to rules for finding the derivative, we have:

  • Constant rule: If c is a constant, then
\Delta c = 0{\,}
\Delta (a f + b g) = a \,\Delta f + b \,\Delta g

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

 \Delta (f g) = f \,\Delta g + g \,\Delta f + \Delta f \,\Delta g
 \nabla (f g) = f \,\nabla g + g \,\nabla f - \nabla f \,\nabla g
\nabla \left( \frac{f}{g} \right) = \frac{1}{g} \det \begin{bmatrix} \nabla f & \nabla g \\ f & g \end{bmatrix} \left( \det {\begin{bmatrix} g & \nabla g \\ 1 & 1 \end{bmatrix}}\right)^{-1}
or
\nabla\left( \frac{f}{g} \right)= \frac {g \,\nabla f - f \,\nabla g}{g \cdot (g - \nabla g)}
\Delta\left( \frac{f}{g} \right)= \frac {g \,\Delta f - f \,\Delta g}{g \cdot (g + \Delta g)}
  • Summation rules:
\sum_{n=a}^{b} \Delta f(n) = f(b+1)-f(a)
\sum_{n=a}^{b} \nabla f(n) = f(b)-f(a-1)

Indefinite sum

The inverse operator of the forward difference operator is the indefinite sum.

Generalizations

  • A generalized finite difference is usually defined as
\Delta_h^\mu[f](x) = \sum_{k=0}^N \mu_k f(x+kh),

where \mu = (\mu_0,\ldots,\mu_N) 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.

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

 f_{x}(x,y) \approx \frac{f(x+h ,y) - f(x-h,y)}{2h} \
 f_{y}(x,y) \approx \frac{f(x,y+k ) - f(x,y-k)}{2k} \
 f_{xx}(x,y) \approx \frac{f(x+h ,y) - 2 f(x,y) + f(x-h,y)}{h^2} \
 f_{yy}(x,y) \approx \frac{f(x,y+k) - 2 f(x,y) + f(x,y-k)}{k^2} \
 f_{xy}(x,y) \approx \frac{f(x+h,y+k) - f(x+h,y-k) - f(x-h,y+k) + f(x-h,y-k)}{4hk} \

See also

References

External links


Advertisements






Got something to say? Make a comment.
Your name
Your email address
Message