CS3414 Afterclass Notes --- 24 June, 2002

3. Error analysis for Ax=b

   1. The residual
      • Def. r = b-Ax^*, where x^* is an approximate solution.
      • Not necessarily a good predictor of error. Example ... See HW5, Problem 1.

   2. Conditioning of Ax=b

      • Theorem: if then
        

      • Remarks:
        • If you replace the perturbation `delta b' in the above result by the residual r, you get a similar result that relates the size of the error to the size of the residual. So a large condition number means that the residual may not be a good estimate of the error.

        • There are other interpretations for cond(A):
          • The cond(A) is a measure of the degree of linear dependence that the columns (or rows) of A have.
          • If cond(A) is about 10^k, then you should not be surprised to lose k decimal digits of accuracy in solving Ax=b.

        • Fortunately, there are relatively inexpensive (O(n²)) ways to get good estimates for the norm of A^-1.

   3. Stability of Gaussian Elimination

      • Can show that G.E. with complete pivoting is stable.

      • Can show that G.E. with partial pivoting may not be stable.

      • But in the overwhelming majority of cases, G.E. with partial pivoting is stable enough.