A Householder QR decomposition introduces zeros below successive diagonal entries using orthogonal reflections. For a nonzero real column segment , set when and otherwise, and defineThen and . The sign choice avoids subtracting nearly equal numbers when constructing . If the segment is zero, skip the reflection.
For with , apply the first reflection to all rows, the second to rows , and so on, extending each by an identity on the earlier rows. This giveswhere is orthogonal and consists of an upper triangular matrix above zero rows. The reflections are stored through their defining vectors, so a full dense need not be formed.[ref]
Fundamentals of Numerical Computation by Tobin A. Driscoll and others. Section 3.4, Householder reflections and successive triangularization
For full column rank, the top block of is invertible and back substitution solves the transformed least squares problem. Orthogonal transformations preserve the Euclidean norm, making this route useful when the normal equations would square a large condition number.
For full column rank , a full QR factorization gives with invertible upper triangular . The equation is consistent exactly when the final entries of vanish. If consistent, back substitution gives its unique solution. This separates consistency from uniqueness in overdetermined systems.
Articles by others on the same topic
There are currently no matching articles.