Proofs: Conjugate gradient method

The Chebyshev bound on the error of CG full

This proof shows: matvecs.worst.

Exact arithmetic, notation of the correctness proof. $0 < \lambda_{\min} \le \lambda_{\max}$ are the extreme eigenvalues of $A$ and $\kappa = \lambda_{\max}/\lambda_{\min}$. $\mathcal{P}_k^1$ is the set of real polynomials $q$ of degree at most $k$ with $q(0) = 1$.

Lemma 1. As long as CG has not stopped, $\|e_k\|_A = \min_{q \in \mathcal{P}_k^1} \|q(A) e_0\|_A$.

Proof. $y \in x_0 + \mathcal{K}_k(A, r_0)$ exactly when $x - y = e_0 - s(A) r_0$ for a polynomial $s$ of degree at most $k - 1$. Since $r_0 = A e_0$, this is $x - y = q(A) e_0$ with $q(t) = 1 - t s(t)$, and the map $s \mapsto q$ is a bijection onto $\mathcal{P}_k^1$. Corollary 1 of the correctness proof says that $x_k$ minimizes $\|x - y\|_A$ over these $y$. $\square$

Lemma 2. For each $q$, $\|q(A) e_0\|_A \le \max_{\lambda \in [\lambda_{\min}, \lambda_{\max}]} |q(\lambda)| \, \|e_0\|_A$.

Proof. Let $A = V \Lambda V^T$ with $V$ orthogonal and $e_0 = V c$. Then $\|q(A) e_0\|_A^2 = \sum_i \lambda_i q(\lambda_i)^2 c_i^2 \le \max_i q(\lambda_i)^2 \sum_i \lambda_i c_i^2$, and $\sum_i \lambda_i c_i^2 = \|e_0\|_A^2$. Each $\lambda_i$ lies in the interval. $\square$

Theorem. $\|e_k\|_A \le 2 \left( \frac{\sqrt\kappa - 1}{\sqrt\kappa + 1} \right)^k \|e_0\|_A$. Consequently $\|e_k\|_A \le \varepsilon \|e_0\|_A$ for each $k \ge \tfrac12 \sqrt\kappa \ln(2/\varepsilon)$, $0 < \varepsilon \le 1$.

Proof. If $\kappa = 1$ then $A = \lambda I$, $r_1 = 0$ and the bound holds for $k \ge 1$ (and for $k = 0$ trivially). Let $\kappa > 1$. Let $T_k$ be the Chebyshev polynomial of degree $k$: $T_k(\cos\theta) = \cos(k\theta)$, so $|T_k(t)| \le 1$ on $[-1, 1]$, and for $|t| \ge 1$, $T_k(t) = \tfrac12 \bigl[(t + \sqrt{t^2 - 1})^k + (t - \sqrt{t^2 - 1})^k\bigr]$. Put $\sigma = (\lambda_{\max} + \lambda_{\min})/(\lambda_{\max} - \lambda_{\min}) = (\kappa + 1)/(\kappa - 1) > 1$ and

Then $q(0) = 1$, $q$ has degree $k$, and the argument of $T_k$ in the numerator lies in $[-1, 1]$ for $\lambda$ in the interval. So $\max |q| \le 1/T_k(\sigma)$ there. Both terms of the formula for $T_k(\sigma)$ are positive, so $T_k(\sigma) \ge \tfrac12 (\sigma + \sqrt{\sigma^2 - 1})^k$. Now $\sigma^2 - 1 = 4\kappa/(\kappa - 1)^2$, so

Lemmas 1 and 2 give the first claim.

For the second, let $t = 1/\sqrt\kappa \in (0, 1)$. Then $\ln\frac{\sqrt\kappa + 1}{\sqrt\kappa - 1} = \ln\frac{1 + t}{1 - t} = 2(t + t^3/3 + t^5/5 + \cdots) \ge 2t$. So $2 \bigl(\frac{\sqrt\kappa - 1}{\sqrt\kappa + 1}\bigr)^k \le 2 e^{-2k/\sqrt\kappa} \le \varepsilon$ when $k \ge \tfrac12 \sqrt\kappa \ln(2/\varepsilon)$. $\blacksquare$

Cost. Each pass of line L2 does one product with $A$, and the start does one more. So reducing the $A$-norm of the error by $\varepsilon$ takes at most $\lceil \tfrac12 \sqrt\kappa \ln(2/\varepsilon) \rceil + 1$ products in exact arithmetic, and $O((z + n)\sqrt\kappa \log(2/\varepsilon))$ flops for a matrix with $z$ nonzeros.

CG produces orthogonal residuals and conjugate directions, minimizes the A-norm error and terminates full

This proof shows: correctness, termination.

Exact arithmetic. $A$ is symmetric positive definite, $x$ solves $A x = b$, and $r_k, p_k, x_k, \alpha_k, \beta_k, \rho_k = r_k^T r_k$ are the values of the pseudocode after $k$ passes (with tolerance $0$, so the loop stops only when $r_k = 0$). Write $\mathcal{K}_k = \mathcal{K}_k(A, r_0)$ and $\langle v, w \rangle_A = v^T A w$, an inner product because $A$ is positive definite.

Theorem. Let $k \ge 1$ and assume $r_0, \ldots, r_{k-1}$ are all nonzero. Then:

• (S) $\operatorname{span}\{r_0, \ldots, r_{k-1}\} = \operatorname{span}\{p_0, \ldots, p_{k-1}\} = \mathcal{K}_k$, and $x_k - x_0 \in \mathcal{K}_k$;
• (O) $r_k^T p_j = 0$ and $r_k^T r_j = 0$ for all $j < k$;
• (C) $p_k^T A p_j = 0$ for all $j < k$;
• (P) $p_j \ne 0$ and $p_j^T A p_j > 0$ for $j < k$, so each $\alpha_j$ is defined, and $\alpha_j = \rho_j / (p_j^T A p_j)$ with $\rho_j = r_j^T p_j$.

Proof. Induction on $k$.

Base $k = 1$. $p_0 = r_0 \ne 0$, so $p_0^T A p_0 > 0$ and (P) holds; $\mathcal{K}_1 = \operatorname{span}\{r_0\}$ and $x_1 - x_0 = \alpha_0 p_0$, so (S) holds. $r_1^T p_0 = r_0^T r_0 - \alpha_0 p_0^T A p_0 = \rho_0 - \rho_0 = 0$, and $r_0 = p_0$, so (O) holds. $p_1^T A p_0 = r_1^T A p_0 + \beta_0 p_0^T A p_0$. From line L7, $A p_0 = (r_0 - r_1)/\alpha_0$, so $r_1^T A p_0 = (r_1^T r_0 - \rho_1)/\alpha_0 = -\rho_1/\alpha_0$, and $p_0^T A p_0 = \rho_0/\alpha_0$. With $\beta_0 = \rho_1/\rho_0$ the sum is $-\rho_1/\alpha_0 + \rho_1/\alpha_0 = 0$, so (C) holds.

Step. Assume the statements for $1, \ldots, k$ and that $r_k \ne 0$; we prove them for $k + 1$.

(P) for $j = k$: by (O), $r_k^T p_{k-1} = 0$, so $\|p_k\|_2^2 = \|r_k + \beta_{k-1} p_{k-1}\|_2^2 = \|r_k\|_2^2 + \beta_{k-1}^2 \|p_{k-1}\|_2^2 \ge \|r_k\|_2^2 > 0$. So $p_k \ne 0$ and $p_k^T A p_k > 0$. Also $r_k^T p_k = r_k^T r_k + \beta_{k-1} r_k^T p_{k-1} = \rho_k$.

(S): $p_k = r_k + \beta_{k-1} p_{k-1}$ and $r_k = r_{k-1} - \alpha_{k-1} A p_{k-1}$, with $A p_{k-1} \in A \mathcal{K}_k \subseteq \mathcal{K}_{k+1}$. So $r_k, p_k \in \mathcal{K}_{k+1}$ and the spans of the first $k+1$ residuals and directions lie in $\mathcal{K}_{k+1}$. The directions $p_0, \ldots, p_k$ are nonzero and pairwise $A$-orthogonal by (C) and (P), so they are linearly independent, and their span has dimension $k + 1 \ge \dim \mathcal{K}_{k+1}$. So all three spaces are equal. The residuals $r_0, \ldots, r_k$ are nonzero and pairwise orthogonal by (O), so they span the same space too. Finally $x_{k+1} - x_0 = (x_k - x_0) + \alpha_k p_k \in \mathcal{K}_{k+1}$.

(O): $r_{k+1} = r_k - \alpha_k A p_k$. For $j < k$, $r_{k+1}^T p_j = r_k^T p_j - \alpha_k p_k^T A p_j = 0 - 0$ by (O) and (C). For $j = k$, $r_{k+1}^T p_k = \rho_k - \alpha_k p_k^T A p_k = 0$ by the formula for $\alpha_k$. So $r_{k+1}$ is orthogonal to $p_0, \ldots, p_k$, hence to $\mathcal{K}_{k+1}$ by (S), hence to $r_0, \ldots, r_k$.

(C): $p_{k+1}^T A p_j = r_{k+1}^T A p_j + \beta_k p_k^T A p_j$. For $j < k$: $A p_j \in \mathcal{K}_{j+2} \subseteq \mathcal{K}_{k+1}$, so the first term is $0$ by (O), and the second is $0$ by (C). For $j = k$: the computation of the base case, with $k$ in place of $0$, gives $r_{k+1}^T A p_k = -\rho_{k+1}/\alpha_k$ and $\beta_k p_k^T A p_k = (\rho_{k+1}/\rho_k)(\rho_k/\alpha_k)$, which sum to $0$. $\square$

Corollary 1 (optimality). Under the same assumption, $x_k$ is the unique minimizer of $\|x - y\|_A$ over $y \in x_0 + \mathcal{K}_k$.

Proof. Let $e_k = x - x_k$; then $A e_k = r_k$. For $y = x_k + w$ with $w \in \mathcal{K}_k$, $\|x - y\|_A^2 = \|e_k\|_A^2 - 2 w^T A e_k + \|w\|_A^2 = \|e_k\|_A^2 - 2 w^T r_k + \|w\|_A^2$. By (O) and (S), $w^T r_k = 0$. So $\|x - y\|_A^2 = \|e_k\|_A^2 + \|w\|_A^2$, which is smallest exactly for $w = 0$; and $x_k \in x_0 + \mathcal{K}_k$ by (S). $\square$

Corollary 2 (termination). Some $r_k$ with $k \le n$ is zero, so CG returns $x$ after at most $n$ passes of line L2 (if maxit $\ge n + 1$).

Proof. If $r_0, \ldots, r_{n-1}$ were all nonzero, then by (O) $r_n$ is orthogonal to the $n$ nonzero, pairwise orthogonal vectors $r_0, \ldots, r_{n-1}$, which span $\mathbb{R}^n$, so $r_n = 0$. If $r_k = 0$, line L3 returns $x_k$, and $A x_k = b$. $\square$

Remark (fewer steps). Write $r_0 = \sum_i c_i v_i$ in an orthonormal eigenbasis of $A$, and let $d$ be the number of distinct eigenvalues $\lambda$ with some $c_i \ne 0$ for $v_i$ in the eigenspace of $\lambda$. Then $\mathcal{K}_k$ lies in the span of the $d$ vectors $\sum_{\lambda_i = \lambda} c_i v_i$, so $\dim \mathcal{K}_k \le d$, and the argument of Corollary 2 within this space gives $r_d = 0$. $\blacksquare$