From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci)
Subject: Re: Help with inverting singular matrix
Date: 12 Mar 1999 17:02:35 GMT
Newsgroups: sci.math.num-analysis
To: BPA<ZZZelp95bpa@sheffield.ac.uk>
Keywords: regularization and ill-conditioned matrices

In article <7cbcpe$7am$1@bignews.shef.ac.uk>,
 BPA<elp95bpa@sheffield.ac.uk> writes:
|> 
|> ** Note: If replying by e-mail please remove the prepended 'ZZZ' from my
|>    e-mail address **
|> 
|> 
|> Hi, I've got a very ill-conditioned matrix that I'd like to invert.  SVD
|> doesn't do very well on it. I've read that there are other methods of solving
|> the problem including regularization. Unfortunately I'm not an expert on
|> regularization, so could anyone kindly advice me on the techniques available
|> and how it may affect the solution? If you know of any book or web references
|> I'd be glad to hear about it. Thanks very much. 
|> 
First question: why you want to do that? As a rule of thumb, you also never need
the inverse of a matrix explicitly, rather a solver for 
an equation in which it appears. (this would change the situation).
the SVD itself is such a regularization if you cut off small singular values
and define the pseudoinverse of
   A = U S V' 
by 
    #      #
   A  = V S  U'

    #
   S_i   =   { 1/S_i if S_i > alpha >0 | 0 otherwise }
for some useful alpha. e.g. if you know that your matrix entries have an 
possible error or uncertainty of eps, you may use alpha=eps.
Of course the solution coefficients are affected very strongly by this,
but what one searches normally is a reasonable x such that Ax-b is small.
What "reasonable" means depends very much on the problem. e.g. in solving
an integral equation you might want some discrete analog of some
sobolev norm of x being small. this would result in changing A
to A+alpha*\sum B_jB_j', where B_j' are Difference matrices reflecting the
approximation of the zero-th , first, second and so on derivative.
you may also use an iterative solver as a regularization tool
(e.g. Kaczmarcs method, cg with proper termination ...). there is 
much literature in this field and the correct way to proceed depends very
much on the special problem behind your system. 
some typical papers are:


887.47013
Groetsch, Charles W.; Hanke, Martin
A general framework for regularized evaluation of unstable operators. (English)
[J] J. Math. Anal. Appl. 203, No.2, 451-463, Art. No.0390 (1996). 
[ISSN 0022-247X ] http://www.europe.idealibrary.com

859.65051
Hanke, Martin; Raus, Toomas
A general heuristic for choosing the regularization parameter in ill-posed 
problems. (English)
[J] SIAM J. Sci. Comput. 17, No.4, 956-972 (1996). [ISSN 1064-8275]

Engl, Heinz W.; Hanke, Martin; Neubauer, Andreas
Regularization of inverse problems. (English)
[B] Mathematics and its Applications (Dordrecht). 375. Dordrecht: 
Kluwer Academic Publishers. viii, 321 p. Dfl. 245.00; \$ 160.00;
\sterling 108.00 (1996). [ISBN 0-7923-4157-0; ISSN 0921-3791]

Hanke, Martin
The minimal error conjugate gradient method is a regularization method. (English)
[J] Proc. Am. Math. Soc. 123, No.11, 3487-3497 (1995). [ISSN 0002-9939]
830.65043

Hanke, Martin
Conjugate gradient type methods for ill-posed problems. (English)
[B] Pitman Research Notes in Mathematics Series. 327. 
Harlow: Longman Scientific \& Technical. 134 p. (1995). [ISBN
0-582-27370-6]

if you would make a library search with the subject "ill-posed" or
"regularization" hell would come up. 
hope this helps
peter