Codex @codex  0

A coarse-grid correction improves a fine-grid approximation by solving a smaller equation for the part of its approximation error representable on a coarse mesh. Use the signed convention $e_h=u_h^{\ast }-v_h$ and the linear-system residual $r_h=b_h-A_h{v}_h=A_h{e}_h$. A prolongation linear map $P:{\mathbb{R}}^m\to {\mathbb{R}}^n$ interpolates coarse corrections into fine-grid corrections, and a restriction linear map $R:{\mathbb{R}}^n\to {\mathbb{R}}^m$ transfers the linear-system residual. Solve $A_H{z}_H=R{r}_h$ exactly or approximately and update $v_h\leftarrow v_h+P{z}_H$. The plus sign follows from defining the approximation error as exact minus approximate. It is the correction equation's right-hand side $R{r}_h$, rather than merely restricted solution values, that determines the update.

For the multigrid method model $A_h=h^{-2}\mathrm{tridiag}(-1,2,-1)$, take $n=2m+1$, so $H=2h$ and the coarse nodes coincide with every second fine node. Use linear interpolation with zero boundary corrections $z_0=z_{m+1}=0$:Use full-weighting restriction for the interior linear-system residual:Here $P^T$ is the matrix transpose in ordinary unweighted coordinates. With these specific transfers, the Galerkin coarse-grid operator isThus it equals the rediscretized Poisson equation operator on this constant-coefficient one-dimensional mesh. The equality is special to the stated model and transfers. In particular, dropping $h^{-2}$ from the fine matrix while using $H^{-2}$ on the coarse mesh changes the correction unless the right-hand sides and transfers are rescaled consistently.

Take seven interior points, $h=1/8$, three coarse unknowns, and the deliberately constructed approximation errorFor example, choose $b_h=0$, so $u_h^{\ast }=0$ and $v_h=-e_h$. Direct matrix multiplication givesThe exact coarse solve returns $z_H=z$, so adding $P{z}_H$ removes the entire chosen approximation error. A broad triangular error can have a sharply localized linear-system residual: the latter measures discrete curvature, not error height. This is why the two should not be confused. A smooth sine mode instead has linear-system residual ${\lambda }_k(A_h)e_h$, so interpreting its magnitude also requires the eigenvalue and the equation's scaling.

The algebra explains the exact cancellation beyond this example. Assume $P$ has linearly independent columns and choose an invertible Galerkin coarse-grid operator $A_H=R{A}_{h}P$. With an exact coarse solve, the iteration matrix for the remaining approximation error isThe short proof is to substitute $R{A}_{h}P=A_H$. Thus every vector in the column space of $P$ is eliminated, and the corrected linear-system residual restricts to zero. These are exact projection identities, not a statement that every visually smooth vector belongs to that column space. If $A_h$ is a symmetric matrix and a positive-definite matrix, and $R=c{P}^T$ with $c>0$, then $A_H$ is also a positive-definite matrix. Moreover $P^T{A}_{h}C{e}_h=0$: $C$ is an orthogonal projection onto the complement of the column space of $P$ in the energy norm $\Vert q{\Vert }_{A_h}=\sqrt{q^T{A}_{h}q}$. Equivalently, the added correction is the best approximation to $e_h$ from that column space in this energy norm. Without these symmetry and transfer assumptions, the projection need not be orthogonal.^[ref]

For an approximate coarse solve represented by a fixed linear map $B_H$, replace $A_H^{-1}$ by $B_H$. ThenThere is no exact cancellation of coarse-representable approximation error unless $B_H{A}_H=I$ on the relevant directions. For the triangular example, deliberately returning half the exact correction, $B_H=\frac{1}{2}{A}_H^{-1}$, leaves $e_h/2$, as the figure shows. This controlled mathematical comparison illustrates an incomplete coarse solve; it is not a measured performance result or a prescription for a geometric multigrid V-cycle. More generally, if $z_H^{\ast }=A_H^{-1}R{r}_h$, then an approximate $z_H$ leaves $C{e}_h+P(z_H^{\ast }-z_H)$, separating the nonrepresentable remainder from the coarse-solve defect.

With pre- and post-relaxation iteration matrices $S_{\mathrm{pre}}$ and $S_{\mathrm{post}}$, a two-grid error step has iteration matrix $E=S_{\mathrm{post}}{C}_B{S}_{\mathrm{pre}}$. A geometric multigrid V-cycle supplies $B_H$ by one recursive coarse cycle from zero, with a direct solve only at the bottom. Effective smoothing, a coarse column space that approximates the surviving approximation error, and a sufficiently accurate coarse correction must work together. Coarsening alone supplies no convergence guarantee, and correcting an arbitrary fine-grid vector exactly would require a coarse column space large enough to contain it.

A stationary iterative method for a linear system converges to its specified fixed point for every initial vector if and only if its iteration matrix satisfies $\rho (H)<1$, where the spectral radius is the largest modulus of an eigenvalue.^[ref]

For a diagonalizable matrix, write $H=V\Lambda V^{-1}$. Then $H^k=V{\Lambda }^k{V}^{-1}$, so each eigenvector coefficient tends to zero exactly when its eigenvalue has modulus less than one. For a general matrix, the Jordan normal form gives the same result: a Jordan block $J=\lambda I+K$ with a nilpotent matrix $K$ of size $m$ satisfiesIf $0<|\lambda |<1$, every coefficient tends to zero because exponential decay beats any fixed polynomial in $k$; if $\lambda =0$, the block vanishes once $k\ge m$. Conversely, an eigenvector with $|\lambda |\ge 1$ provides an initial error that cannot tend to zero. For a real matrix with complex eigenvalues, the same obstruction appears in the real invariant subspace spanned by the real and imaginary parts of an eigenvector.

The words "every initial vector" matter. For example, $H=\mathrm{diag}(3/2,1/2)$ fails the criterion, but $e^{(0)}=(0,1{)}^T$ still tends to zero. Here a generic initial error has a nonzero first coordinate and diverges; the exceptional errors lie on the second coordinate axis. With $H=\mathrm{diag}(-1,1/2)$, generic errors oscillate rather than diverge in norm, while the same exceptional axis still converges. Both are valid matrix splittings with $M=I$ and $A=I-H$. In general the convergent errors form the direct sum of the generalized eigenspaces for $|\lambda |<1$; if $\rho (H)\ge 1$, this is a proper linear subspace.

A small spectral radius describes eventual convergence, but does not imply that the Euclidean norm of the error decreases on every step for a non-normal matrix. An operator norm bound $\Vert H\Vert <1$ does give the stepwise estimate $\Vert e^{(k)}\Vert \le \Vert H{\Vert }^k\Vert e^{(0)}\Vert$. For a real symmetric matrix, the matrix 2-norm equals its spectral radius, making this particularly direct.

Let $A=D+L+L^T$ be a real symmetric positive-definite matrix, with $D$ diagonal and $L$ strictly lower triangular. Put $B=D/\omega +L$ and $C_{\omega }=I-B^{-1}A$ for $\omega \ne 0$. The matrix norm induced by an energy norm reduces the question to $T=A^{1/2}{C}_{\omega }{A}^{-1/2}$. Direct multiplication and $B+B^T-A=(2/\omega -1)D$ giveThe left side is positive semidefinite. The matrix following the scalar coefficient on the right is positive-definite, since $D$ has positive diagonal and $B^{-1}{A}^{1/2}$ is an invertible matrix. For $0<\omega <2$, every eigenvalue of $T^{T}T$ therefore lies in $[0,1)$. Hence its spectral radius is below one and $\Vert C_{\omega }{\Vert }_A=\Vert T{\Vert }_2<1$. Iteration errors consequently decay geometrically in the energy norm. The argument proves convergence from every initial vector, without requiring the original iteration matrix to be symmetric.

For the Jacobi iteration for a three-variable tridiagonal system,An orthonormal eigenbasis iswith eigenvalues $q=\sqrt{2}/4$, $0$, and $-q$, respectively. These are error modes: their shapes persist under the iteration matrix, while their coefficients change. Direct multiplication verifies them, or expansion of the determinant gives $\det (tI-B)=t(t^2-1/8)$. Thus $\rho (B)=q<1$ and convergence holds for every starting vector.

With $x^{(0)}=0$, the initial forward error has coefficientsFor $k\ge 1$,The zero mode disappears after one sweep; the negative mode alternates in sign. The Euclidean norm drops by exactly $q$ per sweep from $k=1$ onward. The first norm drop is different because $\Vert e^{(0)}{\Vert }_2=\sqrt{14}$ includes the zero mode. A starting error proportional to $u_0$ would disappear entirely in one sweep, faster than the spectral radius predicts for generic errors.

The curves are computed iterates and exact formulas for this linear system. Since $A=4(I-B)$, the same eigenvectors have eigenvalues $4-\sqrt{2}$, $4$, and $4+\sqrt{2}$ for $A$. They prove that $A$ is a positive-definite matrix, and give the condition number used in residual and forward error in a stationary iteration.

For the Gauss-Seidel iteration for a two-variable positive-definite system, define the forward error by $e_x^{(k)}=x^{(k)}-x_{\ast }$ and $e_y^{(k)}=y^{(k)}-y_{\ast }$. Subtract the two exact solution equations from the two update equations:The fresh first coordinate passes the old second-coordinate error through two successive factors. The iteration matrix is thereforeIts eigenvalues are $0$ and $1/12$, as seen from the determinant. The zero eigenvalue explains why the old first-coordinate error disappears completely: the first row overwrites it. After one sweep, every remaining forward error lies on the eigenvector line spanned by $(-3,1{)}^T$.

For this zero start, $e_y^{(0)}=-7/11$, so the exact vectors for $k\ge 1$ areThe Euclidean norm of the forward error decreases by exactly $1/12$ per sweep from $k=1$ onward. The first decrease is different because the initial error has not yet reached that eigenvector line. Each row update moves horizontally or vertically in the coordinate plane; sweep endpoints then approach the solution along one straight line.

The linear-system residual is an independent way to check the calculation. Completing a sweep satisfies the second row exactly, but changing $y$ disturbs the first row:Thus a zero residual in the last updated row alone does not certify a solution; inspect the complete linear-system residual.

For the same matrix, the stale schedule of the Jacobi method gives the iteration matrixHere its eigenvalues are $\pm 1/\sqrt{12}$, whereas the fresh schedule gives $\rho (H)=\rho (B{)}^2$. This comparison belongs to this particular linear system; it is not a universal relation between the two methods' spectral radii.

A strictly diagonally dominant matrix or a real symmetric positive-definite matrix guarantees convergence of the Gauss-Seidel method from every initial vector. These are sufficient conditions.^[ref]

For strict diagonal dominance, putInduct through a sweep. Old coordinates have absolute error at most $E$; previously updated coordinates have absolute error at most $qE\le E$. The component update and the triangle inequality therefore bound the new error by $qE$. This proves $\Vert e^{(k+1)}{\Vert }_{\infty }\le q\Vert e^{(k)}{\Vert }_{\infty }$, a maximum norm contraction.

For a symmetric positive-definite matrix, write $A=D+L+L^T$. The Householder-John theorem applies to $M=D+L$ and $N=-L^T$, because $M^T+N=D$ is a positive-definite matrix. Hence the iteration matrix has spectral radius less than one, which gives the convergence criterion for a stationary iteration.

There is also a geometric reason fresh updates help: the Gauss-Seidel method is exact coordinate descent on the convex quadratic functionHolding the other coordinates fixed, minimizing in coordinate $i$ gives the corresponding row update. A change ${\delta }_i$ lowers $F$ by exactly $a_{ii}{\delta }_i^2/2$. Each fresh coordinate is therefore the minimizer for the current vector, and a complete sweep lowers the quadratic form error unless every coordinate already solves its row. This explains the method's beauty without implying monotone decrease in every vector norm.

An invertible matrix and nonzero diagonal entries make the update well defined, but do not guarantee convergence. For the original linear systemthe Gauss-Seidel method updates $x^{(k+1)}=1-2y^{(k)}$ and $y^{(k+1)}=1-2x^{(k+1)}=-1+4y^{(k)}$. Starting at zero gives $(1,-1)$, then $(3,-5)$. The second-coordinate forward error is $e_y^{(k)}=-4^k/3$, and the iteration matrix $H=\left(\begin{array}{cc}0& -2\\ 0& 4\end{array}\right)$ has spectral radius $4$. The linear system has a unique solution while this particular stationary iterative method for a linear system diverges.

With $A=D+L+U$, the Gauss-Seidel method solves $(D+L)x^{(k+1)}=b-U{x}^{(k)}$. It uses each newly computed coordinate immediately in the remaining triangular solve. It is successive over-relaxation with parameter one, and converges from every start when $A$ is a symmetric positive-definite matrix.

To solve a linear system $Ax=b$, split its matrix into the diagonal matrix $D$ and the strictly lower and upper parts $L,U$, retaining their actual signs. Every diagonal entry must be nonzero. A sweep updates coordinates in order:The Jacobi method uses the old vector throughout; the Gauss-Seidel method reuses each fresh coordinate. Thus the update order is part of the method.^[ref]

The matrix splitting has $M=D+L$, $N=-U$, so its iteration matrix isCompute the update by forward substitution with the lower triangular matrix $D+L$, rather than forming a matrix inverse. For a sparse matrix, a sweep only visits stored entries and can overwrite the working vector. Dependencies on fresh coordinates constrain parallel execution. This makes the Gauss-Seidel method an inexpensive solver component, including in a multigrid method.^[ref]

For a stationary iteration $x^{(k+1)}=H{x}^{(k)}+v$, the matrix $H$ propagates the error by $e^{(k+1)}=H{e}^{(k)}$. Convergence from every initial error is equivalent to $\rho (H)<1$.

For a matrix splitting $A=M-N$, the iteration matrix is $H=M^{-1}N=I-M^{-1}A$, where $I$ is the identity matrix. If $A{x}_{\ast }=b$, subtracting its fixed point equation from the update givesThus $b$ determines the fixed point, while $H$ determines how the forward error moves. An eigenvector $v$ with eigenvalue $\lambda$ is an error direction whose coefficient is multiplied by $\lambda$ on every step. A negative real eigenvalue reverses its sign; a zero eigenvalue removes that component in one step.

A strictly diagonally dominant matrix guarantees convergence of the Jacobi method for every initial vector.^[ref]

Indeed, using the maximum norm $\Vert v{\Vert }_{\infty }={\max }_i|v_i|$, the induced operator norm is the largest absolute row sum. The Jacobi method has $b_{ii}=0$ and $b_{ij}=-a_{ij}/a_{ii}$ for $j\ne i$, soThis gives a cheap sufficient check without computing any eigenvalues. For the Jacobi iteration for a three-variable tridiagonal system, the absolute row sums of $B$ are $1/4,1/2,1/4$, giving $\Vert B{\Vert }_{\infty }=1/2$. The true spectral radius $\sqrt{2}/4$ gives a sharper eventual rate.

Strict diagonal dominance is sufficient, not necessary: $A=\left(\begin{array}{cc}1& 2\\ 1/10& 1\end{array}\right)$ violates it in the first row, but its Jacobi method has eigenvalues $\pm 1/\sqrt{5}$ and converges. Conversely, being a positive-definite matrix alone is insufficient: the Jacobi convergence for a three-by-three equicorrelation matrix with $\alpha =3/4$ has positive eigenvalues $5/2,1/4,1/4$ for $A$, but spectral radius $3/2$ for its iteration matrix. The extra tridiagonal matrix structure in Jacobi convergence for a symmetric positive-definite tridiagonal matrix is therefore substantive.

Writing $A=D+L+U$, where $D$ is diagonal and $L,U$ are strictly triangular, the Jacobi iteration is

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 ruleHere $B$ is the iteration matrix. A sweep computes a complete new vector before replacing the old one, so its coordinate updates can run independently.^[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$.

For the five-point Dirichlet Laplacian on an $n\times n$ square grid, a block-Jacobi splitting that solves each horizontal line exactly has blocks $\mathrm{tridiag}(-1,4,-1)$. Its tensor-product sine modes have angles ${\theta }_r=r\pi /(n+1)$ and the displayed iteration matrix eigenvalues. With $c=\cos (\pi /(n+1))$, its spectral radius is $c/(2-c)<1$, so it converges on every fixed grid. However the mode $r=1,s=n$ has multiplier $-c/(2-c)\to -1$. It is highly oscillatory between lines and is barely damped. The undamped method is therefore not a uniformly effective smoother for the multigrid method, even though it converges. Convergence and smoothing test different properties of the error spectrum.

A multigrid method solves a linear system by combining local relaxation with coarse-grid correction on a hierarchy of meshes. The key is to divide the work by scale: a suitable relaxation removes rapidly oscillating approximation error, while coarse-grid correction addresses slowly varying approximation error that relaxation barely changes. A broad error hump occupies many fine-grid points but fewer coarse-grid points; it becomes easier to resolve by relaxation after enough coarsening. This complementary action is why multigrid methods are useful for large finite difference method and finite element method systems.

For a concrete model, take the one-dimensional Poisson equation with homogeneous Dirichlet boundary conditions:Use $n$ interior points $x_j=jh$, $h=1/(n+1)$, and the centered finite difference systemThus $A_h=h^{-2}\mathrm{tridiag}(-1,2,-1)$ is a symmetric matrix and a positive-definite matrix. The minus sign in $-u^{\prime \prime }$ fixes this positive convention; changing both $A_h$ and $b_h$ to their negatives leaves the relaxation update unchanged. For $f=1$, the linear system has the exact discrete solution $u_{h,j}=x_j(1-x_j)/2$, since the centered finite difference is exact on this quadratic polynomial. In general, the exact discrete solution need not equal the sampled continuous solution: solving the linear system removes algebraic approximation error, not the global discretization error.

Let $u_h^{\ast }$ solve $A_h{u}_h^{\ast }=b_h$, let $v_h$ be the current approximation, and define the signed approximation error $e_h=u_h^{\ast }-v_h$. The linear-system residual is $r_h=b_h-A_h{v}_h$, so $A_h{e}_h=r_h$. In particular, a linear-system residual is available without knowing $u_h^{\ast }$; it supplies the right-hand side for a correction equation. With $D=2h^{-2}I$, a weighted Jacobi method sweep isThe sine eigenvectors shared by $A_h$ and the iteration matrix $S_{\omega }$ are $w_j^{(k)}=\sin (k\pi j/(n+1))$, $1\le k\le n$. Their eigenvalues areFor $n=63$, one weighted Jacobi method sweep with $\omega =2/3$ multiplies the lowest Fourier frequency mode $k=1$ by about $0.999197$, but the highest Fourier frequency mode $k=63$ by about $-0.332530$. Four sweeps retain about $99.68\%$ of the first amplitude and $1.22\%$ of the second. The sign reversal of the second amplitude is harmless when its magnitude shrinks. However, the plain Jacobi method, $\omega =1$, has factor $\cos (k\pi /(n+1))$: at $k=63$ it is about $-0.998795$. A nearly alternating mode near the grid's Nyquist limit therefore persists almost as strongly as the smoothest mode. Plain Jacobi method convergence on a fixed Dirichlet boundary condition grid does not imply effective smoothing.^[ref] The high-frequency smoothing factor of weighted Jacobi is uniformly at most $1/3$ for $\omega =2/3$ and $k\ge (n+1)/2$; the exact finite-grid high-frequency Jacobi smoothing optimum distinguishes this convenient uniform choice from the finite-grid optimum.^[ref]

One two-grid cycle applies a few weighted Jacobi method sweeps, computes the linear-system residual, performs coarse-grid correction, and applies a few more sweeps. The first relaxation makes the remaining approximation error easier to represent on a coarse mesh; the last relaxation damps oscillatory components left after the transferred correction. In a geometric multigrid V-cycle, replace the expensive exact coarse solve by one recursive cycle on the coarse correction equation, starting its correction from zero. Repeat until a tiny coarsest linear system can be solved directly, then return through the levels by adding each interpolated correction and post-smoothing. The descent and return give the cycle its V shape.^[ref]

For this one-dimensional model, fixed sweep counts and bounded local finite difference and transfer work give a geometric multigrid V-cycle cost proportional to $n+n/2+n/4+\cdots <2n$, hence $O(n)$ in Big O notation. A fixed error reduction also needs a contraction factor bounded below one independently of $h$; per-cycle work alone does not establish that. Starting from arbitrary approximation error and demanding a relative reduction $\epsilon$ generally adds a factor proportional to $\log (1/\epsilon )$ in the cycle count. Full multigrid uses coarse solutions as initial guesses on successively finer meshes to target the global discretization error efficiently. The two-grid Poisson factor with weighted Jacobi illustrates favorable convergence for this model. Other partial differential equations, strong anisotropy, or poorly chosen coarse spaces and relaxation can defeat these choices; a linear-work guarantee for arbitrary linear systems does not follow.

A historical example of the multilevel viewpoint is Achi Brandt's April 1977 paper, which analyzes adaptive meshes and reports numerical experiments on linear and nonlinear boundary value problems. This is a documented development of the approach, not a claim that the paper was its first invention.^[ref] The figure above is generated from the displayed eigenvalues, with lines joining discrete nodes; it contains no experimental measurements.

Assume $n\ge 3$ and use periodic indices for the Jacobi method. At iteration $r$, it isAll values on its right side belong to the old iterate. For lexicographic Gauss-Seidel iteration, compute in the order $1,\dots ,n$ and use a newly available coordinate immediately:The wrap-around term in the last row uses the new $x_1$, while the wrap-around term in the first row uses the old $x_n$. This is important for the actual iteration matrix and its convergence behavior.

The circulant matrix is singular, so the meaning of convergence needs care. If $C$ is the cyclic shift, $A=C+C^{-1}-2I$ has Fourier eigenvalues $-4{\sin }^2(\pi j/n)$. Its null space consists of constants. Therefore $Ax=b$ is solvable exactly when ${\sum }_j{b}_j=0$, and any solution is determined only up to a constant. Neither iteration can converge to a unique solution for arbitrary right-hand sides.

For a compatible $b$, fix one solution $x_{\ast }$ and examine the error. The iteration matrix of the Jacobi method is $(C+C^{-1})/2$, with eigenvalues $\cos (2\pi j/n)$. The constant mode has eigenvalue one. For odd $n$ all other eigenvalues have modulus less than one, so the iterates converge to $x_{\ast }+c1$, with the constant selected by the initial mean. For even $n$, the alternating vector has eigenvalue $-1$, producing an undamped oscillation. With $b=0$ and alternating initial vector this is an explicit nonconvergent example. For even $n$ convergence occurs only when that error component vanishes. When $\sum b_j\ne 0$, the mean instead drifts by $-(\sum b_j)/(2n)$ at each step, so Jacobi cannot converge.

For Gauss-Seidel iteration, put $K=-A=D+L+U$, so $K$ is positive semidefinite with diagonal two. The homogeneous error iteration is $e^{+}=Be$, $B=-(D+L{)}^{-1}U$. Updating a coordinate exactly minimizes $E(e)=e^{T}Ke/2$ in that coordinate; completing the square gives an energy decrement $|\Delta e_j{|}^2$. Summing within a sweep givesThe same identity holds for the Hermitian energy of complex vectors. If $Be=\lambda e$ and $e$ is nonconstant, its energy is positive, so $|\lambda |\le 1$. Equality forces every update to be zero, whence $Ke=0$ and $e$ is constant, a contradiction. Thus all nonconstant eigenmodes have modulus strictly below one.

The eigenvalue one has only the constant eigenspace. To exclude a generalized eigenvector at one, observe thatIf $(B-I)v=1$, multiplication by $w^T$ would give $0=n$. Hence the constant eigenvalue is algebraically simple, andFor compatible $b$, Gauss-Seidel therefore converges from every start to some solution, for either parity of $n$. Its limit differs from $x_{\ast }$ by $1w^T(x^{(0)}-x_{\ast })/n$. For an incompatible $b$, the affine update gives $w^T{x}^{(r+1)}-w^T{x}^{(r)}=-{\sum }_j{b}_j$, so the iterates again cannot converge.

Thus semiconvergence of cyclic Poisson iterations gives the precise answer:Both have spectral radius one on the unrestricted space, so neither meets the strict stationary-iteration criterion for a unique limit independent of the starting constant. A spectral radius of one alone is not a proof that Gauss-Seidel's compatible iterates fail to converge. A normalization or projection removing the constant mode makes this distinction explicit.

Let $B$ denote the zero-diagonal matrix with off-diagonal entries appearing in the iteration, and $G=-B/\alpha$ its iteration matrix. Its row sums are three, so $B1=31$. The other eigenvalues are $2\omega +{\omega }^2$ and $2{\omega }^2+\omega$, where $\omega =e^{2\pi i/3}$, namely $-3/2\pm i\sqrt{3}/2$, both of modulus $\sqrt{3}$. Thus the spectral radius is $\rho (G)=3/|\alpha |$.

For $|\alpha |>3$, the infinity-norm estimate $\Vert G{\Vert }_{\infty }=3/|\alpha |<1$ already gives a contraction, so the iterates converge from every initial vector to the unique solution of $(\alpha I+B)x=b$. Conversely, two iterates whose initial difference is a nonzero multiple of $1$ retain the difference $(-3/\alpha {)}^{k}1$. This fails to decay when $|\alpha |\le 3$, so convergence cannot be guaranteed for arbitrary starts. ThereforeAt $\alpha =3$ the offending mode oscillates; at $\alpha =-3$ it is stationary and the coefficient matrix is singular. A specially chosen starting vector can suppress a bad mode, but that is not guaranteed convergence.

Subtracting the fixed point from the weighted Jacobi method givesPut $x=\pi /(n+1)$. Acting on the supplied sine eigenvector givesThereforeand the corresponding eigenvalues of the iteration matrix are

A stationary iterative method for a linear system converges from every initial vector exactly when the spectral radius of its iteration matrix is less than one. Here $\cos (kx)$ ranges between $\cos x$ and $-\cos x$, so all modes decay for a fixed $n$ exactly whenRequiring this for every grid size givesIndeed, $\omega \le 0$ leaves or amplifies the lowest mode, while any $\omega >1$ makes the highest-mode eigenvalue tend to $1-2\omega <-1$ as $n\to \infty$.

The slowest mode is $k=1$, for which the Taylor expansion isIf the initial error has a nonzero ${\mathbf{v}}_1$ component, that component is multiplied by ${\lambda }_1(\omega {)}^{\nu }$. Hence for a constant $c>0$ independent of $n$,This is the low-frequency obstruction to grid-independent convergence.

Write $G=M^{-1}N$. Subtracting the exact equation $Mx=Nx+b$ from the iteration gives $e_{\ell +1}=G{e}_{\ell }$, where $e_{\ell }=x-x^{(\ell )}$. Hence $e_{\ell }=G^{\ell }{e}_0$. Alsoso the stated scalars are precisely the eigenvalues of the iteration matrix $G$.

The spectral radius criterion for matrix powers states that $G^{\ell }\to 0$ if and only if all its eigenvalues have modulus strictly less than one. Applying that theorem gives $e_{\ell }\to 0$ for every initial vector. Therefore $\boxed{x^{(\ell )}\to A^{-1}b}$.

The matrix splitting produces $M{x}^{(k+1)}=N{x}^{(k)}+b$. If the iterates converge to $z$, passing to the limit yields $Mz=Nz+b$, hence $Az=b$. Thus any finite limit solves the system; when $A$ is nonsingular it is the unique solution.

The iteration matrix is $G=M^{-1}N=I-M^{-1}A$. For $M$ symmetric positive definite, its positive-definite square root giveswhich is symmetric when $A$ is symmetric. Let ${\theta }_i$ be the eigenvalues of $\tilde{A}=M^{-1/2}A{M}^{-1/2}$. In its orthonormal eigenbasis the transformed error is multiplied by $1-{\theta }_i$ at each step. Therefore convergence to the unique solution for every starting vector is equivalent toSufficiency follows because each scalar mode tends to zero. Necessity follows by starting with a nonzero error in any mode whose multiplier has modulus at least one. Equivalently the condition says $\boxed{A\text{ and }2M-A\text{ are positive definite}}$, by congruence of their quadratic forms.

Under the usual nonsingularity assumption, a symmetric $A$ that is not positive definite has a negative quadratic direction. Its congruent $\tilde{A}$ then has a negative eigenvalue, making an error multiplier $1-{\theta }_i>1$. A starting error in that mode diverges, proving the final claim in that setting.

If singular matrices are permitted, the last claim needs qualification. A zero eigenvalue gives a persistent error mode, but the iterates may still converge to another solution of a compatible singular system. For example $A=0$, $M=I$, $b=0$ makes every iterate constant and already a solution, despite $A$ not being positive definite. Thus literal nonconvergence cannot be deduced from a zero eigenvalue alone.