Why minimizing with respect to A-norm?

Question

Assume solving the linear system $A \textbf x = \textbf b$, with an $A$ so large that nothing but iterative methods may be employed. Assuming $A$ induces a norm, I realized that it is often desired to minimize the residual in the norm induced by $A$ (and not, for instance, 2-norm).

Why is that the case? What is the advantage of using $A$-norm compared to 2-norm in different (general) optimization methods (GMRES, Gradient Decent/ Biconjugate Gradient decent etc.)?

---

PS: I'm more of a visual person and I appreciate it if you come up with a more graphical explanation. :)

Answer 1

In some sense it doesn't matter: In finite dimensions, all norms are equivalent, so if an algorithm conveniently has the property that proving convergence in one norm is easy, then that's what people will choose. In practice, one oftentimes wants to reduce the norm of the residual by a certain factor, and from a practical perspective, a certain reduction in one norm probably also means that another norm has become smaller by a reasonably similar factor -- norm equivalences don't actually provide that this is so, but in practical experience that appears to be the case.

That said, at least for positive definite and symmetric matrices (i.e., exactly those for which the induced $A$ inner product is in fact a norm), there is more to it. In those cases, the solution of the linear system $$ Ax = b $$ is also the minimizer of the function $$ f(x) = \frac 12 x^T A x - x^T b $$ and so the (square of the) A-norm of the error satisfies $$ \|\tilde x-x\|_A^2 = (\tilde x-x)^T A (\tilde x-x) = \tilde x^T A \tilde x - 2 \tilde x^T A x + x^T A x \\ = \tilde x^T A \tilde x - 2 \tilde x^T b + x^T b + \underbrace{(x^Tb - x^T A x)}_{=0} \\ = 2\left[f(\tilde x) - f(x)\right]. $$ In other words, the $A$-norm of the error is also the error in the function you are trying to minimize. In many cases, this function is something like the energy stored in the system, so it has physical meaning.

Answer 2

Wolfgang Bangerth's answer already says almost everything, but another subtle detail is that GMRES/MINRES minimize the norm of the residual, i.e., $\|Ax_k-b\|$, while CG minimizes the (A-)norm of the error, i.e., $\|x_*-x_k\|_A$.

In most cases what you really want to minimize is the error, and the residual serves as an imperfect proxy: recall that by the condition number bound $\|r_k\|/\|b\| \leq \varepsilon$ only implies $\|e_k\| / \|x_*\| \leq \kappa(A) \varepsilon$.

We cannot minimize the error in the 2-norm, because we don't know the exact solution $x_*$ to compute the objective function in the first place. But if one switches to the $A$-norm then it is sufficient to know $Ax_*=b$ to compute it (up to the term $x_*^TAx_*$, which is constant and therefore can be ignored in the minimization). This trick works only when $A$ is positive definite, because otherwise this "$A$-norm" is not really a norm.

So it makes sense to minimize the $A$-norm of the error when you can, but for general $A$ all you can do is minimizing the residual.