0
$\begingroup$

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. :)

$\endgroup$
1
  • $\begingroup$ @FedericoPoloni Thanks. You are right. I edited the question. $\endgroup$
    – arash
    Mar 29 at 8:48
5
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ It is not only choice though, is it? I think you should discuss the subtleties of the convergence analysis of CG. Particularly, CG uses the A-inner product $(Ax,x)$ to compute the update vectors $p_i$, hence, $p_i$ are A-orthogonal (or Conjugate) and as a result the residual is minimized in the A-norm naturally. In contrast, the GCR method generates update vectors $A^TA$-orthogonal and, in return, the residual is minimized in vector 2-norm naturally. $\endgroup$ Mar 26 at 23:57
  • $\begingroup$ @AbdullahAliSivas I am not familiar enough with GCR to comment. You may very well be right. $\endgroup$ Mar 27 at 2:42
  • $\begingroup$ @WolfgangBangerth I cannot agree more with your statement regarding the coincidence of both methods (A-norm and 2-norm) in the case of SPD matrices. This norm equivalent, however, isn't that clear to me. $\endgroup$
    – arash
    Mar 29 at 8:54
  • 1
    $\begingroup$ While all norms on finite-dimensional vector spaces are equivalent, very often we're approximating a solution that lives in an infinite-dimensional Banach space. Using a norm that fails to reproduce the norm in that Banach space in the limit often results in mesh-dependent convergence and other generalized sadness. I 100% agree with the second paragraph you wrote, but I've been bit by this norm thing so many times that I flinch whenever I see this statement repeated without further qualification. Often the fix is as simple as multiplying by a mass matrix. $\endgroup$ Mar 29 at 15:33
  • $\begingroup$ @DanielShapero Yes, I am a big fan of starting in function spaces and thinking about what that means for the discretized problem. $\endgroup$ Mar 29 at 15:58
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.