#### CS3414 Afterclass Notes --- 24 June, 2002

**Linear Systems (Chapter 6)**
- Error analysis for Ax=b

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

- 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
^{2})) ways to get good estimates for the norm
of A^{-1}.

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