Divided differences are the coefficients that make polynomial interpolation usable without solving a new linear system each time a data point is added. Given values of a function at finitely many distinct nodes, they measure the coefficient of the highest-degree term in the interpolating polynomial over those nodes. This makes them central to [Polynomial Interpolation](/page/Polynomial%20Interpolation), Newton Polynomial, Finite Difference, and the numerical study of [Derivative](/page/Derivative) approximation.

The main point is that divided differences package local information in a symmetric algebraic form. For nearby nodes they resemble derivatives; for separated nodes they describe global interpolation data. They also explain why Newton's interpolation formula updates one node at a time, while the Lagrange formula treats all nodes at once.

## Definition

When a function is known only at finitely many nodes, the central interpolation question is which polynomial those data determine. The coefficient of the highest possible power is the part that changes when the interpolation order increases, so it is the coefficient worth naming first.

[definition: Divided Difference] Let $n$ be a nonnegative integer, let $(x_0, \ldots, x_n)$ be a tuple of pairwise distinct [real numbers](/page/Real%20Numbers), and let $X_n=\{x_0,\ldots,x_n\}$. The order-$n$ divided difference at the ordered nodes $(x_0,\ldots,x_n)$ is the functional \begin{align*} D_{x_0,\ldots,x_n}: \mathbb{R}^{X_n} \to \mathbb{R} \end{align*} defined as follows. Let $\mathcal{P}_n$ denote the [vector space](/page/Vector%20Space) of real polynomials of degree at most $n$. For a polynomial $q(t)$, write $[t^n]q(t)$ for the coefficient of $t^n$ in $q(t)$. For $f:X_n\to\mathbb{R}$, if $p\in \mathcal{P}_n$ is the unique polynomial satisfying $p(x_i)=f(x_i)$ for $0\le i\le n$, then \begin{align*} D_{x_0,\ldots,x_n}(f) = [t^n]p(t). \end{align*} The value $D_{x_0,\ldots,x_n}(f)$ is denoted by \begin{align*} f[x_0,\ldots,x_n]. \end{align*} [/definition]

The restriction to distinct nodes prevents denominators such as $x_k-x_j$ from vanishing once the recursive formula is introduced. Repeated nodes lead to Hermite divided differences, where derivative data replaces the missing separation between nodes.

The definition above uses both an ordered tuple and an underlying finite set, and those two pieces of data play different roles. The tuple controls the entries in a divided-difference table; the set is the domain on which the sampled function is known. Naming this node data prevents later formulas from blurring an algorithmic ordering with the interpolation problem itself.

[definition: Interpolation Nodes] Let $n$ be a nonnegative integer. An ordered list of interpolation nodes is a tuple $(x_0, \ldots, x_n)$ of pairwise distinct real numbers. Its underlying node set is \begin{align*} X_n = \{x_0, \ldots, x_n\} \subset \mathbb{R}. \end{align*} [/definition]

The notation $f[x_0,\ldots,x_n]$ is not evaluation of $f$ at a tuple. It records the nodes used to form the interpolation functional. For order zero, the interpolating polynomial is constant, so the divided difference recovers the given function value.

For computation, the leading-coefficient definition is too indirect: constructing the whole interpolating polynomial just to read one coefficient wastes the triangular structure of interpolation data. The recursive definition gives the Newton-table algorithm used in numerical interpolation.

[definition: Recursive Divided Difference] Let $(x_j,\ldots,x_k)$ be pairwise distinct real numbers with $0\le j\le k$, and let $X_{j,k}=\{x_j,\ldots,x_k\}$. The recursive divided difference is the functional \begin{align*} R_{x_j,\ldots,x_k}: \mathbb{R}^{X_{j,k}} \to \mathbb{R} \end{align*} defined as follows: for $f:X_{j,k}\to\mathbb{R}$, set $f[x_j] = f(x_j)$ and, for $j<k$, set \begin{align*} f[x_j,\ldots,x_k] = \frac{f[x_{j+1},\ldots,x_k]-f[x_j,\ldots,x_{k-1}]}{x_k-x_j}. \end{align*} [/definition]

This recursion divides a change in an order-$(k-j-1)$ divided difference by the span of the outer nodes. It is the analogue of a difference quotient after the original function values have been replaced by lower-order interpolation coefficients.

## Equivalent Characterisations

The recursive rule is convenient for computation, but it is not yet clear that it is measuring the same quantity as the interpolation coefficient that motivated divided differences. Without that agreement, the triangular table would produce numbers whose connection to the interpolating polynomial is only asserted, not justified. The key issue is whether each recursive entry is exactly the leading coefficient of the polynomial interpolating the corresponding nodes.

[quotetheorem:907]

This theorem justifies the triangular divided-difference table. Each entry depends on the two entries immediately below it from the previous order, so adding a new node appends one diagonal rather than recomputing a full interpolation problem.

The recursive definition also has to agree with the other standard ways of constructing the interpolating polynomial. In Lagrange form, the polynomial is written directly from basis functions attached to the nodes. In Newton form, the same polynomial is built one node at a time, with divided differences as the coefficients in the triangular table. In Vandermonde form, one instead writes the unknown polynomial as $a_0+a_1t+\cdots+a_nt^n$ and solves the interpolation equations for the coefficient list $(a_0,\ldots,a_n)$.

To compare these constructions without changing the underlying interpolation problem, we need to translate their notations into one common polynomial language. The comparison theorem uses slightly more formal notation for this same picture. Here $\mathbb{R}[t]$ means the set of polynomials in the variable $t$ with real coefficients. The notation $\mathcal{P}_n(\mathbb{R})$ is the same polynomial space earlier denoted by $\mathcal{P}_n$: real polynomials of degree at most $n$. A vector in $\mathbb{R}^{n+1}$ is just an ordered list of $n+1$ real numbers, so in this context it records the coefficients of $1,t,\ldots,t^n$. With that vocabulary fixed, the next theorem says that the Lagrange, Vandermonde, and Newton descriptions are three coordinate systems for one interpolating polynomial.

[quotetheorem:8329]

This equivalence explains why divided differences can be used interchangeably with Lagrange weights or Vandermonde coefficient vectors once the polynomial space and coefficient conventions have been fixed. It also shows that the Newton table is not a separate construction, but a computationally efficient coordinate system for the unique interpolating polynomial.