= Solution
Multiply $Ax=b$ by $Q^T$ to get the equivalent triangular system
$$
Rx=Q^Tb.
$$
For nonsingular $A$, compute $c=Q^Tb$ and use <back substitution>:
$$
x_i=\frac{c_i-\sum_{j=i+1}^nR_{ij}x_j}{R_{ii}},\qquad i=n,n-1,\ldots,1.
$$
Orthogonal transformations preserve the <Euclidean norm>, making this a numerically stable reduction. The factors can be applied as stored <Householder transformation>[Householder transformations] without explicitly forming $Q$.
Since $Q$ is invertible, $A$ is singular exactly when $R$ is singular. For an <upper triangular matrix>,
$$
\det R=\prod_{i=1}^nR_{ii}.
$$
Thus \b[a singular $A$ forces at least one zero diagonal entry in $R$]. In that case, ordinary division-based <back substitution> must be replaced by a consistency/rank analysis: the system may have no solution or infinitely many solutions, and a rank-revealing factorization can identify the free parameters.
Back to article page
