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

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}})\epsilon _{1}{\bigr )}^{m}+\mu _{1}\epsilon _{1}+\mu _{2}n\kappa _{\infty }({\boldsymbol {A}})\epsilon _{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 ε₁.

References

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