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 Galerkin coarse-grid operator is obtained by composing interpolation, the fine operator and residual restriction. With $R=c{P}^T$, $c>0$, and positive-definite $A_h$, the exact coarse-grid correction $I-P(R{A}_{h}P{)}^{-1}R{A}_h$ is the energy-orthogonal projection onto the complement of the coarse space. Indeed it annihilates every vector $Pz$, and its corrected error $e^{\prime }$ satisfies $P^T{A}_h{e}^{\prime }=0$. These identities explain why compatible transfers remove representable smooth error rather than merely averaging an approximate solution.

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.

The multigrid method addresses a characteristic failure of single-grid relaxation: its cheapest updates rapidly remove oscillatory error but barely change smooth error. For example, the one-dimensional Poisson equation matrix has diagonal $2/h^2$. The weighted Jacobi method with weight $\omega$ has Fourier error factorAt low physical frequency, $\theta =O(h)$ and this factor is $1-O(h^2)$, requiring $O(h^{-2})$ sweeps for a fixed error reduction. With $\omega =2/3$, high grid frequencies $\pi /2\le |\theta |\le \pi$ are multiplied by at most $1/3$ in modulus. Smooth error on a fine mesh is well represented on a coarser mesh, where it is relatively more oscillatory and hence cheaper to remove. These two complementary mechanisms motivate smoothing and coarse-grid correction.

Write the discrete problem as $A_h{u}_h=f_h$. For an approximation $v_h$, the residual is $r_h=f_h-A_h{v}_h$ and the error $e_h=u_h-v_h$ satisfies $A_h{e}_h=r_h$. It is this error equation that is transferred to a coarse grid; restricting the approximate solution alone would not solve the missing error. With prolongation $P$ and restriction $R$, solveFor nested Cartesian grids with $H=2h$, linear interpolation copies a coarse value at a coincident fine node and averages the two nearest coarse values at an intermediate node. Its two-dimensional counterpart is bilinear interpolation. Full-weighting restriction uses weights $(1,2,1)/4$ in one dimension andin two dimensions. With these choices $R=2^{-d}{P}^T$ in ordinary coordinate inner products. A Galerkin coarse-grid operator is $A_H=R{A}_{h}P$; alternatively one can rediscretize the PDE on the coarse mesh when that choice remains compatible with the transfers.

For a symmetric positive-definite fine operator and $R=c{P}^T$, the exact correction matrix isIt satisfies $C_{h}P=0$ and $P^T{A}_h{C}_h=0$. Thus it removes the coarse-space component of the error and is an orthogonal projection in the energy inner product. With pre- and post-smoothing matrices $S_{\mathrm{pre}},S_{\mathrm{post}}$, the exact two-grid error matrix is $S_{\mathrm{post}}{C}_h{S}_{\mathrm{pre}}$. Effective smoothing on the complementary space and accurate coarse representation of smooth error are both needed for contraction.

A concrete harmonic calculation makes the mechanism quantitative. On the one-dimensional constant-coefficient problem, couple the two harmonics $\theta$ and $\theta +\pi$, put $s={\sin }^2(\theta /2)$ and $c=1-s$, and use the above transfers. Linear interpolation has harmonic weights $(c,s{)}^T$, while the fine operator has diagonal symbol $4\mathrm{diag}(s,c)/h^2$. Therefore its Galerkin correction on this pair isOne pre- and one post-sweep of weighted Jacobi with $\omega =2/3$ gives $E=SCS$, $S=\mathrm{diag}(1-4s/3,1-4c/3)$. This rank-one matrix has eigenvalues zero andThe two-grid Poisson factor with weighted Jacobi is therefore mesh-independent in this model. A periodic constant nullspace must first be removed; a Dirichlet problem has no such nullspace. This is evidence for the design, not a claim that the same factor applies to every PDE or every smoother.

The geometric multigrid V-cycle replaces the exact coarse solve by one recursively defined coarse cycle. A complete implementation on level $\ell$ proceeds as follows:

Boundary values of the solution are imposed on the fine level; the error equation has homogeneous boundary conditions when those values were already imposed exactly. Residuals must be computed after pre-smoothing, not before. The zero initialization on each recursive error solve makes the cycle an error correction rather than an accidental addition of an old coarse solution. For an energy-symmetric cycle usable in conjugate gradient method, choose compatible adjoint transfers and symmetric smoothing, such as forward Gauss-Seidel before correction and its backward sweep afterward.

With bounded stencil size and fixed sweep counts, a sweep, residual calculation or transfer costs $O(N_{\ell })$. Uniform coarsening gives $N_{\ell -1}\approx 2^{-d}{N}_{\ell }$, soIf the full V-cycle has an error reduction factor $q<1$ independent of mesh size, reducing an arbitrary initial algebraic error by a factor $\epsilon$ takes $O(\log (1/\epsilon ))$ cycles and $O(N\log (1/\epsilon ))$ work. Linear work per cycle alone does not prove the mesh-independent factor; it rests on the smoothing and approximation properties just illustrated. Full multigrid starts on a coarse mesh, interpolates its solution to each successive finer mesh, and uses a few cycles per level. When the interpolation accuracy and cycle contraction match the discretization error, this reaches discretization-level accuracy in $O(N)$ work.

Performance depends on the operator. Strong anisotropy can leave error oscillatory in one direction but weakly penalized by the differential operator, defeating point smoothing; line or plane relaxation and selective coarsening address this. Large coefficient jumps demand compatible coarse spaces. Nonrectangular meshes motivate algebraic rather than purely geometric coarsening. Nonlinear problems use a full-approximation formulation instead of the linear residual correction verbatim. Singular Neumann or periodic operators need right-hand-side compatibility and consistent nullspace treatment on every level. Multigrid is fast because its components address different error scales, not because coarsening alone guarantees a good solver.

A multigrid method combines a fine-grid smoother with a coarse-grid correction. Starting with $u_h$, apply a few smoothing iterations, compute $r_h=b_h-A_h{u}_h$, restrict this residual to a coarser grid, and approximately solve $A_H{e}_H=R{r}_h$. Prolong the coarse error and update $u_h\leftarrow u_h+P{e}_H$, then post-smooth. The coarse solve is itself performed recursively, with a direct solve at the coarsest level; visiting each coarser level once gives a V-cycle. The smoother damps rapidly varying error, while error smooth on the fine grid is efficiently represented and corrected on the coarse grid.

For ordinary Jacobi, $\omega =1$, the highest-frequency sine-product error has eigenvalue approaching $-1$, not zero. In particular for the discrete Poisson equation it is $-\cos (\pi h)$, whose magnitude approaches one. This nearly alternating error changes sign between sweeps but is barely damped, and ordinary coarse-grid restriction does not represent it well. Thus with the standard point-Jacobi smoother and coarse-grid transfers one chooses $\omega \ne 1$, usually $0<\omega <1$, for fast multigrid convergence. For example $\omega =2/3$ makes the extreme high-frequency eigenvalue approach $-1/3$. Convergence of Jacobi as a standalone iteration is therefore insufficient to guarantee that it is an effective smoother. This conclusion concerns that standard multigrid choice; other smoothers or specially designed transfers can change it.