Newton Divided Differences

students, imagine you are trying to predict the value of a function from a small set of known data points, like estimating the temperature at noon using readings from morning and afternoon 📈. In Numerical Analysis, one of the main ways to do this is polynomial interpolation, where we build a polynomial that passes through given points. A powerful tool for this is Newton divided differences.

What Newton divided differences do

The idea behind Newton divided differences is simple: if you know a function at several points, you can build an interpolating polynomial step by step. Instead of starting from a fully expanded polynomial, Newton’s method builds the polynomial in a layered form that is easy to compute and update.

Suppose we have data points $\bigl(x_0,f(x_0)\bigr)$, $\bigl(x_1,f(x_1)\bigr)$, $\dots$, $\bigl(x_n,f(x_n)\bigr)$, where all the $x_i$ values are distinct. Newton divided differences help us construct the interpolating polynomial $P_n(x)$ so that

$$P_n(x_i)=f(x_i) \quad \text{for } i=0,1,\dots,n.$$

This is part of Interpolation I, which also includes the Lagrange form of interpolation. Both methods create the same unique interpolating polynomial of degree at most $n$, but Newton’s form is especially useful when new data points are added later 🔧.

Starting with the simplest divided differences

The basic building block is the first divided difference. If we have two points $x_0$ and $x_1$, then the divided difference is

$$f[x_0,x_1]=\frac{f(x_1)-f(x_0)}{x_1-x_0}.$$

This looks like the slope of the line through the two points. In fact, it is exactly the slope of the secant line. So divided differences are a way to generalize slope ideas to higher-order interpolation.

For one point, we define the zero-order divided difference as

$$f[x_0]=f(x_0).$$

For three points, the second divided difference is defined recursively by

$$f[x_0,x_1,x_2]=\frac{f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0}.$$

This recursive pattern continues for more points. In general, the divided difference of order $k$ is built from two divided differences of order $k-1$.

The recursive pattern

The general recursive formula is

$$f[x_i,x_{i+1},\dots,x_{i+k}]=\frac{f[x_{i+1},\dots,x_{i+k}]-f[x_i,\dots,x_{i+k-1}]}{x_{i+k}-x_i}.$$

This formula is the heart of Newton divided differences. Each new layer uses information from the previous layer. That makes the method efficient and organized.

Let’s see the pattern clearly:

• Zero-order divided difference: $f[x_i]=f(x_i)$
• First-order divided difference: $f[x_i,x_{i+1}]$
• Second-order divided difference: $f[x_i,x_{i+1},x_{i+2}]$
• Higher-order divided differences continue in the same way

Each higher-order divided difference measures how the function values change after removing lower-order trends. This is one reason divided differences are useful in Numerical Analysis: they reveal the structure of the data while building the interpolating polynomial.

Newton form of the interpolating polynomial

Once the divided differences are computed, the interpolating polynomial can be written in Newton form:

$$P_n(x)=f[x_0]+fx_0,x_1+fx_0,x_1,x_2(x-x_1)+\cdots+f[x_0,x_1,\dots,x_n]\prod_{j=0}^{n-1}(x-x_j).$$

This formula may look long, but it follows a clear pattern. Each new term adds one more factor of the form $\bigl(x-x_j\bigr)$, and the coefficient is a divided difference.

For example, the first few terms are:

$$P_0(x)=f[x_0]$$

$$P_1(x)=f[x_0]+fx_0,x_1$$

$$P_2(x)=f[x_0]+fx_0,x_1+fx_0,x_1,x_2(x-x_1).$$

This nested style is very convenient because if a new point is added, the polynomial can be extended without rebuilding everything from scratch. That is a major advantage over some other interpolation formulas 😊.

A worked example

Let’s build an interpolating polynomial from the points $(1,2)$, $(2,3)$, and $(4,1)$.

First, list the values:

$$f[x_0]=2,\quad f[x_1]=3,\quad f[x_2]=1,$$

where $x_0=1$, $x_1=2$, and $x_2=4$.

Now compute the first divided differences:

$$f[x_0,x_1]=\frac{3-2}{2-1}=1,$$

$$f[x_1,x_2]=\frac{1-3}{4-2}=-1.$$

Next, compute the second divided difference:

$$f[x_0,x_1,x_2]=\frac{-1-1}{4-1}=-\frac{2}{3}.$$

So the Newton interpolating polynomial is

$$P_2(x)=2+1(x-1)-\frac{2}{3}(x-1)(x-2).$$

If we simplify, we still get a polynomial that passes through all three points. This example shows how divided differences produce the coefficients one at a time.

Why Newton divided differences are useful

Newton divided differences are popular because they are practical and flexible. Here are some key reasons:

1. They are recursive. Each new coefficient depends on previous ones, so the process is systematic.
2. They support adding data efficiently. If one more point is given, you can extend the polynomial instead of starting over.
3. They work with unequal spacing. Unlike methods based on equally spaced points, divided differences do not require equally spaced $x$-values.
4. They connect to the derivative idea. When points get very close together, divided differences relate to derivatives, which helps connect interpolation to calculus.

For example, if data comes from an experiment and a new reading arrives later, Newton form lets you update the model quickly. That is useful in engineering, science, and computer graphics 🌍.

Connection to the broader topic of Interpolation I

Interpolation I usually introduces the goal of finding a polynomial that matches given data. The two classic forms are Lagrange interpolation and Newton interpolation. Both represent the same unique interpolating polynomial, but they organize the computation differently.

• In Lagrange form, the polynomial is written as a sum of basis polynomials.
• In Newton form, the polynomial is written using divided differences and products like $\bigl(x-x_0\bigr)$, $\bigl(x-x_0\bigr)\bigl(x-x_1\bigr)$, and so on.

Newton divided differences fit into Interpolation I because they provide a practical way to build the interpolation polynomial and understand its coefficients. They are especially important in numerical computation, where efficiency and easy updating matter.

Important properties and interpretation

A key feature of divided differences is that they depend only on the data points, not on the order of algebraic expansion. The interpolating polynomial itself is unique, so Newton and Lagrange forms must agree even though they look different.

There is also a useful interpretation for smooth functions. For a sufficiently smooth function $f$, the higher-order divided differences are related to higher derivatives. In particular, if the points are close together, divided differences can be seen as discrete versions of derivative information.

This connection helps explain why Newton divided differences are not just a computational trick. They are a bridge between data tables and the calculus idea of how a function changes.

Conclusion

Newton divided differences are a core method in Numerical Analysis for polynomial interpolation. They give a recursive way to compute coefficients, form the Newton interpolating polynomial, and update the polynomial when new data is added. students, if you remember one big idea, it is this: divided differences turn a table of values into a structured polynomial model 📘. That makes them an essential part of Interpolation I and a strong foundation for more advanced numerical methods.

Study Notes

• Newton divided differences are used to build an interpolating polynomial from data points $\bigl(x_i,f(x_i)\bigr)$.
• The zero-order divided difference is $f[x_i]=f(x_i)$.
• The first divided difference is $f[x_i,x_{i+1}]=\dfrac{f(x_{i+1})-f(x_i)}{x_{i+1}-x_i}$.
• Higher-order divided differences are defined recursively by

$$f[x_i,\dots,x_{i+k}]=\frac{f[x_{i+1},\dots,x_{i+k}]-f[x_i,\dots,x_{i+k-1}]}{x_{i+k}-x_i}.$$

• The Newton interpolating polynomial has the form

$$P_n(x)=f[x_0]+fx_0,x_1+\cdots+f[x_0,\dots,x_n]\prod_{j=0}^{n-1}(x-x_j).$$

• Newton form is useful because it is recursive and easy to update when new data points are added.
• It works for distinct, not necessarily equally spaced, $x$-values.
• Newton divided differences are one of the two main interpolation forms in Interpolation I, along with Lagrange interpolation.
• The method helps connect data tables, polynomial interpolation, and ideas from calculus.