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.

Let $A \in \mathbb{R}^{m \times m}$ be a real symmetric negative-semidefinite matrix and consider the Neumann series

$$\sum_{k=0}^\infty t^kA^k = I + tA + t^2 A^2 + \cdots$$

where $t > 0$ is a parameter that can be used to make $tA$ arbitrarily small in any matrix norm.

Question: Assuming this series converges (in your favorite norm), is it asymptotic?

In other words, for sufficiently small $t$ can this series be well-approximated by its first $n$ terms? One fact to recall about Neumann series is that

$$ \sum_{k=0}^\infty t^k A^k = (I-tA)^{-1},$$

which is easily seen by multiplying the partial series $\sum_{k=0}^n t^k A^k$ by the matrix $I-tA$ and taking the limit as $n \rightarrow \infty$. In other words, my question amounts to asking whether the inverse of $I-tA$ is well-approximated by the first $n$ terms of the corresponding Neumann series. (Note, however, that I am well-aware this is not a good way to actually compute a matrix inverse in practice!)


Here are some further facts about the $A$ I am primarily interested in, which may or may not be necessary to provide an answer. First, it has corank 1 and in particular has zero row/column sums, so that $I-tA$ is doubly-stochastic for sufficiently small $t$. Also, $A$ is very sparse -- you might imagine that it is the graph Laplacian of a planar graph. Therefore, to get a good approximation of $(I-tA)^{-1}$ one might need to consider at least the first $m$ terms of the Neumann series.

share|improve this question
1  
If $A$ is symmetric, we can consider it diagonal. We can control the remainder of the series in this case. –  Davide Giraudo Aug 3 '12 at 11:00

1 Answer 1

As suggested by Davide, consider a basis in which $A$ diagonalizes -- for instance, its eigenbasis whose eigenvalues we'll call $\lambda$. Then we have

$$\frac{\left|\sum_{k=n+1}^\infty t^k \lambda^k\right|}{|t^n \lambda^n|}\leq\frac{\sum_{k=n+1}^\infty t^k |\lambda^k|}{t^n |\lambda^n|}=\frac{t^{n+1}|\lambda^{n+1}|\sum_{k=0}^\infty t^k |\lambda|^k}{t^n |\lambda^n|}=t|\lambda|\sum_{k=0}^\infty t^k |\lambda|^k=\frac{t|\lambda|}{1-t|\lambda|}$$

which vanishes as $t \rightarrow 0$.

share|improve this answer

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.