# Convergence of Conjugate Gradient Method for Positive Semi-Definite Matrix

Let $A\in\mathbb{R}^{N\times N}$ be a positive semi-definite matrix, given $b\in\mbox{Col}\left(A\right)$ we want to solve the equation system $Ax=b$ . To add some notation, we define $\left<u,v\right>_{A}:=u^{\top}Av$ and given a starting guess $x^{0}$ we define $d^{0}=r^{0}=b-Ax^{0}$ . The iterative conjugate gradient method now follows these update equations: $$\alpha^{n}:=\frac{\left(d^{n}\right)^{\top}r^{n}}{\left\Vert d^{n}\right\Vert _{A}}$$ $$x^{n+1}=x^{n}+\alpha^{n}d^{n}$$ $$r^{n+1}:=b-Ax^{n+1}$$ $$d^{n+1}=r^{n+1}-\frac{\left<d^{n},r^{n+1}\right>_{A}}{\left\Vert d^{n}\right\Vert _{A}}d^{n}$$ Now, I have shown that given $A$ is positive semi-definite then $\left\Vert d^{n}\right\Vert _{A}=0$ iff $d^{n}=0$ and I have shown that $d^{n}\in\mbox{Col}\left(A\right)$ for all $n$ , combining these two facts shows that $\alpha^{n}$ is well defined and the method can be applied to positive semi-definite matrices. Now I want to show that given the error term $e^{n}:=\hat{x}-x^{n}$ (where $\hat{x}$ is a solution for $Ax=b$ ) and given that $e^{n}\notin\ker\left(A\right)$ we have $\left\Vert e^{n}\right\Vert _{A}\to0$ when $n\to\infty$. It would also suffice to show that $\frac{\left\Vert e^{n+1}\right\Vert _{A}}{\left\Vert e^{n}\right\Vert _{A}}<1$. I was advised to look at representation of the remainder, error and current solution in an eigenbasis of $A$ but I haven't managed to get anywhere, help would be most appreciated.

Proof of monotonic error decrease: First observe that $$e_{n+1} = x_{n+1} - \hat{x} = x_{n} + \alpha_{n}d_{n} - \hat{x} = e_{n} + \alpha_{n} d_{n}$$ Thus: $$\left\Vert e_{n+1}\right\Vert _{A}^{2}=\left(e_{n}+\alpha_{n}d_{n}\right)^{\top}A\left(e_{n}+\alpha_{n}d_{n}\right)$$ $$=e_{n}^{\top}Ae_{n}+\alpha_{n}e_{n}^{\top}Ad_{n}+\alpha_{n}\overbrace{d_{n}^{\top}Ae_{n}}^{=e_{n}^{\top}Ad_{n}}+\alpha_{n}^{2}d_{n}^{\top}Ad_{n}$$ $$=\left\Vert e_{n}\right\Vert _{A}^{2}+2\left(\frac{r_{n}^{\top}d_{n}}{d_{n}^{\top}Ad_{n}}\right)e_{n}^{\top}Ad_{n}+\left(\frac{r_{n}^{\top}d_{n}}{d_{n}^{\top}Ad_{n}}\right)^{2}d_{n}^{\top}Ad_{n}$$ $$=\left\Vert e_{n}\right\Vert _{A}^{2}+2\left(\frac{r_{n}^{\top}d_{n}}{d_{n}^{\top}Ad_{n}}\right)e_{n}^{\top}Ad_{n}+\frac{\left(r_{n}^{\top}d_{n}\right)^{2}}{d_{n}^{\top}Ad_{n}}$$ $$=\left\Vert e_{n}\right\Vert _{A}^{2}+2\left(\frac{\left(-Ae_{n}\right)^{\top}d_{n}}{d_{n}^{\top}Ad_{n}}\right)e_{n}^{\top}Ad_{n}+\frac{\left(\left(-Ae_{n}\right)^{\top}d_{n}\right)^{2}}{d_{n}^{\top}Ad_{n}}$$ $$=\left\Vert e_{n}\right\Vert _{A}^{2}-2\left(\frac{e_{n}^{\top}Ad_{n}}{d_{n}^{\top}Ad_{n}}\right)\overbrace{d_{n}^{\top}Ae_{n}}^{=e_{n}^{\top}Ad_{n}}+\frac{\left(e_{n}^{\top}Ad_{n}\right)^{2}}{d_{n}^{\top}Ad_{n}}$$ $$=\left\Vert e_{n}\right\Vert _{A}^{2}-2\frac{\left(e_{n}^{\top}Ad_{n}\right)^{2}}{d_{n}^{\top}Ad_{n}}+\frac{\left(e_{n}^{\top}Ad_{n}\right)^{2}}{d_{n}^{\top}Ad_{n}}=\left\Vert e_{n}\right\Vert _{A}^{2}-\frac{\left(e_{n}^{\top}Ad_{n}\right)^{2}}{\left\Vert d_{n}\right\Vert _{A}^{2}}<\left\Vert e_{n}\right\Vert _{A}^{2}$$ I used the easily shown equality $r_{n}=-Ae_{n}$ and he last inequality is true as long as $e_{n}\neq0$.

• Why can't $d^n$ be in the nullspace of $A$? Generally speaking CG doesn't work for semidefinite matrices, so I'm nervous about what you're trying to prove here... Feb 14, 2015 at 23:15
• Because $d^{n}$ must be in the column-space of $A$ they can't be in the nullspace. See stackoverflow.com/questions/16703303/… for example. It's easy to show by induction on the update equation that $d^{n}$ are all in the column space. Feb 14, 2015 at 23:41
• Oh I see, it's assumed $b$ is in the column space. Feb 14, 2015 at 23:43

I was kind of curious about an answer working on an eigenbasis of $A$ because I only can think of treating the cg-method as Krylow-method and I can't see the direct connection there. So, if you end up with such a solution I'd be happy if you could share it here.

In return, I can at least offer the version that I already know. It basically is the approach for strictly positive definite matrices but under the given conditions it seems to work for semi-definite ones as well (which actually surprises me a little but I just can't see why it doesn't work) $-$ please correct me if I'm wrong.

As you referred to a post using symmetric positive semi-definite matrices in the comments, I assumed that the matrix given here is symmetric, too. Although this possibly isn't necessary either (but then you'd definitely have to pay more attention to how you actually use the $A$-scalar product).

Also you already pointed out that the method is well-defined as of $b\in \mbox{Col}(A)$ and that $r^n, d^n \in \mbox{Col}(A)$ for all $n\in\mathbb{N}$.

### Small Corrections

In your post you defined the $A$-scalar product $\langle u, v\rangle_A = u^\top A v$. From that, you'd usually define $\Vert u \Vert_A = \sqrt{\langle u, u\rangle_A}$. Using this definition, the update rules change to $$\alpha^n = \frac{\langle d^n, r^n\rangle_I}{\Vert d^n \Vert^2_A}$$ and $$d^{n+1} = r^{n+1} - \frac{\langle d^n, r^{n+1}\rangle_A}{\Vert d^n\Vert_A^2} d^n\text{.}$$

### $A$-orthogonality of search directions

If you already know that the search directions will be $A$-orthogonal you can skip this part. I decided to elaborate it a little because it is the important part (for Krylow-methods in general).

We define $$K_n(A,r^0) = \mbox{span}\{ A^k r^0 \mid k \in \{0,\dots,n-1\}\}$$ for all $n\in\mathbb{N}$. We claim:

For all $n\in\mathbb{N}$ we have $$K_n(A,r^0) = \mbox{span}\{d^j \mid j \in \{0,\dots,n-1\} \} = \mbox{span}\{r^j \mid \{0,\dots,n-1\} \}$$ and pairwise $A$-orthogonality of the directions $d^j$ for $j\in\{0,\dots,n\}$ as long as $r_j \neq 0$ for all $j\in\{0,\dots,n\}$.

The proof is done via induction where the induction statement is clearly fulfilled for $n=0$. So we assume the statement holds for some $n\in \mathbb{N}$ and try to show it for $n+1$. First of all, by definition of $r^n$ (using the definition of $x^n$) we have for all $j\in\{0,\dots,n\}$ $$r^n = r^j - \sum_{i=j}^{n-1} \alpha^i Ad^i.$$ Consequently, this yields for all $j\in\{0,\dots,n-1\}$ $$\begin{array}{rl} \langle d^j, r^{n} \rangle_I & = \left\langle d^j, r^j - \textstyle\sum_{i=j}^{n-1} \alpha^j Ad^i \right\rangle_I \\ & = \langle d^j, r^j - \alpha^j A d^j \rangle_I \\ & = \left \langle d^j, r^j - \frac{\langle d^j, r^j\rangle_A}{\langle d^j, d^j\rangle_A} Ad^j \right \rangle_I \\ & = 0 \end{array}$$ where we used $\langle d^j, d^i\rangle_A = 0$ for $i,j \in \{0,\dots, n-1\}$ and $i\neq j$ by induction assumption. In particular, we have $r^{n} \perp K_{n}(A,r^0)$ as of $K_{n}(A,r^0) = \mbox{span}\{d_0,\dots,d_{n-1}\}$ (also by induction assumption).

In addition, we know $K_{n-1}(A,r^0) = \mbox{span}\{r^0,\dots,A^{n-2}r^0\}$ and thus $$AK_{n-1}(A,r^0) = \mbox{span}\{Ar^0,\dots,A^{n-1}r^0\} \subseteq \mbox{span}\{r^0,\dots,A^{n-1}r^0\} = K_n(A,r^0)\text{,}$$ which implies $Ad^j \in K_n(A,r^0)$ for all $j\in \{0,\dots,n-2\}$. Together with $r^{n} \perp K_{n}(A,r^0)$ this leads to $$\langle r^n, d^j \rangle_A = (r^n)^\top Ad^j = 0$$ for all $j\in\{0,\dots,n-2\}$. In particular holds for all $j\in \{0,\dots,n-2\}$ by definition of $d^n$ and pairwise $A$-orthogonality of $\{d^i\}_{i\in\{0,\dots,n-1\}}$ by induction assumption using the above equality $$\langle d^n, d^j\rangle_A = \left\langle r^n - \frac{\langle d^{n-1}, r^n\rangle_A}{\Vert d^{n-1}\Vert_A^2} d^{n-1}, d^j\right\rangle_A = 0\text{.}$$ Furthermore, we of course have $\langle d^n, d^{n-1}\rangle_A=0$, too, which is obvious by using the definition of $d^n$ as above. In total, we have that $\{d^i\}_{i\in\{0,\dots,n\}}$ is pairwise $A$-orthogonal.

By definition of $r^n$ and $d^n$ follows that $\mbox{span}\{d^j \mid j \in \{0,\dots,n\} \} = \mbox{span}\{r^j \mid \{0,\dots,n\} \}$ (is this obvious enough?). Also, the definition of $r^n$ shows $r^n \in K_{n+1}(A,r^0)$.

The pairwise $A$-orthogonality and $\{d^i\}_{i\in\{0,\dots,n\}} \subseteq \mbox{Col}(A)$ imply linear independence of $\{d^i\}_{i\in\{0,\dots,n\}}$ (This step is important! If we couldn't assure $d^i \in \mbox{Col}(A)$ this wouldn't hold anymore). For $d^n \neq 0$ (which follows from $r^n \neq 0$) we consequently have $K_n(A,r_0) \subsetneq \mbox{span}\{d^0,\dots,d^n\}$ and thus we have $K_{n+1}(A,r^0) = \mbox{span}\{d^0,\dots,d^n\}$ because $d_n \in K_{n+1}(A,r^0)$ holds (which follows from the definition of $d^n = r^n - \beta^n d^{n-1}$ and $r^n \in K_{n+1}(A,r^0)$ and $d^{n-1} \in K_n(A,r^0)$). All in all, this leads us to $$K_n(A,r^0) = \mbox{span}\{d^j \mid j \in \{0,\dots,n-1\} \} = \mbox{span}\{r^j \mid \{0,\dots,n-1\} \}$$ so that the claim is proved.

### Convergence

This part basically uses the same arguments as in the proof above. So just for the case that part was skipped or is partly wrong...

Let $n\in\mathbb{N}$ and $\hat{x}$ fulfill $A\hat{x} = b$. Then we have $A(\hat{x}-x^n) = b-Ax^n = r^n$. Using $A$-orthogonality of the $d^j$ we have for all $j\in \{0,\dots,n-1\}$ (just as in the proof above) $$\langle r^n, d^j \rangle_I = \langle r^j - \textstyle \sum_{i=j}^{n-1} \alpha^i Ad^i, d^j \rangle_I = \langle r^j - a^j Ad^j, d^j \rangle_I = \langle r^j - \frac{\langle r^j, d^j\rangle_A}{\langle d^j, d^j\rangle_A} A d^j, d^j \rangle_I = 0.$$ Because the $d^j$ are $A$-orthogonal, non-zero (else we already converged) and a subset of $\mbox{Col}(A)$ we have that the $d^j$ are linearly independent. This implies that for $n = \mbox{dim}(\mbox{Col}(A))$ holds $\mbox{span}\{d_0,\dots,d_{n-1}\} = \mbox{Col}(A)$. From the above property we then have $r^n \perp \mbox{span}\{d_0,\dots,d_{n-1}\} = \mbox{Col}(A)$ but by construction we also have $r^n \in \mbox{Col}(A)$. This implies $r^n = 0$. So we have $0 = r^n = b - Ax^n$ and thus $$\Vert \hat{x}-x^n \Vert_A^2 = \langle \hat{x} - x, \hat{x}-x \rangle_A = (\hat{x}-x)^\top A(\hat{x}-x) = (\hat{x}-x)^\top r^n = 0\text{.}$$ In particular, we have $\Vert \hat{x}-x^n \Vert_A^2 \to 0$ for $n\to \infty$.

• Hey Murp, thanks for your reply! I'm afraid I wasn't able to find any useful way to use the spectral decomposition of $A$ in order to prove these properties (no idea why it was given as a hint), I was however able to additionally prove that the error is monotonically decreasing in the $A$-norm, I will add that to my post later today. Feb 26, 2015 at 6:35