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

Brief Answers to Quiz 04

1:20-2:10PM, Dec 01, 2020.

1. Find the rate of convergence (the p in Ch^{p}) of cubic spline interpolation numerically for the function f(x) = x^{1.5} on [0, 1] using the steps outlined in problem 2, homework 09. The function is not smooth, so do not doubt yourself if the answer is not as good as you expected.

Ans:

Let f_{h}(x) be the approximation of f using cubic spline with x_{j} − x_{j−1} = h.

If max_{x} |f(x) − f_{h}(x)| ≈ Ch^{p}, then p ≈ log_{2} (\frac{max_{x} |f(x) − f_{2h}(x)|}{max_{x} |f(x) − f_{h}(x)|}).

Numerical result shows that p = 1.5. (25 pts)

2. It is known that lim_{h→0^{+}}(1 + h)^{\frac{1}{h}} = exp(1) (you need to find the rate of convergence yourself). We denote by N_{1}(h) = (1 + h)^{\frac{1}{h}}. Use Richardson extrapolation to derive the formula for N_{2}(h). Put in all details from the beginning, then write down

|\frac{exp(1) − N_{2}(0.02)}{exp(1) − N_{2}(0.01)}|.

Ans:

Use the a similar procedure as in problem 1, we find numerically that

exp(1) = N_{1}(h) + C_{1}h + ⋯ (5pts)

Therefore

exp(1) = N_{1}(2h) + 2C_{1}h + ⋯

or

exp(1) = N_{1}(\frac{h}{2}) + C_{1} \frac{h}{2} + ⋯

Use either N_{1}(h) and N_{1}(2h) or N_{1}(h) and N_{1}(\frac{h}{2}) to get

N_{2}(h) = 2N_{1}(h) − N_{1}(2h), or N_{2}(h) = 2N_{1}(\frac{h}{2}) − N_{1}(h) (15pts)

Answer: |\frac{exp(1) − N_{2}(0.02)}{exp(1) − N_{2}(0.01)}| = 3.89 or 3.94. Either one will do. (5 pts)

3. Let f′′_{h}(x) be the numerical approximation of f′′(x) obtained from f(x − h), f(x) and f(x + h). Write down f′′_{h}(x) and its error estimate (need not derive if you are sure about it). Find min_{h>0} e(h) = min_{h>0} |f′′_{h}(x) − f′′(x)|. Express the critical value h^{∗} and the minimum e(h^{∗}) in terms of machine ε as O(ε^{α}) and find α’s for them.

Ans:

f′′_{h}(x) = \frac{1}{h^{2}} (f(x − h) − 2f(x) + f(x + h)) (5 pts)

f′′_{h}(x) − f′′(x) = \frac{h^{2}}{12}f^{(4)}(ξ) (5 pts)

The round-off error + truncation error is bounded by

|fl(f′′_{h}(x)) − f′′(x)| ≤ |fl(f′′_{h}(x)) − f′′_{h}(x)| + |f′′_{h}(x) − f′′(x)| ≤ \frac{4ε}{h^{2}} + \frac{h^{2}}{12}M

where M is an upper bound of |f^{(4)}|. (5 pts) Thus, the optimal h^{∗} = O(ε^{1/4}) (5 pts) and e(h^{∗}) = O(ε^{1/2}) (5 pts).

4. Use any one of the composite quadrature methods to evaluate ∫_{0}^{1} x^{1.5}dx and find the rate of convergence numerically. Again, the function is not smooth, so do not doubt yourself if the answer is not as good as you expected. Ans: Find p as in problem 1. Midpoint rule or Trapezoidal rule: p = 2. Simpson’s rule: p = 2.5. (25 pts)