Finite difference

From Wikipedia, the free encyclopedia
Jump to: navigation, search



Forward, backward, and central differences[edit]


A forward difference is an expression of the form

 \Delta_h[f](x) =  f(x + h) - f(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[edit]




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


 \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; that is, the second derivative of the function, f", is continuous for all x):

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


Higher-order differences[edit]


2nd order central

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

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

2nd order forward

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



\Delta^n_h[f](x) = 
\sum_{i = 0}^{n} (-1)^i \binom{n}{i} f(x + (n - i) h),

or for h=1,

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


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

These equations are using binomial coefficients after the summation sign shown as \ \binom{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 \delta^n[f](x - h/2) and \delta^n[f](x + h/2).



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


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



Arbitrarily sized kernels[edit]

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.


The details are outlined in these notes.


  • 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[edit]



Newton's series[edit]

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,[1] namely the discrete analog of the continuum Taylor expansion,

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


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

is the binomial coefficient, and



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

(x+y)_n=\sum_{k=0}^n {n \choose k} (x)_{n-k} ~(y)_k ~,

(following from it, and corresponding to the binomial theorem), are included in the observations which matured to the system of the 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 which correspond to x0 (underlined) into the formula as follows,


 x & f=\Delta^0 & \Delta^1 & \Delta^2 \\
1&\underline{2}& & \\
 & &\underline{0}& \\
2&2& &\underline{2} \\
 & &2& \\
3&4& & \\


\quad \begin{matrix}
f(x)=\Delta^0 \cdot 1 +\Delta^1 \cdot \dfrac{(x-x_0)_1}{1!} + \Delta^2 \cdot \dfrac{(x-x_0)_2}{2!} \quad (x_0=1)\\
=2 \cdot 1 + 0 \cdot \dfrac{x-1}{1} + 2 \cdot \dfrac{(x-1)(x-2)}{2} \\
=2 + (x-1)(x-2) \\


\Delta _{j,0}=y_j,\quad \quad \Delta _{j,k}=\frac{\Delta _{j+1,k-1}-\Delta _{j,k-1}}{x_{j+k}-x_j}\quad \ni \quad \left\{ k>0,\ \ j\le \max \left( j \right)-k \right\},\quad \quad \Delta 0_k=\Delta _{0,k}

the series of products,

{P_0}=1,\quad \quad P_{k+1}=P_k\cdot \left( \xi -x_k \right) ~,

and the resulting polynomial is the scalar product, f(\xi ) = \Delta 0 \cdot P\left( \xi  \right) .[2]


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.



f(x)=\sum_{k=0}{\frac{x-a}h \choose k} \sum_{j=0}^k (-1)^{k-j}{k\choose j}f(a+j h).

Calculus of finite differences[edit]

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

\Delta_h = T_h-I, \,


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



 \Delta_h = hD + \frac{1}{2} h^2D^2 + \frac{1}{3!} h^3D^3 + \cdots = \mathrm{e}^{hD} - I ~,


 hD = \log(1+\Delta_h) = \Delta_h - \tfrac{1}{2} \Delta_h^2 + \tfrac{1}{3} \Delta_h^3 + \cdots. \,



The analogous formulas for the backward and central difference operators are

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


  \Bigl[ \frac{\Delta_h}{h} ~,~ x\, T^{-1}_h \Bigr] = [ D ~,~ x ] = I ~.



~(x)_n\equiv  (xT_h^{-1})^n=x (x-h) (x-2h) \cdots (x-(n-1)h) ,

so that

\frac{\Delta_h}{h} ~(x)_n=n ~(x)_{n-1} ~,


For example, the umbral sine is

\sin (x\,T_h^{-1}) = x -\frac{(x)_3}{3!} +  \frac{(x)_5}{5!} - \frac{(x)_7}{7!} + ...   ~.


\frac{\Delta_h}{h}~(1+\lambda h)^{x/h} =\frac{\Delta_h}{h} ~e^{\ln (1+\lambda h) ~x/h}= \lambda ~e^{\ln (1+\lambda h) ~x/h} ~,

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.[5] This umbral exponential thus amounts to the exponential generating function of the Pochhammer symbols.


\delta (x) \mapsto \frac{\sin \bigl[ \frac{\pi}{2}(1+x/h) \bigr]}{ \pi (x+h) }~,

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


Rules for calculus of finite difference operators[edit]

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.

 \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}
\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)



  • 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 \mu_k depend on point x : \mu_k=\mu_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.

  • The generalized difference can be seen as the polynomial rings R[T_h] . It leads to difference algebras.

Finite difference in several variables[edit]


Some partial derivative approximations are (using central step method):

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


 f_{xy}(x,y) \approx \frac{f(x+h, y+k) - f(x+h, y) - f(x, y+k) + 2 f(x,y) - f(x-h, y) - f(x, y-k) + f(x-h, y-k)}{2hk}     ~,

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

See also[edit]


  5. ^ Zachos, C. (2008). "Umbral Deformations on Discrete Space-Time". International Journal of Modern Physics A 23 (13): 2005–2014. doi:10.1142/S0217751X08040548. 
  6. ^ Curtright, T. L.; Zachos, C. K. (2013). "Umbral Vade Mecum". Frontiers in Physics 1. doi:10.3389/fphy.2013.00015. 
  10. ^ 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 .

External links[edit]