Newton polynomial

Builds on Divided differences Polynomial interpolation Field

Definition

Let $K$ be a field, 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 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 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.

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.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Tag	`155K06F4JF`
URI	`m2://155K06F4JF`
Kind	definition
Writing	W0 stub
MSC	65D05, 41A05
Defines	Newton polynomial
Uses	Divided differences, Polynomial interpolation, Field

Newton polynomial

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here