MATH3076/3976 Assignment 2: UL and LQ Decompositions

Please complete the following assignment in Jupyter, and email the completed file renamed to LAST_NAME SID.ipynb to [email protected] by midnight on 12 May 2016.

You are strongly encouraged to work out the problems on your own. If you use existing solutions, existing code, help online or collaborate with other students, you will still receive full credit provided that you make this clear and cite your sources. If you collaborate with other students, please submit individual solutions and be specific in giving credit for what each student contributed.

This lab explores two alternative decompositions to the LU and QR decompositions: the UL Decomposition and LQ decompositions.

UL Decomposition

An LU decomposition is constructed by multiplying by a lower triangular matrix that introduces zeros column-by-column starting with the first column.

Instead, we will investigate the UL decomposition: we will introduce zeros column-by-column starting with the last column.

Exercise 1(a) Given an $n \times n$ matrix A, what upper triangular matrix U_j introduces zeros in the $j$th column:

(U_j*A)[1:j-1,j] == zeros(1:j-1)?

Complete the following function that takes in a square Matrix A and an integer j and returns an upper triangular Matrix U_j that satisfies the above property.

In [ ]:
# INPUT:  A square matrix A and integer j
# OUTPUT: A matrix U_j that is upper triangular

function upper_reduce_col(A,j)
    # TODO: Create and return U_j
end

Exercise 1(b) Check that

n=100
A=rand(n,n)
U_n=upper_reduce_col(A,n)
norm((U_n*A)[1:n-1,n])

is small.

In [ ]:

Exercise 1(c) Complete the following function that returns a UL Decomposition.

In [ ]:
# INPUT:  A square matrix A
# OUTPUT: A tuple (U,L) where U is upper triangular and L is lower triangular

function ul(A)
    # TODO: Create and return U and L so that U*L is A
end

Exercise 1(d) Show that your ul decomposition works by calculating the maximum and average value of norm(A-U*L), for n=20 and 1000 randm choices of A.

In [ ]:

Badly conditioned PLU matrix

Recall from lectures the matrix that breaks the PLU Decomposition

$$A_n \triangleq \begin{pmatrix} 1 & && & 1 \cr -1 & 1 && & 1\cr -1 & -1 & 1 && 1 \cr \vdots & \vdots & \vdots & \ddots & \vdots \cr -1 & -1 & -1 & \cdots & 1 \end{pmatrix}$$

Exercise 2(a) Write a routine bad_plu_mat(n) that takes in an integer n and returns an n x n Matrix $A_n$ as defined above. Use a different approach to construct the matrix than what was done in lectures.

In [ ]:
# INPUT:  An Integer n
# OUTPUT: A Matrix A_n that is n x n

# TODO: write bad_plu_mat(n)

Exercise 2(b) Plot the condition numbers ${\rm cond}(L)*{\rm cond}(U)$ for $A_n = P L U$ as a function of n, for n=1:100, using semilogy.

In [ ]:

Exercise 2(c) Plot the condition numbers ${\rm cond}(U)*{\rm cond}(L)$ for $A_n = UL$ as a function of n, for n=1:100, using semilogy. What do you conclude about the stability of the UL decomposition for this example?

In [ ]:

LQ Decomposition

This part investigates the calculation of $A=LQ$, which is an alternative to $A=QR$.

Exercise 3(a) Write a function house(x,j) that takes in a Vector x and returns an orthogonal Matrix $Q$ so that

$$x^\top Q = [x_1,\ldots,x_{j-1},-{\rm sign}\, x_j \|x_{j:end}\|,0,\ldots,0]$$
In [ ]:
# INPUT:  A Vector x and Integer j
# OUTPUT: A Matrix Q that is m x m and orthogonal

# TODO: Write house(x,j)

Exercise 3(b) Check numerically that

$$\|x^\top Q - [x_1,\ldots,x_{j-1},-{\rm sign}\, x_j \|x_{j:end}\|,0,\ldots,0]\|$$

is small for a random vector of length 100 and j=3.

In [ ]:

Exercise 3(c) Use part 3(a) to write a function lq(A) that calculates the RQ Decomposition: it takes in a n x m Matrix A and returns a tuple of matrices L and Q so that L is n x m and lower triangular, Q is m x m and orthogonal, and L*Q is (up to rounding error) equal to A.

In [ ]:
# INPUT:  An n x m matrix A
# OUTPUT: A tuple (L,Q)  where L is n x m lower triangular and Q is m x m and orthogonal

# TODO: Write lq(A)

Exercise 3(d) Demonstrate numerically that your lq routine satisfies $\|A-LQ\|$ is small for random matrices for the cases $n > m$, $n=m$ and $n < m$.

In [ ]:

In [ ]:

In [ ]: