The relative error of the solution of a system of linear equation $Ax=b$, for any natural norm $\|\cdot\|$ is bounded by $$ \frac{1}{\| A\| \|A^{-1} \|} \frac{\|r\|}{\|b\|} \le \frac{\|e\|}{\|x\|} \le \| A\| \|A^{-1} \| \frac{\|r\|}{\|b\|} $$ where $r=Ax_{approx}-b$ and $e=x_{approx}-x_{exact}$. We call $\| A\| \|A^{-1} \|$ condition number of the square matrix $A$ and is denoted by $Cond(A)$. The condition number is greater than or equal to one. I read that the condition number heavily depends on the norm used. But since $Cond(A) \ge 1$ we can say when the condition number is small, $\|r\| / \|b\|$ is a good measure for the error.
I'm confused about this. Since the condition number depends on the norm used, then if a norm minimize the condition number i.e. $Cond(A)\approx 1$ and thus minimize the error, another norm can maximize that. Then when the condition number is small how we can say $\|r\| / \|b\|$ is a good measure for the error?
Good question.
Note that the condition number of a matrix $A$ depends on the norm used. This is true. However, if a matrix $A$ is well-conditioned, it will stay well-conditioned with respect to other values also. On the other hand, if a matrix $A$ is ill-conditioned (having a high value of $\kappa(A)$) with respect to some norm, then it will be ill-conditioned with respect to other norms also. In a finite-dimensional Banach space, all norms are equivalent, and the choice of a norm does not affect the sensitivity analysis of solutions of linear systems $A \mathbf{x} = \mathbf{B}$.