= Solution
Let $x_*=A^{-1}b$, $e_k=x_k-x_*$ and $G=M^{-1}N$. Subtract the exact fixed-point equation to obtain $e_k=G^ke_0$. Hence convergence for every initial vector is equivalent to $G^k\to0$. If this holds, it holds after complexification; applying it to a complex <eigenvector> gives $\lambda^kv\to0$, so $|\lambda|<1$. Conversely, the complex <Jordan normal form> expresses each power as a finite sum of terms $\binom{k}{r}\lambda^{k-r}$ from its blocks. Every term tends to zero when all <eigenvalues> have modulus below one. Thus
$$
\boxed{\text{Convergence for every starting vector}\iff\rho(G)<1.}
$$
The <convergence criterion for a stationary iteration> needs complex triangularization or <Jordan normal form>. The paper's assertion that every real matrix is similar to a real upper-triangular matrix is false when nonreal <eigenvalues> occur; complex triangularization supplies the intended argument. In the <Gauss-Seidel method>, with $A=D+L+U$ split into diagonal, strictly lower and strictly upper parts, $\boxed{M=D+L,\ N=-U}$.
For $n\geq4$, eliminating the ghost values gives the symmetric pentadiagonal <matrix>
$$
\boxed{A=\begin{pmatrix}
7&-4&1&0&\cdots\\
-4&6&-4&1&\cdots\\
1&-4&6&-4&\ddots\\
0&1&-4&6&\ddots\\
\vdots&\vdots&\ddots&\ddots&\ddots
\end{pmatrix},\quad A_{nn}=7,\ A_{jj}=6\ (2\leq j\leq n-1),\quad A_{j,j+1}=-4,\quad A_{j,j+2}=1.}
$$
All other off-diagonal entries vanish. The first two equations are
$$
7U_1-4U_2+U_3=h^4f_1,\qquad
-4U_1+6U_2-4U_3+U_4=h^4f_2,
$$
and the last two are
$$
U_{n-3}-4U_{n-2}+6U_{n-1}-4U_n=h^4f_{n-1},\qquad
U_{n-2}-4U_{n-1}+7U_n=h^4f_n.
$$
For $n=3$ the matrix is $\begin{pmatrix}7&-4&1\\-4&6&-4\\1&-4&7\end{pmatrix}$, for $n=2$ it is $\begin{pmatrix}7&-4\\-4&7\end{pmatrix}$, and for $n=1$ it is $(8)$ because both ghost contributions meet the same unknown. The diagonal entries are positive in every case, so the lower triangular <matrix> $D+L$ is invertible and the <Gauss-Seidel iteration> is well defined.
An <eigenvalue> $\lambda$ of $G=-(D+L)^{-1}U$ makes $H(\lambda)=\lambda(D+L)+U$ singular. Let $\ell_i$ and $r_i$ be the sums of absolute lower and upper entries in row $i$. The row's diagonal-dominance margin is
$$
|\lambda|d_i-|\lambda|\ell_i-r_i.
$$
Interior full rows have $d_i=6$, $\ell_i=r_i=5$, giving margin $|\lambda|-5$. Boundary rows have larger margins; for instance the first gives $7|\lambda|-5$, and the second gives at least $2|\lambda|-5$. Therefore $|\lambda|>5$ would make $H(\lambda)$ a <strictly diagonally dominant matrix>, hence nonsingular, a contradiction.
At $|\lambda|=5$ it is weakly diagonally dominant with strict boundary rows. Its nonzero nearest-neighbour entries make it an <irreducibly diagonally dominant matrix>. The nonsingularity theorem for that class again contradicts singularity. For the small matrices above all rows are already strict at this value. Hence
$$
\boxed{\text{Every iteration eigenvalue has }|\lambda|<5;\text{ equality is impossible}.}
$$
There is also a stronger conclusion. For $T=\operatorname{tridiag}(-1,2,-1)$,
$$
A=T^2+2e_1e_1^T+2e_ne_n^T,
$$
including the $n=1$ overlap. Since $T$ is positive definite, $A$ is a <symmetric positive-definite matrix>. The <Gauss-Seidel convergence from diagonal dominance and positive definiteness> theorem consequently gives the stronger bound $\rho(G)<1$.
Back to article page
