Description
- (a) (3 points) Solve the following system using GEPP (Gaussian elimination with partial pivoting):
ï£®âˆ’31
A = ï£¯ï£¯ï£° 4_{2} |
1
âˆ’3 4 âˆ’2 |
âˆ’3
âˆ’4 âˆ’4 âˆ’4 |
15_{4 }ï£¹ ï£®17_{16}ï£¹
8_{8 }ï£ºï£ºï£» ^{= }ï£¯ï£¯ï£°_{16}^{8 }ï£ºï£ºï£» |
Show intermediate matrices, vectors and multipliers at each step.
(b) (2 points) Compute the LU factorization of the matrix in the previous question with partial pivoting: PA = LU. You have to show intermediate results at each step. This question and the previous one can be answered together.
Note: Do the computations by your hands and donâ€™t consider any rounding errors.
- (3 points) Suppose we have a complex linear system Ax = b, where A âˆˆC^{n}^{Ã—n }is nonsingular and b âˆˆC^{n}. Can you solve it in real arithmetic operations? What is the cost?
Hint: Rewrite Ax = b as an equivalent 2n Ã— 2n real linear system.
- Suppose A âˆˆR^{n}^{Ã—n }is nonsingular.
- (4 points) Given B âˆˆR^{n}^{Ã—p}, show how to use the LU factorization with partial pivoting to solve AX = B. What is the cost of your method?
Hint: AX = B is equivalent to AX(:,j) = B(:,j) for j = 1 : p.
- (5 points) Use m given in the lecture notes to solve AX = B, where 10 Ã— 10 Hilbert matrix A = (a_{ij}), a_{ij }= 1/(i + j âˆ’ 1);
10 Ã— 5 B = A âˆ—randn(10,5).
Here randn is a MATLAB built-in function to generate a random matrix. Denote this randn(10,5) by X_{t }and your computed solution by X_{c}.
- Compute kX_{c }âˆ’ X_{t}k_{F}/kX_{t}k_{F }and Ç«kAk_{F}kA^{âˆ’1}k_{F}, where Ç« is the machine epsilon. Check MTALAB built-in functions or constants norm, cond and eps, to see how to compute or get related quantities.
- Compute the relative residual kB âˆ’ AX_{comp}k_{F}/(kAk_{F}kX_{comp}k_{F}).
- Run your code 10 times (you may use a loop). Notice each time you have differentB, since X_{true }is random. Answer the following questions:
- Do you see any rough relation between kX_{c }âˆ’ X_{t}k_{F}/kX_{t}k_{F }and Ç«kAk_{F}kA^{âˆ’1}k_{F}? iii. Do you see any rough relation between kB âˆ’ AX_{c}k_{F}/(kAk_{F}kX_{c}k_{F}) and Ç« ?
Print out your MATLAB code and the results.
1
(c) Computing A^{âˆ’1}
- (3 points) Show how to use the LU factorization with partial pivoting to computethe inverse of a general n Ã— n nonsingular matrix A. What is the cost of your method? (Hint: Think about what matrix equation AX = B you should solve to get A^{âˆ’1}).
Compute the inverse of a 5 Ã— 5 Hilbert matrix defined in 3(b). Print out your MATLAB code and the result.
- (3 bonus points) For the sake of simplicity, suppose we use the LU factorizationwith no pivoting to compute A^{âˆ’1}. Briefly state an algorithm which costs 2n^{3 } You need to explain why its cost is 2n^{3 }flops.
2