Assignment 2 polynomial interpolation

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)