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

Brief Answers to Quiz 03

Nov 17, 2020.

1. Let P_{n} be the degree n interpolating polynomial of cos(2x) on the uniformly spaced nodes x_{0}, ⋯, x_{n} on [0, 1] with x_{j} = jh, h = 1/n. Is it true that

max_{0≤x≤1} | cos(2x) − P_{n}(x)| → 0 as n → ∞?

Give all details and explain.

Ans:

Yes. (2 pts) Let f(x) = cos(2x). Then

max_{0≤x≤1} | cos(2x) − P_{n}(x)| = max_{0≤x≤1} |\frac{f^{(n+1)}(ξ(x))}{(n + 1)!}(x − x_{0})(x − x_{1}) … (x − x_{n})| (8 pts)
≤ max_{0≤ξ≤1} |\frac{f^{(n+1)}(ξ)}{(n + 1)!}| max_{0≤x≤1} |(x − x_{0})(x − x_{1}) … (x − x_{n})|
≤ \frac{2^{n+1}}{(n + 1)!}n!\frac{1}{n^{n+1}} (8 pts)
= \frac{1}{n + 1} (\frac{2}{n})^{n+1}
≤ \frac{1}{n + 1} → 0 as n → ∞(2 pts).

2. Denote by P_{0,1,···,k}(x) the Lagrange interpolating polynomial on the data set (x_{0}, f(x_{0})), (x_{1}, f(x_{1}), ⋯ (x_{k}, f(x_{k})). Express P_{0,1,···,k} in terms of P_{0,1,···,j−1,j+1,···,k} and P_{0,1,···,i−1,i+1,···,k}. Then verify your answer is indeed the Lagrange interpolating polynomial.

Ans:

P_{0,1,···,k}(x) = \frac{(x − x_{j})P_{0,1,···,j−1,j+1,···,k}(x) − (x − x_{i})P_{0,1,···,i−1,i+1,···,k}(x)}{x_{i} − x_{j}}. (8 pts)

For t ≠ i and t ≠ j,

P_{0,1,···,k}(x_{t}) = \frac{(x_{t} − x_{j})f(x_{t}) − (x_{t} − x_{i})f(x_{t})}{x_{i} − x_{j}} = f(x_{t}).

For t = i,

P_{0,1,···,k}(x_{i}) = \frac{(x_{i} − x_{j})f(x_{i})}{x_{i} − x_{j}} = f(x_{i}).

For t = j,

P_{0,1,···,k}(x_{j}) = \frac{−(x_{j} − x_{i})f(x_{j})}{x_{i} − x_{j}} = f(x_{j}).

Finally, deg P_{0,1,···,j−1,j+1,···,k} ≤ k − 1 and deg P_{0,1,···,i−1,i+1,···,k} ≤ k − 1 imply that

deg P_{0,1,···,k} ≤ k. (12 pts)

3. A natural cubic spline S on [0, 2] is defined by

S(x) = \{ \begin{matrix}S_{0}(x) = 1 + 2x − x^{3}, & 0 ≤ x ≤ 1 \\ S_{1}(x) = 2 + b(x − 1) + c(x − 1)^{2} + d(x − 1)^{3}, & 1 ≤ x ≤ 2 \end{matrix}

Find b, c, d. Ans: Compute S′_{0}, S′_{1}, S′′_{0}, and S′′_{1}. (2 pts)

S′_{0}(1) = S′_{1}(1) (3 pts) ⇒ b = −1 (3 pts)
S′′_{0}(1) = S′′_{1}(1) (3 pts) ⇒ c = −3 (3 pts)
S′′_{1}(2) = 0 (3 pts) ⇒ d = 1 (3 pts)

4. Suppose that we are to construct a piecewise polynomial interpolation S(x) on the data (x_{0}, f(x_{0})), (x_{1}, f(x_{1})), ⋯, (x_{n}, f(x_{n})), with additional continuity conditions for S′, S′′ and S′′′ on the interior nodes x_{1}, ⋯, x_{n−1}. If we use polynomials of the same degree on each of the interval [x_{0}, x_{1}], ⋯, [x_{n−1}, x_{n}], what is the minimal degree needed in each interval? How many additional end conditions are needed? Count carefully and explain (give details). Ans: Values of S at x_{0}, x_{n}: one condtion each. Values of S at x_{1}, ⋯ x_{n−1}: two conditions each. Continuity of S′ at x_{1}, ⋯ x_{n−1}: one condition each. Continuity of S′′ at x_{1}, ⋯ x_{n−1}: one condition each. Continuity of S′′′ at x_{1}, ⋯ x_{n−1}: one condition each. (15 pts, 0 pts without details) Total 5n − 3 conditions. Therefore we require minimal 5n unknowns or degree 4 polynomials on each interval and additional 3 boundary conditions (5 pts).

5. Given four data (x_{i}, exp(−2x_{i})): (0.3, 0.5488), (0.4, 0.4493), (0.5, 0.3679) and (0.6, 0.3012) (you should generate the data yourself to avoid typo in inputting data). Use Inverse Interpolation to find the root of x = exp(−2x). You can use any algorithm for Lagrange interpolation. Extra credits for Neville’s method (or divided difference, if anyone knows it). After finding x, check yourself that x = exp(−2x) is indeed satisfied in case of a bug in your code. Need not show the last part. Hand in code, put all data within the code so that it can be executed immediately. Ans: Use Lagrange interpolation to interpolate the function t = f(s) at s = 0 where s_{i} = y_{i} − x_{i} and t_{i} = x_{i} (10 pts). Result: x^{∗} = f(0) ≈ 0.4263.... (10 pts). C programming: (extra 2 pts).