Lab 17: Lagrange and Divided Difference Lab

Type any x values (all different) and y values. The table shows each Lagrange basis value or each divided-difference term: use it to check your hand work.

Lagrange and divided differences

Try this

Run it. Do both methods give 35?
Add the point (4, 78). Which coefficient appears, and what is its value?
Change X to 10 (extrapolation). Is the answer believable? Compare with 10³ + 10² − 10 + 2.

Q1 Write Lagrange's interpolation formula for three points.

P(x) = y_0\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)} + y_1\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)} + y_2\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}

.

Q2 Give one advantage of divided differences over Lagrange.

Adding a new point only adds one row to the table and one term to the formula; Lagrange must recompute every basis polynomial.

Q3 Find

f(2)

from

x

: 0, 1, 3, 4 and

f

:

-12

,

-9

, 3, 12.

L_0(2) = \frac{(1)(-1)(-2)}{(-1)(-3)(-4)} = -\tfrac16

,

L_1(2) = \tfrac23

,

L_2(2) = \tfrac23

,

L_3(2) = -\tfrac16

;

f(2) = 2 - 6 + 2 - 2 = -4

.

Q4 What is inverse interpolation?

Finding the

x

that gives a known

y

by interpolating

x

as a function of

y

(swap the columns of the table). It works when

y

is monotonic over the data.

Q5 Why not find the coefficients by solving the Vandermonde system?

It costs

O(n^3)

and the Vandermonde matrix is badly ill-conditioned (about

10^{16}

for 20 equally spaced points on

[0, 1]

), so the coefficients lose all their digits.