
Iterative refinement

Iterative refinement is an iterative method proposed by James H. Wilkinson to improve the accuracy of numerical solutions to systems of linear equations.
When solving a linear system formula_1 due to the compounded accumulation of rounding errors, the computed solution formula_2 may sometimes deviate from the exact solution formula_3 Starting with formula_4 iterative refinement computes a sequence formula_5 which converges to formula_6 when certain assumptions are met.
Description.
For formula_7 the th iteration of iterative refinement consists of three steps:
The crucial reasoning for the refinement algorithm is that although the solution for in step (ii) may indeed be troubled by similar errors as the first solution, formula_8, the calculation of the residual in step (i), in comparison, is numerically nearly exact: You may not know the right answer very well, but you know quite accurately just how far the solution you have in hand is from producing the correct outcome (). If the residual is small in some sense, then the correction must also be small, and should at the very least steer the current estimate of the answer, , closer to the desired one, formula_3
The iterations will stop on their own when the residual is zero, or close enough to zero that the corresponding correction is too small to change the solution which produced it; alternatively, the algorithm stops when is too small to convince the linear algebraist monitoring the progress that it is worth continuing with any further refinements.
Error analysis.
As a rule of thumb, iterative refinement for Gaussian elimination produces a solution correct to working precision if double the working precision is used in the computation of , e.g. by using quad or double extended precision IEEE 754 floating point, and if is not too ill-conditioned (and the iteration and the rate of convergence are determined by the condition number of ).
More formally, assuming that each step (ii) can be solved reasonably accurately, i.e., in mathematical terms, for every , we have
where , the relative error in the th iterate of iterative refinement satisfies
where
if is "not too badly conditioned", which in this context means
and implies that and are of order unity.
The distinction of and is intended to allow mixed-precision evaluation of where intermediate results are computed with unit round-off before the final result is rounded (or truncated) with unit round-off . All other computations are assumed to be carried out with unit round-off .