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

Brief Answers to Quiz 05

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

1. Use any desingularization method to evaluate the improper integral ∫_{0}^{1} \frac{e^{x}}{\sqrt{x}} dx with a

composite quadrature rule of 4th order accuracy. The answer is 2.9 · · ·. Demonstrate numerically that the result is indeed 4th order accurate.

Ans:

∫_{0}^{1} \frac{e^{x}}{\sqrt{x}} dx ≈ 2.92530349181436 (25 pts)

Method 1:

See page 252-253 of the textbook.

Method 2:

See page 7 of NA20f 201204 Supplements to improper integrals.pdf

2. Use trapezoidal rule to discretize the integral equation

u + ∫_{0}^{1} exp(−|x − t|) u(t) dt = f

on uniformly spaced nodes 0 = x_{0} < x_{1} < ⋯ < x_{10} = 1, x_{j} − x_{j−1} = \frac{1}{10}, to get a linear system of the form Cu = f. Construct the matrix C and evaluate ∑_{i,j} c_{ij}.

Ans:

a = 0, b = 1, m = 10, h = (b − a)/m,

In matlab or C, let w(j) = \{ \begin{matrix}\frac{h}{2}, & j = 1, m + 1 ( or j = 0, m) \\ h, & 2 ≤ j ≤ m. ( or 1 ≤ j ≤ m − 1.) \end{matrix}

Then c_{ij} = exp(−|i − j|h) ∗ w(j) + δ_{ij}. (15 pts)

∑_{ij}c_{ij} ≈ 18.98582400029024 (10 pts)

3. Let A be an M × M matrix with a_{ij} = 0 except for −2 ≤ i − j ≤ 2. Suppose that Ax = b can be solved using Gaussian elimination without pivoting. Find the leading order operation count (multiplication/division only) kM^{p} for the elimination part (ignore the backward substitution part). Give all details.

Ans:

There are 2M (to leading order) sub-diagonal elements to be eliminated. Each requires 4 multiplications/divisions (1 for calculating the ratio, 1 for each of the 2 super-diagonal elements, and 1 for the right hand side).

Total = 8M multiplications/divisions. (25 pts)

4. Let B be an N^{2} × N^{2} matrix with b_{ij} = 0 except for i − j = 0, ±1 and ±N. Suppose that Bx = c can be solved using Gaussian elimination without pivoting. Find the leading order operation count (multiplication/division only) kN^{p} for the elimination part (ignore the backward substitution part). Give all details.

Ans:

The zeros between i−j = −N and i−j = −1 and between i−j = 1 and i−j = N are filled (become nonzero) after 2N steps of Gaussian elimination. The operation count is the same order as if b_{ij} = 0 except for |i − j| ≤ N. (10 pts)

In this case, there are N^{2}×N (to leading order) sub-diagonal elements to be eliminated. Each requires N (to leading order) multiplications/divisions (1 for calculating the ratio, 1 for each of the N super-diagonal elements, and 1 for the right hand side).

Total = N^{4} multiplications/divisions. (15 pts)