Weighted Jacobi method

With relaxation parameter $\omega$, weighted Jacobi updates byIts iteration matrix is $H_{\omega }=I-\omega D^{-1}A$.

Equivalently, the weighted Jacobi method takes a weighted average of the old vector and its full Jacobi method update: $x^{(k+1)}=(1-\omega )x^{(k)}+\omega x_{\mathrm{Jacobi}}^{(k+1)}$. If $Bv=\lambda v$, its iteration matrix multiplies that eigenvector by $1-\omega +\omega \lambda$. For the diagonal-4 Jacobi iteration for a three-variable tridiagonal system, the factors are $1-\omega$ and $1-\omega \pm \omega \sqrt{2}/4$; a Poisson equation smoothing parameter must not be inferred from this different matrix.

For the five-point discretization of $-\Delta +c$ on the unit square, the weighted iteration eigenvalues are $1-\omega [4{\sin }^2(\pi kh/2)+4{\sin }^2(\pi lh/2)+c{h}^2]/(4+c{h}^2)$. A fixed parameter converges for every mesh when $0<\omega \le 1$, but $\omega =1$ poorly damps the highest frequencies.

For the five-point Dirichlet Poisson matrix, weighted Jacobi iteration has sine-mode multiplier $1-\omega +(\omega /2)(\cos {\theta }_r+\cos {\theta }_s)$. Call a mode high-frequency if at least one cosine is nonpositive. Then the sum lies in $[-2,1]$, so for $\omega =4/5$ the multiplier lies in $[-3/5,3/5]$. This uniform damping makes the iteration a useful smoother for a multigrid method, even though low-frequency multipliers approach one on fine grids. Balancing $|1-2\omega |$ and $|1-\omega /2|$ shows why $4/5$ is the minimax parameter for this high-frequency interval. The two-dimensional high-frequency set gives a different optimum from the familiar one-dimensional value $2/3$.

For the centered second-difference matrix with diagonal $-2$ and off-diagonals $1$, the weighted-Jacobi eigenvalues areThe method converges for every grid size exactly when $0<\omega \le 1$.

Multiplying both $A$ and $b$ by $-1$ leaves $D^{-1}A$ and the weighted Jacobi method unchanged. Thus the same formula applies to the positive second-difference matrix $T_n$ with diagonal $2$ and neighboring entries $-1$, the finite difference form of the one-dimensional Poisson equation with Dirichlet boundary conditions. Its eigenvectors have components $\sin (jk\pi /(n+1))$, and $D^{-1}{T}_n$ has eigenvalues $1-\cos (k\pi /(n+1))$. At $\omega =2/3$, upper-half modes have factors between $-1/3$ and $1/3$, while low-frequency factors remain close to one on fine grids. This explains why the weighted Jacobi method helps a multigrid method by reducing oscillatory errors, even when it is a slow solver on its own.^[ref]

For modes with $k/(n+1)\in [1/2,1]$ and large $n$, the worst attenuation factor isIt is minimized by $\omega =2/3$, for which ${\mu }_{\omega }=1/3$.

For the one-dimensional Dirichlet second-difference grid, high sine modes have eigenvalues $1-\omega t_k$, with $t_k=1-\cos (k\pi /(n+1))$ and $k\ge \lceil (n+1)/2\rceil$. Let $a$ and $b$ be the smallest and largest of these $t_k$. Convexity gives attenuation $\max (|1-\omega a|,|1-\omega b|)$. Balancing its endpoint values with opposite signs gives the displayed exact minimax choice. For odd $n$, $a=1$; for even $n$, $a=1+\sin (\pi /[2(n+1)])$, and always $b=1+\cos (\pi /(n+1))$. Only in the large-grid or uniform-in-grid limit do these become ${\omega }_{\ast }=2/3$, ${\mu }_{\ast }=1/3$.