IAM 961 HW3: QR decomp

Due Monday Nov 21, 2016.

Problem 1.

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]:
qrhouse (generic function with 1 method)

Problem 2.

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

Problem 3.

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]:
backsub (generic function with 1 method)

Problem 4.

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]:
randommatrix (generic function with 1 method)

Problem 5.

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

Problem 6

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

Problem 7

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