Numerical Analysis I, Fall 2020 (http://www.math.nthu.edu.tw/˜ wangwc/)

Homework Assignment for Week 07

Goal: Study both theoretical and practical aspects of Lagrangian interpolating polynomials.

1. Section 3.1: Problem 6(a). Write a program to evaluate the degree three polynomial using for loops.

Hint: One can compute

L_{n,k}(x) = ∏_{{i=0, \atop i≠k}}^{n} \frac{(x − x_{i})}{(x_{k} − x_{i})}

with a for loop in i for each of the k = 0, ⋯, n, then evaluate

P (x) = ∑_{k=0}^{n} f(x_{k})L_{n,k}(x)

with another for loop on k. Note that, in C, the index for an array a(i) starts with i = 0 by default. However, the index starts with i = 1 in matlab. One should shift the index in the Lagrange interpolation formula accordingly.

Remark: This is not the most efficient method to evaluate the Lagrangian interpolation. The proper way is to evaluate P (x) using Neville’s method in section 3.2. An alternative way is to compute the coefficients of P (x) using Newton’s divided-difference formula in section 3.3, then evaluate P (x).

2. Section 3.1: Problems 9, 10, 13(a), 17 (the last sentence simply means h = (10 − 1)/n for some positive integer n).

3. Let x_{0}, ⋯, x_{n} be uniformly spaced nodes on [a, b] with x_{j} = a + jh, h = (b − a)/n.

(a) Show that |(x − x_{0}) ⋯ (x − x_{n})| ≤ n!h^{n+1} on a ≤ x ≤ b. Hint: Can you find an upper bound for max_{0≤i≤n, x_{0}≤x≤x_{n}} |x − x_{i}|?

(b) Let P_{n} be the degree n interpolating polynomial of e^{x} with uniformly spaced nodes on [0, 1]. Show that

max_{0≤x≤1} |e^{x} − P_{n}(x)| ≤ Ch^{n} → 0 as n → ∞

Note that uniform convergence of interpolating polynomials as in (b) does not hold in general. The Illustration on p154-p157 is a good example. In general, we only have

max_{a≤x≤b} |f(x) − P_{n}(x)| ≤ C_{n}h^{n}

from Theorem 3.3. A well known example with similar behavior is f(x) = 1/(1 + x^{2}) on [−5, 5] with uniformly spaced nodes.