COMP350 Numerical Computing Assignment #3: Solving linear systems Solved

Description

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

−31 A =  42

1 −3 4 −2

−3 −4 −4 −4

154  1716 88  = 168 

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.

2. (3 points) Suppose we have a complex linear system Ax = b, where A ∈C^n×n 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^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_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