0
$\begingroup$

In a Jacobi type of iteration for finding solution to a linear system $Ax=b$, one writes

$$x_i^{(k+1)} = Gx_i^{(k)}+c,$$

where $x_i$ is the $i$-th component of vector $x$ and $G=D^{-1}N$, $c = D^{-1}b$.

Here we take $A=D+N$, with $D$ the diagonal part of $A$ and $N$ the rest of $A$, i.e. $N = A-D$, so that

$$x_i^{(k+1)} = -D^{-1}Nx_i^{(k)}+D^{-1}b$$

There is a theorem which says that if the spectral radius $\rho(A)<1$ then this scheme converges, so I need to show that $D^{-1}N$ has spectral radius less than $1$.

In my case, $A=\begin{bmatrix} -6&1 & 1 & 1 &0 & 0 & 0&\dots& 0 \\ 1 & 1 & -6 & 1 & 1 & 1 &0&\dots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots &\vdots&\ddots&0\\ \vdots & \vdots & \vdots & \vdots & \dots & \dots & \dots&-6 & 1\\ 0 & \dots & 0 & 0 & 0 & 1 & 1 & 1 & -6 \end{bmatrix}$, so

$D=diag\{-6,\dots, -6\}$, $\implies D^{-1}=diag\{-1/6, \dots, -1/6\}$,

and $N=\begin{bmatrix} 0&1 & 1 & 1 &0 & 0 & 0&\dots& 0 \\ 1 & 1 & 0 & 1 & 1 & 1 &0&\dots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots &\vdots&\ddots&0\\ \vdots & \vdots & \vdots & \vdots & \dots & \dots & \dots&0 & 1\\ 0 & \dots & 0 & 0 & 0 & 1 & 1 & 1 & 0 \end{bmatrix}$.

One can evaluate the product $D^{-1}N$ to be

$\begin{bmatrix} 0&-1/6 & -1/6 & -1/6 &-1/6 & -1/6 & -1/6&\dots& -1/6 \\ -1/6 & 0 & -1/6 & -1/6 & -1/6 & -1/6 &-1/6&\dots & -1/6 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots &\vdots&\ddots&-1/6\\ \vdots & \vdots & \vdots & \vdots & \dots & \dots & \dots&0 & -1/6\\ -1/6 & \dots & -1/6 & -1/6 & -1/6 & -1/6 & -1/6 & -1/6 & 0 \end{bmatrix}$

It can be shown that the spectral radius of this product is $1/2$ (if I'm not mistaken). But is there a more elegant way to show that $\rho(D^{-1}N)<1$? I don't really like the direct way of showing this.

$\endgroup$
1
$\begingroup$

The spectral radius of the last shown matrix for $D^{-1}N$ is $(n-1)/6$, where $n\times n$ is the size of the matrix. Thus the spectral radius is larger than $1$ for $n\ge8$.

However, from the previous parts of the question, $D^{-1}N=-\frac{1}{6}J$ where $$J=\begin{pmatrix}0&1&1&1&0&\cdots&0\\1&0&1&1&1&\cdots&0\\&\ddots&0&0&0&\cdots&1\end{pmatrix}$$ i.e., there is a band of 1s on first three off-diagonals on both sides.

For a symmetric matrix, the spectral radius is equal to the largest value of the numerical range, $\{x^*Ax:\|x\|_2=1\}$.

The extent of the numerical range of $J$ is given by maximizing the following expression for $x=(a_1,\ldots,a_n)$ unit, $$\begin{pmatrix}a_1,&\ldots,&a_n\end{pmatrix}\begin{pmatrix}0&1&\cdots&0\cr 1&0&\cdots&1\cr&\ddots\cr0&1&\cdots&0\end{pmatrix}\begin{pmatrix}a_1\cr\vdots\cr a_n\end{pmatrix}=\sum_{|i-j|\le3,i\ne j}a_ia_j$$ Now $$\begin{align*}\sum_{|i-j|\le3,i\ne j}a_ia_j &=2(\sum_{i=1}^{n-1}a_ia_{i+1}+\sum_{i=1}^{n-2}a_ia_{i+2}+\sum_{i=1}^{n-3}a_ia_{i+3})\\ &\le \sum_{i=1}^{n-1}a_i^2+\sum_{i=2}^na_i^2+\sum_{i=1}^{n-2}a_i^2+\sum_{i=3}^na_i^2+\sum_{i=1}^{n-3}a_i^2+\sum_{i=4}^na_i^2\\ &<6\sum_{i=1}^na_i^2=6\end{align*}$$

That is, the spectral radius of this $D^{-1}N$ is less than 1, as required.

$\endgroup$
  • $\begingroup$ Thank you. But can you please provide some details for your last expression? I got tangled in notation: where is the $|i-j|\le 3$ coming from? And the rest of the RHS doesn't seem quite clear yet. $\endgroup$ – sequence Feb 21 at 15:38
  • 1
    $\begingroup$ The $|i-j|\le3$ refers to the three off-diagonals; $i\ne j$ to omit the main diagonal. Now the sum is equivalent to three sums along the diagonals, times two (because there are two diagonals each). The first inequality is the usual $ab\le(a^2+b^2)/2$. $\endgroup$ – Chrystomath Feb 21 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.