Newton's Finite Differences Interpolation Method

Topics: Interpolation

---

Let $y=f(x)$ be a function whose exact definition we don’t know. All we know is various values of $f(x)$, like so:

${\mathbf{x}}_{\mathbf{i}}$	${\mathbf{y}}_{\mathbf{i}}=\mathbf{f}({\mathbf{x}}_{\mathbf{i}})$
$x_0$	$y_0$
$x_1=x_0+h$	$y_1$
$x_2=x_0+2h$	$y_2$
$x_3=x_0+3h$	$y_3$
$⋮$	$⋮$
$x_n=x_0+nh$	$y_n$

Notice that every $x_i$ must be spaced by a constant $h$, so that $x_k=x_0+kh$.

Non-Constant Spacing

If we have a table where the spacing between every $x_i$ is not constant, then we must use another interpolation method, like Newton’s divided differences method, which is very similar to this one.

We will be able to interpolate $y_k=f(x_k)$ for any $x_k$ within the constraints of the table by using a method known as Newton’s finite differences interpolation method.

Differences §

First, we’ll define what a difference is.

The first differences are the differences between two consecutive values of $y$. We denote these differences as $a_i$:

$$\begin{array}{rl}{a}_0& =y_1-y_0\\ a_1& =y_2-y_1\\ a_2& =y_3-y_2\\ ⋮& \\ a_k& =y_{k+1}-y_k\end{array}$$

Similarly, the second differences are the differences between two consecutive first differences, and they are denoted as $b_i$:

$$\begin{array}{rl}{b}_0& =a_1-a_0\\ b_1& =a_2-a_1\\ b_2& =a_3-a_2\\ ⋮& \\ b_k& =a_{k+1}-a_k\end{array}$$

In the same way, we have third differences $c_i$, fourth differences $d_i$, etc. We can also write these differences as $\Delta y_i$, ${\Delta }^2{y}_i$, ${\Delta }^3{y}_i$, etc.

The number of difference tiers we have will depend on the size of our table (the amount of known points).

Differences Table

We can arrange all these differences in a table like so:

${\mathbf{x}}_{\mathbf{i}}$	${\mathbf{y}}_{\mathbf{i}}$	${\mathbf{a}}_{\mathbf{i}}$	${\mathbf{b}}_{\mathbf{i}}$	${\mathbf{c}}_{\mathbf{i}}$	${\mathbf{d}}_{\mathbf{i}}$
$x_0$	$y_0$
		$a_0$
$x_1$	$y_1$		$b_0$
		$a_1$		$c_0$
$x_2$	$y_2$		$b_1$		$d_0$
		$a_2$		$c_1$
$x_3$	$y_3$		$b_2$		$d_1$
		$a_3$		$c_2$
$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$
$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$d_{n-4}$
$⋮$	$⋮$	$⋮$	$⋮$	$c_{n-3}$
$x_{n-1}$	$y_{n-1}$	$⋮$	$b_{n-2}$
		$a_{n-1}$
$x_n$	$y_n$

Interpolation Formulas §

Given an $x_k$ contained within the constraints of the table (i.e. $x_0\le x_k\le x_n$), we can use these differences to interpolate its $y_k=f(x_k)$ with one of two formulas that are used to obtain an interpolating polynomial.

For both of them, we choose a specific $x_i$ in our table as an anchor value; we’ll set this value to be $x_0$.

Our choice between these two formulas will depend on the amount of differences that can be used with a given one (the greater, the better the approximation), as well as on how close $x_k$ is to $x_0$ (the closer, the better).

Forwards Interpolation §

Let $k$ be:

$$k=\frac{x_k-x_0}{h}$$

We can obtain an approximation to our $y_k=f(x_k)$ with the forwards interpolation formula:

$$y_k=y_0+k{a}_0+\frac{k(k-1)}{2!}{b}_0+\frac{k(k-1)(k-2)}{3!}{c}_0+\dots$$

Backwards Interpolation §

Let $k$ be:

$$k=\frac{x_0-x_k}{h}$$

We can obtain our $y_k=f(x_k)$ with the backwards interpolation formula:

$$y_k=y_0-k{a}_{-1}+\frac{k(k-1)}{2!}{b}_{-2}-\frac{k(k-1)(k-2)}{3!}{c}_{-3}+\dots$$