AN I M P L I C I T / E X P L I C I T S P E C T R A L M E T H O D FOR BURGERS' EQUATION N. BRESSAN (l) . A. QUARTERONI (2) (3)
ABSTRACT Chebyshev spectral collocation methods for approximating the solution of Burgers' equation are defined and analyzed. Discretization in time by an implicit/explicit single step method is discussed. This method is shown to be stable under a very weak condition on the time step, for the (linear) diffusive part is dealt with implicitly. Besides, fast transform methods can be used to compute the explicit (non linear) convective term. Optimal order error estimates are established in the weighted L2-norm. -
1. I n t r o d u c t i o n
T h e purpose of this paper is to study a fully discrete numerical method for the Burgers problem: 0u
02u
~u
- v ~ + u ~ = 0
0t (1.1)
0x 2
f o r x 9 (-1,1), t e ( 0 , T)
0x
u(-1, t) = u(l, t) = 0
for t 9 (0, T)
u(x, 0) = uo (x)
for x 9 (-I, 1)
where T > 0 and v>0 are two fixed real numbers.
--
(l) Brescia. (2) (3) through
Received 30 September 1986. Dipartimento di Matematica Universit~ Cattolica Via Trieste, 17 - 25100 Istituto di Analisi Numerica del C.N.R. Corso C. Alberto, 5 - 27100 Pavia. The research of this author has been partiallysupported by the U.S. Army its European Research Office under contract No. DAJA-84--C-0035.
266
N. BRESSAN- A.
QUARTERONI:
An Implicit~explicit Spectral
The approximation in space is based on the pseudo-spectral Chebyshev method, i.e., a collocation scheme at the Chebyshev-Gauss nodes. This method guarantees high accuracy for problems with smooth solutions, for the order of convergence depends on the degree of smoothness of u only (e.g., [7]). Several stability and convergence results for the approximation in space of parabolic problems by the Chebyshev method can be found in the existing literature. We refer to [6] for the heat equation, and to [2], [1] and [5] for the linear advection-diffusion equation. The steady Burgers problem has been analyzed in [ 13] and [14]. Discretization in time by fully explicit schemes is discouraged from too severe stability conditions, which take the form At-N 4 ~ constant, where A t > 0 is the time-step and N is the number of collocation points. Implicit methods for the linear, diffusive part, and explicit methods for the nonlinear, convective part are generally used in applications. We refer, e.g., to [4], [9] and [15], where several comparisons with other space discretization methods are also presented. Implicit/explicit methods are generally free of restrictions on the time-step. Moreover, the advective term, which is known at previous time levels, can be computed by the FFT with an order of Nlog2N operations. In this paper, the first order-backward/forward Euler method is investigated. In a previous work [1], this method has been shown to be unconditionally stable for the linearized Burgers problem. We prove here that, for the quasi-linear problem (1.1), stability can be achieved provided A t vanishes faster than N -1/2. This condition is not influent in applications, where the number of collocation points used to get a desired spatial accuracy is always relatively large. Moreover, it is proven that at each time interval the fully discrete Euler-Chebyshev solution converges to the solution of (1.1) with the optimal order in the weighted L2-norm. Convergence in the maximum norm is also shown. We use a truncation for bounding the coefficient of the advective term. This leads to an auxiliary pseudo-spectral problem, which is eventually shown to coincide with the time collocation problem i f / k t and N-1 are small enough. This idea can be also used for other nonlinear problems to infer stability and convergence of spectral approximations. At the expense of further technical difficulties only, the same kind of results could be proven for higher order time-advancing methods of implicit/explicit
Methodfor Burgers' Equation
267
type. Among them there is the second order Crank-Nicolson/Adams-Bashforth scheme, which is probably the mostly preferred in applications. An outline of this paper is as follows. In Section 2 we review existence, uniqueness and regularity results for the solution to (1.1) in the weighted Sobolev spaces, for any T > 0 . In Section 3 the fully discrete Euler-Chebyshev method is derived, while Section 4 is devoted to the stability and convergence analysis.
2. Existence, uniqueness and regularity results. We denote by D the one dimensional interval (-1, 1), by L p ($2), l~
space of measurable functions for which the norm [ u [p = (~1 [ u (x) [P dx) 1/p is finite, and by H r (D) the Sobolev space of those functions o f L 2 (D) for which the norm
II u Ilr = k(__J:0[u/k) 122)x/2is finite, for any
positive integer r. Here u (k) denotes
the distributional derivative ofu of order k. I f r is not an integer, the space H r (D) is defined by interpolation (e.g. [12]). If p = 2 we set for simplicity H = L 2 (~), and
lui = lu12 If p=Oo we define, as usual, [u[| = sup e ~ [u(x)[. Moreover, we set V=Hl0 (~2) = { u e H 1 (D) [ u ( - 1 ) = u(1)= 0}. We recall that, for the Poincar~ inequality, [ux[ is a norm for the space V. In this paper this norm will be denoted by [[ u I[. If X is a Banach space and T is a given positive real number, we set: LP (X) = {u ] u: [0, T] ~ X is measurable, T
(fo [I u (t)[[~ dt) 1/p < oo supess t
~
[[u(t) llx
< oo
if l ~ p < + o o , ifp=oo }
(0,T)
Throughout this paper, C will denote a generic positive constant, which may vary in different contexts, but which is always independent of the discretization parameters N and At. We introduce the Burgers problem:
268
N. BRESSAN - A. Ut--VUxx + U U x =
(2.1)
QUARTERONI:
An Implicit~explicit Spectral
in ~2x (0, T)
0
U(X,0) = u0(x )
for x~g2
u ( - l , t) = u(1, t) = 0
for 0~
where u0 is a given function and, for simplicity, we have set Ou at =
and u~=
Ot
Ou
Ox
The existence of a global solution for all T
which reduces (2.1) to the heat equation ~ , = v~v,o,(see, e.g., [19]). Moreover, the solution to (2.1) tends to zero uniformly in ~ as t---,oo (see [17], thin. 21.1). We note that for a.e. t~
(ut, v) + va(u, v) + b(u, u; v) = 0 for vEV 1
where (u, v) = f l u(x)v(x)dx denotes the inner product of H, a(u, v) = (ux, vx), and b(u, v; z) = *[1 uv• I f u0 e H, the existence of a solution u e L 2 (V) ['1 L = (H) of (2.2) can be proven by the classical Faedo-Galerkin method, using a compactness argument and the identity b (v, v; v) = 0 for v ~V. We refer the interested reader to [11], Ch. 1, where this technique is applied, among others, to the Navier-Stokes equations. The uniqueness of the above solution can be proven using the following Sobolev inequality which holds in one space dimension:
(2.3)
Ivl. -< c II v IJ' 21 v I For the solution of (2.1) the following maximum principle holds.
Methodfor Burgers' Equation
269
Lemma 2.1. Assume that [ Uo I~ ~< M; thenfor any finite T > 0
(2.4)
11u IlL|
~< M
Proof. Let us take v = (u-M) + as test function in (2.2). We recall that, for any function w, w + and w- denote respectively the positive and the negative part ofw. T h e n w = w + - w - and w+w-=0, thus w2=(w+) 2 + (w-) 2. Moreover, from the Rellich theorem (see e.g. [10]) i f w E H 1 (f2), then, w + r l (f2) and wxin { x~f2[w
(x) > O}
W+)x = 0 in (x~QIw (x) ~ 0} in the sense of distributions. Then, writing u = ( u - M ) + M 1
b(u,u;v) = 1
1
2
1
f (U2)x(u-M)+dx =
f~[(u_M)+]2
we find:
I fl{(U-M)2+2M(u-M)}x(u-M)+dx= 2
+ 2M (u-M)+}x ( u - M ) + d x =
2
i
ill{ [(H_M) +]3}•
6
dx +
I M 2
fl ( [ ( u - M ) * ] ~ L d x
= 0
for ( u - M ) + (1) = (u-M) + (-1) = 0. Moreover:
a(u, v) = f
1 1 [(u-M) +
- (u-M)-]x [(u-M)+],, dx I> 0
Then from (2.2) it follows
1 d 0 >I (ut, (u-M) +) = - - - - _ _ I ( u - M ) + (t)[ 2, 2 dt from which ] ( u - M ) + (t) ] ~ [ (u-M) + (0) [ = I (uo-M) + I = 0
N. BRESSAN - A. QUARTERONI:An Implicit/explidt Spectral
270
We obtain that (u (x, t)-M) += 0 for i.e. x~g2, thus u(x, t)~
-M i.e. in I2x(0, T), hence (2.4) holds. 9 We introduce now the Chebyshev weight w (x) = (1-xZ) -In, - l < x < l , and we define LP~ (~2) as the space of the measurable functions for which [ u [p,w = 1
Jl
(~1 [UP(X) ] W (X) dx) vp is finite. For p = 2 we set[ u Iv, = ] u ]2,wSimilarly, for any integer r>~0 we define the weighted Sobolev space I-I~(g2) as the space of those functions of L~(I2) for which the norm [[ u [Ir,w = (k=~OlU(k)l~)'/2is finite. If r is not an integer the above spaces are defined by interpolation (see e.g. [8]). For notational convenience we set H w_-_ L w2 (•) and Vw=H~,0 (f2), where H~,0 (D) is the subspace of the function o f H ~ (D) for which u(1) = u(-1) = 0. If u is any function of Vw, then I Ux I~, is equivalent to II u 11,, (see [2]) and we will set II u Ilw = I Ux Iw in this paper. In Section 3 we will analyze a Chebyshev collocation approximation to problem (2.1), therefore we are now interested in proving that the solution of (2.1) satisfies (2.5)
L | (Hw)
u ~L 2 (Vw) fl
This result could be proved by the same technique of [11] used for proving that u e L 2 (V) fl L | (H). O f course, this time we have to assume that u0 e Hw. However, a much shorter proof can be given by using the information (2.4). Obviously, this proof will require that u0 e L = (f2), however this assumption is not restrictive in our application. Indeed, the Chebyshev collocation scheme we are introducing in next section demands that u0 be a continuous function in ~. We note that if u e L = (12), then u e Hw, for 1 1
Therefore from L e m m a 2.1 we obtain that the solution of (2.1) belongs to
L=(Hw). I
1
We denote by (u, v)w = ~-jluvwdx the inner product of H,~ and by aw (u, v) =
flUx (VW)x dx the Dirichlet form relative to the Chebyshev weight. It has been
Methodfor Burgers' Equation
271
1 1 shown (e.g. [2]) that aw is a continuous form on Hw(D)xHw(g2), and it is coercive on Vw, i.e., there is a positive a such that
(2.6)
aw (v, v)
a II v
for all v eVw
N o w to look for a solution of problem (2.1) satisfying (2.5) is equivalent to look for a solution to the variational problem (2.7)
(ut, v)w +yaw (u, v) + bw (u, u; v) = 0
for all v e V w
1
where b,, (u, v; z) = [ uvxzwdx. If we define the operator Bw as follows: g- 1
= bw (u, u; v) where < . , . > is the duality pairing from V~ to Vw, we see that B~,(u) e L 2 (V~,) ifu is the solution to (2.1). Indeed, for all v~Vw we can use the inequality ([14])
t
(u),v>l = I- 21 f'lu 2 ( v w ) x d x [ ~ C [ u l w l u [ |
from which the result follows since u e L 2 (L = (s In addition, ut e L 2 (V') from (2.2) (note that V' C V ' ) . Therefore, since the solution of (2.7) satisfies (2.8)
yaw (u, v) = -
for all v ~ V,~
we conclude that u s L 2 (Vw). The proof of (2.5) is now complete. THEOREM 2.1. Assume that uo ~ H~ (Q) N Vw. Then (2.9)
ut e L 2 ( v w ) N L = (Hw)
(2.10)
u ~ L = (H~ (sg) fl Vw).
Proof The proof of (2.9) is classical, and relies upon the use of the Faedo-Galerkin method applied to equation (2.7) after differentiation with respect to t. To prove (2.10) we will use the following regularity theorem (see [13]): i f f ~ Hw and
aw (u, v) -- (f, v)w
(2.11) I
then u ~ H~ (s
f] Vw.
for all v e Vw,
272
N. BRESSAN - A.
QUARTERONI:
An Implicit~explicit Spectral
For all v 9 Hw we note that:
I (B,,, (u),
C lu
II u IIw Iv Iw
Hence, setting f(t) = -ut(t)-Bw(u(t)) we find f 9 L = (Hw) from (2.9). Now (2.10) follows from (2.8) using (2.11). I We note that from (2.5) and (2.9) it follows in particular that u 9 H l (Vw). Therefore u is continuous in ~ x [0, T] and (2.4) can be read as follows (2.12)
max { [ u (x, t) [,
-l~x~l,
0 ~ t ~ T } ~< M
We present now an equivalent formulation of problem (2.7). We introduce the continuous function ~: R----~R
x (2.i3)
r (x) =
if] x} ~ 2M,
2M
if x > 2M,
-2M
ifx <-2M.
We note that q~ is Lipschitz continuous, namely (2.14)
[ ~< I ~; - ~2 ]
I q~(~) - r
for all ~t, ~2 9 R
By virtue of (2.12) we deduce that q~ (u(x, t)) = u (x, t) for all (x, t) 9 ~2x[0,T], then we can rewrite problem (2.7) equivalently as
(2.15)
(u,v)w + yaw (u, v) + 21 f l(q~ ~ (u) u)x vwdx = 0
for all v 9 V~
In view of (2.12), the solution of (2.7) is clearly a solution of (2.15) as well. To show that (2.15) and (2.7) are equivalent problems, it is enough to prove that (2.15) has a unique solution. This can be readily seen. As a matter of fact, assuming that ul and u2 are two solutions of (2.15), their difference e = ul - u2 satisfies: A 1
(et, e),.,, + va,,, (e, e) = - ~
g- 1
( [q~ (ux) e]x + [[q~ (ul) - q> (u2)]u2],,} ewdx
Methodfor Burgers"Equation
273
Integrating by parts we have ,
~
I f , [r
el,, ewdx I = I- I , ~ (ut) e (ew)xdx I < CM
c,
lel,,,llell,,, ~<
lel$ + av Ilell~
//
and t
[[q~ (ul) - r (u2)] u2]. ewdx I = [ - f , [ r ( u l ) - r (u2)]u2 (ew).dx I (by (2.14)) [elw tu21| Ilellw ~
C2
lel2w lu21~ + av Ilell~.
/)
Since yaw (e, e) ~> va
Ilell2wone
has
d lel~ < ( c , +
62 [u2l~)lel~
dt
v
v
Using the Gronwall lemma we conclude that e (t) - 0 since e (0) = 0. In Section 4 we will deduce the stability and convergence properties of the scheme approximating problem (2.1) from the same properties proved for the discretization of problem (2.15). Problem (2.15) is therefore a mathematical device only.
3. The implicit/explicit spectral scheme For any integer N, let PN be the space of algebraic polynomials of degree at most N on D, and P~ = { p E PN I P (--1) = p (1) = 0}. Denote by {xl, wi}Ni=0 the nodes and weights of the Gauss-Lobatto integration formula relative to the Chebyshev weight. We recall that xi = cos ,0~i~
and
For any function v, continuous on ~, let IN v ~ PN denote its interpolant at the points xi, i = 0, ..., N. Then ([3]): (3.1)
I[ V-IN v ]kw --< C II v Ho,wN2,'-o, o >
1,O<~g<~a. 2
N. BRESSAN - A. QUARTERONI:An Implicit~explicit Spectral
274
For a given integer m > 0 , let A t = T / m be the time-step, and set t k = k a t for k = 0 , ..., m. For any function ~O=q~(t) the symbol q~kwill denote the value of~0(tk). A pseudo-spectral approximation of problem (2.1) can be defined as follows. At any time-level t TM we look for a function yk+l e ~ such that
(3.2)
__1
{yk+l (Xi) _ yk (Xi) } -- vY,,~k+l (Xi) .1_
At
l {IN [(yk)2]}x (xi) = 0 2 for i = 1. . . . , N-1
and y0 =
INU0. The non-linear term in (3.2) is computed by the usual
pseudo-spectral differencing technique, which consists of replacing a function by its interpolant at the Chebyshev points before differencing it. The scheme (3.2) is of implicit type but the non-linear term is dealt with explicitly. This allows an efficient use of the F.F.T. algorithm in the computations. (Fully explicit schemes are generally avoided for parabolic equations since they would imply extremely severe restrictions on the time-step of the form A t = 0 (N 4) in order to achieve stability [7]). In view of the analysis we will carry out in the next section, it is convenient to state problem (3.2) in variational form. For this we introduce the discrete inner product
(3.3)
N (0, ~0)N = ~' ~ (Xi) ~) (Xi) Wi i=0
for 0, ~0 EC ~ (~)
which satisfies: (3.4)
(q~, ~P)N = (q~, ~P)w
for all q~, ~p: ~O9 ~p E P2N-I.
It turns out that the discrete norm i[ v equivalent to the norm [" [w, namely [3]
(3.5)
I v Iw
II v IIN
g -I v Iw
IIN =
((v,
is uniformly
for all v ~ PN.
Due to (3.3) and (3.4) problem (3.2) can then be restated as follows: (3.6)
1 (yk+l _ yk, v) N -t- Yaw (yk+l, v) -t- 1 ({IN [(yk)2]}., V)N = 0 At 2 for all v e WN and k = 0, ..., m-1
Methodfor Burgers' Equation
275
4. Stability and convergence theorems In this section we will prove stability and convergence for the numerical problem (3.6). For this, we analyze an auxiliary numerical problem which, in analogy with (2.15), is defined as follows: (4.1)
__1 ( u k + l _ U k , v ) N + V a w ( U k + l , v ) + At
1 ({IN [ r (U k) uk]}x, V)N = 0 2
for v ~ P~, and k = 0, ..., m-1. Here U k+l e P~, for k~>0 and U~
.
For each k~>0, problem (4.1) has a unique solution U k+l, for each N and At. Indeed, (4.1) can be written as
- -1 (U k+l, V)N +
yaw (U k+l, v) = (h(Uk), V)N for v e P~.
At The bilinear form on the left hand side is continuous and coercive on P~ x P~ with respect to the norm II. []w, as it follows immediately from (2.6) and (3.4). Moreover, using (3.4) and (3.5) it is readily seen that the right-hand side is bounded by C [ U k Iw I[ v I[w, i.e., it is an element of the dual space of Vw. Thus existence and uniqueness are ensured by the Lax-Milgram theorem. The next theorem will show that the solution to (4.1) remains bounded for all values of N and /~ t. Finally, we will show that r (U k) = U k for all k ~ 0 provided N -1 and A t are sufficiently small. Therefore, under this assumption on N and At, the two problems (4.1) and (3.2) do coincide, thus U k is equal to the pseudo-spectral solution Yk for each k~>0. THEOREM 4.1. The scheme (4.1)/s unconditionally stable, namely there exists a constant A independent of both N and ZXt such that (4.2)
IIUk IIN ~< exp (AT/2v)[I u0 [IN
0 ~
Proof Take v = U k+l into (4.1), use the Cauchy-Schwarz inequality and (2.6) to get (4.3)
2At{ll U 1 +,2flN_IIU
+ =,,llv=+'llw~"~I [({ IN[~ (uk) uk] }x,Uk+ I)N I 2
N. BRSSSAN- A. QUAaTEa0m: An Implicit~explicit Spectral
276
By (3.4) and integration by parts, we obtain:
I ({~,, [4 (u ~) uk]}x, Uk+')N i = I (IN [4 (U k) Uk],
U TM W
w)x )w I
Since U T M ~ P~, (uk+lw)x E PN-1; using (3.4), the Cauchy-Schwarz ine-
W quality and recalling that wi >0, 0~
] (IN It'D(Uk) uk], (uk+lW)x)w ] ~--- I ( r (U k) U k, (uk+lw)x w w max
(4.4)
O~i~N
[ q~ (U k) (xi) I 11 uk [IN [I
U k+l W)X[lN ~ w
2Ma II U ~ II~ IIUT M llw where we have used the inequality (see [2]) I (VWlx Iw ~ a I1 v IIw
(4.5)
for all v s Vw
W
Now from (4.3) and (4.4) it follows that:
l
{ II uk+' tI~ -II u" II~ ) ~<
2 ZXt
M 2 6z 4av
II o k II~
Thus: (4.6)
[] u
M 2 62
TM
II~ ~< (1 + ~
2av
M 2 6z
~ t ) I I u " ll~ ~ (1 + ~ A t ? 2av
'+, 1tuoll~
Since, for any real x, eX~>l+x, from (4.6), setting A = M 2 62/2a, we get the desired result. 9 Remark 4.1. For fixed v and A t, inequality (4.2) insures that stable solutions can be obtained by letting ZXt and N -1 to vanish independently each other. When v--~0, the bound (4.2) becomes meaningless. However, in such case the solution of (2.1) develops steep gradients, and the classical collocation approach (3.2) is far inadequate. To damp oscillations and weak instabilities which affect the numerical solution, some efficient smoothing and filtering procedures have been lately proposed in the spectral literature. The analysis of these methods is beyond the scope of this paper.
Methodfor Burgers' Equation
277
However, the interested reader can refer, e.g., to [18] and the references therein. We introduce now two projection operators: the orthogonal projection operator in Hw (4.7)
PN: Hw--* PN, (v-PN v, @)w = 0
for all ~ 9
and that in Vw (4.8)
H.,-q : Vw --~P~ , aw (v-HN v, q~) = 0
for all q~ 9 P~.
The following estimates hold (see [3], [13]) (4.9)
Hv-PNv [[.,w ~< C II v Ilo,w N3u/2-~ a~O, O~tz~
(4.10)
It v --/TN v tl~,w ~< C tt v Ilo,w N~'-", o>11, 0~<#~<1.
For any function v 9 Vw we will make use for convenience of the following notation (4.11)
(E(v), e)w = (v,~)N -- (v, q~)w
for all q~ 9 PN.
It is readily seen using (3.4) and the Cauchy-Schwarz inequality that (4.12)
I (E (v), ~0)w ] ~< C ( I v--PN-i v Iw + I v-IN v Iw ) I q~ Iw
for q~ 9 PN
by which, using (3.1) and (4.9) we get: (4.13)
I (E(v), ~)w [ ~ CN-~ Nv II,~,w I q~ Iv,, or>
1
, for any ~ 9 PN
2 Finally, for any k~>0, and any function v: (0, T)---~R, we introduce the quantity ek(v) = vk+l--Vk -- Vk+l 9 Ifvtt 9 L 1 (0, T), the Taylor formula yields: At (4.14)
l ek (v) I = [ ~ t
( t k - s) vtt (s)ds I ~<
It
I vtt (s) I as.
We can now state the main theorem of this section. We will assume that ut, EL2 (0, T; Vw) and u0 9 t-I~, u 9 1 (0, T; t-I~) for some s~>l.
N. BRESSAN - A. QUARTERONI: An Implicit~explicit Spectral
278
THEOREM 4.2. There exist a function K (u, ut, Utt) and a constant B such that, i f A t is small enough,
(4.15)
sup O~n~m
I un -- Un [w ~< ( A t + N - s ) K (u, ut, utt) exp (_BT 2~
).
Proof Let's set fi=//N u. Then fi satisfies: (4.16)
1 At
(fik+l
ilk, V) N + Yaw (a TM,V) = --
-I- (Ek (l~l), V)N -1- (O'l, V)w
1 ([~ (u k+l) uk+l]x, V)w 2
for V e P~N
where o, = ilk+, _ uk+l+ E (fikt+l). Setting e k = fik _ U k, and subtracting (4.1) from (4.16) yields: 1
(e TM - e k, v)y + Yaw (e TM, V) =
At
(4.17)
= (ek (a), V)N + (O~, v)w + (02, V)w
for v e P ~
where
a2 =
1 ( [IN (r (U k) uk)]x- [ V (u ~§
uk+~]x} =
2
1 {[IN (r (U k) Uk)]~ + 2
+ [a~ (u k+~) (u k- uk+l)], + [r (u TM) (a k - ub]x - [~ (u TM)ak]x}. We look now for a new expression for a2 which is more suitable for the analysis. Integrating by parts and using (3.4) leads to
([IN (a~ (Ub Uk)]x, %, = - (~ (U k) U k, v (W))N
Hereafter, we are using the notation: v(w) = (VW)x . We recall that v(w) e PN-I i f v EP~q. w M o r e o v e r we have:
Methodfor Burgers'Equation (-- [q~) (U k+l) l~lk]x, V)w • ((~) (U k§
279
"1~k, V (W)) w
= ([C~) (U k+l) -- ~ (uk)]l~l k "Jr- [r (uk) - r (12k)]l~lk "[- (:~ (1~1k) l~lk, V(W))w,
and by (4.11): (q~:} (l~ k) l~k, V (W)) w = (~) (1~k) 11k, V (W)) N -- (E(~P (ilk) ilk), v (w))w
Furthermore (r
(1jk)l~lk--~ (U k) U k, v (w)) N = ([4 (l~lk)--~ (uk)]12 k Jr"
+ cp (U k) (fik--uk), v (W))N -- (Do, V(W))N. We gather the previous identities which yield
1
(4.18)
5
(a2, v)w = -- {(O0, v (w)) N -[- ~Y' (Di, v(w))w} 2 i=l
where we have set: D1 = - O ( u k+l) (uk+l--uk), D2 = -q~ (u k+l) (uk--fik), D3 = [q~ (uk+l)--~(uk)]u k, D4 = [r162
(fik)]fik, D5 = - E (r (ilk) ilk).
Let us take v = e k+L into (4.17). By the Cauchy-Schwarz inequality, by (3.5) and (4.14) it follows:
] (ek (fi), ek+l)N [ ~ ,,1 ]] ek (fi)[[t~.F 1 II e ~§ I1~ 2
2
(4.19) tk+l
2~t f~ I a~ (~)I,~ +
1 II e~§ I1~
2
N. BRESSAN - A. QUARTmRONI:An Implicit~explicit Spectral
280
By (4.10) and (4.13) we now get: (4.20)
I (,,,, eke'),+ I ~ CN -2+ II uP+ ' IlL+ + y
1
II ek+l II~
Moreover, from (2.13), (2.14), (2.3) and (4.5) it follows:
[ (Do, e k+' (W))N I ~ (10 k I+ + I <~ (u k) I+)II ek IIN II eke' (w)IIN (4.21)
(ll u k II~ + 4M2) --II d2
4++
e k II~ + 2~ II eke3+ II~
By similar arguments we can show that: 4
62
li__~t(Di, ek+l (w))w I ~ - - (ll uk 112 + aM+) (1uk+l-uk 12 + I uk--fik[2+ ) 4e (4.22)
+ 4++I+ek+' lie To get a bound for the remaining term of (4.18) requires more attention. We note that, ifN is large enough, by (4.10) and (2.12) we deduce that ~ (ilk) = ilk. Then (4.12) gives:
I (Ds, e k+1 (W))w ] ~ C {1 (I--IN) (ilk)2 Iv, + + l (I-PN-,) (fik)2 l'++} l e T M (w)1,+ where we have denoted by I the identity operator. By (3.1) and (4.10) we get: t (I--IN) (~k)2 I,+ 4 1 (I--IN) (uk) 2 [w + [ (I-IN) [(uk)2-"(llk)2]t w
CN -s II (uk) +' lls,w +" CN-I II u~-,~ k llw II uk+~ '<:lie ~ CN-+ [I uk {[P,w.
Methodfor Burgers' Equation
281
Working similarly with the term [ (I-PN_I) (ilk)2 [w, and using (4.5) it can be shown that: (4.23)
62 [ (D5, e k+l (W))w I ~< CN-2S - - I I 4+
u k II,,+,.+ . + + II ek+' If2
Now we note that, by (2.9), there exists a constant 0 such that II uk 112 § 4M c for k=0, ..., m. Therefore, (4.18) and the inequalities (4.21), ..., (4.23) lead to: 62
12 (o.~, e~+')w I ~ 7+ II e k+' 112 § - o II e k II~ § 4+ 62 62 + -o (I u"+'-u ' 12 + lug-,:, ' I~) + - CN -2s II u" 11+,%. 4+ 4+ Using this inequality, together with (4.19) and (4.20), it follows from (4.17) that:
l (II e k+' II~-II ek II~) § A t ( ~ 2 At 2
(4At
It ktk§[1]tt (r)
7 +)II e ~+' II~
2
62 [2 dr + CN -2s ( 1 [[.k+t2 ., ,,w + - - I I 2 4+
4 u k II,,w/
(4.24)
+ m~"(l u"+'-u ' 12 + f u=-,a"lw>~ , + ^"-="(2 II ek+' II~ + ~06 II ek 1[~) 4+ 2 4+ By Taylor's formula and the Cauchy-Schwarz inequality we have: tk+l
[ uk+l_uk [2 ~ A t
ft,
I ut
(r) [2 dr
Moreover, [ uk-fik [~ can be bounded as in (4.10) taking/~=0 and a=s. Therefore, taking e ~
25t/
.
into (4.24), summing on k from 0 to n-1 (n~m),
7 and using Gronwall's lemma leads to:
N. BRESSAN- A. QUARTERONI: An Implicit~explicit Spectral
282
II e" IIN ~ exp (BT) {lie o It} + 4At2 II u. Ib(..> + -
2
(4.25) 2 max II uk Iltw + c [At2 II u, II,, + TN -2s ( o~k~.
+
omax ~ n II ukt ILL)]}
1)
We have set B = (16av+TCOm)/4a. We note that, by (3.5), (3.1) and (4.10),
Ile~
--< CN-' II uo IIs,w.
Moreover, we note that, by (4.10), I fittiw ~< C II u , IL for a.e. t ~ (0, T). Then, by (4.25) there exists a constant I~ which depends on u, ut and utt such that: (4.26)
IlenliN ~< C exp (B__T_T){N_s II uolls,w + I~ (At+N-S)}. 2v
Now the desired result (4.15) follows from (4.25) and the triangle inequality:
I u "-v~ I~ -< CN -~ II u ~ II~,w + I en Iw, taking K = C (I~+ [I Uo II,,w + II u n Ikw) 9 THEOREM 4.3. In the same hypothesis of theorem 4.2, the solution of problem (4.1) converges
asymptotically to that of problem (2.15) in the maximum norm, i.e.
(4.27)
lira I un-Unl= = 0
0~n~
N---*
provided
(4.28)
/X t-V~--~0
as
N--*~.
Proof. For any v ~ PN we have:
(4.29)
I u"-U" 1~ ~< [ un-vl~ + I v-Un]=
0~
Noting that (v-U") e PN and using the inverse inequality (see [16])
Methodfor Burgers' Equation [ • [= ~< (2N) l/p [[ q~ [[p,w
283
for all q0 9 PN
we deduce (4.30)
[ v - U n lo~ ~< (2N) 1/2 (I v-U"]w + I un-Unlw)
Take V=HNU n into (4.29), use (4.30), (2.3) and the estimates (4.10) and (4.15) to obtain:
] un-Un[oo ~ C (N l/2-s [[ u n ][s,w -~- N [ ( A t + N -s) K exp (BT) + N_s Hu"[kw]} 2v Then (4.27) follows provided (4.28) is fulfilled. 9
Remark 4.2. The stability conditions (4.28) depends on the proof technique. If we had used a scheme of the second order in time (e.g. the Crank-Nicolson/ Adams-Bashforth method) the Outcoming condition would have been /kt 2= 0(1/V'-N). In any case these conditions are not restrictive, as in applications 9 smaller time-steps are currently used to balance the higher precision which is gotten in space. If the hypotheses of theorem 4.3 are fulfilled, then a consequence of (4.27) is that the solution to the auxiliary numerical problem is absolutely stable, namely (4.32)
[Un[= ~ 2M
0~
In fact, if for any N greater than a fixed No, ] un-U n ]= < M, then the triangle inequality and (2.4) give the result. Now (4.32) implies that
(U k)
=
Uk
for k=O, ..., m.
Then, the numerical problem and the auxiliary numerical problem do coincide. Therefore all the results we have proved so far for U k can be equally restated for yk.
Acknowledgments. The authors are indebted with professors D. Arnold and M. Crouzeix for many valuable discussions concerning the content of this paper.
284
N. BRESSAN- A. QUARTERONI;An Implicit~explicit Spectral REFERENCES
[1] N. BRESSAN,A. QUARTERONI,Analysis of Chebyshev collocation methodsfor parabolic equations, to appear on SIAM J. Numer. Anal. [2] C. CANUTO, A. QUARTERONI, Spectral and pseudo-spectral methods for parabolic problems with nonperiodic boundary conditions, Calcolo, 18, (1981), 197-218. [3] C. CANUTO, A. QUARTERONI,Approximation results for orthogonal polynomials in Sobolev spaces, Math. Comp., 38, (1982), 67-86. [4] M. DEVILLE, P. HALDENWANG,G. LABROSSE,Comparison of time integration (finite difference and spectral) for the nonlinear Burgers" equation, Notes on Numerical Fluid Mechanics, Vol. 5, Ed. H. Viviand, Vieweg Verlag, Braunschweig, 1982, 64-76. [5] D. FUNARO,Approssimazione Numerica di Problemi Parabolici e Iperbolici con Metodi Spettrali, Thesis, University of Pavia, 1981. [6] D. GOTTLIEB, The Stability of Pseudospectral Chebyshev Methods, Math. Comp. 36 (1981), 107-118. [7] D. GOTTLmB, S.A. ORSZAO,Numerical Analysis of Spectral Methods: Theory and Applications, CBMS Regional Conference Series in Applied Mathematics 26, SIAM, 1977. [8] P. GRISVARD, Equations diffFrentielles abstraites, Ann. Sci. Ecole Norm. Sup., 4 (1969), 311-395. [9] R.S. HXRSH, T.D. TAYLOR, M.N. NADWORNV, An Implicit Predictor-Corrector Method for Real Space Chebyshev Pseudospectral Integration of Parabolic Equations, Comput. Fluids, 11 (1983), 251-254. [10] D. KINDERLelJRER,G. STAMPACCmA,An Introduction to Variational Inequalities and their Applications, 1980. Academic Press, New York. [11] J.L. LIONS, Quelques mgthodes de Resolution de Probl~mes non Lingaires, 1979. Dunod, Paris. [12] J.L. LIONS,E. MAOENES,Nonhomogeneous Boundary Value Problems and Applications, Vol. I, 1972, Springer, Berlin and New York. [13] Y. MADAY, A. QUARTF.RONI,Legendre and Chebyshev Spectral Approximations of Burgers' equation, Numer. Math. 37 (1981), 321-332. [14] Y. MADAY, A. QUART~.RONI,Approximation of Burgers" equation by pseudo-spectral methods, R.A.I.R.O. Anal. Num. 16 (1982), 375-404. [15] C. BASDEVANT,M. DEVILLE,P. HALDENWANG,J.M. LAOROIX,P. ORLANDI,J. OUAZZANI,A.T. PATER.A,R. PEYRET, Spectral and finite difference solutions of the Burgers' equation, preprint. [16] A. QUART~.RONI,Some results of Bernstein andJackson typefor polynomial approximation in LP-spaces, Japan J. Applied Math. 1 (1984), 173-181. [17] J. SMOLLF.R,Shock Waves and Reaction Diffusion Equations, 1983, Springer-Verlag, New York. [18] R.G. VOIOT, D. GOTTLIEB and M.Y. HUSSAINI, Spectral Methods for Partial Differential Equations, 1984, SIAM, Philadelphia. [19] G.B. WmTHAM,Linear and Nonlinear Waves, 1974, J. Wiley, New York.