if A is symmetric positive definite the method JOR (over-relaxation) converges for a condition over $\omega$

747 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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}. $$