# 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 ${\widehat {x}}$  to linear system $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, ${\widehat {x}}_{1}$ , has been made, with either rounded-Gaussian elimination or otherwise, complete the following steps:

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

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

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

Continue to update step one with the newly calculated ${\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

${\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 ${\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 $A,y,$  and ${\widehat {x}}$ . The approximate solution, ${\widehat {y}}$  satisfies

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

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

{\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 $Ax=b$  and can be re-written and expressed as seen here:

 $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

{\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 ${\widehat {x}}_{4}$  is found. Compare with the true solution.

### Part 2

Estimate the condition number $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?

 ${\begin{bmatrix}1&2\\1.0001&2\end{bmatrix}}$ ${\begin{bmatrix}1&2\\10,001&2\end{bmatrix}}$ ${\begin{bmatrix}1&2\\10,001&20,002\end{bmatrix}}$ ${\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, ${\widehat {x}}_{5}={\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}$ ? $\displaystyle \ x_{1}=$ $\displaystyle \ x_{2}=$ 4

 A linear system is given by ${\begin{bmatrix}3.3330&15920&-10.333\\2.2220&16.710&9.6120\\1.5611&5.1791&1.6852\end{bmatrix}}$ ${\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\end{bmatrix}}$ = ${\begin{bmatrix}15913\\28.544\\8.4254\end{bmatrix}},$ with ${\widehat {x}}_{1}$ = ${\begin{bmatrix}1.2001\\0.99991\\0.92538\end{bmatrix}},$ and $y_{1}$ = ${\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 \ K(A)=$ Using Norms $\displaystyle \ K(A)=$ 