1Polynomial interpolation

IB Numerical Analysis

1.3 The Newton formula

The idea of Newton’s formula is as follows — for

k

= 0

, ··· , n

, we write

p

k

∈ P

k

[

x

]

for the polynomial that satisfies

p

k

(x

i

) = f

i

for i = 0, ··· , k.

This is the unique degree-

k

polynomial that satisfies the first

k

+ 1 conditions,

whose existence (and uniqueness) is guaranteed by the previous section. Then

we can write

p(x) = p

n

(x) = p

0

(x) + (p

1

(x) − p

0

(x)) + ··· + (p

n

(x) − p

n−1

(x)).

Hence we are done if we have an efficient way of finding the differences

p

k

−p

k−1

.

We know that

p

k

and

p

k−1

agree on

x

0

, ··· , x

k−1

. So

p

k

−p

k−1

evaluates to

0 at those points, and we must have

p

k

(x) − p

k−1

(x) = A

k

k−1

Y

i=0

(x − x

i

),

for some A

k

yet to be found out. Then we can write

p(x) = p

n

(x) = A

0

+

n

X

k=1

A

k

k−1

Y

i=0

(x − x

i

).

This formula has the advantage that it is built up gradually from the interpo-

lation points one-by-one. If we stop the sum at any point, we have obtained

the polynomial that interpolates the data for the first

k

points (for some

k

).

Conversely, if we have a new data point, we just need to add a new term, instead

of re-computing everything.

All that remains is to find the coefficients

A

k

. For

k

= 0, we know

A

0

is the

unique constant polynomial that interpolates the point at x

0

, i.e. A

0

= f

0

.

For the others, we note that in the formula for

p

k

− p

k−1

, we find that

A

k

is

the leading coefficient of

x

k

. But

p

k−1

(

x

) has no degree

k

term. So

A

k

must

be the leading coefficient of

p

k

. So we have reduced our problem to finding the

leading coefficients of p

k

.

The solution to this is known as the Newton divided differences. We first

invent a new notation:

A

k

= f[x

0

, ··· , x

k

].

Note that these coefficients depend only on the first

k

interpolation points.

Moreover, since the labelling of the points

x

0

, ··· , x

k

is arbitrary, we don’t have

to start with x

0

. In general, the coefficient

f[x

j

, ··· , x

k

]

is the leading coefficient of the unique

q ∈ P

k−j

[

x

] such that

q

(

x

i

) =

f

i

for

i = j, ··· , k.

While we do not have an explicit formula for what these coefficients are, we

can come up with a recurrence relation for these coefficients.

Theorem

(Recurrence relation for Newton divided differences)

.

For 0

≤ j <

k ≤ n, we have

f[x

j

, ··· , x

k

] =

f[x

j+1

, ··· , x

k

] − f[x

j

, ··· , x

k−1

]

x

k

− x

j

.

Proof.

The key to proving this is to relate the interpolating polynomials. Let

q

0

, q

1

∈ P

k−j−1

[x] and q

2

∈ P

k−j

satisfy

q

0

(x

i

) = f

i

i = j, ··· , k − 1

q

1

(x

i

) = f

i

i = j + 1, ··· , k

q

2

(x

i

) = f

i

i = j, ··· , k

We now claim that

q

2

(x) =

x − x

j

x

k

− x

j

q

1

(x) +

x

k

− x

x

k

− x

j

q

0

(x).

We can check directly that the expression on the right correctly interpolates

the points

x

i

for

i

=

j, ··· , k

. By uniqueness, the two expressions agree. Since

f

[

x

j

, ··· , x

k

],

f

[

x

j+1

, ··· , x

k

] and

f

[

x

j

, ··· , x

k−1

] are the leading coefficients of

q

2

, q

1

, q

0

respectively, the result follows.

Thus the famous Newton divided difference table can be constructed

x

i

f

i

f[∗, ∗] f[∗, ∗, ∗] ··· f[∗, ··· , ∗]

x

0

f[x

0

]

f[x

0

, x

1

]

x

1

f[x

1

] f[x

0

, x

1

, x

2

]

f[x

1

, x

2

]

.

.

.

x

2

f[x

2

] f[x

2

, x

3

, x

4

] ··· f[x

0

, x

1

, ··· , x

n

]

f[x

2

, x

3

]

.

.

.

x

3

f[x

3

]

.

.

.

.

.

.

.

.

.

.

.

.

x

n

f[x

n

]

From the first

n

columns, we can find the

n

+ 1th column using the recurrence

relation above. The values of

A

k

can then be found at the top diagonal, and

this is all we really need. However, to compute this diagonal, we will need to

compute everything in the table.

In practice, we often need not find the actual interpolating polynomial. If

we just want to evaluate

p

(

ˆx

) at some new point

ˆx

using the divided table, we

can use Horner’s scheme, given by

S <- f[x

0

,..., x

n

]

for k = n - 1,..., 0

S <- (^x - x

k

)S + f[x

0

,..., x

k

]

end

This only takes O(n) operations.

If an extra data point

{x

n+1

, f

n+1

}

is added, then we only have to compute

an extra diagonal

f

[

x

k

, ··· , x

n+1

] for

k

=

n, ··· ,

0 in the divided difference table

to obtain the new coefficient, and the old results can be reused. This requires

O(n) operations. This is less straightforward for Lagrange’s method.