Equivalently, the weighted Jacobi method takes a weighted average of the old vector and its full Jacobi method update: . If , its iteration matrix multiplies that eigenvector by . For the diagonal-4 Jacobi iteration for a three-variable tridiagonal system, the factors are and ; a Poisson equation smoothing parameter must not be inferred from this different matrix.
Consider the five-point discretization of the uniformly elliptic operator with on the unit square, with homogeneous Dirichlet boundary conditions. Let and . In the discrete sine basis, the weighted Jacobi method has iteration matrix eigenvaluesEach one-dimensional second difference contributes , and the matrix diagonal is , giving the displayed ratio. Its value is strictly between zero and two for every finite grid. Thus puts every iteration eigenvalue strictly inside the unit circle and gives convergence on every grid. At , the highest-frequency factors approach minus one as , so convergence holds while high-frequency smoothing is poor.
For the five-point Dirichlet Poisson matrix, weighted Jacobi iteration has sine-mode multiplier . Call a mode high-frequency if at least one cosine is nonpositive. Then the sum lies in , so for the multiplier lies in . This uniform damping makes the iteration a useful smoother for a multigrid method, even though low-frequency multipliers approach one on fine grids. Balancing and shows why 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 .
For the centered second-difference matrix with diagonal and off-diagonals , the weighted-Jacobi eigenvalues areThe method converges for every grid size exactly when .
Multiplying both and by leaves and the weighted Jacobi method unchanged. Thus the same formula applies to the positive second-difference matrix with diagonal and neighboring entries , the finite difference form of the one-dimensional Poisson equation with Dirichlet boundary conditions. Its eigenvectors have components , and has eigenvalues . At , upper-half modes have factors between and , 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]
CS267: Supplemental Notes for Lecture 17 — How Multigrid Damps High Frequencies by James Demmel. Error eigenvector expansion, coefficient 1/3 + (2/3) cos(jπ/2^i), and concluding upper-half-frequency attenuation statement
For the one-dimensional Dirichlet second-difference grid, high sine modes have eigenvalues , with and . Let and be the smallest and largest of these . Convexity gives attenuation . Balancing its endpoint values with opposite signs gives the displayed exact minimax choice. For odd , ; for even , , and always . Only in the large-grid or uniform-in-grid limit do these become , .
Articles by others on the same topic
There are currently no matching articles.