2
$\begingroup$

Background:

A generalization of the Jacobi method for solving the system $Ax = b$ is the over-relaxation method (or JOR), which has the following iteration matrix:

$$ B_{J_{\omega}} = \omega B_J + (1 - \omega) I $$

$B_J = I - D^{-1}A$ is the iteration matrix for the Jacobi method (the matrix $D$ is the diagonal of $A$).

I know a iterative method converges if, and only if, its iteration matrix $B$ spectral radius is less than $1$, i.e. $\rho(B) < 1$.

I want to prove:

If $A$ is symmetric positive definite, then the JOR method is convergent if $$0 < \omega < \dfrac{2}{\rho(D^{-1}A)}$$


This question is the theorem 4.4 on the book "Numerical Mathematics", by Alfio Quarteroni - second edition. The book says the result is "immediate" from the information I wrote above, but I can't see it.

$\endgroup$

1 Answer 1

3
$\begingroup$

If $A$ is SPD, then $D^{-1}A$ is diagonalizable and has positive eigenvalues in the interval $(0,\rho]$ with $\rho:=\rho(D^{-1}A)$. Let $\lambda$ and $x$ be an eigen-pair of $D^{-1}A$. Then $$ B_{J_\omega}x=[\omega B_J+(1-\omega)I]x=[\omega (I-D^{-1}A)+(1-\omega)I]x =(1-\lambda\omega)x, $$ so $\mu:=1-\lambda\omega$ and $x$ is an eigen-pair of $B_{J_\omega}$.

We need that $-1<\mu<1$, which (since $0<\lambda$) is equivalent to $$ 0<\omega<\frac{2}{\lambda}. $$ So to confine $\mu$ in this interval for all $\lambda$ in $(0,\rho]$, this leads to the condition $$ 0<\omega<\frac{2}{\rho}. $$

$\endgroup$

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.