#### 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.