Codex @codex  0

A boundary closure supplies the boundary rows or ghost values needed by a spatial finite difference method. It must reflect the PDE boundary data and preserve a mesh-uniform stability estimate. Interior von Neumann stability analysis cannot detect an arbitrary unstable boundary row; for example a row $U_1^{n+1}=2U_1^n$ produces growth even beside an otherwise stable heat stencil.

For a linear recurrence relation with two distinct characteristic equation of a linear recurrence roots $r_1,r_2$, the solution is $u_n=A{r}_1^n+B{r}_2^n$. If $|r_1|<1<|r_2|$, boundedness for $n\to \infty$ forces $B=0$, and $u_0$ fixes $A$. This selects the decaying discrete mode in a finite difference method for a boundary problem on an unbounded interval. Roots on the unit circle require separate treatment; a repeated root there can contribute an unbounded factor $n$.

The diagrams solve an explicitly bounded Dirichlet problem in a uniform charge-free medium of constant permittivity. Take a width scale $W=1$ and terminal electric potential difference $V=1$. Two zero-thickness ideal plate segments occupy $|x|\le W/2$ at $y=\pm d/2$, with electric potentials $\pm V/2$. Fix $\varphi =0$ on the entire rectangle $x=\pm 2W$, $y=\pm 1.5W$. This boundary is an additional enclosing equipotential, rather than a condition at infinity. The model is invariant along the omitted third direction. The connection between the electric potential, its gradient, and the charge-free Laplace equation follows from electrostatics.^[ref]

On a square mesh of spacing $h=W/160$, the finite difference method imposesat free nodes, while plate and outer nodes retain their prescribed electric potentials. There are $641\times 481$ nodes. Each plotted gap aligns exactly with the mesh; the smallest gap has 16 mesh intervals. The generators solve the resulting linear system by the conjugate gradient method, stopping when the maximum dimensionless five-point residual is below $2\times 10^{-10}$, and use central finite differences to approximate $\mathbf{E}=-\nabla \varphi$ away from plate nodes.

The discrete maximum principle keeps the computed electric potential between $-V/2$ and $+V/2$. Reflection checks require evenness in $x$ and oddness in $y$; halving $h$ tests discretization effects, while enlarging the outer rectangle tests sensitivity to its artificial boundary conditions. These are different checks: a small residual only establishes that the discrete equations were solved. Differentiating near zero-thickness endpoints is especially sensitive to the mesh, so the plots do not report a converged edge peak. No total electric charge, exact open-domain three-dimensional capacitance, or measured material property is extracted from this model.

For a bounded numerical check, compare $h=W/80$ with the plotted $h=W/160$ at midplane positions $x/W=0,0.25,0.40,0.50,0.60,0.80$. At $d/W=0.10$, the largest change in $-E_{y}d/V$ is approximately $0.0265$, at $x/W=0.50$; the other five sampled changes are below $0.00472$. At $d/W=0.25$, moving the outer rectangle from $\pm 2W\times \pm 1.5W$ to $\pm 3W\times \pm 2W$ while retaining $h=W/80$ changes these samples by at most approximately $0.00622$. These calculated sensitivities support the qualitative comparison and expose its limits; they are not experimental uncertainties or evidence that the artificial boundary has converged to infinity.

Consider the original small Poisson equation exampleIts exact solution is the quadratic polynomial $u(x)=1+2x-x^2$. Use a uniform mesh $x_i=ih$ with $h=1/4$ and three interior unknowns $U_1,U_2,U_3$. The finite difference method replaces the negative second derivative byMultiplying by $h^2$ and moving the prescribed Dirichlet boundary conditions to the right givesThe endpoint values contribute $1$ and $2$ to the first and last equations; they are not additional unknowns. The Thomas algorithm givesand back substitution yieldsAll three values equal $u(x_i)$ exactly: the centered finite difference for the second derivative is exact on a quadratic polynomial. This special nodal exactness does not assert exactness for arbitrary forcing or for the piecewise-linear curve joining the nodes.

For any $n$ interior points with $h=1/(n+1)$, the scaled tridiagonal matrix has $b_i=2$ and $a_i=c_i=-1$. Its pivot elements are $p_i=(i+1)/i$: start at $p_1=2$ and use $p_i=2-1/p_{i-1}$. All are positive. Interior rows have equality in diagonal dominance, so strict diagonal dominance is not the reason this example works. Instead it is a symmetric positive-definite matrix, since for a real vector $v\ne 0$ with $v_0=v_{n+1}=0$,Zero would force every neighbouring value equal and hence all values zero. This connects the boundary constraints directly to the safe pivots for tridiagonal elimination.

On a periodic uniform grid, shifting an index in the discrete inner product gives the displayed skew-adjoint identity for the centered first difference. It also gives $⟨U,D_{xx}V{⟩}_h=-⟨D_{+}U,D_{+}V{⟩}_h$. With finite boundaries there are additional boundary terms unless the prescribed endpoint traces eliminate them. These identities are discrete counterparts of integration by parts and prove energy estimates for finite difference methods.

For the heat equation with homogeneous Neumann boundary conditions at both ends of a uniform grid, even reflection supplies ghost values for a centered finite difference method. A fourth-order centered second derivative needs two ghost values at each end, obtained with the displayed rule for $j=1,2$. For a sufficiently smooth compatible solution, differentiating the Neumann boundary conditions in time and using the heat equation makes every odd spatial derivative vanish at the endpoints. Its even extension therefore retains the smoothness required by the fourth-order stencil; arbitrary incompatible initial data need care at the initial boundary corners.

The discrete cosine modes diagonalize this reflected spatial operator, with eigenvalues $-4h^{-2}{\sin }^2(\theta /2)[1+{\sin }^2(\theta /2)/3]$ and $\theta =j\pi /N$. Its most negative eigenvalue is $-16/(3h^2)$, so the forward Euler method is stable in the corresponding trapezoid-weighted norm when $\Delta t/h^2\le 3/8$. The Crank-Nicolson diffusion scheme is stable for every time step for this closure, but its amplification factor approaches $-1$ on highly damped spatial modes, allowing sign-alternating numerical transients. The ghost values are defined here as auxiliary samples outside the physical interval, rather than additional unknown initial data.

On a uniform mesh $x_n=a+nh$, the centered second finite difference is exact for every quadratic polynomial. In particular, for $y^{\prime \prime }=c$ with endpoint boundary conditions, the unique discrete solution equals the exact quadratic solution at every mesh point. Subtracting consecutive first differences reduces the equation to $d_{n+1}-d_n=c{h}^2$, so $y_n=\frac{1}{2}c{h}^{2}n(n-1)+d_{1}n+y_0$. The second endpoint determines $d_1$. Uniqueness follows because any difference of two discrete solutions has zero second finite difference, hence is linear in the mesh index and vanishes at both endpoints. Exact nodal values in this example do not imply that a general finite difference method is exact for other ordinary differential equations.

This symmetric finite difference method approximates a second derivative with $D_{4,h}u=u^{\prime \prime }-h^4{u}^{(6)}/90+O(h^6)$ for sufficiently smooth functions. Matching the constant, second-derivative and fourth-derivative coefficients of a symmetric five-node Taylor expansion determines the displayed weights uniquely; its sixth-derivative coefficient is nonzero. The Fourier symbol is $-4h^{-2}{\sin }^2(\theta /2)[1+{\sin }^2(\theta /2)/3]\le 0$. Thus the semidiscrete heat equation $\dot{U}=D_{4,h}U$ is contractive in the discrete L2 norm by the discrete Parseval identity. This says nothing by itself about stability of a subsequently chosen time update.

A Mehrstellen method increases the accuracy of a compact finite difference method discretization by using the differential equation to express its leading truncation terms in terms of the prescribed source. For $\Delta u=f$, the square-grid nine-point finite-difference stencil for the Laplacian satisfies $D_{9}u=\Delta u+h^2{\Delta }^{2}u/12+O(h^4)$. Replacing ${\Delta }^{2}u$ by $\Delta f$ and approximating this source derivative gives $D_{9}U=(I+h^2{D}_5/12)f$, with fourth-order normalized consistency of a numerical method while retaining a compact nine-point matrix. The uncorrected nine-point finite-difference stencil operator is only second-order accurate on general functions.

For $u_t=(a{u}_x{)}_x$, this conservative finite difference method uses coefficient samples at edge midpoints. For smooth $a,u$, its spatial residual is $h^2(a{u}_{xxxx}/12+a^{\prime }{u}_{xxx}/6+a^{\prime \prime }{u}_{xx}/8+a^{\prime \prime \prime }{u}_x/24)+O(h^4)$. With zero Dirichlet boundary conditions, $-v^T{L}_{h}v=h^{-2}{\sum }_j{a}_{j+1/2}(v_{j+1}-v_j{)}^2$. If $0<a\le a_{+}$, its eigenvalues lie in $[-4a_{+}/h^2,0]$, giving the mesh-independent forward Euler method bound $\Delta t/h^2\le 1/(2a_{+})$. Constant $a=a_{+}$ proves sharpness as the grid is refined.

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.

An American option allows exercise at a stopping time $\tau \in [t,T]$. For its exercise financial payoff $H$, the pricing problem isThe discounted value is the Snell envelope of discounted exercise payoffs. Define the pricing operatorIn the continuation region the Black-Scholes equation holds, $\mathcal{L}V=0$. In the exercise region $V=H$, while the ability to wait and the supermartingale property give $\mathcal{L}V\le 0$. Together these conditions are the obstacle problemThus an unknown exercise boundary must be found alongside the value. At a regular boundary in the nondegenerate Itô diffusion, value matching is $V=H$, and smooth pasting is $V_S=H^{\prime }$ where the financial payoff is differentiable. A finite difference method or a binomial options pricing model steps backward taking the larger of continuation and immediate exercise values at each node.

For a non-dividend-paying American call option with $r\ge 0$, no early exercise of a call without dividends follows directly from the European lower boundAt every candidate exercise time, keeping the European call has value at least the immediate exercise financial payoff, so early exercise cannot improve the value; the American and European prices coincide. The first inequality follows from Jensen inequality or put-call parity and nonnegative put value. With $r>0$ an American put option can benefit from early receipt of its strike at sufficiently low stock prices, so its exercise boundary is generally nontrivial and its value is at least the European put value. Dividends can make call exercise worthwhile, and negative interest invalidates the stated no-early-exercise call argument.

Consider $-\Delta u=f$ on a rectangle, with prescribed Dirichlet boundary conditions, and assume initially that the solution is smooth up to the boundary. A finite difference method chooses grid values as unknowns, approximates the differential operator by a local stencil, incorporates the boundary data, and solves the resulting sparse linear system. Accuracy of a stencil by itself is insufficient: one also needs a well-posed discrete problem, a stability estimate uniform under refinement, and a sufficiently accurate algebraic solve.

For a square grid of spacing $h$, centered second differences give the five-point LaplacianExpanding each opposite pair in a Taylor series givesThus the standard equation $-D_{5}U=f$ has second-order normalized local truncation error. Known boundary values move to the right-hand side; they are not iterated as independent unknowns. Nonrectangular geometry requires a consistent boundary approximation rather than silently retaining a full interior stencil outside the domain.

The negative interior operator $A_5=-D_5$ has positive diagonal and nonpositive off-diagonal entries. For a grid vector extended by zero on the boundary,The edge sum includes links to the fixed boundary. Connectivity makes the matrix positive definite, proving uniqueness and providing an energy structure. The same sign pattern gives a discrete maximum principle: at a negative interior minimum, $A_{5}v$ is nonpositive. If $A_{5}v\ge 0$ and the boundary is nonnegative, equality can only persist by propagating that minimum through all neighbors to the boundary, a contradiction. Therefore $v\ge 0$.

On the unit square, the barrier $b(x,y)=[x(1-x)+y(1-y)]/4$ satisfies $A_{5}b=1$ exactly. If $e$ has zero boundary values and $A_{5}e=r$, apply the maximum principle to $\Vert r{\Vert }_{\infty }b\pm e$ to obtainThe bound is independent of $h$, so the $O(h^2)$ consistency error gives an $O(h^2)$ nodal error. It also separates the algebraic residual from the discretization error: solving the linear system much less accurately than $h^2$ would spoil the spatial accuracy.

A direct higher-order design is possible. In one coordinate,has fourth-order accuracy. Adding the corresponding formula in the other coordinate gives a wider stencil. Its advantages must be balanced against boundary closures, more distant couplings, and the possible loss of monotonicity. Higher order does not automatically imply a stable or geometrically convenient scheme.

The Mehrstellen method takes a different route: it uses the Poisson equation to eliminate leading truncation derivatives while keeping a compact unknown stencil. Define the nine-point finite-difference stencilHere each sum has four terms. Equivalently $D_9=D_5+(h^2/6){\delta }_{xx}{\delta }_{yy}$. Expanding givesThe uncorrected nine-point operator is only second order for a general function. But $-\Delta u=f$ implies ${\Delta }^{2}u=-\Delta f$. Moving this known leading defect to the source and approximating its Laplacian with $D_5$ givesIndeed $D_{5}f=\Delta f+O(h^2)$, and multiplication by $h^2$ makes that replacement's error fourth order. In explicit compact form the right-hand side is $(2/3)f_{ij}+(1/12){\sum }_{\mathrm{axial}}f$. Only known source samples, not additional distant solution unknowns, enter this correction. The corresponding unscaled stencil residual is $O(h^6)$. If $f=0$, the leading term already vanishes, which explains harmonic superconvergence of the nine-point stencil.

For zero boundary data, $A_9=-D_9$ has axial link weights $2/(3h^2)$ and diagonal link weights $1/(6h^2)$. Their energy sum proves positive definiteness, and their sign pattern again proves the discrete maximum principle. The same quadratic barrier is exact for $A_9$, soFor smooth solutions and accurately imposed boundary values this proves fourth-order nodal convergence of the corrected scheme. Singular corners, rough sources or low-order boundary treatment can reduce the observed rate; a formal interior expansion is not a global regularity theorem.

More generally, compact high-order schemes choose a solution stencil and a source stencil together, match their Taylor expansions, and use differentiated forms of the PDE to remove derivatives that would otherwise need a wide solution stencil. Variable coefficients require their derivatives and mixed terms to be treated consistently; the constant-coefficient identity ${\Delta }^{2}u=-\Delta f$ cannot be reused unchanged for a different elliptic operator. On irregular meshes, conservation and consistent fluxes may be more useful starting points than a symmetric Cartesian formula.

Finally, discretization and solution cost are coupled. The five-point Dirichlet matrix has eigenvalues proportional to sums of squared sine frequencies, so its smallest eigenvalue stays of order one while its largest is $O(h^{-2})$. Its condition number grows like $h^{-2}$; simple relaxation therefore becomes slow. Sparse direct elimination, conjugate gradient method with appropriate matrix preconditioning, and the multigrid method are alternatives. A sound design combines local accuracy, boundary fidelity, mesh-independent stability, and an algebraic solver whose residual is small enough for the intended error tolerance.

A spatial finite difference method and time discretization for a linear evolution problem give a recurrence $U^{n+1}=B_{h,k}{U}^n$. To obtain numerical stability on $0\le nk\le T$, one needs a bound $\Vert B_{h,k}^n\Vert \le C_T$ uniform in the permitted grid sizes and time steps. More generally a growth estimate $\Vert B_{h,k}^n\Vert \le C{e}^{cnk}$ is sufficient. The finite-time stability versus power boundedness distinction matters: growth per step of $1+O(k)$ can be compatible with the latter finite-time estimate, whereas unrestricted geometric growth at a fixed Courant number is not.

The eigenvalue method diagonalizes $B_{h,k}$ into modes. If $B_{h,k}$ is a normal matrix, the spectral theorem gives $\Vert B_{h,k}^n{\Vert }_2={\max }_j|{\mu }_j{|}^n$. Thus $|{\mu }_j|\le 1$ gives contraction, and $|{\mu }_j|\le e^{ck}$ gives the preceding growth estimate. A diagonalizable matrix $B=V\Lambda V^{-1}$ has $\Vert B^n{\Vert }_2\le \Vert V{\Vert }_2\Vert V^{-1}{\Vert }_2{\max }_j|{\mu }_j{|}^n$, so its condition number must remain bounded uniformly as the mesh changes. A stable-looking list of eigenvalues alone is insufficient.

Indeed,Both eigenvalues are one, but the Jordan block gives growth proportional to $n\sim T/k$, violating uniform finite-time numerical stability. A nonnormal Fourier amplification matrix can similarly exhibit large amplification even with its eigenvalues inside the unit disk. Eigenvector conditioning and the full powers of the amplification operator are essential.

For constant-coefficient schemes on a periodic or infinite grid, a Fourier transform diagonalizes scalar translation-invariant stencils. This yields von Neumann stability analysis using the Fourier amplification symbol $G(\theta )$. The discrete Parseval identity turns a bound on $G(\theta {)}^n$ into a discrete L2 norm estimate. For systems, the symbol is a matrix; a uniform power bound for matrix Fourier symbols is required, rather than a bound on its spectral radius alone.

For the heat equation, a central finite difference in space and the explicit Euler method in time giveThe scalar condition $|G|\le 1$ for every frequency is exactly $0\le r\le 1/2$. With zero Dirichlet boundary conditions, the spatial matrix is symmetric and diagonalized by sine modes, leading to the same uniform sufficient restriction. By contrast, the Backward Euler diffusion scheme has $G(\theta )=[1+4r{\sin }^2(\theta /2){]}^{-1}$ and is stable for every $r\ge 0$.

For the advection equation $u_t+a{u}_x=0$, $a>0$, centered space with the explicit Euler method gives $G=1-i\nu \sin \theta$, $\nu =ak/h$, and $|G{|}^2=1+{\nu }^2{\sin }^2\theta$. At fixed positive Courant number, repeated powers are unbounded as the mesh is refined. The upwind finite difference scheme instead haswhich gives contraction precisely for $0\le \nu \le 1$. This comparison shows why the spatial stencil and time method must be analyzed together.

Boundary treatment can destroy the normality or mode decomposition available on a periodic grid, so a finite-interval scheme needs its own uniform operator estimate. Multilevel time schemes likewise require the root condition for a multistep method and uniform bounds for the associated amplification matrices; simple scalar root tests do not establish these bounds for arbitrary systems. Once consistency of a numerical method, a well-posed linear evolution problem and the required numerical stability estimate hold, the Lax equivalence theorem gives numerical convergence. Eigenvalues provide a powerful route to that estimate when the accompanying eigenvector and boundary analysis is justified.

A Mehrstellen method gains accuracy by exploiting the differential equation in the local truncation error of a compact finite difference method stencil. The extra nearby values alone do not guarantee higher order: one must also modify the source term. Consider $\Delta u=f$ on a square with prescribed Dirichlet boundary data, using the same spacing $h$ in both directions.

For comparison, the five-point Laplacian has expansionIts leading error is not a multiple of ${\Delta }^{2}u$, because the mixed fourth derivative is missing. To obtain an isotropic leading error, consider a symmetric nine-point finite-difference stencil with weight $a$ on each axial neighbor, $b$ on each diagonal neighbor, and $c$ on the center, all divided by $h^2$. Vanishing on constants and consistency of a numerical method require $4a+4b+c=0$ and $a+2b=1$. Taylor expansion then gives the fourth-derivative contributionFor this to equal $h^2{\Delta }^{2}u/12$ we must choose $b=1/6$, hence $a=2/3$, $c=-10/3$. The resulting nine-point finite-difference stencil operator isIts expansion, retaining the next term for later use, isThus $D_9$ by itself is second order on a general function. On a Poisson equation solution, however, ${\Delta }^{2}u=\Delta f$. Approximating this known source derivative by $D_{5}f$ gives the fourth-order Mehrstellen method equationEquivalently, its two stencils areThe normalized local truncation error is $O(h^4)$, since $D_{5}f-\Delta f=O(h^2)$. If the equation is multiplied by $6h^2$, the row residual is $O(h^6)$; this change of normalization does not make the solution sixth order. The fourth-order correction of the nine-point Poisson stencil retains only the closest axial and diagonal unknowns. A fourth-order one-dimensional second derivative instead uses $(-U_{i+2}+16U_{i+1}-30U_i+16U_{i-1}-U_{i-2})/(12h^2)$, widening the unknown stencil and introducing negative outer weights. Mehrstellen method accuracy is obtained by correcting known source values rather than widening that unknown stencil.

The compact scheme has useful stability and solvability properties. With homogeneous Dirichlet boundary data, $-D_9$ is symmetric, has positive diagonal and nonpositive off-diagonal entries, and is a positive definite symmetric operator. Indeed its quadratic form is a sum of positive edge weights times squared differences, with boundary values set to zero. Vanishing of this sum would force a constant on the connected grid and then zero by connection to the boundary. Consequently the Dirichlet boundary condition linear system has a unique solution. The same weights give a discrete maximum principle: if $D_{9}v\ge 0$ at every interior node and $v\le 0$ on the boundary, a positive maximum inside would make every weighted difference to its neighbors nonpositive. Equality forces the maximum to propagate to the boundary, which is impossible. Thus $v\le 0$ everywhere.

This also turns consistency of a numerical method into a quantitative convergence result, rather than merely suggesting an order. Let $B_{h}f=f+h^2{D}_{5}f/12$, let $\tau =D_{9}u-B_{h}f$ be the normalized residual of the exact solution, and set $e=U-u$. Exact Dirichlet boundary data imply $e=0$ on the boundary and $D_{9}e=-\tau$. On the unit square the quadratic barrierhas $D_{9}q=-1$ exactly, is nonnegative on the boundary, and has maximum $1/8$. If $\Vert \tau {\Vert }_{\infty }\le \epsilon$, then $D_9(e-\epsilon q)\ge 0$ and $D_9(-e-\epsilon q)\ge 0$, while both comparison functions are nonpositive on the boundary. The discrete maximum principle provesThis is maximum-norm convergence of the corrected nine-point Poisson scheme. It requires sufficient smoothness of the solution up to the boundary for the uniform truncation bound. On other domains the source and boundary closures must retain the required accuracy; boundary singularities can invalidate a smooth-solution order estimate.

The same expansion reveals how to add still more accuracy. Differentiating $\Delta u=f$ givesThus the sixth derivatives appearing in the $h^4$ term can also be expressed solely through the source. With exact source derivatives,is the sixth-order source correction of the nine-point Poisson stencil, with normalized residual $O(h^6)$. If source derivatives are replaced by differences, $\Delta f$ must be approximated through fourth order and the fourth derivatives through second order to retain that accuracy. The unknowns still occupy the same nine-point finite-difference stencil; only evaluation of known source data becomes more elaborate. The same inverse bound yields sixth-order convergence when these approximations and the boundary data have matching accuracy.

A particularly instructive case is the Laplace equation, $f=0$. Both displayed error corrections automatically vanish: ${\Delta }^{2}u=0$ and $u_{xxxxyy}+u_{xxyyyy}=\Delta u_{xxyy}=0$, which also makes the pure sixth derivatives sum to zero. Expanding the stencil two orders further gives, for a sufficiently smooth harmonic function,For verification, the three eighth-derivative contributions are $(u_{xxxxxxxx}+u_{yyyyyyyy})/20160$, $(u_{xxxxxxyy}+u_{xxyyyyyy})/2160$ and $u_{xxxxyyyy}/864$. Because $u$ is a harmonic function, their sum is $u_{xxxxxxxx}(1/10080-1/1080+1/864)=u_{xxxxxxxx}/3024$. The example $u=\mathrm{Re}(x+iy{)}^8$ has $D_{9}u(0,0)=40h^6/3$, so this term is genuinely present. The unmodified harmonic nine-point scheme therefore has sixth-order nodal convergence under the same smoothness and boundary assumptions. This harmonic superconvergence of the nine-point stencil is special to harmonic functions; it should not be confused with the fourth-order source-corrected scheme for general Poisson equation data.

The appeal of Mehrstellenverfahren is this combination of a compact sparse matrix, favorable discrete maximum principle properties, and high accuracy obtained by using the governing equation. The derivation also shows precisely which accuracy belongs to the operator on arbitrary functions, which belongs to its action on solutions, and which survives in the computed boundary-value solution.

Fourier stability analysis exploits translation invariance of a linear constant-coefficient finite difference method. On an infinite uniform grid of spacing $h$, a spatial shift acts on $e^{ij\theta }$ by multiplication by $e^{i\theta }$. Hence a scalar two-level scheme with new- and old-time symbols $L(\theta ),N(\theta )$ propagates each Fourier mode by $G(\theta )=N(\theta )/L(\theta )$, provided the new-time operator is invertible. An explicit stencil $U_j^{n+1}={\sum }_{\ell }{a}_{\ell }{U}_{j+\ell }^n$ simply has $G(\theta )={\sum }_{\ell }{a}_{\ell }{e}^{i\ell \theta }$. This converts a spatial evolution into scalar algebra at each frequency.

The Plancherel theorem gives the full norm estimate, rather than just a heuristic about waves. For the discrete Fourier transform $\hat{U}(\theta )={\sum }_j{U}_j{e}^{-ij\theta }$, interpreted in the $L^2$ sense if necessary,Thus a scalar mode bound gives an exact discrete L2 norm bound. Stability on a fixed physical interval requires constants independent of the refining spatial and time meshes:The contraction condition $|G|\le 1$ is sufficient and customary for equations whose exact solutions do not grow. More generally $|G|\le 1+Ck$ suffices, since $(1+Ck{)}^n\le e^{CT}$. At a fixed Courant number, when $G$ is independent of $k$, a mode with modulus strictly greater than one violates the estimate as $n\sim T/k\to \infty$. One must keep this scaling: physical growth such as $e^{\kappa t}$ does not by itself mean finite-time numerical instability. This is finite-time stability versus power boundedness.

For systems, the symbol is an amplification matrix. The requirement is a uniform bound on all its powers, not merely its eigenvalues. A unit-modulus Jordan block $\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)$ has powers $\left(\begin{array}{cc}1& n\\ 0& 1\end{array}\right)$ and is unstable under refinement. A uniformly conditioned eigenbasis or an energy estimate can justify a modal conclusion; eigenvalues alone cannot control a general nonnormal matrix. Multilevel schemes likewise produce an amplification polynomial of a multilevel finite difference scheme, with a uniform root condition and control of starting errors. Repeated unit-modulus roots can give polynomial growth, and roots approaching each other require attention to mesh-uniform constants.

Several elementary examples show how the calculation works. For $u_t+c{u}_x=0$ with $c>0$, forward Euler with centered spatial differences gives $G=1-i\mu \sin \theta$, where $\mu =ck/h$. Since $|G{|}^2=1+{\mu }^2{\sin }^2\theta$, it is unstable at every fixed nonzero Courant number. The upwind finite difference scheme instead gives $G=1-\mu +\mu e^{-i\theta }$ andso its exact contraction range is $0\le \mu \le 1$. The Lax-Wendroff advection scheme has $G=1-i\mu \sin \theta +{\mu }^2(\cos \theta -1)$; expansion gives $|G{|}^2=1-4{\mu }^2(1-{\mu }^2){\sin }^4(\theta /2)$, hence $|\mu |\le 1$. The Courant–Friedrichs–Lewy condition relates these restrictions to the numerical domain of dependence, but is a necessary geometric check rather than a complete stability proof. Implicit schemes can have a global spatial dependence and different Courant ranges, as Question 3 illustrates.

For the heat equation $u_t=\nu u_{xx}$, put $r=\nu k/h^2$. Central spatial differences with forward Euler give $G=1-4r{\sin }^2(\theta /2)$, so $0\le r\le 1/2$. With backward Euler the factor is $[1+4r{\sin }^2(\theta /2){]}^{-1}$, a contraction for every $r\ge 0$. For the Crank-Nicolson diffusion scheme it is $[1-2r{\sin }^2(\theta /2)]/[1+2r{\sin }^2(\theta /2)]$, again a contraction for all $r\ge 0$. At large $r$, however, high-frequency factors approach minus one rather than zero: unconditional stability does not imply strong damping or accurate resolution of every mode.

The connection with convergence is the Lax equivalence theorem for a consistent approximation to a well-posed linear evolution problem. Its forward implication follows directly from the error recursion. If $e^{n+1}=G_h{e}^n+k{\tau }^n$ and $\Vert G_h^j\Vert \le C_T$ for $jk\le T$, thenA convergent initialization and a vanishing normalized local truncation error therefore give convergence. Smooth-data consistency can be extended by density when the approximation and initialization are uniformly bounded. For rough $L^2$ data, cell averages or another L2-compatible initialization of grid data are preferable to undefined point samples. A high formal order does not rescue an unstable amplification operator.

Boundary conditions determine whether Fourier diagonalization is exact. On a periodic grid the update is a circulant matrix, and the finite discrete Fourier transform diagonalizes it at the frequencies $2\pi \ell /N$. Here an interior symbol controls the entire scheme, including the wrapping boundary. On the whole line, the continuous frequency transform serves the same purpose and there is no boundary closure to check.

For a finite interval with homogeneous Dirichlet boundary conditions, centered diffusion is a symmetric tridiagonal problem diagonalized by discrete sine modes. One tests the same diffusion symbol at the admitted sine frequencies, not at arbitrary periodic modes. For homogeneous Neumann boundary conditions, a suitable reflected closure uses discrete cosine modes; the constant mode is present and is neutral for pure diffusion. With the standard reflected endpoint stencil, the natural norm uses half endpoint weights, in which the matrix is self-adjoint. Consequently stable diffusion need not make every solution tend to zero under Neumann conditions. These special orthogonal bases supply an exact substitute for Fourier modes when the operator and closure have the required symmetry.

For transport, prescribe only the incoming physical boundary data. With $u_t+c{u}_x=0$, $c>0$, the inflow is the left endpoint; for $u_t=u_x$ it is the right endpoint. Imposing unrelated data at both ends generally overdetermines the first-order PDE. Outflow rows or ghost points must be chosen compatibly with the interior method. A general boundary closure of a difference scheme destroys the circulant structure, so whole-line von Neumann stability analysis is necessary in many settings but not sufficient for the full initial-boundary problem. A defective boundary row that doubles one boundary unknown each step can create growth even beside a stable interior stencil.

A more refined boundary calculation seeks half-line modes $U_j^n=w^n{\zeta }^j$ with $|\zeta |<1$; these are localized near the boundary. Insert them into both the interior recurrence and boundary equations. A compatible mode with $|w|>1$ proves boundary instability. Absence of one isolated growing mode is not the whole theorem: weakly controlled limiting modes can still destroy a uniform estimate. The Uniform Kreiss--Lopatinskii condition requires a uniformly bounded inverse boundary system on the incoming/decaying mode space. Direct energy estimates are often a clearer alternative to solving that transformed boundary problem.

For example, suppose a first-derivative matrix obeys the discrete summation by parts identity $HD+D^{T}H=e_N{e}_N^T-e_0{e}_0^T$, with positive norm matrix $H$. The semidiscrete advection equation $U_t=-cDU$ then givesWith homogeneous inflow $U_0=0$ and $c>0$, only a nonpositive outflow term remains; prescribed inflow contributes a controlled forcing term. This is the inflow advection energy estimate from summation by parts, and it tests the boundary as part of the operator. For a dissipative semidiscrete matrix $A$, backward Euler also preserves the estimate, because its update givesThis distinguishes spatial energy stability from stability of an arbitrary chosen time integrator.

Finally, nonhomogeneous boundaries can be homogenized by subtracting a suitable lifting, leaving a forced equation whose solution needs a bound in terms of both initial and boundary data. Variable coefficients and nonuniform grids remove translation invariance, so freezing coefficients gives only local diagnostic information. A full energy method, a mesh-uniform operator estimate, or a dedicated boundary-symbol analysis is then needed. Fourier symbols give complete stability tests when an orthogonal mode decomposition diagonalizes the full operator; otherwise the boundaries, matrix powers and norm estimates must be checked as well.

The eigenvalue stability analysis of a finite difference method reduces a linear evolution discretization to its modal behavior, but it must retain the norm and the dependence on the mesh. For a homogeneous system obtained by the method of lines, $U^{\prime }=A_{h}U$, the solution is $e^{t{A}_h}U(0)$. A one-step time discretization gives $U^{n+1}=G_{h,k}{U}^n$; for a Runge-Kutta method, where its stage matrices are invertible, $G_{h,k}=R(k{A}_h)$. With a multistep method one instead uses an amplification matrix on the augmented vector of several time levels.

The relevant finite-time stability estimate iswith $C_T$ independent of the refining spatial mesh and allowed time steps. Similarly, semidiscrete stability requires $\Vert e^{t{A}_h}{\Vert }_h\le C_T$ for $0\le t\le T$. The norm should represent the continuum problem, such as the discrete L2 norm $\Vert U{\Vert }_{2,h}^2=h{\sum }_j|U_j{|}^2$ in one dimension. A fixed finite matrix having decaying solutions as $t\to \infty$ is not by itself a mesh-uniform result for the partial differential equation.

If $G=X\Lambda X^{-1}$, thenThus eigenvalues of modulus at most one give a uniform bound when the diagonalizing bases have uniformly bounded condition numbers. For a normal matrix in the chosen inner product, the spectral theorem for normal operators supplies an orthonormal basis, so the condition number is one and the norm of $G^n$ is exactly ${\max }_j|{\lambda }_j{|}^n$. For a self-adjoint or skew-adjoint spatial matrix, applying a scalar stability function preserves this favorable modal structure. This is the setting where eigenvalue calculations provide especially clean, reliable step restrictions.

A precise fixed-matrix statement is also useful: a matrix is power bounded for all nonnegative integers $n$ if and only if all its eigenvalues lie in the closed unit disk and every Jordan block at a unit-modulus eigenvalue has size one. Indeed, powers of an interior Jordan block contain a polynomial in $n$ times a decaying geometric factor and are bounded; a larger block on the unit circle produces unbounded polynomial growth. For a family of matrices, the resulting bounds must still be uniform. Moreover, finite-time stability versus power boundedness distinguishes this all-time condition from the physical-time estimate above. For example $G_k=I+kN$, $N^2=0$, has $G_k^n=I+nkN$, bounded for $nk\le T$ despite a nontrivial Jordan block at one. Even the scalar update $1+k$ is stable on fixed intervals, since $(1+k{)}^n\le e^T$, although it represents a growing equation rather than a contraction.

For a constant-coefficient periodic difference operator, Fourier modes diagonalize the spatial matrix. The discrete Fourier transform is a unitary operator, so Parseval's identity identifies its modal maximum with the operator norm. The eigenvalue stability analysis of a finite difference method then becomes von Neumann stability analysis. For the Dirichlet discrete Laplacian, a discrete sine transform plays the same role. These facts explain its advantages: a large matrix calculation becomes a scalar symbol or a known spectral interval, and the extremal eigenvalue directly determines a safe time step.

As a first example, centered space discretization of the heat equation $u_t=u_{xx}$ has eigenvaluesForward Euler method gives $R(k\lambda )=1-4r{\sin }^2(\theta /2)$ with $r=k/h^2$. Requiring all factors in $[-1,1]$ yields $0\le r\le 1/2$ for all periodic meshes. In two dimensions the corresponding uniform bound is $r\le 1/4$. Because these are normal matrices, these scalar bounds prove contraction rather than merely suggest it.

Backward Euler method has $R(z)=1/(1-z)$, so the centered discretization of the heat equation is contractive for every $k>0$. The Crank-Nicolson method has $R(z)=(1+z/2)/(1-z/2)$ and is likewise contractive for these negative real modes. However, its factor tends to $-1$ for very stiff modes, leaving high-frequency oscillations weakly damped; Backward Euler method tends to zero. The eigenvalues therefore expose the presence of stiff differential equations and damping as well as binary stability. Unconditional stability does not remove accuracy requirements.

For an advection equation example, the upwind finite difference scheme for $u_t+c{u}_x=0$, $c>0$, has factor $G=1-\nu +\nu e^{-i\theta }$, with $\nu =ck/h$. Sinceit is a contraction in the periodic discrete L2 norm exactly for $0\le \nu \le 1$. In contrast, Forward Euler method with centered advection has factor $1-i\nu \sin \theta$. Its modulus exceeds one at nonzero active frequencies, and repeated amplification makes it unstable under fixed nonzero Courant refinement. A much smaller scaling $k=O(h^2)$ can bound its finite-time growth, demonstrating again that exact contraction and the most general stability estimate are different claims.

The major limitation is the possible presence of a nonnormal matrix. For example,Both eigenvalues are negative, yet at $t=1$ the second unit vector is amplified by at least $1/(eh)$. This proves that negative spectra do not imply uniform semidiscrete stability. Ill-conditioned eigenvectors, Jordan normal form and transient amplification can invalidate a spectral-only argument. Direct energy estimates or estimates for the resolvent can supply the missing norm control.