# Numerical Analysis/Iterative Refinement

## What is Iterative Refinement?

A detailed discussion of iterative refinement can be found on the Wikipedia page.

To give a brief description, it is a technique used to improve the approximate solution ${\displaystyle {\widehat {x}}}$ to linear system ${\displaystyle Ax=b.}$ This technique is generally only used on systems that are thought or determined to be ill-conditioned.

The process involves three primary steps:

Iterative Refinement Process

Once an approximation to the solution, ${\displaystyle {\widehat {x}}_{1}}$, has been made, with either rounded-Gaussian elimination or otherwise, complete the following steps:

1. Compute residual: ${\displaystyle r_{i}=b-A{\widehat {x}}_{i}}$

2. Solve ${\displaystyle Ay_{i}=r_{i}}$

3. Update ${\displaystyle {\widehat {x}}_{i+1}={\widehat {x}}_{i}+y_{i}}$

Continue to update step one with the newly calculated ${\displaystyle {\widehat {x}}_{i+1}}$ until a desired tolerance has been reached.

## Approximating the Condition Number

In theory, the condition number of a matrix depends on the norms of the matrix and its inverse. In practice, however, calculating the inverse is subject to round-off error and the accuracy of the calculations.

If these calculations involve arithmetic with t digits of accuracy, then the approximate condition number for the matrix - call it A - is the norm of A the norm of the approximation of the inverse of A.

Assuming that the approximate solution to the linear system is being determined with t-digit arithmetic and Gaussian elimination, we can show

${\displaystyle {\begin{Vmatrix}r\end{Vmatrix}}\approx 10^{-t}{\begin{Vmatrix}A\end{Vmatrix}}{\begin{Vmatrix}{\widehat {x}}\end{Vmatrix}},}$

where r is the residual vector for the approximation ${\displaystyle {\widehat {x}}.}$

This approximation for the condition number can be obtained without having to invert matrix A.

When doing iterative refinement problems, we will have, or will calculate the values for ${\displaystyle A,y,}$ and ${\displaystyle {\widehat {x}}}$. The approximate solution, ${\displaystyle {\widehat {y}}}$ satisfies

${\displaystyle {\widehat {y}}\approx A^{-1}r=A^{-1}(b-A{\widehat {x}})=A^{-1}b-A^{-1}A{\widehat {x}}=x-{\widehat {x}},}$

so ${\displaystyle {\widehat {y}}}$ is an estimate of the error for approximate solution ${\displaystyle {\widehat {x}}.}$ Observe that

{\displaystyle {\begin{aligned}{\begin{Vmatrix}{\widehat {y}}\end{Vmatrix}}\approx {\begin{Vmatrix}x-{\widehat {x}}\end{Vmatrix}}&={\begin{Vmatrix}A^{-1}r\end{Vmatrix}}\leq {\begin{Vmatrix}A^{-1}\end{Vmatrix}}{\begin{Vmatrix}r\end{Vmatrix}}\approx {\begin{Vmatrix}A^{-1}\end{Vmatrix}}(10^{-t}{\begin{Vmatrix}A\end{Vmatrix}}{\begin{Vmatrix}{\widehat {x}}\end{Vmatrix}})\\&=10^{-t}{\begin{Vmatrix}{\widehat {x}}\end{Vmatrix}}K(A).\end{aligned}}}

This approximates the condition number associated with solving ${\displaystyle Ax=b}$ and can be re-written and expressed as seen here:

 ${\displaystyle K(A)\approx {\frac {\begin{Vmatrix}{\widehat {y}}\end{Vmatrix}}{\begin{Vmatrix}{\widehat {x}}\end{Vmatrix}}}10^{t}.}$

## Example

Consider the following ill-conditioned linear system

{\displaystyle {\begin{aligned}3.9x_{1}+1.6x_{2}&=5.5\\6.8x_{1}+2.9x_{2}&=9.7\end{aligned}}}

### Part 1

Solve using Gaussian elimination and iterative refinement (and using two-digit rounding arithmetic). Continue using iterative refinement until ${\displaystyle {\widehat {x}}_{4}}$ is found. Compare with the true solution.

### Part 2

Estimate the condition number ${\displaystyle K(A)}$ in Part 1 using the method discussed above, and compare this with the condition number calculated using norms.

## Quiz

1

Not only does iterative refinement improve ill-conditioned matrices, it is also very help in improving well-conditioned matrices.

 TRUE FALSE

2

Which of the following matrices might benefit from using iterative refinement?

 ${\displaystyle {\begin{bmatrix}1&2\\1.0001&2\end{bmatrix}}}$ ${\displaystyle {\begin{bmatrix}1&2\\10,001&2\end{bmatrix}}}$ ${\displaystyle {\begin{bmatrix}1&2\\10,001&20,002\end{bmatrix}}}$ ${\displaystyle {\begin{bmatrix}1&20,002\\10,001&2\end{bmatrix}}}$

3

 If you calculate another step of iterative refinement on Example 1, what will be the new approximation, ${\displaystyle {\widehat {x}}_{5}={\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}}$ ? ${\displaystyle \displaystyle \ x_{1}=}$ ${\displaystyle \displaystyle \ x_{2}=}$

4

 A linear system is given by ${\displaystyle {\begin{bmatrix}3.3330&15920&-10.333\\2.2220&16.710&9.6120\\1.5611&5.1791&1.6852\end{bmatrix}}}$ ${\displaystyle {\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\end{bmatrix}}}$ = ${\displaystyle {\begin{bmatrix}15913\\28.544\\8.4254\end{bmatrix}},}$ with ${\displaystyle {\widehat {x}}_{1}}$ = ${\displaystyle {\begin{bmatrix}1.2001\\0.99991\\0.92538\end{bmatrix}},}$ and ${\displaystyle y_{1}}$ = ${\displaystyle {\begin{bmatrix}-0.20008\\8.9987\times 10^{-5}\\0.074607\end{bmatrix}}.}$ Based on this info, what is the condition number using the approximation and the typical norms-multiplication method? Using Approximation ${\displaystyle \displaystyle \ K(A)=}$ Using Norms ${\displaystyle \displaystyle \ K(A)=}$

## References

Burden and Faires. Numerical Analysis, 3rd Edition. ISBN 0-87150-857-5