0
$\begingroup$

I was reading the Wikipedia's article regarding the condition number, and it states:

For example, the condition number associated with the linear equation $Ax = b$ gives a bound on how inaccurate the solution $x$ will be after approximation.

...

In particular, one should think of the condition number as being (very roughly) the rate at which the solution, $x$, will change with respect to a change in $b$. Thus, if the condition number is large, even a small error in $b$ may cause a large error in $x$. On the other hand, if the condition number is small then the error in $x$ will not be much bigger than the error in $b$.

This is quite understandable, but then we have the following steps.

The condition number is defined more precisely to be the maximum ratio of the relative error in $x$ divided by the relative error in $b$.

Let $e$ be the error in $b$. Assuming that $A$ is a nonsingular matrix, the error in the solution$A^{−1}b$ is $A^{−1}e$. The ratio of the relative error in the solution to the relative error in b is

$${\displaystyle {\frac {\frac {\left\Vert A^{-1}e\right\Vert }{\left\Vert A^{-1}b\right\Vert }}{\frac {\left\Vert e\right\Vert }{\left\Vert b\right\Vert }}}} $$

The description seems to match up partially with the formula, because the description is talking about a maximum and I don't see it described in the formula. I've also a doubt regarding what the author means by "the error in b" or "the error in x". What error are we talking about, and why?

Then, this formula/fraction is manipulated to obtain:

$${\displaystyle \left({\frac {\left\Vert A^{-1}e\right\Vert }{\left\Vert e\right\Vert }}\right)\cdot \left({\frac {\left\Vert b\right\Vert }{\left\Vert A^{-1}b\right\Vert }}\right)}$$

This was just simple algebraic manipulation. But then it says:

The maximum value (for nonzero $b$ and $e$) is easily seen[clarification needed] to be the product of the two operator norms:

$${\displaystyle \kappa (A)=\left\Vert A^{-1}\right\Vert \cdot \left\Vert A\right\Vert}$$

I don't see any connection why the previous statement should be true, with respect to its previous statements. Can you please explain me how the author(s) made this last conclusion? Which steps did he do to reach this point of saying that the condition number of a matrix is defined as $${\displaystyle \kappa (A)=\left\Vert A^{-1}\right\Vert \cdot \left\Vert A\right\Vert}$$

Note: if someone wants then to edit the Wikipedia's article by writing his/her explanation also there, it would be nice, since someone asked also for explanation there.

$\endgroup$
  • $\begingroup$ In regards to your first question, 'the descriptions is talking about a maximum and I don't see one'. The definition of a matrix norm is that $$\| A \| = \text{sup} \left \{ \frac{\| Ax \|}{\| x \|}, \| x \| \ne 0 \right \}$$ i.e a maximum. In regards to your second question 'I don't see any connection why the previous statement should be true', this again just uses the definition of a matrix norm and the fact that $$\frac{1}{\| A^{-1} \|} \le \| A \|$$ $\endgroup$ – mattos Sep 2 '16 at 15:47
1
$\begingroup$

The expression $$ \left({\frac {\left\Vert A^{-1}e\right\Vert }{\left\Vert e\right\Vert }}\right)\cdot \left({\frac {\left\Vert b\right\Vert }{\left\Vert A^{-1}b\right\Vert }}\right) $$ is the ratio of the relative error in $x$ divided by the relative error in $b$, for a fixed choice of $b$ and $e$. What we want is the maximum that this value can attain. In particular, we want to find $$ \max_{e,b \neq 0} \left({\frac {\left\Vert A^{-1}e\right\Vert }{\left\Vert e\right\Vert }}\right)\cdot \left({\frac {\left\Vert b\right\Vert }{\left\Vert A^{-1}b\right\Vert }}\right) = \left(\max_{e \neq 0} {\frac {\left\Vert A^{-1}e\right\Vert }{\left\Vert e\right\Vert }}\right)\cdot \left(\max_{b \neq 0}{\frac {\left\Vert b\right\Vert }{\left\Vert A^{-1}b\right\Vert }}\right) = \\ \left(\max_{e \neq 0} {\frac {\left\Vert A^{-1}e\right\Vert }{\left\Vert e\right\Vert }}\right)\cdot \left(\max_{x \neq 0}{\frac {\left\Vert Ax\right\Vert }{\left\Vert x\right\Vert }}\right) $$ Now, by the definition of an operator norm, this is the product $\|A^{-1}\| \cdot \|A\|$, as desired.

$\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.