Back to the on-screen lesson ·
Why an orthogonal factor leaves lengths and conditioning alone, how a reflector clears a column, and why this route keeps twice the digits the normal equations do.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to build a Householder reflector, solve a least-squares problem by QR and read its residual off the factorisation, compare the digits kept against the normal equations, and say what distinguishes the three ways of orthogonalising in floating point.
You know that a least-squares approximation is a projection, that the normal equations compute it, and that forming $A^{\mathsf{T}}A$ squares the condition number. This lesson is the factorisation that computes the same projection without ever forming that product.
A matrix is orthogonal when $Q^{\mathsf{T}}Q = I$, so it preserves lengths. A QR factorisation writes $A = QR$ with $Q$ orthogonal and $R$ upper triangular. A Householder reflector is $H = I - \dfrac{2vv^{\mathsf{T}}}{v^{\mathsf{T}}v}$, which reflects across the plane perpendicular to $v$. A matrix is rank deficient when its columns are dependent.
The whole method rests on one property: an orthogonal $Q$ preserves lengths, so $\|b - Ax\| = \|Q^{\mathsf{T}}b - Q^{\mathsf{T}}Ax\|$. Factorise $A = QR$; then $Q^{\mathsf{T}}A = R$ is upper triangular with zeros below row $n$, so only the first $n$ entries of $Q^{\mathsf{T}}b$ can be touched by $x$. Setting those to zero — by back substitution on $Rx = (Q^{\mathsf{T}}b)_{1:n}$ — minimises the residual, and the norm of the remaining entries is the residual norm, free. Because $\kappa_2(Q^{\mathsf{T}}A) = \kappa_2(A)$, the conditioning of the problem has not been touched, and a Householder QR solution of a small-residual problem has forward error about $\kappa_2(A)\varepsilon$ — against $\kappa_2(A)^{2}\varepsilon$ for the normal equations, which is twice the digits lost, for about twice the work. How the factorisation is computed then matters in its own right. Classical Gram-Schmidt loses orthogonality like $\kappa(A)^{2}$; modified Gram-Schmidt, the same algebra in a different order, like $\kappa(A)$; Householder reflectors are orthogonal to working precision whatever $\kappa(A)$ is. Three routes to one mathematical object, three different answers in arithmetic.
Another way: steps
Another way: picture
A reflector is a mirror. Choose the mirror plane so that $x$'s image lies along the first axis: the reflection preserves the length of $x$ and moves all of it into one component, which is what putting zeros below a diagonal entry means. A QR factorisation is $n$ such mirrors applied in turn, each clearing one more column, and $Q$ is the product of the mirrors — never formed explicitly in practice, because only its action on a vector is ever needed.
Gram-Schmidt is treated as the way to compute a QR factorisation because it is the way it is taught. In exact arithmetic it is fine; in floating point the classical version produces a $Q$ whose columns are visibly not orthogonal by the time $\kappa(A)$ reaches $10^{8}$, and the least-squares solution built from it is correspondingly wrong. The fix is not more care but a different construction: reflectors are orthogonal because a reflection is, not because the arithmetic was accurate.
$x = (3, 4)$, $\|x\| = 5$, $v = (8, 4)$, $v^{\mathsf{T}}v = 80$.
The mirror's normal.
$H = \begin{pmatrix} -3/5 & -4/5 \\ -4/5 & 3/5 \end{pmatrix}$, and $Hx = (-5, 0)$.
Length preserved, one component left.
$\kappa_2(A) = 10^{7}$ in double precision.
A perfectly ordinary fitting problem.
QR: about nine correct digits. Normal equations: $\kappa_2(A^{\mathsf{T}}A) = 10^{14}$, so about two.
The same data, two methods.
$\|b - Ax\| = \|Q^{\mathsf{T}}(b - Ax)\|$, because $Q$ is orthogonal.
$= \|Q^{\mathsf{T}}b - Rx\|$, since $Q^{\mathsf{T}}A = R$.
So minimising the original is minimising this, and $R$ being triangular makes it a back substitution — the whole method in three lines.
A least-squares problem with $\kappa_2(A) = 10^{4}$ is solved in double precision by a Householder QR factorisation, with a small residual. About how many correct digits should the coefficients have?
Answer:
Build the Householder reflector $H = I - \dfrac{2vv^{\mathsf{T}}}{v^{\mathsf{T}}v}$ with $v = x + \|x\|e_1$ for $x = (7, 24)$, whose length is $25$. Give the entries of $H$.
This task has no paper form; do it on a device.
In double precision, give the correct digits expected from a QR solution and from the normal equations, for least-squares problems with $\kappa_2(A) = 10^{3}$, $10^{4}$ and $10^{5}$.
| Digits from QR | Digits from the normal equations | |
|---|---|---|
| $\kappa_2(A) = 10^{3}$ | ||
| $\kappa_2(A) = 10^{4}$ | ||
| $\kappa_2(A) = 10^{5}$ |
Match each way of producing a QR factorisation to what it does in floating-point arithmetic.
| Loses orthogonality at a rate like $\kappa(A)^{2}$ | Loses it at a rate like $\kappa(A)$: same algebra, better arithmetic | Orthogonal to a rounding error whatever the conditioning | The same, one entry at a time: better for a sparse matrix | |
|---|---|---|---|---|
| Classical Gram-Schmidt | ||||
| Modified Gram-Schmidt | ||||
| Householder reflections | ||||
| Givens rotations |
A least-squares problem has $12$ columns but the matrix has rank only $11$. What is the dimension of the set of vectors $x$ minimising $\|b - Ax\|$?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Put the five steps of solving a least-squares problem by QR into order.
Number the steps in order (write the number in the box):
You can build a reflector and solve a least-squares problem by QR, and say what it costs and saves. Say in your own words why an orthogonal transformation may be applied to the problem for free.
8. Your turn: what $Q^{\mathsf{T}}$ does to the residual, step 3