2
$\begingroup$

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.

  • 1
    If $A$ is symmetric, we can consider it diagonal. We can control the remainder of the series in this case.2012-08-03

1 Answers 1

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$.