Problem 8 - A First Course in the Numerical Analysis of Differential Equations

Question

Let $$ A=\left[\begin{array}{cc} A_{1} & A_{2} \\ A_{2}^{\top} & A_{3} \end{array}\right], \quad S=\left[\begin{array}{cc} A_{1} & O \\ O & A_{2} \end{array}\right] $$ where \(A_{1}, A_{3}\) are symmetric \(d \times d\) matrices and the rank of the \(d \times d\) matrix \(A_{2}\) is \(r \leq d-1\). We further stipulate that the \((2 d) \times(2 d)\) matrix \(A\) is positive definite. a Let \(A_{1}=L_{1} L_{1}^{T}, A_{3}=L_{3} L_{3}^{\top}\) be Cholesky factorizations and assume that the preconditioner \(B\) is the lower-triangular Cholesky factor of \(S\) (hence \(\left.B B^{\top}=S\right)\). Prove that $$ C=B^{-1} A B^{-\top}=\left[\begin{array}{cc} I & F \\ F^{\top} & I \end{array}\right], \quad \text { where } \quad F=L_{1}^{-1} A_{2} L_{3}^{-T} . $$ \(\mathbf{b}\) Supposing that the eigenvalues of \(C\) are \(\lambda_{1}, \ldots, \lambda_{2 d}\), while the eigenvalues of \(F F^{\top}\) are \(\mu_{1}, \ldots, \mu_{d} \geq 0\), prove that, without loss of generality, $$ \lambda_{k}=1-\sqrt{\mu_{k}}, \quad \lambda_{d+k}=1+\sqrt{\mu_{k}}, \quad k=1,2, \ldots, d . $$ c Prove that the rank of \(F F^{\top}\) is \(r\), thereby deducing that \(C\) has at most \(2 r+1\) distinct eigenvalues. What does this tell you about the number of steps before the PCG method terminates in exact arithmetic?

Step-by-Step Solution

Answer

Matrix \( C \) is block structured, with eigenvalues influenced by \( FF^\top \). PCG terminates in \( 2r+1 \) steps.

Step 1: Understanding Matrix Definitions

Matrix \( A \) is defined as \( A = \begin{bmatrix} A_1 & A_2 \ A_2^\top & A_3 \end{bmatrix} \), where \( A_1 \) and \( A_3 \) are symmetric \( d \times d \) matrices, and \( A_2 \) is a \( d \times d \) matrix with rank at most \( r \leq d-1 \). Matrix \( S \) is given as \( S = \begin{bmatrix} A_1 & O \ O & A_2 \end{bmatrix} \). The matrix \( A \) is positive definite, ensuring its invertibility.

Step 2: Recall the Cholesky Decomposition

For matrix \( S \), the Cholesky decomposition gives \( B B^{\top} = S \). Therefore, \( B = \begin{bmatrix} L_1 & 0 \ 0 & L_2 \end{bmatrix} \) where \( L_1 L_1^{\top} = A_1 \) and \( L_2 L_2^{\top} = A_2 \). Since \( A_2 \) has rank \( r \), \( L_2 \) has size such that \( L_2 L_2^{\top} = A_2 \).

Step 3: Calculate \( C = B^{-1} A B^{-\top} \)

Substitute \( A \) and \( B \) into the expression for \( C \):\[ C = \begin{bmatrix} L_1^{-1} & 0 \ 0 & L_2^{-1} \end{bmatrix} \begin{bmatrix} A_1 & A_2 \ A_2^{\top} & A_3 \end{bmatrix} \begin{bmatrix} L_1^{-\top} & 0 \ 0 & L_2^{-\top} \end{bmatrix} \]Calculate the matrix-matrix product, leading to\[ C = \begin{bmatrix} I & L_1^{-1} A_2 L_3^{-\top} \ (L_1^{-1} A_2 L_3^{-\top})^{\top} & I \end{bmatrix} \]. Here, \( F = L_1^{-1} A_2 L_3^{-\top} \). This achieves the desired form of \( C \).

Step 4: Eigenvalues of Block Matrices

Given \( C = \begin{bmatrix} I & F \ F^\top & I \end{bmatrix} \), the eigenvalues are related to those of \( F F^{\top} \). For a block matrix \( \begin{bmatrix} A & B \ B^\top & D \end{bmatrix} \), if \( A = D = I \) and \( B = F \), eigenvalues are obtained by solving \( \det(C - \lambda I) = 0 \). It results in eigenvalues:\[ \lambda_k = 1 - \sqrt{\mu_k}, \quad \lambda_{d+k} = 1 + \sqrt{\mu_k} \], where \( \mu_k \) are the eigenvalues of \( FF^{\top} \).

Step 5: Rank Determination and Eigenvalue Count

The rank of \( FF^{\top} \) is \( r \) since \( A_2 \) has rank \( r \). The zero eigenvalues of \( FF^{\top} \) contribute \( d - r \) zero eigenvalues. Thus, there can be at most \( 2r + 1 \) distinct eigenvalues of \( C \) (\( [0, \ldots, 0, 1-\sqrt{\mu_1}, \ldots, 1-\sqrt{\mu_r}, 1, 1+\sqrt{\mu_1}, \ldots, 1+\sqrt{\mu_r}] \)). This implies that Preconditioned Conjugate Gradient (PCG) method terminates in at most \( 2r + 1 \) iterations.

Key Concepts

Positive Definite Matrices

A matrix is labeled as positive definite if it fulfills certain conditions. Simply put, a square matrix is said to be positive definite if all its eigenvalues are greater than zero. This characteristic ensures the matrix is invertible. Understanding a matrix's positive definiteness can lead to deeper insights into its properties.

• All the eigenvalues of a positive definite matrix are strictly positive, meaning no zero or negative values.
• The positive definiteness also stems from the quadratic form: for any non-zero vector \( \mathbf{x} \), \( \mathbf{x}^T A \mathbf{x} > 0 \).

Such matrices come in handy when working with optimization problems, stabilizing algorithms, and in statistics for probabilistic interpretations. In our exercise, matrix \( A \) is positive definite, giving it a stable and predictable nature.

Eigenvalues

Eigenvalues play a critical role in understanding matrices. They help in figuring out the directions in which a transformation stretches or compresses a space. Specifically, eigenvalues are scalars \( \lambda \) that satisfy the equation \( A\mathbf{v} = \lambda\mathbf{v} \), where \( \mathbf{v} \) is a non-zero vector called an eigenvector.

• Eigenvalues determine the matrix's behavior and condition.
• They are essential for matrix diagonalization, which simplifies complex calculations.
• In the context of this problem, eigenvalues are calculated to understand the properties of the matrix \( C \).

By exploring the eigenvalues of the matrix being examined, we unravel the stability and dynamics of its system. This knowledge is crucial for tasks like system stability analysis and solving differential equations.

Matrix Rank

The rank of a matrix gives us the count of its independent rows or columns. This is a fundamental property that provides insights into the matrix's linear transformations. In mathematical terms, it's the maximum number of linearly independent column vectors in the matrix.

• Rank determines the dimension of the matrix's column space.
• A rank deficient matrix means some of the rows/columns can be expressed as combinations of others, indicating dependency.
• In this particular example, assessing the rank of \( A_2 \) is crucial since it helps determine the count of non-zero eigenvalues and terminate conditions for algorithms like the PCG method.

Understanding rank helps in identifying if systems of linear equations have solutions and in optimizing computational tasks.

Preconditioned Conjugate Gradient Method

The Preconditioned Conjugate Gradient (PCG) method is an optimization routine for solving systems of linear equations, specifically when dealing with large, sparse, symmetric, positive definite matrices. It's a refinement of the classic conjugate gradient method.

• PCG is effective in improving the convergence rate by utilizing preconditioners.
• Preconditioning transforms the system into another equivalent one, enhancing its suitability for iterative solvers.
• Insights gleaned from the matrix \( C \) in the problem help predict the PCG method's termination point, which is linked to the rank of the matrix.

This method is highly beneficial for computational efficiency in engineering and scientific computations where solving large systems rapidly is crucial.