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

Homework Assignment for Week 13

1. Section 4.9: Problem 1(a).

For this problem, follow the analysis we showed in class to predict the actual order of convergence for standard 2nd order (midpoint, trapezoidal) and 4th order (Simpson’s rule, Gaussian quadrature with 2 or 3 quadrature points) composite quadratures.

Then use any desingularization method of your choice and verify numerically that the result indeed has 2nd, 4th or higher order convergence.

Remark: Simple change of variable x = t^{−p} does not perform well (not enough to restore theoretical order of convergence) for Problem 3 (c,d) due to the oscillatory nature of the integrands. A more subtle subtraction of singular part is required to desingularize the integrand and recover theoretical order of convergence. You are encouraged (although not required) to explore possible desingularization method for problem 3 (c,d).

2. Section 4.9: Problems 4(b).

Remark: Without splitting the domain into ∫_{0}^{1} + ∫_{1}^{∞}, the change of variable t = \frac{1}{x+1} will do the trick and is recommended whenever the integrand has no singularity at x = 0^{+}.

3. Section 6.1: Problems 12 (a,b).

For part (b), change it to K(x, t) = −\frac{1}{2}e^{−|x−t|} and implement Algorithm 6.1 to solve for u. For this problem with the new K, the linear system can be solved accurately without pivoting (row interchanging).

4. Consider an N^{2} × N^{2} matrix A with a_{ij} = 0 except for i − j = 0, ±1, ±2 (only five diagonals have nonzero entries). Estimate total number of multiplication needed for Gaussian elimination without pivoting on A and backward substitution, respectively. Give the leading order of the number of multiplication as KN^{p} for N large. Find both K and p.

5. Do the same for an N^{2} × N^{2} matrix B with b_{ij} = 0 except for |i − j| ≤ N (only 2N + 1 diagonals have nonzero entries).

6. Do the same for an N^{2} × N^{2} matrix C with c_{ij} = 0 except for i − j = 0, ±1 and ±N (only 5 separated diagonals have nonzero entries).