HW3: QR decomposition

Math 753/853 HW3: QR decomposition
Before you begin!
First rename this file "math753-hw3-mylastname" using your last name in the indicated spot. With the file extension, the full filename should be "math753-hw3-mylastname.ipynb". No capital letters, please.

To submit the homework email it to john.gibson@unh.edu with the subject "MATH 753 HW3" by midnight, Sunday Oct 15, 2017.

Writing explanations in your solutions. Many of the problems ask for explanations of answers and calculations. For these you should write one to several complete sentences that explain the reasoning behind your work in a manner that would be helpful to a fellow student.

Problem 1
Write a qrcgs function that computes the QR decomposition of a square matrix A using the Classical Gram-Schmidt algorithm (CGS).

The function should take a matrix A as input and return matrices Q,R.

Test your QR decomposition on a random 5 x 5 matrix. Check that Q is orthogonal, that R is upper-triangular, and that A = QR.


Problem 2
Write a backsubstitution function that solves the system  Rx=b^  for square upper-triangular  R .

The function should take a matrix  R  and a vector  b^  as inputs and return a vector  x .
Test your backsubstitution function using the 5 x 5 upper-triangular  R  from your QR decomp test, a random vector  x , computing  b^=Rx , and then applying the backsubstitution function to compute the numerical solution  x^  and checking that  x^≈x .

Problem 3
Write a solve function that solves an  Ax=b  system for  x , given square matrix  A  and vector  b , using your qrcgs and backsubstitution functions.

The function should take  A  and  b  as inputs and return a vector  x .
Test your solve function on a random 5 x 5  A , a random vector  x , and a  b  vector computed from  b=Ax .

Problem 4
Test your solve function on a random 100 x 100  Ax=b  problem and comment on the results. Is the numerical solution accurate to the degree you expect from the Conditioning and Accuracy Theorem?

m = 100
A = randn(m,m)
x = randn(m)
b = A*x;
Problem 5
Test your solve function on the following 5 x 5  Ax=b  problem and comment on the results. Is the numerical solution accurate to the degree you expect from the Conditioning and Accuracy Theorem?

m = 5
(U,tmp) = qr(randn(m,m))
(V,tmp) = qr(randn(m,m))
Σ = Diagonal([1, 1e-4, 1e-8, 1e-10, 1e-12])
A = U*Σ*V'
x = U[:,1]
b = A*x;
Problem 6
What went wrong on problem 5? See how much you can narrow down the source of the problem by examining the QR decomposition produced by your qrcgs function for the  A  matrix of problem 5.