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

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 ‖ \infty < 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 _{2}n\kappa _{\infty }({\boldsymbol {A}})\varepsilon _{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 of $ε 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$ .

Notes

↑ 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.

Numerical linear algebra

Key concepts	Floating point Numerical stability

Problems	Matrix multiplication (algorithms) Matrix decompositions Linear equations Sparse problems

Hardware	CPU cache TLB Cache-oblivious algorithm SIMD Multiprocessing

Software	BLAS Specialized libraries General purpose software

This article is issued from Wikipedia - version of the 5/12/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.