🚀 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?

Backward error analysis of Gaussian Elimination shows that the error
introduced during the factorization because of finite precision floating
point arithmetic can be modelled as by making small normwise relative
perturbations to the matrix and the right-hand side, where "small" means
a few times the computer's machine epsilon.

Suppose you have a non-singular linear system A.x = b and you perturb the
matrix and right-hand side.  How much is the solution perturbed; i.e.,
how big is dx if (A+dA).(x+dx) = b+db ?

	(A + dA).(x + dx) = b + db

	(A + dA).dx =  b + db - A.x - dA.x

		    = b + db - b - dA.x

		    = db - dA.x

	dx = (A + dA)^-1.(db - dA.x)

	   =A^-1.(I+A^-1.dA)^-1.(db - dA.x)

	||dx|| <= ||A^-1.(I+A^-1.dA)^-1||.||(db - dA.x)||


Assume ||A^-1||.||dA|| < 1.  Then (I+A^-1.dA)^-1 exists and

	||(I+A^-1.dA)^-1|| <= (1-||A^-1||.||dA||)^-1.

Hence
	||dx|| <= ||A^-1||.||(I+A^-1.dA)^-1||.||(db - dA.x)||

	       	      ||A^-1||
	       <= ----------------- . (||dA||.||x|| + ||db||)
		  1-||A^-1||.||dA||

	||dx||        ||A^-1||        ||dA||.||x|| + ||db||
	------  = ----------------- . ---------------------
	||x||	  1-||A^-1||.||dA||          ||x||

	||dx||        ||A^-1||                  ||db||
	------  = ----------------- . (||dA|| + ------)
	||x||	  1-||A^-1||.||dA||             ||x||

	||dx||      ||A||.||A^-1||     ||dA||      ||db||
	------  = ----------------- . (------ + -----------)
	||x||	  1-||A^-1||.||dA||    ||A||	||A||.||x||

	||dx||      ||A||.||A^-1||     ||dA||   ||db||
	------ <= ----------------- . (------ + -------)
	||x||	  1-||A^-1||.||dA||    ||A||	||A.x||

	||dx||      ||A||.||A^-1||     ||dA||   ||db||
	------ <= ----------------- . (------ + ------)
	||x||	  1-||A^-1||.||dA||    ||A||	||b||

Define kappa(A) = ||A||.||A^-1||.  This says that if dA is not too big, the
normwise relative perturbation in the solution is bounded by the condition
number times the sum of normwise relative perturbations of the matrix and
right-hand side.

Finally, ||A||_2 is given by the largest magnitude of the eigenvalues of A
and ||A^-1||_2 is given by the smallest magnitude of the eigenvalues of A,
if A is a normal matrix, but not in general.

----------------------------------------------------------------------

Dave Dodson		                             dodson@convex.COM
Convex Computer Corporation      Richardson, Texas      (214) 497-4234