4
$\begingroup$

I wish to solve numerically for $x$,

$$ y = (A+B^{-1})x $$

with $A, B$ positive definite. So,

$$ x = (A+B^{-1})^{-1}y $$

I would like to avoid calculating $B^{-1}$ since that's generally bad.

This question seems unusually short. I can provide extra info if needed.

$\endgroup$
12
  • 1
    $\begingroup$ You can just do an intermediate solve: Solve $Bw=x$, then $y=Ax+w$ $\endgroup$
    – KevinG
    Jan 26, 2013 at 19:57
  • $\begingroup$ That sounds like just the kind of thing I need, but I don't know what that is. Can you elaborate? Maybe I'm just dense. $\endgroup$ Jan 26, 2013 at 19:58
  • $\begingroup$ Sorry about that... I always forget get that <return> submits a comment... editted above. $\endgroup$
    – KevinG
    Jan 26, 2013 at 19:59
  • $\begingroup$ @JohnSalvatier Could you clarify whether you are solving $x$ for a known $y$, or solving $y$ for a known $x$? $\endgroup$
    – Erick Wong
    Jan 26, 2013 at 20:00
  • 5
    $\begingroup$ You want to solve for $Ax + B^{-1}x = y$ i.e. you want to solve for $$(BA+I)x = By$$ If $\Vert BA \Vert < 1$, then we have $$x = \sum_{k=0}^{\infty} (-1)^k (BA)^k By$$ This can be truncated to get arbitrarily accurate results. IF you truncate after $r$ terms the cost to evaluate this goes as $\mathcal{O}(rn^2)$ where $n$ is the size of the matrices $A$ and $B$. $\endgroup$
    – user17762
    Jan 26, 2013 at 20:08

1 Answer 1

2
$\begingroup$

I would take Marvis' answer one step ahead. You want to solve $(BA+I)x=By$. Because $BA+I$ is positive semidefinite, you can use conjugate gradient. The only operation you need is matrix multiplication and convergence is guarantee to an accurate solution within a finite number of steps.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.