Numerical viscosity and the entropy condition

Weak solutions of hyperbolic conservation laws are not uniquely determined by their initial values; an entropy condition is needed to pick out the physically relevant solutions. The question arises whether finite difference approximations converge to this particular solution. It is known that this is not always the case with the standard Lax-Wendroff (L-W) difference scheme. In this paper a simple variant of the L-W scheme is devised which retains its desirable computational features—conservation form, three point scheme, second-order accuracy on smooth solutions, but which has the additional property that limit solutions satisfy the entropy condition. This variant is constructed by adding a simple nonlinear artificial viscosity to the usual L-W operator. The nature of the viscosity is deduced by first analyzing a model differential equation derived from the truncation error for the L-W operator, keeping only terms of order (Δx)². Furthermore, this viscosity is “switched on” only when sufficiently steep discrete gradients develop in the approximate solution: The full L-W scheme is then shown to have the desired property provided that the Courant-Friedrichs-Lewy restriction |λf′(u)|≤0.14 is satisfied.     

The Entropy Condition for Implicit TVD Schemes

A class of implicit trapezoidal TVD schemes is proven to satisfy a discrete convex entropy inequality and the solution sequence of such implicit trapezoidal schemes converges to the physically relevant solution for genuinely nonlinear scalar conservation laws. The results are extended for a class of generalized implicit one-leg TVD schemes.     

一类TVD格式的熵强迫函数及熵条件

1.引言 在拟线性双曲型方程差分方法的研究中,数值解的收敛性是一个重要的问题,因为这一性质决定了数值解能否近似地反映真实的物理现象。数值解的收敛性实际上包含了三方面的内容: 1°当网格步长趋于零时,数值解序列包含一个按某种范数收敛到函数u的子序列。     

Upwind finite volume schemes for weakly coupled hyperbolic systems of conservation laws in 2D

Summary. Systems of nonlinear hyperbolic conservation laws in two space dimensions are considered which are characterized by the fact that the coupling of the equations is only due to source terms. To solve these weakly coupled systems numerically a class of explicit and implicit upwind finite volume methods on unstructured grids is presented. Provided an unique entropy solution of the system of conservation laws exists we prove that the approximations obtained by these schemes converge for vanishing discretization parameter to this entropy solution. These results are applied to examples from combustion theory and hydrology where the existence of entropy solutions can be shown. The proofs rely on an extension of a result due to DiPerna concerning measure valued solutions to the case of weakly coupled hyperbolic systems. Received April 29, 1997     

Local limit of nonlocal traffic models: Convergence results and total variation blow-up

Consider a nonlocal conservation law where the flux function depends on the convolution of the solution with a given kernel. In the singular local limit obtained by letting the convolution kernel converge to the Dirac delta one formally recovers a conservation law. However, recent counter-examples show that in general the solutions of the nonlocal equations do not converge to a solution of the conservation law. In this work we focus on nonlocal conservation laws modeling vehicular traffic: in this case, the convolution kernel is anisotropic. We show that, under fairly general assumptions on the (anisotropic) convolution kernel, the nonlocal-to-local limit can be rigorously justified provided the initial datum satisfies a one-sided Lipschitz condition and is bounded away from 0. We also exhibit a counter-example showing that, if the initial datum attains the value 0, then there are severe obstructions to a convergence proof.     

Construction of Approximate Entropy Measure-Valued Solutions for Hyperbolic Systems of Conservation Laws

Entropy solutions have been widely accepted as the suitable solution framework for systems of conservation laws in several space dimensions. However, recent results in De Lellis and Székelyhidi Jr (Ann Math 170(3):1417–1436, 2009) and Chiodaroli et al. (2013) have demonstrated that entropy solutions may not be unique. In this paper, we present numerical evidence that state-of-the-art numerical schemes need not converge to an entropy solution of systems of conservation laws as the mesh is refined. Combining these two facts, we argue that entropy solutions may not be suitable as a solution framework for systems of conservation laws, particularly in several space dimensions. We advocate entropy measure-valued solutions, first proposed by DiPerna, as the appropriate solution paradigm for systems of conservation laws. To this end, we present a detailed numerical procedure which constructs stable approximations to entropy measure-valued solutions, and provide sufficient conditions that guarantee that these approximations converge to an entropy measure-valued solution as the mesh is refined, thus providing a viable numerical framework for systems of conservation laws in several space dimensions. A large number of numerical experiments that illustrate the proposed paradigm are presented and are utilized to examine several interesting properties of the computed entropy measure-valued solutions.     

ON ENTROPY CONDITIONS OF HIGH RESOLUTION SCHEMES FOR SCALAR CONSERVATION LAWS

1. IntroductionLet us consider the Cauchy problems for nonlinear hroerbolic scalar cO~ion laws:where the function f(u) E C'(R) and the hatal data ho E BV(R). As is well lmown, thisProblem in general does not ~ smooth solution, so that weak solution in the sense ofdistributions must be considered. Moreover, an elitropy condition must be added in order toensure the ~s of the weak solutions.The research of numerical methods for solving the equation (1.1) has been developed rapidlyin this deca…     

The method of fractional steps for conservation laws

Summary The stability, accuracy, and convergence of the basic fractional step algorithms are analyzed when these algorithms are used to compute discontinuous solutions of scalar conservation laws. In particular, it is proved that both first order splitting and Strang splitting algorithms always converge to the unique weak solution satisfying the entropy condition. Examples of discontinuous solutions are presented where both Strang-type splitting algorithms are only first order accurate but one of the standard first order algorithms is infinite order accurate. Various aspects of the accuracy, convergence, and correct entropy production are also studied when each split step is discretized via monotone schemes, Lax-Wendroff schemes, and the Glimm scheme.Partially supported by an Alfred Sloan Foundation fellowship and N.S.F. grant MCS-76-10227Sponsored by US Army under contract No. DAA 629-75-0-0024     

Preconditioning spectral element schemes for definite and indefinite problems

Spectral element schemes for the solution of elliptic boundary value problems are considered. Preconditioning methods based on finite difference and finite element schemes are implemented. Numerical experiments show that inverting the preconditioner by a single multigrid iteration is most efficient and that the finite difference preconditioner is superior to the finite element one for both definite and indefinite problems. A multigrid preconditioner is also derived from the finite difference preconditioner and is found suitable for the CGS acceleration method. It is pointed out that, for the finite difference and finite element preconditioners, CGS does not always converge to the accurate algebraic solution. © 1999 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 15: 535–543, 1999     

BBPH: Using progressive hedging within branch and bound to solve multi-stage stochastic mixed integer programs

Progressive hedging, though an effective heuristic for solving stochastic mixed integer programs (SMIPs), is not guaranteed to converge in this case. Here, we describe BBPH, a branch and bound algorithm that uses PH at each node in the search tree such that, given sufficient time, it will always converge to a globally optimal solution. In addition to providing a theoretically convergent “wrapper” for PH applied to SMIPs, computational results demonstrate that for some difficult problem instances branch and bound can find improved solutions after exploring only a few nodes.     

A possible counterexample to well posedness of entropy solutions and to Godunov scheme convergence

A particular case of initial data for the two-dimensional Euler equations is studied numerically. The results show that the Godunov method does not always converge to the physical solution, at least not on feasible grids. Moreover, they suggest that entropy solutions (in the weak entropy inequality sense) are not well posed.

     

Block-iterative methods for consistent and inconsistent linear equations

Summary We shall in this paper consider the problem of computing a generalized solution of a given linear system of equations. The matrix will be partitioned by blocks of rows or blocks of columns. The generalized inverses of the blocks are then used as data to Jacobi- and SOR-types of iterative schemes. It is shown that the methods based on partitioning by rows converge towards the minimum norm solution of a consistent linear system. The column methods converge towards a least squares solution of a given system. For the case with two blocks explicit expressions for the optimal values of the iteration parameters are obtained. Finally an application is given to the linear system that arises from reconstruction of a two-dimensional object by its one-dimensional projections.     

Finite Element Methods for Parabolic Stochastic PDE’s

We study the rate of convergence of some explicit and implicit numerical schemes for the solution of a parabolic stochastic partial differential equation driven by white noise. These include the forward and backward Euler and the Crank–Nicholson schemes. We use the finite element method. We find, as expected, that the rates of convergence are substantially similar to those found for finite difference schemes, at least when the size of the time step k is on the order of the square of the size of the space step h: all the schemes considered converge at a rate on the order of h^1/2+k^1/4, which is known to be optimal. We also consider cases where k is much greater than h², and find that only the backward Euler method always attains the optimal rate; other schemes, even though they are stable, can fail to convergence to the true solution if the time step is too long relative to the space step. The Crank–Nicholson scheme behaves particularly badly in this case, even though it is a higher-order method. Mathematics Subject Classifications (2000) 60H15, 60H35, 65N30, 35R60.     

The space of general conservation laws and topology changes

We construct a 5D space in which conservation laws are always and absolutely valid. This general result holds also scaling in 4D space even inducing, when necessary, changes of topology. The inequality of representations of physical laws in 4D and in 5D generalized spaces is founded not on phenomenological but on mathematical results. Essentially, the mechanism is based on the fact that we take into account also transformations where the Jacobian of the change of variables can assume null values. We derive that stress-energy and metric tensors, due to Bianchi identities, are always conserved through the mechanism presented in the following based on the fact that we introduce transformations with null Jacobian in the space definition. Moreover, in the case of metric tensor, conservation is a necessary feature in order to have physically defined theories.     

Extensions of block-projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems

There exist many classes of block-projections algorithms for approximating solutions of linear least-squares problems. Generally, these methods generate sequences convergent to the minimal norm least-squares solution only for consistent problems. In the inconsistent case, which usually appears in practice because of some approximations or measurements, these sequences do no longer converge to a least-squares solution or they converge to the minimal norm solution of a “perturbed” problem. In the present paper, we overcome this difficulty by constructing extensions for almost all the above classes of block-projections methods. We prove that the sequences generated with these extensions always converge to a least-squares solution and, with a suitable initial approximation, to the minimal norm solution of the problem. Numerical experiments, described in the last section of the paper, confirm the theoretical results obtained.     

Weak solutions for equations defined by accretive operators II: relaxation limits

In the first part of this paper we define solutions for certain nonlinear equations defined by accretive operators, “dissipative solution”. This kind of solution is equivalent to the viscosity solutions for Hamilton-Jacobi equations and to the entropy solutions for conservation laws.In this paper we use dissipative solutions to obtain several relaxation limits for systems of semilinear transport equations and quasilinear conservation laws. These converge to diffusion second-order equations and in one case to a single conservation law. The relaxation limit is obtained using a version of the perturbed test function method to pass to the limit. This guarantees existence for the considered equations.     

One-sided stability and convergence of the Nessyahu–Tadmor scheme

Non-oscillatory schemes are widely used in numerical approximations of nonlinear conservation laws. The Nessyahu–Tadmor (NT) scheme is an example of a second order scheme that is both robust and simple. In this paper, we prove a new stability property of the NT scheme based on the standard minmod reconstruction in the case of a scalar strictly convex conservation law. This property is similar to the One-sided Lipschitz condition for first order schemes. Using this new stability, we derive the convergence of the NT scheme to the exact entropy solution without imposing any nonhomogeneous limitations on the method. We also derive an error estimate for monotone initial data.     

On the role of conservation laws in the problem on the occurrence of unstable solutions for quasilinear parabolic equations and their approximations

For a broad class of initial-boundary value problems for quasilinear parabolic equations with nonlinear source and their approximations, we show that if the initial energy is negative, then the solution always blows up in finite time. This is especially important for finding sufficiently simple and easy-to-verify conditions guaranteeing the presence of physical effects such as heat localization in peaking modes or thermal explosions and for deriving two-sided estimates of the solution lifespan. We construct the corresponding new classes of difference schemes for which grid analogs of integral conservation laws hold. We show that, to obtain efficient two-sided estimates for the blow-up time of the solution of the differential problem, in practice, one should use difference schemes with explicit as well as implicit approximation to the source.     

Systems of conservation laws of mixed type

A local theory of weak solutions of first-order nonlinear systems of conservation laws is presented. In the systems considered, two of the characteristic speeds become complex for some achieved values of the dependent variable. The transonic “small disturbance” equation is an example of this class of systems. Some familiar concepts from the purely hyperbolic case are extended to such systems of mixed type, including genuine nonlinearity, classification of shocks into distinct fields and entropy inequalities. However, the associated entropy functions are not everywhere locally convex, shock and characteristic speeds are not bounded in the usual sense, and closed loops and disjoint segments are possible in the set of states which can be connected to a given state by a shock. With various assumptions, we show (1) that the state on one side of a shock plus the shock speed determine the state on the other side uniquely, as in the hyperbolic case; (2) that the “small disturbance” equation is a local model for a class of such systems; and (3) that entropy inequalities and/or the existence of viscous profiles can still be used to select the “physically relevant” weak solution of such a system.     

Antidiffusive Lagrangian‐remap schemes for models of polydisperse sedimentation

One‐dimensional models of gravity‐driven sedimentation of polydisperse suspensions with particles that belong to N size classes give rise to systems of N strongly coupled, nonlinear first‐order conservation laws for the local solids volume fractions. As the eigenvalues and eigenvectors of the flux Jacobian have no closed algebraic form, characteristic‐wise numerical schemes for these models become involved. Alternative simple schemes for this model directly utilize the velocity functions and are based on splitting the system of conservation laws into two different first‐order quasi‐linear systems, which are solved successively for each time iteration, namely, the Lagrangian and remap steps (so‐called Lagrangian‐remap [LR] schemes). This approach was advanced in (Bürger, Chalons, and Villada, SIAM J Sci Comput 35 (2013), B1341–B1368) for a multiclass Lighthill–Whitham‐Richards traffic model with nonnegative velocities. By incorporating recent antidiffusive techniques for transport equations a new version of these Lagrangian‐antidiffusive remap (L‐AR) schemes for the polydisperse sedimentation model is constructed. These L‐AR schemes are supported by a partial analysis for N = 1. They are total variation diminishing under a suitable CFL condition and therefore converge to a weak solution. Numerical examples illustrate that these schemes, including a more accurate version based on MUSCL extrapolation, are competitive in accuracy and efficiency with several existing schemes. © 2015 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 32: 1109–1136, 2016