Iterative Refinement

Recovering accuracy lost to rounding by computing a residual, solving for the correction, and adding it back.

Fixing a computed solution

When a linear system is solved by a factorization, rounding error means the computed solution is not exact. Iterative refinement improves it cheaply: compute the residual (how far the computed solution is from satisfying the equation), solve the system again with that residual as the right-hand side to get a correction, and add the correction to the solution. Repeating this drives the solution toward full accuracy without refactoring the matrix.

The role of extended precision

The key subtlety is that the residual involves subtracting nearly equal quantities and so suffers catastrophic cancellation. Computing the residual in higher precision than the rest of the calculation captures the small but meaningful difference that would otherwise be lost. With the residual computed in extended precision, iterative refinement can recover a solution accurate to working precision even for moderately ill-conditioned systems.

import numpy as np

def iterative_refinement(A, b, solve, steps=3):
    x = solve(b)
    for _ in range(steps):
        r = b - A @ x          # residual (ideally in higher precision)
        dx = solve(r)          # reuse the existing factorization
        x = x + dx
    return x

Cost and payoff

Each refinement step reuses the existing factorization, so it costs only a matrix-vector product and a triangular solve, far cheaper than the original factorization. A few steps typically suffice. This makes iterative refinement a nearly free accuracy insurance policy on top of a direct solve.

Mixed-precision computing

Modern hardware runs low precision much faster than high precision, and iterative refinement exploits this. The expensive factorization is done in fast low precision, then iterative refinement in higher precision recovers full accuracy. This mixed-precision strategy delivers the speed of low precision with the accuracy of high precision, and it is increasingly important on accelerators where low-precision throughput dominates. The technique connects directly to conditioning and backward stability, which determine how many refinement steps are needed and whether full accuracy is attainable.