Householder transformation and QR decomposition A Householder transformation of a vector is its reflection with respect a plane (or hyperplane) through the origin represented by its normal vector of unit length, which can be found as where is the projection of onto. In general, the projection of onto any vector is. Householder Transformation Householder Transformation (also 'Householder Reflection') is an orthogonal reflection transformation: it reflex the vectors in the columns of the matrix such that the first vector has all zeros except the first element. Recall the strategy used in deriving method for QR decomposition using Householder reflections. C) For the matrix A = 0.00001. eye (n) + hilb (n), where eye (n) returns an identity matrix and hilb (n) return a hilbert matrix of size n. 1) Apply QR decomposition for the above matrix using Gram-Schmidt, Householder reflections and method in b). Chosen by editors at Computing in Science and Engineering as one of the 10 most in uential algorithms of the 20th century Used for nding eigenvalues and eigenvectors of a matrix One of the algorithms implemented by LAPACK Eric Mikida The QR Algorithm for Finding Eigenvectors.

• Qr Householder Method Examples
• Qr Householder Method Template
• Householder Qr Decomposition

Next:The Schur Decomposition and Up:ch1 Previous:Householder transformation

QR Decomposition

Qr Householder Method Examples

The QR decomposition (or factorization)is an algorithm that converts a given matrix into a product of an orthogonal matrix and a rightor upper triangular matrix with . In the following we consider two methods for the QR decomposition.

• The Householder transformation:

  We first construct a Householder matrix based on the first column vector of , by which will be converted into a vector with its last elements equal to zero:
  

  We then construct second transformation matrix
  

  (47)

  
  
  where is an dimensional Householder matrix to eliminate the last elements of the first column of :
  This process is repeated with the general kth transformation matrix
  

  (49)

  
  
  where is an dimensional Householder matrix to eliminate the last elements of the first column of the sub-matrix of the same dimension obtained from the previous steps. After such iterations becomes an upper triangular matrix:
  Define and pre-multiply it on both sides we get the QR decomposition of :
  

  (51)

  
  
  where defined aobve is an orthogonal matrix:
  
  

  To find the complexity of this algorithm, we note that the Householder transformation of a column vector is , which is needed for all columns of a submatrix in each of the iterations. Therefore the total complexity is . However, if is a Hessenberg matrix (or more specially a tridiagonal matrix), then the Householder transformation of each column vector is constant (for the only subdiagonal component), and the complexity becomes .

  Note that this method cannot convert into a diagonal matrix, by performing Householder transformations on the rows (from the right) as well as on the columns (from the left), similar to the tridiagonalization of a symmetric matrix previously considered. This is because while post-multiplying a Householder matrix to convert a row, the column already converted by pre-multiplying a Householder matrix will be changed again.

• The Gram-Schmidt process:

  The QR decomposition of can also be obtained by converting the column vectors in , assumed to be independent, into a set of orthonormal vectors , which form the columns of the orthogonal matrix .

  We first find as the normalized version of the first column of , and then find each of the remaining orthogonal vector (), with all previous already normalized:
  

  (53)

  
  
  followed by normalization so that . Now can be represented as a linear combination of vectors as:
  We define and , and rewrite the above as
  

  (55)

  
  
  where is the ith column of , and are yet to be generated (but they are multiplied by zero and play no role here). Combining the equations above in matrix form, we get
  where is orthogonal and is upper triangular.

  The complexity for computing and is , and the total complexity of this algorithm is .

The QR decomposition finds many applications, such as solving a linear system :

(57)

where can be obtained as:
and then can be obtained by solving with an upper triangular coefficient matrix by back-substitution.

More importantly, the QR decomposition is the essential part of the QR algorithm for solving the eigenvalue problem of a general matrix, to be considered in the following section.

The Matlab code listed below carries out the QR decomposition by both the Householder transformation and the Gram-Schmidt method:

Qr Householder Method Template

Next:The Schur Decomposition and Up:ch1 Previous:

Householder Qr Decomposition

Householder transformationRuye Wang2018-08-20