Monday, March 27, 2023
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.

References

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

RELATED ARTICLES