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× 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.
Related
- Improved Upper Bounds for the Rank of the Determinant Tensor via Glynn's Formula
- Improved algorithms for computing the matrix logarithm based on the double-exponential formula
- On the relative Morrison-Kawamata cone conjecture (II)
- Effective Hamiltonians in Perforated Domains: Inf-Max formula and Stability
- Stability for the adjoint Finner inequality and improved lower bounds on the k-plane transform
BibTeX
@misc{hashemi2026error,
title = {{Error bounds for the Sherman-Morrison formula and its modification with improved stability}},
author = {Behnam Hashemi and Yuji Nakatsukasa},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.12266},
eprint = {2609.12266},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.12266},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Error bounds for the Sherman-Morrison formula and its modification with improved stability
AU - Behnam Hashemi
AU - Yuji Nakatsukasa
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.12266
UR - https://arxiv.org/abs/2609.12266
AB - 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× 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.
ER -