MATH20602 Numerical Analysis 1 February 10, 2014 Problem Sheet 3 d write computer programs (in M ATLAB). (3.1) Show that the polynomial pn (x) interpolating f (x) at xi can be written Pn w f (xk )/(x − xk ) Pn k , pn (x) = k=0 k=0 wk /(x − xk ) for x 6= xk where 1 , j6=k (xk − xj ) wk = Q k = 0, . . . , n. This is called the barycentric representation of pn (x). Comment on how efficient it is to evaluate the barycentric form, as compared to the Lagrange form. HINT: Show that pn (x) = n Y (x − xk ) k=0 n X k=0 fk wk . (x − xk ) (3.2) Let x0 = 0, x1 = 1, x2 = −1 and f (x) = cos(πx). Compute the barycentric form of p2 (x). (3.3) Let p(x) = (a + bx)/(1 + cx) and suppose we wish to satisfy p(xi ) = yi , i = 1, 2, 3 for distinct xi . Does such a p(x) exist and is it unique? Why would you prefer a rational function to a polynomial? (3.4) (Newton’s divided differences) 1. For the data (xi , yi ) = (−1, −1), (0, 3), (2, 11), (3, 27), compute the divided difference table and use it to construct p3 (x). Evaluate p(−2). 2. Add an extra point x = 4, y = 19 to the table. Form the divided difference table for these data by adding an upward slanting diagonal to the table. Form the quartic polynomial q(x) that interpolates these five points. 1 MATH20602 Numerical Analysis 1 February 10, 2014 (3.5) (Chebyshev Polynomials) d For n ≥ 0 and x ∈ [−1, 1] define the Chebyshev polynomial of degree n by Tn (x) = cos(n arccos(x)). 1. Show that the Tn satisfy the recurrence relation Tn+1 (x) − 2xTn (x) + Tn−1 (x) = 0 for n ≥ 1. Conclude from this that Tn (x) is a polynomial of degree n with leading term 2n−1 xn . 2. Using M ATLAB or Python, plot the polynomials Tn for n = 0, . . . , 5 and find an explicit expression for the roots. 3. Let x0 , . . . , xn be the roots of the polynomial Tn+1 (x). Given a function f ∈ C (n+1) ([−1, 1]) and the unique interpolation polynomial pn (x) of f at the points xi , 0 ≤ i ≤ n, show that the interpolation error can be bounded as |f (x) − pn (x)| ≤ Mn+1 , 2n (n + 1)! where Mn+1 = maxξ∈[−1,1] |f (n+1) (ξ)|. 4. Using M ATLAB or Python, plot on the interval [−1, 1], for n = 0, . . . , 5, • The function f (x) = 1/(1 + 25x2 ); • The unique interpolation polynomial pn (x) of f at equispaced points x0 , . . . , xn on [−1, 1]; • The unique interpolation polynomial pn (x) of f at the roots x0 , . . . , xn of Tn+1 (x). Can the error bound derived in part 3 explain what is observed in this experiment? 2