CSCD37—Analysis of Numerical Algorithms for Computational Mathematics, Winter 2023

Assignment #2: Polynomial Interpolation / Error

Due: March 14, 2023 at 11:45 p.m.

This assignment is worth 12% of your final grade.

Warning: Your electronic submission on MarkUs affirms that this assignment is your own work and no one else’s, and is in accordance with the University of Toronto Code of Behaviour on Academic Matters, the Code of Student Conduct, and the guidelines for avoiding plagiarism in CSCD37.

This assignment is due by 11:45 p.m. March 14.  If you haven’t finished by then, you may hand in your assignment late with a penalty as specified in the course information sheet.

[10]    1.   Prove the fundamental relationship between divided differences and derivatives; namely:

y(k)(xi)

xi+j →xi                                                                                        k!

1SjSk

provided y e ck .

[10]    2.   Consider the function y e cn+1 and the polynomial p e pn which satisfies

k

p(j)(xi) = y(j)(xi); j = 0, . . . , ji; i = 0, . . . , k;       (ji + 1) = n + 1;

i=0

with all of the xi distinct. The error in this polynomial interpolant is given by

E(x) = y(x) - p(x) =  (x - x0 )j0 +1 (x - x1 )j1 +1 . . . (x - xk)jk+1                 (1)

where ξ e span{x0 , . . . , xk, x} = [min{x0 , . . . , xk, x}, max{x0 , . . . , xk, x}] provided y e cn+1 on span{x0 , . . . , xk, x}.

This is a fundamental formula in Numerical Approximation. The following is an outline of a possible derivation of (1). In this question you will expand this outline by proving certain key statements.       If x = xi, i = 0, . . . , k, then y(x) - p(x) = 0 since p interpolates y at these k + 1 points. Also, E(xi) = 0 in (1) since (xi - xi)ji+1 = 0. Therefore, (1) holds when x = xi .

Now assume x  xi for any i = 0, . . . , k and consider x fixed. Let F (t) = y(t) - p(t) - C W (t) where C = [y(x) - p(x)]/W (x) is a constant and

W (t) = (t - x0 )j0 +1 (t - x1 )j1 +1 . . . (t - xk)jk+1                                              (2)

is a polynomial of degree n + 1. Clearly F (x) = 0, and also

F(j)(xi) = 0; j = 0, . . . , ji; i = 0, . . . , k .                                       (3)

Therefore, counting multiplicities, F (t) has at least n+2 zeros in span{x0 , . . . , xk, x}, which implies F(n+1)(t) has at least 1 zero in span{x0 , . . . , xk, x}, or, in other words,

F(n+1)(ξ) = 0, ξ e span{x0 , . . . , xk, x}.

(4)

Therefore,

F(n+1)(ξ) = 0 =÷ y(n+1)(ξ) - (n + 1) ! C = 0 =÷ C = y(n+1)(ξ)

But

y(x) - p(x)                                 y(n+1)(ξ)

W (x)                                      (n + 1) !

Now for the statements you must prove:

(a) Prove that W (t) in (2) is a polynomial of degree n + 1.

(b) Explain how (4) follows from F (t) having at least n + 2 zeros in span{x0 , . . . , xk, x}.

(c) Prove (3) and (5).

[10]    3.   In lecture we proved that the roots of the Chebyshev polynomial

Tk(x) = cos(k cos-1 (x)), k = 0, 1, . . .                                         (6)

are the optimal interpolation points on [-1, 1].

(a) Prove that (6) is a polynomial of degree k for all k > 0.

(b) Derive the leading coefficient of (6) (i.e., the coefficient of xk).

(c) Derive the roots of (6) (i.e., the so-called Chebyshev points).

(d) Complete the proof showing why the Chebyshev points are optimal.

[10]   4.   Consider interpolating the Runge function y(x) = 1/(1 + 25x2 ) with p e pn using the Chebyshev points over [-1, 1]. This is a simple interpolation problem

p(xi) = y(xi); i = 0, . . . , n

and the interpolation error formula (1) reduces to:

y(n+1)(ξ)

(n + 1) !