Iterative Refinement

Iterative Methods for Linear Algebraic Systems We consider linear, one step, stationary schemes:

We choose and such that an exact solution satisfies

We call the iteration matrix. We want the method to converge for any starting value of . So we want for any So we want for any So we want .

Iterative refinement

By writing

we see that immediately solves the equation. So we want to find which approximates . This will give an iteration matrix .

Splitting

Take now:

with the iteration matrix So we want to approximate with .

Jacobi Method Gauss-Seidel Method The Householder-John Theorem

Relaxation

Suppose we have some that converges but we want to converge faster Define We want to find which minimizes In general, this is unknown, but suppose we know is real and in the interval Then we can figure out optimal by “centering” the spectrum around :