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

Homework Assignment for Week 08

Goal: Study both theoretical and practical aspects Neville’s algorithm and piecewise polynomial interpolations (the cubic spline in particular).

1. Section 3.2: Problem 6, 8, 11, 12.

For problem 11, you will need to write a function (or subroutine) based on the practice in the recitation this Tuesday. The function takes the input vectors x, y, x^{∗}, where x ∈ R^{d}, y = f(x) ∈ R^{d} are data points and x^{∗} ∈ R^{m} is the vector of points to be interpolated (in problem 11, x^{∗} = 1 + \sqrt{10}, m = 1). The function then determines d by checking the lengths of x and/or y and outputs the interpolated values y^{∗} ∈ R^{m} as an approximation of f(x^{∗}). To start with, you can use direct evaluation of Lagrangian interpolating polynomials here (and also in problem 12) as in homework 7. You are encouraged to revise it to Neville’s method later on. Once the function is written, you can generate x, y from outside with any chosen d and m and call the function in the main program. At this point, you can plot the interpolating polynomial vs the original function with roughly d = 8 ∼ 12 and m = 60 ∼ 80. Bring your code next Tuesday to recitation in case of any problem or doubts. Do the same with cubic spline next week. What you will observe is known as Runge’s phenomenon. Repeat the procedure and change the original function from \frac{1}{1+x^{2}} to sin x, cos x and check if Runge’s phenomenon remains.

2. Section 3.5: Problems 12, 13, 14, 30, 34, 35.

Remark: In problem 12: ‘clamped’ means S′(1) = f′(1), S′(3) = f′(3). In problem 13: ‘natural’ means S′′(1) = 0, S′′(3) = 0.

3. The requirement S(x), S′(x) and S′′(x) be continuous at interior nodes x_{1}, ⋯, x_{n−1} can be conveniently referred to as S ∈ C^{2}([a, b]), or S is a C^{2} spline. We showed in class how to count the number of these (continuity) conditions and conclude that there are 4 unknowns in each interval [x_{j}, x_{j+1}], hence a cubic polynomial there and that two additional boundary conditions are required. Do the same for C^{1} splines. Give the degree of the piecewise polynomial and number of additional boundary conditions.

4. In the second table on page 26 of na10 chap03 v01 print.pdf, the new answer 0.5118277 is obtained by adding the new data point (x, y) = (2.5, −0.0483838) and making use of the Q_{i,j} (black numbers) already generated.

(a) Reproduce the blue numbers and hence the new answer.

(b) (optional) Can you do the same for the memory-saving version (ie. without Q) of Neville’s algorithm?