<div class="gmail_quote">On Sun, Jul 17, 2011 at 21:23, Mark F. Adams <span dir="ltr"><<a href="mailto:mark.adams@columbia.edu">mark.adams@columbia.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div id=":3s3">Humm, the only linear algebra proof that I know gives bounds on the error of the form<br>
<br>
 | error |_2 <= Condition-number * | residual |_2,<br></div></blockquote><div><br></div><div>This looks like relative error.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div id=":3s3">
<br>
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 ...<br></div></blockquote></div><br><div>Suppose you have</div><div><br></div><div>
| A x - b | < c</div><div><br></div><div>Then there is some y such that</div><div><br></div><div>A (x + y) - b = 0</div><div><br></div><div>and for which</div><div><br></div><div>|A y| < c</div><div><br></div><div>Suppose s is the smallest singular value of A, thus 1/s is the largest singular value of A^{-1}. Then</div>
<div><br></div><div>|y| = | A^{-1} A y | <= (1/s) |A y| < c/s.</div><div><br></div><div>So you can bound the absolute error in the solution if you know the residual and the smallest singular value.</div>