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

Midterm 02

Dec 02, 2011, 13:10-16:30.

As before, estimate to leading order means CN^{p}, find C and p. Unless otherwise specified, L in LU means l_{ii} = 1.

1. (a) Write a pseudo-code for Gauss elimination (without pivoting) and estimate number

of multiplication/division needed to leading order for a dense N × N matrix A.

(b) Consider an N^{2} × N^{2} matrix B with B_{ij} = 0 except for i − j = 0, 1, ±N (only 4 diagonals have nonzero entries). Estimate total number of multiplication needed for Gaussian elimination (elimination part only) on B to leading order. Explain.

(c) Consider an N^{2} ×N^{2} matrix C with c_{ij} = 0 except for i−j = 0, ±N (only 3 diagonals have nonzero entries). Estimate total number of multiplication needed for Gaussian elimination (elimination part only) on C to leading order. Explain.

2. Which of the following matrices admit LU decomposition (that is, no ’P ’ needed)? Then find L and U (use paper and pencil) for those matrices. Explain.

A = ( \begin{matrix}0 & 2 & −1 \\ 1 & 0 & 3 \\ 2 & 1 & 1 \end{matrix} ) , B = ( \begin{matrix}1 & 2 & −1 \\ 2 & 4 & 0 \\ 0 & 1 & −1 \end{matrix} ) , C = ( \begin{matrix}2 & −1 & 1 \\ 3 & 3 & 9 \\ 3 & 3 & 5 \end{matrix} )

3. True or false? Prove or disprove.

Denote by A_{k} the k × k the leading principles of an N × N real matrix A. If det A_{k} ≠ 0, k = 1, ⋯, N. Then A admits an LU decomposition.

4. Let A be a symmetric positive definite N × N matrix. Suppose that Gaussian elimination on A does not require pivoting. Prove that A admits Choleski decomposition. Suppose further that a_{ij} = 0 except for i − j = 0, ±1, ±2. Write a pseudo-code for it and find the number of multiplications/divisions needed to leading order, assuming square root amounts to 10 multiplications

5. Let A = be a sparse matrix and A = D−L−U with D diagonal, L strictly lower triangular and U strictly upper triangular (l_{ii} = 0 = u_{ii}).

(a) Write down the Jacobi, Gauss-Siedel and SOR iteration for solving Ax = b, respectively.

(b) Suppose T_{j} is diagonalizable and ρ(T_{j}), the largest absolute value of eigenvalues of T_{j}, = 0.94, and initial error ∥x^{(0)} − x∥ = 1. Find the number of Jacobi iteration it takes to reach ∥x^{(k)} − x∥ ≤ 10^{−4}.

(c) Suppose that, for some sparse matrix B, ρ(T_{j}) is diagonalizable with real eigenvalues 2 ≤ λ(T_{j}) ≤ 3. Propose a convergent (and fastest, if possible) iterative method for solving By = c. Explain.

6. Suppose it is known that a nonsingular \underline{tridiagonal} matrix B admits the decomposition B = ŨL̃ where L̃ is lower triangular and Ũ upper diagonal with ũ_{ii} = 1. Show that such a decomposition is unique and write a pseudo-code for it. Then apply it to the 10 × 10 matrix B with b_{ii} = 6.1, b_{i+1,i} = 1 = b_{i,i+1} and b_{ij} = 0 otherwise. Copy your code and

report ∑_{i=1}^{10}abs(l̃_{ii}). If you can’t do it, do the LU case with partial credits.