Skip to main content

Subsection 5.3.7 Improving accuracy via iterative refinement

When solving \(A x = b \) on a computer, error is inherently incurred. Instead of the exact solution \(x \text{,}\) an approximate solution \(\hat x \) is computed, which instead solves \(A \hat x = \hat b \text{.}\) The difference between \(x \) and \(\hat x \) satisfies

\begin{equation*} A ( x - \hat x ) = b - \hat b . \end{equation*}

We can compute \(\hat b = A \hat x \) and hence we can compute \(\delta\!b = b - \hat b \text{.}\) We can then solve \(A \delta\!x = \delta\!b \text{.}\) If this computation is completed without error, then \(x = \hat x + \delta\!x \) and we are left with the exact solution. Obviously, there is error in \(\delta\!x \) as well, and hence we have merely computed an improved approximate solution to \(A x = b \text{.}\) This process can be repeated. As long as solving with \(A\) yields at least one digit of accuracy, this process can be used to improve the computed result, limited by the accuracy in the right-hand side \(b \) and the condition number of \(A \text{.}\)

This process is known as iterative refinement.