Iterative refinement

For broader coverage of this topic, see Iterative method.

This article is about iterative refinement in mathematics. For iterative refinement in software development, see Iterative and incremental development.

Iterative refinement is an iterative method proposed by James H. Wilkinson to improve the accuracy of numerical solutions to systems of linear equations. ^{[1] [2]}

When solving a linear system ${\displaystyle A\mathbf {x} =\mathbf {b} \,,}$ due to the compounded accumulation of rounding errors, the computed solution ${\displaystyle {\hat {\mathbf {x} }}}$ may sometimes deviate from the exact solution ${\displaystyle \mathbf {x} _{\star }\,.}$ Starting with ${\displaystyle \mathbf {x} _{1}={\hat {\mathbf {x} }}\,,}$ iterative refinement computes a sequence ${\displaystyle \{\mathbf {x} _{1},\,\mathbf {x} _{2},\,\mathbf {x} _{3},\dots \}}$ which converges to ${\displaystyle \mathbf {x} _{\star }\,,}$ when certain assumptions are met.

Description

For ${\displaystyle m=1,2,3,\dots \,,}$ the mth iteration of iterative refinement consists of three steps:

1. Compute the residual error r_m
   $${\displaystyle \mathbf {r} _{m}=\mathbf {b} -A\mathbf {x} _{m}\,.}$$
2. Solve the system for the correction, c_m, that removes the residual error
   $${\displaystyle A\mathbf {c} _{m}=\mathbf {r} _{m}\,.}$$
3. Add the correction to get the revised next solution x_m+1
   $${\displaystyle \mathbf {x} _{m+1}=\mathbf {x} _{m}+\mathbf {c} _{m}\,.}$$

The crucial reasoning for the refinement algorithm is that although the solution for c_m in step (ii) may indeed be troubled by similar errors as the first solution, ${\displaystyle {\hat {\mathbf {x} }}}$, the calculation of the residual r_m 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 (b). 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, x_m, closer to the desired one, ${\displaystyle \mathbf {x} _{\star }\,.}$

The iterations will stop on their own when the residual r_m is zero, or close enough to zero that the corresponding correction c_m is too small to change the solution x_m which produced it; alternatively, the algorithm stops when r_m is too small to convince the linear algebraist monitoring the progress that it is worth continuing with any further refinements.

Note that the matrix equation solved in step (ii) uses the same matrix ${\displaystyle A}$ for each iteration. If the matrix equation is solved using a direct method, such as Cholesky or LU decomposition, the numerically expensive factorization of ${\displaystyle A}$ is done once and is reused for the relatively inexpensive forward and back substitution to solve for c_m at each iteration. ^[2]

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). ^[3]

More formally, assuming that each step (ii) can be solved reasonably accurately, i.e., in mathematical terms, for every m, we have

$${\displaystyle A\left(I+F_{m}\right)\mathbf {c} _{m}=\mathbf {r} _{m}}$$

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

$${\displaystyle {\frac {\lVert \mathbf {x} _{m}-\mathbf {x} _{\star }\rVert _{\infty }}{\lVert \mathbf {x} _{\star }\rVert _{\infty }}}\leq {\bigl (}\sigma \,\kappa (A)\,\varepsilon _{1}{\bigr )}^{m}+\mu _{1}\,\varepsilon _{1}+n\,\kappa (A)\,\mu _{2}\,\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 that depend 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 ε₁.

References

1. Wilkinson, James H. (1963). Rounding Errors in Algebraic Processes . Englewood Cliffs, NJ: Prentice Hall.
2. 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 .
3. Higham, Nicholas (2002). Accuracy and Stability of Numerical Algorithms (2 ed.). SIAM. p. 232.