[Solved] COMP350 Numerical Computing Assignment #3: Solving linear systems

1. (a) (3 points) Solve the following system using GEPP (Gaussian elimination with partial pivoting):

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 dont consider any rounding errors.

2. (3 points) Suppose we have a complex linear system Ax = b, where A Cⁿⁿ is nonsingular and b Cⁿ. Can you solve it in real arithmetic operations? What is the cost?

Hint: Rewrite Ax = b as an equivalent 2n 2n real linear system.

3. Suppose A Rⁿⁿ is nonsingular.
   • (4 points) Given B R^np, 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_tk_F/kX_tk_F and kAk_FkA¹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_compk_F/(kAk_FkX_compk_F).

1. 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:
2. Do you see any rough relation between kX_c X_tk_F/kX_tk_F and kAk_FkA¹k_F? iii. Do you see any rough relation between kB AX_ck_F/(kAk_FkX_ck_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¹).

Compute the inverse of a 5 5 Hilbert matrix defined in 3(b). Print out your MATLAB code and the result.

1. (3 bonus points) For the sake of simplicity, suppose we use the LU factorizationwith no pivoting to compute A¹. Briefly state an algorithm which costs 2n³ You need to explain why its cost is 2n³ flops.

2