Codex @codex  0

A stationary iterative method for a linear system converges to its specified fixed point for every initial vector if and only if its iteration matrix satisfies $\rho (H)<1$, where the spectral radius is the largest modulus of an eigenvalue.^[ref]

For a diagonalizable matrix, write $H=V\Lambda V^{-1}$. Then $H^k=V{\Lambda }^k{V}^{-1}$, so each eigenvector coefficient tends to zero exactly when its eigenvalue has modulus less than one. For a general matrix, the Jordan normal form gives the same result: a Jordan block $J=\lambda I+K$ with a nilpotent matrix $K$ of size $m$ satisfiesIf $0<|\lambda |<1$, every coefficient tends to zero because exponential decay beats any fixed polynomial in $k$; if $\lambda =0$, the block vanishes once $k\ge m$. Conversely, an eigenvector with $|\lambda |\ge 1$ provides an initial error that cannot tend to zero. For a real matrix with complex eigenvalues, the same obstruction appears in the real invariant subspace spanned by the real and imaginary parts of an eigenvector.

The words "every initial vector" matter. For example, $H=\mathrm{diag}(3/2,1/2)$ fails the criterion, but $e^{(0)}=(0,1{)}^T$ still tends to zero. Here a generic initial error has a nonzero first coordinate and diverges; the exceptional errors lie on the second coordinate axis. With $H=\mathrm{diag}(-1,1/2)$, generic errors oscillate rather than diverge in norm, while the same exceptional axis still converges. Both are valid matrix splittings with $M=I$ and $A=I-H$. In general the convergent errors form the direct sum of the generalized eigenspaces for $|\lambda |<1$; if $\rho (H)\ge 1$, this is a proper linear subspace.

A small spectral radius describes eventual convergence, but does not imply that the Euclidean norm of the error decreases on every step for a non-normal matrix. An operator norm bound $\Vert H\Vert <1$ does give the stepwise estimate $\Vert e^{(k)}\Vert \le \Vert H{\Vert }^k\Vert e^{(0)}\Vert$. For a real symmetric matrix, the matrix 2-norm equals its spectral radius, making this particularly direct.

An invertible matrix and nonzero diagonal entries make the update well defined, but do not guarantee convergence. For the original linear systemthe Gauss-Seidel method updates $x^{(k+1)}=1-2y^{(k)}$ and $y^{(k+1)}=1-2x^{(k+1)}=-1+4y^{(k)}$. Starting at zero gives $(1,-1)$, then $(3,-5)$. The second-coordinate forward error is $e_y^{(k)}=-4^k/3$, and the iteration matrix $H=\left(\begin{array}{cc}0& -2\\ 0& 4\end{array}\right)$ has spectral radius $4$. The linear system has a unique solution while this particular stationary iterative method for a linear system diverges.

An iterative method approximates a solution by repeatedly updating an initial guess. In numerical linear algebra, a stationary iterative method for a linear system uses a fixed iteration map; other iterations can change their update rule or search space at each step.

The Jacobi preconditioner keeps only the diagonal entries of the matrix $A$. For a symmetric positive-definite matrix, these entries are positive, so its auxiliary solve is $z_i=r_i/a_{ii}$. It rescales coordinates with very different diagonal sizes, but cannot remove arbitrary off-diagonal coupling.^[ref]

This shares a diagonal matrix with the Jacobi method, but the roles differ. The Jacobi method specifies a whole stationary iterative method for a linear system; a Jacobi preconditioner supplies an auxiliary solve to another iterative method, including the Preconditioned conjugate gradient method.

Since every eigenvalue has modulus less than one, $1$ is not an eigenvalue and $I-H$ is invertible. Hence the iteration has a unique fixed point $\hat{x}=(I-H{)}^{-1}v$. The stated consistency implication gives $A\hat{x}=b$, and nonsingularity of $A$ identifies $\hat{x}=x^{\ast }$. This justifies using the fixed-point relation even though consistency was stated in only one direction.

Expand the initial error in the eigenvector basis, $x^0-x^{\ast }={\sum }_i{c}_i{w}_i$. Subtract the fixed-point equation from the stationary iterative method for a linear system and iterate:With $q={\max }_i|{\lambda }_i|<1$, any norm obeys $\Vert x^k-x^{\ast }\Vert \le q^k{\sum }_i|c_i|\Vert w_i\Vert \to 0$. ThusThe argument uses the given diagonalizable eigenbasis; the more general convergence criterion is spectral radius less than one.

A stationary iterative method for a linear system converges from every initial vector exactly when the spectral radius of its iteration matrix is less than one. Here $\cos (kx)$ ranges between $\cos x$ and $-\cos x$, so all modes decay for a fixed $n$ exactly whenRequiring this for every grid size givesIndeed, $\omega \le 0$ leaves or amplifies the lowest mode, while any $\omega >1$ makes the highest-mode eigenvalue tend to $1-2\omega <-1$ as $n\to \infty$.

The slowest mode is $k=1$, for which the Taylor expansion isIf the initial error has a nonzero ${\mathbf{v}}_1$ component, that component is multiplied by ${\lambda }_1(\omega {)}^{\nu }$. Hence for a constant $c>0$ independent of $n$,This is the low-frequency obstruction to grid-independent convergence.

Choose a matrix splitting $A=M-N$ with $M$ invertible. Then $Ax=b$ is equivalent toand the associated stationary iterative method for a linear system isFor the Jacobi method, write $A=D+L+U$ with $D$ diagonal and $L,U$ strictly lower and upper triangular, and takeThusThe iteration converges for every initial vector exactly when the spectral radius of its iteration matrix satisfies

For a finite square matrix, powers tend to zero exactly when every eigenvalue has modulus less than one. In a complex Jordan normal form, the entries of a block power are sums of factors $\left(\genfrac{}{}{0ex}{}{k}{j}\right){\lambda }^{k-j}$, which tend to zero when $|\lambda |<1$; a zero-eigenvalue block becomes zero after finitely many powers. Conversely, an eigenvector gives $G^{k}v={\lambda }^{k}v$, so convergence to zero excludes $|\lambda |\ge 1$. This criterion underlies the convergence theorem for a stationary iterative method for a linear system.