Householder Reflections

Householder reflections and QR decomposition

householder(A)

Arguments

A

numeric matrix with nrow(A)>=ncol(A).

Details

The Householder method applies a succession of elementary unitary matrices to the left of matrix A. These matrices are the so-called Householder reflections.

Value

List with two matrices Q and R, Q orthonormal and R upper triangular, such that A=Q%*%R.

References

Trefethen, L. N., and D. Bau III. (1997). Numerical Linear Algebra. SIAM, Society for Industrial and Applied Mathematics, Philadelphia.

See also

givens

Examples

##  QR decomposition
A <- matrix(c(0,-4,2, 6,-3,-2, 8,1,-1), 3, 3, byrow=TRUE)
S <- householder(A)
(Q <- S$Q); (R <- S$R)
#>      [,1]  [,2]  [,3]
#> [1,]  0.0 -0.80 -0.60
#> [2,] -0.6 -0.48  0.64
#> [3,] -0.8  0.36 -0.48
#>      [,1]         [,2] [,3]
#> [1,]  -10 1.000000e+00    2
#> [2,]    0 5.000000e+00   -1
#> [3,]    0 4.440892e-16   -2
Q %*% R  # = A
#>      [,1] [,2] [,3]
#> [1,]    0   -4    2
#> [2,]    6   -3   -2
#> [3,]    8    1   -1

##  Solve an overdetermined linear system of equations
A <- matrix(c(1:8,7,4,2,3,4,2,2), ncol=3, byrow=TRUE)
S <- householder(A); Q <- S$Q; R <- S$R
m <- nrow(A); n <- ncol(A)
b <- rep(6, 5)

x <- numeric(n)
b <- t(Q) %*% b
x[n] <- b[n] / R[n, n]
for (k in (n-1):1)
    x[k] <- (b[k] - R[k, (k+1):n] %*% x[(k+1):n]) / R[k, k]
qr.solve(A, rep(6, 5)); x
#> [1]  1.074236 -2.331878  2.436681
#> [1]  1.074236 -2.331878  2.436681