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

Homework Assignment for Week 16

1. Section 7.4: Problems 7(c), 13.

2. Read Theorem 7.11 for evaluation of ∥A∥_{∞}.

3. Let A be the (m + 1) × (m + 1) matrix from Homework 13, Problem 4 (with K(x, t) = −\frac{1}{2}e^{−|x−t|}). Show that ∥T_{j}∥_{∞} ≈ 1 − \frac{1}{\sqrt{e}} for large m and therefore Jacobi iteration converges. Then estimate the total number of operations (multiplication/division, to leading order) for Jacobi iteration to reach ∥e^{(k)}∥_{∞} = h^{2} (assuming ∥e^{(0)}∥_{∞} = 1) where h = (b − a)/m = \frac{1}{m} and e^{(k)} = u^{(k)} − u_{e}. Compare the operation count with that of the Gaussian Elimination/LU decomposition approach.

4. Let A be the matrix from Problem 4, Homework 15.

(a) Give the operation count to leading order (on multiplication/division) for one iteration of Jacobi, Gauss Seidel and SOR on this A, respectively.

(b) It is a fact (the proof is beyond this course) that for this A, ρ(T_{j}) ≈ 1 − \frac{π^{2}}{2} h^{2}, ρ(T_{g}) ≈ 1 − π^{2}h^{2} ≈ ρ(T_{j})^{2}. Note that both numbers are very close to 1. Take this fact for granted, estimate the number of iterations Jacobi and Gauss-Siedel take to reach ∥e^{(k)}∥ = h^{2}, respectively (assuming ∥e^{(0)}∥ = 1) where e^{(k)} = u^{(k)} − u_{e}. Then estimate the total number of multiplications/divisions needed for Jacobi and Gauss-Siedel, respectively. You will need that log(1 + x) ≈ x for |x| << 1.

(c) It is another fact (the proof is also beyond this course) that with the optimal ω = ω^{∗} ≈ 2 − 2πh, we will have ρ(T_{ω^{∗}}) ≈ 1 − 2πh for SOR (for this A). Take this fact for granted again, estimate the number of iterations and total multiplications/divisions the optimal SOR takes to reach ∥e^{(k)}∥ = h^{2} with ∥e^{(0)}∥ = 1.

(d) The facts that ρ(T_{j}) ≈ 1 − C_{1}h^{2}, ρ(T_{g}) ≈ 1 − C_{2}h^{2} and ρ(T_{ω^{∗}}) ≈ 1 − C_{3}h remain valid in the 3D case, with different constants C_{i}. Repeat the above problems for the 3D case. Compare these results (operation count) with that of the Gaussian Elimination/LU decomposition approach.

5. Derive the Jacobi version of SOR. Express T_{ω,j} in terms of T_{j}.

6. Section 7.5: Problems 1(a,c), 3(a,c), 11, 12(a).

7. Section 7.5: The Hilbert matrices are well known ill-conditioned matrices.

In addition to the example provided in problem 9, you can use the matlab built-in command ’hilb’ and ’cond’ to find the condition numbers of the Hilbert matrices H^{(n)} in problem 9 directly (i.e. without finding (H^{(n)})^{−1} first). Do this for n = 6, ⋯, 12 and observe how fast the condition number grows with n.