Due Monday Nov 21, 2016.

Write the following Julia functions for computing the QR decomposition of a matrix

`qrcgs(A)`

via Classical Gram-Schmidt orthogonalization,`qrmgs(A)`

via Modified Gram-Schmidt orthogonalization, and`qrhouse(A)`

via Householder triangularization.

Each function should return the two matrices Q and R.

In [110]:

```
function qrcgs(A)
# fill in
end
function qrmgs(A)
# fill in
end
function qrhouse(A)
# fill in
end
```

Out[110]:

Test that your QR algorithms work correctly on a fairly small and well-conditioned matrix (e.g. a 5 x 5 matrix with normally distributed elements, `A = randn(5,5)`

). You should test that $Q$ is unitary and that $QR \approx A$. Verify to your own satisfaction that $R$ is upper-triangular. Make these tests as compact and readable as you can!

In [ ]:

```
```

Write a `backsub(R,b)`

function that computes a solution of $Rx=b$ by backsubstitution. You can assume that $R$ is square and nonsingular. Test your backsubstitution function by solving an $Ax=b$ problem with your 5 x 5 $A$ matrix, one of your QR algorithms, and a known solution $x$.

In [111]:

```
function backsub(R, b)
# fill in
end
```

Out[111]:

Write a function `A = randommatrix(m,n kappa)`

function that returns an m x n
random matrix with condition number kappa and exponentially graded singular values
(i.e. $\sigma_1/\sigma_m = \kappa$ and $\sigma_{j+1}/\sigma_{j} = \text{const}$).
You can use the Matlab code at the top of pg 65 in Trefethen and Bau as a starting
point. Test that it works by constructing a 4 x 4 matrix with kappa=10^8 and then
computing its condition number.

In [45]:

```
function randommatrix(m,n, kappa)
# fill in
end
```

Out[45]:

Solve a large number of random $Ax=b$ problems using your QR decompositions
and `randommatrix`

and `backsubstitution`

functions, and produce a scatter
plot of the normalized solution error $\|\hat{x}-x\|/\|x\|$ versus $\kappa$.
Plot data points from CGS in blue, MGS in red, and Householder in green.

Specifically: Construct a random $A$ matrix with $\kappa = 10^n$ where $n$ is
a random real-valued number uniformly distributed between 0 and 16.
Select a random $x$ vector with `x = randn(m,1)`

, and then set $b = Ax$. For each of
the CGS, MGS, and Householder QR algorithms, compute the numerical solution $\hat{x}$
of $Ax=b$ via QR and then plot $\|\hat{x}-x\|/\|x\|$ versus $\kappa$ using log-log axes
and the color scheme specified above. Do this for one hundred random $Ax=b$ problems and
for a fairly small value of $m$ (perhaps 10 or 20).

In [ ]:

```
```

Comment on your results. What can you explain about the scatter plots based on the algorithms and their implementation in finite-precision arithmetic? Or, contrariwise, what can you say about the algorithms based on the scatter plots?

In [ ]:

```
```

If you are curious, repeat problem 5 for a different value of $m$ (perhaps $m=100$). Does the dimensionality of the matrix (the value of $m$) make any difference?

In [ ]:

```
```