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

Homework Assignment for Week 11

Assigned Nov 25, 2011.

1. Section 7.3: Problems 9(a,c), 10(a,c), 14.

2. Reading instruction for section 7.3:

Read and understand meanings of Jacobi, Gauss-Siedel and SOR methods. SKIP the following: Theorem 7.22, Definition 7.23 through eq. (7.16) (read your class note for derivation of SOR instead), Theorem 7.24, 7.25, 7.26.

3. Let A be the matrix resulted from discretizing

(∂_{x}^{2} + ∂_{y}^{2})u(x, y) = f(x, y), (x, y) ∈ (0, 1)^{2} u = 0, on the boundary of (0, 1)^{2}

(1)

with uniformly spaced grids 0 = x_{0} < x_{1} < ⋯ < x_{N} = 1, 0 = y_{0} < y_{1} < ⋯ < y_{N} = 1, x_{i} − x_{i−1} = y_{j} − y_{j−1} = h = 1/N, using second order centered finite difference method. Study your class note and try to derive the matrix A by yourself.

(a) Recall that LU decomposition for this A requires N^{4} multiplications from previous homework problems. Estimate the number of multiplications (to leading order, also for rest of this problem) for solving Lz = b and Ux = z respectively.

(b) Estimate numbers of multiplications needed for one iteration of Jacobi, Gauss Seidel and SOR on this A, respectively.

(c) 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 needed for Jacobi and Gauss-Siedel, respectively. You will need that log(1 + x) ≈ x for |x| << 1.

(d) It is another fact (the proof is also beyond this course) that with properly chosen 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 the optimal SOR takes to reach ∥e^{(k)}∥ = h^{2} with ∥e^{(0)}∥ = 1.

(e) 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 version of (1), with different constants C_{i}. Repeat the above problems for the 3D case. The purpose of this problem is to show you that, beating Gauss Elimination/LU decomposition with iterative methods is possible, but sometimes non-trivial.

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

5. Continuation on problem 4 of Homework 10, which requires handing in your code, is postponed till after the midterm.