A Stable Adaptive Numerical Scheme for Hyperbolic Conservation Laws

A new adaptive finite-difference scheme for scalar hyperbolic conservation laws is introduced. A key aspect of the method is a new automatic mesh selection algorithm for problems with shocks. We show that the scheme is L-stable in the sense of Kuznetsov, and that it generates convergent approximations for linear problems. Numerical evidence is presented that indicates that if an error of size e is required, our scheme takes at most O(e-3) operations. Standard monotone diiterence schemes can take up to O(e-4) calculations for the same problems. 1. Introduction. Our focus in this paper is the efficient solution of the hyperbolic conservation law, ut+f(u), O, x R, > O, (c) u(x, O) Uo(X), x R. We introduce an adaptive finite-difference scheme that takes advantage of the structure ofthe solution of (C) to reduce its computational complexity.We prove that the scheme is L stable in the sense of Kuznetsov, and we offer numerical evidence that, because of the dynamic mesh modification, asymptotic error decay rates are improved for some problems. For linear problems we show that a version of our method converges if the initial data's first derivative is of bounded variation. Our method is, generally speaking, in the class of viscosity methods, methods that include monotone finite-difference schemes. Monotone schemes have been analyzed by Harten et al. (13), Crandall and Majda (6), Kuznetsov (17), Sanders (22), and Lucier (19). These schemes converge to the entropy weak solution of the conservation law (C), as formulated by Kruzkov 16). Kuznetsov provided a general theory ofapproxima- tion for approximate solutions of (C), and he used this theory to provide error estimates for various approximation methods for (C), including monotone difference schemes on uniform meshes. His techniques were used by Sanders and by Lucier to provide error estimates for difference schemes with nonuniform meshes and nonlocal difference operators respectively. One of the considerations in developing our algorithm was that it must exhibit nonlinear stability properties similar to those ofthe differential equation itself. Solutions of (C) are stable in Ll(R) in the sense that, if u(x, t) and v(x, t) are solutions of (C), then