# Error Bounds for the Methods of Glimm, Godunov and LeVeque

Bradley J. Lucier

► To cite this version:

Bradley J. Lucier. Error Bounds for the Methods of Glimm, Godunov and LeVeque. SIAM Journal on Numerical Analysis, 1985, 22 (6), pp.1074 - 1081. 10.1137/0722064. hal-01435616

HAL Id: hal-01435616

https://hal.science/hal-01435616

Submitted on 14 Jan 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
ERROR BOUNDS FOR THE METHODS OF GLIMM, GODUNOV AND LEVEQUE

BRADLEY J. LUCIER

**Abstract.** The expected error in $L^1(\mathbb{R})$ at time $T$ for Glimm's scheme when applied to a scalar conservation law is bounded by

$$ \left(h + \frac{2}{\sqrt{3}} \left(\frac{h}{\Delta t}\right)^{1/2} (hT)^{1/2}\right) \|u_0\|_{BV(\mathbb{R})}, $$

where $h$ is the mesh size and $\Delta t$ is the time step. We show that the error in Godunov's scheme is bounded by the same expression and use this result to analyze a variant of a large time step numerical method of LeVeque that may be viewed as a combination of Godunov's scheme and a method of Dafermos.

**1. Glimm's scheme.** Glimm's scheme [3] is a probabilistic method for proving existence of solutions for the hyperbolic system of conservation laws,

$$ \begin{array}{l} (C) \qquad \displaystyle u_t + f(u)_x = 0, \quad x \in \mathbb{R}, \quad t > 0, \\ \qquad \displaystyle u(x, 0) = u_0(x), \quad x \in \mathbb{R}. \end{array} $$

Glimm showed that if the total variation of $u_0$ is sufficiently small, the equation is hyperbolic and genuinely nonlinear in the sense of Lax, then the approximate solution generated by his scheme converges almost surely to a weak solution of (C); later Harten and Lax [5] showed that any Glimm weak solution satisfies the entropy condition. Glimm's scheme has also been applied with some success as a numerical method; see, for example, [1]. In this note we bound the expectation of the $L^1$ error of the approximate solution in the special case where (C) is a scalar equation. In particular, we prove the following theorem.

**THEOREM 1.** If $u^n(x, t)$ is the solution of Glimm's method for $t^n \le t < t^{n+1}$, $u(x, t)$ is the entropy solution of (C), and $T = N\Delta t$, then

$$ E(\|u(\cdot, T) - u^N(\cdot, T)\|_{L^1(\mathbb{R})}) \le \left(h + \frac{2}{\sqrt{3}} \left(\frac{h}{\Delta t}\right)^{1/2} (hT)^{1/2}\right) \|u_0\|_{BV(\mathbb{R})}, $$

where $h$ is the mesh spacing, $\Delta t$ is the time step, and $t^n = n\Delta t$.

A function is in $BV(\mathbb{R})$ if its derivative is a bounded measure. We remark that Hoff and Smoller [7] have derived certain error bounds for Glimm's method using equidistributed rather than random sequences of numbers.

We note first that although Glimm's scheme is usually defined on alternating meshes (the approximate solution is piecewise constant on the intervals $[ih, (i+1)h)$ at time $t^n$ if $n$ is even, and piecewise constant on $[(i - \frac{1}{2})h, (i + \frac{1}{2})h)$ when $n$ is odd) this in no way affects the error estimates given below. Consequently, a fixed mesh is used for all time as a notational convenience.

We prove our result for the following formulation of Glimm's scheme. We assume that $u_0$ has bounded variation, and that $\|f'\|_{L^\infty(\mathbb{R})}$ is finite. Choose a positive mesh size
h. For each integer i, let $I_i$ be $[ih, (i+1)h)$, and let $\chi_{I_i}$ be the characteristic function of $I_i$. We assume that the time step, $\Delta t$, satisfies $0 < \Delta t \le h/(2\|f'\|_{L^\infty(\mathbb{R})})$, and we define $t^n = n\Delta t$. For each nonnegative integer $n$, we define a function $U^n: \mathbb{Z} \to \mathbb{R}$ of bounded variation in the following way. Let

$$ (1) \qquad U_i^0 = \frac{1}{h} \int_{I_i} u_0(x) \, dx $$

for each integer i. If $U_i^n$ has been defined for all i, solve the initial value problem

$$ (2) \qquad \begin{aligned} u_i^n + f(u^n)_x &= 0, & x \in \mathbb{R}, & t^n < t < t^{n+1}, \\ u^n(x, t^n) &= \sum_{i \in \mathbb{Z}} U_i^n \chi_{I_i}(x), & x \in \mathbb{R}. \end{aligned} $$

Choose a random variable $X^{n+1}$, uniformly distributed on $[0, h)$, so that the set of random variables $\{X^1, \dots, X^{n+1}\}$ are independent; the values of $U_i^{n+1}$ are then given by

$$ (3) \qquad U_i^{n+1} = u^n(ih + X^{n+1}, t^{n+1}) $$

for every i. Chorin [1] seems to have been the first to use exactly one random choice for all intervals $I_i$.

As can be seen from the definition, $U^n$ is itself a random variable that depends on the sequence of random variables $X^1, \dots, X^n$; we propose to bound the expected value of the error at time $t^N$, $E(\|u(\cdot, t^N) - u^N(\cdot, t^N)\|_{L^1(\mathbb{R})})$.

Because, for any values of $X^1$ through $X^N$, the approximate solution satisfies the differential equation exactly for $(x, t) \in \mathbb{R} \times (t^n, t^{n+1})$, the following theorem of Kuznetsov applies (see [8]).

**LEMMA 2** [Kuznetsov]. If $v(x, t)$ is an exact solution of (C) in every strip $t^n < t < t^{n+1}$ that is right continuous in t, and $\sup_{t \in [0, t^n]} \|v(t)\|_{BV(\mathbb{R})}$ is finite, then

$$ (4) \qquad \begin{aligned} \|v(\cdot, t^N) - u(\cdot, t^N)\|_{L^1(\mathbb{R})} &\le \|u_0 - v_0\|_{L^1(\mathbb{R})} + 2\epsilon \|u_0\|_{BV(\mathbb{R})} \\ &\quad + \sum_{n=1}^N \rho_\epsilon(v(t^n), u(t^n)) - \rho_\epsilon(v(t^n-0), u(t^n)) \end{aligned} $$

where

$$ \rho_{\epsilon}(w, z) = \int_{\mathbb{R}} \int_{\mathbb{R}} \frac{1}{\epsilon} \eta\left(\frac{x-y}{\epsilon}\right) |w(x) - z(y)| \, dx \, dy, $$

and $\eta$ is any nonnegative smooth function with support in $[-1, 1]$ and integral one. From this lemma it follows that

$$ \begin{aligned} E(\|u(\cdot, t^N) - u^N(\cdot, t^N)\|_{L^1(\mathbb{R})}) &\le \|u_0(\cdot) - u^0(\cdot, 0)\|_{L^1(\mathbb{R})} + 2\epsilon \|u_0\|_{BV(\mathbb{R})} \\ &\quad + \sum_{n=1}^N E(\rho_\epsilon(u^n(t^n), u(t^n)) - \rho_\epsilon(u^{n-1}(t^n), u(t^n))). \end{aligned} $$

If we let $E^n(f)$ denote the conditional expectation of $f$ given $X^1, \dots, X^{n-1}, X^{n+1}, \dots, X^N$, then (writing $t$ for $t^n$, $X$ for $X^n$, and $\eta_\epsilon(x)$ for $(1/\epsilon)\eta(x/\epsilon))$,
$$
\begin{align*}
& E^n(\rho_e(u^n(t), u(t)) - \rho_e(u^{n-1}(t), u(t))) \\
&= \int_{[0,h]} \sum_{R \in \mathcal{Z}} \int_{I_i} \eta_e(x-y) \frac{1}{h} \left\{ \begin{aligned}[t]
& |u^{n-1}(ih+X, t) - u(y, t)| \\
& - |u^{n-1}(x, t) - u(y, t)|
\end{aligned} \right\} dx dy dX \\
&= \int_{\mathbb{R}} \sum_{i \in \mathcal{Z}} \int_{I_i} \int_{I_i} \eta_e(x-y) \frac{1}{h} \left\{ \begin{aligned}[t]
& |u^{n-1}(z, t) - u(y, t)| \\
& - |u^{n-1}(x, t) - u(y, t)|
\end{aligned} \right\} dz dx dy \\
&= \frac{1}{2} \int_{\mathbb{R}} \sum_{i \in \mathcal{Z}} \int_{I_i} \int_{I_i} (\eta_e(x-y) - \eta_e(z-y)) \\
& \qquad \times \frac{1}{h} \{ |u^{n-1}(z, t) - u(y, t)| - |u^{n-1}(x, t) - u(y, t)| \} dz dx dy \\
&\le \frac{1}{2} \int_{\mathbb{R}} \sum_{i \in \mathcal{Z}} \int_{I_i} \int_{I_i} |\eta_e(x-y) - \eta_e(z-y)| \frac{1}{h} |u^{n-1}(z, t) - u^{n-1}(x, t)| dz dx dy.
\end{align*}
$$

If we now integrate over $y$, we find that

$$ \int_{\mathbb{R}} |\eta_e(x-y) - \eta_e(z-y)| dy \le |z-x| \frac{\|\eta'\|_{L^1(\mathbb{R})}}{\epsilon}. $$

Trivially, $|u^{n-1}(z, t) - u^{n-1}(x, t)| \le \|u^{n-1}(t)\|_{BV(I_i)}$. So it follows that (5) is bounded by

$$
\begin{align*}
& \frac{1}{2} \sum_{i \in \mathcal{Z}} \int_{I_i} \int_{I_i} \frac{|z-x|}{h} dz \, dx \frac{\|\eta'\|_{L^1(\mathbb{R})}}{\epsilon} \|u^{n-1}(t)\|_{BV(I_i)} \\
&\le \sum_{i \in \mathcal{Z}} \frac{h^2}{6} \frac{\|\eta'\|_{L^1(\mathbb{R})}}{\epsilon} \|u^{n-1}(t)\|_{BV(I_i)} \\
&= \frac{h^2}{6} \frac{\|\eta'\|_{L^1(\mathbb{R})}}{\epsilon} \|u^{n-1}(t)\|_{BV(\mathbb{R})}.
\end{align*}
$$

The inequality $\|u^{n-1}(t)\|_{BV(\mathbb{R})} \le \|u_0\|_{BV(\mathbb{R})}$ is clear, because the choice of the initial data (1), the evolution of $u^{n-1}$ through (C) (2), and the random choice process (3) are all variation diminishing. Thus,

$$ E^n(\rho_e(u^n(t), u(t)) - \rho_e(u^{n-1}(t), u(t))) \le \frac{h^2}{6} \frac{\|\eta'\|_{L^1(\mathbb{R})}}{\epsilon} \|u_0\|_{BV(\mathbb{R})} $$

uniformly with respect to the other random variables $X^i$, implying that $E(\rho_e(u^n(t), u(t)) - \rho_e(u^{n-1}(t), u(t)))$ is bounded by the same quantity. Therefore, if $T = N\Delta t$, by using an obvious bound for the initial error, we have

$$
\begin{equation} \tag{6}
\begin{split}
E(\|u(\cdot, T) - u^N(\cdot, T)\|_{L^1(\mathbb{R})}) &\le h \|u_0\|_{BV(\mathbb{R})} + 2\epsilon \|u_0\|_{BV(\mathbb{R})} \\
&\quad + \frac{T}{\Delta t} \frac{h^2}{6} \frac{\|\eta'\|_{L^1(\mathbb{R})}}{\epsilon} \|u_0\|_{BV(\mathbb{R})}.
\end{split}
\end{equation}
$$

By letting $\eta \to \frac{1}{2}\chi_{[-1,1]}$, $\|\eta'\|_{L^1(\mathbb{R})}$ may be chosen arbitrarily close to 1. Minimizing (6)
with respect to $\varepsilon$ gives

$$ (7) \qquad E(\|u(\cdot, T) - u^N(\cdot, T)\|_{L^1(\mathbf{R})}) \le \left(h + \frac{2}{\sqrt{3}} \left(\frac{h}{\Delta t}\right)^{1/2} (hT)^{1/2}\right) \|u_0\|_{BV(\mathbf{R})}. $$

The theorem is proved. We remark that if one chooses to interpret Glimm's method as providing that the approximate solution is equal to $U_i^n$ on $[ih, (i+1)h) \times [t^n, t^{n+1}]$, then the above inequality still holds with a small change for the error incurred in at most one time step.

It is well known that monotone finite difference schemes, such as Godunov's, perform better for problems with uniformly convex fluxes than for problems with linear fluxes; in fact, Godunov's method is $O(h)$ accurate for the problem

$$ (8) \qquad \begin{aligned} & u_t + \left(\frac{u^2}{2}\right)_x = 0, \quad x \in \mathbf{R}, \quad t > 0, \\ & u(x, 0) = \chi_{(-\infty, 0]}(x). \end{aligned} $$

For problems, such as this one, whose solution consists of a single shock of height one, the expected error in Glimm's scheme may be estimated directly by applying the central limit theorem. If the shock speed is $s$, and $p = s\Delta t/h$, then after $N$ time steps, the probability distribution of the shock location error is approximately normal with mean 0 and variance $\sigma^2 = Np(1-p)h^2$. Asymptotically, the expected value of the $L^1(\mathbf{R})$ error, which is the absolute value of the shock location error, is $\sqrt{8/\pi}\sigma$, or $((8/\pi)p(1-p)h/\Delta t)^{1/2}(Th)^{1/2}$, where $T = N\Delta t$. Our bound on the ratio $\Delta t/h$ implies that $0 \le p \le \frac{1}{2}$. For instance, when Glimm's scheme is applied to (8) with $\Delta t = h/2$, $p = \frac{1}{4}$, the expected value of the error is about $0.6910(h/\Delta t)^{1/2}(hT)^{1/2}$. Theorem 1 gives a bound of $1.1547(h/\Delta t)^{1/2}(hT)^{1/2}$ independently of the value of $p$, a fairly close result.

**2. Godunov's method.** Godunov's finite difference scheme [4] falls into the class of monotone, conservative, finite difference schemes for (C), a class that has been analyzed previously; see, for example, Kuznetsov's paper or Sanders [13]. These papers show that the error at time $T$ is bounded by $C(h + (hT)^{1/2})\|u_0\|_{BV(\mathbf{R})}$ when the time step $\Delta t$ is proportional to $h$, but a good estimate of the constant is not available. In the next theorem we derive a different bound in which the independent effects of $\Delta t$ and $h$ appear along with an explicit determination of a constant $C$, a result that will prove useful in the next section.

Godunov's scheme differs from Glimm's scheme only in that Godunov determines $U_i^{n+1}$ by averaging $u^n(\cdot, t^{n+1})$ over $I_i$:

$$ (3') \qquad U_i^{n+1} = \frac{1}{h} \int_0^h u^n(ih + X, t^{n+1}) \, dX. $$

The following theorem shows that the error in Godunov's method is bounded by the same expression that bounds the expected error in Glimm's scheme.

**THEOREM 3.** If $u^n(x, t)$ is the solution of Godunov's method for $t^n \le t < t^{n+1}$, $u(x, t)$ is the entropy solution of (C), and $T = N\Delta t$, then

$$ (9) \qquad \|u(\cdot, T) - u^N(\cdot, T)\|_{L^1(\mathbf{R})} \le \left(h + \frac{2}{\sqrt{3}} \left(\frac{h}{\Delta t}\right)^{1/2} (hT)^{1/2}\right) \|u_0\|_{BV(\mathbf{R})}. $$
*Proof.* We proceed as in Theorem 1. Again, with $t = t^n$,

$$
\begin{align*}
& \rho_e(u^n(t), u(t)) - \rho_e(u^{n-1}(t), u(t)) \\
&= \int_{\mathbb{R}} \sum_{i \in \mathbb{Z}} \int_{I_i} \eta_e(x-y) \{|U_i^n - u(y,t)| - |u^{n-1}(x,t) - u(y,t)|\} dx dy \\
&= \int_{\mathbb{R}} \sum_{i \in \mathbb{Z}} \int_{I_i} \eta_e(x-y) \left\{ \left| \frac{1}{h} \int_{[0,h)} u^{n-1}(ih+X,t) dX - u(y,t) \right| - |u^{n-1}(x,t) - u(y,t)| \right\} dx dy \\
&\le \int_{[0,h)} \int_{\mathbb{R}} \sum_{i \in \mathbb{Z}} \int_{I_i} \eta_e(x-y) \frac{1}{h} \{|u^{n-1}(ih+X,t) - u(y,t)| - |u^{n-1}(x,t) - u(y,t)|\} dx dy dX.
\end{align*}
$$

One may now follow the series of inequalities in (5) and the subsequent arguments to obtain the estimate in the statement of the theorem. □

The estimate is rather sharp: by exploiting the relationship of the solution of Godunov's method and the cumulative probability distribution of a binomial random variable, one can show that Godunov's scheme applied to the problem with $f(u) = u$, $u_0(x) = \chi_{(-\infty,0]}(x)$, and $\Delta t/h = \frac{1}{2}$ has an asymptotic error rate of $(4/\pi)^{1/2}(Th)^{1/2} = 1.1283(Th)^{1/2}$, compared to our estimate of $2\sqrt{3}(Th)^{1/2} = 1.6330(Th)^{1/2}$. (That the error in this example is $O(h^{1/2})$ may be inferred from results in [6].) Note that our analysis applies even if the CFL condition $\Delta t < h/(2\|f'\|_{L^\infty(\mathbb{R})})$ is violated, as long as the wave interactions in the solution of (2) are calculated exactly; this will prove important in the next section.

**3. LeVeque's method.** LeVeque [11] proposed a numerical scheme for scalar conservation laws in one space dimension whose main idea is to approximate the solution of (C) using piecewise constant states, and to calculate the trajectories of shocks (straight lines) and their interactions exactly. Expansion waves are approximated by a series of constant states separated by entropy violating shocks. At the end of each time step the approximate solution is projected back onto the grid by averaging, as in Godunov's method. LeVeque has shown that a variation of his method is total variation diminishing and that a subsequence of numerical approximations converges to a weak solution of the conservation law [9]. He has also conjectured that if entropy satisfying solutions of (C) advance the approximate solution from one time step to the next, then the weak solution to which the approximations converge would indeed be the entropy weak solution. Among other things, we show below that even if certain entropy violating weak solutions are used to propagate the solution between time steps, the numerical approximations still converge to the entropy solution of (C), and we obtain realistic estimates for the error. LeVeque's later extensions of his method to systems of equations choose to ignore the wave interactions rather than to calculate them exactly [10] (this issue, pp. 1051-1073).

Entropy violating shocks used to model expansion waves may be chosen in such a way that LeVeque's formulation is equivalent to a method of Dafermos [2], which uses a piecewise linear approximation $f^h$ to the flux $f$ to advance the approximate solution between time steps. Although true shock speeds in the two methods differ (speeds differ by less than $O(h)$ for weak shocks and $O(h^2)$ for strong shocks), the numerical results of the two methods are qualitatively indistinguishable.
The scheme that we analyze is as follows. Assume that the flux $f$ is $C^2$ and that the initial data $u_0$ is in $BV(\mathbf{R})$ and is constant outside some finite interval. Let $h > 0$ be the mesh size and $\Delta t > 0$ be the time step; define $t^n = n\Delta t$. Let $f^h$ be the continuous, piecewise linear interpolant of $f$ with breakpoints at $ih$, for $i \in \mathbb{Z}$. It is easily seen that

$$ \|f - f^h\|_{\text{Lip}} \le \frac{h}{2} \|f''\|_{L^\infty(\mathbf{R})}, $$

where

$$ \|g\|_{\text{Lip}} = \sup_{x \ne y} \left| \frac{g(x) - g(y)}{x - y} \right|. $$

Define $u_0^h$ by

$$ (10) \qquad u^h(x, 0) = u_0^h(x) = \sum_{i \in \mathbb{Z}} \int_{I_i} u_0(\sigma) \, d\sigma \chi_{I_i}(x). $$

The complete approximation $u^h(x, t)$ is as follows. For every $n$ solve

$$ (11) \qquad u_t^h + f^h(u^h)_x = 0, \quad x \in \mathbf{R}, \quad t \in [t^n, t^{n+1}), $$

with

$$ (12) \qquad u^h(x, t^{n+1}) = \sum_{i \in \mathbb{Z}} \frac{1}{h} \int_{I_i} u^h(\sigma, t^{n+1} - 0) \, d\sigma \chi_{I_i}(x). $$

The analysis of the scheme is in two parts, corresponding to the two equations (11) and (12).

First we describe more carefully how to solve (11). In [2] Dafermos gives the entropy solution of (11) as follows. He first reduces the problem to a Riemann problem because the initial datum is piecewise constant. If $u_0^h$ is specified as

$$ u_0^h(x) = \begin{cases} u_l, & x \le 0, \\ u_r, & x > 0, \end{cases} $$

with $u_l < u_r$, then the vertices of the boundary of the convex hull of $\{(u, v) | u_l \le u \le u_r, v \ge f^h(u)\}$ will consist of a set of points $(u_l, f^h(u_l))$, $(u^1, f^h(u^1))$, ..., $(u^k, f^h(u^k))$, $(u_r, f^h(u_r))$, where $\{u^i\}$ is a linearly ordered subset of $\{jh\}$. The solution will then be given by the following set of constant states:

$$ u^h(x, t) = \begin{cases} u_l & \text{for } -\infty < \frac{x}{t} \le \frac{f^h(u^1) - f^h(u_l)}{u^1 - u_l}, \\ u^1 & \text{for } \frac{f^h(u^1) - f^h(u_l)}{u^1 - u_l} < \frac{x}{t} \le \frac{f^h(u^2) - f^h(u^1)}{u^2 - u^1}, \\ \vdots & \\ u^k & \text{for } \frac{f^h(u^k) - f^h(u^{k-1})}{u^k - u^{k-1}} < \frac{x}{t} \le \frac{f^h(u_r) - f^h(u^k)}{u_r - u^k}, \\ u_r & \text{for } \frac{f^h(u_r) - f^h(u^k)}{u_r - u^k} < \frac{x}{t} < \infty. \end{cases} $$

A similar result may be inferred if $u_l > u_r$ by considering the convex hull of the set $\{(u, v) | u_r \le u \le u_l, v \le f^h(u)\}$. Thus, the general solution of (11) is found as a composition of Riemann problems, all of whose solutions are shocks. The calculation is started anew whenever two shocks coalesce into one.
We now use the following theorem.

**THEOREM 4** [12]. If $f$ and $g$ are Lipschitz continuous, $u_0$ and $v_0$ are in $BV(\mathbf{R})$, and $u$ and $v$ are the entropy solutions of the equations

$$u_t + f(u)_x = 0, \quad x \in \mathbf{R}, \quad t > 0,$$

$$u(x, 0) = u_0(x), \quad x \in \mathbf{R},$$

and

$$v_t + f(v)_x = 0, \quad x \in \mathbf{R}, \quad t > 0,$$

$$v(x, 0) = v_0(x), \quad x \in \mathbf{R},$$

respectively, then

$$\|u(t) - v(t)\|_{L^1(\mathbf{R})} \le \|u_0 - v_0\|_{L^1(\mathbf{R})} + t \|f - g\|_{\text{Lip}} \min (\|u_0\|_{BV(\mathbf{R})}, \|v_0\|_{BV(\mathbf{R})}).$$

Thus, if $\bar{u}$ is the solution of

$$\bar{u}_t + f^h(\bar{u})_x = 0, \quad x \in \mathbf{R}, \quad t > 0,$$

$$\bar{u}(x, 0) = u_0^h(x), \quad x \in \mathbf{R},$$

then

$$\|\bar{u}(t) - u(t)\|_{L^1(\mathbf{R})} \le \left(\frac{t}{2}\|f''\|_{L^\infty(\mathbf{R})} + 1\right) h \|u_0\|_{BV(\mathbf{R})}.$$

Because $u^h$ is the Godunov approximation to $\bar{u}$ and $\|u_0^h\|_{BV(\mathbf{R})} \le \|u_0\|_{BV(\mathbf{R})}$, it follows from the triangle inequality and (9) that

$$\|u(T) - u^h(T)\|_{L^1(\mathbf{R})} \le \left( h + \frac{Th}{2} \|f''\|_{L^\infty(\mathbf{R})} + \frac{2}{\sqrt{3}} \left(\frac{h}{\Delta t}\right)^{1/2} (hT)^{1/2} \right) \|u_0\|_{BV(\mathbf{R})}.$$

This result implies that if $\Delta t$ is about the same size as $h$, then the error at time $T$ is $O(h + hT + (hT)^{1/2})$; for $\Delta t$ in this regime, the averaging error of Godunov's method dominates the error bound, causing the scheme to be $O(h^{1/2})$ accurate. However, if only one time step is taken, and $\Delta t = T$, then the error at time $T$ is $O(h + Th)$, i.e., the method is first order accurate. This explains why LeVeque achieved such good numerical results when he reduced the number of time steps in his experiments [11].

**Acknowledgment.** I would like to thank David Hoff for informing me of the problem of error bounds for Glimm's method.

## REFERENCES

[1] A. J. CHORIN, *Random choice solution of hyperbolic systems*, J. Comp. Phys., 22 (1976), pp. 517-533.

[2] C. M. DAFERMOS, *Polygonal approximations of solutions of the initial value problem for a conservation law*, J. Math. Anal. Appl., 38 (1972), pp. 33-41.

[3] J. GLIMM, *Solutions in the large for nonlinear hyperbolic systems of equations*, Comm. Pure Appl. Math., 18 (1965), pp. 697-715.

[4] S. K. GODUNOV, *A finite difference method for the numerical computation of discontinuous solutions of the equations of fluid dynamics*, Mat. Sb., 47 (1959), pp. 271-306. (In Russian.)

[5] A. HARTEN AND P. D. LAX, *A random choice finite difference scheme for hyperbolic conservation laws*, this Journal, 18 (1981), pp. 289-315.

[6] G. HEDSTROM, *Models of difference schemes for $u_t + u_x = 0$ by partial differential equations*, Math. Comp., 29 (1975), pp. 969-977.

[7] D. HOFF AND J. SMOLLER, *Error bounds for the Glimm scheme for a scalar conservation law*, to appear.
[8] N. N. KUZNETSOV, *Accuracy of some approximate methods for computing the weak solutions of a first-order quasi-linear equation*, USSR Comp. Math. and Math. Phys., 16, 6 (1976), pp. 105-119.

[9] R. J. LEVEQUE, *Convergence of a large time step generalization of Godunov's method for conservation laws*, Comm. Pure Appl. Math., 37 (1984), pp. 463-477.

[10] ——, *A large time step generalization of Godunov's method for systems of conserved laws*, this Journal, this issue, pp. 1051-1073.

[11] ——, *Large time step shock-capturing techniques for scalar conservation laws*, this Journal, 19 (1982), pp. 1091-1109.

[12] B. J. LUCIER, *A moving mesh numerical method for hyperbolic conservation laws*, Math. Comp., to appear.

[13] R. SANDERS, *On convergence of monotone finite difference schemes with variable spatial differencing*, Math. Comp., 40 (1983), pp. 91-106.