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 :