An Introduction to the Numerical Analysis of Spectral Methods

Lecture Notes in Physics Edited by H. Araki, Kyoto, J. Ehlers, MLinchen, K. Hepp, ZQrich R. Kippenhahn, ML~nchen,D. Ruelle, Bures-sur-Yvette H.A. WeidenmLiller, Heidelberg, J. Wess, Karlsruhe and J. Zittartz, K61n Managing Editor: W. Beiglb6ck

318 Bertrand Mercier

An Introduction to the Numerical Analysis of Spectral Methods

Springer-Verlag Berlin Heidelberg NewYork London Paris Tokyo

Author Bertrand Mercier Aerospatiale, Division Syst6mes Strat~giques et Spatiaux Etablissement des Mureaux Route de Verneuil, F - 7 8 1 3 0 Les Mureaux, France

ISBN 3 - 5 4 0 - 5 1 1 0 6 - 7 Springer-Verlag Berlin Heidelberg N e w Y o r k ISBN 0 - 3 8 7 - 5 1 1 0 6 - 7 Springer-Verlag N e w Y o r k Berlin Heidelberg

This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in other ways, and storage in data banks. Duplication of this publication or parts thereof is only permitted under the provisions of the German Copyright Law of September 9, 1965, in its version of June 24, 1985, and a copyright fee must always be paid. Violations fall underthe prosecution act of the German Copyright Law. © Springer-Verlag Berlin Heidelberg 1989 Printed in Germany Printing: Druckhaus Beltz, Hemsbach/Bergstr. Binding: J. Sch~ffer GmbH & Co. KG., GrL~nstadt 2158/3140-543210 - Printed on acid-free paper

III

EDITORS' PREFACE

This is a translation of report CEA-N-2278, French

Atomic

Energy

M ~ t h o d e s Spectrales.

Commission,

titled

dated 1981, of the

Analyse

Num~mlq~e

des

The translation was prepared under the auspices

of the Institute for Computer Applications in Science and Engineering (ICASE). We hope that this book will serve as an elementary introduction to the m a t h e m a t i c a l

aspects of spectral methods.

The first part of the

monograph is a reasonably complete introduction to the theory of Fourier series while the second part lays some foundations for the theory of polynomial expansion methods, in particular Chebyshev expansions. No m o n o g r a p h of this size can hope to serve as a comprehensive reference to all aspects of spectral methods. The emphasis here is on proving rigorously some fundamental results related to one-dimensional advection and diffusion equations. No applications of the methods are presented subsequent

and no to

revisions

1981.

The

have b e e n made

reader

interested

to in

account recent

for

results

theory

and

applications of spectral methods might wish to consult the book by Canuto et al. [5].

May 1988

Nessan Mac Giolla Mhuiris Moharmaed Yousuff Hussaini

Iv

AUTHOR'S PREFACE

These notes were written while I was t e a c h i n g a course on Spectral Methods at the Universit~ Pierre et Marie Curie, Paris, at the request of Professors P.G. CIARLET and P.A. RAVIART, whom I would like to thank here. They were originally published in French in 1981

as a C.E.A. report.

Their p u b l i c a t i o n in English would certainly not have been possible without the encouragement of Dr. D. GOTTLIEB, Dr. M.Y. HUSSAINI and Dr. R. VOIGT, and the material support of ICASE. Special thanks are due to the Editors who have not only performed the translation, but also improved the original manuscript. The support of the French Commissariat & l'Energie Atomique and in p a r t i c u l a r of Professor R. DAUTRAY,

Scientific Director,

acknowledged.

February 1985

B.MERCIER

(C.E.A.), is also

CONTENTS

INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

A. FOURIER SPECTRAL M E T H O D

i. R e v i e w

of H i l b e r t

2. S i m p l e

Examples

3. F o u r i e r

Series

Bases ............................................

of H i l b e r t in ~

(-K,K) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4. T h e U n i f o r m

Convergence

5. T h e F o u r i e r

Series

6. P e r i o d i c

Sobolev

7. F i r s t - O r d e r 8. L a g r a n g e

10.

Time

of F o u r i e r

14

Series ..........................

19 21

Spaces ............................................

Equations

- The Galerkin

Equation

Discretization

Method ........................

in S N - T h e D i s c r e t e - The C o l l o c a t i o n

Fourier

Transform

......

Method ......................

Schemes ........................................

ii. A n A d v e c t i o n

- Diffusion

12.

of an E l l i p t i c

The Solution

7 9

of a D i s t r i b u t i o n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Interpolation

9. F i r s t - O r d e r

Bases ...................................

Equation .................................. Problem ................................

26 32 43 56 62 77 93

B. P O L Y N O M I A L SPECTRAL M E T H O D S

I. A R e v i e w

of O r t h o g o n a l

2. A n I n t r o d u c t i o n 3.

The A p p r o x i m a t i o n

2.

Approximation

5. The S o l u t i o n

Polynomials .................................

to C e r t a i n

Integration

of a F u n c t i o n

by the

by Chebyshev

Interpolation

of t h e A d v e c t i o n

Formulae

....................

P o l y n o m i a l s ...........

Operator ........................

Equation .............................

97 100 106 122 126

6. T i m e D i s c r e t i z a t i o n

Schemes ........................................

137

7. T h e U s e of t h e F a s t

Fourier

Transform ..............................

141

of the H e a t E q u a t i o n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

145

8.

Solutions

REFERENCES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

153

INTRODUCTION

"Spectral

methods"

is

the

name

given

solution of partial differential equations.

to a numerical

approach

to

the

In this approach the solution to

the equation is approximated by a truncated series of special functions which are the eigenfunctions of some differential operator. Part A of this monograph is devoted to Fourier series, sine series, and cosine

series.

Sections i to 4 are a review of some standard properties of

Fourier series approximation.

Section 5 is devoted to periodic distributions

and their development in Fourier series. derivative

in

the

periodic

definition

of periodic

distribution

Sobolev spaces in

properties of the truncation operator

In particular, we define there the sense

and

this

section 6 where

is

used

in

the

the approximation

PN are reviewed.

An application of these results is given in section 7 where a Galerkin ("spectral") approximation of the equation

~u "~+

8u 8 (au) = O, a ~-~+ ~ x

with periodic boundary conditions, is considered. The error analysis for this approximation will be based on L 2 estimates obtained using the skew symmetry of the operator

L

defined by

~u Lu = a ~ x + ~ x (au).

The

coefficient

a(x)

is assumed

to be smooth,

and we show that the

accuracy depends only on the smoothness of the initial data

u 0.

If

u0

is

in

C~, then the error will decrease faster than

property is known as "spectral accuracy"). continuous,

then

it

is well

Fourier method leads there

is

still

known

convergence

with

for any

On the contrary, if

(see Gottlieb

to some undamped

weak

N -s

and

oscillations. spectral

Orszag

s > 0 (this u0

[8])

is disthat

the

However, we show that

accuracy.

In

particular,

integral quantities are much more accurately captured than pointwise values. This result shows why smoothin ~ is quite useful in the case of discontinuous data. Section If

u

8 is devoted

is continuous, PC u

with

u

at

the interpolation operator

PC"

is the truncated Fourier series which coincides show that operator

PC

enjoys some useful approximation properties in periodic Sobolev spaces.

We

also show that

some

to the study of

equally-spaced

PC u

points

e.. 3

We

can be evaluated easily from the

u(Sj)

by means of the

Fast Fourier Transform. Turning back to the equation

~u ~+Lu ~t

we

carry

out,

in

section

9,

an

error

= 0

analysis

for

the

collocation

(or

"pseudospectral") approximation method discussed in section 8. We

review some

facts about

time discretization in section

show that explicit schemes can be used with a time step

At

I0 where we

of order

I/N.

In section ii we consider the case where a diffusion term is added to the operator

L, i.e., ~u --+ ~t

where the operator

A

Au + Lu = 0

is a second-order operator.

Finally,

section

12 gives a brief analysis

of the Fourier approximation

of the stationary (elliptic) problem

Au=

f

again with periodic boundary conditions.

In Part tions.

B, we

The main

try to relax the restriction

tool

in this latter half

of periodic boundary condi-

of the monograph is to work with

polynomials of degree less than or equal to N. In section

I, we

review the main

properties

of families

which are orthogonal with respect to the scalar product

of polynomials

(.,-)~

defined by

(U,V)m = f U(X) v(--'(~m(x)dx I where

~

is

interval

a

given

weight

function

I

is

usually

defined

as

the

(-I,+I).

The special case where polynomials.

~(x) = (i - x2) - I~

Using the transformation

and the Chehyshev series in

x

we

Transform.

can

then

corresponds to the Chebyshev

x = cos 8, we can map

I

onto

then corresponds to a cosine series in

Choosing as interpolation points spaced,

and

xj = cos 8. 3

compute the interpolant

of

where the u

with

8. 3

(0,~) 8.

are equally

the Fast

Fourier

This is why we put such emphasis on the "Chehyshev weight"

m(x) = (1 - x2) - l & . Section Radau,

and

2 discusses Gauss-Lobatto

the numerical types.

In

integration section

3 we

formulae study

of Gauss, the

Gauss-

approximation

properties

of the orthogonal

where the norm is

Sobolev spaces

projection

{{uI}~ ~ (u,u)~/2 .

Hm(I)

operator

PN

in the space

To this end, we introduce the weighted

c o n t a i n i n g the f u n c t i o n s which a l o n g w i t h t h e i r

t i v e s up to the order

m

are in

L2(I)

deriva-

L2(1).

We will show that

-m

{Iu - PN U{IL2(I ) < C N

{{UIIHm(I)'

which is quite similar to what was proved for Fourier series in Part A. Following Canuto and Quarteroni IIu - P N Part

A.

operator

ull Hm(i) The

which same

show a loss

kind

of

[4] we derive estimates for of accuracy

analysis

is

compared

performed

for

to the results the

in

interpolation

PC in section 6.

These results are applied in section 5 to the equation

xc

~u + a(x) ~u

2-7

Tfx --°'

with homogeneous boundary conditions at Let

(x.)3I<j
denote a set of

the approximate solution

uN

a

is everywhere

t >0

x = ±i. N

points in the interval I; we define

to be a polynomial of degree

Du N Du N (~-- + a 3--~--)(xj) = 0,

When

I,

positive at least

shown to lead to a stable method.

< N

such that

I ~ j < N.

two sets of collocation points are

The first set (Gottlieb's

X.

=

J

--

method)

COS

is

J~ N +------~ '

j = I,..-,N

The second set is X.

=

--

COS

j~ ~-V--rTT~ I_ , J.,~ . T

We will carry out an error analysis Explicit condition

time

discretization

j = I, "',N.

/2

for both methods. is considered

in section

6.

The

stability

is shown to be At < C N -2 .

In

section

7 we

computations.

show This

but it is possible Finally, coefficients.

how

to use

is not

following

section

8

is

the

obvious

Fast

for

the first

the argument devoted

Fourier

to

Transform set

in Gottlieb the

heat

to speed

of collocation

up the points,

[8]. equation

with

variable

PART A

THE FOURIER SPECTRAL METHOD

I.

R e v i e w of Hilbert Bases

Let

H

be a Hilbert space with an inner product denoted by

associated norm

(.,.).

The

II.II is defined by

11v11 = (v,v) 1/2

Recall

that a family

{W. g H} where 3 jcl'

I

is a set (denumerable or nonde-

numerable) of indices, is said to be orthonormal if

(W.,Wk) = 6 3

Suppose

u g H

d~f jk

is given.

1

if

0

otherwise

We can define, for

j = k

j c I,

^

uj = (u,Wj)

Let

J l " ' " 'Jn g I

be

n

given indices and

n

Un

It is easily verified that spanned by

{Wjk}, 1 < k ~ n.

un

=

^

I u. W.

k= 1 3k 3 k

is the projection of

u

on the subspace

Mn

8

Consequently,

u - un

is

orthogonal

to

Mn,

and

thus by Pythagorases

theorem n

"U"2 : ,.U '12 + .,U_U "2 : n n

We have for all

{jl,...,jn },

~ lU^ 12 + 'lu=u "2 ~k i n " k=1

the inequality

n

X lu 12<

k=l

IIuU2

Jk

and it follows that

(1.z)

^12 IUj

< I,U,,2 .

(Bessel's Inequality)

jgl

In

particular,

efficients

uj

for

can

a given

be

u g H,

non-zero.

only

Let

a denumerable

{Jk}kc ~

coefficients; it can be shown that the sequence

be

the

{Un}n=l,

subset

of

co-

indices

of

the

where

^

11 = ]~ U. W. n kEN ]k Jk

is Cauchy in

H

(since flu - u 112 = n m

lUjkI2 + 0

as

m + ~

with

n > m,

m
from (i.I)) and thus convergent. Let tion

M

u" = lim u n. The element u" obviously belongs to the complen+~ of the subspace spanned by (Wj)je I. As u-u" is orthogonal to M,

it is deduced that We

say

then

u~ that

is the orthogonal projection of the

family

(Wj)je I

M = H; in other words if u =

lie un n->~

is

u

a Hilbert

on

M.

basis

of

H

if

or equivalently, if

II u II

The Hi lbert space

H

2 =

luj^ 12.

(the Parseval Equation)

is said to be separable if it admits a denumerable

Hilbert basis.

2.

Simple Examples of Hilbert Bases In what follows the Hilbert space may be real or complex. We

itself.

denote

by

B(H)

the set

iff

M s ~

(T ~ B(H)

We recall the adjoint

T*

of

T

of all bounded such that

linear

operators

;ITvll < MHvlr, for all

of H

to

v s H).

is defined by

(Tu,v) = (u,T v),

and that if

T = T*, the operator

T

is said to be Hermitian (the term self-

ad~oint is, in principle, reserved for unbounded operators). We recall the following fundamental theorem of spectral theory (see, e.g.

Kato [10]).

10

Theorem 2.1: Hermitian

Let

operator.

H Then

be a separable Hilbert there

exists

space and

a sequence

(kn)neIN

T and

a compact (Wn)ne IN

such that

(i)

(ii) (iii)

Example functions

f

I.

x

~

n

~,

the family TW

n

(Wn)neiN ' forms a I ~ l b e r t

= X W for all n n - -

Let

I = ]0,~[

basis in

H,

n ~ IN.

and

H = L2(1), the

defined almost everywhere on

space

of

measurable

I, with complex values such that

If(8)l 2d0 < ~. I

The space

H

is a Hilbert space for the inner product

(f'g) = 71 f

f(e)g(e)d0 o

where

the

defined for

bar

denotes

complex

f ~ L2(1)

by

Let

conjugation.

Tf = u, where

u

T:

L2(1) ÷ L2(1)

is the solution of Dirichlet

problem. -u" = f u(0)

= u(~)

be

-- 0.

*That is to say, T transforms bounded sets into relatively compact sets.

11

Following the Lax-Milgram lemma we state that

(2.1)

for

llTfll1 < Cllfll,

some

HI(1).

constant

C

where

II.II1

As the injection of Hi(l)

follows that

T

denotes

in

L2(1)

the norm

of

is compact,

the

Sobolev

(see e.g.,

space

[II]), it

is compact.

The eigenfunctions

of

T

satisfy

-(%nWn )'' = W n

Wn(0 ) = Wn(~) = 0, and we have

n

2

and

Wn(X) = /2

sin nx,

for

n > i.

n

From Theorem

2.1, we then infer

that all functions

written in the form

^

(2.2)

with

u(e) =

Wn(X) = / ~

sin nx

~ Un Wn(8) , n> i

and

^

u n

= (u

'Wn)

= ¢~ f u(e) sin nO dO. ~-- 0

u ~ L2(0,~)

may be

12

We now consider

Exampl e 2. for

f ~ L2(I)

by

Tf = u, where

the case where u

the operator

T

is defined

is the solution of the following Neumann

problem. -u" + u = f

u'(0)

Here again,

u'(~)

=

=

o.

the Lax-Milgram lemma establishs inequality

ly establishs

the compactness

The eigenfunctions

of the operator

of the operator

T

(2.1), and consequent-

T.

satisfy

-(k W )" + k W = W , n n n n n

w~(o) = w~(~) = o.

It follows that 1

%n

2

for

n > O,

i + n

W0(x) = i

W (x) = # ~ cos nx n

for

n > I.

From Theorem 2.1, we then deduce that all functions written in the form

^

(2.3)

u(O) =

~ UnWn(O), n~O

u g L2(O,~)

may be

13

where

W0(e)

= 1

and ^ I U0 = ~

f

u(O)dO,

0

while Wn(O)

= / 2 cos nO,

for

u(O) cos n0 dO,

0

n > i. Remark

function If

2.1:

u we

truncate to

approximation may

of

not

boundaries.

We

these

the u

converge

The second

sum of functions derivative

Relations

in a sine series

approximations

which

f

v~ ,g

Un

whose

a

see

that

results.

at

u.

series

uniformly

are

termed

the

expansion

order

The of

to

N,

first

functions u, if

we

(the

obtain sine

vanishing

u

two

series) at

of a

first derivative

does not also

uniformly,

expansions

in

vanishes

terms

of Fourier

expansions)

u" series

gives

vanish of

at the boundaries,

to the derivative

different an

the boundaries

(the cosine series) gives an approximation

prised of both of the two preceding satisfactory

(2.3)

or in a cosine series respectively.

function by

and

expansions

may not converge

will

(2.2)

of

at the u

by a

and whose

u.

(which are

com-

will give us, in general,

more

14

3.

Fourier Series in We

consider

L2(-~,w)

now

the

complex

llilbert

L2(-~,~)

space

with

a

scalar

p r o d u c t d e f i n e d by 1

(f,g) = ~

We consider also the set

f f(e)g(e)de.

(Wn)ne~

W (e) n

Theorem 3.1:

Proof:

The set

Any function

an odd function

uo

(Wn)ne ~

of trigonometric functions defined by

=

e

ine •

is a Hilbert basis.

u e L2(-~,~)

is a sum of an even function

ue

defined by:

u (x) = I~ [u(x) + u(-x)] e

Uo(X) = i/2 [u(x) - u(-x)]

From the preceding sections, it follows that for

(3.1)

Uo(X) =

(3.2)

Ue(X) = b 0 +

where

x ~ ]0,~[,

[ a sin nx n>l n

~ b cos nx n 1 n

we can expand

and

15

II

2 f Uo(O)sin nO dO, an=~- 0

(3.3)

2

(3.4)

w

=~ f0Ue(0)cos

bn

nO dO

for n a 1,

and II

b 0 = ~I f0Ue(0)d0.

For odd or even

functions,

are still valid for

it can be seen that the relations

(3.1) and (3.2)

x e ]-~,~[.

As cos nx = I/2 (einX+ e -inx) and as I (einX -inx), sin nx =-~- e

it can be shown that

b

u(x) = Uo(X) + Ue(X) = b 0 +

~ [?(einX+ n>l

i.e., u(x) =

~ n~

u

e inx n

where u 0 = b0

and ^

Un

(b n _ Jan)

a

e -inx) - i ~ ( e inx- e-inx)];

16

^

U_n = 1/2 (bn + ian)

for

n > I.

Finally, note that

I an = ~ f

l Uo(8)sin ne d0 = ~ f

u(8)sin n8 de,

bn = [I f

Ue(8)cos n8 dO = T1 f

u(8)cos ne de,

consequently, ^

i

Un = ~

As

(Wn)ne~

f

u(e)e -in0 d0 = (U,Wn).

is a complete orthonormal

set, it is a Hilbert basis. Q.E.D.

Corollary the functions PN : H + S N

3.1:

Le___!t SN

(einx),

In[ ~ N

be the subspace

of

(and of dimension

H d~f L2(_~,~)

spanned by

2N+I); then the operator

defined by

(PNU)(X) =

In

~

u e
inx

for --

'

u e H,

^

where SN

u

n

is defined

by

(3.5),

coincides

with

the orthogonal

and satisfies: llu - PNU11 ÷ 0

as

N + ~.

projection

on

17

Remark 3.1: (i)

For a given

approximation The unless

u

in

function u

is

(2)

there

However,

uN

being

that is

the

function

u N = PN u

constitutes

an

L2(-~,~). periodic,

periodic and of period

Recall

everywhere; u.

of

u e L2(-z,~),

L2 no

not

converge

uniformly

to

u

2~.

convergence

reason

this difficult

may

for

does

PN u

to

not

imply

converge

result is true (see

convergence

almost

almost

everywhere

to

[6]).

^

The cients

coefficients

of the function

Remark

3.2:

u

n

defined

by

(3.5)

are

called

the

Fourier

coeffi-

u.

The relationship

between

the Fourier

u

function with period

series and the Fourier

transform: (I)

Suppose

is a periodic

u(x)

if

0

otherwise

2~; we set

x s I E (__~,~)

f(x) =

then the Fourier

transform

f(w) dsf

1 ¢~-~ m

f

of

f

satisfies

e -iwx f(x)dx =

I

f e -iwx u(x)dx.

2ti71

Therefore f(k) = ~

In other words, terval

(-~,~))

the Fourier

takes the values

u k.

transform of u (vanishing outside ^ uk ~ at the points k e Zg.

the in-

18

(2) at

the

The Fourier transform of points

multiplied by

k ~ ~

are

u

is a sum of distributions whose weights

precisely

the

Fourier

coefficients

of

u

/~.

In effect, if

f(w)

= 2¢~7~ i f~

f(x)e -iwx dx,

then I

f(x) =

fir

f(w)eiWX dw.

tie

Introducing the Dirac measure

6 w0 '

^ f = 6

==>

w0

1 iWoX f(x) ....... e ; 2¢~E

therefore,

u(x) =

^ inx un e

~

^

==>

u(w) = 2¢~E

prove

the

u n ~n(W) •

ne

nc Remark 3.3:

X

We have used a theorem in spectral theory (Theorem 2.1) to

completeness

of the Fourier basis

reader

should be warned

ness.

We have

chosen

method

involves

quite

(e inx)

ne

in

L2(-~,~).

The

that this is not the usual way of proving completeto do it this way

lengthy

proofs,

methods" given by Gottlieb and Orszag

and [9].

for b)

two reasons: to justify

a) the standard the name

"spectral

19

4.

The Uniform Convergence of the Fourier Series Let us observe

in the first

place that if

then the Fourier coefficients of in

u

I = [-~,7]

and

u e L2(1),

are always less than the average of

lu[

I

(4.1)

lUnl < M(u) def 27 1

f

]u(x) ldx.

--7

Moreover, ferentiable,

if

u

is continuous and periodic,

then, setting

v = u"

with period

2~, and dif-

we have ^ V n

n

in '

(in effect, on integration by parts, we have

^ i Un = ~

f

7

e -inx +7

More generally,

if

u

is

a

1

m~ n x

7

_i--~----]_7- ~ f

u(x)e-inXdx = ~ I [u(x)

u'(x) e_in

times differentiable,

and periodic derivatives up to order

dx).

and has continuous

s-l, we have ^

^

(4.2)

V

U

n

where

v

n

are

the

Fourier

n

-

(in)~ '

coefficients

of

(4.1)) we have

(4.3)

^

lUnl

M(u(a))

fn)

v =

u,~, ./~

In particular

(see

20

Thus,

the

more

regular

a function

cients tend to zero as

Proposition

is,

the more

rapidly its Fourier

In[ + ~.

4.1: I f

u

is

twice

continuously

differentiable

first derivative is continuous and periodic with period series

u N = PN u

Proof:

conver~_es uniformly to

and

its

2z, then its Fourier

u.

According to (4.3) we have

^

lUnl <

where

coeffi-

M2 -in12 '

for

n # 0,

M 2 = M(u"). The series of moduli

(the absolute series)

fUn einXl neTz

is less, (independently of

x) than the convergent series of positive numbers

^

M 2

Uo+ l-~" n*0 n

This proves that the Fourier series of to a continuous function is bounded.

Therefore

W.

W = u

u

converges absolutely and uniformly

Thus converges also in

L2(I)

to

W

since

from Corollary 3.1. Q.E.D.

I

21

5.

The F o u r i e r

Suppose

Series

of a Distribution

I = [-~,~].

Let us define

C~(1) P

tions which are along with all their derivatives, period

to be the space of func-

continuous and periodic with

2~.

From

(4.3),

which decrease

we see that functions

rapidly;

positive constant

C

if

in

C~(I)

have Fourier

~ s C~(I), then, for all

~ > 0,

coefficients

there exists a

such that

C (5.1)

-[~nI ~ [nl ~

In other words, if

(5.2)

~ e C=(1) P

for all

then

>

^I+nl

lira

0,

Inl s ÷ 0 ,

In I+=o

(apply (5.1) with Let

us

~ = B+I).

call

D'(I) P

the

dual

periodic distributions with period We

will

denote

by

<..>

space

of

and

the duality

(.,-) If

the

between

C~(I)

and

_

space

D'(I); P

~ s C~(1), we have



where

is

is the scalar product of

f s D'(1), p

of

2~.

'

f g L2(I)

C~(I). This P

= (f,~),

L2(I)

defined previously.

we will define the Fourier coefficients

fn =

(f) by: n ne2z

if

22

where

Wn(X) = e inx, (note that We have for

Wn ~ Cp(1)).

@ g C~(1) P ^

~-

= = [ #n ' ne ZZ ne ZZ

which implies that ^ -~-

= ~ fn@n • n

Therefore,

the

series

should converge for all holds for functions in

on

the

right-hand

~ e C~(1). P

side

(of

the

last

equation)

As the condition of rapid decrease (5.2)

C~(1) p ' we see that

f e D~(1)

iff the sequence of its

Fourier coefficients increases slowly, that is:

(5.3)

f e D'(1) P

iff there exists

k > 0

The reciprocal is also true, (cf. Schwartz,

such that lim n = O. Inl÷~ (l+n2) k

[16], p. 225) and results from the

fact that any periodic distribution can be represented as a finite sum of the derivatives of continuous functions. We can now define the derivative in the periodic distribution sense by:

def (_i)= , for all

(5.4)

The

derivative

of

order

of

f

% e Cp(1).

is then by definition

distribution g = f(~) e D ' ( 1 ) . P

a periodic

23

We show that

^

(5.5)

gn = (in)a fn"

This results from (4.2) if we write

u = @

and

v = @(~), for then

-A-

= (-i)~ ~

fn Vn

nc~

= (-i)= ~ fn(in) ~ ~n ng2Z ^

=

Z

(in)~ fn #n '

ng 7Z

which yields the result. Remark function troduce

f

The

with ~ The

derivative

(concentrated

modulo

derivative

in

derivative in the sense of We will

in

the

periodic

which is regular but nonperiodic

a Dirac mass

coincides point.

5.1:

now study

mass)

distribution

sense

(i.e., f(~) ~ f(-~))

at the point

~

(or at

of

will in-~

which

2~)

as it will for a function discontinuous

the

sense

D'(I)

of

D'(I) P

does

(for which relation

the convergence

in

D'(I) P

not

coincide

a

with

at a the

(4.2) is false).

of the Fourier

series

for

f:

Z

nEZZ

(where

nWn •

Wn(X) = einx).

First, we are interested in the case where 5.

f

is the Dirac distribution

24

P r o p o s i t i o n 5.1:

Proof:

The Fourier series for

6 converges

By definition of Dirac distribution,

<6,~> = ~(0),

for all

in

D'(1). P

we have

~ e C~(1) P

^

therefore

6

= i, for all

n e ~.

n

We get 6N = inI< N Wn'

(6 N

is the Fourier series for

that

6N + ~

in

D'(I) P

Suppose

~ ~ Cp(I).

Now,

know

we

truncated to order

(see

~ truncated

when

to the

N).

order

We will

N + =.

We have

Proposition

4.1)

that

N) converges uniformly to

lira

PN~

(Fourier

series

~, therefore:

n

and the result follows.

to

f

in

D'(I).

The

for

<6 ,~> = ~(0) = <6,~>

N+~

Theorem 5.1:

show

Q.E.D.

Fourier

series

of distribution

f e D'(I) P

conver~es

2S

Proof:

For the periodic

functions

f

and

g

with period

2~, we may

define the convolution by:

1

(5.6)

f'g(0) = ~

This possesses

the usual properties

Therefore,

if

# ~ CI(I) P

i = ~ - f

and

f f(0-w)g(w)dw. I

of convolution in h = f'g, we have

h(e')~(0")d8"

-

I

Suppose, we set

f f f(O'-w)g(w)~(6")de'dw. I I

0 = 8" - w, then

-

When

i (2~) 2

f,g s D~(I)

are

1 2 f f(0)g(w)~--(eT~d0dw. (2~) I×I

some

distributions,

we

may

then

generalize

the

con-

volution product by setting:

= ,

where and

<-,->

in the right-hand

side

denotes

the duality

between

(D~(1)) 2

(C~(1)) 2 . Since

distribution

f*~ = f, we have by continuity (see e.g., TrSves

of the convolution

[18], p. 294)

f = f*6 = lim f*~N N+~

in the sense of

26

following

Proposition

2.

Now

nl Wnn

*Wn

and (f*Wn)(e)

according

= ,

to (5.6), where

Wn,8(w ) dsf Wn(e-w)

= e in0 e -inw.

Finally in@ (f*Wn)(@)

= e

^ = fn Wn(8)'

and so ^

f = lim ~ N+~ I n ~ N

f W . n n Q.E .D.

6.

Perlodie Sobolev Spaces

Let

I

following

be

the

fashion;

for

interval

]-~,~[.

We

u s L2(1), we set

ilulir = ( I

(l+m2)rl~mi2) I~

me ^

where

u

are the Fourier coefficients m

We define the space

define

of

u.

the norm

ti.tl

in the

27

= {u:u(a) e L2(1),a=0, ...,r},

Hr(1) P

where

the

derivative

denoted

by

the

superscript

see section 5).

periodic distribution sense

is

(a)

The space

Hr(I) P

taken

in

the

is based on

the norm

Ir = ( ~

llluJ

~=0

Where the

Ca r

of

defined in section 3.

L2(I)

ca llu(e),l2) i/2 r

ll-Jl denotes the norm

are the usual binomial coefficients and

We note the following result on denseness.

Lemma 6.1:

The space

Proof:

u s Hr(1) p ' we know that

N + ~.

If

C~(1)

is dense in

u N = PN u ÷ u in

On the other hand, by the definition of

(6.1)

(PNU) (a) =

I (in) a In ~N

Hr(1).p

W

u

n

L2(1)

as

PN

= PN u(a) n

'

^

since the coefficients

of

u (~)

are

(in)eu

from (5.5).

Therefore

UN(e)

n

converges to Finally,

u (a)

in

L2(I).

r l lU-UNIll r + 0

as

N + ~, a n d the result follows, since

PN u e Cp(I). Q.E.D.

The

relation

(6.1)

shows

that

the

operator

derivative in the periodic distribution sense.

PN

commutes

with

the

28

We define then the space

Hr(1)

= {u e L2(1):

iluiI < +~} r

where

II.ll r

is the norm associated to the scalar product

^

(u,V)r =

Proposition the norm

6.1:

liE. Ill r

The space

with the norm

[ (i + m2) r Um Vm. me ZZ

Hr(1)

coincides with the space

H~(1)

and

II.II . r

Proof:

Suppose that

u ~ Hr(1); it can be deduced that

m 2~ I~m 12 < +~,

0~

e<

r,

mg~

Consequently

u (~) g L2(1)

for

0 < ~ ~ r.

The converse follows immediately. Finally, we verify that

II lulli2r =

~ C~r ~ m2e lUm 12 = [ (l+m2)r =0 me 2Z m~ Zg

lUm [2 = ;lUrli2 Q.E.D.

The values

definition

of

extended to

r .

Hr(1) is such that it is sensible for noninteger P The previous result permits the definition of Hr(I) to be P

r ~ • •

of

29

We are now in a position to give error estimates

in the periodic Sobolev

spaces.

Theorem 6.1:

Let

r,s c ~

with

0 < s < r;

then we have

s-r

Jlu - PNUlls ~ (I+N 2) 2

Proof:

for

;lUllr'

u s Hr(1).P

We have

ilU-PNUll2s = Oral>N

(1+m2) s-r+r lu J2m ~ (l+N2)s-rlmI> N (l+m2) r lUm 12

< ( I+N2 )s-r IIull 2 r"

Q.E.D.

Remark 6.1:

The preceding result shows that the more regular

better an approximation

PN u

have

of

an

error

improves as

Lena

r

estimate

is to

order

u.

0(N -r)

More precisely, in norm

if

L2(I)

u

is the

u s Hr(I), we P which

clearly

increases.

6.2:

(Sobolev Inequality).

lluli2 < Cilu;l0 11ufl (!) i' e

and in particular

HI(1) p

+

L~(1).

There exists a constant

for all

u ~ HI(1), p

C

such that

30

^

Proof: over

I.

Suppose

u e C~(1).

We know that

u0

is the average of

From the mean value theorem, there exists x 0 s I

^

U

such that

^

u 0 = U(Xo).

Let

v(x) = u(x) - uo; we have

i/2 iv(x)i2 = f x v(y)v'(y)dy < (fXlv(y)Imdy) i/2 (fx Iv'(y)I2dy) < 2~,Ivil ilv'li, x0 x0 x0

[u(x)] <

+ Jv(x) J < ]u0J + 2~I/2llulil~llu.iji~, ^

because

v" = u"

and

livH < liul[. Since

Ino[ < lluJl, we have

]u(x) l ~ Clluijl~ 2 HuJ;#/2.

The inequality is then proved for all Hi(I),- it also holds for p

Since

u s C~(1). P

C~(1)

is dense in

u e HI(1). P Q.E.D.

From Lemma 6.2 we immediately obtain an error estimate in

L~(I)

norm;

we have 1-r

ilu_P,uli2

4 C(I+N2)-r/Z(I+N 2) 2

= C(I+N 2) I/2-r

L~(1)

,

thus

IIU-PNUll

= 0(Nl/2-r),

L(1)

valid for this case

r > I, and uniform convergence for all u

is continuous.)

u e Hi(l). P

(Note that in

This result is stronger than that given in

31

Proposition 4.1. Remark 6.2: the

functions

If, instead of

SN

(e inx), -N+I ~ n < N, we

properties for the projection operator SN

is of dimension

we consider the space have

some

PN :L2 + SN"

analogous

SN

spanned by

approximation

(We note that the space

2N, and the space SN is of dimension 2N+I).

32

7.

First-Order

Let

L

Eqtmtlons

- The Galerkin

Method

be the first-order operator defined by

au a(au) Lu ~ a ~ x + 'ax

where

a e C~(1) P

is regular and periodic (real).

We observe first that

(Lu,v) = ~ -

L

is skew symmetric:

~ x + ~--x-----jvcx = ~

--~

for

u,v ~ D(L) d~f H~(1).

and

v

Hk(1) P

in

gx

+ au ~-~x)dX = -(u,Lv),

(Note that we have used the periodicity of a, u,

in the integration by parts.)

operator of

-~

We observe that

is a bounded

Hk-l(1). P

We consider then the following problem in the space u(t) ~ D(L)

L

L2(1).

Find

such that

~u

--+Lu=0 ~t

t > 0

(7.1) u(x,0) = u0(x)

where

u 0 e D(L)

is given.

We have the following existence result:

Theorem

7.1:

a unique solution independent of

u0

Let

s > i

and

u 0 ~ H~(1); then the problem (7.1) admits

u ~ C0(0,r;H~(1)). and

t

such that:

Moreover, there exists a constant

C

33

.u(.,t)ll

< Cllu01Ls,

for

t s [0,T],

S

where

T

is positive and given.

Proof:

The proof of this result is an elegant applieaton of the theory

of pseudo-differential

operators (see M. Taylor,

[17], pp. 62-65).

content ourselves with establishing the a priori estimate in solution assuming it exists. For that purpose we introduce the operator

A s : ~(I)

+ L2(1)

defined by

^ einx + ASu ~ [ [ Un ne ~ ns

u =

(l+n21S/2, u^

e inx • n

We note that

/lUlls -- /IAs Ullo;

on the other hand, if

and if

s

s = 2, we have

is a multiple of

2, we have

A s u = (I - d2 Is/2 - -

dx 2~

U,

Hpr

Let us of the

34

(In the general case where differential If

u

s

is real and positive,

operator of order

As

is a pseudo-

s.)

is a solution of (7.1) we have then, by setting

K = [AS,L] --- ASL - LA s

d 2 d 2 ~u ASu) + (hSu, A s ~u d'-~ llu(t)l]s = d'~ t]hSu(t)110 = (AS ~ ' ~-t)

= - (ASLu, ASu) - (ASu,ASLu)

= - (LESu, hSu) - (Ku, hSu) - (hSu ,LASu) ~ (hSu, Ku)

= - (Ku, ASu) - (ASu, Ku),

where we have utilized the antisymmetry of Since order

K

L.

is an operator (pseudo-differential

in the general case) of

s, it follows that

IIKull0 4 Cilulis '

d {tu(t)ll2 < 211Kuli0 ilASuU0 < 2Cilull2. dt s s

Therefore, llu(t)il2 4 e2Ctltu011 S

and the result follows.

S'

85

Let us verify in the case order

s

(and not of order

s = 2

that

K

is truely an operator

of

s+l); in this case

d2 Ku = (i - ~ ) ( L u )

- L(u-u")

dx ~

whence by setting

Lu = bu" + C

with

b = 2a

Ku = bu" + C - (bu'+C)" - b(u-u")"

= bu" + C - (b"u'+2b'u"+bu"')

and

C = a', we get,

- C(u-u")

- C" - b(u'-u"')

- C(u-u"),

and we see that the terms of third order disappear.

We carry out now a spatial looking

for an approximate

spanned by the functions The approximate Find

uN

semi-discretization

solution (einX)ini4N

UN(t ) E UN(.,t )

Q.E.D.

of the problem in the space

(1).

problem is therefore

the following.

such that

~u N (~--{--+ LUN;VN)

= 0,

for all

v N c SN,

(~N(0) - u0,vN) = 0,

for all

v N s S N.

(7.2)

(I)

See Corollary

3.1.

t~0

(7.1) by SN

36

Let

LN = PN L, where

PN : L2(1) ÷ SN

is the projection on

SN, we may

equivalently write (7.2) in the form

uN 8t + L N U N

=0

(7.3) UN(0) = PN u0"

Note that

LN

is also antisymmetric

(L N UN,V N) = (LUN,VN) = - (UN,LVN) = - (UN,L N v N)

for

UN, v N E S N.

In particular, with

(7.4)

uN = vN

Re(L N VN,VN) = 0.

Since

SN

differential operator

LN

is of finite dimension,

system with a solution

Theorem 7.2: If

u 0 e H~+I(1),

and CI

;iu(t) - UN(t)tl 0 < CI(I+N2)-s/2

~(t)

[in other words the

cO].

result in the following

(7.1) then there exists a constant

We set

(7.3) is in fact a

u N ~ C0(0,T;SN)

generates a semi-group of class

We establish the convergence

Proof:

the equation

= PNU(t)

u

is the solution of the equation

independent

llu011s+l,

and note that

of

u0

for

and

t

t s [0,T].

such that

$7

Du

Du

d

(8-t)n = (8-t- 'Wn) = ~

d

^

(U'Wn) = d-t Un

therefore 8u = ~-~ D PN u = ~-~ D IN • PN ~-~-

Consequently, (see (7.1))

Du N D--F-+ LNU = 0 therefore

au~ 8t + LN]N = LN(UN-U)"

Subtracting from (7.3) and setting

WN = UN - UN' we obtain

8W N 8t + LNWN = LN(U-~N)"

Taking the scalar product with

WN, we obtain

DW N (~--, W N) + (LNWN,W N) = (LN(U-UN) , WN)-

whence (taking the real part, and applying (7.4)):

Utilizing the identity

i/2~'~ d IlWN(t)II02 = llWN(t)it0 d

IIWN(t)IIO ,

38

we Obtain

(7.5)

d___dtliWN(t)ll0 < IILN(U-UN)II0 < IIL(U-~N)"0 < C211U-~NIII

where the constant

C2

is the constant of continuity for the mapping

L : Hi(l) + L2(1).

Since II(U-~N)(t)ti 1 < (l+N2)-s/21iu(t)lls+l < C(l+N2)-s/2ilu0iis+l ,

according to the Theorems 6.1 and 7.1, we deduce from (7.5)

llWN(t)ll0 < CC2(I+N2)-s/2t L1u011s+l; as

ll(U-UN)(t)ll0 < ll(U-UN)(t)ll0 + IIWN(t)II0;

we have obtained the desired result and an evaluation of the constant

C. Q.E.D.

Remark 7.1: (i) the norm

If

u 0 ~ •ps+l (I), we have therefore an error estimate of .

ll-iio, with a constant which increases linearly with

0(N -s)

t.

The method is thus of infinite order in the sense that the accuracy of the method is only limited by the regularity of the initial data (and the

in

39

coefficients). faster than

If this is in

N -s

for all

Cp(1), the error decreases to zero as

s > 0.

N +

This property is called "spectral

accuracy." This shows that the spectral methods will be superior to all the finite element or finite difference methods from the point of view of accuracy when one is dealing with regular solutions. (2)

We may replace the space

SN (of dimension 2N+I) by the space

SN

(of dimension 2N) introduced by Remark 6.2, with exactly the same results.

Remark 7.2: Let quantity N + =

¢

Estimate in the norm of Sobolev spaces of negative indices.

be a given function sufficiently regular; we will show that the

(¢, UN(t) - u(t))

even if

u(t)

converges "sufficiently rapidly" to zero as

is not regular.

For that purpose, we introduce the solution

aW * t~--+ L W = O,

w(o)

where

L* (= -L) Let

of the adjoint problem

t ~ 0

= ¢

is the adjoint of

WN(t) ~ S N

W

L.

be the solution of the approximate adjoint problem

aW N , (~--~--+ L WN,VN) = 0,

for all

v N ~ SN

(WN(O) - ¢,VN) = 0,

for all

v N e SN.

40

According

_s+l

to the Theorem 7.2, if

~ e lip

(I),

lIW(t) - WN(t)li 0 < C N-Sll~lls+I

for

t < T. Using the relation

(7.6)

(~,UN(t) - u(t)) = (WN(t) - W(t),u0) ,

(which we will establish shortly) we deduce the upper bound sought

(7.7)

(¢,UN(t) - u(t)) < C N-SH~Hs+itlu0fl 0.

Noting that

(¢,UN(t)-u(t)) llUN(t) - u(t)l;_o ~

sup

~ H~(~) we may interpret

li~ I;

o

(7.7) as an error estimate in the Sobolev space of negative

indices. In the extreme case where

u0

is discontinuous,

we observe then on

account of the Gibbs phenomenon an oscillation in the approximate the vicinity of the discontinuity,

solution in

but the oscillations annul themselves

"in

the mean," according to the relation (7.7) (since the second member of (7.7) converges

to zero as

~

is regular).

This explains intuitively the success of the Fourier method with smooth-

41

ing, consisting Osher,

[12]).

of smoothing

the initial

solution

By that we mean the following;

let

u 0 (see Majda-McDonoughp

be a positive

regular

function with a compact support such that:

/ p(x)dx = I.

We set

s(x)

x)

and us(t) = Os* u(t)

UsN = Pc* UN"

We know that

us(t) + u(t)

when

e + 0,

u (x) = / Os(X-y)u(y)dy

(where we have set

Oex(y ) d~f pe(x_y))"

J(u -u N)(x) j = I(pgx,UN-U)]

since by definition

= (U,Psx)

We have

~ CN-(S-l)llPexllsltUollo

as

ifOsxlls = ilpells.

We deduce that if constant

C(s,e)

p

such that

is very regular,

for all

e > O, there exists a

42

I(uc'uEN)(X)I < C(s,~)N -s

Therefore, there is uniform convergence of the regularized regularized

uN

to the

u, which has an "infinite rate of convergence."

Proof of (7.6):

We have by definition

(~, UN(t)-u(t)) = (WN(0),UN(t)) - (W(0),u(t)).

Now, t d (~NCS),UN(S))ds (WN(0),uN(t)) = (WN(t) , UN(0)) + f ~7 0 where have set WN(S) = WN(t-s ).

Noting that t f

d

W~(s) = -W~(t-s)

we have

t (~N(S),U(s))ds = f ((WN(t_s),u~<s)) _ (W~(t_s),uN(S))d s

0

0

t = f (WN(t-s),-LUN(S)) - (-L WN(t-s),uN(s)))ds

0 =0,

which yields (WN(0),UN(t)) = (WN(t),UN(0)).

It can be shown that

43

(W(0),u(t))

= (W(t),u(0)),

whence (~,UN(t)-u(t))

= (WN(t),UN(0))

- (W(t),u(0))

Q.E.D.

and result (7.6) follows.

8.

Lagrange I n t e r p o l a t i o n i n In practice,

interval

if

SN; The D i s c r e t e F o u r i e r Transform

u ~ C0(1) is a continuous P

I = [-~,~], it is not possible to calculate exactly the Fourier

coefficients

UN

of

u.

We therefore do not know in general of

u

in

SN (for the norm of

to determine a function coincides with

u

at

L2(I)).

v g SN, 2N+I

PN u

which is the best approximation

However, we will see that it is easy

called the interpolant

points

(xj)lj I < N

x. = jh, 3 (8.1)

periodic function on the

of

u, which

defined by

lJl 4 N

where 2~ h = 2N+I

In fact if we set v(x) =

we see that the

2N+I

coefficients

I akeikx' Ik ~N

ak

are solutions of the linear system

44

ikxj (8.2)

ikl! N e

ak = u(xj),

Now, up to a multiplicative

factor

lJl ~ N.

(2N+I), the

(2N+I) x (2N+I)

matrix

of this linear system is unitary (and hence invertlble). In effect (8.2) may be rewritten as

(8.3)

where

Ikl~ ~ N wJkak = u(xj)

W = e

ih

= e

2i~ 2N+I

is the principal

lJl < N

root of order (2N+I) of unity, and we

have the identity

1 2N+I

(8.4)

i! lJ

1

if

N

0

otherwise

which results from the following lemma (applied with

Lemma 8.1:

Suppose

I 2N+I

Proof:

Set

k =

wJkw-J~ = ~k£ =

~

1

[J (N

M = 2N+I

is a root of order

~J =

m = W k-~) •

2N+l

m=

of unity; then we have

i

if

1

0

otherwise

and

J

if

0~

j ~ N

J+M

if

-N ~ J < 0

j" =

Since m j+M = m j

we have

45

M-I

1

2N+I

~I

lJ
mJ

1

~0J"

= ~ j'=0 Z

This gives the desired result with the identity

(l-m)

valid for all

M-I Z 0~j" -= i-~oM, j'=0

m ~ (~. Q.E.D.

Corollary 8.1: inte~polant of

u

Let i__n_n S N

(ak) Ik I < N

be the Fourier coefficients

of the

defined b 7 (8.3), we have:

i i~ w-Jkz. me = 2N+i lJ < N J '

(8.5)

where the

(zj)ljl < N

are the values of

z. = u(x.) J ]

Definition 8.1:

u

a__~t xj

given by:

lJl ~ N.

We call discrete Fourier transform the mapping

(zj)lji< N + (ak)[kl~
Remark 8.1:

The advantage of the discrete Fourier transform is, that

thanks to the existence of the Fast Fourier Transform (see, for example, Auslander-Tolimieri, the

ak

from the

[i]), the computation of the zj

can be performed in

zj

O(N log N)

from the

ak

and of

operations and not

46

in 0 ( N 2) full

operations as one would expect when one calculates the product of a

(2N+I) x (2N+I)

matrix by a vector.

In what follows, the mapping which associates with each polant

v s SN, will be denoted by

sesquilinear form on

C~(I)

PC : C~(I) + SN.

Let

u

its inter-

('")N

be the

defined by

1

The operator

PC

satisfies

(PcU)(X.) j = u(xj)

lJl < N

and, in particular

(8.7)

for all

(u-PcU,VN) N = 0,

By the definition of

PN

for all

(U-PNU,VN) = 0,

so we see that in order to obtain product

(.,.)

v N s S N.

v N g SN,

PC, it suffices to replace the scalar

by the "discrete scalar product"

('")N"

The name "discrete scalar product" may be justified by noting that ('")N

(8.8)

and

(.,.)

coincide on

SN.

(UN,VN) N = (UN,VN) ,

for all

UN,V N s SN.

47

This results from the fact that the numerical integration formula

I

(8.9)

2-~f

f(x)dx = ~

I

~ f(xj), lJ
--~T

is exact for

f c S2N.

Indeed, from Lemma 8.1, we have

2N+I lJ 4N

ikx. e

2N+I lJ


wJk=

1

if k = 0 (mod 2N+I)

0

otherwise

and thus

ikx.

1

I

e

2N+I lJ 4N

J:~ 2~

f eikXdx' I

if Ikl < 2N.

The Relation Between the Fourier Coefficients of a Function and the Fourier Coefficients of its Interpolant.

Lemma 8.2: coefficients, and PC u

Let

u e C~(1)

(an)lni< N

with

(Uk)ke ~

as its Fourier

the Fourier coefficients of its interpolant

i__n_nSN; we have the relation

^

an = £12Z Un+£M where M dsf 2N+I.

48

Proof:

Let

(Wn)ne ~

be the basis of

W

J

n

%

tx~

= e

L2(1)

defined by

inx •

We have

I (Wk'Wn)N = 2N+I ljI(N Wk(Xj) 1 I ei(k-n)xj = 2N+I lJ ~N

I ~ wJ (k-n) = 2N+I lJ ~N Using Lemma 8.1, applied with

(8.io)

(Wk,Wn) N =

m = W k-n, we may deduce that

1

if

k = n (mod M)

0

otherwise

Since

(8.ii)

PcU = InI gN anWn'

we infer from (8.7) and (8.10) that

an = (Pc u'Wn)N = (U,Wn)N

^

: (kl

uk Wk'WN)N = Z ~

Zg

Un+~M" Q.E.D.

49

Remark 8.2:

With the preceding notation, we have

(8.12)

Uk = (U'Wk) = ~-~

(8.13)

ak

=

(U'Wk)N

=

/I u~k dx

i [ u(xj) ~ 2N+I ljl~N

,

which shows that if we use the numerical integration formula (8.9) to evaluate the integral defining a Fourier coefficient

^

^

Uk, we obtain (not

uk

that is to say the Fourier coefficient of the interpolant of

Estimation of

but)

a k,

u.

UU-PcULI0 .

We will establish the following theorem:

Theorem 8.1:

Let

r >I~

be fixed; then there exists a constant

that

(8.14)

i~u-PcUll0 < C N-riluFI

for all

u g H~(1).

r ~

Proof: PcPN = PN"

Noting first that

PC

leaves

SN

invariant, we have

We may thus write

(8.15)

u - PC u = u - PN u + Pc(PN - l)u.

Therefore, by setting

v = (I - PN)U

C

such

50

IlU-PcUll 0 4 IlU-PNUll 0 + IIPcVll 0-

Using Theorem 6.1, it suffices to show that

(8.16)

IIPcVll 0 < CN-rllull

For this purpose, we note that if the coefficients

of

r

.

ak

denote the Fourier

PC v, we have from Lemma 8.12

^

(8.17)

where the

ak =

vn

~ Vk+EM , £~ ZZ

are the Fourier coefficients

^

Vn =

of

v

and satisfy

0

if Inl ~ N

^ un

otherwise

Suppose Y(k) = {n ~

2Z :

n = k + £M

with

£ s ~/{0}},

we see that (8.17) may be rewritten

ak =

~ Sn = ~ (l+n2)-r/2 ngY(k) neY(k)

Using the Cauchy-Schwarz

(8.18)

lak I < (

Sn (l+n2)r/2

inequality, we have then that

~ (l+n2) -r) 1/2 ( I ( l+n2)r IVn 12) 1/2" nsY(k) n~Y(k)

51

Now,

(l+n2) -r ~ CN -2r.

(8.19) nsY(k)

In fact,

(l+n2)-r = N-2r neY(k)

[

N-2r

i

neY(k)

2 r N~ )

(~.~.+

[ £g~/{0}

1 r b£

where

1

[k+£M )2

b£ e ~ +

c---N--j.

Now, bE ~ £2 ,

(since

M = 2N+I

and

Ikl < N)

b r ~ £>0 We deduce (8.19) with

so the series

~ ~-2r ~>0

C = 2o(r).

def = a(r) < +~.

Returning to (8.18) we see that

lakl ~ CN-2r I (l+n2)rlSnI2 • nsY(k)

Thus

52

IIPcvIIg =

lakl2

I Ikl
< CN-2r

~

Ikl
~ (l*n2)rl~n]2 nEY(k) lSn 12(l+nm)r < CN-2r

I fUn I2(l+n2)r ne2Z

~

< CN-2rllull 2 , r

Q.E .D.

and (8.16) follows.

Remark 8.3: r >i 6 .

Thus

From the formula (8.18) we see that

PC

is defined when

u e Hpr(1)

for

lak]

is bounded since

r >I 6

This is

consistent because of the results of injection of the Sobolev space HE(l)

into

C~(1)

Remark 8.4:

when

r >I 6 .

We have defined the discrete Fourier transforms for only an

odd number (2N+I) of points.

We can define the discrete transform for an even

number of points constructing an interpolant in the space Remark 6.2) and which is of dimension

x. = jh, 3

2N.

SN

(introduced in

To do this we choose

-N + 1 < j < N

~=~. The analogue of (8.2) is then

N

ik~. e

k =-N+ 1

3a k = u(x.) J

whose matrix, multiplied by a factor

-N+

I~

2N, is unitary.

j < N ,

The analogue of Lemma

53

8.1 is easy to establish,

and is given as follows

1 ak = 2-~

(which is the analogue

~ W -kj zj , j =-N+I

of (8.5)) with

W = e

We have

N

2i~/2N

PC : C0(1) + SN'

zj = u(~j).

and

with

for all

(u-PcU,VN) N = 0,

v N E SN

(analogue

of (8.7))

N

(u,v)N = 2-~ 1

Finally,

~

j=-N+I

as the numerical

u(~j) v(~j) .

integration

formula

N

i i 2-~ f f(x)dx ~ 2N -~ j=-N+I

is exact for

f g S2N_I , we have the analogue

f(~j ,

of (8.8) (the proof is left to

the reader as an exercise). We can deduce an error estimate established

(8.20)

for

llu-PcUll0

similar to that

in Theorem 8.1, namely

llu-PCutl 0 < C(I+N2) -r/2 llullr.

54

Estimation of

llU-PcU~ls •

Proposition 8.1:

II vN Us

Proof:

l,VNl,2 =

For

a ~ s, we have the "inverse" inequality

(I+N2)(s-~)/211VNH

We have. for

for all

v N e S N.

vN e SN:

[ (l+m2)Slvm 12 < (I+N2) s-O ~ (l+m2)°IVm 62 = (l+N2)S-O,lVN,t2 ImI
,

and the result follows.

Corollary

C

8.2:

such that if

Suppose

s < r

then, there exists a constant

u e H~(I), we have

LIu-PCull

Proof:

is given,

s

< C(I+N2) (s-r)/2 ;lull . r

Recalling the identity

(8.15) we see that

llu-PC ull < ilu-PN ull + flPc vlt . s s s

We note that Theorem 6.1 takes care of the first term. second one.

We now turn to the

55

As

PC v s SN, we may apply the inverse inequality

Proposition

8.1 (with

a = 0).

liPC v]ls 4 (I+N2) s/2 rIPcvi]0,

and the required

result follows from (8.16).

established

in

56

9.

First-Order Equations - The Collocation Method (1) We shall now study a semi-diseretization more realistic than the Galerkin

method which can be applied in the case where the coefficient, a, entering the definition of the operator

L

~u Lu - a ~ + ~

(au),

is not constant. The approximate problem is then the following.

Find

Uc(t) e SN

such that

~-~ u C + LcU C = 0

for > 0

(9.1) uc(O) = PcUo .

where the operator

(9.2)

L C : SN + S N

is defined by

+ ~ x (Pc(a(x)u))

LcU E Pc(a ~ )

We now show that the operator (8.7) of

PC, and (8.8), we have for

LC

is antisymmetric. u,v c SN

(i) also called "pseudo-spectral" method.

Using definition

57

bu (LcU,V) = (a ~-~x,V)N + (a-xx (Pc (au))'v) = (integrating by parts)

(9.3)

_

= (~xu , av) N

= (~

'

av (au, ~x)N

Pc(aV))N

-

(u,Pc( a ~av)] x JN

Pc(aV) ) _ (u,Pc( a ~v

= -(u,Lcv).

Since

SN

differential

is of finite dimension the equation (9.1) yields a

system which admits a unique solution

u C s C0(0,T ; SN).

Remark 9.1: true for

L

and

If

a

is constant, L C

LN, we deduce that

and

L

uC = u N

coincide on

SN; as is also

and with it the equivalence of

the Galerkin and collocation methods for this case. We return to the general case of nonconstant

coefficient and establish

the following convergence result

Theorem

constant C

9.1:

Le____tt T > 1

such that if

and

u 0 g H;(1)

T > 0 and

@iven, then there exists a u

is the solution of the equation

(7.1), then I-T llu(t) -Uc(t)ll 0 < C(I+N 2) 2 llu011r,

for

0 ~ t ~< T.

58

Proof:

Let

UN(t) - PNU(t)

and

z ( t ) = (UN-U)(t),

we have from (7.1)

3q N ~+ ~t + LUN - - ~z

Lz,

that is to say

~UN ~t

az + LcuN = (Lc-L)UN + ~-t+ Lz,

so by subtracting (9.1), and setting

WN ~ ~

- uC

~WN az ~t + LcW N = (Lc-L)u N + ~ + Lz.

Multiplying this relation by

WN

in terms of the scalar product

(.,.), we

have

aW N (~--~', W N) + (LcWN,W N) " ((Lc-L)UN,WN) + (~, W N) + (LZ,WN).

From the antisymmetry of

LC, we deduce that, (passing to the real parts)

d ~ #WN' 0 ~ ~'~-~" 1 d IWNI~ = Re((Lc-L)UN,WN) + R eL-~-~rSz , W N) + Re(LZ,WN). 'WN'o'-~-

The Schwartz inequality then yields

d"~ #WNHo < I ( b c - L ) u s # o + U~-~ 0 + #LZno

59

so integrating between

(9.4)

0

and

T

IIWN(t)II0 < ;IWN(0)U0 + t

we find

Sup (I$(Lc-L)UNI]0 + ll~z~II0=~+ llLzil0). tg[0,T]

We will now obtain an estimate for the Sup term in (9.4).

ILc-L)u N = (Pc-l)a ~Du N + ~

First consider

(pc_ I )au N.

Let y(t) = a ~

(t);

vo as

a e Cp(1), we have

~N(t)

Ify(t)iiT_1 < Cii~--~llT_ 1 < CilUN(t)fl~.

Furthermore, from the definition of the norm

li. ti

given in section 6,

r

it follows immediately that

(9.5)

since

llUN(t)llT < rfu(t);{T

UN(t) = PNU(t) • We deduce then from Theorem (8.1) (applied with

r = T'I)

IIY-PcYll0 < C(I+N2)-(T-I)/211ylIT_I

C(l+N2)-(T-l)/2tiull .

that

60

We have

II(Lc-L)]NIi 0 < II(Pc-I)yll0 + H(Pc-I)a]NII I

C(l+N2)(l-~)/2iluIIT + ;i(Pc-l)a]Nil I.

Applying Corollary 8.2 with

s = 1

and

r = T

we find that

I-T L l;(eC-l)auNii I

Using inequality

C(I+N 2) 2

(9.5) we have

liauNiIy < CIIUNII~

This establishes

ilauNflT,

Cil uil

T.

that l-r

II(Lc-L)~N(t)Ii 0 < C(I+N2) 2

(9.6)

ilu(t)ll .

As z(t) : -(l-PN)U(t) ,

it follows that I--T

(9.7)

tiLzll0 < CIIzU 1 = CltU-PNUb~ I < C(I+N2) "-~-- IIu(t)ilT

(9.8)

z ~u )--f- ~u 11~_~ii0 = il(l_PN) ~-t li0 ~ C(I+N 2 U~IIT-I < C(I+N 2) 2

l-r

i-~

liullr'

61

where the last inequality is gotten by noting

~U

B--~ = -Lu,

IIL u II~ - 1 < Cllul} . T

an d

Therefore I--T

~Z

sup (II(Lc-L)UNII 0 te[0,T]

+

fl~-~ll0 + ULzlI0) < C(I_N 2) 2

IIu 0 II•.

We also have T

IIWN(O)II0 = IIPcU-PNUlf0 = trPc(U_PNU)H 0 ~ C(I+N 2)

2 itUoll ,

(see (8.16)). From (9.4) then we have l-r ilWN(t)ll0 ~ (I+Ct)(I+N 2) "2"

IlUoIIr ,

0 ~ t < T,

and the result follows since

(9.9)

;lu(t) - Uc(t)I; 0 ~ Itu(t)-]N(t);l0 + rlWN(t)It0. Q.E.D.

Remark 9.2: we

have

an

error

The preceding result shows that if estimate

of

order

0(N I-T)

obtained for the Galerkin method (see Remark 7.1).

u c H~(1), with

which

is

identical

T > I, to

that

62

I0.

Time Discretization Schemes: Suppose

A

is a

MxM

matrix and

U(t) e

is

the solution

of the

differential system

d d--~U + AU -- 0,

(10.1) u(o)

We former

can

discretize

correspond

(I0.I)

to the

by

= u o.

either

approximation

implicit of

the

or explicit

true

schemes.

exponential

solution

The by

some rational fraction, the latter by polynomials. For example, the scheme

U n+l = (I + AtA)-iu n,

is an implicit

scheme,

since for each iteration

solve (a matrix to invert),

there is a linear system to

As

U((n+l)At) = e-AtAu(nAt),

and

as

(I + AtA) -I

is

an

approximation

small, this algorithm converges. In contrast the schemes

(10.2)

U n+l = Pj(AtA)U n

of

e

-AtA

for

At

sufficiently

63

where

(-T)J

J

(10.3)

Pj(~) -

[ ..... J'O Jl

'

are explicit, because there is no linear system to solve at each iteration. They are convergent tlons

(of order

since the polynomials

J) to the exponential

(and thus the matrices

Pj(AtA)

e -T

Pj(T) when

approximate

e

T

-etA)

constitute approxtmais sufficiently small

•

We do not assert a priori that the explicit schemes have a big advantage in

terms of efficiency over

full matrix

A.

the implicit

using

for the general

case of a

But in the case of the collocation method studied in section

9 we saw that the product of a vector rapldly,

schemes

Un

by the matrix

the Fast Fourier Transform

A

can be evaluated

(see Remark 8.1).

Let us examine

these schemes now in some detail. The scheme

first question

to

converge,

approximation

to

it

that presents itself is that of stability. is

not

sufficient

the exponential;

it

is

that

the

further

radius be less than I, otherwise the sequence

matrix

required

Un

Pj(At)

that

For the be

an

the spectral

generated by the algorithm

(10.2) will increase exponentially. Whether this is so depends on the spectrum of the matrix

Proposition

I0. I:

The

with an antlsymmetric matrix

Proof:

differential A

of order

system MxM

(9.1) with

Suppose 1 f w-nkelnX ' Sk ~" 2N+I' In CN

is

A.

of the type (I0. I)

M = 2N+I.

64

where

W

is (as in section 8) the principal root of order

(2N+I)

of unity;

we have shown in section 8) that

(10.4)

for lJ l, Ikl < N

*k(Xj ) = 6jk

Therefore, for all

u ~ SN

and

*k ~ SN"

we have

U(x) = {kI
We set

Uk = U(Xk) , Ikl < N

Further, the functions

~k

so that

U = (Uk) e

~N+I.

are orthogonal; in fact, according to (8.8),

we have

(10.5)

i (*k'*£) = (*k'*£)N _ 2N+I lJi
N _i~

Letting Uc(t ) = ikI6N Uk(t)~k(x)'

we may write (9.1) in the equivalent form

(~Uc,,z)

+ (Lcuc,%) = O,

I£ I < N,

that is to say

dUk

fk~
-~

+ (Lc¢k,,£)Uk] = O.

6£k.

65

Then using account (10.5), we get

dU£ dt + (2N+I)

$ (Lc~k,¢£)Uk = 0, Ik| ~N

which shows that (9.1) is indeed a differential

system of the form (i0.i) with

a matrix A of order M×M (where M = 2N+I) defined by

A = (a£k)ikl,l£1
(10.6)

a~k = (2N+I)(Lc~k,~).

The

antisymmetry

(9.3)

of

LC

shows

that

the

matrix

A

is

anti-

Q.E.D.

symmetric.

Remark 10.1:

The Galerkin method amounts to solving

~u N ~u N ~v N (~-~- ,VN) + (a ~ x 'VN) - [anN' ~ x ) = 0,

for all

v N e SN,

without numerical integration. The collocation method amounts to solving

~u C

(zo.7)

where

~u C

~v N

(r6- ,VN) + (ar~- 'VN)N - (aUC' ~r~--)N= 0, a

form

of

numerical

summation

integrals which are generally impossible

(8.9)

has

been

used

to evaluate exactly.

to evaluate

the

66

Remark 10.2: given vector

In practice,

to evaluate the product of the matrix

U, we first note that the coefficients

a~k

A

by a

of the matrix

A

given by (10.6) may equally well be written using (8.8) as

a~k = (2N+I)(Lc~k,~£) N ,

that is to say a£k = [jl
(In this

form in which

I(L C Sk)(Xj)) $£(x-~.) = (L C Sk)(X£)

the skew symmetry

of

A

is less obvious).

Suppose

then that

(10.8)

u(x) = [kI¢ N ~k(X)U k.

In order to calculate

(AU) E ~ a~k U k = ~ (L C ~k)(X~)U k = (L C u)(x~), k

it is sufficient the function

u

to calculate

LC u

at the points

X£

given the values of

at the same points.

Using (9.2) it is possible therefore to proceed in the following fashion I.

Given

u(xj) = Uj, we calculate

the Fourier

coefficients

an

of

u

(see Corollary 8.1) with the help of Fast Fourier Transform (FFT). 2.

We deduce the Fourier coefficients of

^

vn = ina n.

~u v = ~x

by means of the formula

67

3.

Using

points

x~

the inverse

FFT we obtain

(~Pc(aU))(x£). (i)

Bu a ~x

and then the values of

In order to evaluate

the values

(Lcu)(x£)

at

v(x£)

of

~U

~x

at the

x~.

it remains to calculate

For that (in an analogous manner)

We calculate by multiplication

W(Xj) = a(xj)u(xj) E (Pc(aU))(xj)

(ii)

next (via an FFT) the Fourier coefficients

^

Wn

(iii)

from

W - PC(au).

we have therefore by multiplication the Fourier coefficients

~W ~ x (x£)

FFT the values of

As the FFT has an operation infer

that

operations.

the

calculation

(Instead

of

of

of the

8W ~x ;

then by an inverse

and finally

count of the

0(M 2)

(cf. 2 above)

(Lcu)(x£).

O(M log2M)

product

AU

operations

needed

(see section 8), we

costs

only

0(Mlog2M )

if we calculated

the

product directly). We shall then use discretization

schemes for differential

type (I0.I) which are efficient when the matrix For example we may use the three-level

A

systems of the

is antisymmetric.

leap-frog scheme (of second-order)

(see e.g., Richtmyer-Morton

[14])

(10.9)

un+l - un-i + AU n = 0, 2At

68

or

one

of

the

schemes

(10.2)

provided

that

the

following

condition

is

satisfied

(I0.I0)

there exists

6 > 0

such that

it[ < 6,T e ~

implies

IPj(iT)I < I.

In matrix

fact,

as

Q, where

A

is

D = Q*AQ

antisymmetric

it

is

diagonalizable

by

a unitary

diagonal and pure imaginary.

Let %. = d.. J 33

and

V n = Q U *; n

we may write QV n+l = pj(AtA)QV n

vn+l = Q *Pj(AtA)QV n

V n+l = pj(AtD)V n

whence vn+ i = Pj(At%j )Vjn

The condition that

(I0.i0) shows that if

IAt%jl < 6, for all

At

[j

is chosen sufficiently

J, then

V n = (Pj(At%j))nv~ J

,

"

< N.

small so

69

is bounded

and this proves the stability of the scheme. It is well known 3,4,7

or

that

the condition

(I0.I0) is satisfied,

e.g., if

J =

8.

For example,

for J = 3 we have

2 T2

Pj(i~) = 1 - iT

2 [Pj(iT)I 2 = (1 _ ~ ) 2

(iT)36

2 3 i ---~-~ i(T - ~ )

3 + (T _ ~ ) 2

4 6 T T = i - ' i 2 - + 3-6 ° Q.E.D.

To

finish

the analysis

bound for the eigenvalues

Proposition

10.2:

If

of stability,

of the matrix

A.

% s Sp(A)

for

it remains

only

to find an upper

A defined by (10.6), then

I%1 ~ CN.

Proof:

Suppose

~ s Sp(A)

and

U

From (10.5) and (10.6) we have by setting

E(2N+l)(u,u)

i.e., assuming

llull0 = I,

is an eigenvector u =

~ Uk~ k Ik| ~N

so that

AU = ~U.

(as in (10.8)

= XU U = U AU = ....(2N+I)(LcU,U),

70

k = (LcU,U).

Now (see (10.7)) (denoting by

Im

the imaginary part of a complex number)

~u (au, ~x)N

(Lcu,U)=(a ~x ~u 'U)N

2 Im(a ~u ,U)N

and ~U

I(a ~~u ,U)N l < max la(xj) [ l;~xfl0,N HUllo,N J

liUflo, N

where

in (8.6).

is the norm of

As

u

associated with the scalar product defined

u ~ SN, we have

fi~xflO,N = 'I~I 0 = (in~4 N n21Unl 2) I/2< NIlnI< N ]UnI2) I/2= NHUIIo = N

ikl < 2N max la(xj)i

consequently,

and this furnishes an evaluation of the

J constant

C.

Corollary I0. I: If (I0.I0) and

C

6 At < ~-~

where

6

is the constant introduced in

is the constant of the Proposition 10.2, the iterative method

(10.2) is stable; we have

iiun+ID
where

HUff0

d~f

-

( ~ - I " ik~
Error Estimate Let

g c SN

be given, we define

O'

71

U°(g) = g

un+l(g) = Pj(AtLc)U n (g),

and we also define

uc(t;g)

n > 0

tO be the solution of the equation

@u C B t + LcUc = 0

Uc(0;g)

According to (i0.i0), we have, for

(10.11)

=

At

g.

chosen as in the Corollary 10.I,

I I u n ( g ) l l 0 < IIgrl O.

On the other hand the skew symmetry of

~Uc , Uc) = 0 Re(~-E--

>

LC

shows that

I dd'--tliUc(t)ii2 = 0, -2

and therefore that

(I0.12)

llUc(t;g)l;0 = llgllO.

Setting

(10.13)

where

Ej(g) = UJ(g) -Uc(tj,g),

tj E jAt;

we note that

Ej

is linear in

g.

72

We

are

interested

in

estimating

Ej(Pcu0).

To

do

that,

we will

establish the following preliminary result, proved in Pasciak [13]

Lem,n~ 1 0 . 1 :

If

At

is chosen as in Cor@!larY i0. I, and

nat < to,

we have

(i)

lIEn(g)ll0 ~ Cilgll0

(ii)

where

IIEn(Tcg)II 0 < cAtm-lltgllo

for

1 < m < J+l,

T C = (I + LC )-I.

Proof: (10.12).

(i) results immediately from the stability results (i0.ii) and

To establish (ii), note that if

f = T~g

Ej+l(f) = uJ+l(f) - Uc(tj+l,f) = Pj(AtLc)UJ(f ) - exp(-AtLc)uc(tj,f )

= Pj(AtLc)Ej(f ) + (Pj(AtL C) - exp(-AtLc))Uc(t j,f).

According

to the stability

result established

in the Corollary

i0.i we

have, liEj+l(f)fi0 ~ llEj(f)ll0 + iI(Pj(AtLC) - exp(-AtLc))Uc(tj,f)Ll 0.

To estimate the second term, which we will denote by f = T~g

we have Uc(t j,f) = r~uc(t j,g).

ST, note that since

73

(This results from the commutative properties of the resolvent of an operator and the semi-group associated with this operator, (see Kato [10]). Let of

LC •

%k e ~

and

~k e SN

denote the eigenvectors and eigenfunctions

Set Uc(tj,g) = ~ ak~ k k

Uc(tj,f) = ~ Bk~ k k (pj(AtL C) - exp(-AtLc))Uc(t j,f) = ~ Tk~ k" k We have Be

~k -- _ _ (l+%k)m

and (l+~k)m Atm%k = ~k (l+%k)m

As by hypothesis

(-At%k)£

~k

Yk = [Pj(AtXk) - exp(-At%k)]Bk

£>J

(-ht%k)£" ~ £'>J-m

IAt%k I 4 ~,

(%-+m) !

we have

(-Atlk)£" ~ -~f~-[= e ,

I I

">J-m

therefore ITk Thus

ST

satisfies

< I~klAtm e ~

74

ST - (I l~k 12) 1/2< Atme6(l l=k 12) I/2= Atme~"Uc(tj,g)"0 " k

k

We conclude (using (10.12))

llEj+l(f)ll 0 < llEj(f)ll0 + Atme~ilgiio ,

whence

(ii) with

hypothesis that

C = to e~

by summation

from

j = 0

to

n, and using the

nat < t o . Q.E.D.

We are now in a position to establish the principal result.

Theorem I0.I:

If

u 0 ~ H~+J(1), we have the error estimate

llU(tn) - Unll0 < C(NI-~+ AtJ),

where

Un = un(Pcuo)

is the solution at time

tn = nat

for the completel 7

discretized problem.

Proof:

We establish (by induction on

u=

J) the following identity

J+l T~(Lc-LN)(I+LN )j-lu + TJ+I(I+LN )J+Iu'C j=l

for all

u g SN.

We infer from the linearity of the operator

En

defined in (10.13) that

75

En(PcU 0) = EnCPcU0-PNU0) + EnIPNU0) J+l En(PNU0) = ]I I'= En(T~(Lc-LN)(I+LN)J-IPNu0 )

(10.14)

J+l J+l + gn(T C (I+L N) PNU0)-

Applying result (ii) of Lemma I0.i, we have for

j=l,...,J+l

IIE n I T~ (LC-L N ) (I+L N )j - 1PNU0 ) ii0 ~ CA t j - 1 II(L C-L N ) (I +L N )j - 1PNU0 II0"

From the definition of

LN, we have, for

v c SN

II(Lc-LN)Vll 0 < II(Lc-L)vlL 0 + U (I-PN)LVI~ 0 l-r C(I+N 2)

2

i-~ Lfvlir + (I+N 2)

2

tlLvll_i,

where we have applied a variant of (9.6) for the first term and Theorem 6.1 to the second term. As

IILvIIT_1 < CllvllT

(since the coefficient

a

is smooth) we have

I-T II(Lc_LN)Vll 0 < C(I+N 2) 2

Finally, L

from

HSp(1)

supposing in

v = ~I+LN)J-IPNu0, we

11v11T"

have

from

_ Hps+l (1)

llvll < CIIPNU0 IIT+j-I < Cllu011 +j_ I.

the continuity

of

76

Then the last term needed to estimate in (10.14) is

CA tJ llu0ilj+I.

ilEn(TJ+I(!+LN)J+IPNu0)II

We have then I--T

J+l itEn(PNU0)ll ~ ~ cAtJ-I(I+N2) 2 j=l

llu0ilT+j_1 + CAtJl[u01lj+l

and ;IE n (Pcu0) II0 ~ ItEn (Pcuo-PNU0) it0 + 11En (PNUo) ;I0

llPcUo-U0i;0 + llu0-PNU01l0 + liEn(PNU0)li0 I-T

C(I+N 2) 2 Ilu0llr_l + tlEn(PNU0)lt0,

that is to say 1-T

UEn(PcU0);I < C((I+N 2) 2

we conclude by noting that if

+ AtJ) IIuoiET+j,

g = PcU0 , JlEn(PcU0)ll0

gives the error between

the solution of the semi-discrete problem and that of the fully discrete problem.

As the error between

U(tn)

and

UC(tn)

is of order

N I-T

according

to section 9, we have the desired result.

Remark 10.3: i.

The

error

estimate

established

in

Theorem

i0.I

requires

strong

77

regularity for the initial solution For the case of the weaker

u0, (and hence the exact solution

regularity

manner, convergence of order

0(At J)

u 0 s H~(I), we can prove, in the same of

Un

to

constant introduced in this case depends a priori on 2.

In practice,

established schemes

u(t)).

Uc(t n)

as

At + 0 but the

N.

as the time step is limited by the stability condition

in Corollary

10.1, it is not useful to take the order

to be very high (J = 3

seems a reasonable choice).

J

of the

We might as well

use the leap-frog scheme which is second order accurate and requires only the product of the matrix

II.

A

by a vector at each iteration.

An Advection-Diffuslon Equation We consider now the parabolic equation

i)

ii)

iii)

~u ~ + Tu = 0,

t > 0,

u(0,x) = u0(x)

(initial condition),

u(t,-~) = u(t,~), 78u x (t,-~) = ~ 8u x (t,~)

(periodicity condition),

where the operator

T

is given by

T = sA + L,

where

A

is the diffusion operator

x s I,

78

(11.2)

and

L

A = - ~fx b ( x )

~fx + e ( x ) ,

is the advection operator

~u 3 Lu = a ~ x + ~ x (au).

The

coefficients

periodic,

a,

b,

and regular,

We shall examine

and

e

of

e > 0

the

operator

the dependence

b(x) ) 8,

assumed

to be

real,

is a real number. of the solution,

We suppose that there exist constants

(11.3)

T

~ > 0

e(x) > -7,

us, on

and

e.

7 e R

such that

for all

x e I.

for all

u e H$(1)

This means that

3Ul2

yllull2,

(Au,u) ~ ell~xl 0 -

(11.4) (Au,u) > ~llull 2 1

The existence the classical

of a solution

(¥+B)NuU

u

.

of (11.1)

results on parabolic problems,

We will confine U

-

our attention

for

e > 0

follows

(see e.g., Lions-Magenes

to establishing

then from [Ii]).

an a priori estimate

for

•

Theorem positive

II.I:

constant

Let C

A > 0 such that

and s ~ 0 for all

~ > 0

~iven; and

then

there

exists

t ~ [0,A] we have

a the

79

inequalit~

flu (t)r~s ~ Cilu011s.

Proof:

In a manner analogous to the proof of Theorem 7.1, we introduce

the operator A s : Hp(1) + L2(1), such that

IIASull

Ilull

= 0

Recall that where

s

As

.

s

is an operator (pseudo-differential,

is not even integer) of order

d Uu e(t)li2 = (AS(_Tu),ASue) dt s

s.

in the general case

We have then

+ (ASue,AS(_Tue))

= -((L+L*)ASuc,ASuc ) - 2Re(Ku ,ASu )

- 2e(AASue,hSu ) - e([hS,Alu

where

K ~ [AS,L] E ASL - LA s In order

antisymmetry (see

(11.4)),

to get an upper of and

denotes the commutator of bound

L, the fact that finally

the fact

s+l, to yield the result that

,hSue) - e(hSu ,[AS,Alu ),

K

on

us,

the

and

L.

we can use successively

is of order that

As

s, the coercivity

operator

[AS,A]

of

the A

is of order

80

It[AS,A]u II0 < Cll~Ustls+l.

We obtain

a-{ d llus(t)ll 2s ~ 2(C+s(Y+B))llus if2s - 2eBliASuslt 2I + 2CleLiuslis+lliUe ~Is •

(11.5)

Then using the inequality

211uslls+l fluslIs < elIusils+ 2 I + - 1 Hu II2 c~ E s

with

~

taken equal to

~BI ' (noting that

11ASusll1 = ]tuslts+l))

we find that

d__ flus(t)ii2 ~ C2[lugll2 dt s s

wi th c 2 ~ 2(c+~(~+~))

+-%--

.

Thus C2t 2 2 llue(t)ils < e ;lUoII s ,

and the result follows by, noting that

C2

is bounded independently

of

s. Q.E.D.

The Semi-discrete We introduce

Problem the operator

AC

defined by

81

(11.6)

AcU = - ~ax (pc( b ~au)] x j + PC (eu)

which is an operator from

SN

to itself.

Set

(11.7)

where

T C = cA C + L C

LC

is the operator,

studied in sections 9 and i0, defined by

LcU = PC (a ~ )

The semi-discrete

a + ~ x PC (au)"

problem is then to find

(i)

a---tUc + TcUc = 0

(ii)

Uc(0) = Pc(U0).

Uc(t) < S N

satisfying

(11.8)

I~ua

II.I:

The

operator

TC

defined

in

(11.7)

satisfies

coercivity inequality

Re(Tcu,U) )

Proof:

As

EBII~---~II02

Re(Lcu,u) = 0

-

eyIlull~

,

for all u s S N.

from (9.3), it suffices to establish that

the

82

~u 2 2 Re(Acu,U) ~ BII~II0 - yllullO.

Now, we have for

u s SN

~u)),u ) (Acu'U) = (- ~x (Pc(b ~x

+

(Pc(eu)'u)

~u),~u

= ImC(b~x

~x ) + (eu,u) N

= (b ~x' ~u ~x)N ~u + (eu'u)N

1 2N+I ij~
1 12 lu(xj)i2) 2N+I ijI
3u 2 0

= B lir--ll oE

since

u ~ SN

exact for

2 0

y IIu li

(and the fact that the numerical integration formula (8.9) is

f c S2N). Q.E.D.

We study now the error between the solution (11.1) and the solution

uC

we shall drop subscript

E.)

u

of the continuous problem

of the discrete problem (11.8).

(For simplicity,

83

Theorem 11.2: constant

C

Let

Y ) 1

(independent

of

and s)

A > 0 such

be given;

that if

then there exists a

~+i u0 e-p (I), we have

the

error estimate: I-T

Ilu(t) - Uc(t)ll 0 ~ C(I+N 2) 2

for all

t E [0,A].

Proof: = 0)

(llu0llT_l + (llu0112 + (Uu0ll ~ + ~llu01lT+l)2)1/2),

To simplify the calculations we suppose

e ~ 0

(and hence

(the general case is left to the reader as an exercise).

Suppose UN(t) = PNU(t)

and

z(t) = UN(t) - u(t).

We have from (II.I)

a~N ~-{--+ TC~ N =

Letting

WN = ~

Bz

(Tc-T)]N + T f+ Tz.

- Uc, and subtracting

aWN t~+

(11.9)

(Ii.8), we deduce that

az TcW N = (Tc-T)~ N + - ~ +

Taking an inner product with

Tz.

WN, and taking the real part, we find that

(applying Lemma 11.1)

aWN 2 d IIWNII2 + EBII~T~0 ~ Zl + z2 + z3 ' 21 dt

84

where Z I ~ Re((Tc-T)~N,WN)

Z 2 E Re(~8-~, W N)

Z 3 E Re(TZ,WN).

Let us first find an upper bound for

ZI; we have

Z 1 = eRe((Ac-A)~N,WN) + Re((Lc-L)]N,WN)

(11.1o)

((Ac_A)~N,WN)

= (_ ~--~x ~ PC b ~-'~-,WN) ~UN ~ b ~-~--, ~ N W N) - (- ~-~x ~W N 2 ~N ~WN 1 ~N 2 = ((Pc -l)b ~x ' ~xx ) < 2-~ il(Pc-l)b ~-x--x 11 + ~ IL~--~--II0'

and ~

0

2

I (Lc_L)UNII02 ' Re((Lc-L)UN,WN) ~ ~ ilWNfl0 + ~II whence

~ N 2 + ~iI (Lc-L)UN~0 + ~ Z1 ~ -i~ II(Pc-I)B ~-~-X-110

Now, if

~W N 2 + 7~) ilWNIle. 1'~-x--i'0

~u N y(t) = b ~x-x- (t), we have in a manner analogous to the proof of

Theorem 9.1:

(II.ii)

,lY-Pcy,i~ < C(I+N2)I-TI,u(t)LI~,

85

and according to (9.6)

II(Lc-L)UN(t)II20 < C(I+N2) I-T liu(t)U2, whence SW N 2 0 2 Z1 < C(~-+ ~)(l+N2)1-Tflu(t)..2 + -~ ,,~--~--I, 0 + ~ ilWNI,0 .

Moving onto

Z2, we have

1 Z2 < ~

8z 2 ll~-~II 0

+

0 2 ~ llWNil0,

with 8z2 8ui12 I-T 8UEl2 t~8-tT-I" ii~-~tI0 = il(l-eN) ~-~ 0 < C(I+N2)

Finally, for

Z 3 we have

Z 3 = (TZ,WN) = ¢(AZ,WN) + (LcZ,W N) with (Az,W N) = (b 8z 8WN I ~ x ' "~x ") ( ~

8zH2 8WN 2 llb ~ 0 + ~ ll~--x--ll0'

and 1 (Lcz.W N) ~ ~

2 8 2 llLczli0 + ~ ;IWNI)0"

IILczU20 ~ C(I+N2) I-T ilu(t)1,2 ,

(11.12)

therefore

8z 02 < C" zli~ ~ C(I+N2) I-T flu(t)'l~ "b ~qx'

86

z3< ~c~ + ~I(1+=~)I-~ u(t)~ + ~ ~~WoN Gathering the terms

2

+ 8 IIWNIII

•

ZI, Z2, Z3, we find that:

30 IIWNI2 lu 2 21 ddt IIWNI20 < 2-0 + C(l+N2)l-X(llu(t)llr2 + ll~-tllT-IJ"

Applying Gronwall's Lemma 11.2, proven later we deduce that 30

0 where we have used the estimate established in Theorem 9.1 namely

IIWN(0)I20 < C(I+N2)-TIIu012.

Theorem Ii.i shows that

lu(s)l T2 < Clu0112

with a constant

C

independent of

~U

l]~--~I] T_1

¢

so we conclude that

f

cIAUlT_ I + IILull _ 1 < Cl~llu01iT+I + flu01 J. Q.E.D.

Lemma

11.2 (Gronwall's Lemma):

Suppose that a differentiable

satisfies the inequality

(11.13)

y'(t) < ~y(t) + g(t),

function

87

then: t

y(t) ~ yo eat + f

g(s)ea(t-S)ds. 0

Proof:

We may rewrite (ii.13) in the form

d (y(t)e-~t) < g(t)e-~t, dt

so integrating betwen

0

and

t

yields

t y(t) < e~t(y 0 +

f

g(s)e-~Sds). 0

Remark II.I:

The result obtained in Theorem 11.2 is not as strong as

that of Theorem 9.1. of

~(I)

In Theorem 11.2, we require that

u 0 ~ H~+I(1)

instead

which was all that was needed for the earlier error estimate.

In fact, we have merely established that

8U 2 2 ,,8-~,,z_1 ~ C (,,Uol, 2 + ~,,Uot,T+I),

where the constant In order

C

is independent of

to obtain a result which is as strong as Theorem 9.1, it is

necessary to eliminate the term this

is

possible

though at vicinity of

the

g.

(see

cost

t = O.

following

~11u0Ti2+l in the right-hand side above. example)

of introducing

in

a term in

the

constant

I/t 2

which

coefficient

Now case

diverges in the

88

Example

II.i:

Consider

the particular

case where

d2 A = -

and

L = ~--~

dx 2

that is to say where

u

is the solution

s

~u

i)

~2u g

of ~u

s

~-i---s--+~--f-=

o

~x 2

ii )

u s ( t, -~ ) = u s ( t , ~ )

(11.14)

( peri odi city) iii)

iv)

In this

~u ~ s (t,-~)=

us(0,x) = g(x)

case we know explicitly

n~

then,

referring

(initial

the Fourier

ug(x,t)

we have

~u ~ s (t,~)

coefficients

^ . . inx Un~t)e ,

to (ii.14)(i)

^

du n ^ t~-6--+ (en 2 + in)u n = 0

Un(0)

= gn

Un(t)

= e-(en2 + in)tgn.

so

condition).

of

us;

if

89

It is easily verified that

,,ue(t),,2 = ~ le-(Sn2+in)t]2Ign]2 n

I.

-2en2t = I

e

[gnl

2

2

<

Ilgll 0

n

and that I,u~(t)I,~ = ~ (l+n2)Se-2en2tlgnlr2

2.

n

is bounded for all that for given effect).

s

and

t > 0 (but with a constant dependent on

¢, g ¢ L 2 + u¢(t) s H s

for

t > 0

and any

We can also establish that (Theorem 11.1)

,,U¢(t)H2S ~< ,,gl,2 = ~ (l+n2)Sign[2 n

3.

Consider

t~

~ (-(sn2 + in))e-(¢n2+in)t gn einx n

We have ~u¢ 2 I't~lls = I (l+n2)s [¢ne+inl 2 e-2¢n2t Ign 12 n

= ~ (1+n2)S(¢2n4+n2)e-2¢n2t Ign 12 n

As the function 2

~(y) = y e

is bounded by

-2yt

s

¢), and

(regularizing

90

~(~)

=.

i

(te)2 ' we have 2 2 4 -2~n t ~ne

1 (te)2 ;

therefore

~us 2 n l+n2)Sf I n2]iSnl 2 2 I 'r~'s < I ( ~777~ + < 'gs+1 + 7 7 7 7

I,g,I~

which illustrates Remark II.I. (In this example with constant coefficients, we may calculate directly PNUs(t)

without

having

to

solve

the

discrete

problem

with

the

methods

described in section i0.)

Remark 11.2: preceding

If

example

coefficients (1))

s > 0

(which

is fixed, the regularization observed in the generalizes

ensures that

order of the error may not be

to

u(t) e H~(1)

0(N -s)

the

case

of

for all s, and

for all

s

nonconstant t > 0.

The

as one would expect because

of possible errors in the approximation to the initial solution if it is not regular. Remark 11.3: interval

]0,~[

Suppose that we have to solve the problem (ii.I) in the with

the

Dirichlet

boundary

conditions;

replaced by u(t,0) = u(t,~) = 0,

(i)

See Taylor, [17].

for all

t ~ 0.

(ll.1)(iii)

is

91

We

will

interval

show

that

I = ]-~,~[

To

we

may

convert

this

problem

with periodic boundary

do so we will

use the fact

that

to

the

one

posed

in the

conditions.

the derivative

of an odd function

is

even and vice versa. Suppose

that

the

solution

coefficients

a, b

and

e

u,

the

initial

are, for the moment,

solution

Uo,

and

the

only defined on the interval

[0,~]. We can extend even;

for

u,u 0

and

a

b(x) = b(-x),

Au

this

fashion

b

and

e

to be

~au x

Uo(X) = -Uo(-X),

a(x) = -a(-x)

e(x) = e(-x).

will

be

even

be

odd,

au

as will, b~-~ 8u

while ,

~ x b ~-~ ~u

and

(au)

is

will be odd. Similarly,

odd and

Ln

If

the

interval

a ~x

equation

other

u

periodic

problem,

we

boundary

conditions.

a

]0,~[,

are

(ll.l)(i)

and at

hand

cient

will

will

be even,

therefore

will thus be odd.

]-~,0[

On the

on

I, and

x < O, we let

U(X) = -U(-X),

In

to be odd over all

regular

0

holds

(since

is periodic. are

brought

However,

even

over

an odd function

will

back

to

solving

also

on

a

of the solution problem

if the given initial

so for

hold

the

is zero at the origin).

By the uniqueness

for the problem with

that is not necessarily

]0,~[, it

the Dirichlet the problem

with

of the

periodic

u 0 and the coeffiboundary

conditions

with periodic

boundary

92

conditions

except

derivatives) The

if

vanish at

Fourier

method

on the interval

]0,~[

the same defects;

u0 0

and and

can

(at

same

time

their

even

order

produces

in fact

an approximation

to the function

by a sine

series,

an approximation

which

we can only approximate

also

the

~.

of their even order derivatives We

a

consider

well

vanish at

the

0

problem

functions

and

with

suffers

u

from

which along with all

z.

homogeneous

Neumann

boundary

conditions. ~u ~--x (t,0) = ~~u x (t,~) = 0;

in

this

case

functions,

u

and

the

and

u0

Fourier

are

extended

method

will

over

the

correspond

entire

interval

as

to an approximation

even by

a

cosine series.

Remark Suppose

11.4:

A Nonhomo~eneous

equation.

that we have the problem

~u --+Tu=f ~t

with

f # 0

(II.8)(i)

((ll.l)(i)

and

(ii))

being

unchanged.

is replaced by

~u C ~ t + TcUc = fc

with

fc = PC f"

The

discrete

problem

03

The equivalent

of equation

(11.9) occuring in the proof of Theorem 11.2

is ~WN ~ ~z ~t + T c W N = (Tc-T)u N + ~--~+ Tz + f - fc'

and there is a supplementary term to estimate, which depends on the regularity of

f.

(Note that the estimates given in Theorems 9.1 and Ii.i are always

valid.)

12.

The Solution

of an Elliptic

Problem

To conclude our study of the applications of Fourier series, we will now examine elliptic problems. We consider the following stationary problem; find

i)

Au = f,

u = u(x)

such that

x e I,

(12.1) ii)

We

u(~)

suppose

= u(u),

that

u'(-~r)

= u'(~)

the scalar

y

(periodic boundary conditions).

introduced

in the hypothesis

(11.3) is

negative so that (see (11.4))

2 (Au,u) > ailull I

(12.2)

with

~ = min(8,-y) > 0. The

inequality

(12.2)

expresses

uniformly strongly elliptic on the space

the

fact

H~(1).

that

the

operator

A

is

94

The Lax-Milgram lemma along with the regularity results for the elliptic problems

(see Lions-Magenes,

solution

u ~ H~+2(1)

if

[11]) permits

f e H~(1), for

us

to affirm the existence

of a

s > 0.

The discrete problem may be written naturally in the form

AcUc = fc'

where

AC The

is defined in (11.6), and operator

AC

satisfies

fc = PN f"

an inequality

of uniform ellipticity

(see

Lemma II.i): (AcU,U) ~

~llull~,

for all

u ~ SN.

This will be useful in proving the following theorem.

Theorem that if

12.1:

Let

~

f s H -2(I)

T > 1

(and

be $iven;

there

exists

a constant

llU-Uclll < C(I+N 2) 2

We have, by setting

~N = PN u

Ac~uN = (Ac-A) ~

so for

WN = ~

- Uc,

such

~(I)) , we have the (optimal) error estimate u e Hp I--T

Proof:

C

IlulIT "

and

+ Az + f,

z = UN - u,

95

AcWN

=

(Ac-A)~N

+

Az

+

f

-

fc'

and ~IIWNI'~ ~ (AcWN,WN) = ((Ac-A)~N,WN)

+

(Az,WN)

+

(f-fc,WN).

Now, we have (see (11.6))

~N ((Ac-A)~N,Wn) = ((Pc-l)(b T~--) + ((Pc-I)(euN),WN)

I-~ < C(I+N 2) 2 llu;l IIWNI;I and ~W N (Az,W N) = (b ~)z ~x ' ~ ) + (eZ,WN)

<

C(lJzll1

IIWNII I

+ tlzli0 IIWNII0)

I-T < C((I+N2) "2 + (I+N2)-T/2)IluflT IIWNIII.

Finally,

l-Y (f_fc,WN) < itf_fcll_l llWNtl1 ~ (I+N 2)

where we have used Theorem 6.1 (with

II ull+t"

we have

ell fll+r 2 '

2 llfilT_2 IIWNUl'

s = -I); then, noting that

(regularity result),

96

1-'E

~IIWNII21 < C(I+N 2) 2

llfllT-2

LIWNIIi'

and the result follows with

;lU-UcIi1 < llU-~N1i1 + IIWNIII. Q.E.D.

Remark 12.1: must at least choose

If we choose f

in

fc = PC f

H~(1)

for

(the interpolant of PC f

to have a meaning.

other hand, we only know in this case that

Itf-fcU_l < Cllf-fcIl0,

which yields the nonoptimal error estimate I-T

ilU_Ucii 1 ~ C(I+N 2) 2

ilull,r+l,

f), then we

(for

~ > 3).

On the

PART B POLYNOMIAL SPECTRAL METHODS

I.

A Review of Orthogonal Polynomials Suppose

I = ]a,b[

: I + ~+

be

a

weight

strictly positive on We denote by

is a given interval function

which

(bounded or not). is

positive

Let

and

continuous

(and

I

into

I).

L~(I)

the space of measurable

functions

v

from

such that

(f

Uv]I E

[v(x) i2 (x)dx) i~< +~. I

L2(I)

is a Hilbert space for the scalar product

(u,v)

= f

u(x) v(x) m(x)dx. I

We will assume that

f

(i.I)

xnmdx < += ;

for all

n ~

I so that space

L2(I)

contains all the polynomials.

By othogonalization

of the family of monomials

{l,x,x 2 , . . . - } ,

we can obtain an orthonormal

family of polynomials

(Pn)ng~

such that

98

i) (1.2)

Pn e ~n

ii)

the coefficient

iii)

It Pn

is well

of

(Pn'Pm)m = ~nm

known

(cf.

satisfy a recurrence

(1.3)

where

(space of polynomials

e.g.,

xn

of degree ~ n)

i_.~n Pn

is strictly positive.

(orthonormality).

Davis-Rabinowitz

[7])

> 0.

the

polynomials

relation of the following type

XPn = anPn+ 1 + 8np n + 7nPn_l ,

a

that

It is also well

known

n ) I,

that the zeros of

Pn

separate

the

n

zeros of

Pn+l, and that the polynomial

In particular

(see (l.2)(ii))

i)

Pn

has

n

distinct roots on

I.

this yields

Pn(b) > 0,

n e

(1.4) ii)

Example and

i.i:

I = ]-i,+I[.

Pn(a)Pn+l(a)

< 0,

Chebyshev Polynomials. The Chebyshev polynomials

n e I%

In this case are defined by

t (cos B) = cos ne. n We now show that the

(1.5)

As

tn

satisfy the recurrence

2xt n = tn+ I + tn_ I.

relation

~ = (l-x2) - I~ ,

99

+I f f(x)m(xldx -1

(1,6)

we infer

= ~ 0

f(cos

8)d8,

that

+I t (x)t (x)~0(x)dx = f cos n8 cos m0 dS, n m 0

(t n, tin)m = -1

whence

(t n ,tin)~ = 0

Therefore

the

(tn)n~ ~

family

is

if

n = m = 0

if

n = m ~ 0 .

if

n # m.

orthogonal,

but

not

orthonormal.

We

then set

/V Pn = ~v/w~

tn

for

n > 1

for

n = O.

(1.7) I PO = - ~-

Thus n>

the recurrence

1 to = - -

relation

(1.5)

follows

as

an = Yn =i/2'

Bn = 0

2. We note

that

the change

of variable

u E L2(1)

by the f o r m u l a This

u(8)

to

x = cos 8

transforms

~ e L2(O,w),

= u(cos 8).

tr an sf or ma t i o n

is itself

isometric

since

according

to (1.6)

for

100

(1.8)

For

other

f

[u(0)[ 2 dO = f

0

I

examples

of orthogonal

]u(x)[ 2 o~(x)dx.

polynomials

(Legendre,

Jacobi, Hermite

Laguerre polynomials) we refer the reader to Davis and Rabinowitz [7].

2.

An I n t r o d u c t i o n

to

the

Numerical

Formulae of G a u s s , G a u s s -

Integration

Radau and G a u s s - L o b a t t o We return to the general case of an interval arbitrary

weight

function

orthogonal polynomial We

may

choose

m.

PN

some

We

denote

by

I

bounded or not with an

(Xj)l~j< N

the

roots

of

the

(of degree N). coefficients

(wj)1~j< N

such

that

the

numerical

integration formula

N

f f (x)to(x)dx =

(2.1)

I

is exact for

f e ~N-I

(the

wj

~ w.f(x.) j=l J J

are the solutions of the linear system

N

( x . ) k wj = f j=l

j

x k codx,

0<

k<

N-I,

I

whose matrix is invertible since the

xj

are all distinct; it is the Van Der

Monde matrix). We recall that as the order the

N, N

the formula

xj

(2.1)

point Gauss formula.

are the roots of the orthogonal polynomial of is in fact exact for

f e ~2N-I;

it is called

101

The Gauss-Radau polynomial

q

formula,

is defined

in terms

of the

defined by

q(x) = PN(a)PN+I(X)

which vanishes at • Let

of the (N+I) roots

t0 = a

- PN+I(a)PN(X),

x = a. and

(~j)I4j
then (N+I) coefficients

q; we determine

be the roots of polynomial

(mj)0<j
such that the formula

N

(2.2)

f f0Jdx = ~ ~ojf(~j ) I j=0

is exact for

f ~ ~N"

The formula point

(2.2) is actually exact for

Gauss-Radau

formula

another

Gauss-Radau

a

b

by

(associated

formula

in the definition

Gauss'Lobatto

with

associated of

formula, we use the

f ~ ~2N" It is called the (N+I) point

a).

with point

There

is,

in fact,

b, obtained by replacing

q.

Finally,

to obtain

the

N+I

roots of the polynomial

(N+I) q

point

defined by

q(x) = PN+I(X) + ~PN(X) + 8PN_I(X),

where

~

and

B

are determined by the condition test

q(a) = q(b) = 0.

Let

t 0 = a, (~j)I<j~N-I' ~N = b

be the roots of

q. N

In the usual fashion we determine the demanding that the formula

(N+I)

coefficients

(mj)O~j
by

102

N

f

(2.3)

f~dx =

be exact for

f ~ ~N"

~jf(~j)

Z

I

j=0

This formula is actually exact for

f c ~2N-I

and is

called the (N+I) point Gauss-Lobatto formula. Example 2.1: We

are going

Th e Case of the Chebyshev weight to make

explicit

the Gauss,

formulae for the case where the weight

~

~(x) = (l-x2) - I ~ •

Gauss-Radau

and Gauss-Lobatto

is given by

~(x) = (l-x2) -I/2.

The

corresponding

Radau-Chebyshev,

formulae

will

be

called

the Gauss-Chebyshev,

and the Gauss-Lobatto-Chebyshev

formulae.

the Gauss-

Let us begin with

the Gauss-Radau-Chebyshev formula. In

Part

A (see section

8) we have

seen

that

the numerical

integration

formula i

~-~

where

0j = j ~

~

f--x

g(0)d8

is exact for

Limiting attention to functions the linear combinations of

=

~

1

lJ

g ~ S2N. g

which are even in

8

(that is to say

(cos nS)0
N

]" g(0)d0 = 2N+l (g(00) + 2 ~ g(0~)), 0

is exact for all

g

j=l

o

of this form.

By the change of variable

x = cos 0

(see (1.6)), we deduce that

103

+i (2.4)

with

f

N f(x)~(x)dx = 2N+~ 1 (f(~0) + 2 ~ f(~j)) -i j=1

~j = cos 8j

is exact for

This is therefore point

f e ~2N"

the Gauss-Radau-Chebyshev

formula (associate d with the

+I).

(The Gauss-Radau-Chebyshev

formula

~. = -cos 8.). 3 ] To obtain the Gauss-Lobatto-Chebyshev

associated

with

the point

x = -i,

would be obtained with

formula, we start with the numerical

integration formula

1 z 2--~ /

with

N g(e )as = 1 ~ g(~j ) 2N j=-N+I

8j = j ~ , which is exact for Analogously

to the above,

g s S2N_I

we d e d u c e

that

+i (2.5)

/

f(x)~(x)dx = ~-~ ~ (f(~0) + 2

-i

with

~j = cos 8j, This

is

the

is exact for

the

(see Part A, Remark 8.3). formula

N-I 1 f(~j) + f(~N)), j=l

f e ~2N-I"

Gauss-Lobatto-Chebyshev

formula.

Finally,

to obtain

the

Gauss-Chebyshev formula, we remark that

--2zl/_~ g(e)d0 ~ 2NI

where

8j. is always given by

fractional for

values

g ~ S2N_I.

(j" + 1/2

N - 1/2 lJ'l=l/2g(ej')'

IT

0 "3 = j" N ' but where index

j"

takes only

being a positive or negative integer), is exact

104

In fact,

1

N-I/2

--

I

2N lJ';= i~

1

if

n = 0

0

if

0 < Inl < 2N .

-i

if

Inl = 2N

inS.. e

3

=

As in the preceding case, we conclude that the formula

+i (2.6)

f

f(x)~(x)dx = ~

-i xj = cos (j/ ~ 2I!~ ) ,

with

N ~if(xj),

j=

is exact for

f s P2N-I; this is the Gauss-Chebyshev

formula. Example

2.2:

Gauss-Radau

The Jacobi Weight.

We are going

formula in the case of Jacobi weight

to make

explicit

~(x) = (l+x~ I/2

the (This

formula will be used in section 4.) Let

g e ~2N-I

be given, and

f = (l+x)g e ~2N-I"

The Gauss-Lobatto-Chebyshev formula gives us

+I f

N-I

-I g(x)(l+x)(l-x2)-I/2dx = ~w

(In fact, ~N = -I, and thus

(2g(~o) + 2

[ (1+~j ~ )g(~j)) j=1

f(~N ) = 0).

We have thus shown that the formula

f

(2.7)

+i

l+x = ~ N-I g ( x ) ( ~ ) I/2dx ~ (g(1) + I (l+gj)g(gj)),

-i is

exact

for

g e IP2N_2.

j=1 This

is

the

N

point

Gauss-Radau

formula

a s s o c i a t e d w i t h t h e J a c o b i weight

'

(and a t t h e p o i n t

x = 1).

S i m i l a r l y , we show t h a t t h e formula

i s exact f o r

g

lP2N-2.

E

T h i s i s t h u s a Gauss-Radau

formula b u t a s s o c i a t e d

w i t h t h e weight

(and w i t h t h e p o i n t

x = -1).

We a r e now g o i n g t o c o n c e n t r a t e our e f f o r t s on t h e Chebyshev weight

-

W ( X )= (1-x 2 ) 112

.

For t h i s w e i g h t , t h e p o i n t s of numerical i n t e g r a t i o n f o r t h e Gauss-Lobatto and Gauss-Radau

formulae,

r o o t s of u n i t y of o r d e r

a r e t h e p r o j e c t i o n s on t h e r e a l a x i s of

M, where

M

the

M

i s an even o r odd i n t e g e r .

T h i s n i c e p r o p e r t y w i l l e n a b l e us t o u s e t h e F a s t F o u r i e r Transform t o compute t h e polynomial i n t e r p o l a n t of a g i v e n f u n c t i o n . Before going Canuto-Quarteroni

to

this,

we

shail

first

review some r e s u l t s

o b t a i n e d by

141 about t h e b e s t polynomial approximations of a f u n c t i o n

when u s i n g t h e Chebyshev weight.

106

3.

The Approximation o f a F u n c t i o n by Chebyshev P o l y n o m i a l s We restrict ourselves in this section to the case where the weight

~

is

projection

on

the Chebyshev weight m(x) = (l-x2) - i~

We shall frequently use the mapping

L2(1)

+

L2(-~,~)

u(x)

+

~(e) ~ u(cos 0).

(3.1)

From (1.7), we have

(3.2)

llull = 2Uull L2(-~ ,7 )

.

The above mapping is therefore continuous and one to one.

Proposition

the

subspace

3.1: ~N

Le__~t PN : L~(1) + ~N of polynomials

of degree

be the ortho~onal < N.

For all

u e L2(1)

we

have llU-PNUllm + O,

Proof: expand

~

Suppose

as

~(O) = u(cos 8).

From Part

in Fourier series

^

(3.3)

~(O) =

[ ng

u n e in0,

N + ~.

A (see

Section

3) we may

107

In particular,

let

(3.4)

~N(8) =

[ u n e ine Inl
,

then (see Section 3),

N

(3.5)

when

N

IIU-UNII 2 ÷ 0, L (-~ ,~)

N + ~. As (by definition)

u

is even in

8, we have

^

^

Un=U_

n ,

and (from (3.3) and the definition of Chebyshev polynomials)

^

^

~(8) = u 0 + 2

[ u n cos n0 n~ 1

^

U(X) = U 0 + 2 nll ~ t n < X ) "

Thus, from (3.4) we have

^

N

UN(X ) = u 0 + 2 n~ 1 Untn(X),

therefore

u N = PN u

scalar product

(.,-)m

since

the Chebyshev

(see Section i).

polynomials

are orthogonal

for the

108

Finally,

with

(3.5) and (3.2) we have

llU-PNUll~ ~ IlU-UNIim = ~1 II~_]NIIL2(_~,~) + 0,

as

N ÷ =. Q.E.D.

We are now going to establish

the error estimate

for the quantity

llU-PNUllm • To do that, we introduce

the family of weighted

2 (1)' Hmm(1) : { u : u (c~) e L m

where sense.

u (e)

denotes

The space

the derivative

H m(I)

is a Hilbert

m,m

We will use the following

0 < 8 < ~

Proof: x = ~(O),

from

In general, and

~

is a

of

u

in the distribution

16 ,,u(~),,~)

~=0

u + u Hm(1)

defined by to

](e) = U(COS e)

if we make a change of variable C

function.

for

Hm(0,~).

Let

u(e) = u(~(e)), then

~

result.

The mapping

is continuous

c~ : O , . . . , m } .

space for the norm

m ~ ( [

,u,

Theorem 3.1:

of order

Sobolev spaces

x + 0,

where

109

°Iu(=)(~(o)) I

Iu~°~ where

C

c X

,

c~=O

is a positive constant depending only on

the particular case where

~

and

m.

We deduce in

~(0) = cos e, that

; lu~o~o~ ~ do < o ~ s lu~o~l~ 0

~(x)dx,

a=0 1

and this yields the desired result. Q.E.D.

Remark

3.1:

isomorphism from

The

mapping

L2(1)

onto

However, the image of

u + ~ L2(0,g)

Hm(1)

defined

in

Theorem

3.1

is not the space

Hm(0,~)

for

m ~ 0, but a

For example, the space

X = {u : (l-x 2) l~u. s L2(1), (l-x 2) - l ~ u

e L2(1)}

(which contains strictly the space:

HI(1) = {u : (l-x 2) - 14u" ~ L2(1),(l-x 2) - 14u ~ L2(1)})

HI(o,~).-

In fact, the change of variable formula

f

(~/l_x 2 lU.[2 + . 1 I

~/1-X

2

an

(and it is also isometric).

smaller space.

has for its image

is

lui2)dx = f~ ([~.[2 + [~[2)dO, 0

110

shows that the mapping

Theorem 3.2: -~ ~ 0 ( ~,

u ÷ ~

is an isometry from

The mapping

u + ~

defined by

is continuous from

Hm(1)

into

the periodic Sobolev space of order

Proof:

The

function

even;

consequently,

tives

of odd order are odd.

the restriction of ]-~,0[

is in

u

m

~

to

is in

HI(0,~).

~(0) ~ u(cos 0)

H~(-~,~)

(where

by

~(O) E u(cos O)

of even order are even,

According

]0,7[

onto

for

Hp(-~,~)m

is

defined in Part A, Section 6).

defined

its derivatives

X

to Theorem 3.1, if

is

obviously

and its derivau ~ Hm(I),

then

Hm(0,~); likewise, its restriction to

Hm(-~,0). m u e Hp(-~,~), it suffices that all its derivatives of order

In order that

less than or equal to m-i be continuous and periodic (of period 2~); as

~

is even,

necessary at

8 = 0

this is clearly true for its even order derivatives.

however and

~(8) ~ cos 8

to verify

0 = ~. are zero for

that its

odd order

derivatives

(< m-i)

It is vanish

This follows from the fact that the derivatives of 8 = 0

and

8 = ±~.

In fact, we have for example

u'(0) = -sin 0u'(cos 0)

u'''(0) = -sin 3 0 u'''(cos 0) + 3 sin 0 cos 0 u"(cos 0) + sin e u'(cos 8),

which shows that if

u e Hm(1)

with

~'(0)

m> 2, then

= ~'(~)

= 0,

111

and that if

u ~

Hm(1)

with

m

~

we have in addition

4,

W

~'"(0)

and the result follows for

= ~'-'(,~)

= o,

0 ~ m ~ 5.

The proof of the general case is left to the reader. Q. E. D

Remark definition

3.2:

We

of spaces

refer

the

HS(1), s

reader

to

noninteger,

Canuto-Quarteroni

[4]

for

and for a generalization

the

of the

W

preceding real

theorems

to the case where

the integer

m

is replaced by positive

s.

Theorem 3 . 3 :

Let

s > 0

be given.

There exists a constant

C

such

that llU-PNUllm < CN -s Ilull

for all

S,~O

u e HS(1).

Proof:

Let

uN - P N U , ~ ( O )

= UN(COS 0)

and

u(e) = u(cos 0).

From

(3.2), we have IIU-PNUlI~ = IIU-UNII~ = ~1 l'u-uN,,L 2 (-~,~)

Now,

(see

the proof

of Proposition

3.1), u N

N

Fourier series of

u

truncated to order

N.

happens

to be equal to the

112

According to Theorem 6.1 of Part A, we have therefore

"u-uNto 2 L (-~ ,~)

c N -s s Hp(-~ ,7)

On the other hand, Theorem 3.2 (I) yields

lieu

~ C R u~ H~(-~ ,~)

HS(1)

which proves the result. Q.E.D.

We will between We

u

now establish

an estimate

for

and its projection on the subspaee

introduce

the

following

convention;

01U-PNUUo,m ~N if

which

in the norm of (bn) n ~ IN

sequence, we denote by

n

def

£=m

where

[~]

[~] £ "=0

denotes the integer part of any real number

We define also the sequence

(Ck)keiN

by

2

if

1

otherwise

k = 0

ck =

(I)

in the case of nonlntegers

is the error

s, see the Remark 3.2.

~.

H°(I). denotes

any

113

this will simplify the presentation

Lemma 3.1 :

Let

u g ]PN

of results.

be a polynomial

of degree

N

and

N u =

be its expansion

in Chebyshev

Z

a k tk

k=O

polynomials.

Then its derivative

by

N u" =

~

bk tk

k=0

where 2 bk - Ck

Proof:

N

[ " £a£ £=k+l

The following formulae are easily confirmed

tO = tl

t

=

n

1 ftn+l 2 ' ~

tn-i n-i ") '

for

n ) I.

We have then

u" =

Thus

N N t~+ 1 Z bkt k = bot" I + 1/2 I be( k+l k=O k=l

tk'-i .)° k-1

u"

is $1ven

114

N

u" =

[ akt ~ k=O

•

The following formulae follow

b2 b0 --~=

aI

1 2--n (bn-I - bn+l) = an'

2~n~

N-2

bN- 2 2 (N-I) = aN-I

bN- 1 2N = aN-2 '

whence

the result,

solving this system of equations

(upper triangular matrix)

by substitution. Q. E. D.

Le--.~ constant

3.2

C

(3.6)

and for all

Proof:

(Inverse Inequality):

Let

s > 0

be give n.

There exists a

such that:

HU{{s,m

CN 2s }{uN ,

for all

u e ~N,

N > 0.

Let us begin by establishing

we have N

u =

~ akt k k=O

the result for

s = i.

Let u e ]PN;

115

and

N u" =

~ bkt k , k=0

wi th 2 bk - Ck

from Lemma 3.1.

N~

" ~a£ , %=k+l

Noting that:

(tn'tm)m

Cn ~ ~nm '

(see Section I, example I.I) we obtain N N "u'"0~2 = --~2 ~ Ck Ibk 12 = ~ ~ 2 k=0 k=0 ~k

~" £ =k+ 1

~a~

2

•

Now, the Schwarz inequality yields

I N

~a£

12 ~

~=k+l

( N ~ £2)( N I la~I2) ~ ~=k+l ~=k+l

N3 N~ ~=0

la~[2 ~ CN3 'u'2 • m

We deduce Ifu'll2 < CN 4 ilull2

whence the result for A

repeated

positive integer

s = I.

application

of

this

theorem

s.

the

result

for

any

s.

We refer the reader to Canuto-Quarteroni noninteger

furnishes

[4] for a proof in the case of

116

Q.E.D.

Remark

3.2:

In

inequality

(3.6)

the

exponent

of

N

is

optimal

(although worse than that obtained in the case of Fourier

series, see Part A,

Proposition

[4],

polynomials

8.1).

In

of degree N

fact,

(see

Canuto-Quarteroni

we

may

find

such that

IIPNIIm,~

N2m .

IIPN[Im

We

present

constitutes

the

following

result

(prove

in Canuto-Quarteroni,

[4]) which

an extension of Lemma 3.1.

Proposition 3.2:

Let

u

be a sufficiently regular function such that

u =

~ akt k , k=0

then we have u" =

~ bkt k k=0

wi th 2 ~" ~ag • bk = c-~ g=k+l

In order to estimate

the error between

u

and

is necessary to estimate

ilu" - (PNU)'II

•

PN u

in the space

HI(1),- it

117

Now, PN u"

contrary

to the case of Fourier

are not identical

N-I, and

PN u"

(note that

is a polynomial

series

(PNU)"

(Part A), here

is a polynomial

of degree

of degree

N).

We then begin by estimating

llPNU" - (PNU)'II

Lem~a

3.3:

Suppose

u ~ HS(1)

then we have the inequalitY

IIPNU" - (PNU)'II < cN-S+ 3/2 IIu IIS,60

Proof:

Let qN = PN u" - (PN u)''

u =

~ a kt k , k>0

u" =

~ bkt k. k>0

From Lemma 3.1, we have 2 bk - Ck

Similarly

~" £a£. £=k+l

as N

PN u = we have

~ akt k , k=0

(PNU)"

and

118

N

(PNU)" =

~ b Nk tk k=0

wi th N

N=2__ bk

Ck

[ £a£. £=k+l

We deduce that N

qN

k[0 Yk tk '

with

m S

N

2

~k = bk - bk = ~

[

I £'=0

(k+2£'+l)ak+2£.+l

(k+2£'+l)ak+2£-+l],

£'=0

where

m

n-k-I 2

if

N-k

is odd

n-k-2 2

if

N-k

is even

=

Therefore (k+2£'+ i )ak+2£.+ i.

CkY k = 2 ~,'=m'+l

That is to say

co

2

I" ~a£ - bN+ 1 £=N

if

N-k

is odd

if

N-k

is even

Ck Yk = 2

[" Za £~ b N £=N+I

We have then demonstrated that if

N

is even

119

I qN = ~ bN to + bN+l tl + bN t2 + .... + bNtN '

and if

N

is odd

1 qN = ~ bN+l to + bN tl + bN+l t2 + .... + bN tN'

that is to say

qN =

N N bN dP0 + bN+l ~I

if

N N bN ~i + bN+l ~0

otherwise

N

even

where N ~0 =

As the functions

N dp0

and

N I" ~=0

N ~I

1 ~

N t~, = I" ~=i ~i N

t~

are orthogonal, we have

if

N

even

if

N

odd

ilqNII2 =

Now, from Theorem 3.3, we have

flu" - PN-I u'ilm ~ C(N-I)I-s llu'lls-I ~ CNI-S liuils.

Since u" - PN-IU" =

~ bn tn, n~N

120

we have established

that

Jbnl < CNI-S llUlls

Finally,

forall

n > N.

as ,

we deduce

that

ilull2

2 < CN3-2s

IIqNllm

s Q.E.D.

Corollary

3.1:

exists a constant

For C

all

p

and

o

such

Lemmas

3.2

and

to the case where

Theorem constant

ilullcf,o~

u e H°(I).

(Apply extended

0 4 p ~ o-1, there

such that

lipNu. _ (PNU).llp, m ~ cN2P-O+ 3/2

for all

that

C

3.4:

For

3.3. p

Following

and

all

o

~

Remark

3.2,

- PNUll

result

may

be

exists

a

are real.)

and

o

0 < ~ ( o, there

such that

Ilu

this

< ON e(~'°)

llullo.,~°

121

for all

u e Ho(1), where

2~ - o

-I/2

for

~ > 1

for

0 < p < 1

e(~,o) = 3

Proof:

~ - ~

(We restrict ourselves

is obviously true for = 0,..-,m-l.

~ = 0.

to the case of integer

~).

The result

Suppose by induction that it is so for all

From the relation

ilvlf 2 = uv(m)fl2 m~,6o

which is true for all

+ Iiv[12_l,

~ IIv'l; 2 , + Uvll2m 1 m - i ,60 - ,60

v e Hm(1), we get, using the induction hypothesis

2 Uu - PNUIlm,60

m+ CN2e(m-l'°) ilu" - (PNU)'II 1,60

Now using once again the induction hypothesis,

Ilu" - (PN u)'llm_l,~ < Ilu" -

PNU'II m

fluil2

o,m "

and Lemma 3.3 we get

+ IIPNU" - (PNU)'IIm_I, m

CNe(m-l'~-l)rlu'lio_l,m + CN2(m-I)-o+

3/2 lluli

we deduce

;lu - PNUflm,m ~ C[(Ne(m-l'°-l)+

N 2(m-l)-°+ 3/2)2 + N2e(m-l,o)] 1/2 l]uFIa,~

122

CNe(m'a)11 uU

(In

fact

e(m-l,o-l)

and

e(m-l,o)

are

bounded

by

e(m,o);

for

m > I.)

the

dominant

term is then the second term

N2(mml)-a+ 3/2 = Ne(m,o)

Q.E.D.

Remark 3.4:

The exponent

N

in the upper bound found for flu - PNUl; ,m

cannot be improved; we refer to Canuto-Quarteroni

4.

[4], for counter examples.

Approximation by the Interpolatlon Operator In the previous section, we have established error estimates for

where

PN

This

is the projection operator of result

does not

suffice

L2(1)

u - PN u,

on ~ .

in applications

where

boundary

conditions

must be taken into account. As in the case of Fourier series (see Part A, Section 8) it is necessary to define an interpolation operator

Pc : c°(T)

+ mN

defined by 0<

(Pcu)(yj) = u(yj)

where

(Yj)o<j~N

are

(N+I)

distinct

points

of

j ~ N,

the

interval

I.

The

123

operator

PC

is thus defined in a unique fashion

(Lagrange interpolation).

We consider first the case where

Yj

that

is

points

to

say,

we

use

as

(see Example 2.1).

=

~j

-

2j~ COS 2N+l

interpolation

'

points

the

Gauss-Radau-Chebyshev

Introducing again the change of variable

X = COS 0 U(X)

+

~(0)

We note that the operator PC

: C~(-~,~)

+

SN

PC

with

~(0) E U(COS 0).

is related to the interpolation

operator

defined by

N

(Pcu)(0j) = u(e.) J

(with

0j ~ ~ ' ~ )

lJ[ 4 N,

and which has been studied

(under another name) in Par t A

(see Section 8). More precisely,

Theorem 4.1: exists a constant

we have

Let C

s > I~

and

o

be given such that

0 < o < s.

such that

IIU-PcU]I°

~ C N 2°-s llu]1 ~0J

S~L0 ~

for all

u ~ HS(1). 0~

There

124

Proof:

Let us begin by establishing the result for

a = O.

Setting

u(8) = u(eos 8), we have (see Theorem 3.2)

I1~11 ,

~(_~,~)

From Part A (Theorem 9.1), we have for

~;

C II ull

s >

s,~

1

IIU-PcUll 2 ~ C N-Sllufl L (-~ ,I~) s Hp(-~,x)

whence

1

For

N

~

N

IIU-PcUlI0,m = ~ llU-PcUll 2 ~ C N -s Ilull L (-~ ,.~)

(4.1)

S,(0

a > 0, we note that, according to inverse inequality (Lemma 3.2)

ilu-PcUlla,~

< UU-PNUlla, m + C N2olIPNU-PcuIi0, ~

The conclusion follows from Theorem 3.4 and the inequality (4.1). Q.E.D.

Remark PC

4.1:

We note that the approximation

are weaker than those of

denote the norm

cO(l)

PN, at least when

defined by

tlull = max Iu(x) I, xgl

properties

a > O.

of the operator

Actually, let

l;.tl

125

it is well known (see e.g., Rivlin [15]) that

flu - PC ullo= g (I + AN) II.u - P N

where

AN

uH°~ '

is called the Lebesque constant.

Actually Brutman [3] has proved that

AN

grows like

log N.

If the interpolation points were chosen in an arbitrary way the growth of the Lebesque points

AN

not

using

of

PC u

constant

AN

could be much worse.

grows exponentially fast. T h i s equally

spaced

poCnts,

another

In fact for equally spaced

is, of course, one good reason for reason being

that

the computation

is ill-conditloned for such points.

Remark 4.2:

Theorem 4.1 is established when the interpolation points

are those of Gauss-Radau-Chebyshev formula associated with the point

yj

x = I.

We have an analogous result in the case where the interpolation points are those

of

(change

Gauss-Radau-Chebyshev x

to

formula

associated with

the

point

x = -I

-x).

Let us consider now the case where the interpolation points are those of Gauss-Lobatto-Chebyshev formula.

J" , = cos---~

yj

Suppose

~C

j = 0,..-,N.

is the interpolation operator

C0(W)

+ ~N

(defined by

(~cU)(~j) = u(~j)), we have the following result.

Theorem 4.2: exists a constant

Let C

s >

I~

such that

and

o

be $iven such that

0 g G g s.

There

126

llU-~cUll

for all

The Theorem

,m

~

C N2 ° - s

Ilull

u e HS(I).

proof

of this

4.1 because

variable

x ÷ 0

result

the image

is in every

respect

of the operator

is an interpolation

analogous

~C

under

to the proof

the change

of

of the

operator which has already been studied

in Part A (see Remark 8.3 and formula (8.20)).

5.

The Solution

of

the Advection

Equation

We consider the advection equation in the interval

(5.1)

Unlike

i)

~u+ ~--~ a(x)~u ~x =

ii)

u(-l,t) = g(t)

, t > 0,

iii)

U(x,O) = Uo(X)

, x 8 I.

0

I = ]-I,+I[

, x e I, t > 0.

the problem studied in Part A (see Sections 7 and 9) the boundary

conditions are not periodic. We suppose that coefficient

a c C=(T)

is strictly positive in

T.

We consider for simplicity the case of a homogeneous boundary condition (g(t) E 0).

127

We are going to approximate the problem (5.1) using a collocation method which we now describe.

Let

UN = {P s ~N : p(-1) = 0}.

and let

(xj)j=l,..., N

be

N

given points in the interval

The approximate problem will then be the following

I.

Find

UN(t) s ~N such

that

(5.2)

where

i)

Du N Du N (~-f- + a ~--f-) (xj) = 0

, j

ii)

uN(-l,t) = 0

, t ~ 0

iii)

UN(X,0) = U0N(X),

, x s I,

U0N e U N

=

I,...,N,

t

> 0.

will be fixed subsequently.

The essential problem which is posed is the following How does stable?

(In

one

choose

other

the collocation points

words,

so

that

the

uN

xj of

so that the method is the

system

of

ordinary

differential equations will not grow exponentially.) Numerical experimentation shows that the correct choice of the collocation points is crucial to the success of the method.

Method A:

(See Gottlieb [8].)

We first study the points

128

(5.3)

xj

-cos N+I '

J = I,...,N

(which are used both by the (N+2)-point Gauss-Lobatto-Chebyshev formula and by the (N+l)-point Gauss-Radau formula for weight

1-x I/2 ~i - (TW)

and associated with point

Theorem 5.]:

With

x

= I, (see Section 2).

the choice (5.3) for the collocation points, we have

the stability for the discrete norm

II-IIN

associated with the discrete scalar

product =

N

~j

(u'v)N j~0 ~

u(xj)v(xj),

where x 0 = -I,

~0 = N+I

and

~j = (l-xj) ~

.

That is to say, we have

IUN(t)II2N

Proof:

(5.4)

~

~UN(0)" 2 ,

for all

t > 0.

According to (5.2), we have

8 uN 8 uN 8t (xj) + a(xj) ~ (xj) = 0,

We have seen (2.8) that the formula

J = I,-..,N.

129

N

(5.5)

~- X ~j g (xj), j=0

g(x)~ l(X)dx I

(where

l-x 1~

~l(X) = (~x)

)

was exact for

g e ~2N

(this is a (N+l)-point

Gauss-Radau formula. Multlplying (5.4):by UN(X0) = 0

~j U~I~I ))

and summing, we obtain (by noting that

according to (5.2ii)) N m. 8uN N [ 3 uN(x j ) ) + [ j--0 x--~j) a 8--{--(xj j=0

8u N

~j UN(Xj ) ~

(xj) = 0,

that is, to say

(5.6)

8uN (UN, t ~ ) N

+

8u N f UN x ~ m I

Now, integrating by parts (and noting that

I dx = 0.

UN(-l) = 0

and

ml(1) = 0)

SUN 8 flUN ~--x--ml dx = -~i UN ~x (mlUN)dX

whence SUN 2 m: dx 2 / uN ~ m l dx = -f uN I I

0.

Returning to (5.6), we see that

1 d llUN(t)ll~ 2 at =

~UN (UN' ~--~-)N <

0,

which proves the result. Q.E.D.

130

Remark

5.1:

Suppose

~

and

C

are

such

that

0 < ~ ~ a(x) ~ C.

According to (5.5), we have

N

(5.7)

~-livNli

<

llVNH2

-

1

for all

v N e PN"

0~.

a(xJj) [VN(Xj)[ 2

~

I

~-llVNll21 ,

j=0

Therefore, from Theorem 5.1 we get that for all

llUN(t)ii21

which means stability in

<

C.lUN(t)il2

<

t > 0

+ ~,

L2 .

We will show later that method A is easily implemented using Fast Fourier Transforms

(see Section 7).

Remark 5.2: Let constant.

us

Choice of the Weight

consider

the

particular

ml case

when

the

coefficient

The exact solution of problem (5.1) is then

u(x,t) = u0(x-at) ,

so that we may have

Tlu(t)ll i

only if

~I

<

flu011 1 ,

for

is decreasing.

We note that this is what happens in Method A if

t > 0,

a

is

a

131

i-xi~

~i~(i-V~)

This

explains

why we

the Chebyshev weight

Theorem 5.2: if

cannot

for the norm associated

for

~ > ! ~ , s > 2(i+o)

0 ~ t ~ T, there exists

flu(t) - UN(t)ll 1

for all

stability

with

m = (l_x2)_ i~ •

Suppose

u(t) e HS(1)

have

•

<

and

T > 0

C > 0

are $iven.

Then

such that

C N 2(l-°)-s + ;IU0N - u011 i

t < T.

Proof:

Let

Radau-Chebyshev PC : C0(T)

~ j = -cos N--~72 J~ '

j=0,...,N,

formula associated with point

+ ~N

be

the interpolation

be the

N+I

points of Gauss-

x = $0 = -i.

operator

Let

associated

with

these

(N+I)

points.

Let

~(t)

According

= Pcu(t), where

to Theorem 4.1, we have

(5.8)

where

Uu(t) - UN(t)ll ~

m(x) z (l-x2) - I ~

from the fact that Setting

is

the

u

is

~(-1,t)

~0 1

~

z(t) = (u - ~N)(t),

solution

= u(-l,t) = 0

of

problem

(5.1).

(5.8)

follows

and

C N 2~-s llu(t)ll s~0~

Chebyshev

~l(X) < ~(x), for all

the

weight. x s I.)

(Equation

132

8~N

(5.9)

~t

~qN

+ a(x) Fx

In particular, setting

the

equation

WN(t) = (uN - UN)(t)

~WN (~r

Multiplying by

8z + a(x) 8z ~x '

xe

- ~t

(5.9) is

true for

x = x., j=I,..-,N, so 3

we have

~WN

~z

+ a -~x)(~j)

= ('~ + a

~-~)(xj).

WN(X j ) mj aN(xj) and summing up from

~WN 8z + fl WN ~--x-~l dx = (-~-~,WN) N +

8WN (WN' ~ ) N

I, t ) 0.

j = 0

to

N

N ~z ~ ~j Yx (xj) WN(Xj) ,

j=0

whence

HW NIIN

~-{

~wN

=

3z

(jN

,,w~,,N +

8z

Upon simplification

~z

ddt IIWN(t)IIN ~ fl~-{llN+

and using the fact that

-d-

dt

Now, we have for

o >1/2

c( N

X

j=0

~z

mj I ~x (xj)l2)

0 < a (a(x) < C

tlWN(t)iI N

<

C I ll~-{ll~Z+

n

i~,l

i/2

))2 ).

133

av~

<

UvI

L==(I )

whence for

z = u-

gv]~

.

o,m

0 >'1/2

d HWN(t)NN d'-{

As

';

Ho(1)

~z ,m + ll~l o ,m) " < C [J-~ll

uN(t) , we have

<

~)x o,c0

IIz!

1+o ,~

< C N 2(l+a)-s

llu(t)U • s

~Slnde ~z =

~u ~'{ -

~u PN ~-6 '

we have ~z

C N2 ° - ( s - l )

I[~t o ,oJ

(where we have used equation

Finally,

i~u~ I~-~. s-I

C N 2o+l-s

Uu(t)~

(5.1i)).

we have

d

IIWN(t)~ N

<

C N 2(l+a)-s

llu(t)l s,~

so integrating

between

0

and

t

t gWN(t)N N < ,WN(O)H N + C N 2(l+°)-s f

Uu(t)U 0

s~

134

According to (5.7), we have for

t < T

C ~ ~ llWN(0)lim

ilWN(t)II~ 1

+ C

N2(l+a)-s

1

Now,

(5.10)

;;WN(0)I; I = llU0N-Pcu01iml < llU0N-u01i~l + liu0-PcU011m

llU0N-u0il i + C N-Sflu01fs,m ,

whence liWN(t)IIml < C llU0N-U01; 1 + C N 2(l+°)-s

To conclude, we note that

llu(t)-UN(t)I1 1 < llu(t)-UN(t)II 1 + liWN(t)l; i

and that flu(t) -UN(t)fl

~ C N -s llu(t)ll

g

Q.E .D.

Remark 5.3: i.

We may choose U0N = PcU0 .

In this case (see (5.10)), WN(0 ) = 0

in the preceding discussion so that

135

we obtain directly

(5.11)

flu(t) - uN(t)Jl ~

<

C N 2(l+a)-s

1

(Of course, other choices are possible.) 2. to

The result established

u(t)

solutions

has

a known

(at least

in Theorem 5.2 shows the convergence

rate

when

C2); however,

s > 3,

of

that is to say for very

UN(t) regular

it might not be optimal.

Method B We now consider collocation

(5.12)

x.J = - c o s

The point

xj

are the points

points

~ J~

,

j=0,--.,N.

of Gauss-Radau-Chebyshev

x = -I (see Example 2.1).

The numerical

formula associated with

integration

formula

M

(5.13)

f

f(x) m(x) dx I

is then exact for

~

~ ~jf(xj), j=0

f e ]P2N' with

27

~. l 2N+I '

(See

=

j=I,...,N

and

(2.4).)

This means that (choosing

g = (l-x)f) the formula

~0 - 2N+I"

136

N

(5.14)

f

g(x)ml(X)dx

X mjg(xj ), j=0

=

I

where

mj = (l-xj)~j , is exact for

Theorem 5.3: stability for

g e ]P2N-I"

With the choice (5.12) f_or the collocation points, we have

the discrete norm

ll.IIN

associated

with the discrete

scalar

product N m. j=0 a-~J) u(xj)v(xj ),

(u,v) N

that is to say ilUN(t)llN

<

IIUN(O)IIN,

Du N Du N [~-- + a ~--~)(xj) = 0,

Multiplying by =

t > O.

According to (5.2) we have

Proof:

UN(X 0)

for all

~j UN(Xj) a(xj)

j = l~...,N.

and summing for

j=l ...,N, we obtain (noting that

0)

N

~0j

Du N

[ a-UfTY uN(xj) ~ j=0 j

N

Du N

(xj) + ~ ~jUN(X j) x~-- (xj) = 0, j=0

i.e., (see (5.14))

~uN

~u N

(~N, t~T-IN÷ f UNx~--~1 dx--0,

137

and the result follows in the same fashion as in Theorem 5.1. Q.E.D.

We leave it to the reader to establish for these collocation points the error estimate analogous to Theorem 5.2., i.e.,

liu(t) - UN(t)liN

< C N 2(l+~)-s.

But here, as the formula is only exact for

g e ~2N-I, we do not have the

analogue of (5.7), and we cannot replace the discrete norm

II.II N

by the norm

li,ll

6.

Time D i s e r e t i z a t i ~

Following reasons

Schemes

the analysis of Part A (Part A, Section I0) we would like for

of efficiency to use

some explicit

discretization schemes in time.

These allow us to benefit from the Fast Fourier Transform. the general case where the collocation points

The Choice of a Basis for Suppose

(6.1)

(The

(~k)k=l,..., N

xj

We consider first

are arbitrary.

UN is the basis in

UN

defined by

~k(Xj ) = ~jk"

~k

are the Lagrange polynomials.)

For any

v ~ UN, we have

138

N

v(x) =

~ Zk~k(X), k=l

with

zk = V(Xk).

Setting N

UN(X,t ) =

where

uN

~ Yk(t)~k(X); k=l

is the solution to the approximate problem (5.2), we have

N

dyk ~ *k(Xj ) +

k=l

N a(xj )~(xj )Yk = 0, k=l

i.e.~ d_~y+ Ay = 0, dt

where

A

is the

N×N

matrix the coefficients of the form

j, k=l,.°.,N.

a(xj )~(xj ),

We wish to study some properties of the eigenvalues of matrix s Sp(A), we have Ay = ly,

i.e., N

N

a(x.)3 k~l= ~k(Xj )yk = iyj = k=l ~ ~k(xj)Yk'

and setting N

uN = k~ I Yk~k (x)

s

U N,

A.

Suppose

139

we obtain

3u N a(xj) ~ (xj) = 1 UN(Xj).

(6.2)

Finally, complex

multiplying

valued--recall

obtain (noting that

by that

a(~j) UN(Xj) uN

(in general

denotes

the

complex

I e ~

and

conjugate

of

uN

is

u N)

we

UN(X0) = 0)

N

Du N __ N ~o. (x) U N ) = I X a(xj) J %.(xj) -u N (xj ). mj ~ j =0 3 (xj j=0

Now, we notice

that when the

xj

are defined as in method A, the left-hand

side is an exact numerical integration formula so that

DUN__ UN

f ml ~x

= lllUN[l~ .

dx

I

Now, using integration by parts we see that

2 Re f

~

u N __ u N ~I dx = - f

I

fUN !2 oJI dx > O. I

We deduce

(6.3)

Re(1) > 0.

In the case where the then holds.

the numerical Furthermore,

xj

integration

are the Gauss-Radau-Chebyshev formula

is

also

we can get an upper bound for

according to (6.2), we have

exact,

points (method B)

so that

Ill. Let

(6.3)

I e Sp(A),

still

140

N

M

~u N

__

N

m

(xj) uN (xj) = ~ j=0 X

j=0 ~k ~

J uN(xj ) ~NN (xj),

~

where we use this time the true weight of Gauss-Radau-Chebyshev

formula (see

(5.13)). We have then (using the fact that

fI ~

uN ~o dx

a(x)

!

is bounded)

1

I%

~

fl fuN

12

to dx

and so ~u N

il-~--xII

Ix l

(6.4)

< CN 2 ,

IIu NII

from the inverse inequality established in Lemma 3.2. In

practice

problem

(5.2)

is solved using

explicit

Run~e-Kutta

schemes

(see Part A, Section I0). Condition

(6.3)

ensures

the

stability

of

the

order

4

scheme

method

using

the

for

a

sufficiently small time step. The

condition

(6.4),

obtained

for

the

Gauss-Radau-

Chebyshev points, shows that it is stable for

At

Remark Fourier

6.1:

series

limitation

in

Result (see time

Part step.

(6.4) A,

<

is

C N

less

Proposition This

affects

especially if resolution requires a large

-2

.

favorable

than

10.2)

leads

the N.

and

efficiency

that

obtained

to a more of

the

for

severe

method

in

141

7.

The Use of the Fast Fourier Transform In order

limitations

to use

the

explicit

schemes

advantageously

on the time step due to stability)

very rapidly the product of the matrix a column vector

y

with

N

A

(given

it is necessary

the

severe

to calculate

defined in the preceding section by

components.

Let us begin by considering the Gauss-Radau-Chebyshevpoints.

Let

be given.

y = (Yk)k=l,...,N Setting

N

UN(X) =

~ Yk ~k (x)" k=l

We have by definition ~u N (Ay)j = a(xj) ~ (xj).

In

the

coefficients

first

stage we use

(an)n=0,..., N

the Fast

Fourier

in the expansion of

Transform uN

to calculate

the

in Chebyshev polynomials

N

UN(X ) =

(This is possible because the

(x.) 3 j=0,...,N

projections on the real axis of In the second the coefficient

bn

stage,

~ an tn(X). n=0

2N+I

fixed by (5.2) are precisely the

roots of unity.

we use the formula given by Lemma 3.i to determine

in the expansion of

~u N ~

in Chebyshev polynomials.

In the third stage we again use the Fast Fourier Transform (actually, its 8u N inverse) to calculate from bn the values ~ (xj) at the collocation points The

xj. calculation

in this

fashion

requires

0(N

log 2 N)

operations

and

142

multiplications

(instead

elements of matrix

of

0(N 2)

operations

if we directly

calculate

the

A).

Method A We

shall

see

that

for

Transform to evaluate

return

to

points

Ay, for given

subtle (see Gottlieb, We

these

y

we

may

still

use

the Fast

Fourier

being known, but the argument is more

[8]).

the

choice

(5.3)

of

the

collocation

points

xj.

The

following result is fundamental.

Proposition 7.1:

Let

(xj)j=0,...

X~

=

N+ 1

j~ COS ~-~

be given by

•

J

Suppose

u s IPN

is given.

We have

N

U(X) =

[ a t (x), n= 0 n n

wi th an

where

the

=

dn

+

(dn)n=O,...,N+ 1

Chebyshev polynomials

of

2 ( l)N+n ~-- dN+ 1 , n

are

v s IPN+1

v(xj) = u(xj), (7.1)

the

n=0~...,N,

expansion

coefficients

such that

j=0,...,N-I

in

terms

of

143

V(XN+l)

= 0

and y n

Before

proving

polynomial

u ~ ~N

j=0,..o,n

we

an .

N+2

projections To

this

(In fact,

v s ~N+I

equals

0

at

of

1

for

1 ~ n ~ N.

result,

directly the

this

polynomial

expansion

n = 0

or

N+I

let us first

explain

how we use it.

by its values at the points

use

the

Fast

(xj)j=0,..,, N

Fourier

constitute

Transform

only

v

difficulty, which

N+2 nd

we

coincides point

in Chebyshev

will

calculate

to

N+I

with

XN+ I.

u

at

Thus,

polynomials

the

calculate

of the needed 2N+2).

coefficients

(xj)j=O,..., N

the coefficients

will

As the

xj,

on the real axis of the roots of unity of order

circumvent

to

for

is determined

cannot

the

2 E

be calculable

of

a

and which dn

using

of the the Fast

Fourier Transform. Now,

it

7.1) between

turns the

out ak

that

there

and the

Let

i 2N+2

(The verification

~

n=-N

(given by Proposition

7.1, we need the two following

be such that

N+I ~

relation

d k.

In order to prove Proposition

Lemma 7.1:

is a simple

n

~

2N+2

= i, then

1

if

m = 1

0

otherwise

of this lemma is left to the reader.)

results:

144

Lem.~ 7.2:

We have

N+I

I n=O q1 (-1)n tn(Xj) = 0,

(where the

~n

for

j=O,...,N,

are defined in Proposition 7.1.)

Proof:

According

N+i

to Lemma 7.1 (applied with

m

eik ~---~N+I),

we have

ink N+I e

= 0,

for

I ~ k ~ 2N+I.

n=-N

Let us set

k = N+j+I, with

ink N+--~ ~ e

j=0,..-,N;

in ~N+j+I ~ = e

= e

we have

in~ in ~ e

j~ in N+I = (-I) n e

,

whence N+I

in (-11 n e

J~ N+I

= 0.

n=-N

Taking the real part of this relation, we obtain

0 =

N+I

nj~ (-l)n e°s N--~ = 2

n=-N

N+I N+I (-l)___~n ~ (_l)n tn(Xj ), ~ ~n c°s nJ N--~ = 2 ~ ¥----~ n=0 n=0

which is the desired result. Q.E.D.

Proof of Proposition (dn)n=0,...,N+ I

7.1:

Let

v ~ PN+I

be its Chebyshev coefficients.

satisfy (7.1) and From Lemma 7.2, we have

145

v(xj) =

N ~ d tn(Xj) + ~ + I n= 0 n

tN+l(Xj)

N+I + (-i) N 2dN+l[ ~ n=0

for

1 )n tn(Xj)], ~-- (-I n

j=0,-..,N, i.e.,

N N v(x.) = ~ d t (x.) + (-I)N 2dN+ 1 n~= 0 3 n= 0 n n J

The right-hand side is a polynomial u

at the (N+I) points

1 (-i )n tn(X j). ~nn

of degree

N

which coincides with

(xj)j=0,...,N," we have then

=

an

+ 2

dn

)N+n

~-- (-I

dN+ 1 .

n

Q.E.D. 8.

Solutions of the Heat Equation

We consider the equation

~U_

i)

ii)

(8.1)

iii)

The

a(x) ~2u

~i-

boundary

x ~ I, t ) 0,

~--~x = 0

u(-l,t) = g(t), u(l,t) = h(t),

t ) 0

u(x,0) = u0(x) ,

x e I.

conditions

(8.1ii)

are

not

periodic,

unlike

the

problem

considered in Part A. We consider for simplicity the case of homogeneous boundary conditions, g(t)

=

h(t)

=

0

(i)

to

approximate

problem

(8.1)

with

the

following

146

collocation method. Suppose

VN

is the space (of dimension

N-I) defined by

V N = {p s PN : p(-l) = p(1) = 0}

and

(xj)0<j~ N

the

(N+I)

(8.2)

xj = cos ~N

we define the approximate Find

points defined by

UN(t) s V N

i)

j=I,...,N-I;

,

problem by

such that

~u N

.Ca-"~-

~2u N - a---~]

(x.)

1 < j < N-I

= 0,

3

~x ~

(8.3) ii)

I~

UN(Xj,0) = u0(xj),

j ~N-I.

We establish first the stability of the method (see Gottlieb (In

the

present

coefficient

a(x)

Theorem

8.1:

section,

all

functions

are

supposed

[8]).

real-valued,

and

is supposed regular and strictly positive).

Let:

(mj)0<j~N

points Gauss-Lobatto-Chebyshev

denote

formula and

the

U,llN

coefficients

of

the

(N+I)-

~he discrete norm defined by_

(1)Note that in this particular case the Fourier method is applicable.

147

I'PI'N E ((p,p)N)i~ N

~.

(P'q)N ~ 3~ O= ~

p(xj) q(xj),

then we have llUN(t)llN ~ UUN(0)liN.

We will need the following lemma from Gottlieb and Orszag [9]):

Lem

8.1:

Let

u s CI(T)

be a function such that

= u(-1)

u(1)

= o

then, we have

f where

~(x) ~ (l-x2) -I~

u u w' to d x ~ 0,

I

denotes the Chebyshev weight.

Proof of Lemma 8.1:

We note first that as

and zero at the end points, we have

lim

~ ( x ) u ( x ) = O.

x+±l

It follows that f

I NOW~

U U" m dx = - f

I

(mu)'u'dx.

u

is Lipschitz continuous

148

f I

(60u)'u'dx

f

--

(tou)'(tou)"

I

1

to dx - f

--

I

to~ (tou)" -to- u

dx,

and f

( t o u ) " to"

(60u)" 60u ~60" dx 60

--60 U dx = f I

I

2 f I

(°~2u2)"

dx

~ f I

~

to2u2 to

where we have integrated by parts, to obtain the last term.

Now,

(~-~2)- = (x(l-x2) - 1/2 )- = (l_x2) -3/2 60

yields

f (60u)"-60" I

U dx = -I/2f I

to

(l-x2) -5/2 u2dx.

We have shown that

f

((60u)~2 ~I dx -I/2f

u u" 60 dx = - f I

I

(l-x2) -5/2 u 2 dx, I

and the result follows. Q.E.D.

Proof of Theorem 8.1:

According to (8.3i) and the definition of

VN, we

have N

mj

~u N

j=0 ~-~7~so using

the

fact

that

(Xj )UN(Xj)-

the

N ~2u N ~ m (Xj)UN(X j) = 0 j=0 J ~

(N+l)-point

Gauss-Lobatto-Chebyshev

formula is

149

exact for the polynomials

of degree

Du N

UN)N -

~ 2N

f

I

32UN --u ~x 2

N ~ dx = 0.

With Lemma 8.1, we obtain

d iiUN(t) it2N ~UN --at = (~--~-, UN) N ~ 0,

and hence the result. Q.E.D.

An Error Estimate

Theorem ~iven;

8.2:

then if

Let

~ >I~,

s > 2G + 4

u e LI(0,T;H~(1)),

and

e

such that

there exists a constant

ilu(t) - UN(t)llN ~ C N 2a+4-s,

Proof:

Let

~(x,t)

= (~cU)(X,t),

C

z =~

- u.

where

~C

is

the

We have, using equation (8.1i),

~t ~

32 - a(x) ~

uN

= - ~~. z

be

such that

~ < t < T.

operator defined in Section 4. Let

0 < ~ < T

-

a(x)

~2z ~x 2

.

interpolation

150

Let then

WN(t) = (uN - UN)(t) s VN; we have, with (8.1i),

~W N ~2 3z 32z~ (~-- - a --3x 2 WN)(Xj) = (~-~ - a 3xmJ(Xj) ,

Multiplying the two sides by

J a(xj)

l~j


WN(Xj ) and summing from j=l to N-l, we

obtain 32W N --W (8--~'-'WN)N + f I 3x 2 3w N

N m dE = ( ~ -

a 32z, 3x-~ WN)N,

whence, with Lemma 8.1

1

~W N llWN(t)ilN = (8--t--'WN)N <

d IIWNIiN ~

(3z ~ - a 322, 3x WN) N ii~z ~2z11 ~-~ - a ~x2 N liWNfiN,

and by integration from

0

to

t

(and using the fact that

IIWN(0)IIN = 0)

t 32z] IIWN(t)IIN < ~0 ,.(~-~- a -~j(T)I, Nd~.

Now, i~l~-~z_ a ~3x--2z~ FIN < Cli~-~- a 3x 282zilo,m '

since

H:(:)

÷

H°(~)

~1a ~2zll

÷

n~

(I)

for

o >i/2 •

~x 2 c ,£0 ~< CIlu - uNlio+2,m

From Theorem 4.2, we have

C N 2"°+2"-s(~ Ilull

S~

151 /

and

II~t Ic~,

= II~-~C

~ull o,m ~ C N 2a-(s-2) ~-t

I1~,~11s-2,m"

Now, from equation (8.1i), we have

II~-~IIs-2 ,m = iFa - -2ull 8 < ~x 2 s-2,m

CIIull s,~o

Finally, we have shown that

z ~ 2z I N2o+4-s il(~--~- a ~x2J(T)jlo, m < C llu(T)lls,t0 ,

so for

0 < t < T

ll(u - UN)(t)ll N < ll(u - ]N)(t)ll N + IIWN(t);IN

N Cli(u-uN)(t)II ,m + C N 2~+4-s

Now,

for

t > e > 0, we know

that

u(t) e HI(1)

effect), therefore ll(U-UN)(t)rr ~

~ C N 2°-s.

/

t

0

S,0J

for all

s

aT °

(regularizing

t52

Finall:y, as we have assumed that

u ~ LI(0,T; Hi(l)), we obtain

ll(u - UN)(t)llN ~ C(N 2a-s + N2a+4-sl,

whlch yields the desired result. Q.E.D.

Remark 8.1: belong to

In order that the solution

u

of the heat equation (8.1)

LI~0,T; H~(1)), it is necessary that the initial solution should

satisfy certain regularity and compatibility conditions and also the boundary conditions (see Bramble'Schatz-Thomee

[2]).

References

[i]

Auslander-Tolimieri:

"Is

Fast

Fourier

Transform

pure

or

applied

mathematics," Bull. (New Series) AMS, I, 6 (1979), pp. 847-898.

[2]

Bramble-Schatz- Thomee:

[3]

Brutman, L.:

SlAM J. Numer. Anal., 14 (1977), pp. 218-241.

"On the Lebesgue function for polynomial interpolation,"

SlAM J. Numer. Anal. 15 (1978), pp. 694-704.

[4]

Canuto,

C. and A. Quarteroni:

"Proprietes d'approximation

espaces de Sob01ev de systemes de polynomes orthogonaux," Sci. Paris 290 (1980) Series A, pp. 925-928,

dans

les

C.R. Acad.

see also "Approximation

results for orthogonal polynomials" in Math. Comp. 38 (1982), pp. 6786.

[5]

Canuto, C., M. Y. Hussaini, A. Quarteroni, and T. A. Zang:

Spectral

Methods in Fluid Dynamics, Springer-Verlag, 1987.

[6]

Carleson:

[7]

Davis,

Acta Mathematica 116 (1966), pp. 135-157.

P. J.

and P. Rabinowitz:

Methods of Numerical Inte@ration,

Academic Press, New York, 1975.

[8]

Gottlieb,

D.:

"The

stability

of pseudospectral

Math. Comp. 36 (1981), pp. 107-118.

Chebyshev methods,"

154

[9]

Gottlieb, D. and S. A. Orszag:

Numerical Analysis of Spectral Methods,

SIAM, Philadelphia, 1977.

[to]

Kato, T.:

Perturbation Theory of Linear Operators,

Springer-Verlag,

Berlin, 1980.

[11]

Lions, J. L. and E. Magenes:

Nonhomogeneous Boundary Value Problems,

Springer-Verlag, Berlin, 1972.

[12]

Majda,

A.,

J.

McDonough,

and

S.

0sher:

"The

Fourier

method

for

nonsmooth initial data," Math. Comp. 32 (1978), pp. 1041-1081.

[13]

Pasciak,

J.:

"Spectral

and

pseudospectral

methods

for

advection

equations," Math. Comp. 35, 152 (1980), pp. 1081-1092.

[14]

Richtmyer,

R. and K. Morton:

Difference Methods

for Initial Value

Problems, J. Wiley & Sons, New York, 1963.

[15]

Rivlin,

T. J.:

An Introduction

to the Approximation

of Functions,

Dover, New York, 1969.

[16]

Schwartz, L.:

[17]

Taylor, M.:

Theorie des Distributions, Hermann, Paris, 1967.

Pseudo Differential Operators, Springer, Lecture Notes in

Mathematics No. 416.

[18]

Treves, F.:

Topolo$ical

Vector Spaces, Distributions,

Academic Press, New York, 1967.

and Kernels,