COMP350 Numerical Computing Assignment #3: Solving linear systems Solved

30.00 $

Category:
Click Category Button to View Your Next Assignment | Homework

You'll get a download link with a: . zip solution files instantly, after Payment

Description

5/5 - (1 vote)
  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.

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

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

  1. Suppose A ∈Rn×n is nonsingular.
    • (4 points) Given B ∈Rn×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 = (aij), aij = 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 Xt and your computed solution by Xc.

  • Compute kXc XtkF/kXtkF and ǫkAkFkA−1kF, 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 AXcompkF/(kAkFkXcompkF).
  1. Run your code 10 times (you may use a loop). Notice each time you have differentB, since Xtrue is random. Answer the following questions:
  2. Do you see any rough relation between kXc XtkF/kXtkF and ǫkAkFkA−1kF? iii. Do you see any rough relation between kB AXckF/(kAkFkXckF) and ǫ ?

Print out your MATLAB code and the results.

1

(c) Computing A−1

  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.

  1. (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 2n3 You need to explain why its cost is 2n3 flops.

2

  • a3-3.zip