Homework 6

Section 7.1: 1b, 2, 8

Section 7.2: 1a-c, 6, 9

Section 9.1: 3a, 4d

Section 7.3: 1a, 11, 13

Computer Assignment 6
Solution

Computer Assignment 6

Due Thursday, Nov 10 at 11:59pm

Use the following pseudo-code to implement the LU factorization with partial pivoting.

INPUT: An n x n matrix A

OUTPUT: An n x n permutation matrix P, an n x n lower-triangular matrix
L and an n x x upper-triangular matrix U such that PA = LU

STEP 1: Set P = I, L = I
STEP 2: For j = 1,2,.. n-1 do STEPS
  STEP 3: Set MAX to be the maximum of abs(A(i,j)) for i =
  j,j+1,..,n
  STEP 4: If MAX = 0 then
    DISPLAY('Method failed: matrix is rank deficient')
    OUTPUT(A);
    STOP.
  STEP 5: Let p be the smallest number such that MAX = abs(A(p,j));
  STEP 6: Do Rj <--> Rp on A;
  STEP 7: Do Cj <--> Cp on L;
  STEP 8: Do Rj <--> Rp on L;
  STEP 9: Do Rj <--> Rp on P;
  STEP 10: For i = j+1,j+2,...,n do STEPS 11-12
    STEP 11: Set L(i,j) = A(i,j)/A(j,j)
    STEP 12: Do Ri - L(i,j) Rj --> Ri on A
STEP 13: OUTPUT([P,L,U]); STOP.

Demonstrate that your code works by consdering

norm(P*A-L*U)

Explain why this shows that the factorization worked.

Construct a singular matrix and show that the error message is returned.

Solution

function [P,L,A] = LU(A)
    n = length(A);
    P = eye(n);
    L = eye(n);
    % Your code here
end

Homework 6

Contents

Computer Assignment 6

Solution