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

Quiz 05

Dec 23, 2014.

1. Let A be an N^{2} × N^{2} matrix with a_{ij} = 0 except for −N ≤ i − j ≤ 2N (only 3N + 1 diagonals have nonzero entries). Suppose that Ax = b can be solved using Gaussian elimination without pivoting. Find the leading order operation count (multiplication/division only) CN^{p} for the elimination and backward substitution, respectively.

2. True or False? Give details.

Let A be an n × n nonsingular matrix. If the linear system Ax = b can be solved using Gaussian elimination without pivoting, then A = LU where L is a lower triangular matrix with diagonal entries equal to 1 and U is an upper triangular matrix with nonzero diagonal entries.

3. Write a pseudo code for LU decomposition where L, U are as described above.

4. Find P, L, U in the factorization P A = LU for the matrix

A = ( \begin{matrix}0 & 0 & −1 & 1 \\ 1 & 1 & −1 & 2 \\ −1 & −1 & 2 & 0 \\ 1 & 2 & 0 & 2 \end{matrix} )  (1)

where P is a permutation matrix and L, U are as described above.

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

Quiz 05

Dec 23, 2014.

1. Let A be an N^{2} × N^{2} matrix with a_{ij} = 0 except for −N ≤ i − j ≤ 2N (only 3N + 1 diagonals have nonzero entries). Suppose that Ax = b can be solved using Gaussian elimination without pivoting. Find the leading order operation count (multiplication/division only) CN^{p} for the elimination and backward substitution, respectively.

2. True or False? Give details.

Let A be an n × n nonsingular matrix. If the linear system Ax = b can be solved using Gaussian elimination without pivoting, then A = LU where L is a lower triangular matrix with diagonal entries equal to 1 and U is an upper triangular matrix with nonzero diagonal entries.

3. Write a pseudo code for LU decomposition where L, U are as described above.

4. Find P, L, U in the factorization P A = LU for the matrix

A = ( \begin{matrix}0 & 0 & −1 & 1 \\ 1 & 1 & −1 & 2 \\ −1 & −1 & 2 & 0 \\ 1 & 2 & 0 & 2 \end{matrix} )  (2)

where P is a permutation matrix and L, U are as described above.