🚀 go-pugleaf

Dave Dodson <dodson@convex.COM> writes:

[original question deleted]
[Dodson's reply deleted except for the following excerpts.]

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

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

Dodson's proof assumes that A^(-1) exists, which is not necessary.
Here is a similar but somewhat shorter derivation that only assumes
that there is a unique solution to Ax = b.  It derives the bound using
a first order differential approximation to the deviations, which
simplifies matters considerably.

If Ax = b has a unique solution then A has full column rank, in which
case an explicit formula for the solution is

	x = (A'A)^(-1)A'b = Cb

where C = (A'A)^(-1)A'.  Note that C'C = (A'A)^(-1).

Let |y| denote the usual Euclidean norm for a vector y, and define the
norm of a matrix Z by:

	          |Zy|
	|Z| = max ---- = Sqrt( maximum eigenvalue of Z'Z )
	       y   |y|

This norm satisfies: |ZW| <= |Z| |W|.  Applying the definition we get

	|C| = Sqrt( maximum eigenvalue of (A'A)^(-1) )
	    = 1 / Sqrt( minimum eigenvalue of A'A )

First order perturbations to the linear equation Ax = b must satisfy:

	A(dx) + (dA)x = db      (i.e. we drop the term (dA).(dx) )
or
	A(dx) = db - (dA)x	
or
	dx = C ( db - (dA)x )

Thus	|dx| / |x| <= |C| ( |db|/|x| + |dA| )
	           <= |C| |A| [ |db|/(|A| |x|) + |dA|/|A| ]

However since b = Ax we have |b| <= |A| |x|.  Substitution then gives

	|dx| / |x| <= |C| |A| ( |db|/|b| + |dA|/|A| )

The condition number is |C| |A| = |(A'A)^(-1)A| |A| which is the
square root of the ratio of the largest and smallest eigenvalues of
A'A.

This argument is not quite as useful for a formal analysis of
precision loss as as Dodson's, since it applies to first order
differentials rather than finite differences.  I find it somewhat
"simpler", to understand, however.
--
T. Scott Thompson              email:  thompson@atlas.socsci.umn.edu
Department of Economics        phone:  (612) 625-0119
University of Minnesota        fax:    (612) 624-0209