Hyperbolic finite-difference methods

Use $\mathbb{N}$ for the natural-number index set (including zero) (The natural numbers $\mathbb{N}$ (von Neumann)), $\mathbb{R}$ for the real scalar field (The real numbers), and $\mathbb{C}$ with its real embedding and modulus (The complex numbers as $\mathbb{R}[x]\mathrm{/}(x^2+1)$, with the real embedding and imaginary unit $i$, Real and imaginary parts, complex conjugation, and modulus).

Let $N\ge 2$, $h>0$, $k>0$, and $t_n=nk$. For the finite periodic grid put $J_N=\{0,\dots ,N-1\}$ and reduce every shifted index modulo $N$. A periodic grid function is a map $v:J_N\to \mathbb{C}$, with weighted norm $\mathrm{\parallel }v{\mathrm{\parallel }}_{2,h}={\left(h{\sum }_{j=0}^{N-1}\mathrm{\mid }{v}_j{\mathrm{\mid }}^2\right)}^{1\mathrm{/}2}\mathrm{.}$ The infinite uniform grid has indices $j\in \mathbb{Z}$ and positions $x_j=jh$. On the periodic and infinite grids define $(D_{+}v{)}_j=\frac{v_{j+1}-v_j}{h},(D_{-}v{)}_j=\frac{v_j-v_{j-1}}{h},(D_{0}v{)}_j=\frac{v_{j+1}-v_{j-1}}{2h},({\mathrm{\Delta }}_{h}v{)}_j=\frac{v_{j+1}-2v_j+v_{j-1}}{h^2}\mathrm{.}$ Use the inner product linear in its first entry, $⟨p,q{⟩}_{2,h}=h{\sum }_{j=0}^{N-1}{p}_j\overline{q_j},⟨D_{+}p,D_{+}q{⟩}_{e,h}=h{\sum }_{j=0}^{N-1}(D_{+}p{)}_j\overline{(D_{+}q{)}_j},$ where the indices in $D_{+}$ are reduced periodically, and set $\mathrm{\parallel }{D}_{+}p{\mathrm{\parallel }}_{e,h}^2=⟨D_{+}p,D_{+}p{⟩}_{e,h}$. The same definitions apply to real-valued grid functions.

For a finite interval of length $L=Nh$, use physical nodes $x_j=jh$ with indices $j=0,\dots ,N$. On its edges $j=0,\dots ,N-1$ define $(D_{+}v{)}_j=(v_{j+1}-v_j)\mathrm{/}h$, and on interior nodes $j=1,\dots ,N-1$ use $({\mathrm{\Delta }}_{h}v{)}_j=(v_{j+1}-2v_j+v_{j-1})\mathrm{/}{h}^2$. At the right endpoint define $(D_{-}v{)}_N=(v_N-v_{N-1})\mathrm{/}h$. For interior-node arrays $r,s$ indexed by $j=1,\dots ,N-1$ and edge arrays $p,q$ indexed by $j=0,\dots ,N-1$, define $⟨r,s{⟩}_h=h{\sum }_{j=1}^{N-1}{r}_j\overline{s_j},\mathrm{\parallel }r{\mathrm{\parallel }}_h^2=⟨r,r{⟩}_h,⟨p,q{⟩}_{e,h}=h{\sum }_{j=0}^{N-1}{p}_j\overline{q_j}\mathrm{.}$ Set $\mathrm{\parallel }p{\mathrm{\parallel }}_{e,h}^2=⟨p,p{⟩}_{e,h}$. For nodal grid functions, interior pairings and norms mean restriction to the interior nodes. Thus $\mathrm{\parallel }\cdot {\mathrm{\parallel }}_h$ is a norm on the zero-endpoint subspace, but only a seminorm on the full nodal space. Dirichlet grid functions have prescribed endpoint values; when they are zero, the interior norm and edge inner product above are the ones used for the wave energy.

All statements below distinguish these periodic, infinite, and finite-interval index sets. Periodic Fourier calculations are not boundary estimates for the finite-interval grid.

Use the index sets and uniform spacings of Uniform periodic, infinite, and Dirichlet grid conventions: $x_j=jh$, $j\in \mathbb{Z}$, or $j$ reduced modulo $N$ in the periodic case. Fix $a>0$, $h,k>0$, and $\nu =ak\mathrm{/}h$. The target equation is the one-dimensional constant-velocity transport equation $u_t+a{u}_x=0$, the constant-coefficient case of Linear transport equations and their characteristic flow. Set $U_j^0=u_0(jh)$ and define, for $n\ge 0$, $\begin{array}{rl}{\displaystyle \text{upwind: }}& {\displaystyle U_j^{n+1}=U_j^n-\nu (U_j^n-U_{j-1}^n),}\\ {\displaystyle \text{downwind: }}& {\displaystyle U_j^{n+1}=U_j^n-\nu (U_{j+1}^n-U_j^n),}\\ {\displaystyle \text{centered: }}& {\displaystyle U_j^{n+1}=U_j^n-\frac{\nu }{2}(U_{j+1}^n-U_{j-1}^n),}\\ {\displaystyle \text{Lax–Friedrichs: }}& {\displaystyle U_j^{n+1}=\frac{U_{j-1}^n+U_{j+1}^n}{2}-\frac{\nu }{2}(U_{j+1}^n-U_{j-1}^n),}\\ {\displaystyle \text{Lax–Wendroff: }}& {\displaystyle U_j^{n+1}=U_j^n-\frac{\nu }{2}(U_{j+1}^n-U_{j-1}^n)+\frac{{\nu }^2}{2}(U_{j+1}^n-2U_j^n+U_{j-1}^n)\mathrm{.}}\end{array}$ On a periodic grid, every index in these formulas is reduced modulo $N$; no physical boundary data are present. For $a<0$, reflect the stencil by $j\mapsto -j$ and replace $\nu$ by $\mathrm{\mid }a\mathrm{\mid }k\mathrm{/}h$.

For a finite interval $[0,L]$ with $a>0$, the inflow boundary is $x=0$. The upwind initial/boundary rows are $U_j^0=u_0(jh)$ for $j=0,\dots ,N$, $U_0^n=g(t_n)$ with $u_0(0)=g(0)$, and $U_j^{n+1}=(1-\nu )U_j^n+\nu U_{j-1}^n,j=1,\dots ,N,n\ge 0.$ The outflow node $j=N$ is computed by this row and receives no prescribed value. This item supplies no finite-interval boundary closure or stability statement for centered, Lax--Friedrichs, or Lax--Wendroff updates.

Use the uniform-grid indices, physical nodes, and spacings of Uniform periodic, infinite, and Dirichlet grid conventions. Fix a wave speed $c>0$, an interval length $L=Nh$ with $N\ge 2$, and a time step $k>0$. Write $\nu =ck\mathrm{/}h$. The target model is the real scalar wave equation $u_{tt}=c^2{u}_{xx}$, and grid states are real-valued. Prescribe a real initial displacement row $U^0$ and discrete initial-velocity row $V^0$, and set $U^1=U^0+k{V}^0$. For smooth Dirichlet data $u_0,u_1:[0,L]\to \mathbb{R}$ with $u_0(0)=u_0(L)=u_1(0)=u_1(L)=0$, the corresponding sample rows are $U_j^0=u_0(x_j)$ and $V_j^0=u_1(x_j)$; for smooth periodic data, take real $L$-periodic $u_0,u_1$ and sample them at $x_j$. In both cases the discrete initial velocity equals the sampled $u_1$. The centered leapfrog recurrence is $U_j^{n+1}-2U_j^n+U_j^{n-1}={\nu }^2(U_{j+1}^n-2U_j^n+U_{j-1}^n),n\ge 1.$ For the finite Dirichlet interval, require $U_0^0=U_N^0=V_0^0=V_N^0=0$ and impose the recurrence for $j=1,\dots ,N-1$, with $U_0^n=U_N^n=0$ for every $n\ge 0$. For the periodic branch, use $j=0,\dots ,N-1$, reduce indices modulo $N$, and impose the recurrence at every node. Fourier analysis of this real periodic update uses its complex-linear extension to the complexified grid space. No convergence order for a particular initialization formula is asserted here.

Let $N\ge 2$, $h>0$, and let $u=(u_0,\dots ,u_N)$ and $v=(v_0,\dots ,v_N)$ be complex grid functions. With the finite-interval inner products and differences of Uniform periodic, infinite, and Dirichlet grid conventions, $⟨u,-{\mathrm{\Delta }}_{h}v{⟩}_h=⟨D_{+}u,D_{+}v{⟩}_{e,h}+u_0\overline{(D_{+}v{)}_0}-u_N\overline{(D_{-}v{)}_N}\mathrm{.}$ In particular, if $u_0=u_N=0$, the two boundary terms vanish. On the subspace of grid functions with zero endpoints, $-{\mathrm{\Delta }}_h$ is self-adjoint and nonnegative in the interior grid inner product, with $⟨u,-{\mathrm{\Delta }}_{h}u{⟩}_h=\mathrm{\parallel }{D}_{+}u{\mathrm{\parallel }}_{e,h}^2$.

Let $N\ge 2$, $h>0$, $L=Nh$, and let $w=(w_0,\dots ,w_N)$ be a complex grid function with $w_0=w_N=0$. Then $\mathrm{\parallel }w{\mathrm{\parallel }}_h\le L\mathrm{\parallel }{D}_{+}w{\mathrm{\parallel }}_{e,h}\mathrm{.}$

Fix $a\in \mathbb{R}\setminus \{0\}$. Let $u:{\mathbb{R}}^2\to \mathbb{R}$ be a $C^6$ solution of $u_t+a{u}_x=0$ that is periodic in $x$ with period $P>0$, so $u(x+P,t)=u(x,t)$, and whose derivatives through order six are bounded. Let $h,k\to 0$ with $0<c_{-}\le k\mathrm{/}h\le c_{+}<\mathrm{\infty }$, and put $\nu =\mathrm{\mid }a\mathrm{\mid }k\mathrm{/}h$. For a stencil $S$, define its local residual by ${\tau }_S(x,t)=\frac{u(x,t+k)-S(u(\cdot ,t))(x)}{k}\mathrm{.}$ Then, for the sign-selected stencils of Periodic advection schemes and the finite-interval upwind row, the upwind, downwind, centered, and Lax--Friedrichs residuals are $O(h)$ uniformly in $(x,t)$, while the Lax--Wendroff residual is $O(h^2)$. Here a remainder $R=O(\eta (h,k))$ uniformly means $\mathrm{\mid }R(x,t;h,k)\mathrm{\mid }\le C\eta (h,k)$ for all $x,t$ and sufficiently small $h,k$, with $C$ independent of $x,t,h,k$ under the stated ratio bounds. These are smooth-solution consistency statements and imply no convergence result at discontinuities.

For the homogeneous Dirichlet recurrence of Centered leapfrog wave recurrence with Dirichlet and periodic rows, let $0<\nu =ck\mathrm{/}h<1$, $V^n=(U^{n+1}-U^n)\mathrm{/}k$, and ${\bar{U}}^n=(U^{n+1}+U^n)\mathrm{/}2$. Define $E^{n+1\mathrm{/}2}=\frac{1}{2}\mathrm{\parallel }{V}^n{\mathrm{\parallel }}_h^2+\frac{c^2}{2}⟨D_{+}{U}^{n+1},D_{+}{U}^n{⟩}_{e,h}\mathrm{.}$ Then $E^{n+1\mathrm{/}2}$ is independent of $n$ and $E^{n+1\mathrm{/}2}\ge \frac{1-{\nu }^2}{2}\mathrm{\parallel }{V}^n{\mathrm{\parallel }}_h^2+\frac{c^2}{2}\mathrm{\parallel }{D}_{+}{\bar{U}}^n{\mathrm{\parallel }}_{e,h}^2\mathrm{.}$ Consequently it is a positive quadratic form on adjacent zero-boundary states. For mesh families with fixed wave speed $c>0$, fixed interval length $L$, and $\nu \le {\nu }_0<1$, it controls the interior state and its discrete velocity with constants independent of $h$.

On an $N$-point periodic grid let $z_{\mathrm{\ell }}=\exp (2\pi i\mathrm{\ell }\mathrm{/}N)$, $C_{\mathrm{\ell }}=\mathrm{Re}{z}_{\mathrm{\ell }}$, $S_{\mathrm{\ell }}=\mathrm{Im}{z}_{\mathrm{\ell }}$, and $\nu =ak\mathrm{/}h$ with $a>0$. The Fourier vector $j\mapsto z_{\mathrm{\ell }}^j$ is multiplied in one step by $g_{\mathrm{u}\mathrm{p}}=1-\nu +\nu z_{\mathrm{\ell }}^{-1},g_{\mathrm{d}\mathrm{o}\mathrm{w}\mathrm{n}}=1+\nu -\nu z_{\mathrm{\ell }},g_{\mathrm{c}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{e}\mathrm{d}}=1-i\nu S_{\mathrm{\ell }},g_{\mathrm{L}\mathrm{F}}=C_{\mathrm{\ell }}-i\nu S_{\mathrm{\ell }},g_{\mathrm{L}\mathrm{W}}=1-{\nu }^2(1-C_{\mathrm{\ell }})-i\nu S_{\mathrm{\ell }}\mathrm{.}$ Their squared moduli, in the same order, are $1-2\nu (1-\nu )(1-C_{\mathrm{\ell }}),1+2\nu (1+\nu )(1-C_{\mathrm{\ell }}),1+{\nu }^2{S}_{\mathrm{\ell }}^2,1-(1-{\nu }^2)S_{\mathrm{\ell }}^2,1-{\nu }^2(1-{\nu }^2)(1-C_{\mathrm{\ell }}{)}^2\mathrm{.}$ The $N$ Fourier vectors form an orthogonal basis under the periodic inner product of Uniform periodic, infinite, and Dirichlet grid conventions, and each has squared norm $Nh$.

On a periodic grid of length $L=Nh$, let $\nu =ck\mathrm{/}h>0$, $V^0=(U^1-U^0)\mathrm{/}k$, and write $U^n={\sum }_{\mathrm{\ell }=0}^{N-1}{w}_{\mathrm{\ell }}^n{\varphi }_{\mathrm{\ell }}$ in the discrete Fourier basis; write ${\widehat{V}}_{\mathrm{\ell }}^0$ for the coefficient of $V^0$ in the same basis. Then $w_{\mathrm{\ell }}^{n+1}-2(1-2{\nu }^2{s}_{\mathrm{\ell }})w_{\mathrm{\ell }}^n+w_{\mathrm{\ell }}^{n-1}=0,s_{\mathrm{\ell }}={\sin }^2(\pi \mathrm{\ell }\mathrm{/}N)\mathrm{.}$ For $0<\nu \le {\nu }_0<1$, the nonconstant roots are distinct and have modulus one, and $\mathrm{\parallel }{U}^n{\mathrm{\parallel }}_{2,h}\le (1+\frac{{\nu }_0}{\sqrt{1-{\nu }_0^2}})\mathrm{\parallel }{U}^0{\mathrm{\parallel }}_{2,h}+t_n\mathrm{\parallel }{V}^0{\mathrm{\parallel }}_{2,h}\mathrm{.}$ The mean mode is $w_0^n=w_0^0+t_n{\widehat{V}}_0^0$. At $\nu =1$ and even $N$, the Nyquist mode has the repeated root $-1$ and solution $w_{N\mathrm{/}2}^n=(-1{)}^n(A+nB)$, where $B=0$ exactly when $w_{N\mathrm{/}2}^1=-w_{N\mathrm{/}2}^0$. Thus arbitrary starting pairs do not have a uniform endpoint power bound.

For the periodic schemes of Periodic advection schemes and the finite-interval upwind row with $a>0$, upwind powers are contractions in $\mathrm{\parallel }\cdot {\mathrm{\parallel }}_{2,h}$ for $0\le \nu \le 1$ and grow for $\nu >1$. Lax--Friedrichs and Lax--Wendroff powers are contractions for $\mathrm{\mid }\nu \mathrm{\mid }\le 1$; when $\mathrm{\mid }\nu \mathrm{\mid }>1$, Lax--Wendroff grows for $N\ge 2$ and Lax--Friedrichs grows for $N\ge 3$ (the $N=2$ Lax--Friedrichs stencil aliases its nonconstant mode). Downwind powers grow for every $\nu >0$ and $N\ge 2$. Centered powers grow for every $\nu \mathrm{\ne }0$ when $N\ge 3$, while the $N=2$ centered stencil aliases to the identity. Reflection gives the same assertions for $a<0$ with $\mathrm{\mid }\nu \mathrm{\mid }$.