1.  (20 points) Consider the classical Lagrange interpolation formula for constructing an interpolating polynomial p(x) approximating f (x) at the points x1  < x2  < . . . < xn ,

where

n

p(x) =       f (xi)ai(x),

i=1

and

x 一 xi 

i=1 xk 一 xi .

ik

(a) In what situations could a loss of precision occur if we were to implement this

formula numerically, as written?

(b)  The accompanying codes provide an implementation of Lagrange interpolation.

How does this code avoid the numerical issues you described in part (a)?

(c)  Suppose that an interpolant constructed to approximate f (x) at n points and is evaluated at m points. What is the asymptotic cost of the classical Lagrange interpolation formula? What is the cost of the implementation analyzed in part (b)?

2.  (30 points) Consider the function

f (x) =

on the interval [一1, 1].

(a)  Plot both f (x) and the polynomial interpolant p(x) approximating f (x) at

the n equispaced nodes

2(i 一 1)

for n = 10, 20, 30 and δ = 0.2, 0.4. The resulting behavior is called the Ruoge pheoomeooo.

(b)  Explain the difference in the plots for δ = 0.2 and δ = 0.4. Hint: Recall the

formula for the remainder term in polynomial interpolation.

(c)  Estimate the quantity /f 一 p/尸  on [一1, 1] by evaluating the interpolant at

1000 equispaced points in [一1, 1], for δ = 0.2 and n = 10, 20, 30, 40, 50. Why does the error behave this way?

(d)  Estimate the quantity /f 一 p/尸  as in part (b), except only on the interval [一0.1, 0.1], for the same values of δ and n. Why does the error near the middle of the interval behave this way?

(e)  Construct the polynomial interpolant p(x) approximating f (x) at the n Cheby-

shev nodes

xi = cos╱  2i2n(一) 1 π、,        i = 1, 2, . . . , n,                         

Estimate  the  /f 一 p/尸  on  [一1, 1]  as  in  part  (b),  for  δ  =  0.2  and  n  = 10, 30, 50, 70. Why does the error behave this way?

3.  (30 points) Let xi , i = 1, 2, . . . , n, denote the Chebshev nodes defined by formula (5). Consider the n ( n matrix A defined by the formula

Ai,j  = Ti-1 (xj),        i, j = 1, 2, . . . , n.                               

It is possible to show that

(a)  Prove that the Clenshaw-Curtis quadrature weights w = (w1 , w2 , . . . , wn)T are given by the formula w = A-1y, where y = (y1 , y2 , . . . , yn)T  and yi  =

1-1 Ti-1 (x) dx.

(b)  Consider the function

f (x) = (µ + 1)lxlu .                                         

Let I =   1-1 f (x) dx and let Iˆn denote the n-point Clenshaw-Curtis quadrature rule applied to f (x). Let eˆn = I 一 Iˆn . Report eˆ20  for µ = 1, 2, . . . , 7. Why do you see these results?

(c) Fill in the following table for µ = 1, 3, 5, 7:

where

pˆn = log( n/2/ n)/ log(2).

Explain the convergence orders you observe.

4.  (25 points) Consider the integral

尸

exp(一x2 ) & (x + x2 + sin(3x + 1)) dx.

-尸

(a)  Suppose that, instead of evaluating the integral over the range  ( 一2, 2),

you evaluated it over the finite interval [一a, a]. What, approximately, is the smallest value of a such that the integral over the finite interval approximates the desired integral to within machine precision?

(b) Evaluate the integral over the finite interval using the Clenshaw-Curtis quadra-

ture rule from question 3. How many points do you need to achieve machine precision?

(c)  Evaluate the integral over the finite interval using the trapezoidal rule. How many points do you need to achieve machine precision?

(d) Which rule is better in this case, and why?

5.  (30 points) It is possible to show that

1

Pn(x)eTikα dx = 2i & jn(πk),                                  

-1

where Pn(x) is the Legendre polynomial of degree n and jv(x) denotes the so-called spherical Bessel function

jv(x) = ← Jv+ (x),