On Sun, Jul 17, 2011 at 21:23, Mark F. Adams
<mark.adams@columbia.edu> wrote:
Humm, the only linear algebra proof that I know gives bounds on the error of the form
| error |_2 <= Condition-number * | residual |_2,
This looks like relative error.
for SPD matrices of course. This is pessimistic but I'm not sure how you could get a bound on error with only the lowest eigen value ...
Suppose you have
| A x - b | < c
Then there is some y such that
A (x + y) - b = 0
and for which
|A y| < c
Suppose s is the smallest singular value of A, thus 1/s is the largest singular value of A^{-1}. Then
|y| = | A^{-1} A y | <= (1/s) |A y| < c/s.
So you can bound the absolute error in the solution if you know the residual and the smallest singular value.