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 1 = x ̂$ , iterative refinement computes a sequence ${x 1, x 2, x 3,\dots$ } which converges to $x *$ when certain assumptions are met.

Description

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

Compute the residual
$r m = b - Ax m$
Solve the system
$Ad m = r m$
Add the correction
$x m +1 = x m + d m$

Error analysis

The relative error in the $m$ th iterate 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

$‖\cdot‖ \infty$ denotes the $\infty$ -norm of a vector,
$κ \infty (A)$ is the $\infty$ condition number of $A$ ,
$n$ is the order of $A$ ,
$ε 1$ and $ε 2$ are unit round-offs of floating-point arithmetic operations,
$σ$ , $μ 1$ and $μ 2$ are constants depending on $A$ , $ε 1$ and $ε 2$

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

0 < σκ \infty (A) ε 1 ≪ 1

and implies that $μ 1$ and $μ 2$ are of order unity.

The distinction between $ε 1$ and $ε 2$ is intended to allow mixed-precision evaluation of $r m$ where intermediate results are computed with unit round-off $ε 2$ before the final result is rounded (or truncated) with unit round-off $ε 1$ . All other computations are assumed to be carried out with unit round-off $ε 1$ .

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)

This computer science article is a stub. You can help Wikipedia by expanding it.