Neumann series and spectral radius

2,599

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

Share:
2,599

Related videos on Youtube

s_2
Author by

s_2

Updated on August 01, 2022

Comments

  • s_2
    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
      Erick Wong almost 11 years
      Are you familiar with Gelfand's formula relating operator norm to spectral radius?
    • s_2
      s_2 almost 11 years
      I know the formula, but that's it. in particular, I would not know how to apply it here...
    • Erick Wong
      Erick Wong almost 11 years
      If $\|A^n\|^{1/n} \to c < 1$ then for some $n$ large enough, $\|A^n\| < 1$.
    • s_2
      s_2 almost 11 years
      ok, 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
      Erick Wong almost 11 years
      You said you know how to show convergence given the operator norm is $<1$...How does the proof go?
    • Jonas Meyer
      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
      s_2 almost 11 years
      well, 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
      s_2 almost 11 years
      ok, 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
    bkarpuz over 5 years
    Also note that $\rho(A^{n+i})=\bigl(\rho(A^{n})\bigr)^{i}$.
  • R. W. Prado
    R. W. Prado over 2 years
    I'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
    R. W. Prado over 2 years
    This 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
    R. W. Prado over 2 years
    It'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
    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
    R. W. Prado over 2 years
    Interesting. =) 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.