Convergence of $A^t$

54 Views Asked by At

Consider

$$a_t = Aa_{t-1}$$

i.e.

$$a_t = A^ta_0$$

for a matrix $A$ and an intial vector $a_0$.

In wonder whether this process converges iff the process

$$b_t = Ab_{t-1}+c$$

converges, starting from the same $a_0$, and a fixed vector $c$.

We have

$$b_t = A^ta_0+\left(\sum_{s=0}^{t-1}A^s\right)c$$

Intuitively, I would say, if $a_t$ converges then also $b_t$, but I don't know.

1

There are 1 best solutions below

5
On

Actually, $b_t$ can diverge even if $a_t$ converges and vice-versa.

Consider the problem for the scalar case $A = 1$, $a_0 = 1$, and $c = 1$.

Then, $a_t = A^ta_0 = 1^t \cdot 1 = 1$ for all $t$, so $a_t$ converges to $1$ as $t \to \infty$. However, $b_t = A^ta_0+\displaystyle\sum_{s = 0}^{t-1}A^sc = 1^t \cdot 1 + \sum_{s = 0}^{t-1}1^s \cdot 1 = 1+(t-1) = t$ which diverges as $t \to \infty$.

Also, consider the problem for the scalar case $A = -1$, $a_0 = 1$, $c = 2$.

Then, $a_t = A^ta_0 = (-1)^t \cdot 1 = (-1)^t$ which does not converge as $t \to \infty$. However, $b_t = A^ta_0+\displaystyle\sum_{s = 0}^{t-1}A^sc = (-1)^t \cdot 1 + \sum_{s = 0}^{t-1}(-1)^s \cdot 2 = (-1)^t + \dfrac{1-(-1)^t}{1-(-1)} \cdot 2 = 1$ for all $t$, so $b_t$ converges to $1$ as $t \to \infty$.


Note: In order to ensure that both $a_t$ and $b_t$ converge, you need the condition $\|A\| < 1$, i.e. all of the eigenvalues of $A$ are between $-1$ and $1$ exclusive.