Finite differences and interpolation · Lecture 17

Lagrange and Divided-Difference Interpolation

Interpolation when the data are not equally spaced: Lagrange's formula built from basis polynomials, Newton's divided differences that grow one point at a time, inverse interpolation, and why both beat solving for the coefficients.

Md Mahbub E Noor · Assistant Professor
CSE-3107 Numerical Methods · B.Sc. 3rd Year 1st Semester
Department of CSE, University of Barishal

Why this lecture

The problem: a sensor that skipped some readings

A data logger was supposed to record every second, but readings at $t = 3$ and $4$ were lost. We need the value at $t = 3$ .

The remaining times 0, 1, 2, 5 are not equally spaced
Newton's forward and backward formulas (Lecture 16) do not apply
We still want the polynomial through all the points, and a quick way to update it when a reading is recovered
Two answers: Lagrange (one formula, any spacing) and divided differences (a table that grows)

$t$ (s)	0	1	2	5
$y$	2	3	12	147

Md Mahbub E Noor

Lecture 17: Lagrange and Divided Differences

University of Barishal

2 / 22

Today's goals

Build Lagrange basis polynomials and interpolate with any spacing
Build a divided-difference table and use Newton's general formula
Add a new data point without starting again
Use inverse interpolation to find $x$ for a given $y$
Explain why these formulas beat solving the Vandermonde system

Last time

Newton forward and backward: equal spacing only.

Today

Same polynomial, any spacing: two ways to write it.

Finite differences and interpolation · you are here

L15 · Finite Differences and Operators→L16 · Newton's Forward and Backward Interpolation→L17 · Lagrange and Divided-Difference Interpolation→L18 · Spline Interpolation and the Runge Phenomenon

Builds on: L15, L16

Md Mahbub E Noor

Lecture 17: Lagrange and Divided Differences

University of Barishal

3 / 22

Start here

The idea in one picture

Three dots, not necessarily equally spaced.Build a small curve that passes through dot 0 and is zero at the other x values.Another one for dot 1: correct there, zero at x₀ and x₂.And one for dot 2.Add the three curves. At each x only one of them is non-zero, so the sum passes through every dot.

In plain words

Points need not be equally spaced
Give each point its own small curve: right at that point, zero at the others
Add them up: the sum passes through every point

New words today

node: an x value where the data are known
basis polynomial Lᵢ: equals 1 at node i and 0 at the other nodes
divided difference: a slope, a slope of slopes, …
unique: whatever the method, the polynomial is the same

Md Mahbub E Noor

Lecture 17: Lagrange and Divided Differences

University of Barishal

4 / 22

Lagrange's formula

Basis polynomial: 1 at its own point, 0 at all the others

L_i(x) = \prod_{j \ne i}\frac{x - x_j}{x_i - x_j}, \qquad L_i(x_j) = \begin{cases} 1 & j = i \\ 0 & j \ne i \end{cases}

Interpolating polynomial

P(x) = \sum_{i=0}^{n} y_i\,L_i(x) = y_0L_0(x) + y_1L_1(x) + \cdots + y_nL_n(x)

At $x = x_k$ every term vanishes except $y_kL_k(x_k) = y_k$ : the curve passes through every point
Each $L_i$ has degree $n$ , so $P$ has degree at most $n$
No equal spacing needed, no table needed
Same polynomial as Newton's formulas whenever both apply

Md Mahbub E Noor

Lecture 17: Lagrange and Divided Differences

University of Barishal

5 / 22

The method, step by step

Lagrange interpolation, step by step

List the points $(x_0, y_0), \dots, (x_n, y_n)$ ; all $x_i$ must be different
For each $i$ : numerator $\prod_{j\ne i}(x - x_j)$ , denominator $\prod_{j\ne i}(x_i - x_j)$
Compute $L_i(x)$ = numerator / denominator
Add up $y_iL_i(x)$
Check: the $L_i(x)$ must add up to 1

Pseudocode

input x[0..n], y[0..n], X
sum ← 0
for i = 0 … n:
    L ← 1
    for j = 0 … n, j ≠ i:
        L ← L·(X − x[j]) / (x[i] − x[j])
    sum ← sum + y[i]·L
return sum

Two nested loops: $O(n^2)$ work for every new $X$ .

Md Mahbub E Noor

Lecture 17: Lagrange and Divided Differences

University of Barishal

6 / 22

Problem 1: $y(3)$ by Lagrange

Points

(0, 2)

,

(1, 3)

,

(2, 12)

,

(5, 147)

. Find

y(3)

.

1

L_0(3) = \dfrac{(3-1)(3-2)(3-5)}{(0-1)(0-2)(0-5)} = \dfrac{-4}{-10} = 0.4

,

\quad L_1(3) = \dfrac{(3)(1)(-2)}{(1)(-1)(-4)} = -1.5

2

L_2(3) = \dfrac{(3)(2)(-2)}{(2)(1)(-3)} = 2

,

\quad L_3(3) = \dfrac{(3)(2)(1)}{(5)(4)(3)} = 0.1

; check:

0.4 - 1.5 + 2 + 0.1 = 1

✓

3

y(3) = 2(0.4) + 3(-1.5) + 12(2) + 147(0.1) = 0.8 - 4.5 + 24 + 14.7

y(3) = 35

.

Md Mahbub E Noor

Lecture 17: Lagrange and Divided Differences

University of Barishal

7 / 22

Newton's divided differences

Divided differences: differences divided by the x-gap they span

\begin{aligned} f[x_i, x_{i+1}] &= \frac{f[x_{i+1}] - f[x_i]}{x_{i+1} - x_i} \\ 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} \end{aligned}

Newton's divided-difference formula

\begin{aligned} P(x) = {} & f[x_0] + f[x_0,x_1](x - x_0) \\ & + f[x_0,x_1,x_2](x - x_0)(x - x_1) + \cdots \end{aligned}

Equal spacing: $f[x_0, \dots, x_k] = \Delta^k y_0/(k!\,h^k)$ , giving the forward formula back
Order of the points does not matter: divided differences are symmetric
Adding a point adds one term; nothing else changes
Evaluate with nested multiplication (Horner): $O(n)$ per $x$

Md Mahbub E Noor

Lecture 17: Lagrange and Divided Differences

University of Barishal

8 / 22

The method, step by step

Divided differences, step by step

Column 0: the $y_i$
Column $k$ : $\dfrac{\text{(lower entry)} - \text{(upper entry)}}{x_{i+k} - x_i}$ , where the denominator spans all points involved
Read the coefficients $f[x_0], f[x_0,x_1], \dots$ from the top edge
Evaluate $P(x)$ by nested multiplication
New point? Add it at the bottom: one new entry per column, one new term

Pseudocode

input x[0..n], y[0..n], X
c ← copy of y
for k = 1 … n:               # build table
    for i = n … k:
        c[i] ← (c[i] − c[i−1]) / (x[i] − x[i−k])
# c[k] = f[x0, …, xk]
p ← c[n]
for k = n−1 … 0:             # Horner
    p ← c[k] + (X − x[k])·p
return p

$O(n^2)$ once for the table, then $O(n)$ for each $X$ .

Md Mahbub E Noor

Lecture 17: Lagrange and Divided Differences

University of Barishal

9 / 22

Problem 2: the same data by divided differences

Build the divided-difference table for

t = 0, 1, 2, 5

and find

y(3)

. Then add the recovered reading

y(4) = 78

.

$x_i$	$f[x_i]$	first	second	third	fourth (with $x = 4$ )
0	2	$\frac{3-2}{1-0} = 1$	$\frac{9-1}{2-0} = 4$	$\frac{9-4}{5-0} = 1$	$\frac{1-1}{4-0} = 0$
1	3	$\frac{12-3}{2-1} = 9$	$\frac{45-9}{5-1} = 9$	$\frac{12-9}{4-1} = 1$
2	12	$\frac{147-12}{5-2} = 45$	$\frac{69-45}{4-2} = 12$
5	147	$\frac{78-147}{4-5} = 69$
4	78

$P(x) = 2 + 1\cdot x + 4x(x-1) + 1\cdot x(x-1)(x-2)$ , so $P(3) = 2 + 3 + 24 + 6 = 35$ . The new point adds one entry per column; the fourth divided difference is 0, so the data are a cubic.

Md Mahbub E Noor

Lecture 17: Lagrange and Divided Differences

University of Barishal

10 / 22

Explore: Lagrange and divided differences

Switch the method: the curve and the estimate do not change
Lagrange table: each $L_i(x)$ ; divided table: each coefficient and term
Add a point to the lists and watch only the last row change (divided)
The $\sqrt{x}$ preset shows a real interpolation error

Md Mahbub E Noor

Lecture 17: Lagrange and Divided Differences

University of Barishal

11 / 22

Problem 3: inverse interpolation

From

x

: 2, 3, 4 and

y = x^2

: 4, 9, 16, estimate the

x

at which

y = 10

(that is,

\sqrt{10}

).

1

Swap roles: treat

x

as a function of

y

, with points

(4, 2)

,

(9, 3)

,

(16, 4)

2

Lagrange in

y

at

y = 10

:

\;L_0 = \dfrac{(10-9)(10-16)}{(4-9)(4-16)} = -0.1

,

\;L_1 = \dfrac{(10-4)(10-16)}{(9-4)(9-16)} = \dfrac{36}{35}

,

\;L_2 = \dfrac{(10-4)(10-9)}{(16-4)(16-9)} = \dfrac{1}{14}

3

x = 2(-0.1) + 3\left(\tfrac{36}{35}\right) + 4\left(\tfrac{1}{14}\right) = 3.1714

x \approx 3.1714

(true

\sqrt{10} = 3.1623

, error 0.009). Inverse interpolation works when

y

is monotonic in the range.

Md Mahbub E Noor

Lecture 17: Lagrange and Divided Differences

University of Barishal

12 / 22

Classical vs numerical

Same polynomial, two approaches

Linear algebra

Classical (solve for the coefficients)

Write $P(x) = a_0 + a_1x + a_2x^2 + a_3x^3$
Four conditions $P(x_i) = y_i$ : a 4×4 Vandermonde system (Lecture 12)
Get $a = (2, -1, 1, 1)$ , then $P(3) = 35$

vs

Formula

Numerical (Lagrange / divided differences)

No system to solve
Divided differences: one small table, $P(3) = 35$
A new point: one more row, not a new system

When the classical approach cannot work

20 points on [0, 1]

The Vandermonde matrix has condition number about $10^{16}$ (Lecture 11): all 16 digits of double precision can be lost and the coefficients are garbage. Lagrange (in barycentric form) and divided differences never form that matrix and stay accurate.

Md Mahbub E Noor

Lecture 17: Lagrange and Divided Differences

University of Barishal

13 / 22

Lagrange and divided differences in Python and C

Lagrange: the two nested loops of the pseudocode
Divided differences built in place, then Horner
Both print $y(3) = 35$
Lab: add the point $(4, 78)$ and compare

Md Mahbub E Noor

Lecture 17: Lagrange and Divided Differences

University of Barishal

14 / 22

When polynomial interpolation goes wrong

Limitations shown failing

Many points, high degree: wild swings near the ends (Runge); look at the $L_i$ values: some are huge
Noisy data: the polynomial passes exactly through every error
Inverse interpolation far from the points is unreliable
Lagrange costs $O(n^2)$ per evaluation and restarts when a point is added

Md Mahbub E Noor

Lecture 17: Lagrange and Divided Differences

University of Barishal

15 / 22

Practice

Practice problem

Problem 4"Using Lagrange's interpolation formula, find

f(9)

from the table:

x

: 5, 7, 11, 13, 17;

f(x)

: 150, 392, 1452, 2366, 5202. Verify with Newton's divided-difference formula."

How to write a complete answer

Write the formula with all five basis polynomials evaluated at $x = 9$ , then add
Answer $f(9) = 810$
Divided differences: first 121, 265, 457, 709; second 24, 32, 42; third 1, 1; fourth 0
Newton: $150 + 121(4) + 24(4)(2) + 1(4)(2)(-2) = 810$ ✓; the zero fourth difference shows the data are a cubic

Md Mahbub E Noor

Lecture 17: Lagrange and Divided Differences

University of Barishal

16 / 22

When to use it

Lagrange and divided differences: method profile

Best case

A handful of points with any spacing
Divided differences: points arriving one at a time
Exact for polynomial data; elegant formulas for theory

Worst case

Many equally spaced points (Runge oscillation)
Noisy data: the curve chases the noise
Lagrange evaluated naively at many $x$ : $O(n^2)$ each

Best suited for

Irregular samples, few points
Deriving quadrature rules (Simpson, Gauss: Lecture 20)
Exact algebra over finite fields: secret sharing, error-correcting codes

Avoid when

Long data sets (splines, Lecture 18)
Noisy measurements (least squares, Lecture 23)
Solving for the monomial coefficients (Vandermonde)

Rule of thumb: few points, any spacing → divided differences (or barycentric Lagrange); many points → splines; noisy points → least squares.

Md Mahbub E Noor

Lecture 17: Lagrange and Divided Differences

University of Barishal

17 / 22

Comparative analysis: four ways to write one polynomial

Form	Spacing	Setup	Each new $x$	New point	Main use
Monomial (Vandermonde)	any	$O(n^3)$ solve, ill-conditioned	$O(n)$	resolve	avoid
Newton forward/backward	equal	$O(n^2)$ table	$O(n)$	one term	tables, hand work
Lagrange	any	none	$O(n^2)$ (barycentric $O(n)$ )	restart (barycentric: update)	theory, few points
Divided differences	any	$O(n^2)$ table	$O(n)$	one row, one term	irregular data

All four give the same polynomial through the same points; only cost and rounding differ.

Md Mahbub E Noor

Lecture 17: Lagrange and Divided Differences

University of Barishal

18 / 22

Roadmap

Limitations, and where we fix them

Both methods handle any spacing, but one polynomial through many points behaves badly.

What it does well (keep this)

Any spacing
Exact through the data
Divided differences grow one point at a time
Inverse interpolation for quick root estimates

LimitationHow it is overcomeWhere

Oscillation with many points (Runge)

→

Piecewise cubics: splines

Lecture 18 →

Noise is reproduced exactly

→

Fit instead of interpolate: least squares

Lecture 23 →

We need derivatives or integrals of tabulated data

→

Differentiate or integrate the interpolant

Lecture 19 →

Quadrature rules with unequal points

→

Gauss quadrature from Lagrange basis

Lecture 20 →

Md Mahbub E Noor

Lecture 17: Lagrange and Divided Differences

University of Barishal

19 / 22

Applications

Where this method runs in the real world

Click a card: each uses the Lagrange or divided-difference formula at a specific step.

Md Mahbub E Noor

Lecture 17: Lagrange and Divided Differences

University of Barishal

20 / 22

Checkpoint

Checkpoint · think, then discuss with your neighbourLagrange basis for

x_0 = 1

,

x_1 = 3

,

x_2 = 4

. What is

L_0(2)

?

A

\tfrac{1}{3}

B

-\tfrac{1}{3}

C

\tfrac{2}{3}

D

1

A.

L_0(2) = \dfrac{(2-3)(2-4)}{(1-3)(1-4)} = \dfrac{(-1)(-2)}{(-2)(-3)} = \dfrac{2}{6} = \tfrac13

.

Md Mahbub E Noor

Lecture 17: Lagrange and Divided Differences

University of Barishal

21 / 22

Summary

Key points

Lagrange: $P(x) = \sum y_iL_i(x)$ , $L_i(x) = \prod_{j\ne i}\frac{x - x_j}{x_i - x_j}$ ; any spacing
Divided differences: a table divided by spans; Newton's general formula, one term per new point
Same polynomial as Newton forward/backward; never solve the Vandermonde system
Inverse interpolation: swap $x$ and $y$ ; many points or noisy data need other tools

Opening problem: solved

$y(3) = 35$ by Lagrange and by divided differences; adding the recovered reading $y(4) = 78$ needed one new row, and its zero fourth divided difference showed the data are a cubic.

Homework

Find $f(2)$ by Lagrange from $x$ : 0, 1, 3, 4 and $f$ : $-12$ , $-9$ , 3, 12.
Build the divided-difference table for $x$ : 1, 2, 4, 7 and $f$ : 2, 8, 62, 338 and find $f(5)$ .
From $x$ : 1, 2, 3 and $y = x^3$ : 1, 8, 27, find by inverse interpolation the $x$ with $y = 10$ . Compare with $\sqrt[3]{10}$ .
Make your own secret-sharing example with a quadratic and check that any 3 shares recover the secret.

Next lecture

Splines and the Runge phenomenon. Why one polynomial through many points fails, and how piecewise cubics fix it.

Md Mahbub E Noor

Lecture 17: Lagrange and Divided Differences

University of Barishal

22 / 22

Lagrange and Divided-Difference Interpolation

The problem: a sensor that skipped some readings

Today's goals

The idea in one picture

Lagrange's formula

Lagrange interpolation, step by step

Problem 1: $y(3)$ by Lagrange

Newton's divided differences

Divided differences, step by step

Problem 2: the same data by divided differences

Explore: Lagrange and divided differences

Problem 3: inverse interpolation

Same polynomial, two approaches

Classical (solve for the coefficients)

Numerical (Lagrange / divided differences)

20 points on [0, 1]

Lagrange and divided differences in Python and C

Limitations shown failing

Practice problem

Lagrange and divided differences: method profile

Comparative analysis: four ways to write one polynomial

Limitations, and where we fix them

Where this method runs in the real world

🔑 Shamir's secret sharing

📀 Reed–Solomon codes

⏱️ Irregular time stamps

∫ Where Simpson's rule comes from

Checkpoint

Summary

Lagrange and Divided-Difference Interpolation

The problem: a sensor that skipped some readings

Today's goals

The idea in one picture

Lagrange's formula

Lagrange interpolation, step by step

Problem 1: y(3)y(3)y(3) by Lagrange

Newton's divided differences

Divided differences, step by step

Problem 2: the same data by divided differences

Explore: Lagrange and divided differences

Problem 3: inverse interpolation

Same polynomial, two approaches

Classical (solve for the coefficients)

Numerical (Lagrange / divided differences)

20 points on [0, 1]

Lagrange and divided differences in Python and C

Limitations shown failing

Practice problem

Lagrange and divided differences: method profile

Comparative analysis: four ways to write one polynomial

Limitations, and where we fix them

Where this method runs in the real world

🔑 Shamir's secret sharing

📀 Reed–Solomon codes

⏱️ Irregular time stamps

∫ Where Simpson's rule comes from

Checkpoint

Summary

Problem 1: $y(3)$ by Lagrange