Jtdylktuy

I saw some definition that if

$$M=max_{xnot=0} tfrac{|Ax|}{|x|}
quadtext{and}quad
m=min_{xnot=0} tfrac{|Ax|}{|x|} ,,$$
the condition number of $A=M/m$.

In my opinion, If we have a matrix $A$ and a vector $x$, shouldn't $tfrac{|Ax|}{|x|}$ just be a constant number? Why are there $M$ and $m$? Can anyone give a specific example?

There are different "matrix condition numbers" relative to the problem to be solved. I assume that you are inquiring about the matrix condition number to solving a linear system $Ax = b$. The condition of a problem is a measure for the sensitivity of the solution on small perturbations in the problem statement.

Using the approachin "Matrix Computations, 4th Ed" by Golub and Van Loan (MC4), we can write a perturbed version of the initial problem as $$(A + epsilon F) x(epsilon) = b + epsilon f$$ where $epsilon$ is a small quantity and $F$ and $f$ are perturbations of the original matrix $A$ and right-hand-side $b$ respectively. Clearly, $x(0) = x$: for a zero perturbation, the solution coincides with $x$.

Using a Taylor expansion, one can shown (see MC4) that $$frac{parallel x(epsilon)-x parallel}{parallel xparallel} leq kappa(A)left(midepsilonmid frac{parallel Fparallel}{parallel Aparallel} + mid epsilon mid frac{parallel fparallel}{parallel bparallel}right) +O(epsilon^{2})$$ where $kappa(A)$, the matrix condition number (without specifying the exact matrix norm) is given by $$kappa(A) = parallel A parallel cdotparallel A^{-1}parallel$$ and is a measure for the sensitivty of the problem $Ax=b$. The special case of the matrix 2-norm $$kappa_{2}(A) = {parallel A parallel}_{2}cdot {parallel A^{-1}parallel}_{2} = frac{sigma_{text{max}}(A)}{sigma_{text{min}}(A)}$$ where $sigma_{text{max}}(A)$ and $sigma_{text{min}}(A)$ denote the largest and smallest singular value of $A$ respectively (in your nomenclature $M$ and $m$, but the definitions you gave for them are not correct).

You misinterpret the definition of a matrix norm: in this defition, the vector $x$ is not fixed; the matrix norm ${parallel Aparallel}_{p}$ is defined as $${parallel Aparallel}_{p} = sup_{x neq 0} frac{{parallel Axparallel}_{p}}{{parallel xparallel}_{p}}$$ so it is in fact the supremum of a ratio of two vector norms where the supremum is searched for taking $x$ as "variable".You can then shown that ${parallel Aparallel}_{2} = sigma_{text{max}}$

As a final note and rule of thumb: in floating point, having $d$ significant digits (like 16 in IEEE double precision), solving a linear problem $Ax=b$ with $log_{10}left(kappa_{2}(A)right) approx p$, you can only "count" on $d-p$ digits to be correct in your solution $x$. So solving a problem with $kappa_{2}(A) approx 10^{12}$ will only get you at maximum 4 correct digits in the solution $x$, no matter what algorithm you apply (in fact, you will only get the 4 digits if you use the most stable algorithm available).

For in-depth reading, I suggest "Matrix Computations" by Golub and Van Loan and "Accuracy and stability of numerical algorithms" by Higham. Enjoy linear algebra, it's a wonderful world !

First of all, the term $frac{| A x |}{| x |}$ is not constant.

For example, consider a $2 times 2$ matrix and let $w_1$ and $w_2$ be the columns of $A$. Then,

$$ A x = x_1 w_1 + x_2 w_2 . $$

Now, observe that for $e_1 = (1, 0)^T$ we have that

$$frac{| A e_1 |}{| x |} = frac{| w_1 |}{| x |} = | w_1 |$$

and for $e_2 = (0,1)^T$

$$frac{| A e_2 |}{| x |} = frac{| w_2 |}{| x |} = | w_2 | ,.$$

Obviously, $| w_1 |$ and $| w_2 |$ do not need to be the same.

Now, assume that you want to compute $A e_1$; the solution is $w_1$. Furthermore, let $| w_2 | gg | w_1 |$.

On a computer, however, we are in general not able to perform an exact computation; we have to deal with round-off errors. Hence, consider the perturbed matrix vector product,

$$ A (e_1 + epsilon e_2) = w_1 + epsilon w_2 ,. $$

The difference between the true solution and the perturbed one, which is

$$ w_1 + epsilon w_2 - w_1 = epsilon w_2 ,, $$

is large (in comparison to the size of $w_1$) even if $epsilon$ is small, since $| w_2 |$ is large. Hence, the value of the perturbed matrix vector product is very different from the true value, while the perturbation of the input data was small.

You can see that it can cause problems, when a matrix sends vectors of the same magnitude to vectors of very different magnitudes, and the quotient of the largest and smallest possible magnitude is exactly the definition of the condition number.

The condition number of a matrix appears in many different contexts. One can, e.g., imagine that a large condition number also causes trouble, when solving a linear system. Take a look at @GertVdE great answer for that matter.