Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
You can just do an intermediate solve: Solve $Bw=x$, then $y=Ax+w$ –  KevinG Jan 26 '13 at 19:57
    
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. –  John Salvatier Jan 26 '13 at 19:58
    
Sorry about that... I always forget get that <return> submits a comment... editted above. –  KevinG Jan 26 '13 at 19:59
    
@JohnSalvatier Could you clarify whether you are solving $x$ for a known $y$, or solving $y$ for a known $x$? –  Erick Wong Jan 26 '13 at 20:00
5  
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$. –  user17762 Jan 26 '13 at 20:08
show 7 more comments

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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