Weighted Jacobi Method

1.3k Views Asked by At

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$?

1

There are 1 best solutions below

3
On BEST ANSWER

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$