Question

Show that two matrices in adjacent iterations of the QR eigenvalue algorithm with a single explicit shift, \(A_{k}\) and \(A_{k+1}\), are orthogonally similar.

Short answer

Question: Show that matrices in adjacent iterations of the QR eigenvalue algorithm with a single explicit shift are orthogonally similar. Answer: The matrices in adjacent iterations of the QR eigenvalue algorithm with a single explicit shift, \(A_{k}\) and \(A_{k+1}\), are orthogonally similar since we've shown that there exists an orthogonal matrix \(Q\) such that \(A_{k+1} = Q^{-1} A_{k} Q\). The proof followed the steps of the shifted QR eigenvalue algorithm, leading to the equation \(A_{k+1} = Q^T A_{k} Q\), which verifies orthogonal similarity.

Step-by-step solution

Understanding the QR eigenvalue algorithm with a single explicit shift

The QR eigenvalue algorithm with a single explicit shift is an iterative method for finding the eigenvalues of a matrix. Given a matrix \(A_{0}\), the algorithm works as follows: 1. Choose a shift parameter \(\mu\) (usually chosen as an estimate of an eigenvalue). 2. Compute the shifted matrix \(A_{k}' = A_{k} - \mu I\), where \(I\) is the identity matrix. 3. Perform the QR decomposition of the shifted matrix \(A_{k}'\): \(A_{k}' = QR\), where \(Q\) is an orthogonal matrix and \(R\) is an upper triangular matrix. 4. Compute the next iteration matrix \(A_{k+1} = RQ + \mu I\). Note that the matrices \(A_{k}\) and \(A_{k+1}\) are related through the orthogonal matrix \(Q\).

Multiplying both sides of the equation by \(Q\)

Given the QR decomposition of the shifted matrix \(A_{k}' = A_{k} - \mu I = QR\), we now multiply both sides of this equation by \(Q\): \(A_{k}'Q = QRQ\)

Expressing \(A_{k+1}\) in terms of \(A_{k}'\) and \(Q\)

Recall that \(A_{k+1} = RQ + \mu I\). We can express \(A_{k+1}\) in terms of \(A_{k}'\) and \(Q\) by adding \(\mu I Q\) to both sides of the equation obtained in Step 2: \(A_{k+1} = A_{k}'Q + \mu I Q = (A_{k} - \mu I)Q + \mu I Q\) This simplifies to: \(A_{k+1} = A_{k}Q\)

Proving orthogonally similarity

From Step 3, we know that \(A_{k+1} = A_{k}Q\). Our goal is to show that \(A_{k+1} = Q^{-1} A_{k} Q\). Since \(Q\) is an orthogonal matrix, \(Q^{-1} = Q^T\). Thus, we need to show that \(A_{k+1} = Q^T A_{k} Q\). We can do this by multiplying both sides of the equation \(A_{k+1} = A_{k}Q\) by \(Q^T\): \(A_{k+1}Q^T = A_{k}QQ^T\) Since \(QQ^T = I\) for an orthogonal matrix, we have: \(A_{k+1}Q^T = A_{k}I\) This is equivalent to: \(A_{k+1} = Q^T A_{k}\) Now, we can multiply both sides by \(Q\) again: \(A_{k+1} Q = Q^T A_{k} Q\) Finally, we can rewrite this equation as: \(A_{k+1} = (Q^T)^{-1} A_{k} Q\) Since \((Q^T)^{-1} = Q\), we have: \(A_{k+1} = Q^{-1} A_{k} Q\) This proves that the matrices \(A_{k}\) and \(A_{k+1}\) are orthogonally similar.

Key concepts

Orthogonally Similar Matrices

Matrices are said to be orthogonally similar if one can be transformed into the other through multiplication by an orthogonal matrix and its transpose. In essence, if we have matrices A and B, they are orthogonally similar if there exists an orthogonal matrix Q such that B = Q^T A Q.

Orthogonal matrices have a special property: their transpose is also their inverse, denoted as Q^T = Q^{-1}. This special attribute means that the multiplication of an orthogonal matrix by its transpose results in the identity matrix, QQ^T = I.

In the context of the QR eigenvalue algorithm, orthogonally similar matrices play a critical role in ensuring that the process maintains the spectrum of the original matrix—meaning that the eigenvalues do not change as the iterative process unfolds.

QR Decomposition

The QR decomposition is a cornerstone of linear algebra, particularly important in the realm of eigenvalue algorithms. It is a process by which any matrix A can be decomposed into two matrices—a Q (an orthogonal matrix) and an R (an upper triangular matrix). Mathematically, it can be expressed as A = QR.

This technique is not just pivotal for eigenvalue computation but also holds utility in solving linear systems, optimizing algorithms, and more. During the QR eigenvalue algorithm, the QR decomposition is repeatedly applied after the so-called 'shift'—a scalar value often chosen to accelerate convergence—is subtracted from the matrix.

Eigenvalue Computation

At the heart of the QR eigenvalue algorithm lies the goal of eigenvalue computation. Eigenvalues are significant in understanding the characteristics of a matrix and play a fundamental role in disciplines such as physics, engineering, and computer science. Computationally, finding these values is non-trivial, especially for large matrices.

The QR algorithm, through its iterative nature, helps refine guesses to the actual eigenvalues. With each iteration, the matrix converges closer to a form where its diagonal elements reveal the eigenvalues. It is for this reason that the QR algorithm—aided by strategies like the explicit shift demonstrated in the exercise—remains one of the standard methods for eigenvalue computation.