Programming Assignment 2

In this assignment we will explore the accuracy of polynomial interpolation for large n. It turns out

that the interpolating polynomial usually does not converge to the function as n → ∞ when the grid

points are uniformly spaced, but there is another set of points, the Chebyshev grid points, in which it is

guaranteed to converge under very mild assumptoins on f. (f only needs to be Lipshitz continuous.)

1. Write a program that begins function yout = interpolate1(f,xin,xout). Here f is a function

handle (like we have been using for Newton’s method, etc.), xin contains the interpolation points, and

xout contains the evaluation points. The program should return yout, the values of the interpolating

polynomial P(x) evaluated at each point in xout. Use the formula

P(x) = Xn

j=0

f(xj )Lj (x), Lj (x) = Y

k6=j

x − xk

xj − xk

,

where the xj are the entries of the vector xin and x ranges over the entries of xout. Do this with

n = 10, 19, 50, 99 on two grids:

xinU = linspace(-1,1,n+1) (uniform),

xinC = cos(linspace(-pi,0,n+1)) (Chebyshev).

Note that the Chebyshev grid points are clustered more closely at the endpoints of the interval. For output,

use xout=linspace(-1,1,500), and for the function, use f = @(x) 1.0 ./ (1+9*x.^2).

2. Write a second program function yout = interpolate2(f,xin,xout) that does exactly the

same thing as above, but using the following (barycentric) formula for the interpolating polynomial:

P(x) =

f(xj ) x = xj

Pn

j=0

λj f(xj )

x−xj

?Pn

j=0

λj

x−xj

, x 6∈ {x0, . . . , xn}

, λj =

1

Q

k6=j

(xj − xk)

.

In case you are curious, the derivation of barycentric interpolation is given in chapter 5 of Trefethen’s book,

Approximation Theory and Approximation Practice, which is posted on bCourses.

Submit your codes interpolate1.m, interpolate2.m and a write-up briefly explaining how your

codes work and showing 8 plots: First four: for n ∈ {10, 19} and xin ∈ {xinU,xinC}, plot f(x) and P(x)

on top of each other, using either code for P(x). Last four: for n ∈ {50, 99} and xin ∈ {xinU,xinC}, plot

semilogy(xout,1.0e-18+abs([youtA1-f(xout),youtA2-f(xout)]),’linewidth’,1), where A=U or A=C

and youtA1 and youtA2 are the results of the two codes you wrote. Examples with n = 14 and n = 99 are

given below. (Modify the instructions above as needed if you are not using Matlab).

−1 −0.5 0 0.5 1

0

0.2

0.4

0.6

0.8

1

−1 −0.5 0 0.5 1

0

0.2

0.4

0.6

0.8

1

1.2

1.4

−1 −0.5 0 0.5 1

10−20

10−10

100

1010

1020

Chebyshev, n=14 uniform, n=14

uniform, n=99

barycentric (green)

usual lagrange formula (blue)

(semilog plots of error)

P(x) f(x)