CS3414 Afterclass Notes --- 24 June, 2002

Linear Systems (Chapter 6)
  1. 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 10k, then you should not be surprised to lose k decimal digits of accuracy in solving Ax=b.

        • Fortunately, there are relatively inexpensive (O(n2)) 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.