iterative refinement

You solved Ax = b and got x-hat, but rounding error during the factorization cost you some accuracy. Iterative refinement recovers it with a remarkably cheap loop. Compute the residual r = b - A x-hat, solve A d = r for the correction d, and update x-hat to x-hat + d. The residual measures exactly how much the current answer fails to satisfy the equation, so correcting by d nudges the solution toward the truth. Repeat a few times.

The key economy is that you reuse the factorization you already paid O(n^3) for. Solving A d = r is just one more forward-and-back substitution at O(n^2), so each refinement step is cheap compared to the original solve. A couple of steps usually suffice. The one subtlety that makes or breaks it: the residual r must be computed accurately, ideally in higher precision than the rest, because r is a small difference of larger quantities and prone to cancellation.

Why it works: in exact arithmetic the update would be perfect, since A(x-hat + d) = A x-hat + r = A x-hat + (b - A x-hat) = b. Rounding spoils that ideal, but each pass still removes a large fraction of the remaining error. As long as the residual is computed accurately and A is not too ill-conditioned, the iteration converges to full working accuracy.

Today iterative refinement enjoys a renaissance through mixed precision. Hardware makes low-precision arithmetic (single or half) far faster than double, so the modern recipe is to factor and solve cheaply in low precision, then use a few refinement steps with a high-precision residual to claw back double-precision accuracy. This delivers fast results without sacrificing the final accuracy.