The Optimal Accuracy of Difference Schemes

We consider difference approximations to the model hyperbolic equation ${u_{t}} = {u_x}$ which compute each new value $U(x,t + \Delta t)$ as a combination of the known values $U(x - r\Delta x,t),\ldots ,U(x + s\Delta x,\Delta t)$. For such schemes we find the optimal order of accuracy: stability is possible for small $\Delta t/\Delta x$ if and only if $p \leqslant \min \{ {r + s,2r + 2,2s} \}$. A similar bound is established for implicit methods. In this case the most accurate schemes are based on Padé approximations $P(z)/Q(z)$ to ${z^\lambda }$ near $z = 1$, and we find an expression for the difference $|Q{|^2} - |P{|^2}$; this allows us to test the von Neumann condition $|P/Q| \leqslant 1$. We also determine the number of zeros of $Q$ in the unit circle, which decides whether the implicit part is uniformly invertible.