Conjugate residual method

Remarks

The method is the conjugate gradient method with the inner product $\ip{u}{v} = u^T A v$ in place of $u^T v$. Conjugate gradients in this inner product minimize $\norm{x - x^*}_{A^2}$, and $\norm{x - x^*}_{A^2} = \norm{A(x - x^*)}_2 = \norm{b - A x}_2$, which gives clause 1. Clause 2 is the image of the orthogonality and conjugacy relations of conjugate gradients under the change of inner product. The update of $A p_{k+1}$ saves a product with $A$, so each step needs one product, $A r_{k+1}$. Example: if $r_0$ is an eigenvector of $A$ for $\lambda$, then $\alpha_0 = \lambda r_0^T r_0 / \lambda^2 r_0^T r_0 = 1 / \lambda$ and $r_1 = 0$. For a symmetric indefinite $A$ the same formulas can be run, but $r_k^T A r_k$ can vanish and the method then breaks down. The MINRES method avoids this breakdown.

Going deeper

For a student

For symmetric positive definite systems, conjugate residuals and conjugate gradients minimize different norms over the same Krylov spaces. In practice the residual norm of conjugate residuals is monotone, which is convenient for stopping tests. For indefinite symmetric systems MINRES is the robust choice, and for nonsymmetric systems the generalizations GCR and GMRES apply. Like all Krylov iterative methods, it is normally combined with a preconditioner.