Numerical Analysis/Iterative Refinement

From Wikiversity
Jump to navigation Jump to search

What is Iterative Refinement?[edit | edit source]

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 | edit source]

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 | edit source]

Consider the following ill-conditioned linear system

Part 1[edit | edit source]

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 | edit source]

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

Quiz[edit | edit source]

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


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


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


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 | edit source]

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