Question

(a) Write a program for solving the linear least squares problems that arise throughout the iterations of the GMRES method, using Givens rotations, where the matrix is a nonsquare \((k+1) \times k\) upper Hessenberg matrix. Specifically, solve $$ \min _{\mathbf{z}}\left\|\rho e_{1}-H_{k+1, k} \mathbf{z}\right\| $$ Provide a detailed explanation of how this is done in your program, and state what \(Q\) and \(R\) in the associated QR factorization are. (b) Given \(H_{k+1, k}\), suppose we perform a step of the Arnoldi process. As a result, we now have a new upper Hessenberg matrix \(H_{k+2, k+1}\). Describe the relationship between the old and the new upper Hessenberg matrices and explain how this relationship can be used to solve the new least squares problem in an economical fashion. (c) The least squares problems throughout the iterations can be solved using a QR decomposition approach. Show that the upper triangular factor cannot be singular unless \(\mathbf{x}_{k}=\mathbf{x}\), the exact solution.

Short answer

When is the upper triangular factor \(R\) singular?

Step-by-step solution

Problem statement and variables

First of all, we are given an upper Hessenberg matrix \(H_{k+1,k}\) and we need to find the vector \(\mathbf{z}\) which minimizes: $$ \min _{\mathbf{z}}\left\|\rho e_{1}-H_{k+1, k} \mathbf{z}\right\| $$ Where \(\rho\) is a scalar constant, and \(e_1\) is a unit vector. We will use QR decomposition with Givens rotations to solve this problem. The associated QR factorization has matrices \(Q\) and \(R\).

Computing the QR factorization with Givens rotations

To compute the QR factorization using Givens rotations, we perform the following steps: 1. Initialize \(Q\) as the identity matrix. 2. For each element below the diagonal of \(H_{k+1,k}\), perform a Givens rotation: a. Compute the rotation angle which would zero that element. b. Apply the Givens rotation to both the target element and the corresponding element in the upper Hessenberg matrix. c. Multiply \(Q\) with the Givens rotation to update it for this step. After completing these steps, we will have \(R = Q^T H_{k+1,k}\), an upper triangular matrix, and \(Q\), an orthogonal matrix with the Givens rotations applied.

Solving for z

Now, we can solve the least squares problem as follows: 1. Compute the product \(Q^T (\rho e_{1})\). 2. Solve the upper triangular system \(R \mathbf{z} = Q^T (\rho e_{1})\) using backward substitution.

Updating the Hessenberg matrix after an Arnoldi process step

When we perform a step of the Arnoldi process, we obtain a new upper Hessenberg matrix \(H_{k+2, k+1}\). The relationship between the old and the new Hessenberg matrices can be described as follows: - The first \(k+1\) rows of \(H_{k+2, k+1}\) are the same as the rows of \(H_{k+1, k}\) - The \((k+2)\)-th row of \(H_{k+2, k+1}\) contains only one nonzero element in the \((k+1)\)-th column, which is the result of the Arnoldi process step We can solve the new least squares problem by simply applying a new Givens rotation to the last row of \(H_{k+2, k+1}\). This new rotation won't affect the previous work, and the updated solution can be computed efficiently.

Proof that the upper triangular factor cannot be singular unless x_k = x

We want to show that the upper triangular factor \(R\) cannot be singular unless \(\mathbf{x}_{k}=\mathbf{x}\). Suppose \(R\) is singular, which means it has a zero diagonal element. When applying Givens rotations to the Hessenberg matrix, we ensure that the diagonal elements are nonzero. Hence, the only way \(R\) could be singular is if the Hessenberg matrix already had a zero diagonal element before the Givens rotations. However, during the Arnoldi process, if a zero diagonal element was encountered in Hessenberg matrix, it means that the Krylov subspace has converged to the solution already, and thus, \(\mathbf{x}_{k}=\mathbf{x}\). Hence, the upper triangular factor cannot be singular unless \(\mathbf{x}_{k}=\mathbf{x}\) as required.

Key concepts

QR factorization

QR factorization is a mathematical process used to decompose a matrix into two components: an orthogonal matrix \(Q\) and an upper triangular matrix \(R\). In the context of solving linear least squares problems, especially within the GMRES method, this factorization provides an efficient way to handle equations and systems within algorithms. The main advantage of using QR factorization is its numerical stability, which becomes critical when performing iterations over matrices in numerical simulations.

In this exercise, QR factorization is done using Givens rotations, which are instrumental in simplifying the factorization of matrices with a specific structure, like the upper Hessenberg matrices common in numerical linear algebra problems. The matrix \(H_{k+1,k}\) in this context is first transformed such that the product \(Q^T H_{k+1,k} = R\), where \(Q\) is orthogonal and \(R\) is upper triangular.

• Orthogonal Matrix \(Q\): Helps in preserving the norms and angles during transformation.
• Upper Triangular Matrix \(R\): Makes solving systems straightforward through backward substitution methods.

QR factorization lays the groundwork for addressing the least squares issue efficiently by transforming complex eigenproblems into simpler forms.

Givens rotations

Givens rotations are a technique used in numerical linear algebra to zero out off-diagonal elements in matrices. They are particularly useful when working with upper Hessenberg matrices because they offer a way to systematically introduce zeros below the diagonal while maintaining numerical stability.

In practice, a Givens rotation is a simple rotation in the plane that can be applied directly to the rows or columns of a matrix. Each rotation is defined by a rotation angle, which is calculated to zero out the targeted element. This transformation can be visualized like aligning a certain axis with the diagonal element in a particular section of the matrix.

• Efficient Calculation: They involve only a few calculations, making them computationally efficient.
• Multiple Rotations: They are often used repeatedly in sequence to methodically transform matrices.
• Stable Results: They enhance the stability of numerical calculations by avoiding large rounding errors.

By iteratively performing Givens rotations on an upper Hessenberg matrix, one can directly use the resulting structure to facilitate the solving of least squares problems, minimizing computation time and resources.

Upper Hessenberg matrix

An upper Hessenberg matrix is a type of square matrix where all elements below the first sub-diagonal are zero. This structure appears frequently in algorithms dealing with eigenvalue problems, such as the QR algorithm or the GMRES method, due to its balanced approach to retaining matrix simplicity while allowing for complex eigenvalue interactions.

Specifically, in the iterative Arnoldi process, an upper Hessenberg matrix emerges naturally, simplifying the progression and solution of related linear problems. These matrices are essential in the GMRES method because they permit concise computations and manageable operations over successive iterations.

• Compact Structure: The partial zeros in the matrix reduce the computational complexity.
• Ease of Manipulation: Having zeros simplifies arithmetic operations which aids in faster convergence of calculations.
• Suitability for Iterations: Perfect for iterative methods as subsequent steps seamlessly build upon one manageable matrix form.

This type of matrix, due to its properties, requires fewer operations to perform Givens rotations, making it a key component in efficient numerical solutions.

Arnoldi process

The Arnoldi process is an iterative method used to convert a given matrix into an upper Hessenberg matrix which can then facilitate numerical solutions such as eigenvalue computations more efficiently. This process finds applications especially within the GMRES method as it helps in reducing complex linear systems into formats more manageable for computations like QR factorization.

During each iteration of the Arnoldi process, a vector from the Krylov subspace—a sequence of vector spaces generated by the powers of a matrix acting on an initial vector—is used to incrementally build a system of orthonormal vectors. These vectors directly contribute to forming the upper Hessenberg matrix.

• Incremental Construction: Builds the matrix in a step-by-step fashion, suitable for iterative problems.
• Krylov Subspace: Leverages subspaces that suit the GMRES' needs for convergence to an approximate eigenpair solution.
• Connection with Hessenberg: The process naturally yields Hessenberg forms that make eigenvalue computations more concise.

The Arnoldi process streamlines the conversion of matrix systems into forms where subsequent QR factorizations become more straightforward and efficient, thus creating a clearer path towards solving large linear systems.