1.3 Perturbation Theories for Linear Systems and Eigenvalues

A computer (approximate) solution will not satisfy (1.1) exactly so it is of interest to examine the perturbation theory.

Theorem 1.3.5. Let Ax = b and ( A + ? A)( x + ? x)= b + ? b. If A ^?1 ? A < 1 , then

(1.22)

The proof of this result is easy once one notes that

Here for our application to iterative solution, ? A is not a major concern but ? b will be reflected in the usual stopping criterion based on residuals. Clearly the condition number ?( A) will be crucial in determining the final solution accuracy as computer arithmetic has a finite machine precision.

Eigenvalue perturbation. We give a brief result on eigenvalues simply for comparison and completeness [218].

Theorem 1.3.6. (Bauer Fike). Let A, X ? ^{n n} and X be nonsingular. For D = diag( ? _i ) with ?i = ? _i ( A) , let . be one of these norms: 1, 2 or ?, such that . If B = A + ? A is a perturbed matrix of A and X ^?1 AX = D, then all eigenvalues of B are inside the union of n discs where the discs are defined by

General case : 1,...