I am trying to solve $Ax=b$ using the conjugate gradient method. However, it is important to me to obtain a bound not only on the usual residual $||b-Ax_k||_2$ but also on the quantity $||b-Ax_k||_1$.

I have two questions:

  1. Is it true that $||b-Ax_k||_1 \leq C ||b-Ax_0||_1$ for all iterations $k$ where $C$ is some constant?

In other words, is it true that the conjugate gradient amplifies $1$-norm of the residual by at most a constant factor?

If we can choose $C=\sqrt{n}$ (where $A \in \mathbb{R}^{n \times n}$) then the above fact is trivial since its true with the 1-norm replaced by the 2-norm and using the bound $||\cdot||_1 \leq \sqrt{n} ||\cdot||_2$. However, I'd like to $C$ to be a constant not depending on dimension $n$.

  1. If the answer to question one is negative, is there some modification of the conjugate gradient which achieves such a bound?

Your Answer

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

Browse other questions tagged or ask your own question.