Forward Difference
Goals of this chapter
Understand the definition and properties of the forward difference operator $\Delta$, how to build a forward difference table, and Newton's forward difference interpolation formula.
Prerequisites
Contents
Introduction: Why Forward Differences?
We often want a derivative $f'(x)$ but cannot differentiate a formula: the data may be measurements available only at discrete points, or the function may exist only as a computer program. The simplest tool for such situations is the forward difference. By taking the difference between the values at two neighbouring points, we can estimate how much the function changes.
Taking differences also helps us find the rule behind a sequence. The differences between neighbours in $1, 4, 9, 16, 25$ are $3, 5, 7, 9$, and their differences are $2, 2, 2$, which are constant. Because the second differences are constant, the original sequence is given by a quadratic ($n^2$). This chapter treats the operation of "taking differences" systematically.
1. Definition
For a function $f(x)$, the forward difference is defined as follows.
Definition of the forward difference
$$\Delta f(x) = f(x + h) - f(x)$$
Here $h > 0$ is the step size.
Intuitively, $\Delta f(x)$ is the "amount of change" of $f$ over the interval $[x,\; x+h]$. It is the discrete counterpart of $f'(x)\,h$ in calculus.
2. Higher-Order Differences
Applying the difference operation repeatedly gives higher-order differences.
The $n$-th forward difference
$$\begin{aligned} \Delta^n f(x) &= \sum_{k=0}^{n} (-1)^{n-k} \\ &\qquad \times \binom{n}{k} f(x + kh) \end{aligned}$$
Writing out the first few explicitly gives the following.
- $\Delta^0 f(x) = f(x)$ (the identity operator)
- $\Delta^1 f(x) = f(x+h) - f(x)$
- $\Delta^2 f(x) = f(x+2h) - 2f(x+h) + f(x)$
- $\Delta^3 f(x) = f(x+3h) - 3f(x+2h)$ $+\, 3f(x+h) - f(x)$
Note how binomial coefficients appear with alternating signs. The $n$-th difference uses $n+1$ function values.
Difference Table
From function values at equally spaced points $x_i = x_0 + ih$ we can build a difference table.
| $i$ | $x_i$ | $f_i$ | $\Delta f_i$ | $\Delta^2 f_i$ | $\Delta^3 f_i$ |
|---|---|---|---|---|---|
| 0 | $x_0$ | $f_0$ | |||
| $\Delta f_0$ | |||||
| 1 | $x_1$ | $f_1$ | $\Delta^2 f_0$ | ||
| $\Delta f_1$ | $\Delta^3 f_0$ | ||||
| 2 | $x_2$ | $f_2$ | $\Delta^2 f_1$ | ||
| $\Delta f_2$ | |||||
| 3 | $x_3$ | $f_3$ |
Each column is computed as the difference of two adjacent values in the column to its left: $\Delta f_i = f_{i+1} - f_i$ and $\Delta^2 f_i = \Delta f_{i+1} - \Delta f_i$.
3. Difference Operators
Treating the forward difference as a formal operator makes the relations between operations clear.
Main Operators
- Shift operator $E$: $Ef(x) = f(x+h)$
- Forward difference operator $\Delta$: $\Delta f(x) = f(x+h) - f(x)$
- Identity operator $I$: $If(x) = f(x)$
- Differential operator $D$: $Df(x) = f'(x)$
Basic relations between the operators
$$\Delta = E - I$$
that is, $E = I + \Delta$. Moreover, by formal power series expansion,
$$E = e^{hD}$$
Combining these gives
$$\Delta = e^{hD} - I$$
which provides a bridge between differences and derivatives.
The $n$-th difference is the $n$-th power of the operator, $\Delta^n = (E - I)^n$, and the binomial expansion gives
$$\Delta^n = \displaystyle\sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} E^k$$
which recovers the binomial formula of the previous section.
4. Newton's Forward Difference Interpolation Formula
Given function values $f_i$ at equally spaced points $x_i = x_0 + ih$ ($i = 0, 1, \ldots, n$), Newton's forward difference interpolation formula reads as follows.
Newton's forward difference interpolation formula
With $s = (x - x_0)/h$,
$$P_n(x) = \displaystyle\sum_{k=0}^{n} \binom{s}{k} \Delta^k f_0$$
where $\displaystyle\binom{s}{k} = \dfrac{s(s-1)(s-2)\cdots(s-k+1)}{k!}$ is the generalised binomial coefficient.
Expanded, this is
$$\begin{aligned} P_n(x) = {} & f_0 + s\,\Delta f_0 \\ & + \dfrac{s(s-1)}{2!}\,\Delta^2 f_0 \\ & + \dfrac{s(s-1)(s-2)}{3!}\,\Delta^3 f_0 + \cdots \end{aligned}$$
A characteristic feature is that the interpolating polynomial is built from the top row of the difference table ($\Delta^k f_0$) alone.
Worked example
Suppose $x_0 = 0,\; h = 1$ and $f(0)=1,\; f(1)=2,\; f(2)=5,\; f(3)=10$. The difference table gives
$\Delta f_0 = 1,\; \Delta f_1 = 3,\; \Delta f_2 = 5$
$\Delta^2 f_0 = 2,\; \Delta^2 f_1 = 2$
$\Delta^3 f_0 = 0$
Hence
$$\begin{aligned} P_3(x) &= 1 + x \cdot 1 \\ &\quad + \dfrac{x(x-1)}{2}\cdot 2 \\ &\quad + \dfrac{x(x-1)(x-2)}{6}\cdot 0 \\ &= 1 + x + x(x-1) \\ &= x^2 + 1 \end{aligned}$$
Since the third difference is 0, the data are represented exactly by the quadratic $x^2 + 1$.
5. Relation to the Derivative
The forward difference and the derivative are related by the following basic limit as $h \to 0$.
Forward difference quotient and the derivative
If $f$ is differentiable,
$$\begin{aligned} \lim_{h \to +0} \dfrac{\Delta f(x)}{h} &= \lim_{h \to +0} \dfrac{f(x+h) - f(x)}{h} \\ &= f'(x) \end{aligned}$$
(Since we defined $h > 0$, this is the limit from the right. If $f$ is differentiable, it equals $f'(x)$.)
This is exactly the definition of the derivative, and it shows that the forward difference quotient $\Delta f(x)/h$ is a first-order approximation of the derivative $f'(x)$.
Likewise for higher orders,
$$\dfrac{\Delta^n f(x)}{h^n} \approx f^{(n)}(x)$$
In operator language this corresponds to $\Delta/h \to D$ as $h \to 0$.
6. Truncation Error
When $f$ is sufficiently smooth, Taylor expansion lets us estimate the error of the forward difference quotient.
$$\begin{aligned} f(x+h) ={} & f(x) + hf'(x) \\ & + \dfrac{h^2}{2}f''(x) + O(h^3) \end{aligned}$$
gives
$$\begin{aligned} \dfrac{\Delta f(x)}{h} &= \dfrac{f(x+h) - f(x)}{h} \\ &= f'(x) + \dfrac{h}{2}f''(x) + O(h^2) \end{aligned}$$
Truncation error
$$\begin{gathered} \dfrac{\Delta f(x)}{h} - f'(x) = \dfrac{h}{2}f''(\xi), \\ \xi \in (x,\; x+h) \end{gathered}$$
The truncation error is $O(h)$. This is called first-order accurate.
For comparison, the truncation error of the central difference is $O(h^2)$ (second-order accurate), one order better than the forward difference. The forward difference, however, needs points on one side only, so it can be used where points exist on just one side, such as the left end of a domain. In time-evolution problems it is also the basis of explicit methods (such as the forward Euler method) that compute the value at the next time step directly from the current value.
Balancing Against Rounding Error
Making $h$ smaller reduces the truncation error, but $f(x+h)$ and $f(x)$ become closer, so cancellation error grows. If the unit roundoff of floating-point arithmetic is $\varepsilon_{\mathrm{mach}}$, the rounding error is of order $O(\varepsilon_{\mathrm{mach}}/h)$, and the $h$ that minimises the total error is of order
$$h_{\mathrm{opt}} \sim \sqrt{\varepsilon_{\mathrm{mach}}}$$
In double precision ($\varepsilon_{\mathrm{mach}} \approx 10^{-16}$), $h \approx 10^{-8}$ is a good guide.
Caution: smaller $h$ is not always more accurate
Because the truncation error is $O(h)$, it is tempting to think that "the smaller $h$, the more accurate the result". This is not true. Here are the errors when the derivative $e$ of $f(x) = e^x$ at $x = 1$ is computed in double precision with the forward difference quotient.
| $h$ | $10^{-1}$ | $10^{-4}$ | $10^{-8}$ | $10^{-12}$ | $10^{-14}$ |
|---|---|---|---|---|---|
| Error | $1.4 \times 10^{-1}$ | $1.4 \times 10^{-4}$ | $6.6 \times 10^{-9}$ | $4.3 \times 10^{-4}$ | $9.3 \times 10^{-3}$ |
The error is smallest around $h = 10^{-8}$; below that, cancellation makes it grow. At $h = 10^{-12}$ the error is worse than at $h = 10^{-4}$.
7. Applications
7.1 Numerical Differentiation
When the derivative is hard to obtain analytically, the forward difference quotient $\Delta f/h$ is the simplest means of numerical differentiation. When it is not accurate enough, it is often combined with the central difference or with Richardson extrapolation.
7.2 Finite Difference Methods (Numerical Solution of PDEs)
In the numerical solution of partial differential equations, the forward difference is widely used to discretise the time direction.
FTCS scheme (heat equation)
For the one-dimensional heat equation $\dfrac{\partial u}{\partial t} = \alpha \dfrac{\partial^2 u}{\partial x^2}$, approximating the time derivative by a forward difference and the second spatial derivative by a central difference gives
$$\dfrac{u_i^{n+1} - u_i^n}{\Delta t} = \alpha \dfrac{u_{i+1}^n - 2u_i^n + u_{i-1}^n}{(\Delta x)^2}$$
(FTCS: Forward Time, Central Space). This explicit scheme is stable when $\alpha\,\Delta t / (\Delta x)^2 \le 1/2$.
7.3 Sequences and Difference Equations
A difference equation $\Delta y_n = g(n, y_n)$ in a discrete system is the discrete counterpart of the differential equation $y' = g(x, y)$ in a continuous system. It can be computed step by step as the recursion $y_{n+1} = y_n + g(n, y_n)$, and its correspondence with Euler's method is clear.
7.4 Combinatorics and Detecting Polynomial Degree
If $f$ is a polynomial of degree $n$, then $\Delta^n f$ is constant and $\Delta^{n+1} f = 0$. Therefore the degree of the original polynomial can be read off from the stage at which a column of the difference table becomes 0. This property is also used in combinatorics to guess the general term of a sequence.
8. Practice Problems
Problem 1 (basic): For $f(x) = x^3$ with $h = 1$, build the difference table at $x = 0, 1, 2, 3, 4$ and check that $\Delta^3 f$ is constant. Find that constant.
Hint
The function values are $0, 1, 8, 27, 64$. Take differences three times. By Section 7.4, the $n$-th difference of a polynomial of degree $n$ is constant.
Problem 2 (standard): Approximate the derivative of $f(x) = e^x$ at $x = 0$ by the forward difference quotient with $h = 0.1$. Check that the error lies within the range given by the formula $\dfrac{h}{2}f''(\xi)$ ($0 < \xi < 0.1$) of Section 6.
Hint
$\dfrac{e^{0.1} - 1}{0.1} \approx 1.0517$. The true value is $f'(0) = 1$. The value $f''(\xi) = e^{\xi}$ lies between $1$ and $e^{0.1}$.
Problem 3 (advanced): Using Taylor expansion, find the difference between $\dfrac{\Delta^2 f(x)}{h^2}$ and $f''(x)$, and state the order of the error.
Hint
Expand $f(x+2h)$ and $f(x+h)$ up to the $h^3$ term and substitute them into $\Delta^2 f(x) = f(x+2h) - 2f(x+h) + f(x)$. Look at the first term that remains after dividing by $h^2$.
9. Frequently Asked Questions
Q1. What is the difference between the forward difference and the central difference?
The forward difference $\Delta f(x) = f(x+h) - f(x)$ uses information from one side only, and its truncation error is $O(h)$. The central difference $\delta f(x) = f(x+h/2) - f(x-h/2)$ uses information from both sides and is more accurate, with truncation error $O(h^2)$. The forward difference, however, can be applied at boundary points and is simple to implement.
Q2. When is Newton's forward difference interpolation formula used?
It performs polynomial interpolation using a difference table when data are given at equally spaced points. It is especially accurate near the beginning of the data (the starting end), and it is widely used for interpolating numerical tables and as a basis for numerical integration.
Q3. How is the forward difference used in the numerical solution of partial differential equations?
Using the forward difference to discretise the time direction of a partial differential equation gives the explicit finite difference method. A typical example is the FTCS scheme, which approximates the time derivative of the heat equation by a forward difference and the spatial derivative by a central difference. It is simple to implement, but stability requires $\alpha\,\Delta t / (\Delta x)^2 \le 1/2$.
10. References
- Wikipedia, "Finite difference"
- Wikipedia, "Newton's forward difference formula"
- R. L. Burden & J. D. Faires, Numerical Analysis, 10th ed., Cengage, 2016.
- K. E. Atkinson, An Introduction to Numerical Analysis, 2nd ed., Wiley, 1989.
- C. Jordan, Calculus of Finite Differences, 3rd ed., Chelsea, 1965.