Representation of Sets of Trees for Abstract Interpretation

Laurent Mauborgne

Description

Niveau: Supérieur
Representation of Sets of Trees for Abstract Interpretation Laurent Mauborgne Thesis defended November 25, 1999 at Ecole Polytechnique Jury : Ahmed Bouajjani Patrick Cousot (director) Jean Goubault-Larrecq Nicolas Halbwachs Neil Jones (rapporteur, president) Andreas Podelski David Schmidt (rapporteur)

• abstract interpretation


• structures de donnees permettant de representer


• automate d'arbres


• proprietes de programmes


• nouvelle representation des ensem- bles d'arbres


• automates d'arbres infinis


• representation

Sujets

• Isnard
• École polytechnique
• Schmidt
• Maurice Halbwachs
• Abstract interpretation

Informations

• Publié par: chaeh
• Nombre de lectures: 8
• Langue: English
• Poids de l'ouvrage: 11 Mo

Extrait

NAVIER STOKES EQUATIONS
THEORY AND NUMERICAL ANALYSIS
ROGER TEMAM
Unioersite de Paris Sud, Orsay, France
Ecole Polytechnique, Palaiseau,
N'H
(l\>l9I5=
--
1977
NORTH HOLLAND PUBLISHING COMPANY AMSTERDAM' NEW YORK' OXFORD© North Holland Publishing Company 1977
All rights reserved. No part of this publication may be reproduced, stored in a
retrieval system, or transmitted, in any form or by any means, electronic, mechanical,
photocopying, recording or otherwise, without the prior permission ofthe copy-
right owner.
ISBN: 07204 2840 8
Published by:
North Holland Publishing Company
Amsterdam' New York· Oxford
Sole distributors for the U.S.A. and Canada:
Elsevier North Holland, Inc.
52 Vanderbilt Avenue
New York, NY 10017
Library of Congress Cataloging in Publication Data
Temam, Roger.
Navier Stokes equations.
Bibliography: 15 pp.
1. Navier Stokes equations. I. Title.
QA372.T38 515'.352 76 51536
ISBN 0 7204 2840 8
Printed in EnglandFOREWORD
In the present work we derive a number of results concerned with
the theory and numerical analysis of the Navier Stokes equations for
viscous incompressible fluids. We shall deal with the following prob-
lems: on the one hand, a description of the known results on the
existence, the uniqueness and in a few cases the regularity of solutions
in the linear and non linear cases, the steady and time dependent cases;
on the other hand, the approximation of these problems by discret-
isation: finite difference and finite element methods for the space
variables, finite differences and fractional steps for the time variable.
The questions of stability and convergence of the numerical procedures
are treated as fully as possible. We shall not restrict ourselves to these
theoretical aspects: in particular, in the Appendix we give details of
how to program one of the methods. All the methods we study have
in fact been applied, but it has not been possible to present details of
the effective implementation of all the methods. The theoretical
results that we present (existence, uniqueness,...) are only very basic and none of them is new; however we have tried as far as possible
to give a simple and self contained treatment. Energy and compactness
methods lie at the very heart of the two types of problems we have gone
into, and they form the natural link between them.
Let us give a more detailed description of the contents of this work:
we consider first the linearized stationary case (Chapter 1), then the
non linear stationary case (Chapter 2), and finally the full non linear
time dependent case (Chapter 3). At each stage we introduce new
mathematical tools, useful both in themselves and in readiness for
subsequent steps.
In Chapter I, after a brief presentation of results on existence and
uniqueness, we describe the approximation of the Stokes problem by
various finite difference and finite element methods. This gives us an
opportunity to introduce various methods of approximation of the
divergence free vector functions which are also vital for the numerical
aspects of the problems studied in Chapters 2 and 3.
In Chapter 2 we introduce results on compactness in both the contin-
uous and the discrete cases. We then extend the results obtained for the
linear case in the preceding chapter to the non linear case. The chapter
ends with a proof of the non uniqueness of solutions of the stationary
Navier Stokes equations, obtained by bifurcation and topological meth-
ods. The presentation is essentially self contained.
vForewordvi
Chapter 3 deals with the full non linear time dependent case. We
first present a few results typical of the present state of the mathemat-
ical theory of the Navier Stokes equations (existence and uniqueness
theorems). We then present a brief introduction to the numerical
aspects of the problem, combining the discretization of the space vari-
ables discussed in Chapter I with the usual methods of discretization
for the time variable. The stability and convergence problems are
treated by energy methods. We also consider the fractional step method
and the method of artificial compressibility.
This brief description of the contents will suffice to show that
this book is in no sense a systematic study of the subject. Many
aspects of the Navier Stokes equations are not touched on here. Several
interesting approaches to the existence and uniqueness problems, such
as semi groups, singular integral operators and Riemannian manifolds
methods, are omitted. As for the numerical aspects of the problem, we
have not considered the particle approach nor the related methods de-
veloped by the Los Alamos Laboratory.
We have, moreover, restricted ourselves severely to the Navier Stokes
equations; a whole range of problems which can be treated by the
same methods are not covered here. Nor are the difficult problems of
turbulence and high Reynolds number flows.
The material covered by this book was taught at the University
of Maryland in the first semester of 1972 3 as part of a special year on
the Navier Stokes equations and non linear partial differential equations.
The corresponding lecture notes published by the University of Mary-
land constitute the first version of this book.
I am extremely grateful to my colleagues in the Department of
Mathematics and in the Institute of Fluid Dynamics and Applied at the University of Maryland for the interest they showed
in the elaboration of the notes. Direct contributions to the preparation
of the manuscript were made by Arlett Williamson, and by Professors
J. Osborne, J. Sather and P. Wolfe. I should like to thank them for
correcting some of my mistakes in English and for their interesting
comments and suggestions, all of which helped to improve the manu-
script. Useful points were also made by Mrs Pelissier and by Messrs
Fortin and Thomasset. Finally, I should like to express my thanks
to the secretaries of the Mathematics Departments at Maryland and
Orsay for all their assistance in the preparation of the manuscript.CHAPTER I
THE STEADY-STATE STOKES EQUATIONS
Introduction
In this chapter we study the stationary Stokes equations; that is, the
stationary linearized form of the Navier-Stokes equations. The study of
the Stokes equations is useful in itselfj it also gives us an opportunity to
introduce several tools necessary for a treatment of the full Navier-Stokes
equations.
In Section 1 we consider some function spaces (spaces of divergence›
2free vector functions with L -co m po ne nts). In Section 2 we give the
variational formulation of the Stokes equations and prove existence and
uniqueness of solutions by the projection theorem. In Sections 3 and 4
we recall a few definitions and results on the approximation of a normed
space and of a variational linear equations (Section 3). We then propose
several types of approximation of a certain fundamental space V of diver›
gence-free vector functions; this includes an approximation by tae finite›
difference method (Section 3), and by conforming and non-conforming
finite-element methods (Section 4). In Section 5 we discuss certain
approximation algorithms for the Stokes equations and the corresponding
discretized equations. The purpose of these algorithms is to overcome the
difficulty caused by the condition div u = 0. As it will be shown, this
difficulty, sometimes, is not merely solved by discretization.
Finally in Section 6 we study the linearized equations of slightly com›
pressible fluids and their asymptotic convergence to the linear equations
of incompressible fluids (i.e., Stokes’ equations).
§1. Some function spaces
In this section we introduce and study certain fundamental function
spaces. The results are important for what follows, but the methods used
in this section will not reappear so that the reader can skim through the
proofs and retain only the general notation described in Section 1.1 and
the results summarized in Remark 1.6.
1.1. Notation
nIn Euclidean space tR we write el = (1, 0, ..., 0), e2 = (0, 1, 0, ..., 0),
..., en = (0, ..., 0, 1), the canonical basis, and x = (xl’ ..., X ),nThe steady-state Stokes equations2 en. 1, § 1
y = (Yl’ ..., Y ), Z = (Zl’ ... , Zn)’ ... , will denote points of the space.n
The differential operator
will be written D and if i =(i!, ... in) is a multi-index, J)i will be thej
differentiation operator
aU)
J =Dh Din =D (1.1)1’" n . .axIl ... ax~n
where
(1.2)
Ifi; =0 for some t, IY;i is the identity operator; in particular if [j] = 0,
o! is the identity.
The set n
nLet n be an open set of tR with boundary r. In general we shall
need some kind of smoothness property for n. Sometimes we shall
assume that n is smooth in the following sense:
The boundary r is a (n-l j-dimensional manifold
of class lfr(r ~ I which must be specified) and n
is locally located on one side of r. (1.3)
We will say that a set n satisfying (1.3) is of class’s". However this
hypothesis is too strong for practical situations (such as a flow in a
square) and all the main results will be proved under a weaker condition:
(1.4)The boundary of n is locally Lipschitz.
This means that in a neighbourhood of any point x E r, r admits a
representation as a