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.

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 [ ]:

```
```

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 [ ]:

```
```

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

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

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 [ ]:

```
```