Suppose a data set of points

(x_0, y_0), (x_1, y_1), ... (x_{n-1}, y_{n-1})

We want to find a polynomial P(x) such for all TODO

Lagrange’s Polynomial

We’ll construct these:

l_i (x) = ?_{j=0, i \ne j}^{n-1} \frac{x-x_j}{x_i - x_j}

TODO What is it?

If you expand the big multiplication, it looks like:

l_x (x) = \frac{x - x_0}{x_i - x_0} \times \frac{x - x_1}{x_i - x_1} \times ...

Notice if you ever have j = i, you would ???.

We want to multiply everything by ??? (image???) and add them all up.

L(x) = \sum_{i=0}^{n-1} y_i l_i (x)

If we put in x_i, we get y_i (???). If we put in anything else, we’ll just get some other value (soe interpolated value) ????

Example: Apply lagrange’s to these points

(0,1), (0.5, 1.3), (1, 1.7), (1.5, 2.1)

l_0 (x) = \frac{x - 0.5}{0 - 0.5} \times \frac{x-1}{0-1} \times \frac{x-1.5}{0-1.5}

Notice how we skip x=0

l_1 (x) = TODO

Notice how we skip x=1

l_2 (x) = TODO

Notice how we skip x=2

l_3 (x) = TODO

Now we simplify or something???

Newton’s Polynomial

Is this another method? I have no fucking clue.

We use lagrange polynomial, but factor out the constants to end up with some special form called Newton’s nested form.

Divided Differences:

c = ???

???

P_1(x) = 1 + 0.6x

This is the same as Lagrange, but the difference is how we got there.

If add one more points,

(0,1) , (0.5,1.3) , (1.1/7)

The polynomial is now

P_2(x) = P_1(x) c_2 (x-x_0) (x-x_1)

We want to ????

We take a constant c_2 because ???.

• Goal: Find c_2 such that when we plug in x_2, we get y_2 (WHY?)

Now we can generalize this to n terms.

Lets compute the c values as if we only have one point. We’ll call them f[x_i]. These are constants, because f[x_i] = y_i

Somehow we get something of the form

f[x_0, x_1] f[x_1, x_2] ... f[x_{n-1}, x_{n-2}

The generalized form of ??? is:

f[x_i, x_{i+1} = \frac{ f[x_{i+1}] - f[x_i] }{ x_{i+1} - x_i }

Actually, the generalized form is

f[x_i, x_{i+1}, ..., x_j] = ???

Those are the formulas, but building a table is a piece of cake.

0,1 0.5,1.3 1, 1.7 1.5, 2.1

Note: When implementing this, we can use a cache to speed up calculations.

Remember the constants you need are the top diagonal.

Above, we just did:

f[0,1] = \frac{1.3 - 1}{0.5 - 0} = 0.6

How do you compute this? No clue.

Finally, we plug into the polynomial ????.

P(x) = c_0 + c_1 (x-x_0) + c_2 (x-x_0) (x - x_1) = c_3 (x-x_0) (x - x_1) (x-x_2)

Which yields ???

Again, this yields the same polynomial as Lagrange, except ???.