Assignment 3¶
Submission deadline: 8 March 2019, 14:00
In this assignment we are considering alternative ways to compute orthogonal decompositions of a given matrix $A\in\mathbb{R}^{m\times n}$ with $m\geq n$.
1.) Define the Householder reflector $P = I – \beta vv^T$ for some vector $v\in\mathbb{R}^m$ and $\beta = \frac{2}{v^Tv}$. Show that it is symmetric and orthogonal. Give an explicit expression of the SVD of $P$.
2.) Given a vector $a\in\mathbb{R}^m$. We want to choose $v$ in such a way that $Pa = \pm\|a\|_2e_1$, where $e_1$ is the first unit vector. Find a vector $v$ that satisfies this property. Hint: Write $v = a + \alpha e_1$, $\alpha\in\mathbb{R}$, and see if there exists an $\alpha$ for which this holds true.
3.) Based on the previous question implement a Python function Q, R = householder_qr(A) that for a given matrix $A$ computes its QR decomposition using Householder reflectors. The idea is that you reflect the first column of $A$ onto a multiple of the first unit vector. Then you move on to the remaining submatrix A[1:, 1:] and repeat this procedure. Hint: For numerical stability reasons if the first component of the vector $a$ to be rotated is positive then you should choose $\alpha$ to be positive, and negative otherwise.
4.) Using your Householder QR function write a function x = solve_householder(A, b) that returns a solution of a linear system $Ax = b$ with $A$ square and nonsingular by using the QR decomposition $A=QR$ to write the system as $QRx = b$ and then solve $Rx = Q^Tb$ by backward substitution (use the solve_triangular function from Scipy for the backward substitution).
5.) In the lectures we investigated a matrix with exponentially growing growth factor. Try your solve_householder function with this matrix and compute the backward error of the solutions. Compare the backward error with that of using pivoted LU decomposition (e.g. coming from the Scipy solve routine). What do you observe?
In [ ]: