Question

Let \(A\) be a general nonsymmetric nonsingular square matrix, and consider the following two alternatives. The first is applying GMRES to solve the linear system \(A \mathbf{x}=\mathbf{b} ;\) the second is applying CG to the normal equations $$ A^{T} A \mathbf{x}=A^{T} \mathbf{b} $$ We briefly discussed this in Section \(7.5\); the method we mentioned in that context was CGLS. (a) Suppose your matrix \(A\) is nearly orthogonal. Which of the two solvers is expected to converge faster? (b) Suppose your matrix is block diagonal relative to \(2 \times 2\) blocks, where the \(j\) th block is given by $$ \left(\begin{array}{cc} 1 & j-1 \\ 0 & 1 \end{array}\right) $$ with \(j=1, \ldots, n / 2\). Which of the two solvers is expected to converge faster? [Hint: Consider the eigenvalues and the singular values of the matrices.]

Short answer

a) It is difficult to determine which solver, GMRES or CGNE, is expected to converge faster when the matrix A is nearly orthogonal, as both methods are expected to converge fast based on the distribution of eigenvalues and singular values. b) When the matrix A is block-diagonal relative to \(2\times2\) blocks, the GMRES solver is expected to converge faster than the CGNE solver.

Step-by-step solution

Understand the convergence rate of GMRES

The convergence rate of GMRES is determined by the distribution of singular values of the matrix A. If A is nearly orthogonal, this means that its singular values are close to 1, and GMRES is expected to converge fast.

Understand the convergence rate of CGNE

CGNE is applied on the normal equations \(A^TA\mathbf{x}=A^T\mathbf{b}\), so the convergence of CGNE depends on the distribution of the eigenvalues of the matrix \(A^TA\). If matrix A is nearly orthogonal, the eigenvalues of \(A^TA\) are also close to 1. Therefore, CGNE is expected to converge fast.

Compare the convergence rates

Since both GMRES and CGNE are expected to converge fast for a nearly orthogonal matrix A, it is difficult to determine which one will converge faster solely based on the distribution of eigenvalues and singular values. Therefore, we cannot make a definitive conclusion about which solver is expected to converge faster when A is nearly orthogonal. #b) Block Diagonal Matrix#

Compute the eigenvalues of A and \(A^TA\).

For a block diagonal matrix, where the j-th block is given by $$ \left(\begin{array}{cc} 1 & j-1 \\\ 0 & 1 \end{array}\right), $$ with \(j=1,\ldots,n/2\), we can compute the eigenvalues for both A and \(A^TA\). The eigenvalues of the j-th block of A are 1 (repeated twice), and thus the eigenvalues of A are 1 (repeated \(n\) times). The eigenvalues of the j-th block of \(A^TA\) will be \(1+j^2-2j\) and \(1\), and thus the eigenvalues of \(A^TA\) will span a larger range than the eigenvalues of A.

Understand the convergence rate of GMRES

The convergence rate of GMRES is determined by the distribution of the singular values of the matrix A. In this case, the matrix A has repeated eigenvalues equal to 1, which makes its singular values close to 1. Therefore, GMRES is expected to converge fast.

Understand the convergence rate of CGNE

The convergence rate of CGNE is determined by the distribution of eigenvalues of the matrix \(A^TA\). In this case, the eigenvalues of \(A^TA\) span a larger range than the eigenvalues of A. This implies that the convergence rate of CGNE will be slower than that of GMRES.

Compare the convergence rates

Based on the eigenvalues of A and \(A^TA\), we can conclude that the GMRES solver is expected to converge faster than the CGNE solver when the matrix A is block-diagonal relative to \(2\times2\) blocks. The final answers are: a) We cannot make a definite conclusion about which solver is expected to converge faster when A is nearly orthogonal. b) The GMRES solver is expected to converge faster than the CGNE solver when A is block-diagonal relative to \(2\times2\) blocks.

Key concepts

Generalized Minimal Residual Method (GMRES)

The Generalized Minimal Residual Method, known as GMRES, is an iterative method used to solve non-symmetric linear systems of the form \(A\mathbf{x}=\mathbf{b}\). It's particularly useful when dealing with nonsymmetric and possibly ill-conditioned matrices.

GMRES works by constructing a Krylov subspace that approximates the solution. It minimizes the residual over this subspace in a least squares sense. One of the primary considerations affecting the convergence of GMRES is the distribution of the singular values of the matrix \(A\).

In the case of a nearly orthogonal matrix—where singular values are close to 1—the residuals diminish rapidly, leading to faster convergence. The advantage of GMRES lies in its ability to handle a wide spectrum of problems. However, it is worth noting that it may require preconditioning for optimal performance and its memory usage can be substantial since it stores vectors of increasing Krylov subspaces.

Conjugate Gradient Method for Normal Equations (CGNE)

The Conjugate Gradient on Normal Equations (CGNE) is an adaptation of the Conjugate Gradient (CG) method which finds the solution to the normal equations \(A^TA\mathbf{x}=A^T\mathbf{b}\). Unlike GMRES, CGNE is well-suited to symmetric positive definite matrices which are derived from the original coefficient matrix \(A\).

The convergence of CGNE is intrinsically linked to the eigenvalue distribution of \(A^TA\). In scenarios where \(A\) is nearly orthogonal, implying that \(A^TA\) will have eigenvalues close to 1, CGNE is also expected to converge quickly. Nevertheless, it can be less effective if the eigenvalues are widely spread, which leads to a slower convergence rate. It's particularly important to assess the condition number—the ratio of the largest to the smallest singular value—when predicting the convergence rate of CGNE.

Eigenvalues and Singular Values of Matrices

The eigenvalues and singular values of a matrix play a central role in determining the efficiency of iterative methods like GMRES and CGNE. Eigenvalues are scalar values that, when multiplied by their corresponding eigenvectors, yield the same product as when the eigenvectors are multiplied by the matrix. Singular values, by contrast, are the square roots of the non-negative eigenvalues of \(A^TA\), for a given matrix \(A\).

Eigenvalues give insights about the stability and dynamics of systems modeled by matrices. Singular values provide information on how a matrix stretches or compresses vectors and can also inform about the condition number of the matrix. For symmetric or nearly orthogonal matrices, where eigenvalues are tightly clustered, iterative methods like GMRES are often efficient. However, when dealing with matrices that have a broad spectrum of eigenvalues, such as in the block diagonal case mentioned in the exercise, divergence of eigenvalues can result in a slower convergence for methods that rely on eigenvalue distributions, like CGNE.

In summary, understanding the eigenvalue and singular value structure of a matrix provides valuable foresight into which iterative method may offer faster and more reliable convergence — a key point when addressing the convergence rate of iterative solvers.