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 Ax = b, due to the presence of rounding errors, the computed solution x̂ may sometimes deviate from the exact solution x^*. Starting with x₁ = x̂, iterative refinement computes a sequence {x₁,x₂,x₃,…} which converges to x^* when certain assumptions are met.

Description

For m = 1,2,…, the $m$th iteration of iterative refinement consists of three steps:

1. Compute the residual
   r_m = b − Ax_m
2. Solve the system
   Ad_m = r_m
3. Add the correction
   x_m+1 = x_m + d_m

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 r, e.g. by using quad or double extended precision IEEE 754 floating point, and if A is not too ill-conditioned (and the iteration and the rate of convergence are determined by the condition number of A).^[1]

More formally, assuming that each solve step is reasonably accurate, i.e., in mathematical terms, for every m, we have

A(I + F_m)d_m = r_m

where ‖F_m‖_∞ < 1, the relative error in the $m$th iterate of iterative refinement satisfies

$\frac{\lVert\boldsymbol{x}_m-\boldsymbol{x}^\ast\rVert_\infty}{\lVert\boldsymbol{x}^\ast\rVert_\infty}\leq\bigl(\sigma\kappa_\infty(\boldsymbol{A})\varepsilon_1\bigr)^m+\mu_1\varepsilon_1+\mu_2n\kappa_\infty(\boldsymbol{A})\varepsilon_2$

where

• ‖·‖_∞ denotes the ∞-norm of a vector,
• κ_∞(A) is the ∞-condition number of A,
• $n$ is the order of A,
• ε₁ and ε₂ are unit round-offs of floating-point arithmetic operations,
• σ, μ₁ and μ₂ are constants depending on A, ε₁ and ε₂

if A is “not too badly conditioned”, which in this context means

0 < σκ_∞(A)ε₁ ≪ 1

and implies that μ₁ and μ₂ are of order unity.

The distinction of ε₁ and ε₂ is intended to allow mixed-precision evaluation of r_m 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 ε₁.

Notes

1. Higham, Nicholas (2002). Accuracy and Stability of Numerical Algorithms (2 ed). SIAM. p. 232.

References

• Wilkinson, James H. (1963). Rounding Errors in Algebraic Processes. Englewood Cliffs, NJ: Prentice Hall.
• Moler, Cleve B. (April 1967). "Iterative Refinement in Floating Point". Journal of the ACM (New York, NY: Association for Computing Machinery) 14 (2): 316–321. doi:10.1145/321386.321394.