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

1. Introduction.

• SM computes the solution using two solves with A and a scalar correction along A^-1u.The correction uses the capacitance 1 + v^T A^-1u.Source: §1 · pp. 1–2
• An open question asks whether SM admits a backward-error bound proportional to the infinity-norm condition number of A.Earlier sufficient-condition analysis assumes a lower bound on |v^Tz|.Source: §1 · p. 2
• The paper derives backward and forward error bounds, proposes MSM, and introduces growth factors for assessing SM and MSM stability.The SM backward-error bound accounts for all rounding errors and requires no condition on capacitance size.Source: §1 · p. 2
• The analysis assumes systems with nonsingular A can be solved efficiently and that the solver is normwise backward stable.The intended setting includes cases where A has exploitable structure or an available factorization.Source: §1 · pp. 2–3

2. Error bounds for SM.

• The backward-error derivation models rounding in the inner products, scalar calculations, vector operations, and linear solves.It starts from the floating-point inner products used to compute the SM scalar quantities.Source: §2 · pp. 4, 6
• The SM backward-error bound includes a term of order ε_Mκ(A), and can be large when ||A + uv^T|| is much smaller than ||A|| + ||u||||v||.The theorem assumes normwise backward-stable solves for Ay = b and Az = u.Source: §2 · pp. 8–9

2.1. Forward error bounds for the SM solution.

• When B = A + uv^T is well-conditioned, the forward-error bound makes SM accuracy depend on the norm of the intermediate solution y.The section also describes a computable forward-error bound based on the computed approximation and residual.Source: §2 · p. 9, §2.1 · p. 11
• The forward-error result requires ϵ_M(2r_c1 + c_s)κ(B) < 1 for the stated bound to apply.The theorem assumes normwise backward-stable solves for Ay = b and Az = u.Source: §2.1 · p. 9

3. A modified Sherman-Morrison (MSM) method.

• The bordered-system formulation treats θ = v^T x as an intermediate unknown, with θ equal in exact arithmetic to the SM scalar α/β.This links solving Ax + uθ = b to the original rank-one perturbed system.Source: §3 · p. 12

3.1. Modified Sherman-Morrison (MSM).

• MSM corrects the provisional pair (0, θ_SM) by solving for a residual correction, then returns the corrected vector solution.Its steps use three solves with A and compute the correction along z = A^-1u.Source: §3 · p. 12, §3.1 · pp. 13–14

3.2. An alternative way to think about MSM.

• An alternative derivation splits b into d = b − uθ and f = uθ, simplifying the SM solves for the two resulting right-hand sides.This derivation arrives at the same output form, x = w − zθ1.Source: §3.2 · pp. 14–15

4.1. Backward error of MSM.

• MSM’s backward error is bounded using an error representation that accounts for perturbations across the algorithm’s computed steps.Theorem 4.2 gives a bound for the computed solution’s backward error.Source: §4.1 · pp. 19, 21

4.2. Forward error of MSM.

• MSM’s forward error bound assumes normwise backward-stable solves and requires ϵ_M rc3 κ(B) < 1.The section also gives a corollary with a bound intended to support a convenient test for MSM forward stability.Source: §4.2 · pp. 21–23

4.3. Discussion of error bounds and growth factors.

• The section defines backward and forward growth factors for SM and MSM as ratios that should ideally be O(1), measuring degradation from ideal error bounds.These factors are intended to be cheap a posteriori indicators of stability.Source: §4.3 · pp. 23–24
• Even when ill-conditioning makes some forward-bound constants negative, the growth factors may still correctly predict method stability.The discussion also characterizes SM backward stability by its growth-factor criterion.Source: §4.3 · p. 24
• SM is forward stable when its bound’s computable denominator is positive; that denominator lower-bounds ||(A + uv^T)x|| and substitutes for ||b|| because the computed solution differs from x.If the denominator is not positive, the residual has not been small enough for the bound to provide useful information about ||x||.Source: §4.3 · pp. 24–25
• MSM is backward stable if its correction vector satisfies the stated size condition and its MSM growth factor is O(1).The passage specifies the correction-vector condition as ||p|| = O(||px||).Source: §4.3 · p. 25
• MSM is forward stable if either of the stated sufficient growth-factor conditions holds, with the denominator in the latter condition assumed positive.These conditions combine the backward-error bound with bounds on ||x|| or the related bound in (2.28), and make explicit a factor hidden in c6.Source: §4.3 · p. 25

5. Experiments.

• In Example 5.1, SM is not backward stable, while MSM and SMIR are; all methods are forward stable, and SMIR uses up to six refinement steps.The comparison is shown in Fig. 5.1.Source: §5 · p. 26, Figure 5.1 · p. 26
• In the large-norm Example 5.2, SM already performs backward stably, MSM is also backward stable, and all methods are forward stable.SMIR requires no extra refinement steps in this regime.Source: §5 · p. 27, Figure 5.2 · p. 27
• In Example 5.3, SM’s backward stability deteriorates as A becomes more ill-conditioned, while MSM and SMIR remain backward stable and MSM is faster.The tests use n = 1000 and condition numbers of A from 10 to 10^4.Source: §5 · p. 28, Figure 5.3 · p. 28
• In Example 5.4, SM is neither backward nor forward stable, whereas MSM and SMIR are stable in both senses.Here B is well-conditioned, A is ill-conditioned, and the solution has modest norm.Source: §5 · p. 29, Figure 5.4 · p. 29

5.1. Does small capacitance cause backward instability in SM and MSM?.

• With capacitance values from 10^-16 to 10^-1 in Example 5.5, the largest backward errors are 3.3×10^-15 for MSM, 1.6×10^-15 for SM, and 8.7×10^-16 for backslash.The experiment constructs 100 test problems with an exact solution of modest norm.Source: §5.1 · p. 30, Figure 5.5 · p. 30
• In one concrete run, pβ ≪ 3.3×10^-13 and pα ≈ 7.8×10^-12 produce pθ ≈ 23.8; despite a residual norm about 10^-8, SM relative backward error remains acceptable when B and b are both of order 10^6.The absolute error of 10^-8 is absorbed in the relative backward-error denominator.Source: §5.1 · p. 30
• In Example 5.6, SM and MSM remain backward stable because the very large computed solution norms let the Rigal–Gaches denominator absorb inflated residuals.The authors describe this as a different mechanism from Example 5.5.Source: §5.1 · pp. 31–32, Figure 5.6 · p. 31
• The derived growth factors provide a posteriori sufficient stability conditions when they are of order one, but unconditional proof or disproof of MSM stability remains open.The authors report that targeted attempts did not produce adversarial examples for MSM.Source: Summary and future directions · p. 32

• Lemma A.1 begins by conditioning its statement on the assumptions of Theorem 2.1 being satisfied.Source: Appendix A · p. 33
• The stated bound involves the matrix norm and the norms of the perturbation vectors.Source: Appendix A · p. 33
• The proof takes norms of both sides and obtains terms involving unit roundoff and matrix/vector norm factors.Source: Appendix A · p. 33