Question

Let \(A\) be symmetric positive definite and consider the \(\mathrm{CG}\) method. Show that for \(\mathbf{r}_{k}\) the residual in the \(k\) th iteration and \(\mathbf{e}_{k}\) the error in the \(k\) th iteration, the following energy norm identities hold: (a) \(\left\|\mathbf{r}_{k}\right\|_{A^{-1}}=\left\|\mathbf{e}_{k}\right\|_{A}\). (b) If \(\mathbf{x}_{k}\) minimizes the quadratic function \(\phi(\mathbf{x})=\frac{1}{2} \mathbf{x}^{T} A \mathbf{x}-\mathbf{x}^{T} \mathbf{b}\) (note that \(\mathbf{x}\) here is an argument vector, not the exact solution) over a subspace \(S\), then the same \(\mathbf{x}_{k}\) minimizes the error \(\left\|\mathbf{e}_{k}\right\|_{A}\) over \(S\).

Short answer

Question: Prove the identity \(\left\|\mathbf{r}_{k}\right\|_{A^{-1}}=\left\|\mathbf{e}_{k}\right\|_{A}\) and show that if \(\mathbf{x}_{k}\) minimizes the quadratic function \(\phi(\mathbf{x})\) over a subspace \(S\), then it also minimizes the error \(\left\|\mathbf{e}_{k}\right\|_{A}\) over \(S\). Answer: We have shown that \(\left\|\mathbf{r}_{k}\right\|_{A^{-1}}=\left\|\mathbf{e}_{k}\right\|_{A}\) by transforming the expressions and making use of the properties of symmetric positive definite matrices. Moreover, we showed that if \(\mathbf{x}_{k}\) minimizes the quadratic function \(\phi(\mathbf{x})\) over a subspace \(S\), it also minimizes the error \(\left\|\mathbf{e}_{k}\right\|_{A}\) over \(S\) by demonstrating that minimizing \(\phi(\mathbf{x})\) over \(S\) is equivalent to minimizing \(\left\|\mathbf{e}_{k}\right\|_{A}\) over \(S\).

Step-by-step solution

Part (a) Proof of \(\left\|\mathbf{r}_{k}\right\|_{A^{-1}}=\left\|\mathbf{e}_{k}\right\|_{A}\)

Define \(\mathbf{r}_{k}=\mathbf{b}-A \mathbf{x}_{k}\) and \(\mathbf{e}_{k}=\mathbf{x}_{\text{exact}}-\mathbf{x}_{k}\), where \(\mathbf{x}_{\text{exact}}\) is the exact solution of the system \(A \mathbf{x}=\mathbf{b}\). We are given that \(A\) is symmetric positive definite, so \(A^{-1}\) also exists and is symmetric positive definite. The energy norm \(\left\|\cdot\right\|_A\) is defined as \(\left\|\mathbf{v}\right\|_{A}=\sqrt{\mathbf{v}^TA\mathbf{v}}\) and similarly for \(\left\|\cdot\right\|_{A^{-1}}\). To show that \(\left\|\mathbf{r}_{k}\right\|_{A^{-1}}=\left\|\mathbf{e}_{k}\right\|_{A}\), we have: \begin{align*} \left\|\mathbf{r}_{k}\right\|_{A^{-1}}^2 &= \mathbf{r}_{k}^TA^{-1}\mathbf{r}_{k} \\ &= (\mathbf{b}-A \mathbf{x}_{k})^TA^{-1}(\mathbf{b}-A \mathbf{x}_{k}) \\ &= (\mathbf{b} - A(\mathbf{x}_{\text{exact}} - \mathbf{e}_{k}))^T A^{-1}(\mathbf{b} - A(\mathbf{x}_{\text{exact}} - \mathbf{e}_{k})) \\ &= (\mathbf{b}-\mathbf{b}+A \mathbf{e}_{k})^TA^{-1}(\mathbf{b}-\mathbf{b}+A \mathbf{e}_{k}) \\ &= \mathbf{e}_{k}^TAA^{-1}A\mathbf{e}_{k} \\ &= \mathbf{e}_{k}^TA\mathbf{e}_{k} \\ &= \left\|\mathbf{e}_{k}\right\|_{A}^2 \end{align*} Thus, \(\left\|\mathbf{r}_{k}\right\|_{A^{-1}}=\left\|\mathbf{e}_{k}\right\|_{A}\).

Part (b) Minimizing \(\phi(\mathbf{x})\) and \(\left\|\mathbf{e}_{k}\right\|_{A}\)

Given that \(\mathbf{x}_{k}\) minimizes the quadratic function \(\phi(\mathbf{x})=\frac{1}{2} \mathbf{x}^T A \mathbf{x}-\mathbf{x}^T\mathbf{b}\) over a subspace \(S\), we want to show that the same \(\mathbf{x}_{k}\) minimizes the error \(\left\|\mathbf{e}_{k}\right\|_{A}\) over \(S\). First, let's write \(\phi(\mathbf{x})\) in terms of \(\mathbf{e}_{k}\): \begin{align*} \phi(\mathbf{x}) &= \frac{1}{2} \mathbf{x}^T A \mathbf{x}-\mathbf{x}^T\mathbf{b} \\ &= \frac{1}{2} (\mathbf{x}_{\text{exact}}-\mathbf{e}_{k})^TA(\mathbf{x}_{\text{exact}}-\mathbf{e}_{k}) - (\mathbf{x}_{\text{exact}}-\mathbf{e}_{k})^T\mathbf{b} \\ &= \frac{1}{2}\mathbf{e}_{k}^TAA^{-1}A\mathbf{e}_{k} - \frac{1}{2}\mathbf{e}_{k}^TAA^{-1}\mathbf{b} \\ &= \frac{1}{2}\mathbf{e}_{k}^TA\mathbf{e}_{k} - \frac{1}{2}\mathbf{e}_{k}^T\mathbf{r}_{k} \\ \end{align*} Now, minimizing \(\phi(\mathbf{x})\) over \(S\) is equivalent to minimizing \(\frac{1}{2}\mathbf{e}_{k}^TA\mathbf{e}_{k} - \frac{1}{2}\mathbf{e}_{k}^T\mathbf{r}_{k}\) over \(S\). However, since \(\mathbf{e}_{k}^T\mathbf{r}_{k}\) is a constant, minimizing \(\phi(\mathbf{x})\) over \(S\) is equivalent to minimizing \(\frac{1}{2}\mathbf{e}_{k}^TA\mathbf{e}_{k}\) over \(S\). Finally, as \(\frac{1}{2}\mathbf{e}_{k}^TA\mathbf{e}_{k} = \left\|\mathbf{e}_{k}\right\|_{A}^2\), then minimizing \(\phi(\mathbf{x})\) over \(S\) is also equivalent to minimizing \(\left\|\mathbf{e}_{k}\right\|_{A}\) over \(S\). Therefore, the same \(\mathbf{x}_{k}\) that minimizes \(\phi(\mathbf{x})\) over \(S\) also minimizes \(\left\|\mathbf{e}_{k}\right\|_{A}\) over \(S\).

Key concepts

Symmetric Positive Definite Matrix

In the realm of numerical linear algebra, a symmetric positive definite (SPD) matrix is a key concept. A matrix \(A\) is symmetric if it is equal to its transpose, meaning \(A^T = A\). It is positive definite if, for any non-zero vector \(\mathbf{v}\), the quadratic form \(\mathbf{v}^T A \mathbf{v} > 0\) holds. These properties make SPD matrices very useful for methods like the Conjugate Gradient (CG) method, employed for solving systems of linear equations.
The SPD property ensures the existence, uniqueness, and numerical stability when finding solutions.
This is because they guarantee that the matrix has real, positive eigenvalues.
An implication of this quality is the guarantee that the matrix is invertible and well-conditioned, providing robustness needed for CG methods used in solving optimization problems.
In essence, SPD matrices provide a secure mathematical foundation for minimizing quadratic functions, as highlighted by their application in energy norms and error minimization.

Energy Norm

The energy norm is a specialized norm used in the analysis of linear systems and iterative methods like the Conjugate Gradient method. For a given vector \(\mathbf{v}\) and SPD matrix \(A\), the energy norm, denoted as \(\|\mathbf{v}\|_A\), is defined as \(\sqrt{\mathbf{v}^T A \mathbf{v}}\).
This norm is crucial because it takes into account the metric induced by the matrix \(A\), allowing for proper scaling of vectors in the transformation space.

• The energy norm is specifically tailored for problems where the matrix \(A\) represents a physical property like stiffness or conductivity.
• This norm simplifies to the Euclidean norm when \(A\) is the identity matrix, indicating its versatility.

In the context of the CG method, this norm helps in analyzing residuals and errors by providing more relevant insights into the convergence of the iterative process.

Quadratic Function Minimization

Quadratic function minimization focuses on minimizing functions of the form \(\phi(\mathbf{x}) = \frac{1}{2} \mathbf{x}^T A \mathbf{x} - \mathbf{x}^T \mathbf{b}\) where \(A\) is an SPD matrix. This form is standard in optimization problems and is important due to its simplicity and the existence of efficient algorithms to solve it, like the CG method.
In these problems, the quadratic function \(\phi(\mathbf{x})\) represents the potential energy, whereby the goal is to find the argument \(\mathbf{x}_k\) that minimizes this function over a given subspace \(S\). This corresponds to finding the most stable state in terms of reduced energy or cost.

• The SPD nature of \(A\) guarantees that there is a unique minimum point, ensuring convergence of optimization algorithms.
• The minimization links closely with the error minimization in CG, where finding the correct \(\mathbf{x}_k\) also minimizes the error norm \(\|\mathbf{e}_k\|_A\).

This process is not just a mathematical exercise but has real-world applications in structural engineering, data fitting, and economics, where such minimization problems directly translate into optimal solutions.

Residual and Error Analysis

In iterative methods like the Conjugate Gradient method, understanding residual and error analysis is critical to assess convergence and accuracy. The residual \(\mathbf{r}_k\) represents the difference between the observed value \(\mathbf{b}\) and the value estimated by the current solution \(A\mathbf{x}_k\). It is defined as \(\mathbf{b} - A\mathbf{x}_k\).
On the other hand, the error \(\mathbf{e}_k\) is the difference between the true solution \(\mathbf{x}_{\text{exact}}\) and the estimated solution \(\mathbf{x}_k\). Both residuals and errors provide insights:

• The norm of the residual in \(A^{-1}\) indicates how far the current estimate is from satisfying the system.
• The norm of the error in \(A\) gives a direct measure of how close we are to the exact solution.

The fascinating part is how the two are related in

• In CG, it is shown that the energy norm of the residual \(\|\mathbf{r}_k\|_{A^{-1}}\) equals the energy norm of the error \(\|\mathbf{e}_k\|_A\). This property is crucial as it signals a balance between approximation and correction.

Such analysis is instrumental in designing efficient algorithms with assured rates of convergence.