---
tag: 155K06F4JF
kind: definition
name: Newton polynomial
msc: [65D05, 41A05]
defines: 9W77FPTM9E
uses: [N5ZHV4HWDC, SS1YMS2NPC, 04C5ZBG1WT]
sources:
  - url: https://en.wikipedia.org/wiki/Newton_polynomial
---

## Definition

Let $K$ be a [[field|04C5ZBG1WT]], let $n \ge 0$, and let $x_0, \dots, x_n \in K$ be pairwise distinct.
Let $f$ be a function defined at these points with values in $K$.
The *Newton polynomial* of $f$ at $x_0, \dots, x_n$ is
$$N(x) = \sum_{j=0}^{n} f[x_0, \dots, x_j] \prod_{k=0}^{j-1} (x - x_k),$$
where $f[x_0, \dots, x_j]$ are the [[divided differences|N5ZHV4HWDC]] of $f$ and the empty product for $j = 0$ is $1$.

## Remarks

$N$ has degree at most $n$ and $N(x_i) = f(x_i)$ for all $i$, so it is the [[interpolation polynomial|SS1YMS2NPC]] of the data, written in the Newton basis.
The first $j + 1$ terms form the interpolation polynomial at $x_0, \dots, x_j$.
It can be evaluated with nested multiplication, as in [[Horner's method|FYBQ3Z52Z7]].

Example: for $f(0) = 1$, $f(1) = 3$, $f(2) = 7$, the divided differences are $f[0] = 1$, $f[0, 1] = 2$, $f[1, 2] = 4$ and $f[0, 1, 2] = 1$.
So $N(x) = 1 + 2x + x(x - 1) = x^2 + x + 1$, and indeed $N(0) = 1$, $N(1) = 3$, $N(2) = 7$.

Non-example: $1 + 2x + 2x(x - 1)$ has the Newton shape but its last coefficient is not $f[0, 1, 2]$; its value at $2$ is $9 \ne 7$.

For equally spaced nodes $x_k = x_0 + kh$, the divided differences become forward differences divided by $k! \, h^k$, which gives the [[Newton–Gregory forward formula|Q4YAST023H]].