course |
course_year |
question_number |
tags |
title |
year |
Numerical Analysis |
IB |
64 |
IB |
2006 |
Numerical Analysis |
|
3.II.19D |
2006 |
(a) Define the QR factorization of a rectangular matrix and explain how it can be used to solve the least squares problem of finding an $x^{*} \in \mathbb{R}^{n}$ such that
$$\left|A x^{*}-b\right|=\min _{x \in \mathbb{R}^{n}}|A x-b|, \quad \text { where } \quad A \in \mathbb{R}^{m \times n}, \quad b \in \mathbb{R}^{m}, \quad m \geqslant n,$$
and the norm is the Euclidean distance $|y|=\sqrt{\sum_{i=1}^{m}\left|y_{i}\right|^{2}}$.
(b) Define a Householder transformation (reflection) $H$ and prove that $H$ is an orthogonal matrix.
(c) Using Householder reflection, solve the least squares problem for the case
$$A=\left[\begin{array}{rr}
2 & 4 \\
1 & -1 \\
2 & 1
\end{array}\right], \quad b=\left[\begin{array}{l}
1 \\
5 \\
1
\end{array}\right]$$
and find the value of $\left|A x^{*}-b\right|=\min _{x \in \mathbb{R}^{2}}|A x-b|$.