Polynomial interpolation — Lagrange form, Newton's divided differences: Foundations

This page assumes you know nothing beyond " $x$ times $x$ is $x^{2}$ " and "a graph has a horizontal axis and a vertical axis". Every letter, subscript, product sign and squiggle used by the parent note is built here, from the floor up, in the order you need them.

0. The picture we are always in

Before any symbol: we have a piece of graph paper. A few dots are marked. We want a rule — a function — whose graph is a single connected curve touching every dot.

Figure — Polynomial interpolation — Lagrange form, Newton's divided differences

Look at the amber dots. There are infinitely many wiggly curves through them, but only one polynomial of a chosen low degree. That uniqueness is the whole reason the topic works — hold that thought.

1. A point and its coordinates: $(x_{i}, y_{i})$

The picture: pick a dot. Walk right along the horizontal axis until you're under it — that distance is $x$ . Then walk up — that distance is $y$ .

Why the topic needs it: our data is a list of dots, so every dot needs a name.

The subscript $i$

The picture: imagine numbered tags hanging off each dot: dot 0, dot 1, dot 2. We start counting at 0 (a computing habit) so that " $n + 1$ dots" are numbered $0, 1, \dots, n$ .

2. The function $f$ behind the dots

The picture: think of $f$ as the true hidden curve; our dots are just a few places where we peeked at its height. Interpolation tries to guess the rest of $f$ from those peeks.

Why the topic needs it: the error formula and the divided differences $f [\dots]$ all speak about this hidden $f$ — so $f$ must exist as a named object before those symbols appear.

3. What "polynomial" and "degree" mean

The picture below shows how degree controls how many bends a curve can make.

Why the topic needs it: the whole subject is choosing these dials so the curve hits the dots.

4. The Greek letters and the "distinct" condition

The picture: two dots stacked in the same vertical line would demand the curve be at two heights above one $x$ — impossible for a function. That's why nodes must be spread out horizontally.

Why the topic needs it: distinctness is exactly what makes the solution unique (next section) — the denominators $x_{i} - x_{j}$ in Lagrange are never zero, and the Vandermonde determinant is nonzero.

5. Sum $\sum$ and product $\prod$ — the two big loops

The parent note leans hard on two symbols. They are just shorthand for "do this repeatedly".

The condition $j = 0 j \neq = i \prod$ just means "multiply over all $j$ except $j = i$ ". The picture: a row of factors with one gap punched out where $j = i$ .

Why the topic needs it: Lagrange's basis is a product; Newton's polynomial is a sum of products. These two loops are the entire notation of the parent formulas.

6. The Lagrange basis "switch" $L_{i} (x)$

Now that we have the product sign, we can meet the symbol $L_{i}$ that the parent page (and the map below) uses.

Why this formula does the job, in two moves:

The numerator $\prod_{j \neq = i} (x - x_{j})$ is zero whenever $x$ lands on one of the other nodes — that gives the "0 elsewhere".
Dividing by $\prod_{j \neq = i} (x_{i} - x_{j})$ (the numerator's value at $x = x_{i}$ ) scales it to exactly 1 at $x_{i}$ .

Why the topic needs it: stacking these switches, each scaled by its height, forces a curve through every dot — that is exactly the Lagrange interpolant on the parent page.

7. The Vandermonde matrix and its determinant (why "unique")

For the Vandermonde grid this number works out to a product over all ordered pairs of nodes: $det = \prod_{i < j} (x_{j} - x_{i}) .$

Why the topic needs it: this non-zero product is the exact statement of "distinct nodes ⇒ one and only one interpolating polynomial".

8. Slope, secant slope, and divided differences $f [\dots]$

Newton's divided differences are built on the idea of slope, applied to the hidden function $f$ from §2.

Why the topic needs it: these numbers $2, 3, - 2$ are precisely Newton's coefficients on the parent page.

9. The error toolkit: factorial and derivatives

The error formula uses two more symbols. You only need to recognise them here; Taylor series develops them fully.

Why the topic needs it: together $\frac{f ^{(n + 1)} ( ξ )}{( n + 1 )!}$ scales the product $\prod (x - x_{i})$ into the actual gap between the true function $f$ and $P (x)$ — the Runge phenomenon is this product growing near interval ends.

10. How it all connects

Read top-to-bottom: naming dots, the hidden function $f$ , and powers gives dials; distinct nodes make the dial-setting unique via a non-zero determinant; the two loop-symbols dress that unique curve as Lagrange switches $L_{i}$ or Newton brackets $f [\dots]$ ; slopes feed Newton; factorial and derivatives measure the leftover error at the mystery point $ξ$ .

Equipment checklist

Cover the right side and test yourself.

What does the subscript in

x_{3}

tell you?

It labels which dot (dot number 3); it is not a power.

How are

y_{i}

and

f (x_{i})

related?

They are the same number —

y_{i}

is the height of dot

i

, and

f

is the hidden function that produced it, so

y_{i} = f (x_{i})

What is the degree of

- 2 x^{2} + 11 x - 7

2 — the highest power that appears.

How many coefficients (free dials) does a degree-

\leq n

polynomial have?

n + 1

, namely

a_{0}, \dots, a_{n}

What does "distinct nodes" mean and why is it required?

No two

x_{i}

are equal; otherwise a function would need two heights at one position, and the Vandermonde determinant would vanish.

Give the formula and the "switch" property of

L_{i} (x)

L_{i} (x) = \prod_{j \neq = i} \frac{x - x _{j}}{x _{i} - x _{j}}

; it is 1 at

x_{i}

and 0 at every other node.

Expand

\sum_{i = 0}^{2} y_{i} L_{i} (x)

y_{0} L_{0} (x) + y_{1} L_{1} (x) + y_{2} L_{2} (x)

Expand

\prod_{j = 0 j \neq = 1}^{2} (x - x_{j})

for that range.

(x - x_{0}) (x - x_{2})

— skip the

j = 1

factor.

What does the condition

i < j

under

\prod

ensure?

Each pair of nodes is used exactly once and no node is paired with itself.

What is a secant slope in words?

Rise over run: change in height divided by change in horizontal position between two dots.

Write the second divided difference

f [x_{0}, x_{1}, x_{2}]

as a formula.

\frac{f [ x _{1} , x _{2} ] - f [ x _{0} , x _{1} ]}{x _{2} - x _{0}}

What does the Kronecker delta

δ_{ik}

equal?

1 if

i = k

, otherwise 0.

Compute

3!

1 \cdot 2 \cdot 3 = 6

What does

f^{(2)}

mean, and how is it different from

f^{2}

f^{(2)}

is the second derivative (differentiate twice);

f^{2}

would mean

f

multiplied by itself.

What is

ξ

in the error formula?

An unknown point somewhere between the nodes at which the

(n + 1)

-th derivative is evaluated; we only need that it exists.

Why does a unique interpolating polynomial exist for

n + 1

distinct nodes?

n + 1

dials matched to

n + 1

demands via a Vandermonde system whose determinant

\prod_{i < j} (x_{j} - x_{i})

is non-zero gives exactly one solution.

Connections

Parent topic
Vandermonde matrix — the grid that guarantees uniqueness.
Runge phenomenon — what the error product does near the ends.
Chebyshev nodes — smarter node placement.
Cubic splines — piecewise low-degree alternative.
Numerical differentiation — where derivatives come from.
Newton-Cotes quadrature — integrating the interpolant.
Taylor series — factorials and derivatives, developed fully.