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

Quiz 04

Nov 25, 2011.

1. Prove that if A is non-singular, then the decomposition A = LU with l_{ii} = 1, if it exists, is unique.

2. What is Cholesky decomposition? When does a matrix admit Cholesky decomposition? (Need not prove your statement).

3. Write a pseudo-code of Cholesky decomposition for a matrix that satisfies the requirement from problem 2 and is also a tridiagonal matrix. Give the number of multiplications/divisions to leading order (assuming that a square root amounts to 10 multiplications). Give your answer as CN^{p}, find C and p.

4. Let A be an 20 × 20 tridiagonal matrix with a_{ii} = 5.1, a_{i+1,i} = a_{i,i+1} = 2 and a_{ij} = 0 otherwise. Show that Gaussian elimination on A is the same as Gaussian elimination with partial pivoting.

5. Let b = (1, ⋯, 1)′ and A as above. Use the octave built-in function to get LU decomposition for A. Find z = U^{−1}b via forward/backward (you have to decide which) substitution. Then compute max(abs(U ∗ z − b)). Copy your code (carefully) and max(abs(U ∗ z − b)) on the answer sheet.

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

Quiz 04

Nov 25, 2011.

1. Prove that if A is non-singular, then the decomposition A = LU with l_{ii} = 1, if it exists, is unique.

2. What is Cholesky decomposition? When does a matrix admit Cholesky decomposition? (Need not prove your statement).

3. Write a pseudo-code of Cholesky decomposition for a matrix that satisfies the requirement from problem 2 and is also a tridiagonal matrix. Give the number of multiplications/divisions to leading order (assuming that a square root amounts to 10 multiplications). Give your answer as CN^{p}, find C and p.

4. Let A be an 20 × 20 tridiagonal matrix with a_{ii} = 5.1, a_{i+1,i} = a_{i,i+1} = 2 and a_{ij} = 0 otherwise. Show that Gaussian elimination on A is the same as Gaussian elimination with partial pivoting.

5. Let b = (1, ⋯, 1)′ and A as above. Use the octave built-in function to get LU decomposition for A. Find z = U^{−1}b via forward/backward (you have to decide which) substitution. Then compute max(abs(U ∗ z − b)). Copy your code (carefully) and max(abs(L ∗ z − b)) on the answer sheet.