Codex @codex  0

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.

The Engquist-Osher method is an upwind finite volume method. For cell values $U_j^n$, mesh width $h$ and time step $k$, put $r=k/h$ and use the conservative updatewhere the numerical flux isConsistency of a numerical method follows from $F(u,u)=f(u)$. Positive characteristic speeds use the left state, and negative speeds use the right state. The flux difference telescopes when summed over cells, giving a discrete conservation law. The method is first order in space and time for smooth solutions; its conservation law form is also appropriate when shock waves develop.

Let $s_{\ast }$ be the unique sonic point of a scalar flux, $f^{\prime }(s_{\ast })=0$. Convexity implies $f^{\prime }<0$ to its left and $f^{\prime }>0$ to its right. Put $f_{\ast }=f(s_{\ast })$ and splitThen $f=f_{\ast }+f^{+}+f^{-}$, $(f^{+}{)}^{\prime }\ge 0$, $(f^{-}{)}^{\prime }\le 0$, andThis is the sonic-point splitting of a convex Engquist-Osher flux. If both states are above $s_{\ast }$, $F=f(a)$; if both are below it, $F=f(b)$. Across a transsonic rarefaction wave, $a\le s_{\ast }\le b$, the flux is the minimum $f_{\ast }$. In the opposite crossing it is $f(a)+f(b)-f_{\ast }$, which in general differs from the exact Godunov numerical flux. This distinction does not affect the monotonicity proof.

Here stability requires the usual Courant–Friedrichs–Lewy condition. Let the initial values lie in $[m,M]$, and chooseA differentiable convex function has a continuous derivative on this interval, so the maximum is finite. Write the three-input update as $H(a,b,c)$. Differentiating givesThus the update $T$ preserves componentwise order. Constants are fixed, since $H(c,c,c)=c$, so comparison with the constants $m,M$ proves $m\le U_j^n\le M$ for every time level. In particular the same CFL condition remains applicable. This is a mesh-independent maximum-principle stability bound.

A stronger stability statement is contraction in discrete $L^1$. Consider two solutions $U,V$ in the same invariant interval, on a periodic mesh or on the infinite lattice with summable differences. Let $Q=U\vee V$ be their componentwise maximum. Monotonicity gives $TQ\ge TU,TV$, henceThe discrete conservation law for the difference gives the equality: on a finite periodic mesh the flux sum cancels exactly, and on the infinite lattice it follows by truncation and the fact that the flux is a Lipschitz function on $[m,M]$. Interchanging $U,V$ and adding provesThis is L1 contraction of a monotone conservative scheme. Since $T$ commutes with the cell shift, applying this contraction to $U$ and its shift gives ${\sum }_j|U_{j+1}^{n+1}-U_j^{n+1}|\le {\sum }_j|U_{j+1}^n-U_j^n|$. The scheme is therefore a total variation diminishing scheme as well.

The same order argument proves a discrete entropy inequality, explaining why this stable discretization selects entropy solutions rather than nonphysical expansion shock waves. For a constant $c\in [m,M]$, setBecause $T(U\vee c)\ge TU,c$ and $T(U\wedge c)\le TU,c$, their componentwise difference is at least $|TU-c|$. Subtracting their updates givesFor constants outside $[m,M]$, the entropy inequality is an equality by the invariant bound and the conservative update. At equal states $Q_c(u,u)=\mathrm{sgn}(u-c)[f(u)-f(c)]$, the Kruzhkov entropy flux. The flux is a Lipschitz function on the invariant interval: writing $L=\max |f^{\prime }|$, the conservative update gives $h{\sum }_j|U_j^{n+1}-U_j^n|\le 2kL{\sum }_j|U_{j+1}^n-U_j^n|$. This time-translation bound, the invariant bound and the total variation estimate give local space-time compactness for bounded-variation initial conditions as the mesh is refined; the conservative update passes to the weak conservation law, and the displayed inequality passes to its Kruzhkov entropy inequality. This identifies the limit as the entropy solution.

Finally the time-step qualification is essential. For the convex Inviscid Burgers equation flux $f(u)=u^2/2$, whose unique sonic point of a scalar flux is zero, linearize about a positive constant $U$. The perturbation update becomes $v_j^{n+1}=(1-rU)v_j^n+rU{v}_{j-1}^n$. At Fourier frequency $\pi$ its multiplier is $1-2rU$, with modulus greater than one if $rU>1$. Wave packets near this phase give linear instability even for summable Cauchy perturbations. Thus the assumptions on $f$ imply the stability results above under the CFL condition, not for arbitrary $k/h$. This is CFL necessity for explicit Engquist-Osher stability.