The Sherman-Morrison formula; numerical instability and stabilization via iterative refinement
Behnam Hashemi (Leicester, Computing and Mathematical Sciences)
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^T)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 analyze the backward stability of the SM formula and prove its instability in a scenario increasingly common in scientific computing, supported by numerical evidence. We then address an open question posed by Nick Higham regarding the proportionality of the SM backward error bound to the condition number of $A$. Finally, we integrate fixed-precision iterative refinement (IR) into the SM framework to develop the SM-IR algorithm. We prove that, under reasonable assumptions, IR enhances the backward error of the SM formula and present practical evidence supporting the eventual backward stability of SM-IR. Since SM-IR reuses previously computed decompositions, it retains the efficiency of the original SM algorithm. This is joint work with Yuji Nakatsukasa (University of Oxford).