QR Decomposition

QR DECOMPOSITION

1. The modified Gram−Schmidt process

The Gram−Schmidt orthogonalization process yields inaccurate results due to round−off error under finite digit arithmetic. A modification of that algorithm exists which is more stable and it generates the same vectors in the absence of rounding. This modification also transforms a set of linearly independent vectors { X₁, X₂, X₃ ... X_n} into a set of orthonormal vectors { Q₁, Q₂, Q₃ ... Q_n} such that each vector Q_k(k = 1, 2, 3 ... n) is a linear combination of X₁ through X_k−1. The modified algorithm is iterative, with the k^th iteration given by the following steps.

Step 1: Set r_kk = ||X_k||₂ and Q_k = (1/r_kk) X_k.

Step 2: For j=k+1, k+2, k+ 3, ... n, set r_kj= <X_j, Q_k>.

Step 3: For j=k+1, k+2, k+3, ... n, replace X_j by X_j−r_kjQ_k.

2. QR−Decomposition

Every m×n matrix A (m≥n) can be factored into the product of a matrix Q having orthonormal vectors for its columns, and an upper right triangular matrix R.

The product A = QR is the QR decomposition of A.

                        ………….(1)

If A is square, then Q is unitary. The QR decomposition follows immediately from the modified Gram−Schmidt process applied to the columns A, provided those columns are linearly independent. If they are, then the columns of Q and the elements r_ij(i≤j) of R are the quantities generated by the modified Gram−Schmidt process.

If the columns of A are not linearly independent, then one or more of the r_kk values determined in step 1 will be zero. That step must be modified to

Step 1: Calculate r_kk=||X_k||₂. If r_kk ≠ 0, then Q_k = X_k/r_kk. If r_kk=0, then choose Q_k to be any normalized vector which is orthogonal to Q₁, Q₂, ... Q_k−1.

In practice, r_kk is rarely zero. Even if the columns of A are linearly dependent, round−off will produce an г_kk value close to but not equal to zero, permitting Q_k to be calculated in the usual manner. The result is an incorrect vector. Thus, whenever an r_kk value is sufficiently small, Q_k must be checked to guarantee it is orthogonal to the previously calculated Q vectors. If it is not, the modification given as step 1' must be implemented.

3. The QR Algorithm

The QR algorithm is a procedure for determining all eigenvalues of a real matrix A₀. The algorithm sequentially constructs matrices A_k(k=1, 2, 3 ...) by forming QR decompositions.

 A_k−1 = Q_k−1 R_k−1

                   ……………(2)

for A_k−1, and then reversing the order of the product to define

  A_k = R_k−1Q_k−1

                  ……….. (2)

Each A_k is similar to its predecessor and has the same eigenvectors. In general, the sequence {A_k} converges to a partitioned matrix having either of two forms.

                …………….. (5)

If form (4) occurs, then the element G is an eigenvalue and the remaining eigenvalues are obtained by applying the QR algorithm to the matrix E. If form (5) arises, then two eigenvalues can be determined from the characteristic equation of the 2×2 submatrix in the lower right partition and the remaining eigenvalues are obtained by applying the QR algorithm to the matrix G. If E or G is already a 2×2 matrix, its eigenvalues are determined from its characteristic equation.

4. Accelerating convergence

Convergence of the QR algorithm is accelerated by a shift at each iteration. If the matrices have order n×n, then the element in the (n, n) position of A_k‒1 is denoted as S_k−1, and a QR decomposition is constructed for the shifted matrix A_k−1−S_k−1I. Equation (2) is modified to

    A_k−1 − S_k−1I = Q_k−1R_k−1

                 …………..(6)

and equation (3) is replaced with

 A_k = R_k−1Q_k−1 + S_k−1I

                ……..... (7)

Equations (6) and (7) constitute the shifted QR algorithm.