🚀 go-pugleaf

In article <1993Jan11.083253.9521@dutrun2.tudelft.nl> rcpshdb@dutrun2.tudelft.nl (Han de Bruijn) writes:
>The condition number of a matrix  A  is defined as the absolute value of
>its largest eigenvalue divided by its smallest eigenvalue. Right?
>
>I'm at loss how this is related to the loss of decimals when solving the
>equations system:
>                      A.x = b
>
>Can someone out there provide a simple argument?

David Dodson has provided a nice derivation of the relevant
perturbation theory.  However, some additional comments are needed to
get to loss of decimals.  (I'll use LaTeX notation here, with
apologies to those who don't read it.)

If we replace $A$ by $A+E$, we find that the change $h$ in the
solution satisfies (up to second order terms in $E$)
\[
\|h\|/\|X\| \leq \kappa(A)\|E\|/\|A\|,
\]
where
\[
\kappa(A) = \|A\| \|A^{-1}\|
\]
is the condition number of $A$.  Now if $\|E\|/\|A\| = 10^{-t}$, then
the elements of $A$ will be perturbed in their $t$th decimal digits
(some qualifications about balance in the sizes of the elements of $E$
and $A$ are needed here).  Hence if $\kappa(A) = 10^{k}$, then
$\|h\|/\|X\| \leq 10^{k-t}$, so that the components of $x$ are
perturbed in their $(t-k)$th digits.  In ordinary English, if $A$ is
known to $t$ digits and $\kappa(A) = 10^{k}$, then $x$ will be known
to $t-k$ digits.

In particular, if a stable algorithm like Gaussian elimination is used
to solve the system, then $t$ is the number of digits used in the
computation.  Thus, if you try to solve a system with condition
number $10^{k}$ using Gaussian elimination, you can expect a loss
of about $k$ digits in the solution.

All this is a useful oversimplification.  For the complete story, see
an introductory text on matrix computations.

Pete Stewart