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

Homework Assignment for Week 09

1. Section 3.5:

The cubic spline with not-a-knot end condition gives rise to a linear system Ax = b where A is an (n + 1) × (n + 1) matrix and x = (c_{0}, c_{1}, ⋯, c_{n})^{T}. Eliminating c_{0} and c_{n} results in a new equivalent linear system Ãx̃ = b̃ where x̃ = (c_{1}, ⋯, c_{n−1})^{T} and Ã can be made symmetric. Carry out the details for the case h_{0} = ⋯ = h_{n} = h and show that Ã is symmetric and positive definite (hence the original A is non-singular). Hint: Under not-a-knot end condition, S′′(x) is a linear function on [x_{0}, x_{2}] and on [x_{n−2}, x_{n}] (why?). This leads to an linear equation relating c_{0}, c_{1} and c_{2}, and one relating c_{n−2}, c_{n−1} and c_{n}.

2. Section 3.5:

Find the rate of convergence (as Ch^{p}, where h = x_{j} −x_{j−1}) of cubic spline interpolation numerically with default (not-a-knot) and clamped boundary conditions by evaluating roughly 10 points on each interval [x_{j−1}, x_{j}]. For example, let (x_{j}, y_{j}), j = 0, ⋯, n be data points where x_{j} = a + jh, h = (b − a)/n and y_{j} = f(x_{j}). Denote by x_{k}^{∗} = a + kh^{∗}, h^{∗} = h/10, k = 0, ⋯, 10n the points to be interpolated. Take a = 1, b = 5, f(x) = 1/x, n = 16, 32, ⋯ and evaluate max_{k} |f(x_{k}) − S(x_{k})| to find the order of accuracy p numerically. Optional: Do the same for natural cubic spline. Key words: csape (advanced version of spline in MATLAB), ’variational’.

3. Section 4.1: Problems 24, 26, 28, 29.

Definition: The linear combination ∑_{i=−k}^{k} c_{i}f(x_{0} + ih) is a pth order approximation of f^{(q)}(x_{0}) if

∑_{i=−k}^{k} c_{i}f(x_{0} + ih) = f^{(q)}(x_{0}) + O(h^{p})

4. Section 4.1:

Apply the round-off error instability calculation (end of section 4.1) to second order approximation of f′′(x_{0}). Find the critical h^{∗} that minimizes e(h). Express both h^{∗} and e(h^{∗}) in terms of the machine ε as O(ε^{p}) and find p for both h^{∗} and e(h^{∗}).

5. Section 4.1: Repeat previous problem for fourth order approximation of f′(x_{0}).

6. Section 4.1, 4.2:

Derive the five-point formula for f′′′(x_{0}) and and f^{(4)}(x_{0}), respectively using f(x_{0}), f(x_{0} ± h) and f(x_{0} ± 2h). You can either use the method of undetermined coefficients (combined with Taylor expansion around x_{0}), or repeat the three-point formula for f′(x_{0}) and/or f′′(x_{0}) and the identities f′′′ = (f′)′′ = (f′′)′ and f′′′′ = (f′′)′′ to get the five-point formulae for f′′′(x_{0}) and and f^{(4)}(x_{0}).