Iterative Systems

What does a a linear iterative system look like?

A linear iterative system takes the form:

$u^{(k+1)}=T{u}^{(k)}$, $u^{(0)}=a$ where $T\in {\mathbb{R}}^{n\times n}$ or ${\mathbb{C}}^{n\times n}$ is the coefficient matrix.

The vector iterates $u^{(k)}$ belonging to ${\mathbb{R}}^n\text{ or }{\mathbb{C}}^n$. The system represents a discrete time evolution. This is tantamount to a discretized first order linear ODE where k represents the iteration step.

Scalar Version:

$u^{(k+1)}=\lambda u^{(k)}$, $u^{(0)}=a$, $\lambda ,a\in \mathbb{R}\text{ or }\mathbb{C}$

How does the value of lambda affect our iterative equation?

When lambda is 0, we get $u^{(k)}=0$ for all $k\ge 1$. If lambda is $0\le \lambda \le 1$, then it is stable and will approach $u^{(k)}=0$ monotonically. Overall, there are three main classes:

• Asymptotically Stable: $|\lambda |<1$
• Stable (but not asymptotic): $|\lambda |=1\to |u^{(k)}|$ is constant or oscillating
• Unstable: $|\lambda |>1\to u^{(k)}$ grows unbounded

This means our equation as a whole should be below 1 with our initial guess.

What does a general linear iterative system look like?

$u^{(k+1)}=T{u}^{(k)}$, $u^{(0)}=a$

iterates as such: $u^{(1)}=Ta$, $u^{(2)}=T^{2}a$, $u^{(3)}=T^{3}a$ ⇒ $u^{(k)}=T^{k}a$

How do matrix powers work?

To put matrices to a power, we use the power ansatz:

$u^{(k)}={\lambda }^{k}v$ $\to u^{(k+1)}={\lambda }^{k+1}v$ $\to T{u}^{(k)}={\lambda }^{k}Tv$ $\to Tv=\lambda v$

We, therefore, seek eigenvalues $\lambda$ and eigenvectors v of T.