= Jacobi convergence from strict diagonal dominance
{c}
{title2=$\|B\|_\infty=\max_i\sum_{j\ne i}|a_{ij}/a_{ii}|<1$}
A <strictly diagonally dominant matrix> guarantees convergence of the <Jacobi method> for every initial <vector>.<Math 221, Matrix Computations, Fall 2009/Notes for Ma221 Lecture 21, Nov 10 2009>[Math 221, Matrix Computations, Fall 2009; Theorem 1 on strict row diagonal dominance and its proof beginning “Split A = D − (D − A)”]{ref}
Indeed, using the <maximum norm> $\|v\|_\infty=\max_i|v_i|$, the induced <operator norm> is the largest absolute row sum. The <Jacobi method> has $b_{ii}=0$ and $b_{ij}=-a_{ij}/a_{ii}$ for $j\ne i$, so
$$
\rho(B)\leq\|B\|_\infty=\max_i\frac{\sum_{j\ne i}|a_{ij}|}{|a_{ii}|}<1,\qquad \|e^{(k)}\|_\infty\leq\|B\|_\infty^k\|e^{(0)}\|_\infty.
$$
This gives a cheap sufficient check without computing any <eigenvalues>. For the <Jacobi iteration for a three-variable tridiagonal system>, the absolute row sums of $B$ are $1/4,1/2,1/4$, giving $\|B\|_\infty=1/2$. The true <spectral radius> $\sqrt2/4$ gives a sharper eventual rate.
Strict <diagonal dominance> is sufficient, not necessary: $A=\begin{pmatrix}1&2\\1/10&1\end{pmatrix}$ violates it in the first row, but its <Jacobi method> has <eigenvalues> $\pm1/\sqrt5$ and converges. Conversely, being a <positive-definite matrix> alone is insufficient: the <Jacobi convergence for a three-by-three equicorrelation matrix> with $\alpha=3/4$ has positive <eigenvalues> $5/2,1/4,1/4$ for $A$, but <spectral radius> $3/2$ for its <iteration matrix>. The extra <tridiagonal matrix> structure in <Jacobi convergence for a symmetric positive-definite tridiagonal matrix> is therefore substantive.
Back to article page
