Je bent je ingevulde velden bij deze pagina aan het verwijderen. Ben je zeker dat je dit wilt doen?
You are erasing your filled-in fields on this page. Are you sure that is what you want?
Nieuwe Versie BeschikbaarNew Version Available
Er is een update van deze pagina. Als je update naar de meest recente versie, verlies je mogelijk je huidige antwoorden voor deze pagina. Hoe wil je verdergaan ?
There is an updated version of this page. If you update to the most recent version, then your current progress on this page will be erased. Regardless, your record of completion will remain. How would you like to proceed?
One of the main virtues of orthogonal matrices is that they can be easily inverted—the transpose is the inverse. This fact,
combined with the factorization theorem in this section, provides a useful way to simplify many matrix calculations (for
example, in least squares approximation).
Let \(A\) be an \(m \times n\) matrix with independent columns. A QR-factorization of \(A\) expresses it as \(A = QR\) where \(Q\) is \(m \times n\) with orthonormal columns and \(R\)
is an invertible and upper triangular matrix with positive diagonal entries.
The importance of the factorization lies in the fact that there are computer algorithms that accomplish it with good control over
round-off error, making it particularly useful in matrix calculations. The factorization is a matrix version of the Gram-Schmidt
process.
Suppose \(A = \left [ \begin{array}{cccc} |&|& &| \\ \vec {c}_{1} & \vec {c}_{2} & \cdots & \vec {c}_{n}\\ |&|& &| \end{array}\right ]\) is an \(m \times n\) matrix with linearly independent columns \(\vec {c}_{1}, \vec {c}_{2}, \dots , \vec {c}_{n}\). The Gram-Schmidt algorithm can be applied to these columns to
provide orthogonal columns \(\vec {f}_{1}, \vec {f}_{2}, \dots , \vec {f}_{n}\) where \(\vec {f}_{1} = \vec {c}_{1}\) and
for each \(k = 2, 3, \dots , n\). Now write \(\vec {q}_{k} = \frac {1}{\norm { \vec {f}_{k} }}\vec {f}_{k}\) for each \(k\). Then \(\vec {q}_{1}, \vec {q}_{2}, \dots , \vec {q}_{n}\) are orthonormal columns, and the above
equation becomes
Here the first factor \(Q = \left [ \begin{array}{ccccc} |&|&|& &| \\ \vec {q}_{1} & \vec {q}_{2} & \vec {q}_{3} & \cdots & \vec {q}_{n}\\ |&|&|& &| \end{array}\right ]\) has orthonormal columns, and the second factor is an \(n \times n\) upper triangular matrix \(R\) with positive diagonal
entries (and so is invertible). We record this in the following theorem.
QR-Factorization Every \(m \times n\) matrix \(A\) with linearly independent columns has a QR-factorization \(A = QR\) where \(Q\) has orthonormal columns
and \(R\) is upper triangular with positive diagonal entries.
The matrices \(Q\) and \(R\) in Theorem th:QR-025133 are uniquely determined by \(A\); we return to this below.
Denote the columns of \(A\) as \(\vec {c}_{1}\), \(\vec {c}_{2}\), and \(\vec {c}_{3}\), and observe that \(\{\vec {c}_{1}, \vec {c}_{2}, \vec {c}_{3}\}\) is independent. If we apply the Gram-Schmidt algorithm to these
columns, the result is:
If a matrix \(A\) has independent rows and we apply QR-factorization to \(A^{T}\), the result is:
If \(A\) has independent rows, then \(A\) factors uniquely as \(A = LP\) where \(P\) has orthonormal rows and \(L\) is an invertible lower triangular matrix
with positive main diagonal entries.
Since a square matrix with orthonormal columns is orthogonal, we have
Every square invertible matrix \(A\) has factorizations \(A = QR\) and \(A = LP\) where \(Q\) and \(P\) are orthogonal, \(R\) is upper triangular with positive diagonal
entries, and \(L\) is lower triangular with positive diagonal entries.
We now take the time to prove the uniqueness of the QR-factorization.
Let \(A\) be an \(m \times n\) matrix with independent columns. If \(A = QR\) and \(A = Q_{1}R_{1}\) are QR-factorizations of \(A\), then \(Q_{1} = Q\) and \(R_{1} = R\).
Write \(Q = \left [ \begin{array}{cccc} |&|& &| \\ \vec {c}_{1} & \vec {c}_{2} & \cdots & \vec {c}_{n}\\ |&|& &| \end{array}\right ]\) and \(Q_{1} = \left [ \begin{array}{cccc} |&|& &| \\ \vec {d}_{1} & \vec {d}_{2} & \cdots & \vec {d}_{n}\\ |&|& &| \end{array}\right ]\) in terms of their columns, and observe first that \(Q^TQ = I_{n} = Q_{1}^TQ_{1}\) because \(Q\) and \(Q_{1}\) have orthonormal columns. Hence it suffices to
show that \(Q_{1} = Q\) (then \(R_{1} = Q_{1}^TA = Q^TA = R\)). Since \(Q_{1}^TQ_{1} = I_{n}\), the equation \(QR = Q_{1}R_{1}\) gives \(Q_{1}^TQ = R_{1}R^{-1}\); for convenience we write this matrix as
This matrix is upper triangular with
positive diagonal elements (since this is true for \(R\) and \(R_{1}\)), so \(t_{ii} > 0\) for each \(i\) and \(t_{ij} = 0\) if \(i > j\). On the other hand, the \((i, j)\)-entry of \(Q_{1}^TQ\) is \(\vec {d}_{i}^T\vec {c}_{j} = \vec {d}_{i} \dotp \vec {c}_{j}\), so we have \(\vec {d}_{i} \dotp \vec {c}_{j} = t_{ij}\)
for all \(i\) and \(j\). But each \(\vec {c}_{j}\) is in \(\mbox {span}\{\vec {d}_{1}, \vec {d}_{2}, \dots , \vec {d}_{n}\}\) because \(Q = Q_{1}(R_{1}R^{-1})\). We know how to write a vector as a linear combination of an orthonormal basis (using
Corollary cor:orthonormal from Orthogonality and Projections):
The first of these
equations gives \(1 = \norm { \vec {c}_{1} } = \norm { t_{11}\vec {d}_{1} } = | t_{11} | \norm { \vec {d}_{1} } = t_{11}\), whence \(\vec {c}_{1} = \vec {d}_{1}\). But then we have \(t_{12} = \vec {d}_{1} \dotp \vec {c}_{2} = \vec {c}_{1} \dotp \vec {c}_{2} = 0\), so the second equation becomes \(\vec {c}_{2} = t_{22}\vec {d}_{2}\). Now a similar argument gives \(\vec {c}_{2} = \vec {d}_{2}\),
and then \(t_{13} = 0\) and \(t_{23} = 0\) follows in the same way. Hence \(\vec {c}_{3} = t_{33}\vec {d}_{3}\) and \(\vec {c}_{3} = \vec {d}_{3}\). Continue in this way to get \(\vec {c}_{i} = \vec {d}_{i}\) for all \(i\). This proves that \(Q_{1} = Q\).
QR-Algorithm for approximating eigenvalues
In The Power Method and the Dominant Eigenvalue, we learned about an iterative method for computing eigenvalues. We
also mentioned that a better method for approximating the eigenvalues of an invertible matrix \(A\) depends on the
QR-factorization of \(A\). While it is beyond the scope of this book to pursue a detailed discussion of this method, we give an
example and conclude with some remarks on the QR-algorithm. The interested reader is referred to J. M. Wilkinson, The
Algebraic Eigenvalue Problem (Oxford, England: Oxford University Press, 1965) or G. W. Stewart, Introduction to Matrix
Computations (New York: Academic Press, 1973).
The QR-algorithm uses QR-factorization repeatedly to create a sequence of matrices \(A_{1} =A, A_{2}, A_{3}, \dots ,\) as follows:
Let \(A\) be an invertible matrix.
Step 1: Define \(A_{1} = A\) and factor it as \(A_{1} = Q_{1}R_{1}\).
Step 2: Define \(A_{2} = R_{1}Q_{1}\) and factor it as \(A_{2} = Q_{2}R_{2}\).
Step 3: Define \(A_{3} = R_{2}Q_{2}\) and factor it as \(A_{3} = Q_{3}R_{3}\).
Note that \(A_{k + 1}\) is similar to \(A_{k}\) (in fact, \(A_{k+1} = R_{k}Q_{k} = (Q_{k}^{-1}A_{k})Q_{k}\)), and hence each \(A_{k}\) has the same eigenvalues as \(A\). If the eigenvalues of \(A\) are real and have
distinct absolute values, the sequence of matrices \(A_{1}, A_{2}, A_{3}, \dots \) converges to an upper triangular matrix with these eigenvalues on the
main diagonal. We will discuss the complex case eigenvalue case below.
If \(A = \left [ \begin{array}{rr} 1 & 1 \\ 2 & 0 \end{array}\right ]\) as in Example ?? of The Power Method and the Dominant Eigenvalue, use the QR-algorithm to approximate the
eigenvalues.
The matrices \(A_{1}\), \(A_{2}\), and \(A_{3}\) are as follows:
This is converging to \(\left [ \begin{array}{rr} 2 & \ast \\ 0 & -1 \end{array}\right ]\) and so is approximating the eigenvalues \(2\) and \(-1\) on the main diagonal.
Shifting.
We first learned about the concept of shifting in The Power Method and the Dominant Eigenvalue. Convergence is
accelerated if, at stage \(k\) of the algorithm, a number \(\tau _{k}\) is chosen and \(A_{k} - \tau _{k}I\) is factored in the form \(Q_{k}R_{k}\) rather than \(A_{k}\) itself. Then
is said to be in upper Hessenberg form, and the QR-factorizations of such matrices are greatly simplified.
Given an \(n \times n\) matrix \(A\), a series of orthogonal matrices \(H_{1}, H_{2}, \dots , H_{m}\) (called Householder matrices can be easily constructed such that
\begin{equation*} B = H_{m}^T \cdots H_{1}^TAH_{1} \cdots H_{m} \end{equation*}
is in
upper Hessenberg form. Then the QR-algorithm can be efficiently applied to \(B\) and, because \(B\) is similar to \(A\), it produces the
eigenvalues of \(A\).
Complex Eigenvalues.
If some of the eigenvalues of a real matrix \(A\) are not real, the QR-algorithm converges to a block upper triangular matrix where
the diagonal blocks are either \(1 \times 1\) (the real eigenvalues) or \(2 \times 2\) (each providing a pair of conjugate complex eigenvalues of
\(A\)).
If \(R\) is upper triangular and invertible, show that there exists a diagonal matrix \(D\) with diagonal entries \(\pm 1\) such that \(R_{1} = DR\) is invertible,
upper triangular, and has positive diagonal entries.
If \(A\) has independent columns, let \(A = QR\) where \(Q\) has orthonormal columns and \(R\) is invertible and upper triangular. (Some authors do not require a \(QR\)-factorization to have
positive diagonal entries.) Show that there is a diagonal matrix \(D\) with diagonal entries \(\pm 1\) such that \(A = (QD)(DR)\) is the QR-factorization of \(A\).
See Practice Problem
In each case, find the exact eigenvalues and then approximate them using the QR-algorithm.
If \(A\) is symmetric, show that each matrix \(A_{k}\) in the QR-algorithm is also symmetric. Deduce that they converge to a diagonal
matrix.
Click the arrow to see answer.
Use induction on \(k\). If \(k = 1\), \(A_{1} = A\). In general \(A_{k+1} = Q_{k}^{-1}A_{k}Q_{k} = Q_{k}^{T}A_{k}Q_{k}\), so the fact that \(A_{k}^{T} = A_{k}\) implies \(A_{k+1}^{T} = A_{k+1}\). The eigenvalues of \(A\) are all real
(Theorem ??), so the \(A_{k}\) converge to an upper triangular matrix \(T\). But \(T\) must also be symmetric (it is the limit of symmetric
matrices), so it is diagonal.
Apply the QR-algorithm to \(A = \left [ \begin{array}{rr} 2 & -3 \\ 1 & -2 \end{array}\right ]\). Explain.
Given a matrix \(A\), let \(A_{k}\), \(Q_{k}\), and \(R_{k}\), \(k \geq 1\), be the matrices constructed in the QR-algorithm. Show that \(A_{k} = (Q_{1}Q_{2} \cdots Q_{k})(R_{k} \cdots R_{2}R_{1})\) for each \(k \geq 1\) and hence that this is a
QR-factorization of \(A_{k}\).
Show that \(Q_{k}R_{k} = R_{k-1}Q_{k-1}\) for each \(k \geq 2\), and use this equality to compute \((Q_{1}Q_{2} \cdots Q_{k})(R_{k} \cdots R_{2}R_{1})\) “from the centre out.” Use the fact that \((AB)^{n+1} = A(BA)^{n}B\) for any
square matrices \(A\) and \(B\).
