Consider solving a linear system $A \boldsymbol{x}=\boldsymbol{b}$. Let $D$ be the diagonal matrix whose diagonal entries are those of $A,-L$ be the strictly lower triangular part of $A$, and $-U$ be the strictly upper-triangular part of $A.$ The weighted Jacobi method updates as$$ \boldsymbol{x}^{(k)}=w\left(D^{-1}(L+U) \boldsymbol{x}^{(k-1)}+D^{-1} \boldsymbol{b}\right)+(1-w) \boldsymbol{x}^{(k-1)} $$
Suppose that $A$ is symmetric and positive definite, and $D=a I$ for a positive constant $a$ and an identity matrix $I$. Find the condition of $w$, in the form $\alpha<w<\beta$, that guarantees the convergence of the weighted Jacobi method.
In case that the system matrix $A$ is of symmetric positive-definite type, it is easy to show that $C_{\omega}=I-\omega D^{-1} A$ is the iteration matrix and according to Wikipedia, convergence is guaranteed for$$ \rho\left(C_{\omega}\right)<1 \quad \Longleftrightarrow \quad 0<\omega<\frac{2}{\lambda_{\max }\left(D^{-1} A\right)} $$where $\lambda_{\max }$ is the maximal eigenvalue.
Is there any proof why $\omega$ less than the above expression guarantees that spectral radius will be less than $1$?
$\endgroup$ 41 Answer
$\begingroup$Note that if $\lambda$ is eigenvalue of A, the $1 + \lambda$ is eigenvalue of $I + A$ (for proof: Show that 1 + $\lambda$ is an eigenvalue of $I + A$).
If $\lambda_1$ to $\lambda_n$ are eigenvalues of $w*D^{-1}A$, then $1 - \lambda_{i}$'s are eigenvalues of $C_w$So in your problem, 2nd part means that $\rho\left(wD^{-1}A\right)<2$ and therefore,
$\rho\left(C_{\omega}\right) = \rho\left(I - wD^{-1}A\right)<1$ iff $\rho\left(wD^{-1}A\right)<2$
$\endgroup$ 2
