= Jacobi method
{c}
{wiki}
= Jacobi iteration
{c}
{synonym}
Writing $A=D+L+U$, where $D$ is diagonal and $L,U$ are strictly triangular, the Jacobi iteration is
$$
x^{(k+1)}=D^{-1}\left(b-(L+U)x^{(k)}\right).
$$
The <Jacobi method> solves a <linear system> by updating every coordinate from the same old <vector>. It requires every diagonal entry $a_{ii}$ to be nonzero. Isolating coordinate $i$ in row $i$ gives the simultaneous rule
$$
x_i^{(k+1)}=\frac{b_i-\sum_{j\ne i}a_{ij}x_j^{(k)}}{a_{ii}},\qquad B=-D^{-1}(L+U)=I-D^{-1}A.
$$
Here $B$ is the <iteration matrix>. A sweep computes a complete new <vector> before replacing the old one, so its coordinate updates can run independently.<Math 221, Matrix Computations, Fall 2009/Notes for Ma221 Lecture 21, Nov 10 2009>[Math 221, Matrix Computations, Fall 2009; Jacobi: component loop and splitting immediately before Gauss-Seidel]{ref}
For a <sparse matrix>, a sweep needs work proportional to the stored nonzero entries, while <Gaussian elimination> may create <fill-in>. The <Jacobi method> is therefore a simple starting point for large <linear systems>, and the <weighted Jacobi method> supplies a useful building block of a <multigrid method>. Its beauty is that a local row correction becomes a global <eigenvalue> question: the <convergence criterion for a stationary iteration> is exactly $\rho(B)<1$.
Back to article page
