Finite Difference

The finite difference is the discrete analog of the Derivative. The finite Forward Difference of a function $f_p$ is defined as

$$\Delta f_p\equiv f_{p+1}-f_p,$$ (1)

and the finite Backward Difference as

$$\nabla f_p\equiv f_p-f_{p-1}.$$ (2)

If the values are tabulated at spacings $h$, then the notation

$$f_p\equiv f(x_0+ph)\equiv f(x)$$ (3)

is used. The $k$th Forward Difference would then be written as $\Delta^k f_p$, and similarly, the $k$th Backward Difference as $\nabla^k f_p$.

However, when $f_p$ is viewed as a discretization of the continuous function $f(x)$, then the finite difference is sometimes written

$$\Delta f(x)\equiv f(x+{\textstyle{1\over 2}})-f(x-{\textstyl... ... = 2\mathop{{\rm I}\lower3pt\hbox{{\rm I}}}\nolimits (x)*f(x),$$ (4)

where $*$ denotes Convolution and $\mathop{{\rm I}\lower3pt\hbox{{\rm I}}}\nolimits (x)$ is the odd Impulse Pair. The finite difference operator can therefore be written

$$\tilde\Delta=2 \mathop{{\rm I}\lower3pt\hbox{{\rm I}}}\nolimits *.$$ (5)

An $n$th Power has a constant $n$th finite difference. For example, take $n=3$ and make a Difference Table,

$$\matrix{x\cr 1\cr 2\cr 3\cr 4\cr 5\cr}\matrix{x^3\cr 1\cr 8\... ...\cr} \matrix{\Delta^3\cr 6\cr 6\cr}\matrix{\Delta^4\cr 0\cr}.$$ (6)

The $\Delta^3$ column is the constant 6.

Finite difference formulas can be very useful for extrapolating a finite amount of data in an attempt to find the general term. Specifically, if a function $f(n)$ is known at only a few discrete values $n=0$, 1, 2, ... and it is desired to determine the analytical form of $f$, the following procedure can be used if $f$ is assumed to be a Polynomial function. Denote the $n$th value in the Sequence of interest by $a_n$. Then define $b_n$ as the Forward Difference $\Delta_n\equiv a_{n+1}-a_n$, $c_n$ as the second Forward Difference $\Delta^2_n\equiv b_{n+1}-b_n$, etc., constructing a table as follows

$a_0\equiv f(0) \quad a_1\equiv f(1) \quad a_2\equiv f(2) \quad \ldots \quad a_p\equiv f(p)$
$\quad b_0\equiv a_1-a_0 \quad b_1\equiv a_2-a_1 \quad \ldots \quad b_{p-1}\equiv a_p-a_{p-1}$
$c_0\equiv b_2-b_1 \quad \ldots \quad \ldots$
$\ddots$	(7)

Continue computing $d_0$, $e_0$, etc., until a 0 value is obtained. Then the Polynomial function giving the values $a_n$ is given by

$$f(n)=\sum_{k=0}^p \alpha_k{n\choose k} = a_0+b_0n+{c_0n(n-1)\over 2}+{d_0n(n-1)(n-2)\over 2\cdot 3}+\ldots.$$ (8)

When the notation $\Delta_0\equiv a_0$, $\Delta_0^2\equiv b_0$, etc., is used, this beautiful equation is called Newton's Forward Difference Formula. To see a particular example, consider a Sequence with first few values of 1, 19, 143, 607, 1789, 4211, and 8539. The difference table is then given by

$1\quad 19\quad 143\quad 607\quad 1789\quad 4211\quad 8539$
$18\quad 124\quad 464\quad 1182\quad 2422\quad 4328$
$106\quad 340\quad 718\quad 1240\quad 1906$
$234\quad 378\quad 522\quad 666$
$144\quad 144\quad 144$
$0\quad 0$

Reading off the first number in each row gives $a_0=1$, $b_0=18$, $c_0=106$, $d_0=234$, $e_0=144$. Plugging these in gives the equation

$$f(n)=1 + 18 n + 53 n(n-1) + 39 n(n-1)(n-2)+ 6 n(n-1)(n-2)(n-3),$$ (9)

which simplifies to $f(n)=6n^4+3n^3+2n^2+7n+1$, and indeed fits the original data exactly!

Beyer (1987) gives formulas for the derivatives

$$h^n{d^n f(x_0+ph)\over dx^n} \equiv h^n{d^n f_p\over dx^n} \equiv {d^n f_p\over dp^n}$$ (10)

(Beyer 1987, pp. 449-451) and integrals

$$\int_{x_0}^{x_n} f(x)\,dx = h\int_0^n f_p\,dp$$ (11)

(Beyer 1987, pp. 455-456) of finite differences.

Finite differences lead to Difference Equations, finite analogs of Differential Equations. In fact, Umbral Calculus displays many elegant analogs of well-known identities for continuous functions. Common finite difference schemes for Partial Differential Equations include the so-called Crank-Nicholson, Du Fort-Frankel, and Laasonen methods.

See also Backward Difference, Bessel's Finite Difference Formula, Difference Equation, Difference Table, Everett's Formula, Forward Difference, Gauss's Backward Formula, Gauss's Forward Formula, Interpolation, Jackson's Difference Fan, Newton's Backward Difference Formula, Newton-Cotes Formulas, Newton's Divided Difference Interpolation Formula, Newton's Forward Difference Formula, Quotient-Difference Table, Steffenson's Formula, Stirling's Finite Difference Formula, Umbral Calculus

References

Finite Difference Equations

Abramowitz, M. and Stegun, C. A. (Eds.). ``Differences.'' §25.1 in Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, pp. 877-878, 1972.

Beyer, W. H. CRC Standard Mathematical Tables, 28th ed. Boca Raton, FL: CRC Press, pp. 429-515, 1987.

Boole, G. and Moulton, J. F. A Treatise on the Calculus of Finite Differences, 2nd rev. ed. New York: Dover, 1960.

Conway, J. H. and Guy, R. K. ``Newton's Useful Little Formula.'' In The Book of Numbers. New York: Springer-Verlag, pp. 81-83, 1996.

Iyanaga, S. and Kawada, Y. (Eds.). ``Interpolation.'' Appendix A, Table 21 in Encyclopedic Dictionary of Mathematics. Cambridge, MA: MIT Press, pp. 1482-1483, 1980.

Jordan, K. Calculus of Finite Differences, 2nd ed. New York: Chelsea, 1950.

Levy, H. and Lessman, F. Finite Difference Equations. New York: Dover, 1992.

Milne-Thomson, L. M. The Calculus of Finite Differences. London: Macmillan, 1951.

Richardson, C. H. An Introduction to the Calculus of Finite Differences. New York: Van Nostrand, 1954.

Spiegel, M. Calculus of Finite Differences and Differential Equations. New York: McGraw-Hill, 1971.