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$

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.