Finite difference 39147 222872035 2008-07-01T14:57:30Z Delaszk 6980814 /* See also */ A '''finite difference''' is a mathematical expression of the form ''f''(''x'' + ''b'') &minus; ''f''(''x'' + ''a''). If a finite difference is divided by ''b'' &minus; ''a'', one gets a [[difference quotient]]. The approximation of derivatives by finite differences plays a central role in [[finite difference method]]s for the [[numerical analysis|numerical]] solution of [[differential equation]]s, especially [[boundary value problem]]s. In [[mathematical analysis]], [[operator]]s involving finite differences are studied. A [[difference operator]] is an operator which maps a function ''f'' to a function whose values are the corresponding 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 :<math> \Delta_h[f](x) = f(x + h) - f(x). \, </math> Depending on the application, the spacing ''h'' may be variable or held constant. A '''backward difference''' uses the function values at ''x'' and ''x'' &minus; ''h'', instead of the values at ''x'' + ''h'' and ''x'': :<math> \nabla_h[f](x) = f(x) - f(x-h). </math> Finally, the '''central difference''' is given by :<math> \delta_h[f](x) = f(x+\tfrac12h)-f(x-\tfrac12h). \ </math> == Relation with derivatives == The [[derivative]] of a function ''f'' at a point ''x'' is defined by the [[limit (mathematics)|limit]] :<math> f'(x) = \lim_{h\to0} \frac{f(x+h) - f(x)}{h}. </math> If ''h'' has a fixed (non-zero) value, instead of approaching zero, then the right-hand side is :<math> \frac{f(x + h) - f(x)}{h} = \frac{\Delta_h[f](x)}{h}. </math> 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 :<math> \frac{\Delta_h[f](x)}{h} - f'(x) = O(h) \quad (h \to 0). </math> The same formula holds for the backward difference: :<math> \frac{\nabla_h[f](x)}{h} - f'(x) = O(h). </math> However, the central difference yields a more accurate approximation. Its error is proportional to square of the spacing (if ''f'' is twice continuously differentiable): :<math> \frac{\delta_h[f](x)}{h} - f'(x) = O(h^{2}) . \!</math> ==Higher-order differences== <!-- this section is linked to further down in the article --> 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 <math>f'(x+h/2)</math> and <math>f'(x-h/2)</math> and applying a central difference formula for the derivative of <math> f' </math> at ''x'', we obtain the central difference approximation of the second derivative of ''f'': :<math> f''(x) \approx \frac{\delta_h^2[f](x)}{h^2} = \frac{f(x+h) - 2 f(x) + f(x-h)}{h^{2}} . </math> More generally, the ''n''<sup>th</sup>-order forward, backward, and central differences are respectively given by: :<math>\Delta^n_h[f](x) = \sum_{i = 0}^{n} (-1)^i \binom{n}{i} f(x + (n - i) h), </math> :<math>\nabla^n_h[f](x) = \sum_{i = 0}^{n} (-1)^i \binom{n}{i} f(x - ih), </math> :<math>\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). </math> Note that the central difference will, for odd <math>n</math>, have <math>h</math> multiplied by non-integers. If this is a problem (usually it is), it may be remedied taking the average of <math>\delta^n[f](x - h/2)</math> and <math>\delta^n[f](x + h/2)</math>. The relationship of these higher-order differences with the respective derivatives is very straightforward: :<math>\frac{d^n f}{d x^n}(x)</math> <math>= \frac{\Delta_h^n[f](x)}{h^n}+O(h)</math> <math>= \frac{\nabla_h^n[f](x)}{h^n}+O(h)</math> <math>= \frac{\delta_h^n[f](x)}{h^n} + O(h^2).</math> 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 :<math> \frac{\Delta_h[f](x) - \frac12 \Delta_h^2[f](x)}{h} = - \frac{f(x+2h)-4f(x+h)+3f(x)}{2h} </math> approximates ''f'''(''x'') up to a term of order ''h''<sup>2</sup>. 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. ===Properties=== * For all positive ''k'' and ''n'' :<math>\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).</math> * [[Leibniz rule (generalized product rule)|Leibniz rule]]: :<math>\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).</math> == Finite difference methods== {{main|finite difference method}} An important application of finite differences is in [[numerical analysis]], especially in [[numerical ordinary differential equations]] and [[numerical partial differential equations]], which aim at the numerical solution of [[ordinary differential equation|ordinary]] and [[partial differential equation]]s 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== {{main|difference operator}} The forward difference can be considered as a difference operator, which maps the function ''f'' to Δ<sub>''h''</sub>[''f'']. This operator satisfies :<math>\Delta_h = T_h-I, \,</math> where <math>T_h</math> is the [[shift operator]] with step <math>h</math>, defined by <math>T_h[f](x) = f(x+h)</math>, and <math>I</math> is an [[identity operator]]. Finite difference of higher orders can be defined in recursive manner as <math>\Delta^n_h(f,x):=\Delta_h(\Delta^{n-1}_h(f,x), x)</math> or, in operators notation, <math>\Delta^n_h:=\Delta_h(\Delta^{n-1}_h).</math> Another possible (and equivalent) definition is <math>\Delta^n_h = [T_h-I]^n.</math> The difference operator Δ<sub>''h''</sub> is [[linear operator|linear]] and satisfies [[Leibniz rule]]. Similar statements hold for the backward and central difference. [[Taylor's theorem]] can now be expressed by the formula :<math> \Delta_h = hD + \frac12 h^2D^2 + \frac1{3!} h^3D^3 + \cdots = \mathrm{e}^{hD} - 1, </math> where ''D'' denotes the derivative operator, mapping ''f'' to its derivative ''f'''. Formally inverting the exponential suggests that :<math> hD = \log(1+\Delta_h) = \Delta_h - \frac12 \Delta_h^2 + \frac13 \Delta_h^3 + \cdots. \, </math> 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 <math>f'(x)</math> mentioned at the end of the [[#Higher-order differences|section ''Higher-order differences'']]. The analogous formulas for the backward and central difference operators are :<math> hD = -\log(1-\nabla_h) \quad\mbox{and}\quad hD = 2 \, \operatorname{arcsinh}(\tfrac12\delta_h). </math> The calculus of finite differences is related to the [[umbral calculus]] in combinatorics. ==Generalizations== A '''generalized finite difference''' is usually defined as :<math>\Delta_h^\mu[f](x) = \sum_{k=0}^N \mu_k f(x+kh),</math> where <math>\mu = (\mu_0,\ldots,\mu_N)</math> is its coefficients vector. An '''infinite difference''' is a further generalization, where the finite sum above is replaced by an [[Series (mathematics)|infinite series]]. Another way of generalization is making coefficients <math>\mu_k</math> depend on point <math>x</math> : <math>\mu_k=\mu_k(x)</math>, thus considering '''weighted finite difference'''. Also one may make step <math>h</math> depend on point <math>x</math> : <math>h=h(x)</math>. Such generalizations are useful for constructing different [[modulus of continuity]]. ==Finite difference in several variables== Finite differences can be considered in more than one variable. They are analogous to [[partial derivative]]s in several variables. ==See also== * [[Taylor series]] * [[Numerical differentiation]] * [[Five-point stencil]] * [[Divided differences]] * [[Modulus of continuity]] * [[Time scale calculus]] == References == * William F. Ames, ''Numerical Method for Partial Differential Equations'', Section 1.6. Academic Press, New York, 1977. ISBN 0-12-056760-1. * Francis B. Hildebrand, ''Finite-Difference Equations and Simulations'', Section 2.2, Prentice-Hall, Englewood Cliffs, New Jersey, 1968. * Boole, George, ''A Treatise On The Calculus of Finite Differences'', 2<sup>nd</sup> ed., Macmillan and Company, 1872. [See also: Dover edition 1960]. * Robert D. Richtmyer and K. W. Morton, ''Difference Methods for Initial Value Problems'', 2<sup>nd</sup> ed., Wiley, New York, 1967. == External links == *[http://www.adeptscience.co.uk/products/mathsim/maple/powertools/des/unit18.html#MapleAutoBookmark4 Finite Difference Method] *[http://math.fullerton.edu/mathews/n2003/FiniteDifferenceMod.html Finite Difference Method for Boundary Value Problems] *[http://reference.wolfram.com/mathematica/tutorial/NDSolvePDE.html#c:4 Table of useful finite difference formula generated using [[Mathematica]] ] [[Category:Finite differences| ]] [[Category:Numerical differential equations]] [[Category:Mathematical analysis]] [[bg:Крайна разлика]] [[de:Finite-Differenzen-Methode]] [[es:Diferencia finita]] [[fr:Méthode des différences finies]] [[ja:差分]] [[pt:Método das diferenças finitas]] [[ru:Конечные разности]]