iterative refinement

Cheaply improving an already-computed approximate solution by solving one more, small system for the correction, reusing the same factorization instead of re-solving from scratch.

Iterative refinement computes the residual $\mathbf{r}=\mathbf{b}-A\hat{\mathbf{x}}$ of an approximate solution $\hat{\mathbf{x}}$ , solves $A\mathbf{c}=\mathbf{r}$ for the correction $\mathbf{c}$ (reusing $\hat{\mathbf{x}}$ 's own $LU$ factorization at $O(n^2)$ cost), and sets $\hat{\mathbf{x}}_{\text{new}}=\hat{\mathbf{x}}+\mathbf{c}$ , since $\mathbf{c}=A^{-1}\mathbf{r}=\mathbf{x}-\hat{\mathbf{x}}$ exactly. The residual itself must be computed as accurately as practical, since catastrophic cancellation in $\mathbf{b}-A\hat{\mathbf{x}}$ would otherwise undermine the whole procedure.

Examples

Given an $LU$ factorization already in hand, one refinement pass costs only $O(n^2)$ -- far cheaper than re-solving the whole $O(n^3)$ system from scratch.