6
$\begingroup$

The Sherman-Morrison formula $$ (A+uv^T)^{-1} = A^{-1} - \frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u} $$ results in small errors in relation to the standard matrix inverse operation after each application, as shown here. From what I understand, the Sherman-Morrison identity is exact, so the error must come from numerical problems. But where exactly? Also, are there any theoretical bounds for this error? Some sources argue that the error is related to the matrix condition number, but wouldn't that affect the standard inversion too?

$\endgroup$
  • 1
    $\begingroup$ Can you give a minimal reproducible example showing these errors? The pdf you link to applies the formula to a sequence of $N$ random updates $u_k,v_k$ and shows error $\|A^{-1}_{\mathrm{sm},k} - A^{-1}\|$ as growing slower than something like $N\epsilon_{\mathrm{mach}}$ ($\sqrt{N}\epsilon_{\mathrm{mach}}$?), which doesn't seem unreasonable to me. $\endgroup$ – Kirill Aug 6 '15 at 5:43
  • $\begingroup$ The example I have is the one you saw in the pdf. So would you say it is just a precision issue? So the error occurs in both approaches, but since we are measuring only the difference between them, it is not possible to tell? $\endgroup$ – rcpinto Aug 6 '15 at 5:53
  • 1
    $\begingroup$ If you perform $N$ operations and each has error $\pm\epsilon$, you accumulate on average an error of $\sqrt{N}\epsilon$ in a kind of random walk. It's just accumulation of roundoff errors, and not anything specifically to do with Sherman-Morrison, that's the non-exceptional behaviour you'd usually get. $\endgroup$ – Kirill Aug 6 '15 at 6:19
  • 2
    $\begingroup$ In Higham Accuracy and Stability of Numerical Algorithms (2002), Exercise 26.2 forward and backward error bounds for Sherman-Morrison (not running error after $N$ updates - which is it that you're after?) are listed as a research problem, with a citation to E. L. Yip in J. Sci. Statist. Comput. 7 (3) 1986, which I can't look up right now. Can you state the question more clearly please? $\endgroup$ – Kirill Aug 6 '15 at 6:29
  • 1
    $\begingroup$ Sherman-Morrison requires you to compute $A^{-1} v$. Note that $A + vv^T$ can be well-conditioned even when $A$ is not. $\endgroup$ – tmyklebu Aug 7 '15 at 1:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.