Error bounds for the Sherman-Morrison formula and its modification with improved stability

Abstract

It is known that the Sherman--Morrison (SM) formula is not numerically stable. In recent work, we introduced SMIR, an algorithm that incorporates iterative refinement to enhance the SM backward error. In this paper we take a different route: adapting an algorithm of Govaerts, originally designed for general bordered linear systems, we develop a modified Sherman--Morrison (MSM) method whose built-in self-correction makes it surprisingly resilient. Whereas standard SM requires the solution of two $n\times n$ linear systems, MSM requires three; by contrast, SMIR requires $2+k$ solves, where $k$ is the number of IR steps and can be substantially larger than three, when IR converges slowly. We then derive backward and forward error bounds for both SM and MSM. The SM backward error bound established here is stronger than the one proved in [Hashemi \& Nakatsukasa 2026]: it accounts for every rounding error and holds with no conditions on the size of the capacitance. From these bounds we extract growth factors that are cheap to compute a posteriori and can be used to certify the backward and forward stability of SM and MSM on a given problem. In our experiments, MSM consistently produces backward stable solutions, and is therefore observed to be forward stable as well. A formal proof of the stability --- or instability --- of MSM remains an open problem.

33 pages, 6 figures