Numerical Analysis/Iterative Refinement

What is Iterative Refinement?

edit

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   to linear system   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,  , has been made, with either rounded-Gaussian elimination or otherwise, complete the following steps:

  1. Compute residual:  

  2. Solve  

  3. Update  

Continue to update step one with the newly calculated   until a desired tolerance has been reached.

Approximating the Condition Number

edit

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

 

where r is the residual vector for the approximation  

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   and  . The approximate solution,   satisfies

 

so   is an estimate of the error for approximate solution   Observe that

 

This approximates the condition number associated with solving   and can be re-written and expressed as seen here:

 



Example

edit

Consider the following ill-conditioned linear system

 

Part 1

edit

Solve using Gaussian elimination and iterative refinement (and using two-digit rounding arithmetic). Continue using iterative refinement until   is found. Compare with the true solution.

Part 2

edit

Estimate the condition number   in Part 1 using the method discussed above, and compare this with the condition number calculated using norms.

Quiz

edit

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?

 
 
 
 

3

If you calculate another step of iterative refinement on Example 1, what will be the new approximation,    ?
 

 

4

A linear system is given by

    =   with   =   and   =  

Based on this info, what is the condition number using the approximation and the typical norms-multiplication method?
Using Approximation  

Using Norms  


References

edit

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