Friday, March 29, 2024
HomeMatlabWhat Is Iterative Refinement? – Nick Higham

What Is Iterative Refinement? – Nick Higham


Iterative refinement is a technique for enhancing the standard of an approximate answer widehat{x} to a linear system of equations Ax = b, the place A is an ntimes n nonsingular matrix. The fundamental iterative refinement algorithm could be very easy.

  1. Compute the residual r = b - Awidehat{x}.
  2. Resolve Ad = r.
  3. Replace widehat{x} gets widehat{x} + d.
  4. Repeat from step 1 if mandatory.

At first sight, this algorithm appears as costly as fixing for the unique widehat{x}. Nonetheless, often the solver is LU factorization with pivoting, A = LU (the place we embody the permutations in L). A lot of the work is within the LU factorization, which prices O(n^3) flops, and every iteration requires a multiplication with A for the residual and two substitutions to compute d, which whole solely O(n^2) flops. If the refinement converges rapidly then it’s cheap.

Turning to the error, with a steady LU factorization the preliminary widehat{x} computed in floating-point arithmetic of precision u satisfies (omitting constants)

notag     displaystylefrac{|x- widehat{x}|}xlesssim kappa_{infty}(A) u, qquad (1)

the place kappa_{infty}(A) = |A|_{infty} |A^{-1}|_{infty} ge 1 is the matrix situation quantity within the infty-norm. We wish refinement to provide an answer correct to precision u:

notag     displaystylefrac{|x- widehat{x}|}xapprox u. qquad (2)

But when the solver can not compute the preliminary widehat{x} precisely when A is ill-conditioned why ought to it be capable to produce an replace d that improves widehat{x}?

The only reply is that when iterative refinement was first used on digital computer systems the residual r was computed at twice the working precision, which may very well be completed at no further price within the {hardware}. If widehat{x} is an affordable approximation then we anticipate cancellation in forming r = b - Awidehat{x}, so utilizing further precision in forming r ensures that r has sufficient appropriate digits to yield a correction d that improves widehat{x}. This type of iterative refinement produces an answer satisfying (2) so long as kappa_{infty}(A) < u^{-1}.

Here’s a MATLAB instance, the place the working precision is single and residuals are computed in double precision.

n = 8; A = single(gallery('frank',n)); xact = ones(n,1);
b = A*xact; % b is shaped precisely for small n.
x = Ab;
fprintf('Initial_error = %4.1en', norm(x - xact,inf))
r = single( double(b) - double(A)*double(x) );
d = Ar;
x = x + d;
fprintf('Second error  = %4.1en', norm(x - xact,inf))

The output is

Initial_error = 9.1e-04
Second error  = 6.0e-08

which exhibits that after only one step the error has been introduced down from 10^{-4} to the extent of u_sapprox 5times 10^{-8}, the unit roundoff for IEEE single precision arithmetic.

Fastened Precision Iterative Refinement

By the Nineteen Seventies, computer systems had began to lose the power to cheaply accumulate inside merchandise in further precision, and additional precision couldn’t be programmed portably in software program. It was found, although, that even when iterative refinement is run totally in a single precision it could convey advantages when kappa_{infty}(A) < u^{-1}. Particularly,

  • if the solver is considerably numerically unstable the instability is cured by the refinement, in {that a} relative residual satisfying

    notag     displaystylefrac{|b-Awidehat{x}|_{infty}}{|A|_{infty} |widehat{x}|_{infty} + |b|_{infty}} approx u qquad(3)

    is produced, and

  • a relative error satisfying

    notag     displaystylefrac{|x- widehat{x}|_{infty}}{|x|_{infty}}      lesssim mathrm{cond}(A,x) u   qquad (4)

    is produced, the place

notag    mathrm{cond}(A,x) = displaystylefrac{ |, |A^{-1}| |A| |x| ,|_{infty} } {|x|_{infty}}.

The sure (4) is stronger than (1) as a result of mathrm{cond}(A,x) is not any bigger than kappa_{infty}(A) and might be a lot smaller, particularly if A has badly scaled rows.

Low Precision Factorization

References

We give 5 references, which include hyperlinks to the sooner literature.

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments