| course |
course_year |
question_number |
tags |
title |
year |
Numerical Analysis |
IB |
54 |
IB |
2021 |
Numerical Analysis |
|
Paper 2, Section II, 17B |
2021 |
(a) Define Householder reflections and show that a real Householder reflection is symmetric and orthogonal. Moreover, show that if $H, A \in \mathbb{R}^{n \times n}$, where $H$ is a Householder reflection and $A$ is a full matrix, then the computational cost (number of arithmetic operations) of computing $H A H^{-1}$ can be $\mathcal{O}\left(n^{2}\right)$ operations, as opposed to $\mathcal{O}\left(n^{3}\right)$ for standard matrix products.
(b) Show that for any $A \in \mathbb{R}^{n \times n}$ there exists an orthogonal matrix $Q \in \mathbb{R}^{n \times n}$ such that
$$Q A Q^{T}=T=\left[\begin{array}{ccccc}
t_{1,1} & t_{1,2} & t_{1,3} & \cdots & t_{1, n} \\
t_{2,1} & t_{2,2} & t_{2,3} & \cdots & t_{2, n} \\
0 & t_{3,2} & t_{3,3} & \cdots & t_{3, n} \\
\vdots & \ddots & \ddots & \ddots & \vdots \\
0 & \cdots & 0 & t_{n, n-1} & t_{n, n}
\end{array}\right]$$
In particular, $T$ has zero entries below the first subdiagonal. Show that one can compute such a $T$ and $Q$ (they may not be unique) using $\mathcal{O}\left(n^{3}\right)$ arithmetic operations.
[Hint: Multiply A from the left and right with Householder reflections.]