Iterative refinement: Difference between revisions
Bluelink 1 book for verifiability.) #IABot (v2.0) (GreenC bot |
laid out formulas in table; math typesetting; inserted discussion below algorithm |
||
Line 1: | Line 1: | ||
{{about|iterative refinement in mathematics|iterative refinement in software development|Iterative and incremental development}} |
{{about|iterative refinement in mathematics|iterative refinement in software development|Iterative and incremental development}} |
||
{{use dmy dates}} |
|||
'''Iterative refinement''' is an [[iterative method]] proposed by James H. Wilkinson to improve the accuracy of numerical solutions to [[systems of linear equations]]. |
|||
'''Iterative refinement''' is an [[iterative method]] proposed by James H. Wilkinson to improve the accuracy of numerical solutions to [[systems of linear equations]].<ref name=Wilkinson1963>{{cite book |first=James H. |last=Wilkinson |year=1963 |title=Rounding Errors in Algebraic Processes |publisher=[[Prentice Hall]] |place=Englewood Cliffs, NJ |url=https://archive.org/details/roundingerrorsin0000wilk |url-access=registration}}</ref><ref name=Moler1967>{{cite journal |first=Cleve B. |last=Moler |date=April 1967 |title=Iterative refinement in floating point |journal=[[Journal of the ACM]] |volume=14 |issue=2 |pages=316–321 |url=http://portal.acm.org/citation.cfm?id=321394 |doi=10.1145/321386.321394 |publisher=[[Association for Computing Machinery]] |place=New York, NY}}</ref> |
|||
When solving a linear system |
When solving a linear system <math>\,\mathrm{A} \, \mathbf{x} = \mathbf{b} \,,</math> due to the compounded accumulation of [[Round-off error|rounding error]]s, the computed solution <math>\hat{\mathbf{x}}</math> may sometimes deviate from the exact solution <math>\mathbf{x}_\star\,.</math> Starting with <math>\mathbf{x}_1 = \hat{\mathbf{x}}\,,</math> iterative refinement computes a sequence <math>\{\,\mathbf{x}_1,\,\mathbf{x}_2,\,\mathbf{x}_3,\,...\}</math> which converges to <math>\mathbf{x}_\star\,,</math> when certain assumptions are met. |
||
==Description== |
==Description== |
||
For |
For <math>m = 1, 2, 3, ...\,,</math> the {{mvar|m}}th iteration of iterative refinement consists of three steps: |
||
:{| |
|||
# Compute the residual<br>{{math|'''<var>r</var>'''<sub><var>m</var></sub> {{=}} '''<var>b</var>''' − '''<var>Ax</var>'''<sub><var>m</var></sub>}} |
|||
|- |
|||
# Solve the system<br>{{math|'''<var>Ad</var>'''<sub><var>m</var></sub> {{=}} '''<var>r</var>'''<sub><var>m</var></sub>}} |
|||
| style="text-align:center;"| (i) <br/> |
|||
# Add the correction<br>{{math|'''<var>x</var>'''<sub><var>m</var>+1</sub> {{=}} '''<var>x</var>'''<sub><var>m</var></sub> + '''<var>d</var>'''<sub><var>m</var></sub>}} |
|||
| Compute the residual<br/>error {{math|'''r'''{{sub|''m''}}}} |
|||
| <math>\mathbf{r}_m = \mathbf{b} - \mathrm{A} \mathbf{x}_m\,.</math> <br/> |
|||
|- |
|||
| style="text-align:center;"| (ii) <br/> |
|||
| Solve the system for the correction,<br/>{{math|'''c'''{{sub|''m''}}}},that removes the residual error |
|||
| <math>\mathrm{A}\,\mathbf{c}_m = \mathbf{r}_m\,.</math> <br/> |
|||
|- |
|||
| style="text-align:center;"| (iii) <br/> |
|||
| Add the correction to get the<br/>revised next solution {{math|'''x'''{{sub|''m''+1}}}} |
|||
| <math>\mathbf{x}_{m+1} = \mathbf{x}_m + \mathbf{c}_m\,.</math> <br/> |
|||
|} |
|||
The crucial reasoning for the refinement algorithm is that although the solution for {{math|'''c'''{{sub|''m''}}}} in step (ii) may indeed be troubled by similar errors as the first solution, <math>\hat\mathbf{x}</math>, the calculation of the residual {{math|'''r'''{{sub|''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 ({{math|'''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, {{math|'''x'''{{sub|''m''}}}}, closer the the desired one, <math>\mathbf{x}_\star\,.</math> |
|||
The iterations will stop on their own, when the residual {{math|'''r'''{{sub|''m''}}}} is zero, or close enough to zero that the correction {{math|'''c'''{{sub|''m''}}}} is too small to change the solution {{math|'''x'''{{sub|''m''}}}} which produced it; alternatively, the algorithm stops when {{math|'''c'''{{sub|''m''}}}} is too small to convince the linear algebraist monitoring the refinement that it is worth continuing with any further refinements. |
|||
==Error analysis== |
==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 {{math| |
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 {{math|'''r'''}}, e.g. by using [[Quadruple-precision floating-point format|quad]] or [[extended precision|double extended]] precision [[IEEE 754]] [[floating point]], and if {{math|A}} is not too ill-conditioned (and the iteration and the rate of convergence are determined by the condition number of {{math|A}}).<ref>{{cite book |first=Nicholas |last=Higham |title=Accuracy and Stability of Numerical Algorithms |edition=2 |publisher=SIAM |year=2002 |pages=232}}</ref> |
||
More formally, assuming that each |
More formally, assuming that each step (ii) can be solved reasonably accurately, i.e., in mathematical terms, for every {{mvar|m}}, we have |
||
:<math>\mathrm{A}\,\left( \mathrm{ I + F}_m \right)\mathbf{c}_m = \mathbf{r}_m</math> |
|||
:{{math|'''<var>A</var>'''('''<var>I</var>''' + <var>'''F'''<sub>m</sub></var>)<var>'''d'''<sub>m</sub></var> {{=}} <var>'''r'''<sub>m</sub></var>}} |
|||
where {{math| |
where {{math|‖F{{sub|''m''}}‖{{sub|∞}} < 1}}, the [[Approximation error|relative error]] in the {{mvar|m}}th iterate of iterative refinement satisfies |
||
:<math>\frac{\lVert\ |
:<math>\frac{ \lVert \mathbf{x}_m - \mathbf{x}_\star \rVert_\infty }{ \lVert \mathbf{x}_\star \rVert_\infty} \leq \bigl( \sigma\,\kappa(\mathrm{A})\,\varepsilon_1\bigr)^m + \mu_1\, \varepsilon_1 + n\, \kappa(\mathrm{A})\, \mu_2\, \varepsilon_2</math> |
||
where |
where |
||
* {{math|‖·‖<sub>∞</sub>}} denotes the [[Uniform norm|{{math|∞}}-norm]] of a vector, |
* {{math|‖·‖<sub>∞</sub>}} denotes the [[Uniform norm|{{math|∞}}-norm]] of a vector, |
||
* {{math| |
* {{math|''κ''(A)}} is the {{math|∞}}-[[condition number]] of {{math|A}}, |
||
* |
* {{mvar|n}} is the order of {{math|A}}, |
||
* {{ |
* {{mvar|ε}}{{sub|1}} and {{mvar|ε}}{{sub|2}} are [[Machine epsilon|unit round-offs]] of [[Floating point|floating-point]] arithmetic operations, |
||
* {{ |
* {{mvar|σ}}, {{mvar|μ}}{{sub|1}} and {{mvar|μ}}{{sub|2}} are constants that depend on {{math|A}}, {{mvar|ε}}{{sub|1}} and {{mvar|ε}}{{sub|2}} |
||
if {{math| |
if {{math|A}} is "not too badly conditioned", which in this context means |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | The distinction of {{ |
||
⚫ | The distinction of {{mvar|ε}}{{sub|1}} and {{mvar|ε}}{{sub|2}} is intended to allow mixed-precision evaluation of {{math|'''r'''{{sub|''m''}} }} where intermediate results are computed with unit round-off {{mvar|ε}}{{sub|2}} before the final result is rounded (or truncated) with unit round-off {{mvar|ε}}{{sub|1}}. All other computations are assumed to be carried out with unit round-off {{mvar|ε}}{{sub|1}}. |
||
==Notes== |
|||
{{Reflist}} |
|||
==References== |
==References== |
||
{{reflist|25em}} |
|||
*{{cite book|title=Rounding Errors in Algebraic Processes|url=https://archive.org/details/roundingerrorsin0000wilk|url-access=registration|first=James H.|last=Wilkinson|publisher=[[Prentice Hall]]|location= Englewood Cliffs, NJ|year=1963}} |
|||
*{{cite journal|title=Iterative Refinement in Floating Point|first=Cleve B.|last=Moler|publisher=[[Association for Computing Machinery]]|location=New York, NY|date=April 1967|journal=[[Journal of the ACM]]|volume=14|issue=2|pages=316–321|url=http://portal.acm.org/citation.cfm?id=321394|doi=10.1145/321386.321394}} |
|||
{{Numerical linear algebra}} |
{{Numerical linear algebra}} |
Revision as of 04:30, 3 July 2020
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 due to the compounded accumulation of rounding errors, the computed solution may sometimes deviate from the exact solution Starting with iterative refinement computes a sequence which converges to when certain assumptions are met.
Description
For the mth iteration of iterative refinement consists of three steps:
(i)
Compute the residual
error rm
(ii)
Solve the system for the correction,
cm,that removes the residual error
(iii)
Add the correction to get the
revised next solution xm+1
The crucial reasoning for the refinement algorithm is that although the solution for cm in step (ii) may indeed be troubled by similar errors as the first solution, , the calculation of the residual rm 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, xm, closer the the desired one,
The iterations will stop on their own, when the residual rm is zero, or close enough to zero that the correction cm is too small to change the solution xm which produced it; alternatively, the algorithm stops when cm is too small to convince the linear algebraist monitoring the refinement that it is worth continuing with any further refinements.
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
where ‖Fm‖∞ < 1, the relative error in the mth iterate of iterative refinement satisfies
where
- ‖·‖∞ denotes the ∞-norm of a vector,
- κ(A) is the ∞-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 that depend on A, ε1 and ε2
if A is "not too badly conditioned", which in this context means
- 0 < σ κ(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 rm 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. (April 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.
- ^ Higham, Nicholas (2002). Accuracy and Stability of Numerical Algorithms (2 ed.). SIAM. p. 232.