From the Classical Sherman–Morrison Formula to Iterative Refinement and a Self-Correcting Modification for Improved Stability

Owing to its simplicity and efficiency, the Sherman-Morrison (SM) formula has seen widespread use across various scientific and engineering applications for solving rank-one perturbed linear systems of the form (A +
uv')x = b. Although the formula dates back at least to 1944, its numerical stability properties have remained an open question and continue to be a topic of current research.

We analyse the backward stability of the SM formula and show, both theoretically and through numerical experiments, that it is unstable in a scenario that is increasingly common in scientific computing. We then answer an open question posed by Nick Higham regarding the proportionality of the SM backward error bound to the condition number of A.

Next, we integrate fixed-precision iterative refinement (IR) into the SM framework to develop the SM-IR algorithm. We prove that, under reasonable assumptions, IR improves the backward error of the SM formula.

Finally, we will introduce a modified SM (MSM) algorithm motivated by block Gaussian elimination for bordered linear systems. MSM is typically faster than SM-IR and its built-in self-correction strategy makes it surprisingly resilient to the ill-conditioning of A. Time permitting, we will also present backward and forward error bounds for MSM, together with the associated amplification factors. This is joint work with Yuji Nakatsukasa (University of Oxford).