Neumann series and spectral radius
Solution 1
Gelfand's formula shows that if $\rho(A) < 1$, then for some $n$, $\|A^n\| < 1$. One can then rewrite the series as $(1 + A + \cdots + A^{n-1}) \sum_{i=0}^\infty A^{ni}$, which surely does converge in norm.
Solution 2
Let us start defining a function $T:\mathbb{R}^{n \times n}\rightarrow \mathbb{R}^{n \times n}$ such that $T(x)=I+xA,$ for all $x\in\mathbb{R}^{n\times n}.$ Note that the fixed point iteration $x_{n+1} = T(x_n)$ staring with $x_0=I$ is equal to the sum $x_k=\sum^{k}_{i=0}A^i.$ Hence, we only need to show that $x_k$ converges to show that $\sum^{k}_{i=0}A^i$ converges.
Note that $$ \begin{split} T^{k+1}(x)-T^{k+1}(y) = & (I + T^{k}(x) A) - (I + T^{k}(y) A)\\ =& T^{k}(x) A - T^{k}(y) A \\ = & (T^{k}(x)-T^{k}(y))A, \end{split} $$ for all $x,y\in \mathbb{R}^{n \times n}. $Thus, by induction, $$T^{k}(x)-T^{k}(y) = (x-y)A^{k},$$ for all $k\in\mathbb{N}$ and all $x,y\in \mathbb{R}^{n \times n}$. Now, choosing your favorite submultiplicative norm, since $\lim_{k\rightarrow \infty} \|A^{k}\|^{1/k} = \rho(A)<1,$ we can choose $k_0$ big enough such that $\|A^{k_{0}}\|<1.$ Hence, $$\|T^{k_0}(x)-T^{k_0}(y)\| \leq \|x-y\|\|A^{k_0}\|.$$ Hence, $T^{k_0}$ is a contraction. Consequently, the fixed point iteration $z_{k+1}=g(z_k)$, with $g$ given by $g(x)=T^{k_0}(x),$ for all $x\in\mathbb{R}^{n \times n},$ converges to the unique fixed point of $g$ independently to the starting point $z_0\in\mathbb{R}^{n \times n}, $ as stated here.
Let $y^{*}\in\mathbb{R}^{n\times n}$ be the unique fixed point for $g$. Given a natural number $0 \leq i< k_0$, as previously commented, the fixed point iteration $z_{k+1} = g(z_{k})$ staring with $z_0=T^{i}(x_0)$ will converge to $y^{*}$. Since $g$ commutes with $T$, we have that $$\begin{split} y^{*} =& \lim_{k \rightarrow \infty} z_{k} \\ =& \lim_{k \rightarrow \infty} g^{k}(T^{i}(x_0))\\ =& \lim_{k \rightarrow \infty} T^{i}(g^{k}(x_0))\\ =& \lim_{k \rightarrow \infty} T^{i}(T^{k_0 k} (x_0))\\ =& \lim_{k \rightarrow \infty} T^{k_0 k + i} (x_0)\\ =& \lim_{k \rightarrow \infty} x_{k_0 k + i}.\end{split}$$ Taking into account that the last conclusion is true for all $0 \leq i<k_0$, all of the subsequences $\{x_{k_0 k +i}\}_{k\in\mathbb{N}}$ of $\{x_{k}\}_{k\in\mathbb{N}}$ converges to $y^{*}$. Thanks to Division theorem, this is enough to show that that $\{x_{k}\}_{k\in\mathbb{N}}$ converges to $y^{*}$.
As a last observation, I will show that $y^{*}$ is actually the inverse of $I-A.$ Considering that $y^{*}$ is the fixed point of $g$ and limit of the sequence defined by $y_{k+1}=g(y_{k})$ staring with $x_0=T(y^{*}).$ The calculations $$\begin{split} y^{*} =& \lim_{k \rightarrow \infty} y_{k} \\ =& \lim_{k \rightarrow \infty} g^{k}(T(y^{*}))\\ =& \lim_{k \rightarrow \infty} T(g^{k}(y^{*}))\\ =& \lim_{k \rightarrow \infty} T(y^{*})\\ =& T(y^{*}).\end{split}$$ shows that $y^{*}=T(y^{*})=I-Ay^{*}$. Hence, $y^{*}(I-A) = I.$ This shows that $(I-A)y^{*}=I$ also, since all square matrices which has a left inverse has a right inverse as well. This shows that $y^{*}$ is the inverse of $I-A.$
Related videos on Youtube
s_2
Updated on August 01, 2022Comments
-
s_2 over 1 year
I have a question about the convergence of the Neumann series:
Let $A$ be a matrix with spectral radius $\rho(A)<1$, i.e., all eigenvalues of $A$ are strictly less than $1$. Does that imply that the series \begin{equation} \sum_{i=0}^{\infty}A^i \end{equation} converges (in the operator norm)? I know how to prove it if the operator norm of $A$ is strictly less than $1$, but I don't know how to prove it if I only know that the spectral radius is less than $1$.
Many thanks for any help!
-
Erick Wong almost 11 yearsAre you familiar with Gelfand's formula relating operator norm to spectral radius?
-
s_2 almost 11 yearsI know the formula, but that's it. in particular, I would not know how to apply it here...
-
Erick Wong almost 11 yearsIf $\|A^n\|^{1/n} \to c < 1$ then for some $n$ large enough, $\|A^n\| < 1$.
-
s_2 almost 11 yearsok, I understand. but how does that help me here exactly. sorry that I don't see it... and many thanks for your help!
-
Erick Wong almost 11 yearsYou said you know how to show convergence given the operator norm is $<1$...How does the proof go?
-
Jonas Meyer almost 11 years$\|A^n\|^{1/n}\leq d<1$ implies $\|A^n\|\leq d^n$, so you can use convergence of geometric series.
-
s_2 almost 11 yearswell, how to use your hint in the proof with the operator norm smaller than 1 is what I was thinking about. But I cant directly use sub-multiplicativity of the operator norm to deduce from your hint that the operator norm is less than 1. the key element in the proof is to show that the partial sums are Cauchy. how could I deduce the same property here? I can't come up with a geometric series as majorant (or do I - am I just not able to see it?)?
-
s_2 almost 11 yearsok, there is the answer - I was just not able to see it! sorry for taking your time. and many thanks Erick and Jonas!!! I really appreciate your help.
-
-
bkarpuz over 5 yearsAlso note that $\rho(A^{n+i})=\bigl(\rho(A^{n})\bigr)^{i}$.
-
R. W. Prado over 2 yearsI'm not sure how do you could to conclude that $s_k= \sum^{k}_{i=0} A^{n+i}$ actually converges. I'm not even sure how to show that $\rho(A^{n+1})= \rho(A^{n})^i .$ For me it looks like $ \rho(A^{n+i})= \rho(A^{n}) \rho (A)^{i}.$
-
R. W. Prado over 2 yearsThis proof includes a proof of something interesting, that is, if $T^k$ is a contraction for some $k$, then the inductively defined sequence $T(x_{n})=x_{n+1}$ starting with $x_0=x$ converges to the unique fixed point of T independently of $x$. An error can be derived as well, as here: en.wikipedia.org/wiki/Fixed-point_iteration
-
R. W. Prado over 2 yearsIt's possible to generalize this result for Banach spaces, considering that $x_k=T^k(I)$ commutes with $I-A.$ The last lines would change for general Banach spaces.
-
Erick Wong over 2 years@R.W.Prado Thanks for your comment. It looks like some years ago, an inexperienced user completely misinterpreted my answer and edited it to something true but rather useless to the argument at hand. The deduction should be much clearer now.
-
R. W. Prado over 2 yearsInteresting. =) Now I can see everything works. This way of proving resembles the way I have found to prove it. This shows that a subsequence of $$s_k = \sum^{k}_{i=0} A^{i}$$ converges. I have filled out the details in my answer of how to prove that the series actually converges.