These Venel
These Venel
These Venel
o d'ordre : 9245
Université Paris-Sud
THÈSE
DE L'UNIVERSITÉ PARIS XI
tel-00346035, version 1 - 10 Dec 2008
par
Juliette Venel
Sujet :
ii
Remer
iements
Je voudrais ensuite adresser mes remer
iements à Yann Brenier et à Lionel Thibault
pour l'intérêt qu'ils ont porté à mes travaux en a
eptant de rapporter sur
ette thèse,
ainsi qu'aux autres membres du jury, Cé
ile Appert-Rolland, Jean-François Coulombel
et Patri
k Gérard pour leur présen
e à la soutenan
e. J'aimerais plus parti
ulièrement
remer
ier Patri
k Gérard, qui depuis mon arrivée à Orsay (et
ela
ommen
e à dater) a
suivi ave
beau
oup d'attention mon par
ours.
tel-00346035, version 1 - 10 Dec 2008
Bien évidemment,
ette thèse n'aurait pu voir le jour sans l'enseignement mathéma-
tique de qualité dont j'ai béné
ié tout au long de mes études. J'en prote pour remer
ier
tous les professeurs qui y ont
ontribué et plus parti
ulièrement pour exprimer toute ma
gratitude à Jean Voedts qui m'a donné le goût et l'envie de faire des mathématiques.
Un grand mer
i à la ne équipe de do
torants ave
qui j'ai traversé
es trois années et
plus spé
ialement aux thésards (an
iens et nouveaux) du bureau 256, pour la très bonne
ambian
e qui y règne. Mer
i à Adeline qui me proposait un
ho
olat à
ha
un de mes
soupirs ; heureusement que je ne les ai pas tous a
eptés ! Mer
i à Christine pour son
é
oute et sa sympathie. An
ienne représentante de l'ordre dans le bureau, ses
huts me
manquent déjà. J'aimerais aussi plus spé
ialement remer
ier Aline et Fred, pour m'avoir
épaulée tout au long de
ette thèse et surtout au
ours de
es derniers mois. Votre le
-
ture minutieuse du manus
rit, vos nombreuses suggestions le
on
ernant, m'ont été très
pré
ieuses. Je vous remer
ie aussi pour toutes nos dis
ussions mathématiques et
onver-
sations en tous genres. Mer
i à Aline pour son aide lors des préparations d'exposé et pour
la patien
e dont elle a fait preuve en m'initiant au C++. Mer
i à Fred pour sa
uriosité,
sa gentillesse et son dévouement.
iii
J'en prote pour remer
ier Anne-Laure pour sa présen
e malgré la distan
e. Mer
i
pour toutes
es années d'amitié ! Je tiens également à souligner le rle essentiel de ma
famille tout au long de mes études. Mer
i à mes pro
hes qui ont fait le dépla
ement, mes
pensées a
ompagnent aussi
eux qui ne pouvaient venir. Je tiens à remer
ier sin
èrement
mes parents pour leur
onan
e et leurs en
ouragements. Ainsi, j'ai pu suivre leur exemple
en devenant do
teur à ma façon. Mer
i à mes frère et soeur, Yann et Véronique pour les
bons week-ends
h'tis, tourangeaux et angevins.
Enn, il me reste à remer
ier Maxime mon matheux préféré qui a eu le
ourage de
me supporter toutes
es années. C'est dans son soutien, son é
oute et sa tendresse que je
trouve mon équilibre. Sans lui, rien de tout
ela n'aurait été possible.
tel-00346035, version 1 - 10 Dec 2008
iv
Résumé
Nous nous intéressons à la modélisation des mouvements de foule
ausés par des situa-
tions d'éva
uation d'urgen
e. L'obje
tif de
ette thèse est de proposer un modèle mathé-
matique et une méthode numérique de gestion des
onta
ts, an de traiter les intera
tions
lo
ales entre les personnes pour nalement mieux rendre
ompte de la dynamique glo-
bale du tra
piétonnier. Nous proposons un modèle mi
ros
opique de mouvements de
foule reposant sur deux prin
ipes. D'une part,
haque personne a une vitesse souhaitée,
elle qu'elle aurait en l'absen
e des autres. D'autre part, la vitesse réelle des individus
prend en
ompte une
ertaine
ontrainte d'en
ombrement maximal. En pré
isant le lien
entre
es deux vitesses, le problème d'évolution prend la forme d'une in
lusion diéren-
tielle du premier ordre. Son
ara
tère bien posé est démontré en utilisant des résultats
sur les pro
essus de rae par des ensembles uniformément prox-réguliers. Ensuite, nous
présentons un s
héma numérique et démontrons sa
onvergen
e. Pour
al
uler une vitesse
souhaitée parti
ulière (
elle dirigée par le plus
ourt
hemin évitant les obsta
les), nous
présentons une programmation orientée objet ayant pour but de simuler l'éva
uation d'une
stru
ture de plusieurs étages présentant une géométrie quel
onque. Nous nissons ave
d'autres
hoix de vitesse souhaitée (par exemple, en ajoutant des stratégies individuelles)
tel-00346035, version 1 - 10 Dec 2008
et présentons les résultats numériques asso
iés. Ces simulations numériques permettent
de retrouver
ertains phénomènes observés lors de dépla
ements piétonniers.
Abstra
t
We are looking for modelling
rowd motion in emergen
y eva
uation. The aim of this
thesis is to propose a mathemati
al model and a numeri
al method to handle
onta
ts, in
order to deal with lo
al intera
tions between people and to des
ribe the whole dynami
s
of the pedestrian tra
. We propose a mi
ros
opi
model for
rowd motion whi
h rests
on two prin
iples. On the one hand, ea
h individual has a spontaneous velo
ity that he
would like to have in the absen
e of other people. On the other hand, the a
tual velo
ity
must take into a
ount
ongestion. By spe
ifying the link between these two velo
ities, the
evolution problem takes the form of a rst order dierential in
lusion. Its well-posedness
is proved with the help of results
on
erning sweeping pro
esses by uniformly prox-regular
sets. Then we present a numeri
al s
heme and prove its
onvergen
e. In order to
om-
pute a spe
i
spontaneous velo
ity (the one dire
ted by the shortest path avoiding the
obsta
les), we present an obje
t oriented programming to simulate the eva
uation of any
building
onsisting of several oors. To
on
lude, we des
ribe other
hoi
es of sponta-
neous velo
ity (for example, by adding individual strategies) and we present asso
iated
numeri
al results. These numeri
al simulations allow us to re
over some
hara
teristi
s of
pedestrian tra
.
v
tel-00346035, version 1 - 10 Dec 2008
vi
Table des matières
Introdu tion 1
Chapitre 1
Diérents modèles pour représenter la foule
1.1 Etat de l'art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
tel-00346035, version 1 - 10 Dec 2008
organisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Partie I
Aspe
ts théoriques 21
Chapitre 2
Cadre mathématique et résultats
2.1 Reformulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
vii
Table des matières
Chapitre 3
Prox-régularité de l'ensemble des
ongurations admissibles Q0
3.1 Etude de l'ensemble Q12 . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.1.2 Prox-régularité . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2 Généralisation à Q0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.2.2 Prox-régularité . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Partie II
Dis
rétisation et étude numérique 65
Chapitre 4
Présentation et étude d'un s
héma numérique
4.1 Présentation du s
héma numérique . . . . . . . . . . . . . . . . . . . . 68
de Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
viii
Partie III
Programmation et résultats numériques 97
Chapitre 5
Méthodes numériques utilisées et programmation ee
tive
5.1 Cal
ul de la vitesse réelle ave
l'algorithme d'Uzawa . . . . . . . . . . . 100
Chapitre 6
Résultats numériques
6.1 Résultats re
ouvrant les phénomènes d'auto-organisation . . . . . . . . 121
Annexes
ix
Table des matières
Annexe A
Quelques résultats d'analyse
onvexe
Annexe B
Lemme de Farkas
Annexe C
Cne polaire
Annexe D
Opérateurs maximaux monotones
Annexe E
Étude du gradient de la fon
tion D12
tel-00346035, version 1 - 10 Dec 2008
Annexe F
Autre preuve de la prox-régularité de Q12
Annexe G
Autre démonstration de l'inégalité triangulaire inverse
Annexe H
Formulation point-selle
Annexe I
Algorithme d'Uzawa
Bibliographie 195
x
Introdu
tion
Dans
ette thèse, nous nous intéressons à la modélisation de mouvements de foule
ausés par des situations d'éva
uation d'urgen
e. De telles situations sont
ara
térisées
par des
ongurations très denses en individus et présentent de nombreux
onta
ts. L'ob-
je
tif de
ette thèse est de proposer un modèle mathématique et une méthode numérique
de gestion des
onta
ts, an de traiter les intera
tions lo
ales entre les personnes pour
nalement mieux rendre
ompte de la dynamique globale du tra
piétonnier.
Depuis plusieurs dé
ennies, de nombreuses études portant sur le
omportement des pié-
tons ont été menées. Dans un premier temps, des travaux d'observation ([Fru71, NW69,
Wei93℄) ont été ee
tués dans le but de réunir des données qualitatives (préféren
es,
tendan
es des mar
heurs) mais aussi quantitatives
omme pour pré
iser par exemple, la
vitesse des individus en fon
tion de la densité de la foule (
f. sous-se
tion 1.1.1). Ensuite,
grâ
e aux résultats pré
édents, de nombreux modèles de mouvements de foule ont été
proposés. Ces derniers a
hent un but
ommun, prédire les
hemins les plus empruntés
mais dièrent sur plusieurs points : leur mode de représentation de la foule (mi
ros
o-
pique en se plaçant à l'é
helle de l'individu ou ma
ros
opique en dé
rivant la foule par
sa densité), leur façon d'appréhender les zones de dépla
ement (dis
rétisation spatiale
ou non) et leur
ara
tère déterministe ou sto
hastique. Ces modèles peuvent être
las-
sés en quatre
atégories (
f. sous-se
tion 1.1.2) : les modèles basés sur des automates
ellulaires [BA01, BKSZ01, Nag98, S
h01℄, les modèles utilisant des graphes orientés
[BT86a, BT86b, Løv94, YS89℄, le modèle de for
es so
iales [HM95, HFV00b℄ et les mo-
dèles ma
ros
opiques [Hel92b, Hen71, HB00, HB04a, HB04b℄. Beau
oup de
es modèles
ont abouti à la
réation de logi
iels de simulation du tra
piétonnier,
omme par exemple
PedGo [HMK03℄, SimPed [Daa04℄, Legion [Sti93℄ ou en
ore Mipsim [HB00℄.
Déterminer les traje
toires des piétons permet de proposer des dire
tives aux
onstru
-
teurs an d'améliorer leur
onfort. En eet,
es informations peuvent être d'une grande
utilité pour évaluer la largeur satisfaisante des
ouloirs, des portes, ... . Prévoir les dépla-
ements des personnes peut aussi aider à pla
er les panneaux d'information importants
ou même positionner stratégiquement les panneaux publi
itaires.
Par ailleurs, il existe un tout autre enjeu à la modélisation des mouvements de foule. De-
puis plusieurs années, la demande de simulations d'éva
uation en
as d'urgen
e n'a
essé
d'augmenter. L'obje
tif est d'estimer la durée de l'éva
uation (à
omparer par exemple
au temps de propagation d'un feu) mais aussi de prédire les zones où les individus seront
1
Introdu
tion
Cependant,
es méthodes (prin
ipe d'ex
lusion ou for
e de répulsion) ne prennent pas en
ompte le
onit dire
t entre les individus, et ne peuvent don
pas fournir d'informations
sur les intera
tions lo
ales entre les piétons.
Notre obje
tif est de proposer un modèle de mouvements de foule traitant dire
tement
les
onta
ts entre les individus et pouvant déterminer les zones sus
eptibles d'a
her de
fortes pressions. Notre modèle de gestion des
onta
ts doit aussi faire preuve de souplesse
et être
apable d'in
lure les modèles déjà existants qui déterminent les
hemins les plus
empruntés.
Le modèle
Nous proposons un modèle mi
ros
opique de mouvements de foule qui repose sur
deux prin
ipes. D'une part,
haque personne a une vitesse souhaitée,
elle qu'elle aurait
en l'absen
e des autres. D'autre part, la vitesse réelle des individus prend en
ompte
une
ertaine
ontrainte d'en
ombrement maximal. Plus pré
isément, dans
e modèle, la
vitesse réelle est la proje
tion de la vitesse souhaitée sur un ensemble dit de vitesses
admissibles (qui respe
tent une
ontrainte de non-
hevau
hement des disques représentant
les individus). Dans le premier point du modèle réside sa souplesse. En eet, tout modèle
de prédi
tion des mouvements piétonniers peut être i
i intégré. Dans le se
ond point du
modèle, s'opère la gestion dire
te des
onta
ts.
En pré
isant le lien entre les deux vitesses souhaitée et réelle, nous obtenons un pro-
blème d'évolution qui prend la forme d'une in
lusion diérentielle du premier ordre vé-
riée par le ve
teur position des personnes. Formulations naturelles des problèmes ave
ontrainte unilatérale, les in
lusions diérentielles ont fait l'objet de nombreux travaux.
Les premiers problèmes d'in
lusion diérentielle ont été étudiés au début des années 70
par H. Brezis grâ
e à la théorie des opérateurs maximaux monotones (
f [Bre73℄). Plus
tard dans [Mor77℄, J.J. Moreau
onsidère un problème mettant en jeu un opérateur mul-
tivalué dépendant du temps. Il s'agit du premier problème de pro
essus de rae ( sweeping
2
pro
ess ) par des ensembles
onvexes. Ne pouvant appliquer la théorie pré
édente, l'au-
teur utilise un algorithme dit de rattrapage (
at
hing-up algorithm ) pour
onstruire des
solutions du problème et démontrer sous
ertaines hypothèses, son
ara
tère bien posé.
Depuis,
es pro
essus de rae ont fait et font en
ore l'objet de nombreuses études. Des
généralisations signi
atives ont été apportées (
f. sous-se
tion 2.4.2), notamment en at-
ténuant l'hypothèse de
onvexité des ensembles
onsidérés, faisant apparaître la notion de
prox-régularité (
f. sous-se
tion 2.4.1). Cette nouvelle notion s'avère pour nous essentielle,
puisque
'est le
ara
tère uniformément prox-régulier de l'ensemble des
ongurations ad-
missibles (au sens où les disques ne se
hevau
hent pas) qui permet d'établir, à l'aide de
résultats ré
ents [ET05℄, que le problème d'évolution asso
ié au modèle est bien posé.
Le modèle de mouvements de foule proposé, bien qu'idéalisé par la représentation
somme toute simpliste des individus, ore la possibilité de retrouver
ertains phéno-
mènes observés lors de dépla
ements piétonniers et jugés importants par les modélisa-
teurs (
f. se
tion 6.1). De plus, les études théorique et numérique de
e modèle ont per-
mis d'établir des liens entre des notions mathématiques abstraites et des
omportements
numériques observés dans les milieux granulaires. En eet, le
on
ept théorique de prox-
régularité (propriété de l'ensemble des
ongurations admissibles) est relié, dans le présent
tel-00346035, version 1 - 10 Dec 2008
travail, aux
ara
téristiques géométriques réelles de la stru
ture formée par les amas de
disques (pouvant représenter des grains ou des individus). Or la géométrie de
e réseau
a un rapport dire
t ave
la non-uni
ité des pressions subies par les disques. D'un point
de vue mathématique,
es pressions sont formellement des multipli
ateurs de Lagrange,
qui apparaissent naturellement dans le modèle. Leur non-uni
ité explique les instabilités
numériques des pressions
al
ulées, instabilités qui sont observées dans la réalité, que
e
soit dans le milieu granulaire ou piétonnier.
3
Introdu
tion
du
adre des pro
essus de rae présenté au
hapitre 2. En reformulant
ette proje
tion sous
la forme d'un problème point-selle, nous démontrons la
onvergen
e du s
héma par une
méthode de
ompa
ité, en prouvant le
ara
tère uniformément borné des multipli
ateurs
de Lagrange.
La troisième partie
onstituée des
hapitres 5 et 6, est
onsa
rée à la programmation
et à la présentation des résultats numériques. Dans le
hapitre 5, pour programmer le se-
ond point du modèle, nous proposons d'utiliser l'algorithme d'Uzawa an de
al
uler la
vitesse réelle dis
rète
omme proje
tion de la vitesse souhaitée. Nous présentons
e dernier
ainsi que des résultats de
onvergen
e. Ensuite, nous nous intéressons au premier point
du modèle en
hoisissant une vitesse souhaitée parti
ulière (
elle dirigée par le plus
ourt
hemin évitant les obsta
les). Nous présentons la méthode de type Fast Mar
hing utilisée
lors de son
al
ul. Enn, nous proposons une programmation orientée objet in
luant
ette
méthode et ayant pour but de simuler l'éva
uation d'une stru
ture de plusieurs étages
présentant une géométrie quel
onque. Dans le
hapitre 6, nous proposons diérents
hoix
de vitesse souhaitée et présentons les résultats numériques asso
iés. Dans un premier
temps, nous verrons que
ertains
hoix permettent de retrouver les phénomènes observés
lors de dépla
ements piétonniers dé
rits dans la sous-se
tion 1.1.3. Ensuite, nous présen-
tel-00346035, version 1 - 10 Dec 2008
tons des simulations numériques asso
iées au
hoix de la vitesse souhaitée dirigée par
le plus
ourt
hemin. Ces résultats sont issus de la programmation C++ pré
édemment
évoquée. Puis nous présentons un autre
hoix de vitesse souhaitée prenant également en
ompte les obsta
les. Nous proposons de prendre pour
elle-
i la solution d'une équation
aux dérivées partielles ave
des
onditions aux bords sur les obsta
les. Ce
hoix, bien que
donnant des résultats raisonnables, ne sera pas utilisé de façon systématique
omme le
hoix du ot géodésique, plus justié en termes de modélisation. Enn, nous diérentions
le
omportement des personnes en ajoutant des stratégies individuelles (ralentissement ou
ontournement lors d'un embouteillage).
La présentation du modèle, son
adre mathématique ainsi que sa dis
rétisation nu-
mérique ont fait l'objet d'un pro
eeding [MV07℄. Le travail de modélisation réalisé pour
l'ajout de stratégies individuelles a été présenté dans un autre pro
eeding [Ven09℄. Leur
ontenu ayant été intégralement repris, développé et réorganisé,
es arti
les ne sont pas
joints au présent do
ument.
4
Chapitre 1
Diérents modèles pour représenter la
foule
Sommaire
1.1 Etat de l'art . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
tel-00346035, version 1 - 10 Dec 2008
5
Chapitre 1. Diérents modèles pour représenter la foule
Dans
ette se
tion, après une présentation de quelques données empiriques
on
ernant
le ux piétonnier, nous dé
rivons les modèles de mouvements de foule existants. Puis
nous présentons les phénomènes importants observés lors des dépla
ements de piétons que
ertains modèles permettent de retrouver. Enn, nous nous
on
entrons sur les modèles
traitant des situations d'éva
uation.
son
onfort (prote
tion
ontre les intempéries, présen
e d'es
alators au lieu d'es
a-
liers, qualité du sol, ...).
Diagramme fondamental
On se pla
e i
i dans le
adre d'un ux unidire
tionnel non
ontraint (tous les individus
suivent la même dire
tion dans un lieu sans obsta
le). La des
ription ma
ros
opique de la
foule repose sur trois variables : la densité ρ, la vitesse v et le ux Q vériant le relation
fondamentale Q = ρv . Comme pour étudier le tra
routier, il est intéressant de tra
er
le diagramme fondamental,
'est-à-dire de représenter le ux Q du tra
piétonnier en
fon
tion de la densité ρ, an d'analyser la transition entre régime libre et régime en
ombré.
On dit qu'on se trouve en régime libre (resp. en
ombré) lorsque la densité est inférieure
(resp. supérieure) à ρcrit : densité
ritique lorsque le ux Q est maximal (Q = Qmax ). On
dénit alors ucrit = Qmax /ρcrit et on note par ailleurs ρjam la densité au dessus de laquelle
le ux Q est nul (embouteillage). Dans [Wei93℄, on trouve les valeurs suivantes pour
es
paramètres : ρcrit = 1.75 piétons par m2 , ucrit = 0.7 m.s−1 , et ρjam = 5.4 piétons par m2 .
6
1.1. Etat de l'art
• du lieu
onsidéré (par exemple, dans un es
alier, la vitesse moyenne en montée est
estimée à 0.9m.s−1 alors qu'en des
ente elle est de 0.7 m.s−1 ).
2
D'après [Wei93℄, la surfa
e o
upée par une personne est d'environ 0.15 m . Lorsque les
2
piétons sont dans une phase d'attente, la densité varie entre 2 et 3 individus par m .
De plus, des études ont été menées dans le but de mieux appréhender la relation entre
vitesse moyenne et densité. Beau
oup de travaux (par exemple [Fru71, NW69℄) ont
on
lu
à une relation linéaire entre vitesse et densité,
u = u0 − αρ , α > 0.
[DH03, HD05℄ ont été menées pour déterminer la
onséquen
e d'un rétré
issement de voies
sur la densité et la vitesse des piétons. Dans [DH03, HD05℄, une telle situation est
réée,
obligeant des personnes à passer dans un
ouloir de 5 mètres de long et d'une largeur d'1
mètre, de sorte que deux personnes ne peuvent pas rentrer dans le
ouloir simultanément
(un individu o
upe une largeur de 50
entimètres). Les auteurs remarquent que lors des
expérien
es, les gens mar
hent dans le
ouloir de manière à réduire l'espa
e vide
omme
2
illustré par la gure 1.1, la densité atteignant alors la valeur de 2.5 piétons par m . D'autre
−1
part, la vitesse moyenne à
ause du rétré
issement dé
roît à environ 1 m.s . Les auteurs
en
onsidérant les traje
toires que suivent les piétons pour rentrer dans un passage étroit
(
f. g 1.2) parlent de zipper ee
t.
7
Chapitre 1. Diérents modèles pour représenter la foule
8
1.1. Etat de l'art
met de par
ourir le plus de
ases possibles vers la sortie. Si au
un mouvement vers l'avant
n'est possible, les personnes s'arrêtent et peuvent
hoisir de
ontourner après un
ertain
temps. Il est aussi possible que les gens
hangent soudainement de dire
tion ou s'arrêtent
indé
is suivant
ertaines probabilités. Dans [Sti93℄, des automates
ellulaires sont aussi
utilisés mais
haque piéton o
upe plusieurs
ases. Le
hemin de toute personne doit sa-
tisfaire plusieurs
ontraintes, par exemple
elle de non-
ollision ave
les autres individus
ou
elle de passer par
ertaines régions de l'espa
e et dans un ordre imposé. Ensuite, l'au-
teur dénit le
oût d'un
hemin pouvant prendre en
ompte diérents paramètres
omme
sa longueur, l'eort à fournir pour l'emprunter ou son temps de par
ours. Finalement,
le mouvement des piétons est traité globalement, en minimisant le
oût total, somme
des
oûts des
hemins individuels, et
ela tout en respe
tant les
ontraintes imposées
aux
hemins. Ce modèle est à la base du logi
iel Legion dé
rit dans le
hapitre 5 de la
thèse [Sti00℄.
so
iales se pla
e au niveau mi
ros
opique et propose de dé
rire les mouvements de foule
par un système d'équations diérentielles. Plus pré
isément, le dépla
ement de l'individu
i est régi par une équation du type,
dwi (t)
= Fi (t),
dt
où wi est la vitesse dite préférée de la personne i et Fi (t) est la somme des for
es s'exerçant
sur l'individu i au temps t. Les for
es mises en jeu sont des a
élérations et des dé
éléra-
tions dues aux diverses réa
tions des individus quand ils perçoivent leur environnement
(autres individus et obsta
les). Plus pré
isément, quatre for
es diérentes
omposent le
se
ond membre Fi (t) : deux for
es de répulsion ave
les autres individus et les obsta
les,
une for
e d'attra
tion (vers un endroit stratégique ou une personne intéressante) et un
terme d'a
élération du type
vi0 ei (t) − wi (t)
,
τi
où ei (t) est la dire
tion souhaitée (vers la destination), vi0 l'allure souhaitée et τi un
ertain
temps de relaxation. Ensuite, les auteurs tronquent la vitesse pré
édente pour obtenir la
vitesse souhaitée de la personne i : vi (t) est dénie par
max
wi (t) si |wi (t)| ≤ vi
vi (t) = wi (t)
vimax sinon
|wi (t)|
où vimax est la norme maximale de la vitesse de la personne i.
9
Chapitre 1. Diérents modèles pour représenter la foule
gère intrinsèquement la présen
e d'obsta
les. Ensuite, il reste à déterminer les
hemins
que vont prendre les piétons, on parle alors de Route
hoi
e model. De nombreuses possibi-
lités existent. Dans [BT86a, BT86b, BS90℄ par exemple, les
hemins possibles
onsidérés
sont les plus
ourts
hemins entre les noeuds de départ et d'arrivée. Dans [Gip86℄, les
hemins potentiels ne sont pas déterminés dans leur intégralité mais des destinations
intermédiaires sont d'abord générées en fon
tion de l'origine et de la destination nale
du trajet puis des sous-
hemins possibles entre
es étapes intermédiaires sont détermi-
nés. Beau
oup d'algorithmes existent pour
al
uler
es plus
ourts
hemins (pour plus
de détails voir [Daa04℄). Dans [GGLF01℄, l'en
ombrement et les
onditions extérieures
(présen
e de fumée) sont prises en
ompte en pondérant les arêtes. Cette méthode est à
la base du logi
iel buildingEXODUS et de ses dérivés maritimeEXODUS et airEXODUS.
D'autres modèles utilisant des les d'attente [Løv94, YS89℄ ( Queuing models ) sont éga-
lement basés sur des graphes. Dans
es modèles, une loi de probabilité est dénie pour
gérer l'arrivée des individus (par exemple une loi de Poisson). Ensuite, pour prendre en
ompte les les d'attente grandissantes lorsque la demande du tra
piétonnier est plus
grande que la
apa
ité de la porte, des temps d'attente aléatoires pondèrent les arêtes du
réseau représentant les portes.
tel-00346035, version 1 - 10 Dec 2008
10
1.1. Etat de l'art
des vitesses admissibles sont
hoisies dépendant linéairement de la densité. La vitesse des
individus est la vitesse admissible qui réalise le minimum de
ette fon
tionnelle.
Remarque 1.1 Nous attirons i
i l'attention sur le fait que
es modèles ne traitent pas
globalement la foule mais distinguent les individus selon leurs vitesses ou leurs destina-
tions. Dans les modèles type Route
hoi
e models, quels que soient les
ritères
hoisis
pour déterminer les
hemins potentiels, seul un nombre ni de possibilités existe. Dans les
modèles [HB04a, HB04b, Hug00, Hug02℄, l'absen
e de dis
rétisation permet de dépasser
es limitations.
Formation de les lorsque deux groupes d'individus mar
hent en sens opposé
tel-00346035, version 1 - 10 Dec 2008
Quand deux groupes d'individus, mar
hant en sens oppposé, se
roisent, le ux piéton-
ner s'organise pour minimiser les intera
tions entre les individus qui n'ont pas la même
destination. Pour
ela, il se divise en plusieurs voies
onstituées de personnes allant dans
le même sens. La gure 1.3 illustre bien
et en
hevêtrement de voies au sens de par-
ours diérent (ngering pattern ) de sorte que les personnes ayant la même dire
tion se
suivent à la le. Dans [HM95℄, des résultats numériques asso
iés au modèle de for
es so-
11
Chapitre 1. Diérents modèles pour représenter la foule
de for
es so
iales est réutilisé pour simuler à nouveau la ren
ontre de deux groupes de
piétons se déplaçant en sens opposé. Mais aux diérentes for
es d'attra
tion et de répul-
sion déjà détaillées dans la sous-se
tion 1.1.2, ils ajoutent un terme sto
hastique pour
réer des u
tuations au niveau des vitesses des individus. Les auteurs remarquent que
si
e terme devient trop important, la formation de les n'a plus lieu et les individus se
bloquent indéniment en formant un réseau
ristallin. Cette transition est
onnue sous le
nom de freezing by heating.
12
1.1. Etat de l'art
tel-00346035, version 1 - 10 Dec 2008
Fig. 1.6 Diérentes phases d'une optimisation d'un rétré issement de voie.
dans la sous-se
tion 1.1.4 que le modèle de for
es so
iales adapté [HFV00b℄ et les modèles
utilisant des automates
ellulaires [KS02, SKN03℄ permettent de retrouver
es ar
hes (
f.
gs 1.9 et 1.10). D'après [HFV00b℄, il est très important d'identier les zones où
es ar
s
se dessinent, puisqu'elles sont
ara
téristiques des lieux d'engorgement où apparaissent de
fortes pressions.
13
Chapitre 1. Diérents modèles pour représenter la foule
vi (t)
ηi (t) = 1 − ,
vi0
14
1.1. Etat de l'art
où vi (t) est la vitesse réelle moyenne dans la dire
tion souhaitée de la personne i et vi0
est la vitesse souhaitée initialement dans
ette même dire
tion. Le terme vitesse signie
l'allure, la norme du ve
teur vitesse. Ce taux modie la vitesse souhaitée à l'instant t,
selon
vi0 (t) = [1 − ηi (t)]vi0 + ηi (t)vimax .
Un
as numérique traite de l'éva
uation de 200 personnes d'une piè
e sans obsta
le ave
une unique porte de sortie (d'une largeur d'un mètre). Les rayons ont été pris distin
ts
pour ne pas faire apparaître de
ongurations
ristallines. Lors des simulations, les auteurs
0
remarquent qu'au début, plus la vitesse souhaitée vi augmente, meilleur est le temps de
0 −1
sortie T des 200 personnes. Mais, dès que vi dépasse une
ertaine valeur (1.5 m.s ), des
blo
ages au niveau de la porte apparaissent : pendant quelques se
ondes, au
une personne
ne sort (
f. g 1.9). Et nalement le temps T augmente. Les auteurs parlent de faster-
tel-00346035, version 1 - 10 Dec 2008
is-slower ee
t : quand les personnes perdent patien
e, leur vitesse souhaitée augmente,
vi0 dépasse 5 m.s−1 , des personnes sont bles-
e qui a
roît les for
es de fri
tion. Enn, si
sées et deviennent des obsta
les passifs pour les autres. Les auteurs
onsidèrent que des
individus se retrouvent ainsi immobilisés si la somme des amplitudes des for
es radiales
−1
divisée par leur
ir
onféren
e dépasse une pression de 1600 N.m . En dernier lieu, les
auteurs veulent modéliser le
omportement de masse, qui
rée une fâ
heuse tendan
e à
ne pas utiliser toutes les sorties disponibles, en faisant dépendre la dire
tion souhaitée de
la personne i de la dire
tion moyenne de ses voisins se trouvant à une
ertaine distan
e.
Si
ette dépendan
e est faible, des
omportements individualistes en résultent, sinon
'est
un
omportement moutonnier qui apparaît. Les auteurs ont appliqué
e
i au
as de 90
personnes présentes dans une salle enfumée (sans obsta
le) qui dispose de deux sorties.
Le meilleur temps d'éva
uation est obtenu quand on
ombine les deux
omportements :
quelques personnes repèrent les sorties et les autres les suivent. Dans le
as d'un individua-
lisme pur, les personnes partent dans des dire
tions opposées et se gênent mutuellement,
alors qu'un
omportement de masse
onduit à l'utilisation d'une unique sortie.
Nous passons maintenant aux modèles utilisant une dis
rétisation spatiale en débutant par
les modèles basés sur des automates
ellulaires. Ave
le modèle présenté dans [KMKWS00℄
15
Chapitre 1. Diérents modèles pour représenter la foule
et détaillé dans la sous-se
tion 1.1.2, plusieurs simulations d'éva
uations d'urgen
e ont
été ee
tuées dans diérents lieux : dans une é
ole primaire [KMKS01℄, dans un na-
vire [KMKWS00, MKKKS01℄. Les auteurs
omparent leurs résultats numériques ave
leurs données expérimentales. Dans [KMKS01℄, le temps d'éva
uation numérique est in-
férieur à
elui observé lors des expérien
es. Les auteurs expliquent
ela par le fait que
les élèves
onnaissent bien les lieux et obéissent à leur maîtresse,
e qui a tendan
e à
optimiser le temps d'éva
uation. De plus, les meubles dans les salles de
ours ne sont pas
pris en
ompte alors que leur présen
e a pour eet d'améliorer la uidité des groupes.
Dans [HINT03℄, les tables dans les salles de
lasse n'étant pas négligées, les résultats ob-
tenus par simulation
oïn
ident mieux ave
les résultats expérimentaux.
Dans [KMKWS00℄ qui traite de l'éva
uation d'un navire, le temps de sortie de la première
personne est bien appro
hé mais
elui de la dernière (et don
le temps d'éva
uation) est
assez éloigné des résultats expérimentaux. Ces résultats sont améliorés dans [MKKKS01℄
grâ
e à quelques modi
ations. D'une part, le mouvement du bateau est pris en
ompte
en utilisant un fa
teur de rédu
tion de vitesse des individus (dépendant de l'a
élération
du navire). D'autre part, les dépla
ements des gens sont mieux appréhendés et sont ren-
dus dépendant des
onditions extérieures. Par exemple, lorsque les
onditions de visiblité
tel-00346035, version 1 - 10 Dec 2008
sont bonnes, les personnes traversant un
orridor ne rasent pas les murs dans le modèle,
quand elles savent qu'elles tournent au bout du
ouloir. En revan
he, en
as de mauvaise
visibilité, les personnes auront tendan
e à longer
es derniers.
Un autre modèle d'automates
ellulaires est utilisé pour simuler l'éva
uation d'une salle
+
[KS02℄ ou d'un avion [KKN 03℄. Dans
e modèle, les piétons peuvent se dépla
er sur 4
ases (en haut, en bas, à gau
he, à droite) suivant des probabilités de transition qui dé-
pendent de deux
hamps, statique noté S et dynamique noté D. Le premier indépendant
du temps
ara
térise l'attra
tivité d'une zone. Dans le
adre d'une éva
uation,
haque
ase
a une valeur de S qui dépend de sa distan
e à la sortie. Plus
elle-
i est petite, plus la
valeur est grande. Le se
ond
hamp D varie en fon
tion du temps et représente en quelque
sorte une tra
e virtuelle laissée par les piétons. Cette méthode s'inspire des automates
el-
lulaires modélisant les dépla
ements de fourmis. Ces dernières déposent des phéromones
pour que leurs
ongénères puissent les suivre (pour plus de détails voir [SKN03℄). À l'ins-
tant initial, le
hamp D est nul sur toutes les
ases et dès qu'un piéton arrive sur une
ase,
il augmente la valeur de D de 1 pour
elle-
i. D'autre part, le
hamp D diuse selon la
probabilité α et se détériore selon la probabilité δ . Finalement, la probabilité de transition
pour aller sur la
ase (i, j) est
al
ulée
omme suit,
16
1.1. Etat de l'art
une méthode de mise à jour parallèle des positions. Pour insister sur la
ompétition entre
individus, ils introduisent, lorsque les personnes essaient d'atteindre la même
ase, un
paramètre de fri
tion qui est la probabilité que tout le monde reste à sa pla
e. D'autres
modèles utilisant des graphes orientés [BT86a, BT86b, Løv94, YS89℄ et déjà détaillés
tel-00346035, version 1 - 10 Dec 2008
dans la sous-se
tion 1.1.2 sont aussi employés pour simuler des situations d'éva
uation.
Toutefois, d'après [HMFB01℄,
es modèles ne permettent pas de retrouver les phénomènes
de formations d'ar
hes pré
édemment évoqués.
Remarque 1.2 Dans le
as d'une éva
uation d'urgen
e, il est beau
oup plus di
ile de
omparer les résultats numériques à des données réelles quasiment inexistantes. De plus,
re
réer la panique lors d'une expérien
e ave
des personnes volontaires n'est pas non plus
hose aisée puisque bien évidemment il n'est pas question que des gens se blessent lors
de
es tests. Dans [MBM96℄, deux expérien
es d'éva
uation d'un avion ont été menées
ave
60 personnes environ. Dans la première expérien
e, on demandait aux gens de sortir
rapidement, dans la se
onde, on donnait de l'argent aux 30 premiers sortis. La largeur
de la porte de sortie était inférieure à 70 cm. Le temps d'éva
uation dans le premier
as s'est avéré bien inférieur à
elui mesuré dans le se
ond : la surmotivation de tous les
individus est don
ontre-produ
tive. On s'attend à retrouver
e problème lors de situations
d'éva
uation d'urgen
e.
Ce
i termine la présentation des modèles employés pour simuler des situations d'éva
ua-
tion d'urgen
e. Ces derniers utilisent don
diérentes méthodes de gestion des
onta
ts.
Dans le modèle de for
es so
iales, les
onta
ts entre les individus sont gérés à l'aide de
for
es de répulsion,
hoisies très singulières,
e qui impose de fortes
ontraintes sur le pas
de temps utilisé lors de la résolution des équations diérentielles. Les modèles les plus
souvent utilisés (
ar moins
oûteux en temps de
al
ul) sont les modèles basés sur une
dis
rétisation spatiale (automates
ellulaires ou graphes orientés). Toutefois,
es derniers
qui ne gèrent pas dire
tement les
onta
ts entre les individus ne rendent pas véritable-
ment
ompte des fortes intera
tions lo
ales qui peuvent apparaître entre les piétons. Nous
dé
rivons maintenant le modèle qui fait l'objet du présent travail.
17
Chapitre 1. Diérents modèles pour représenter la foule
Nous proposons un modèle mi
ros
opique de mouvements de foule ayant pour prin
ipal
obje
tif de simuler des situations de
ongurations denses typiques des
as d'urgen
e. Ce
modèle repose sur deux prin
ipes :
1. haque personne a une vitesse souhaitée, elle qu'elle aurait en l'absen e des autres ;
2. la vitesse réelle des individus doit prendre en
ompte une
ertaine
ontrainte d'en-
ombrement maximal. Plus pré
isément, les personnes identiées à des disques ri-
gides, doivent respe
ter une
ontrainte de non-
hevau
hement.
Dans notre modèle, la vitesse réelle est la proje
tion de la vitesse souhaitée sur un ensemble
de vitesses admissibles (respe
tant la
ontrainte de non-
hevau
hement). Ce dernier point
permet de traiter dire
tement les
onta
ts entre les individus.
Pour pré
iser
es deux prin
ipes, nous introduisons quelques notations. Nous
onsidérons
N personnes assimilées à des disques rigides et évoluant dans un espa
e bidimensionnel
pouvant
ontenir des obsta
les. La personne i est représentée par le disque de
entre
qi = (qix , qiy ) ∈ R2 ri .
tel-00346035, version 1 - 10 Dec 2008
et de rayon Quant aux obsta
les présents (murs, tables, ...), ils sont
modélisés par un ensemble de segments. Ainsi,
ette représentation fournit en quelque
sorte une vue de dessus de la piè
e (
f. g. 1.11).
La
onguration des N piétons est donnée par le ve
teur position q = (q1 , . . . , qN ) ∈ R2N
(espa
e muni de la norme eu
lidienne). On note Dij la distan
e relative entre les personnes
i et j (
f g.1.12).
PSfrag repla
ements
rj
ri qj
qi
Dij (q)
18
1.2. Des
ription d'un nouveau modèle
Vitesse souhaitée
Le premier point du modèle
onsiste à
hoisir une vitesse souhaitée pour les individus.
Ce
hoix est très important puisque
ette vitesse
ontient toutes les informations sur le
omportement des piétons. Elle doit traduire dans quelle mesure la géométrie des lieux et
la présen
e d'autres personnes inuen
ent les dépla
ements d'un individu. D'une part, la
vitesse souhaitée d'un piéton dépend du lieu où
e dernier évolue. Il est par exemple es-
sentiel de prendre en
ompte les obsta
les présents dans une piè
e et de pré
iser
omment
les piétons vont vouloir les
ontourner. La vitesse souhaitée d'un individu est ainsi dé-
pendante de sa propre position dans la piè
e. Pour dé
rire
e fait, il existe de nombreuses
possibilités. Cette vitesse souhaitée peut par exemple être
onstruite à la main, et pour
traduire la présen
e d'un panneau de sortie, on peut donner des dire
tions privilégiées à
elle-
i. On peut aussi
her
her à dénir
ette dernière de manière systématique dès que la
géométrie est donnée. Nous avons par exemple
hoisi (
f. se
tion 5.2) de prendre
omme
vitesse souhaitée pour toutes les personnes la vitesse dirigée par le plus
ourt
hemin vers
une sortie, qui évite bien entendu les obsta
les (la norme de la vitesse étant xée).
D'autre part, la vitesse souhaitée d'un individu peut aussi dépendre de la présen
e des
autres piétons. Lorsque plusieurs
hemins sont possibles, les personnes pressées ont sou-
tel-00346035, version 1 - 10 Dec 2008
vent tendan
e à emprunter le
hemin le moins embouteillé. Il est tout à fait envisageable
de distinguer les piétons en les munissant de diérentes stratégies en
as de situation
engorgée (
f. se
tion 6.4). Toutefois, on prendra garde au fait que lors d'une éva
uation
d'urgen
e, les personnes en proie à la panique ne développent pas en général de stratégies
individuelles. Nous proposons d'autres
hoix dans le
hapitre 6, mais toute alternative
est possible, par exemple en s'inspirant des résultats obtenus lors d'études menées sur le
omportement piétonnier.
Supposons que la vitesse souhaitée des individus est
hoisie. On dénit Ui (q) ∈ R2 , la
vitesse souhaitée de la personne i, dépendant potentiellement de la
onguration globale
q. Le ve
teur vitesse des N personnes est noté
19
Chapitre 1. Diérents modèles pour représenter la foule
20
tel-00346035, version 1 - 10 Dec 2008
21
Première partie
Aspe
ts théoriques
tel-00346035, version 1 - 10 Dec 2008
Chapitre 2
Cadre mathématique et résultats
Sommaire
2.1 Reformulation . . . . . . . . . . . . . . . . . . . . . . . . . . 24
23
Chapitre 2. Cadre mathématique et résultats
2.1 Reformulation
Nous rappelons brièvement les notations introduites à la se
tion 1.2 et nous en intro-
duisons de nouvelles. La
onguration des N personnes assimilées à des disques rigides
est donnée par le ve
teur position q = (q1 , . . . , qN ) ∈ R2N . L'espa
e R2N est muni de sa
norme eu
lidienne,
v
u N
uX
|q| = t |q |2 , où |qi |2 = (qix )2 + (qiy )2 .
tel-00346035, version 1 - 10 Dec 2008
i
i=1
rj
eij (q)
ri qj
qi
Dij (q)
−eij (q)
Fig. 2.1 Notations.
De plus, pour tout q ∈ Q0 , on dénit (
f. g. 2.1) le ve
teur unitaire eij (q) se dirigeant
de la personne i vers la personne j,
omme suit,
qj − qi
eij (q) = .
|qj − qi |
24
2.1. Reformulation
Ce
i nous permet de pré
iser l'expression du ve
teur Gij (q), gradient de la fon
tion Dij
au point q :
Gij (q) = ∇Dij (q) = (0, . . . , 0, −eij (q) , 0, . . . , 0, eij (q) , 0, . . . , 0) ∈ R2N .
i j
Le ve
teur vitesse souhaitée des N personnes est noté U(q) = (U1 (q), . . . , UN (q)) . Pour
dénir la vitesse réelle, on introduit un ensemble de vitesses dites admissibles.
Dans le modèle, la vitesse réelle u des N individus est la proje
tion eu
lidienne de la
vitesse souhaitée U sur l'ensemble des vitesses admissibles Cq . Le modèle s'é
rit don
tel-00346035, version 1 - 10 Dec 2008
nalement : Z
q = q0 + u,
(2.1)
u = PCq U.
Remarque 2.4 Cette é
riture assez simple sous la forme d'une équation diérentielle
du premier ordre masque
ertaines di
ultés. L'ensemble Cq ne dépend pas
ontinûment
de q. En eet, lorsque la
onguration q ne présente au
un
onta
t, l'ensemble Cq est
l'espa
e R2N (il n'y a au
une
ontrainte sur la vitesse). Mais dès qu'apparaît un
onta
t,
et ensemble se transforme en un demi-espa
e.
Pour pré
iser le
adre mathématique dans lequel
e problème se situe, une reformulation
de (2.1) est né
essaire. On introduit pour q ∈ Q0 , le
ne Nq ,
ne polaire de Cq qu'on
appelle
ne normal sortant au point q. On expliquera
ette dénomination lors de la
remarque 2.7.
Grâ e au lemme de Farkas (lemme B.1 p. 146), l'expression du ne Nq peut être pré isée.
Proposition 2.6
( )
X
Nq = − µij Gij (q) , µij ≥ 0 , µij = 0 si Dij (q) > 0 .
i<j
25
Chapitre 2. Cadre mathématique et résultats
Démonstration :
Ce résultat est ee
tivement une
onséquen
e dire
te du lemme de Farkas. Toutefois, on
présente i
i une autre preuve qui s'appuie sur la notion de
ne polaire (
f. Annexe C
p. 149). On dénit Icontact = {(i, j) , i < j , Dij (q) = 0}. Le fait qu'un ve
teur v appar-
tienne à Cq est équivalent à la propriété suivante,
Ce i équivaut aussi à
X
∀µij ≥ 0 , µij Gij (q) · v ≥ 0.
(i,j)∈Icontact
Si on dénit
X
Fq = − µij Gij (q) , µij ≥ 0 ,
(i,j)∈Icontact
Fq◦ = Cq = Cq ◦◦ = Nq◦.
N q2
PSfrag repla
ements
D13 < 0
q2
q1
Cq1
Q0
26
2.1. Reformulation
deux
onta
ts. On remarque que dans le
as d'un unique
onta
t, le
ne Nq1 est engen-
dré par la normale sortante au domaine d'équation D34 ≥ 0, qui est le ve
teur −G34 (q1 )
renormalisé. Dans le
as de deux
onta
ts (ou plus), la
onguration q2 est un point où
la surfa
e est non lisse et le
ne Nq2 (engendré par −G12 (q2 ) et −G13 (q2 )) étend en
quelque sorte la notion de dire
tion normale sortante.
Réé
rivons maintenant le système (2.1). Grâ
e à la proposition C.3 p. 150, on peut expri-
mer la proje
tion sur Cq en fon
tion de la proje
tion sur Nq . On obtient ainsi que
u = PCq U = U − PNq U.
dq + P U(q) = U(q)
Nq
dt (E1 )
q(0) = q0 .
tel-00346035, version 1 - 10 Dec 2008
En é
rivant que PNq U ∈ Nq , on obtient la relation suivante entre vitesse réelle et vitesse
souhaitée :
dq + N ∋ U(q),
q
dt (E2 )
q(0) = q0 .
On aboutit don
à une in
lusion diérentielle du premier ordre faisant intervenir l'opéra-
teur multivalué (ou multivoque) N , qui à un point q ∈ R asso
ie le
ne Nq ⊂ R
2N 2N
dq
= U(q).
dt
Quand il n'y a pas de
onta
t, il n'existe pas de
ontraintes et la vitesse réelle est égale à
la vitesse souhaitée. Lorsque des
onta
ts existent, l'in
lusion diérentielle traduit juste
le fait suivant : la
onguration q qui est soumise au
hamp U(q), doit évoluer tout en
restant dans Q0 .
Remarque 2.9 L'é
riture de notre problème sous la forme d'une in
lusion diérentielle
(E2 ) implique une perte d'information par rapport au problème de départ (E1 ). Cependant
on verra que dans le
as parti
ulier de la se
tion 2.2 (
as où les personnes se dépla
ent
dans un
ouloir)
es deux é
ritures sont en fait équivalentes. La solution régulière du
problème d'in
lusion diérentielle vérie bien l'équation diérentielle initiale.
27
Chapitre 2. Cadre mathématique et résultats
Dans
ette se
tion, on
onsidère un
as parti
ulier où des personnes évoluent dans un
ouloir si étroit qu'elles ne peuvent se dépasser (
f. g. 2.3). Les
entres des disques sont
alors repérés par une seule
oordonnée : on travaille maintenant dans l'espa
e RN . Il est
alors naturel de restreindre Q0 à l'une de ses
omposantes
onnexes.
Autrement dit, on a imposé un ordre sur la position des parti
ules, ordre qui sera toujours
respe
té, grâ
e à la
ontrainte de non-
hevau
hement. On observe fa
ilement la propriété
tel-00346035, version 1 - 10 Dec 2008
suivante.
L'interprétation est simple : si les personnes i et i+1 sont en
onta
t, la personne i+1
qui se trouve à l'avant doit avan
er plus vite que la personne i située à l'arrière. De plus,
on rappelle que le
ne normal sortant Nq est le
ne polaire de Cq ,
'est-à-dire que
Nq = {w ∈ RN , ∀v ∈ Cq , v · w ≥ 0}. (2.4)
Démonstration : [
On
ommen
e par montrer une première in
lusion : λ (Q0 − q) ⊂ Cq .
[ λ>0
Soit w∈ λ (Q0 − q),
omme
λ>0
Q0 − q = p ∈ RN , ∀i pi+1 − pi ≥ ri+1 + ri − (qi+1 − qi ) ,
28
2.2. Cas parti
ulier : dépla
ement dans un
ouloir
Dans les deux as, l'inégalité est vériée, e qui prouve que
w ∈ λw (Q0 − q).
La deuxième in
lusion est ainsi démontrée.
Nous allons maintenant pré
iser la bonne propriété vériée par l'opérateur N. Pour
ela,
on introduit IQ0 l'indi
atri
e de Q0 et ∂IQ0 (q) le sous-diérentiel de
ette fon
tion au
point q ∈ R
N
(
f. dénitions A.2 et A.3 p. 142).
Dès lors, on peut appliquer les résultats de la théorie des opérateurs maximaux monotones
pour en déduire que le problème (E2 ) est bien posé.
29
Chapitre 2. Cadre mathématique et résultats
Théorème 2.13 (Existen
e et uni
ité d'une solution à l'in
lusion diérentielle)
Soit Q0 déni par (2.2) p. 28 et soit U lips
hitz, alors
pour tout T > 0, pour tout q0 ∈ Q0 ,
il existe une unique fon
tion q ∈ W 1,1
[0, T ], R solution de
N
dq + N − U (q) ∋ 0,
q
dt (E2 )
q (0) = q0 ,
On peut maintenant vérier
e qui était annon
é dans la remarque 2.9 p. 27, à savoir que
tel-00346035, version 1 - 10 Dec 2008
la solution pré
édente au problème d'in
lusion diérentielle (E2 ) est en fait solution de
l'équation diérentielle (E1 ).
dq + P (U (q)) = U (q) ,
Nq
dt (E1 )
q (0) = q0 ,
dp + N ∋ f,
p
dt
p (0) = q0 .
D'après le théorème D.5 p. 154, il existe une unique solution p ∈ W 1,∞ ([0, T ], H) à
e
problème d'in
lusion diérentielle. De plus,
ette fon
tion p possède une dérivée à droite
en tout point t ∈]0, T [ vériant
d+ p
(t) = f (t) − PNp(t) (f (t)).
dt
30
2.3. Problèmes ren
ontrés lors de la généralisation
Comme p ∈ W 1,∞ ([0, T ], H), la fon
tion p est lips
hitzienne et elle est don
dérivable
presque partout, d'après le théorème de Radema
her. Ainsi, on obtient
dp
(t) = f (t) − PNp(t) (f (t)) p.p.
dt
Par uni
ité de la solution au problème d'in
lusion diérentielle (E2 ) et sa
hant que
W 1,∞ ([0, T ], H) ⊂ W 1,1 ([0, T ], H)
ar T < ∞, on
on
lut que p = q. Par
onséquent, on
obtient
dq
(t) = U(q(t)) − PNq(t) (U(q(t))) p.p.
dt
La simple généralisation des pré
édents résultats est impossible quand on permet aux
N personnes de se dépla
er dans le plan. L'ensemble des
ongurations admissibles dont
tel-00346035, version 1 - 10 Dec 2008
on rappelle l'expression :
Q0 = q ∈ R2N , ∀i < j , Dij (q) ≥ 0 ,
PSfrag repla
ements
n'est pas un ensemble
onvexe. En eet sur la gure 2.4, sont représentées trois
ongu-
rations, q et e
q ainsi que leur moyenne q̄. On voit fa
ilement que q et e
q appartiennent
q̃2 q̄2
q1 q2 q̄1
q̃1
q+qe
onguration q
onguration q
e
onguration q̄ =
2
Fig. 2.4 Défaut de
onvexité.
à Q0 , mais pas q̄. En
onséquen
e, l'argument (
f. propriété 2.10) faisant le lien entre
l'opérateur N et Q0 ne peut être réutilisé.
Montrons pour nir
ette se
tion que l'opérateur N n'a plus de propriété de monoto-
nie (
f. dénition D.2 p. 154).
Dans le
as de N = 2 personnes, on peut montrer que l'opérateur −N est maximal
monotone. En eet, quand on
onsidère uniquement 2 individus,
Q0 = {q ∈ R4 , D12 (q) ≥ 0}
est alors le
omplémentaire d'un
onvexe, puisque D12 est une fon
tion
onvexe. Si on
dénit C = {q ∈ R , D12 (q) ≤ 0}, alors on a Nq = −∂IC (q). Par
onséquent, −N est
4
31
Chapitre 2. Cadre mathématique et résultats
q̃2
q̃3
tel-00346035, version 1 - 10 Dec 2008
α
PSfrag repla
ements
q1 = q̃1 q2
q3
Par onséquent,
32
2.4. Cadre mathématique
Ainsi,
n − n, q
(e e − q) = − cos α (2 cos α − 2) − sin α (2 sin α − b)
= −2 cos2 α + 2 cos α − 2 sin2 α + b sin α
= 2 cos α − 2 + b sin α
= 2(cos α − 1) + b sin α.
On remarque que, si α est positif, pro
he de 0,
ette quantité a le même signe que b. En
on
lusion, ni N, ni −N n'est un opérateur monotone.
Pré
isons maintenant
ette notion. On
onsidère H un espa
e de Hilbert, muni de son
produit s
alaire h, i et on note || sa norme assso
iée. Pour x∈H et r > 0, on désigne
par B(x, r) la boule ouverte de
entre x et de rayon r . Soit S un sous-ensemble fermé non
vide de H , on note dS (y) la distan
e du point y à l'ensemble S , dénie par
De plus, pour y∈H on dénit l'ensemble des points de S, les plus pro
hes de y par,
n o
PS (y) = x ∈ S, dS (y) = |y − x| .
33
Chapitre 2. Cadre mathématique et résultats
y
x
PSfrag repla
ements
Dénition 2.16 On appelle
ne proximal normal à S en x l'ensemble des ve
teurs proxi-
mal normal à S en x noté
n o
N P (S, x) = v ∈ H, ∃α > 0, x ∈ PS (x + αv) .
tel-00346035, version 1 - 10 Dec 2008
◦
Si x ∈ S, alors N P (S, x) = N L (S, x) = {0}. On
her
hera don
à déterminer N P (S, x) et
◦
L
N (S, x) pour x ∈ ∂S = S̄ \ S .
Remarque 2.18 On a
lairement
N P (S, x) ⊂ N L (S, x).
Mais il n'y a pas en général égalité de
es ensembles. En eet, la gure 2.7 illustre un
ontre-exemple dans lequel N L (S, x) est
omposé de demi-deux droites (tra
ées en poin-
tillé). L'une provient de la limite de vn1 quand x1n tend vers x, l'autre provient de la
limite de vn2 quand x2n tend vers x. Et pourtant, on peut fa
ilement se
onvain
re que
N P (S, x) = {0}.
Démonstration :
En eet, en supposant qu'il existe β0 < α, tel que x∈
/ PS (x + β0 v), on peut trouver x̄ un
élément de S vériant
|x̄ − (x + β0 v)| < β0 |v|.
34
2.4. Cadre mathématique
N L (S, x)
vn2
PSfrag repla
ements
x2n vn1
x x1n
Ce i implique que
|x̄ − (x + αv)| ≤ |x̄ − (x + β0 v)| + |(β0 − α)v| < β0 |v| + (α − β0 )|v| = α|v|,
tel-00346035, version 1 - 10 Dec 2008
Les dénitions pré
édentes des diérents
nes et la dénition qui suit, se trouvent dans
[CSW95, CLSW98℄.
Pré
isons la relation utile par la suite entre le sous-diérentiel proximal normal et le
ne
du même nom, qui est démontrée dans [BT02, CLSW98℄.
35
Chapitre 2. Cadre mathématique et résultats
η
x
PSfrag repla
ements
S
Proposition 2.23 Soit η > 0, S est η-prox-régulier si et seulement si, pour tout x ∈ S
tel-00346035, version 1 - 10 Dec 2008
De la proposition 2.23 illustrée par la gure 2.8, dé
oule la propriété vériée par un
ensemble uniformément prox-régulier et qui était annon
ée au début de la se
tion : la
proje
tion sur un ensemble S uniformément prox-régulier est bien dénie pour les points
se situant à une distan
e de S , plus petite que la
onstante de prox-régularité.
Propriété 2.24 Si S est η -prox-régulier, alors pour tout y ∈ H , tel que dS (y) < η , la
proje
tion de y sur S est bien dénie, au sens où l'ensemble PS (y) est un singleton.
Remarque 2.25 La proje
tion sur un ensemble S η-prox-régulier ave
η < +∞ n'est que
lo
alement lips
hitzienne sur son ensemble de dénition. En eet, on peut montrer grâ
e
à la proposition 2.23 que pour tous y, ỹ ∈ H , tels que dS (y) < η et dS (ỹ) < η , on a
2η
|PS (y) − PS (ỹ)| ≤ |y − ỹ|.
2η − dS (y) − dS (ỹ)
La onstante de Lips hitz explose lorsque l'on s'appro he de la zone {y, dS (y) = η}.
36
2.4. Cadre mathématique
On propose i
i de pré
iser
ette notion, tout d'abord en détaillant le premier pro
essus
de rae
onsidéré dans les années 70, et ensuite en évoquant des résultats plus ré
ents sur
des problèmes de pro
essus de rae plus généraux.
Le début
Les pro
essus de rae ont été introduits par J.J. Moreau dans [Mor77℄. Il
onsidérait le
problème suivant : un point se trouve à l'intérieur d'un
onvexe fermé C mobile in
lus
dans un espa
e de Hilbert. Quand il est attrapé par le bord de C qui se dépla
e, il part
dans la dire
tion normale à
elui-
i,
omme s'il était poussé par le bord, an de rester
dans C. Le mouvement de
e point est alors régi par l'équation suivante :
Celle-
i fait intervenir un opérateur maximal monotone qui dépend du temps. Pour ré-
soudre
e problème, J.J. Moreau
onstruit une suite de solutions dis
rètes selon un prin-
ipe dit de rattrapage (
at
hing-up ). Sous
ertaines hypothèses de régularité de la fon
tion
multivaluée t 7→ C(t), l'intervalle de temps est divisé en sous-intervalles Jk où C(·) varie
peu. La traje
toire d'ensembles t 7→ C(t) est appro
hée par une multifon
tion
onstante
par mor
eaux, valant Ck sur Jk ,
e qui permet de
onstruire une fon
tion q̃
onstante par
mor
eaux, égale à q̃k sur Jk et telle que q̃k+1 = PCk+1 (q̃k ). Il démontre alors la
onver-
gen
e de
ette suite de fon
tions lorsque le pas de la subdivision tend vers zéro, obtenant
à la limite une solution de (2.6). La solution a au moins la même régularité que
elle de
la multifon
tion C(·). D'après la remarque 2.26 p. 37, l'équation (2.6) s'é
rit aussi
Cependant, notre problème (E2 ) ne rentre pas dans
e
adre, d'une part, à
ause du défaut
de
onvexité de Q0 , et d'autre part, à
ause de la présen
e du se
ond membre U(q).
37
Chapitre 2. Cadre mathématique et résultats
q̃k
q̃k+1 Ck
PSfrag repla
ements
Ck+1
Fig. 2.9 Algorithme de rattrapage.
Le problème général
Introduisons plus généralement un pro
essus de rae dit perturbé, mettant en jeu des
ensembles C(t) non vides η -prox-réguliers, in
lus dans un espa
e de Hilbert réel H . On
pose le problème de l'existen
e et de l'uni
ité d'une fon
tion x dénie sur I = [T0 , T ] et
tel-00346035, version 1 - 10 Dec 2008
vériant, (
−ẋ(t) ∈ N(C(t), x(t)) + F (t, x(t)) p.p.t. t ∈ I
(2.8)
x(T0 ) = x0 .
La perturbation F : [T0 , T ] × H ⇉ H est une appli
ation multivaluée à valeurs dans
les ensembles
onvexes
ompa
ts non vides de H. L'ensemble N(C(t), x(t)) est le
ne
proximal normal de C(t) au point x(t) (
f. dénition 2.16 p. 34).
Dans [CM95℄, les auteurs étudient
e problème perturbé en dimension nie dans le
as
où les ensembles C(t) sont
onvexes. Ils montrent que le problème admet des solutions
sous
ertaines hypothèses
on
ernant la perturbation F et l'appli
ation multivaluée C.
D'une part, la perturbation F est supposée semi-
ontinue supérieurement par rapport
à la se
onde variable et doit satisfaire une
ondition de
roissan
e linéaire
ompa
te, à
savoir :
F (t, x) ⊂ β(t)(1 + |x|)B(0, 1) , ∀(t, x) ∈ [T0 , T ] × H. (2.9)
D'autre part, l'appli
ation multivaluée C est supposée
ontinue pour la distan
e de Haus-
dor et doit satisfaire une
ondition de boule intérieure, du type suivant :
où dx est la mesure diérentielle de la fon
tion x. L'existen
e et l'uni
ité d'une fon
tion
à variation bornée solution de (2.11) est prouvée, en supposant que C(·) est Hausdor-
ontinue, ave
une
ondition de boule intérieure (semblable à (2.10)) et une
ondition de
38
2.4. Cadre mathématique
Théorème 2.27 Soit H un espa
e de Hilbert. On
onsidère l'appli
ation multivaluée C(·)
de I = [T0 , T ] dans H vériant les hypothèses suivantes
(H1 ) Il existe η > 0, tel que pour tout t ∈ I , C(t) soit un sous-ensemble fermé non
vide de H, η -prox-régulier ;
(H2 ) C(t) varie d'une façon absolument
ontinue,
'est-à-dire qu'il existe une fon
tion
absolument
ontinue v : I → R, telle que pour tout y ∈ H et pour tous s, t ∈ I , on
ait
|dC(t) (y) − dC(s) (y)| ≤ |v(t) − v(s)|.
tel-00346035, version 1 - 10 Dec 2008
Soit une fon
tion f : I × H → H telle que ∀x ∈ H , f (·, x) soit mesurable sur I et
vériant,
(i) Pour tout α > 0, il existe une fon
tion positive kα ∈ L1 (I, R) telle que pour tout
t ∈ I et (x, y) ∈ B(0, α) × B(0, α),
(ii) Il existe une fon
tion positive β ∈ L1 (I, R), telle que pour tout t ∈ I et pour tout
x ∈ ∪s∈I C(s), |f (t, x)| ≤ β(t)(1 + |x|).
Alors, pour tout x0 ∈ C(T0 ), le pro
essus de rae suivant
(
−ẋ(t) ∈ N(C(t), x(t)) + f (t, x(t)) p.p.t. t ∈ I
x(T0 ) = x0
Remarque 2.28 L'hypothèse (H2) n'est pas né
essaire pour assurer l'existen
e de solu-
tions. Par exemple, dans [ET06℄, le problème
onsidéré est le suivant,
(
−dx ∈ N(C(t), x(t)) + F (t, x(t))dλ
(2.12)
x(T0 ) = x0 ,
39
Chapitre 2. Cadre mathématique et résultats
et telle que
η
sup µ({s}) < . (2.14)
s∈]T0 ,T ] 2
La démonstration utilise l'algorithme de rattrapage introduit par J.J. Moreau. Le point
fondamental est de diviser l'intervalle de temps I en sous-intervalles Ik =]tk , tk+1 ] où
C(·) varie peu. Ce
i est ee
tivement né
essaire pour passer à la limite mais aussi pour
ee
tuer à
haque instant les proje
tions (qui ne sont possibles qu'à distan
e stri
tement
inférieure à η ). Si l'hypothèse (2.13) permet le dé
oupage de I en sous-intervalles ouverts
où C(·) varie peu, l'obtention d'intervalles semi-ouverts se fait grâ
e à l'hypothèse (2.14).
tel-00346035, version 1 - 10 Dec 2008
Nous pouvons à présent énon
er le théorème essentiel qui assure le
ara
tère bien posé du
modèle introduit au début de
e
hapitre.
Théorème 2.30 (Existen
e et uni
ité d'une solution de l'in
lusion diérentielle)
Soit Q0 l'ensemble des
ongurations admissibles (
f. dénition 2.1 p. 24) et soit U lip-
s
hitzienne et bornée, alors pour tout T > 0, pour tout q0 ∈ Q0 , il existe une unique
fon
tion q absolument
ontinue sur [0, T ], solution de
dq + N ∋ U(q),
q
dt (E2 )
q(0) = q0 ,
Démonstration :
Ce résultat dé
oule du théorème 2.27 p. 39. Les hypothèses (i) et (ii) de
e dernier
viennent du
ara
tère lips
hitzien et bornée de U. L'hypothèse (H2 ) est trivialement
vériée dans notre
as. Il reste don
à vérier l'hypothèse (H1 ) (uniforme prox-régularité
de Q0 ) et l'égalité entre le
ne normal sortant Nq et le
ne proximal normal N(Q0 , q).
Ces résultats dont la démonstration est assez te
hnique, font l'objet du
hapitre suivant
(proposition 3.12 p. 51 et proposition 3.9 p. 48 respe
tivement).
40
Chapitre 3
Prox-régularité de l'ensemble des
ongurations admissibles Q0
Sommaire
tel-00346035, version 1 - 10 Dec 2008
41
Chapitre 3. Prox-régularité de l'ensemble des
ongurations admissibles Q0
Dans
e
hapitre, nous proposons de justier que l'ensemble des
ongurations admis-
sibles Q0 est uniformément prox-régulier et de déterminer son
ne proximal normal (
f.
dénition 2.16 p. 34) an de terminer la preuve du théorème 2.30 p. 40. Pour
ela, on
dénit pour i < j,
Ainsi,
\
Q0 = q = (q1 , q2 , .., qN ) ∈ R2N , Dij (q) ≥ 0, ∀(i, j), i < j = Qij .
i<j
Dans un premier temps, nous étudions l'ensemble Q12 , qui ne présente qu'une seule
ontrainte. Nous donnons l'expression de son
ne proximal normal et montrons que
et ensemble est uniformément prox-régulier en
al
ulant pré
isément sa
onstante de
prox-régularité. Nous en déduisons dans un se
ond temps, l'expression du
ne proximal
normal de Q0 et prouvons le
ara
tère uniformément prox-régulier de Q0 en donnant une
minoration η de sa
onstante de prox-régularité. Enn, nous proposons de fournir une
tel-00346035, version 1 - 10 Dec 2008
majoration de
ette
onstante η. Celle-
i n'est pas à proprement parler la
onstante op-
timale de prox-régularité de Q0 , mais sa majoration permet de suggérer une dépendan
e
de la
onstante optimale par rapport aux données du problème (à savoir le nombre de
personnes N et les rayons ri des disques les représentant).
Proposition 3.1
∂Q12 = {q ∈ R2N , D12 (q) = 0}
est une hypersurfa
e de
lasse C 2 orientable de R2N .
Démonstration :
On dénit pour ε < r1 + r2 , l'ouvert
La fon
tion D12 est de
lasse C2C ∞ ) sur Uε et en tout point q ∈ Uε , le gradient
(même
de D12 ne s'annule pas,
ar il vaut ∇D12 (q) = G12 (q) 6= 0. Par
onséquent, ∂Q12 est
une sous-variété diérentiable de R
2N 2
, de
lasse C et de dimension 2N − 1, autrement
42
3.1. Etude de l'ensemble Q12
dit
'est une hypersurfa
e de
lasse C2 de R2N . De plus,
omme en tout point q ∈ Uε , la
diérentielle de D12 ne s'annule pas, on peut dénir une normale à ∂Q12 par
−G12 (q)
ν(q) = √ .
2
Ainsi, ∂Q12 est orientable. Le signe a été
hoisi de telle sorte que
e ve
teur soit une
normale extérieure à Q12 .
Cette propriété, vériée par l'ensemble Q12 , va nous permettre d'exprimer son
ne proxi-
mal normal en utilisant le résultat de la proposition suivante.
N(S, x) = R+ ν(x).
tel-00346035, version 1 - 10 Dec 2008
Démonstration :
Soit x ∈ ∂S ,
omme ∂S est une hypersurfa
e de
lasse C 2 , il existe un ouvert U de Rn
ontenant x et une fon
tion f ∈ C (U, R) tels que
2
∃α > 0 , ∀β ≤ α , x ∈ PS (x + βν(x)),
∃α > 0 , ∀β ≤ α , dS (x + βν(x)) = β.
Raisonnons par l'absurde en supposant qu'il existe une suite (βk ) tendant vers zéro telle
que
dS (x + βk ν(x)) < βk .
Par
onséquent, pour tout k, il existe rk ∈ ∂S , vériant
43
Chapitre 3. Prox-régularité de l'ensemble des
ongurations admissibles Q0
(x − rk ) · ∇f (x) = O(|x − rk |2 ),
et ainsi
(x − rk ) · ν(x) = O(|x − rk |2 ).
Autrement dit, il existe K1 ≥ K0 et λ>0 tels que pour tout k ≥ K1 , on ait
Comme la suite (βk ) tend vers zéro, on sait qu'il existe K2 ∈ N tel que pour tout k ≥ K2 ,
on ait
1
βk < .
2λ
Ainsi, pour tout k ≥ max(K1 , K2 ), on a |x − rk |2 < 0,
e qui est absurde.
N(S, x) ⊂ R+ ν(x).
Soit v ∈ N(S, x) de norme 1, on raisonne par l'absurde en supposant que v 6= ν(x). Tout
d'abord, on peut justier que
v 6= −ν(x).
En eet, pour α>0 pro
he de 0, on a
−ν(x) ∈
/ N(S, x).
44
3.1. Etude de l'ensemble Q12
On s'aperçoit don
que pour tout β > 0, pour δ > 0 assez petit, le point γ(δ) de S est
à distan
e stri
tement inférieure à β du point x + βv. Par
onséquent, pour tout β > 0,
x∈
/ PS (x + βv) et v∈
/ N(S, x), d'où la
ontradi
tion.
Grâ
e aux propositions 3.1 et 3.2, on obtient l'expression du
ne proximal normal de Q12
en tout point de sa frontière.
3.1.2 Prox-régularité
D'après la proposition 2.23 p. 36, la prox-régularité se
ara
térise par une
ondition
de boule extérieure, la
onstante de prox-régularité étant égale au rayon maximal de
ette
boule. Comme Q12 est le
omplémentaire d'un
onvexe lisse, on peut
al
uler
e rayon
en utilisant des outils de géométrie diérentielle. Plus pré
isément,
elui-
i s'exprime en
fon
tion des
ourbures prin
ipales de S qui sont, par dénition, les valeurs propres de
l'opérateur de Weingarten. Pour montrer que Q12 est uniformément prox-régulier, on va
utiliser le théorème suivant, dont la démonstration peut être trouvée dans [Del79℄.
Théorème 3.5 Soit C un sous-ensemble
onvexe fermé de Rn telle que ∂C soit une
hypersurfa
e de Rn , de
lasse C 2 et orientable. On note νC (x) la normale extérieure à C
en x et µ1 (x), .., µn−1(x) ≥ 0 les
ourbures prin
ipales de C en x. On suppose que
µ = sup sup µi (x) < ∞.
x∈∂C 1≤i≤n−1
◦ 1
Alors S = Rn \ C est un ensemble η -prox-régulier ave
η = .
µ
r1 + r2
Proposition 3.6 L'ensemble Q12 est η-prox-régulier ave
η = √ .
2
Démonstration :
2
D'après la proposition 3.1, ∂Q12 est une hypersurfa
e de
lasse C orientable et l'ensemble
C = {q ∈ R , D12 (q) ≤ 0} est un sous-ensemble fermé
onvexe de R2N , par
onvexité
2N
◦
Q12 = R2N \ C.
45
Chapitre 3. Prox-régularité de l'ensemble des
ongurations admissibles Q0
Dans toute la suite, on
onsidère q ∈ ∂Q12 . On a déni pré
édemment la normale à ∂Q12
en
e point de la façon suivante,
ν: ∂Q12 → S2N −1
G12 (q) (e12 (q), −e12 (q), 0, ..0) .
q = (q1 , q2 , .., qN ) →
7 − √ = √
2 2
Dans la suite, le ve
teur e12 (q) sera noté e12 . La normale extérieure à C en q est
don
égale à −ν(q). Déterminons les valeurs propres de l'endormorphisme de Weingar-
ten Wq : h ∈ Tq (∂Q12 ) 7→ −Dν(q)[h]. D'après la proposition E.1 p. 156, on a pour tout
h ∈ Tq (∂Q12 )
1
−Dν(q)[h] = √ −Pe⊥12 (h2 − h1 ), Pe⊥12 (h2 − h1 ), 0, . . . , 0 ,
2|q2 − q1 |
Pe⊥
12
(h2 − h1 ) = (h2 − h1 ) − [(h2 − h1 ) · e12 ]e12 = (e⊥ t ⊥
12 e12 )(h2 − h1 ).
!
Aq 0
Wq = ,
0 0
ave
!
1 e⊥ t ⊥
12 e12 −e⊥ t ⊥
12 e12
Aq = √ .
2|q2 − q1 | −e⊥ t ⊥
12 e12 e⊥ t ⊥
12 e12
2
√ Tr e⊥ t ⊥
12 12 .
e
2|q2 − q1 |
Comme le ve
teur e⊥
12 est unitaire, on a
Tr e⊥ t ⊥
12 e12 = 1,
et par
onséquent
√
2
Tr(Wq ) = .
|q2 − q1 |
De plus, la matri
e Wq est de même rang que la matri
e Aq
qui est de rang 1. On peut
⊥ ⊥
même pré
iser que l'image de Wq est engendrée par le ve
teur τ (q) = (e12 , −e12 , 0, . . . , 0).
Wq a don
2 valeurs propres 0 et a, ave
√
2
a= ,
|q2 − q1 |
46
3.2. Généralisation à Q0
|q2 − q1 |
rc = √ .
2
Comme q ∈ ∂Q12 , on en déduit que
r1 + r2
rc = √ .
2
Grâ
e au théorème 3.5, on
on
lut que l'ensemble Q12 est η -prox-régulier ave
r1 + r2
η= √ .
2
On a bien sûr les mêmes résultats
on
ernant l'expression du
ne proximal normal et le
ara
tère uniformément prox-régulier des autres ensembles Qij (i < j ) dont on rappelle
tel-00346035, version 1 - 10 Dec 2008
la dénition,
Qij = {q = (q1 , q2 , .., qN ) ∈ R2N , Dij (q) = |qj − qi | − (ri + rj ) ≥ 0}. (3.3)
Remarque 3.8 On peut démontrer les propositions 3.3 et 3.6 sans utiliser des notions
de géométrie diérentielle (voir annexe F).
3.2 Généralisation à Q0
On rappelle que l'ensemble des
ongurations admissibles Q0 est l'interse
tion des
ensembles Qij dénis par (3.3).
qui apparaît dans le problème (E2 ) est bien le ne proximal normal de Q0 au point q.
47
Chapitre 3. Prox-régularité de l'ensemble des
ongurations admissibles Q0
P
Proposition 3.9 Soit q ∈ Q0 , on a N(Q0 , q) = N(Qij , q) = Nq .
Démonstration : ◦
La deuxième égalité dé
oule de la proposition 3.7. Prouvons la première. Si q ∈ Q0 , alors
◦
q ∈ Qij , pour tout
ouple (i, j). D'où,
X
N(Q0 , q) = {0} = N(Qij , q).
On
onsidère maintenant q ∈ ∂Q0 . On note (sans pré
iser la dépendan
e par rapport
à q)
Icontact = {(i, j), i < j, Dij (q) = 0} = {(i, j), i < j, q ∈ ∂Qij }. (3.4)
∃M, α > 0, dQij (q̃) − dQij (q) + M|q̃ − q|2 ≥ v · (q̃ − q), ∀q̃ ∈ B(q, α).
∃M, α > 0, dQ0 (q̃) − dQ0 (q) + M|q̃ − q|2 ≥ v · (q̃ − q), ∀q̃ ∈ B(q, α).
Ainsi, v ∈ ∂ P dQ0 (q) et w ∈ N(Q0 , q). Par
onséquent, pour tout
ouple (i, j) ∈ Icontact ,
on a
N(Qij , q) ⊂ N(Q0 , q).
X
N(Qij , q) ⊂ N(Q0 , q).
w
v= ,
|w1 | + |w2 |
48
3.2. Généralisation à Q0
|w1 |
t= .
|w1 | + |w2 |
On pose α = min(α1 , α2 ) et M = tM1 + (1 − t)M2 , on a don
dQ0 (q̃) − dQ0 (q) + M|q̃ − q|2 ≥ v · (q̃ − q), ∀q̃ ∈ B(q, α).
Autrement dit, v ∈ ∂ P dQ0 (q) et w ∈ N(Q0 , q). On a don
démontré l'in
lusion suivante,
X
N(Q0 , q) ⊃ N(Qij , q).
Etape 3 : Il reste à montrer l'autre in
lusion. Pour
ela, on utilisera les propriétés de deux
P
nes mutuellement polaires (
f. annexe C). En eet, N(Qij , q) = Nq et par dénition,
Nq est le
ne polaire de Cq . Soit w ∈ N(Q0 , q), il s'é
rit w = v + z, où v et z sont les
proje
tions de w, respe
tivement sur Nq et Cq . On rappelle que
es proje
tions vérient
v · z = 0. (3.5)
tel-00346035, version 1 - 10 Dec 2008
Supposons que z 6= 0. Comme w ∈ N(Q0 , q) par hypothèse, il existe t > 0, tel que
q ∈ PQ0 (q + tw). On pose
Dij (q)
s = min(t, ǫ) où ǫ= min √ .
(i,j)∈I
/ contact 2|z|
D'après la proposition 2.19 p. 34,
omme s ≤ t, q ∈ PQ0 (q + sw). On note
q̃ = q + sw − sv = q + sz.
Montrons que q̃ ∈ Q0 . Par
onvexité de Dij , on a
∀(i, j) ∈ Icontact , Dij (q̃) ≥ Dij (q) + s Gij (q) · z = s Gij (q) · z ≥ 0.
Dij (q)
D'autre part, si (i, j) ∈
/ Icontact , alors s≤ √ . D'où,
2|z|
√
Dij (q̃) ≥ Dij (q) + s Gij (q) · z ≥ Dij (q) − s 2|z| ≥ 0.
Don
q̃ ∈ Q0 . Ainsi, dQ0 (q + sw) ≤ |q + sw − q̃| = s|v|. Or |q + sw − q| = s|w| > s|v|
2 2 2
ar |w| = |v| + |z| d'après (3.5). Par
onséquent, q ∈ / PQ0 (q + sw),
e qui est absurde.
Finalement, z = 0 et w = v ∈ Nq . Ce
i prouve la deuxième in
lusion.
Remarque 3.10 Les arguments-
lé de
ette démonstration sont la
onvexité des fon
-
tions Dij , le
ara
tère borné des Gij et le fait que dQ0 (q) ≥ dQij (q), ∀q, ∀(i, j).
Remarque 3.11 On retrouve le résultat déjà évoqué dans le
as parti
ulier du
ouloir
(
as où Q0 est
onvexe). En eet, on avait montré que pour tout q ∈ Q0 , Nq = ∂IQ0 (q)
(
f. (2.5) p. 29). Et d'après la proposition A.8 p. 144, on a l'égalité ∂IQ0 (q) = N(Q0 , q).
49
Chapitre 3. Prox-régularité de l'ensemble des
ongurations admissibles Q0
3.2.2 Prox-régularité
On souhaite i
i démontrer le
ara
tère uniformément prox-régulier de Q0 . On a vu
(
f. théorème 3.5 p. 45) que les
omplémentaires de
onvexes lisses sont uniformément
prox-réguliers. On peut se demander si l'interse
tion de tels ensembles (
as de Q0 ) n'est
pas uniformément prox-régulière ave
une
onstante de prox-régularité qui dépendrait des
onstantes de prox-régularité de
es ensembles. En général,
e
i est faux
omme l'illustre
la gure 3.1. Sur
elle-
i, on a tra
é en trait plein les frontières d'un ensemble S qui
est l'interse
tion des
omplémentaires de deux disques de même rayon. Cet ensemble
est uniformément prox-régulier mais sa
onstante de prox-régularité (rayon du disque en
pointillé) tend vers zéro quand les
entres des disques s'éloignent. Cette dégénéres
en
e
est due au fait que le produit s
alaire des ve
teurs normaux aux disques n1 et n2 en leurs
points d'interse
tion (
f. g 3.2) tend vers -1. Ainsi la
onstante de prox-régularité de S
dépend aussi de l'angle formé par les ve
teurs normaux n1 et n2 .
tel-00346035, version 1 - 10 Dec 2008
n1 n2
50
3.2. Généralisation à Q0
N
π 1
η ∼
ste √ .
N →+∞ nv N N +1
Démonstration :
D'après la proposition 2.23, on doit montrer que pour tout q ∈ Q0 et tout v ∈ N(Q0 , q),
|v|
v · (q̃ − q) ≤ |q̃ − q|2 , ∀q̃ ∈ Q0 . (3.6)
2η
On sait, d'après la proposition 3.7, que pour tout q ∈ Qij et tout w ∈ N(Qij , q),
|w|
w · (q̃ − q) ≤ |q̃ − q|2 , ∀q̃ ∈ Qij . (3.7)
2ηij
◦
v est le ve
teur nul. Or si q ∈ Q0 , N(Q0 , q) = {0},
L'inégalité (3.6) est triviale lorsque
on
onsidère don
q ∈ ∂Q0 et v ∈ N(Q0 , q) \ {0}. D'après la proposition 3.9,
X
v=− αij Gij (q), αij ≥ 0.
(i,j)∈Icontact
51
Chapitre 3. Prox-régularité de l'ensemble des
ongurations admissibles Q0
1 X
v · (q̃ − q) ≤ √ αij |q̃ − q|2 , ∀q̃ ∈ Q0 .
2ηmin
Pour obtenir l'inégalité (3.6), il sut de trouver une
onstante η > 0, indépendante des
αij et de q, telle que
X 1 1 X
αij √ ≤ αij Gij (q) ,
2ηmin 2η
autrement dit telle que,
X √ η X
αij Gij (q) ≥ 2 αij .
ηmin
Finalement, on
her
he γ > 0 tel que,
X √2 X
αij Gij (q) ≥ αij ,
γ
tel-00346035, version 1 - 10 Dec 2008
ηmin 1 ri + rj
η= = min √ .
γ γ (i,j) 2
Il s'agit don
de prouver une inégalité triangulaire inverse,
X √ X X
αij |Gij (q)| = 2 αij ≤ γ αij Gij (q) .
où
Icontact = {(i, j), i < j, Dij (q) = 0} et les αij sont des réels positifs quel
onques.
La
onstante γ peut être prise égale à
N
√
Nnv 2 nv
γ= √
.
2 π 2π
min sin , sin
nv + 1 N
52
3.2. Généralisation à Q0
Remarque 3.15 Noter l'importan
e du signe des
oe
ients αij . Cette inégalité est
fausse en toute généralité pour des
oe
ients réels quel
onques, puisque pour N grand
le
ardinal de l'ensemble Icontact peut être stri
tement supérieur à 2N ,
e qui impose une
relation de liaison entre les ve
teurs Gij (q).
Établir une inégalité inverse pour un grand nombre de ve
teurs semble di
ile. La mé-
thode proposée fournit des
onstantes γ et η probablement non optimales. An de montrer
la
omplexité de
e problème, on propose à la se
tion 3.3 une minoration de γ et don
une majoration de η.
ave
√
2 nv
b= .
π 2π
min sin , sin
nv + 1 N
En sommant sur les
ouples (k, l) ∈ Icontact , on obtient
X √ X
αkl |Gkl (q)| ≤ 2 card(Icontact ) bN α G (q) .
ij ij
(k,l)∈Icontact (i,j)∈Icontact
Ainsi,
X Nnv X
αkl |Gkl (q)| ≤ √ bN αij Gij (q) .
2
(k,l)∈Icontact (i,j)∈Icontact
Il reste à justier la majoration du nombre maximal de voisins que peut avoir une personne
(majoration donnée à la proposition 3.12 p. 51).
Lemme 3.16 En notant rmin = min ri et rmax = max ri , le nombre maximal de voisins
nv que peut avoir une personne vérie
π
nv ≤ .
rmin
arcsin
rmax + rmin
53
Chapitre 3. Prox-régularité de l'ensemble des
ongurations admissibles Q0
C
PSfrag repla
ements
rmin
rmax
B
A
Démonstration :
On
onsidère une personne représentée par un disque de rayon rmax et on
her
he à
al
uler
le nombre maximal de voisins représentés par des disques de rayon rmin, qu'elle peut avoir
(
f. g. 3.3).
tel-00346035, version 1 - 10 Dec 2008
On a
−→ −→
BC 2 = AB 2 + AC 2 − 2AB · AC
−→ −→
(2rmin)2 = (rmin + rmax )2 + (rmin + rmax )2 − 2|AB||AC| cos θ
2
4rmin = 2(rmin + rmax )2 (1 − cos θ).
D'où,
2
2rmin
1 − cos θ = .
(rmin + rmax )2
Ce qui est équivalent à
2
2 θ rmin
sin = .
2 (rmin + rmax )2
Par
onséquent,
rmin
θ = 2 arcsin
rmin + rmax
2π
Comme nv ≤ , on obtient
θ
π
nv ≤ .
rmin
arcsin
rmax + rmin
54
3.3. Majoration de la
onstante η
q1 qN
N
X −1
q0 = (0, r1 + r2 , r1 + 2r2 + r3 , ..., r1 + 2 ri + rN ).
i=2
( N −1
)
X
N(Q0 , q0 ) = − αi,i+1 Gi,i+1 (q0 ), αi,i+1 ≥ 0 ,
i=1
55
Chapitre 3. Prox-régularité de l'ensemble des
ongurations admissibles Q0
ave
Gi,i+1 (q0 ) = (0, ..., −1, 1, 0, ..., 0), (le 1 étant à la ième pla
e). On dénit
( N −1
)
X
C= α, αi,i+1 ≥ 0, αi,i+1 = 1 .
i=1
|α12 G12 (q0 )| + |α23 G23 (q0 )| + ... + |αN −1N GN −1N (q0 )|
≤ γ|α12 G12 (q0 ) + α23 G23 (q0 ) + ... + αN −1N GN −1N (q0 )|, ∀α ∈ (R+ )N −1 .
√
Comme |Gij (q0 )| = 2,
e
i est équivalent à
√
2 ≤ γ|α12 G12 (q0 ) + α23 G23 (q0 ) + ... + αN −1N GN −1N (q0 )|, ∀α ∈ C. (3.8)
α12 G12 (q0 ) + α23 G23 (q0 ) + ... + αN −1N GN −1N (q0 )
= (−α12 , α12 − α23 , ..., αN −2,N −1 − αN −1N , αN −1N ).
tel-00346035, version 1 - 10 Dec 2008
Ainsi,
|α12 G12 (q0 ) + α23 G23 (q0 ) + ... + αN −1N GN −1N (q0 )|2
N
X −1
2
= α12 + (αi−1,i − αi,i+1 )2 + αN
2
−1N .
i=2
On
her
he don
une
ondition sur γ pour que l'inégalité (3.8) soit vériée,
'est-à-dire
pour que,
" N −1
!#
X
2
min γ 2 α12 + (αi−1,i − αi,i+1 )2 + αN
2
−1N ≥ 2. (3.9)
α∈C
i=2
On note la fon
tion
Hγ : RN −1 → R
N −1
!
X
(αi,i+1 ) 7→ γ 2 2
α12 + (αi−1,i − αi,i+1 )2 + αN
2
−1N .
i=2
et la fon
tion
F : RN −1 → R
N
X −1
(αi,i+1 ) 7→ αi,i+1 .
i=1
De plus, on dénit l'ensemble
( N −1
)
X
S= α ∈ RN −1 , αi,i+1 = 1 = α ∈ RN −1 , F (α) = 1 .
i=1
Pour obtenir l'inégalité (3.9), on utilise la proposition suivante qui sera démontrée plus
loin.
56
3.3. Majoration de la
onstante η
12γ 2
≥ 2.
N(N − 1)(N + 1)
Ce
i est équivalent à,
N(N − 1)(N + 1)
γ2 ≥ ,
6
e qui donne la minoration annon
ée
r
N(N − 1)(N + 1)
γ≥ .
6
tel-00346035, version 1 - 10 Dec 2008
γ ≥ N − 1.
En eet, en
onsidérant le
as parti
ulier où les
oe
ients αi,i+1 sont égaux et valent
1
, l'inégalité (3.8) est équivalente à,
N −1
√ 1 1
2≤γ |G12 (q0 ) + G23 (q0 ) + ... + GN −1N (q0 )| = γ |(−1, 0, .., 0, 1)|.
N −1 N −1
Ce
i implique que √ √
2(N − 1) ≤ γ 2,
d'où le résultat.
Lemme 3.21 La fon
tion Hγ est stri
tement
onvexe et
oer
ive.
57
Chapitre 3. Prox-régularité de l'ensemble des
ongurations admissibles Q0
Comme la fon
tion Hγ est stri
tement
onvexe, il existe un unique α̃ ∈ C minimisant Hγ
sur C (qui est
onvexe et
ompa
t). De plus,
omme la fon
tion Hγ est
oer
ive, il existe
un unique α0 ∈ S minimisant Hγ sur S. Déterminons maintenant α0 .
Etape 2 :
On
al
ule les dérivées partielles de Hγ ,
∂Hγ
= γ 2 [4α12 − 2α23 ]
∂α12
:
∂H
γ
= γ 2 [4αi,i+1 − 2αi−1,i − 2αi+1,i+2 ]
∂αi,i+1
:
∂Hγ
= γ 2 [4αN −1N − 2αN −2,N −1 ].
∂αN −1N
tel-00346035, version 1 - 10 Dec 2008
On a aussi DF (α) = (1, .., 1), ∀α. D'après le théorème des extrema liés, si
alors,
4 −2 0 α121
−2 4 −2 α23 1
λ
.. .. .. .
. .
. . . . = 2 .. . (3.10)
γ
−2 4 −2 αN −2,N −1 1
0 −2 4 αN −1N 1
| {z } | {z }
AN−1 e
La matri
e AN −1
est inversible, son déterminant vaut N2N −1 (
f. démonstration du
−1
lemme 3.21). En posant sN −1 = AN −1 e, on a
λ
α0 = sN −1 .
γ2
1
sN = (sN,1 , sN,2 , . . . , sN,N ) ave
sN,k = (kN − k(k − 1)).
4
58
3.3. Majoration de la
onstante η
N impair N pair
N
N
2N − 2
2N − 2
3N − 6
3N − 6
.
.
.
.
..
kN − k(k − 1)
kN − k(k − 1)
.
.
.
.
.
.
N(N + 2)
2
1 N +1 1 4
sN =
sN =
4 2 4 N(N + 2)
.
. 4
.
tel-00346035, version 1 - 10 Dec 2008
.
.
.
.
.
.
..
..
.
. .
.
.
3N − 6
3N − 6
2N − 2
2N − 2
N
N
On pré ise la valeur de F (sN ), ainsi que de Hγ (sN ) ave les lemmes 3.22 et 3.23.
Lemme 3.22
1
F (sN ) = N(N + 1)(N + 2).
24
Lemme 3.23
γ2
Hγ (sN ) = N(N + 1)(N + 2).
48
λ
De plus, α0 = sN −1 . Comme F (α0 ) = 1 (
ar α0 ∈ S ), on a
γ2
F (α0 ) 1 24γ 2
λ = γ2 = γ2 = .
F (sN −1 ) F (sN −1 ) N(N − 1)(N + 1)
59
Chapitre 3. Prox-régularité de l'ensemble des
ongurations admissibles Q0
λ
Hγ (α0 ) = Hγ sN −1
γ2
2
λ
= Hγ (sN −1 )
γ2
2 2
λ γ
= 4
N(N − 1)(N + 1)
γ 48
N(N − 1)(N + 1)
= λ2
48γ 2
242γ 4 N(N − 1)(N + 1)
= 2
(N(N − 1)(N + 1)) 48γ 2
12γ 2
= .
N(N − 1)(N + 1)
α0 est un extremum de Hγ sur S. Comme Hγ n'est pas majorée sur S sup Hγ = +∞ ,
tel-00346035, version 1 - 10 Dec 2008
S
α0 est don
le minimum de Hγ sur S.
Etape 3 :
Comme le ve
teur sN −1 a toutes ses
omposantes positives et que le réel λ est positif, on
a né
essairement α0 ∈ C. Par uni
ité du minimiseur de Hγ sur C , on a α̃ = α0 . Ce
i
termine la démonstration de la proposition 3.19.
q1 qN
prendre une
ertaine dire
tion du
ne proximal normal N(Q0 , q0 ) à savoir
N
X −1
Gi,i+1 (q0 )
i=1
60
3.3. Majoration de la
onstante η
1
Remarque 3.25 La matri
e − AN (équation 3.10 p. 58) est la matri
e du lapla
ien
tel-00346035, version 1 - 10 Dec 2008
2
dis
rétisé,
e qu'on retrouve en traçant la solution sN = A−1
N e sur la gure 3.7.
Démonstration :
61
Chapitre 3. Prox-régularité de l'ensemble des
ongurations admissibles Q0
Stri
te
onvexité
La hessienne de Hγ , en tout point, est la matri
e AN −1 (
f. équation 3.10 p. 58), qui n'est
autre que l'opposé de la matri
e du lapla
ien dis
rétisé. Rappelons
omment on peut mon-
trer qu'elle est symétrique dénie positive. Pour
ela, il sut de vérier que ses mineurs
prin
ipaux (déterminants des matri
es Ap pour 1 ≤ p ≤ N − 1) sont tous stri
tement
p p
positifs. On peut montrer que det(Ap ) = (p + 1)2 > 0. En eet, det(Ap ) = 2 det(Bp ) où
2 −1 0
−1 2 −1
.. .. ..
Bp = . . . .
−1 2 −1
0 −1 2
En développant par rapport à la première
olonne, on s'aperçoit que
Coer
ivité
On raisonne par l'absurde en supposant qu'il existe une suite (αn ), vériant
N
!
1 X
F (sN ) = kN − k(k − 1)
4 k=1
N
!
1 X
= (N + 1)k − k 2
4 k=1
N N
!
1 X X
= (N + 1) k− k2 .
4 k=1 k=1
62
3.3. Majoration de la
onstante η
p
X p(p + 1)(2p + 1)
k2 = ,
k=1
6
on obtient,
1 N(N + 1) N(N + 1)(2N + 1)
F (sN ) = (N + 1) −
4 2 6
1
= N(N + 1)(N + 2).
24
γ2
tel-00346035, version 1 - 10 Dec 2008
" N
#
X
Hγ (sN ) = γ 2 s2N,1 + (sN,k−1 − sN,k )2 + s2N,N
k=2
" N 2 2 #
N X (−N + 2(k − 1))2 N
2
= γ + + ... +
4 k=2
16 4
" N −1
#
γ2 X
2
= N + (N − 2k)2 + N 2
16
k=1
N
2 X
γ
= (N − 2k)2
16 k=0
" N N
#
γ2 X X
= (N + 1)N 2 − 4N k+4 k2
16 k=0 k=0
γ2 2 N(N + 1) N(N + 1)(2N + 1)
= N + 1)N − 4N +4
16 2 6
γ2 2
= N(N + 1) N − 2N + (2N + 1)
16 3
2
γ
= N(N + 1)(N + 2).
48
63
tel-00346035, version 1 - 10 Dec 2008
Deuxième partie
tel-00346035, version 1 - 10 Dec 2008
65
tel-00346035, version 1 - 10 Dec 2008
Chapitre 4
Présentation et étude d'un s
héma
numérique
Sommaire
tel-00346035, version 1 - 10 Dec 2008
67
Chapitre 4. Présentation et étude d'un s
héma numérique
Initialisation : qn0 = q0
Bou
le en temps : qnk
onnu
Cet algorithme s'inspire d'un s
héma initialement développé pour les é
oulements granu-
laires [Mau06℄. La proposition suivante montre que
e s
héma ne fournit que des
ongu-
rations admissibles.
68
4.1. Présentation du s
héma numérique
On projette sur K(qnk ) ⊂ Q0 que l'on peut qualier d'approximation
onvexe intérieure
de Q0
(voir g. 4.1). À
haque pas de temps, on résout ainsi un problème sur un espa
e
n
admissible stri
tement plus petit. Sur la gure 4.1, les frontières de K(qk ) sont en pointillé.
n
Les points qk+1 et q enk+1 sont obtenus respe
tivement après proje
tion sur K(qnk ) et sur
Q0 de qnk + h U(qnk ) (pour les deux exemples de U(qnk ) donnés). On rappelle en eet que
n n
pour h susamment petit, la proje
tion de qk + h U(qk ) sur Q0 est bien dénie puisque
tel-00346035, version 1 - 10 Dec 2008
qnk + hU(qnk )
qnk + hU(qnk ) enk+1
q enk+1
q
qnk+1
qnk+1
Q0
K(qnk )
D'un point de vue numérique, rempla
er Q0 par K(qnk ) permet d'utiliser des méthodes déjà
existantes permettant de
al
uler la proje
tion sur un ensemble
onvexe. Toutefois,
ette
69
Chapitre 4. Présentation et étude d'un s
héma numérique
approximation entraîne quelques di
ultés théoriques. Une première
hose importante à
justier est qu'on ne perd pas d'information sur le
ne proximal normal en remplaçant
Q0 par K(qnk ). Ce résultat est l'objet du lemme suivant :
Démonstration :
La preuve utilise des lemmes qui seront démontrés ultérieurement dans la sous-se
tion 4.2.3
p. 90. D'après la proposition 3.9 p. 48, on sait que
n X o
N(Q0 , q) = − µij Gij (q), µij ≥ 0, µij = 0 si Dij (q) > 0 .
X
w · (p − q) = − µij Gij (q) · (p − q).
Comme p appartient à K(q), on a Dij (q)+Gij (q)·(p−q) ≥ 0, ∀i < j. De plus, si µij > 0
alors Dij (q) = 0 et par
onséquent Gij (q) · (p − q) ≥ 0. Don
w · (p − q) ≤ 0, ∀p ∈ K(q).
D'après le lemme 4.24 (b) p. 90,
e
i est équivalent au fait que w ∈ N(K(q), q).
Remarque 4.3 Par ailleurs, une autre di
ulté viendra du fait que l'on projette sur un
ensemble K(qnk ) dépendant de la position qnk ,
e qui sort du
adre stri
t des pro
essus de
rae dé
rit dans la se
tion 2.4.2. En eet, dans
e dernier, sont
onsidérés des ensembles
C(t) où l'appli
ation multivaluée C est supposée à variation bornée ave
une fon
tion de
variation
ontinue à droite (
f. équation (2.13) p. 40). Cependant, nous démontrerons à
la proposition 4.9 p. 76 la propriété de
ontinuité lo
ale suivante : la fon
tion
Q0 × R2N 7−→ R
(q, q̃) −→ dK(q) (q̃)
70
4.1. Présentation du s
héma numérique
est
ontinue sur un voisinage de la diagonale. En fait, nous prouverons que l'appli
ation
Q0 × R2N 7−→ R2N
(q, q̃) −→ PK(q) (q̃)
est
ontinue sur
e même voisinage. (Le point projeté q̃ est supposé pro
he du point q
asso
ié à l'ensemble K(q) sur lequel on projette.)
On dénit les fon
tions asso
iées à
e s
héma, à savoir les fon
tions un , Un
onstantes
par mor
eaux par,
page 27,
dq
(t) − U (q(t)) ∈ −N (Q0 , q(t)) , p.p.t. t ∈ [0, T ]
dt
et le problème dis
rétisé.
Démonstration :
Par dénition,
qnk+1 = PK(qnk ) (qnk + hU(qnk )),
e qui implique d'après la proposition A.4 (
) p. 143,
71
Chapitre 4. Présentation et étude d'un s
héma numérique
Comme
ela a été souligné dans la remarque 4.3, le rempla
ement de Q0 par des ensembles
K(q) soulève une nouvelle di
ulté (par rapport aux travaux de J.F. Edmond et L.
Thibault [ET06℄) puisqu'une hypothèse de régularité de
es ensembles nous fait défaut.
tel-00346035, version 1 - 10 Dec 2008
Par
onséquent,
kun kL∞ ([0,T ],R2N ) ≤ CU .
Z t
n
Comme pour tout t dans [0, T ], q (t) = q0 + un (s)ds, on a
0
D'après le théorème d'As
oli, il existe don
une suite extraite, toujours notée qn , qui
0 2N
onverge uniformément sur [0,T℄ vers une fon
tion q ∈ C ([0, T ], R ).
vu
qn −−−→ q sur [0, T ] (4.5)
n→∞
On peut montrer en fait que la fon tion limite est plus régulière.
Démonstration :
∞ 2N
La suite des dérivées, toujours notée u , est bornée dans L ([0, T ], R
n
). Il existe don
∞ 2N
une suite extraite (toujours notée) u qui
onverge dans L ([0, T ], R
n
) faible ⋆. Appelons
u sa limite, on a alors
⋆
un ⇀ u dans L∞ ([0, T ], R2N ). (4.6)
L'égalité
Z t
n
q (t) = q0 + un (s)ds, ∀t ∈ [0, T ]
0
donne à la limite Z t
q(t) = q0 + u(s)ds, ∀t ∈ [0, T ].
0
dq
On en déduit que la fon
tion q est dans W 1,∞ ([0, T ], R2N ) et que = u p.p.
dt
Proposition 4.7 La fon
tion q vérie q(t) ∈ Q0 , pour tout t dans [0, T ].
Démonstration :
tel-00346035, version 1 - 10 Dec 2008
n n n n n
Par
onstru
tion et par
onvexité de K(qk ), q (t) ∈ K(qk ) ⊂ Q0 si t ∈ [tk , tk+1 ]. A
n
fortiori, q (t) ∈ Q0 , pour tout t dans [0,T℄. Comme Q0 est fermé, on obtient bien à la
limite le résultat annon
é.
Finalement, la fon
tion q est dans W 1,∞ ([0, T ], Q0 ) ⊂ W 1,1 ([0, T ], Q0 ). Si on montre que
ette fon
tion vérie l'in
lusion diérentielle pré
édente, le théorème 2.30 p. 40 armera
son uni
ité. Ainsi, par
ompa
ité et par uni
ité de la valeur d'adhéren
e, on en déduira
n
que la suite q
onverge vers la fon
tion q, unique solution du problème.
In
lusion diérentielle
On veut montrer que la fon
tion limite q vérie l'in
lusion diérentielle du théo-
rème 4.5. Le début de la preuve qu'on propose i
i s'inspire d'une démonstration présente
dans [ET06℄. An de fa
iliter la le
ture de la preuve, les lemmes énon
és seront démontrés
ultérieurement dans la sous-se
tion 4.2.3 p. 90. On veut montrer que
dq
− U (q) ∈ −N(Q0 , q) p.p.
dt
D'après le lemme 4.2 p. 70, il sut de montrer que
dq
− U (q) ∈ −N(K(q), q) p.p.
dt
dqn
On sait, d'après les résultats (4.5) et (4.6), qu'il existe des suites qn et un = telles
dt
que
dqn ⋆ dq
⇀ dans L∞ ([0, T ], R2N )
dt dt
vu
qn −−−→ q sur [0, T ].
n→∞
73
Chapitre 4. Présentation et étude d'un s
héma numérique
Comme on travaille sur l'intervalle [0,T℄ borné,
ela implique en parti
ulier,
dqn dq
⇀ dans L1 ([0, T ], R2N )
dt dt
vu
q −−−→ q
n
sur [0, T ].
n→∞
vu
Comme U est lips
hitzienne, on a Un −−−→ U(q) et nalement,
n→∞
dqn dq
− Un ⇀ − U(q) dans L1 ([0, T ], R2N )
dt dt
vu
qn −−−→ q sur [0, T ].
n→∞
Ce
i asso
ié au lemme de Mazur assure l'existen
e d'une suite de fon
tions zn ∈ L1 ([0, T ], R2N )
telle que,
n dqk k dq
z ∈ Conv −U , k ≥n et zn −−−→ − U(q) dans L1 ([0, T ], R2N ).
dt n→∞ dt
tel-00346035, version 1 - 10 Dec 2008
dq
zn −−−→ z = − U(q) p.p.
n→∞ dt
Or d'après la proposition 4.4, on sait que
dqn
(t) − Un (t) ∈ −N(K(qn (ρn (t))), qn (θn (t))), p.p.t. t ∈ [0, T ]. (4.7)
dt
dq
On xe t dans [0, T ] tel qu'on ait la
onvergen
e de (t) − U(q(t)) et
zn (t) vers z(t) =
n
dt
que l'in
lusion
i-dessus soit vériée au point t (i.e. pour t ∈
/ {tk }). On
veut montrer que
k
dq
z(t) ∈ −N(K(q(t)), q(t)). Comme zn (t) ∈ Conv dt (t) − Uk (t), k ≥ n , on a
2N n dqk k
∀ξ ∈ R , hz (t), ξi ≤ sup (t) − U (t), ξ .
k≥n dt
A la limite, on obtient
2N dqn n
∀ξ ∈ R , hz(t), ξi ≤ lim sup (t) − U (t), ξ . (4.8)
n dt
On souhaite maintenant majorer
ette limite supérieure. Pour
ela, on utilise l'équa-
tion (4.7) et le résultat suivant (
f. lemme 4.24 (d) p. 90) à savoir que
dqn
(t) − Un (t) ∈ −N(K(qn (ρn (t))), qn (θn (t)))
dt
est équivalent à
n
dqn dq
∀ξ ∈ R 2N
, − (t) + Un (t), ξ
≤ (t) − U (t) dK(qn (ρn (t))) (ξ + qn (θn (t))).
n
dt dt
74
4.2. Convergen
e du s
héma numérique
On a don
n
dqn dq
∀n, ∀ξ ∈ R 2N
, (t) − Un (t), ξ ≤ (t) − U (t) dK(qn (ρn (t))) (qn (θn (t)) − ξ)
n
dt dt
D'après (4.4), on obtient
2N dqn
∀n, ∀ξ ∈ R , (t) − Un (t), ξ ≤ 2CU dK(qn (ρn (t))) (qn (θn (t)) − ξ). (4.9)
dt
De plus, on a ∀n, ∀ξ ∈ R2N
dK(qn (ρn (t))) (qn (θn (t)) − ξ) − dK(q(t)) (q(t) − ξ)
≤ dK(qn (ρn (t))) (qn (θn (t)) − ξ) − dK(qn(ρn (t))) (q(t) − ξ)
+ dK(qn (ρn (t))) (q(t) − ξ) − dK(q(t)) (q(t) − ξ)
≤ |qn (θn (t)) − q(t)| + dK(qn (ρn (t))) (q(t) − ξ) − dK(q(t)) (q(t) − ξ) .
tel-00346035, version 1 - 10 Dec 2008
Proposition 4.8 Il existe ν > 0 tel que pour tout ξ ∈ R2N , |ξ| < ν ,
dK(qn (ρn (t))) (q(t) − ξ) − dK(q(t)) (q(t) − ξ) −−−→ 0. (4.10)
n→∞
dK(qn (ρn (t))) (qn (θn (t)) − ξ) −−−→ dK(q(t)) (q(t) − ξ).
n→∞
Ainsi, s'a
hève la démonstration du théorème 4.5 dans ses grandes lignes. Reste main-
tenant à justier les lemmes utilisés (
f. se
tion 4.2.3) et surtout la proposition 4.8 qui
est fondamentale. On a
hoisi de donner une preuve diérente de
elle é
rite dans [ET06℄
pour majorer la limite supérieure de l'équation (4.8), toutefois l'argument-
lé est le même.
En eet, les auteurs ont par hypothèse (
f. équation (2.13) p. 40),
analogue à (4.10). Ce
i leur permet de démontrer la proposition 2.1 de [ET06℄, qui à partir
de l'équation (4.8) donne le résultat (4.11).
75
Chapitre 4. Présentation et étude d'un s
héma numérique
Démonstration :
On sait d'après le lemme 4.25 p. 91, que les ve
teurs fn
p sont solutions d'un système de
type suivant :
X
f
p = e
q + λnij Gij (qn )
n
i<j
(Pqn,q̃ ) ∀i < j, Dij (qn ) + Gij (qn ) · (f pn − qn ) ≥ 0
tel-00346035, version 1 - 10 Dec 2008
X
λnij (Dij (qn ) + Gij (qn ) · (f
pn − qn )) = 0,
i<j
où les λnij sont des réels positifs. De même, le ve
teur e est solution d'un système analogue :
p
X
e
p = e
q + λij Gij (q)
i<j
(Pq,q̃ ) ∀i < j, Dij (q) + Gij (q) · (ep − q) ≥ 0
X
λij (Dij (q) + Gij (q) · (e
p − q)) = 0,
i<j
où les λij sont des réels positifs. Les réels λnij et λij sont des multipli
ateurs de Lagrange
et la dernière ligne des deux systèmes
ontient une relation appelée relation de
omplé-
mentarité. La proposition suivante (dont la démonstration fait l'objet de la se
tion 4.2.2)
n n
arme que la suite λ = (λij ) est bornée.
Proposition 4.10 Pour tout q ∈ Q0 , il existe ν > 0 et M dans N tels que pour tout
n ≥ M , tout q
e dans B(q, ν) et tout λn solution de (Pqn ,q̃ ), on ait
√
2 nv
∀i < j, λij ≤ 2νb où b =
n N
π ,
π
min sin , sin
2(nv + 1) N
76
4.2. Convergen
e du s
héma numérique
Remarque
T 4.11 Le résultat de la proposition 4.9 n'est pas vrai en toute généralité lorsque
K(q) = i<j Kij (q) est une interse
tion quel
onque de demi-espa
es. Sur la gure 4.2, on
a tra
é les frontières des demi-espa
es K12 n
= K12 (qn ) et K13
n
= K13 (qn ). Ces frontières
tel-00346035, version 1 - 10 Dec 2008
se rejoignent lorsque n tend vers l'inni. On remarque don
que la suite p fn , qui est
stationnaire, ne tend pas vers p e.
n → +∞ fn
p e
p n
F r(K12 )
e
q
n
F r(K13 )
Fig. 4.2 Contre-exemple.
77
Chapitre 4. Présentation et étude d'un s
héma numérique
nuls quand il n'y a pas
onta
t. Dénissons don
l'ensemble des
ouples de personnes qui
sont éloignées l'une de l'autre (i.e. à distan
e stri
tement positive) :
If ar (q) = (i, j) ∈ J1, NK2 , i < j, Dij (q) > 0 ,
et pré isons la valeur des multipli ateurs de Lagrange asso iés à es ouples.
Lemme 4.12 Il existe ν > 0 et M0 dans N tels que pour tout n ≥ M0 et tout q
e dans
B(q, ν), on ait :
ε
∃M0 > 0, ∀n ≥ M0 , Dij (qn ) ≥ ε, ∀(i, j) ∈ If ar (q) et |qn − q| ≤ .
8
ε ε
Posons ν= e ∈ B(q, ν)
et
hoisissons q , on a alors |e
q − q| < .
8 8
Comme p q) et q ∈ K , on a
e = PK (e
|e
p−q
e| ≤ |q − q
e|. (4.12)
Par
onséquent,
ε
|e
p − q| ≤ |e
p−qe| + |e
q − q| ≤ 2|e
q − q| ≤ .
4
De manière analogue,
omme p q) et qn ∈ Kn , on a
fn = PKn (e
|f
pn − q
e| ≤ |qn − q
e| ≤ |e
q − q| + |q − qn | ≤ 2ν. (4.13)
D'où,
ε
|f
pn − qn | ≤ |f
pn − q
e| + |e
q − qn | ≤ 2|e
q − qn | ≤ 4ν ≤ .
2
Par
onséquent,
√ ε √ ε
Dij (q) + Gij (q) · (e
p − q) ≥ 2ε − 2 > 0 et Dij (qn ) + Gij (qn ) · (f
pn − qn ) ≥ ε − 2 > 0.
4 2
La relation de
omplémentarité et la positivité des multipli
ateurs de Lagrange permettent
alors de
on
lure.
78
4.2. Convergen
e du s
héma numérique
Remarque 4.13 Lorsque Dij (q) > 0, on peut don
armer que les multipli
ateurs de
Lagrange λij et sont nuls pour n assez grand. Lorsque Dij (q) = 0, λij peut être nul
λnij
sans que λnij le soit pour n assez grand (même si Dij (qn ) > 0). Dans la gure 4.3 ,
sont dessinées les
ongurations q, qn et q e de 3 parti
ules. Dé
rivons-les. Partant de la
onguration q, le
entre de la parti
ule 2 a subi une homothétie et une rotation de
entre
q1 , pour obtenir la suite des
ongurations qn tendant vers q. La parti
ule 2 a juste été
translatée pour obtenir la
onguration qe (toujours à partir de la
onguration q). Sur les
tel-00346035, version 1 - 10 Dec 2008
ongurations q et qn , on a tra
é respe
tivement la droite ∆12 de ve
teur normal e12 (q)
et la droite ∆n12 de ve
teur normal e12 (qn ). Ces deux droites ont été représentées sur la
onguration q e. Ainsi, on observe que qe appartient à K(q) puisque les parti
ules 1 et 2
se trouvent bien de part et d'autre de la droite ∆12 . Par
onséquent, λ12 = 0. Cependant,
e n'appartient pas à K(qn ) et λn12 > 0 pour tout n.
q
On
her
he à borner les λn solutions de (Pqn ,q̃ ) qui apparaissent dans l'é
riture :
X
λnij Gij (qn ) = p e = Fn .
fn − q
i<j
Mais, d'après le lemme 4.12 p. 78, les seuls multipli
ateurs de Lagrange à
onsidérer
sont
eux qui sont asso
iés aux
onta
ts présents dans la
onguration nale q. Ainsi, on
ommen
e d'abord par étudier les multipli
ateurs intervenant dans l'é
riture suivante :
X
e−q
λij Gij (q) = p e = F.
i<j
Par sou
i de
larté, on
onsidère dans la suite le
as monodisperse (tous les disques ont le
même rayon noté r ). Les modi
ations à apporter dans le
as polydisperse seront pré
isées
dans la démonstration de la proposition 4.21 p. 86.
Cas monodisperse
Proposition 4.14 Dans le
as monodisperse, pour tout q dans Q0 , pour tout F dans
R 2N
, on dénit l'ensemble
( )
N(N−1) X
Λq,F = λ∈R 2 , λij Gij (q) = F, λij ≥ 0, λij = 0 si Dij (q) > 0 .
i<j
79
Chapitre 4. Présentation et étude d'un s
héma numérique
Cet ensemble, s'il est non vide, est borné uniformément en q. Plus pré
isément, on a
3
∀λ ∈ Λq,F , ∀i < j, λij ≤ |F| aN où a = .
sin( 2π
N
)
Démonstration :
On
onsidère le
as où Λq,F P
est non vide. On
her
he à estimer les solutions λ du système
suivant (à 2N équations) : i<j λij Gij (q) = F. Comme λij = 0 si Dij (q) > 0, beau
oup
de multipli
ateurs de Lagrange sont nuls. On
her
he en fait à résoudre
X
λij Gij (q) = F , λij ≥ 0 (P ).
i<j
Dij (q) = 0
En pré
isant l'é
riture des ve
teurs Gij (q), on peut expli
iter les 2 lignes du système qui
on
ernent la personne i0 ,
n
X
tel-00346035, version 1 - 10 Dec 2008
g
λ ji0 eji0 = Fi0 (Pi0 )
j=1
j 6= i0
j voisin de i0
où
g λji0 si j < i0
λ ji0 = et eji0 = eji0 (q).
λi0 j si j > i0
Comme on s'est pla
é dans le
adre monodisperse, il y a au maximum 6 termes dans la
somme puisque la personne i0 a au plus 6 voisins. Bien entendu, il est plus fa
ile de résoudre
(Pi0 ) quand le membre de gau
he
ontient peu de termes. L'idée de la démonstration est
la suivante. Quand il n'y a qu'un seul terme (i0 a un unique voisin j ), la résolution est
triviale (
f. Etape 1
i-après). Lorsqu'il y a deux termes (i0 a deux voisins j1 et j2 ), le
système est inversible si ei0 j1 et ei0 j2 sont indépendants. Le
as qui pose problème est
elui où les 3 personnes sont alignées, i0 j1 et j2 . En résumé, si l'angle
se trouvant entre
entre les ve
teurs ei0 j1 et ei0 j2 est stri
tement inférieur à π , le système est inversible, la
borne de l'inverse dépend de
et angle et diverge quand
e dernier se rappro
he de π .
Comme on veut majorer les multipli
ateurs de Lagrange, on veillera don
à
ontrler
et
angle (
f. Etape 2
i-après). Pour résoudre le problème global, il sut de résoudre
es
sous-problèmes (Pi ) dans un ordre bien
hoisi : on résout les plus simples d'abord.
80
4.2. Convergen
e du s
héma numérique
L'idée est la suivante : à
haque résolution d'un problème (Pi0 ), on enlèvera l'élément
qi0 de A, on supprimera le sous-problème (Pi0 ) du système global (P ), et on prendra en
Par
onséquent, λf
ji = |Fi |. On retire alors l'élément qi de A et on modie le se
ond
membre Fj
omme suit
Fj = Fj − λf
ji eij .
Ce
i nous amène à rempla
er la borne du se
ond membre Fj par |Fj | + |Fi |. On élimine
tel-00346035, version 1 - 10 Dec 2008
ainsi tous les
onta
ts simples de A,
e qui permet par exemple, de traiter entièrement le
as de la gure 4.4.
81
Chapitre 4. Présentation et étude d'un s
héma numérique
Cas 1 : qi a 2 voisins
qi qj
γ
PSfrag repla
ements
qk
Fig. 4.5 Cas 1.
tel-00346035, version 1 - 10 Dec 2008
−1 cos γ
Plus pré
isément, eji = et eki = . Le problème
0 sin γ
λf f
ji eji + λki eki = Fi (Pi )
Ainsi, on a
√
2 1
λf
ji ≤ |Fi | et λf
ki ≤ |Fi |.
sin γ sin γ
On enlève qi A. On
de l'ensemble
√ modie les bornes du se
ond membre, plus pré
isément,
2 1
on rempla
e |Fj | par |Fj | + 2π |Fi | et |Fk | par |Fk | + |Fi |
ar sin γ ≥ sin( 2π ).
sin( N ) sin( 2π
N
) N
Cas 2 : qi a 3 voisins
82
4.2. Convergen
e du s
héma numérique
π
Par ailleurs, on a β ≤ −
ar les parti
ules j et k ne se
hevau
hent pas. De plus,
omme
3
β ≥ −π + γ + 3 , on a d'après (4.14), β ≥ 2π
π
N
− 2π
3
. On obtient don
l'en
adrement de β
suivant,
2π 2π π
− ≤β≤− . (4.15)
N 3 3
Noter que né
essairement, N ≥ p ≥ 6 pour que l'en
adrement (4.14) ait un sens. En eet,
il est fa
ile de voir que pour N < 7 personnes, on réduit l'amas A jusqu'à un singleton
grâ
e à l'étape 1.
qi qj
β
ql qk
tel-00346035, version 1 - 10 Dec 2008
−1 − cos β cos γ
Plus pré
isément, eji = , eki = et eli = . Le problème (Pi )
0 − sin β sin γ
s'é
rit
λf f f
ji eji + λki eki + λli eli = Fi .
Bien sûr, on voit apparaître dans
ette situation la non-uni
ité des multipli
ateurs de
Lagrange (2 équations, 3 in
onnues). Elle est due au fait que le ve
teur eik peut s'é
rire
omme
ombinaison linéaire à
oe
ients positifs des ve
teurs eij et eil . On dénit une
Il reste alors à dé
rire le noyau de la matri
e du système (Pi ) pour obtenir toutes les
solutions. On utilise don
le lemme suivant démontré p. 93.
Lemme 4.15 Le noyau de la matri
e du système (Pi ) est engendré par le ve
teur :
sin(β − γ)
kβγ = sin γ .
sin β
De plus, on
onnaît les signes de ses
omposantes,
√
2π 2π 3
sin(β − γ) ≤ − sin( ) < 0, sin γ ≥ sin( ) > 0 et sin β ≤ − < 0.
N N 2
83
Chapitre 4. Présentation et étude d'un s
héma numérique
fli
λ f0
λ sin β
li
Or nous
her
hons toutes les solutions positives. La positivité de sin γ implique que t doit
être positif. De plus, les signes négatifs de sin(β − γ) et de sin β impliquent que t ≤ tmax
où !
λf
0
ji
f0
λ li
tmax = min , . (4.17)
− sin(β − γ) − sin β
Comme t sin(β − γ) < 0 et t sin β < 0, on a
λf f0
ji ≤ λji et λ f0 .
fli ≤ λ
li
Or on a déjà vu (
f.
as 1) que
√
2 1
λf
0 f0 ≤
tel-00346035, version 1 - 10 Dec 2008
ji ≤ |Fi | et λ li |Fi |.
sin γ sin γ
D'où √
2 1
λf
ji ≤ |Fi | et fli ≤
λ |Fi |.
sin γ sin γ
Comme t sin γ > 0, on a
λf
ki ≤ tmax sin γ.
Bilan
En itérant
e pro
édé,
'est-à-dire en éliminant tous les
onta
ts simples puis en
hoisissant
une parti
ule extrêmale vériant la
ondition d'angle pré
édente et ainsi de suite, on résout
le problème global (P ) en (N − 1) étapes. On remarque qu'à
haque résolution de sous-
problèmes, on arrive à borner les multipli
ateurs de Lagrange par le se
ond membre à une
onstante près. Il sut don
de savoir
omment évolue la borne du se
ond membre pour
estimer les λij . Le lemme suivant (démontré p. 94) permet de
on
lure.
84
4.2. Convergen
e du s
héma numérique
Lemme 4.17 A
haque rédu
tion de l'ensemble A, la norme |F| est rempla
ée au pire
3
des
as par |F|.
sin( 2π
N
)
Corollaire 4.18 Dans le
as monodisperse, pour tout q ∈ Q0 , il existe ν > 0 tel que pour
tout q
e dans B(q, ν) et tout λ solution de (Pq,q̃ ), on ait
3
∀i < j, λij ≤ νaN où a = .
sin( 2π
N
)
Démonstration :
Le lemme 4.12 donne l'existen
e de ν > 0 tel que pour qe ∈ B(q, ν), (e
p, λ) solution de
(Pq,q̃ ) implique que λ ∈ Λq,F ave
F = p
e−q e. De plus, lors de la démonstration de
e
tel-00346035, version 1 - 10 Dec 2008
lemme (p. 78), on montre que |F| ≤ ν (
f. équation (4.12)). La proposition 4.14 permet
alors de
on
lure.
Remarque 4.19 Dans [Mau06℄, B. Maury avait déjà montré le
ara
tère borné des mul-
tipli
ateurs de Lagrange, sans expli
iter de borne, en utilisant la notion de
ne asymptote
(voir [Mau06℄). L'idée de
onsidérer les parti
ules extrêmales y était déjà présente. Ce-
pendant, pour montrer le
ara
tère uniformément borné des multipli
ateurs de Lagrange,
il est essentiel de
omprendre la dépendan
e de
ette borne par rapport à la
onguration
q
onsidérée. Celle-
i dépend très fortement de la géométrie de la
onguration et plus
pré
isément de la présen
e de gros amas.
Nous avons don
démontré que les multipli
ateurs de Lagrange intervenant dans la proje
-
tion de e sur K(q)
q sont bornés. Reste à étudier
eux qui interviennent dans la proje
tion
de e
q sur K(qn ).
Proposition 4.20 Dans le
as monodisperse, pour tous q, qn dans Q0 , pour tout F dans
R2N , on dénit l'ensemble
( )
N(N−1) X
Λq,qn,F = λ∈R 2 , λij Gij (qn ) = F, λij ≥ 0, λij = 0 si Dij (q) > 0 .
i<j
Alors, il existe M1 dans N tel que pour tout n ≥ M1 , l'ensemble Λq,qn,F , s'il est non vide,
est uniformément borné. Plus pré
isément, on a
3
∀λ ∈ Λq,qn,F , ∀i < j, λij ≤ |F| aN où a = .
sin( Nπ )
85
Chapitre 4. Présentation et étude d'un s
héma numérique
Démonstration :
Comme la suite (qn ) tend vers q, il existe M1 dans N tel que pour tout n ≥ M1 , pour
tous
ouples (i, j), i < j , (k, l), k < l, l'angle orienté entre les ve
teurs eij (qn ) et ekl (qn )
soit pro
he de l'angle entre les ve
teurs eij (q) et ekl (q) :
π
∃M1 , ∀n ≥ M1 , ∀(i, j), i < j, ∀(k, l), k < l, |(eij (q\ \
n ), ekl (qn ))−(eij (q), ekl (q))| < α < .
N
Soit n ≥ M1 ,
on suit maintenant la même démar
he que
elle de la démonstration de la
n
proposition 4.14. On dénit les sous-problèmes (Pi )
omme suit :
n
X
λf n
ji eji = Fi (Pin )
j=1
j 6= i
Dij (q) = 0
où
λji si j<i
λf
ji = et enji = eji (qn ).
λij j>i
tel-00346035, version 1 - 10 Dec 2008
si
On remarque que la somme du membre de gau
he porte sur les j voisins de i dans la
onguration nale q. Considérer les voisins dans la
onguration qn serait une erreur
ar λij
peut être stri
tement positif alors que la distan
e Dij (qn ) est stri
tement positive
n
(
f remarque 4.13). On résout les sous-problèmes (Pi ) exa
tement dans le même ordre
que les sous-problèmes (Pi ). Les résolutions ee
tuées lors de l'étape 2 ne poseront pas
de problème puisque les angles entre les ve
teurs eij (qn ) sont
ontrlés. L'angle γn (ave
2π
des notations évidentes) est maintenant supérieur à
N
− α ≥ Nπ .
Généralisation au
as polydisperse
Le
ara
tère uniformément borné des multipli
ateurs de Lagrange se généralise au
as
polydisperse. La proposition suivante est analogue à la proposition 4.14.
Proposition 4.21 Pour tout q dans Q0, pour tout F dans R2N , on dénit l'ensemble
( )
N(N−1) X
Λq,F = λ∈R 2 , λij Gij (q) = F, λij ≥ 0, λij = 0 si Dij (q) > 0 .
i<j
Cet ensemble, s'il est non vide, est uniformément borné en q. Plus pré
isément, on a
√
2 nv
∀λ ∈ Λq,F , ∀i < j, λij ≤ |F| b N
où b = ,
π 2π
min sin , sin
nv + 1 N
où nv est le nombre maximal de voisins que peut avoir une personne (
f. lemme 3.16
p. 53).
Démonstration :
Comme il sut de reprendre le
heminement suivi pour prouver la proposition 4.14, seules
86
4.2. Convergen
e du s
héma numérique
π
niv ≤ nv ≤ .
rmin
arcsin
rmax + rmin
β2
β3
sin(βp − γ)
0
.
.
.
0
kβ p γ = sin γ ,
0
.
..
0
sin βp
sin γ se trouvant à la (p + 1)ème
oordonnée. Les solutions du problème (Pi ) s'é
rivent
don
omme somme de la solution parti
ulière (analogue à
elle de l'équation (4.16)
87
Chapitre 4. Présentation et étude d'un s
héma numérique
P
p. 83) et de tp kβp γ , où tp ∈ R. De la même manière que dans le
as monodisperse,
on vérie fa
ilement que les
oe
ients tp sont positifs. Ensuite, on essaie d'estimer les
majorants tp,max dénis
omme dans (4.17) p. 84. Pour
ela, on majore les quantités
suivantes sin(βp − γ) et sin βp . Grâ
e à la démonstration du lemme 3.16 p. 53, on peut
armer que
rmin
βp ≤ −θ = −2 arcsin .
rmax + rmin
De même, on montre que βp − γ ≤ −θ. Ainsi, sin(βp − γ) ≤ − sin θ et sin βp ≤ − sin θ. Ce
qui nous permet d'obtenir nalement
1
tp,max sin γ ≤ |Fi |.
sin θ
Enn, en faisant un nouveau bilan, on montre (même preuve que le lemme 4.17 p. 85)
que dans le pire des
as la norme de |F| est rempla
ée par
√
2 nv
tel-00346035, version 1 - 10 Dec 2008
2π
|F|.
min sin θ, sin N
π
On
on
lut grâ
e à la minoration θ≥ .
nv + 1
Proposition 4.22 Pour tous q, qn dans Q0 , pour tout F dans R2N , on dénit l'ensemble
( )
N(N−1) X
Λq,qn ,F = λ∈R 2 , λij Gij (qn ) = F, λij ≥ 0, λij = 0 si Dij (q) > 0 .
i<j
Alors, il existe M1 dans N tel que pour tout n ≥ M1 , l'ensemble Λq,qn,F , s'il est non vide,
est uniformément borné. Plus pré
isément, on a
√
2 nv
∀λ ∈ Λq,qn,F , ∀i < j, λij ≤ |F| b N
où b = π ,
π
min sin , sin
nv + 1 N
où nv est le nombre maximal de voisins que peut avoir une personne (
f. lemme 3.16
p. 53).
Nous arrivons au but de
ette se
tion. On peut maintenant démontrer la proposition 4.10
qui arme le
ara
tère uniformément borné des multipli
ateurs de Lagrange dans le
as
général polydisperse.
88
4.2. Convergen
e du s
héma numérique
Remarque 4.23 Il est à noter que le
ara
tère borné des multipli
ateurs de Lagrange dé-
montré à la proposition 4.21, est équivalent à l'existen
e de l'inégalité triangulaire inverse
de la proposition 3.14 p. 52. Et de
ette inégalité dé
oule le
ara
tère uniformément prox-
tel-00346035, version 1 - 10 Dec 2008
λ^
1, obst1
λ^
2, obst2
λf
12
Fig. 4.8 Situation où les multipli ateurs de Lagrange sont non bornés.
En eet, dans l'exemple présenté sur la gure 4.8, les multipli
ateurs doivent vérier le
système suivant :
−λf ^ x
12 + λ1, obst1 = F1
λf − λ^ x
12 2, obst2 = F2 .
89
Chapitre 4. Présentation et étude d'un s
héma numérique
Lemme 4.24 Soit S un
onvexe fermé in
lus dans un espa
e de Hilbert H , soient x ∈ S
et w ∈ H alors les propositions suivantes sont équivalentes :
déf
w ∈ N(S, x) ⇔ x = PS (x + w) (a)
⇔ ∀y ∈ S, hw, y − xi ≤ 0 (b)
⇔ ∀y ∈ H, hw, y − xi ≤ |w| dS (y) (c)
⇔ ∀ξ ∈ H, hw, ξi ≤ |w| dS (ξ + x) (d)
⇔ ∃η > 0, ∀v ∈ H, |v| < η, hw, vi ≤ |w| dS (v + x) (e)
⇔ ∃k > 0, ∃η > 0, ∀v ∈ H, |v| < η, hw, vi ≤ k dS (v + x) (f )
tel-00346035, version 1 - 10 Dec 2008
Démonstration :
Démontrons l'équivalen
e des propriétés :
(a) ⇔ (b) :
ara
térisation du projeté orthogonal sur un
onvexe fermé d'un espa
e de
Hilbert.
(c) ⇔ (d) :
lair en posant ξ = y − x.
(d) ⇒ (e) :
lair.
(e) ⇒ (f ) :
lair.
Justions maintenant :
(b) ⇒ (c) : on
onsidère y ∈ H et w ∈ N(S, x). Si y ∈ S , dS (y) = 0 et l'inégalité (
) est
vériée. Sinon, on dénit z = PS (y) alors
hw, y − xi = hw, z + (y − z) − xi
= hw, z − xi + hw, y − zi
≤ hw, y − zi
ar z ∈ S,
≤ |w||y − z|
≤ |w|dS (y).
(e) ⇒ (d) : on
onsidère ξ ∈ H et w ∈ N(S, x). Si |ξ| ≤ η , l'inégalité (d) est vériée.
Sinon, on pose ξ = αv où v ∈ H, |v| ≤ η et α > 1. Alors,
90
4.2. Convergen
e du s
héma numérique
p α−1
Soit p = PS (αv + x), alors |p − αv − x| = dS (αv + x). On dénit ζ= α
+ α
x. Comme
S est
onvexe, ζ ∈ S et ainsi
dS (v + x) ≤ |ζ − v − x|
p 1
≤ + 1− x − v − x
α α
p x
≤ − − v
α α
1
≤ |p − x − αv|
α
1
≤ dS (αv + x).
α
D'où,
y−x 1 1
v+x= +x= 1− x + y ∈ S,
ar S est
onvexe .
α α α
Et par onséquent,
91
Chapitre 4. Présentation et étude d'un s
héma numérique
Démonstration :
La
onguration e
p est solution du problème de minimisation sous
ontrainte suivant :
1
e |2 .
argmin |p − q
p∈K(q) 2
Le lagrangien du problème point-selle asso
ié est,
1 X
e |2 −
L (p, µ) = |p − q µij (Dij (q) + Gij (q) · (p − q)) .
2 1≤i<j≤N
N(N−1)
Φ : R2N → R 2
p 7→ − (Gij (q) · p)i<j
et
N(N−1)
Φ⋆ : R 2 → R2N
P
µ 7→ − i<j µij Gij (q) .
tel-00346035, version 1 - 10 Dec 2008
est un fermé. Cette dernière propriété est démontrée au sous-lemme B.2 p. 146. Ce
ouple
(e
p, λ) vérie alors le système,
e + Φ⋆ (λ) = q
p e
e ∈ K(q)
p
hλ, −D(q) − Φ(q) + Φ(p)i = 0,
Remarque 4.26 Comme l'appli
ation Φ n'est pas surje
tive en général, on ne peut pas
on
lure à l'uni
ité des multipli
ateurs de Lagrange. On montre même que
e résultat est
faux lors de la démonstration de la proposition 4.14 p. 80 (Etape 2, Cas 2).
92
4.2. Convergen
e du s
héma numérique
λf
ji + λf
ki
fli
+λ = 0.
0 − sin β sin γ
e qui équivaut à :
λf f f sin β cos γ
ji = −λki cos β + λki
sin γ
fli = λf sin β
λ ki .
sin γ
Par
onséquent, on peut prendre
omme ve
teur du noyau,
sin β
− cos β + cos γ
sin γ
1
sin β
sin γ
ou en le multipliant par sin γ ,
− cos β sin γ + sin β cos γ sin(β − γ)
sin γ = sin γ .
sin β sin β
2π π
Reste à vérier les majorations. Comme
N
≤γ≤ 3
(
f. en
adrement (4.14) p. 82), on a
bien
2π
sin γ ≥ sin( ) > 0.
N
93
Chapitre 4. Présentation et étude d'un s
héma numérique
2π 2π
De plus,
N
− 3
≤ β ≤ − π3 (
f. en
adrement (4.15) p. 83) don
√
3
sin β ≤ − < 0.
2
2π
Enn, des deux en
adrements pré
édents, on en déduit que
N
− π ≤ β − γ ≤ − 2π
N
− π3 .
On obtient alors que
2π 2π
sin(β − γ) ≤ sin( − π) = − sin( ) < 0.
N N
√ !
2 1 1 1
tmax ≤ min |Fi |, |Fi | .
sin γ (− sin(β − γ)) sin γ (− sin β)
Par onséquent,
√ !
2 1
tmax sin γ ≤ min |Fi |, |Fi | .
(− sin(β − γ)) (− sin β)
√ !
2 2 2
tmax sin γ ≤ min 2π |Fi |,
√ |Fi | ≤ √ |Fi |.
sin( N ) 3 3
94
4.2. Convergen
e du s
héma numérique
√
6
Lors de l'étape 2, dans le
as 1, elle est rempla
ée par |F|
ar
sin( 2π
N
)
√ !2 2
2 1
|Fj | + |Fi | + |Fk | + |Fi |
sin( 2π
N
) sin( 2π
N
)
2 2 1 2
≤ 2 |Fj |2 + 2
|Fi | + 2 |Fk | + |Fi |
sin2 ( 2π
N
) sin2 ( 2π
N
)
6 2
≤ (|Fi | + |Fj |2 + |Fk |2 ).
sin2 ( 2π
N
)
3
Enn, lors de l'étape 2, dans le
as 2, elle est rempla
ée par |F|
ar
sin( 2πN
)
√ !2 2 2
2 2 1
|Fj | + |Fi | + |Fk | + √ |Fi | |Fl | + |Fi |
sin( 2π
N
) 3 sin( 2π
N
)
2 4 1
tel-00346035, version 1 - 10 Dec 2008
≤ 2 |Fj |2 + 2 2 2 2
|Fi | + 2 |Fk | + |Fi | + 2 |Fl | + |Fi | 2
sin2 ( 2π
N
) 3 sin2 ( 2π
N
)
9 2
≤ (|Fi | + |Fj |2 + |Fk |2 + |Fl |2 ).
sin2 ( 2π
N
)
95
tel-00346035, version 1 - 10 Dec 2008
Troisième partie
tel-00346035, version 1 - 10 Dec 2008
97
tel-00346035, version 1 - 10 Dec 2008
Chapitre 5
Méthodes numériques utilisées et
programmation ee
tive
Sommaire
tel-00346035, version 1 - 10 Dec 2008
99
Chapitre 5. Méthodes numériques utilisées et programmation ee
tive
Dans
e
hapitre, nous présentons les méthodes numériques utilisées lors de la pro-
grammation ee
tive du modèle. Dans la se
tion 5.1, nous proposons d'utiliser l'algorithme
d'Uzawa pour réaliser le se
ond point du modèle à savoir
al
uler la vitesse réelle en tant
que proje
tion de la vitesse souhaitée. Nous détaillons
et algorithme, présentons les ré-
sultats de
onvergen
e asso
iés et terminons par sa programmation en Matlab. Ensuite,
nous nous intéressons au premier point modèle en programmant une vitesse souhaitée sou-
haitée parti
ulière, dirigée par le plus
ourt
hemin. Autrement dit, toutes les personnes
tentent de par
ourir la plus petite distan
e pour atteindre la sortie. An de
al
uler
ette
vitesse souhaitée, nous présentons une méthode de type Fast Mar
hing et détaillons sa
programmation en C++.
toute référen
e au pas de temps
ourant ainsi qu'au nombre de pas de temps (l'indi
e k
et l'exposant n sont omis). La vitesse réelle u est solution du problème de minimisation
sous
ontrainte suivant,
u = argmin |v − U(q)|2 ,
v∈Ch (q)
où h désigne le pas de temps et où Ch (q) est l'ensemble des vitesses admissibles au premier
ordre,
Ch (q) = v ∈ R2N , ∀ i < j , Dij (q) + h Gij (q) · v ≥ 0 .
Le Lagrangien du problème point-selle asso
ié est
1 X
L (v, λ) = |v − U(q)|2 − λij (Dij (q) + h Gij (q) · v) .
2 1≤i<j≤N
N(N−1)
Φ : R2N → R 2
v 7→ −h (Gij (q) · v)i<j
et
N(N−1)
Φ⋆ : R 2 → R2N P
λ 7 → −h i<j λij Gij (q) .
100
5.1. Cal
ul de la vitesse réelle ave
l'algorithme d'Uzawa
L'existen
e d'un point-selle (u, λ) pour L est immédiate (proposition H.11 p. 185). On a
alors la relation,
u = U(q) − Φ⋆ (λ),
autrement dit X
u = U(q) + h λij Gij (q) .
1≤i<j≤N
Ces notations étant xées, pré
isons l'algorithme d'Uzawa qui permet de déterminer u.
N(N−1)
N
2N N
On
onstruit deux suites (v )k ∈ R
k k +
et (µ )k ∈ (R ) 2 de la façon suivante :
µ0 = 0
vk+1 = U(q) − Φ⋆ µk
µk+1 = Π+ µk + ρ Φ vk+1 − D(q) ,
N(N−1)
où ρ est une
onstante stri
tement positive et Π+ est le proje
teur orthogonal sur (R+ ) 2 :
On remarque i
i l'intérêt d'un tel algorithme puisqu'on a substitué la proje
tion sur un
onvexe par une proje
tion sur R (simple tron
ature). D'après la proposition I.4 p. 191,
+
k
la suite v
onverge vers u solution du problème de minimisation lorsque
2
0 < ρ < ρmax = .
kΦk2
On peut même montrer que la suite des multipli
ateurs de Lagrange
onverge aussi,
N(N−1)
d'après la proposition I.5 p. 192. Plus pré
isément, la suite µk
onverge vers λ ∈ (R+ ) 2
Remarque 5.1 S'il y a toujours existen
e du multipli
ateur de Lagrange pour
e problème
de dimension nie, son uni
ité n'est pas assurée en général,
omme on l'a vu lors de
la sous-se
tion 4.2.2. Sans le moindre
al
ul, il est fa
ile de voir qu'on n'a pas uni
ité
lorsque la disposition des personnes forme un amas
ristallin assez grand. Considérons
par exemple la
onguration de N = 14 personnes représentée sur la gure 5.1, on peut
dénombrer 29
onta
ts a
tifs. Autrement dit, la dimension de l'espa
e où vit λ est 29,
101
Chapitre 5. Méthodes numériques utilisées et programmation ee
tive
alors que l'espa
e des
ongurations a pour dimension : 2 × 14 =28. L'appli
ation Φ⋆
n'est don
pas inje
tive. Par
onséquent, pour w ∈ R2N , l'ensemble
( )
N(N−1) X
+
Λw = λ∈ R 2
,w = λij Gij (q)
i<j
n'est pas réduit en général à un singleton. En revan
he, on a montré que
et ensemble,
quel que soit le nombre de personnes et de
onta
ts, est borné (théorème 4.10 p. 76).
Remarque 5.2 Pour les physi
iens
onsidérant des é
oulements granulaires,
ette non-
uni
ité est bien
onnue et typique de la stru
ture stri
tement monodisperse. Lorsque les
disques sont de tailles diérentes, l'uni
ité semble être générique (
f Iso
ounting
onje
ture
dans [DCST07℄). Dans le
adre des disques représentant des personnes,
ette non-uni
ité
du modèle idéalisé se traduira par une forte instabilité des pressions subies par les indivi-
dus.
Remarque 5.3 (Lien entre prox-régularité lo
ale et rapidité de
onvergen
e de
l'algorithme)
tel-00346035, version 1 - 10 Dec 2008
On note G(q) la matri
e remplie
olonne par
olonne par les ve
teurs Gij (q), où les
ouples (i, j) sont tels que Dij (q) = 0 (autrement dit, les
ouples (i, j) appartiennent à
l'ensemble Icontact déni par (3.4) p. 48). On dénit aussi la matri
e C(q) de la manière
suivante,
C(q) = t G(q)G(q). (5.1)
C'est une matri
e
arrée de taille ncontact égal au nombre de
onta
ts que présente la
onguration q (
ardinal de Icontact ). L'inégalité triangulaire inverse énon
ée à la propo-
sition 3.14 p. 52 arme qu'il existe une
onstante γ telle que pour tout q ∈ Q0 , pour tout
λ ∈ (R+ )ncontact vériant |λ|1 = 1, on ait
X 2 2
λij Gij (q) = t λt G(q)G(q)λ = t λC(q)λ ≥ 2 .
γ
(Dans la suite, pour pré
iser que l'on
onsidère λ ∈ (R+ )ncontact , on é
rira juste λ ≥ 0).
On dénit pour q ∈ Q0 , le paramètre lo
al γq vériant
2
min t λC(q)λ = ,
|λ|1 =1
λ≥0
γq2
102
5.1. Cal
ul de la vitesse réelle ave
l'algorithme d'Uzawa
Or
min t λC(q)λ ≤ min t λC(q)λ.
|λ|2 ≥1 |λ|2 ≥1
λ≥0
√
Comme pour tout λ, |λ|1 ≤ ncontact |λ|2 , on a
Finalement,
2ncontact
ηmin ≤ ncontact min t λC(q)λ = ncontact min t λC(q)λ = .
|λ|1 ≥1
λ≥0
|λ|1 =1
λ≥0
γq2
Ainsi
nv N
ηmin ≤ ,
γq2
tel-00346035, version 1 - 10 Dec 2008
où nv est le nombre maximal de voisins que peut avoir une personne (
f lemme 3.16 p. 53).
D'autre part, le
onditionnement de la matri
e C(q) vaut
ηmax
cond2 (C(q)) = kC(q)k2 kC(q)−1 k2 = .
ηmin
√
Comme Gij (q) = 2, on obtient que
kC(q)k2 = ηmax ≥ 2.
Ainsi,
2 2γq2
cond2 (C(q)) ≥ ≥ .
ηmin nv N
Par dénition de ηq , on obtient
p 1
cond2 (C(q)) ≥ √ min(ri + rj ).
ηq nv N (i,j)
103
Chapitre 5. Méthodes numériques utilisées et programmation ee
tive
5.1.2 Programmation
Prise en
ompte des obsta
les
On interdit aux disques de traverser les obsta
les présents, autrement dit on impose une
distan
e positive entre
es derniers. Si les obsta
les sont au nombre de nobst , on introduit
alors pour 1 ≤ i ≤ N et 1 ≤ l ≤ nobst ve
teurs Gil (q) ∈ R
obst 2N
, gradient de la distan
e
entre la personne i et l'obsta
le l :
Gobst
il (q) = (0, . . . , 0, −nil (q) , 0, . . . , 0),
i
où nil (q) est un ve
teur unitaire de R2 qui dépend de la position qi par rapport à l'obsta
le
l (
f. gure 5.2).
qi
obsta le l
qi
qi
Ces Nnobst nouvelles
ontraintes sont gérées numériquement de la même manière que
les
ontraintes de non-
hevau
hement entre les disques. On
al
ule de la même façon les
multipli
ateurs de Lagrange asso
iés. Le nombre de
onta
ts sus
eptibles d'être a
tivés
est nettement inférieur à
N(N − 1)
+ Nnobst .
2
Dans le
as où tous les rayons sont égaux à r par exemple,
haque disque est en
onta
t
ave
au plus 6 autres. Le nombre de
onta
ts est alors inférieur à (3 + nobst )N . Lors de
l'implantation, seules les
ontraintes
orrespondant à deux personnes pro
hes ou à une
personne près d'un obsta
le, sont a
tivées. Il est aussi hors de question de sto
ker la
obst
matri
e
ontenant tous les ve
teurs Gij (q) et Gil (q). On ne garde en mémoire que les
ve
teurs eij (q) et les ve
teurs nil (q).
Voi
i le noyau du programme
odé en Matlab. L'algorithme d'Uzawa s'arrête dès que le
hevau
hement relatif entre les personnes ou entre les individus et les obsta
les, se situe
en dessous d'un
ertain seuil (xé i
i à 10% du rayon minimal).
104
5.1. Cal
ul de la vitesse réelle ave
l'algorithme d'Uzawa
% h pas de temps
%
onta
t tableau de
onta
ts possibles
for instant = 1 : nt
105
Chapitre 5. Méthodes numériques utilisées et programmation ee
tive
Dans le
ode pré
édent, la mise à jour des
onta
ts potentiels à
haque instant est
ee
tuée de façon naïve (bou
le en O(N 2 ) pour
al
uler les distan
es, gestion non dy-
namique de la mémoire). An de diminuer le temps de
al
ul lors de simulations d'un
grand nombre de personnes, nous avons
hoisi d'utiliser le logi
iel SCoPI (Simulation de
Colle
tions de Parti
ules en Intera
tion),
odé en C++. Ce dernier gère e
a
ement les
onta
ts et il est fa
ile d'y intégrer notre modèle. Nous pré
isons les
ara
téristiques de
SCoPI dans la sous-se
tion suivante.
rieur (gravité, uide ...) d'intera
tion interparti
ulaire (for
e de
ohésion...) et de
onta
t
(inélastique, visqueux, agrégation...) qu'il souhaite. Le logi
iel permet également la prise
en
ompte de diérents types d'obsta
les (segments, disques en 2D, sphères, plans en 3D),
mobiles ou non. Cette modularité été obtenue par une programmation orientée objet et
par la
onstru
tion d'un diagramme de
lasses adapté.
An d'ee
tuer des simulations ave
un grand nombre de disques,
e logi
iel gère de ma-
nière e
a
e la mémoire ainsi que le temps de
al
ul. À
haque instant, ne sont
onsidérés
que les
onta
ts potentiels à l'instant suivant (
eux
on
ernant des disques susamment
pro
hes). An de déterminer
eux-
i, un algorithme de re
her
he des voisins de type bu-
ket sorting est utilisé. Son prin
ipe
onsiste à dé
ouper le domaine d'étude en boîtes
arrées et à ne
al
uler les distan
es qu'entre des parti
ules se trouvant dans des boîtes
2
voisines (au
une bou
le en N n'est ee
tuée).
Il reste à pré
iser que la méthode de proje
tion programmée dans
e logi
iel est l'al-
gorithme d'Uzawa, mais une autre méthode serait fa
ilement implantable. Grâ
e à la
modularité de SCoPI, il est fa
ile pour l'utilisateur d'intégrer dans le programme une vi-
tesse des disques a priori, de son
hoix (vitesse avant proje
tion). Dans notre
as, il s'agit
de la vitesse souhaitée par les personnes,
e qui nous amène à la se
tion suivante.
Dans
ette se
tion, nous nous intéressons au premier point du modèle, à savoir le
hoix de la vitesse souhaitée et à sa programmation. I
i, nous faisons en quelque sorte le
hoix le plus simple pour la vitesse souhaitée. Tous les individus sont supposés avoir le
même
omportement : ils veulent atteindre la sortie en par
ourant le plus
ourt
hemin.
On dénit pour
ela D(x) la distan
e géodésique entre la position x et la sortie la plus
106
5.2. Cal
ul de la vitesse souhaitée en utilisant une méthode de type Fast Mar
hing
|∇D(x)| = 1.
• la zone de pénombre
onstituée des noeuds où une valeur de D a été
al
ulée mais
pas en
ore xée ;
• la zone d'ombre
onstituée des noeuds très éloignés où la valeur de D n'a pas en
ore
été
al
ulée.
Pour initialiser
ette méthode, on dénit la zone é
lairée initialement,
'est-à-dire formée
des points où la valeur de D est
onnue. Il y en a dans notre
as deux types,
eux qui se
trouvent à une sortie où la valeur de D est xée à 0 et
eux qui se situent à l'intérieur
des obsta
les auxquels on asso
ie une très grande valeur de D . Ce
i permet de prendre en
ompte la géométrie des lieux en empê
hant le plus
ourt
hemin de traverser les obsta
les
présents,
omme l'illustre la gure 5.3. Sur
elle-
i, on a tra
é les lignes de niveau de D,
al
ulée par la méthode de Fast Mar
hing, pour une piè
e
ontenant 5 obsta
les et dont
la sortie se trouve à gau
he.
Après l'initialisation des noeuds é
lairés, on dénit la zone de pénombre initiale. Elle est
onstituée par les points qui n'appartiennent pas à la zone é
lairée et voisins des points
é
lairés. Pour
ha
un de
es points, la valeur de D est
al
ulée de sorte qu'une version
dis
rète de l'équation |∇D| = 1 soit satisfaite. Pré
isons
elle-
i. On note hF M M le pas de
107
Chapitre 5. Méthodes numériques utilisées et programmation ee
tive
la grille et Di,j la valeur de D au noeud (i, j). On dénit les dérivées partielles appro
hées
par rapport à x à gau
he et à droite
omme suit :
−y +y
max(∆−x +x 2 2
ij , −∆ij , 0) + max(∆ij , −∆ij , 0) = 1. (5.2)
La valeur de D pour les points restants
onstituant la zone d'ombre est initialisée à +∞.
Il reste à expliquer
omment on
al
ule de manière e
a
e Di,j de telle sorte que l'égalité
(5.2) soit satisfaite.
Cal
ul de Di,j :
On
al
ule a = min(Di−1,j , Di+1,j ) et b = min(Di,j−1, Di,j+1).
Si |a − b| < hF M M alors on pose
p
tel-00346035, version 1 - 10 Dec 2008
Remarque 5.4 On peut vérier qu'ave
ette valeur de Di,j , l'équation (5.2) est satis-
faite.
Maintenant que les trois zones initiales ont été dénies, expliquons
omment se déroule
une étape de la Fast Mar
hing. On
onsidère le noeud (imin , jmin) de la zone de pénombre
ayant la plus petite valeur de D. On ajoute
e point (imin , jmin ) à la zone é
lairée et on
l'enlève de la zone de pénombre. Ses voisins (i, j) qui se trouvent dans la zone d'ombre
passent alors dans la zone de pénombre et la valeur Di,j est
al
ulée
omme expliqué
i-dessus. Et ainsi de suite jusqu'à
e que tous les points de la grille soient é
lairés. La
gure 5.4 illustre le déroulement de la Fast Mar
hing. Sur
elle-
i, les points de la grille
présentant une très grande valeur de D (points intérieurs aux obsta
les ou dans la zone
d'ombre) ne sont pas
oloriés. Les deux images représentant l'instant initial et un instant
ultérieur de la Fast Mar
hing montrent la propagation des zones é
lairée et de pénombre.
Remarque 5.5 Si on imagine qu'aux noeuds présents à la sortie se trouvent des émet-
teurs de lumière, les autres noeuds seront déterminés dans l'ordre où ils sont atteints par
la lumière.
Le seul
oût que présente
ette méthode est la re
her
he du noeud (imin , jmin ). Une stru
-
ture de tas ( heap ) est don
utilisée pour sto
ker la liste des points
onstituant la zone de
pénombre. Si np est le nombre de points de la grille, la
omplexité de la Fast Mar
hing
Method est en O(np log np ).
108
5.2. Cal
ul de la vitesse souhaitée en utilisant une méthode de type Fast Mar
hing
noeuds é lairés
où par exemple les stru
tures de tas ( map, multimap ) existent déjà. Notre obje
tif est
de pouvoir simuler l'éva
uation de milliers de personnes hors de salles ou de bâtiments
de géométrie quel
onque. Nous avons dû pour
ela ajouter au
ode SCoPI de nouvelles
lasses renfermant les données géométriques. Il a également fallu ajouter d'autres
lasses
an que la vitesse des disques avant proje
tion soit la vitesse souhaitée dirigée par le plus
ourt
hemin.
On rappelle qu'une
lasse est une des
ription d'objet. Elle possède des attributs
'est-à-
dire des données et des méthodes ou plus simplement des fon
tions. Pour représenter une
lasse, on tra
e son diagramme dont un exemple est donné sur la gure 5.5.
109
Chapitre 5. Méthodes numériques utilisées et programmation ee
tive
Ens_Ma
ros_Obs_h permet quant à elle de
réer des ensembles de Ma
ro_Obs. Détaillons
les
lasses Ens_Ma
ros_Obs_h et Ma
ro_Obs. Sur la gure 5.6, le diagramme de
es
lasses
a été tra
é ave
le logi
iel ArgoUML.
tel-00346035, version 1 - 10 Dec 2008
110
5.2. Cal
ul de la vitesse souhaitée en utilisant une méthode de type Fast Mar
hing
Classe Ma
ro_Obs
Ses attributs sont :
Type
Nombre d'obsta
les
Numéro dans l'ensemble Ens_Ma
ros_Obs_h
Ensemble d'objets Obsta
le
Ses prin
ipales méthodes sont :
Méthodes renvoyant les diérents attributs
Méthodes permettant de faire du
al
ul ve
toriel
Méthode prenant en argument les
oordonnées d'un point et renvoyant 0 ou 1 suivant
sa présen
e ou non à l'intérieur de l'ensemble d'obsta
les
onsidéré (
odé dans la
lasse lle)
Le type de la
lasse Ma
ro_Obs est un entier qui est égal à 0 quand il s'agit d'une
lasse
Ma
ro_Room, 1 pour une
lasse Ma
ro_Table, 2 pour une
lasse Ma
ro_Stairwell, 3 pour
une
lasse Ma
ro_Stair et enn 5 pour une
lasse Ma
ro_Door. Toutes
es
lasses lles
héritent des attributs et des méthodes dé
rits pour la
lasse Ma
ro_Obs.
tel-00346035, version 1 - 10 Dec 2008
La méthode essentielle de
ette
lasse (appelée inside ) est la dernière évoquée puisque
'est elle que nous allons utiliser lors de l'initialisation de la méthode Fast Mar
hing. Son
a
tion est la même pour tous les Ma
ro_Obs mais sa programmation est diérente suivant
le type de Ma
ro_Obs. Elle sera don
odée au niveau des
lasses lles en utilisant les
méthodes et attributs parti
uliers de
es dernières. Les diagrammes des
lasses lles se
trouvent à la n de
ette se
tion.
111
Chapitre 5. Méthodes numériques utilisées et programmation ee
tive
tel-00346035, version 1 - 10 Dec 2008
112
5.2. Cal
ul de la vitesse souhaitée en utilisant une méthode de type Fast Mar
hing
Classe VSG_Level_h
Ses prin
ipaux attributs sont :
Numéro dans l'ensemble Vap_Souh_Geo_h
Pas de la grille pour la méthode de Fast Mar
hing
Sa prin
ipale méthode toujours appelée run prend en argument la
lasse Parti
le et
renvoit la vitesse souhaitée de
elle-
i. Elle est
odée dans les
lasses lles.
Pour
al
uler la valeur de la première
omposante de ∇D dans une
ase, on utilise les
valeurs de D aux 4
oins de
elle-
i en faisant la moyenne des deux taux d'a
roissements
li
ites. On pro
ède de manière analogue pour la deuxième
omposante de ∇D . Les ta-
bleaux GradX et GradY sont ainsi
al
ulés une seule fois lors de la
réation de l'objet
VSG_Room_h à l'instant initial.
113
Chapitre 5. Méthodes numériques utilisées et programmation ee
tive
tel-00346035, version 1 - 10 Dec 2008
114
5.2. Cal
ul de la vitesse souhaitée en utilisant une méthode de type Fast Mar
hing
115
Chapitre 5. Méthodes numériques utilisées et programmation ee
tive
tel-00346035, version 1 - 10 Dec 2008
116
tel-00346035, version 1 - 10 Dec 2008
Sommaire
6.1 Résultats re
ouvrant les phénomènes d'auto-organisation 121
119
Chapitre 6. Résultats numériques
Dans
e
hapitre, nous pré
isons le premier point du modèle, à savoir le
hoix de la
vitesse souhaitée, en proposant plusieurs exemples. Nous présentons pour
haque option
les résultats numériques asso
iés, obtenus en intégrant la vitesse souhaitée
hoisie dans
l'algorithme numérique détaillé dans la se
tion 5.1. Dans la se
tion 6.1, nous retrouvons
ertains phénomènes d'auto-organisation (dé
rits dans la se
tion 1.1) à l'aide de vitesses
souhaitées simples
onstruites à la main . Dans la se
tion 6.2, la vitesse souhaitée
hoisie
pour tous les individus est
elle dirigée par le plus
ourt
hemin. Les résultats numériques
présentés sont issus de la programmation en C++ (implantation d'une méthode de type
Fast Mar
hing) détaillée dans la se
tion 5.2. Dans la se
tion 6.3, nous proposons de prendre
omme vitesse souhaitée la solution d'une équation aux dérivées partielles en prenant en
ompte les obsta
les à l'aide de
onditions aux bords sur
es derniers. Enn, dans la
se
tion 6.4, nous diérentions le
omportement des personnes en ajoutant des stratégies
individuelles : ralentissement ou
ontournement lors d'un embouteillage.
tel-00346035, version 1 - 10 Dec 2008
120
6.1. Résultats re
ouvrant les phénomènes d'auto-organisation
nisation
Les trois premières séries de
al
uls présentées
i-dessous ont été ee
tuées sous Mat-
lab. Le but i
i est de vérier le programme sur quelques
as simples et de retrouver
ertains
phénomènes observés et dé
rits dans la se
tion 1.1.
6.1.1 A
ès à un es
alator
Ce premier exemple traite de 300 personnes qui sortent d'un train et se dirigent vers
un es
alator. Elles se dépla
ent toutes à la même allure. Le paramètre h est xé de telle
sorte qu'une personne libre de ses mouvements par
ourt en un pas de temps, une distan
e
égale à sa propre taille. Sur la gure 6.1, on retrouve la tendan
e des individus à se pla
er
autour de la sortie en formant des
er
les.
t =1 t =5
tel-00346035, version 1 - 10 Dec 2008
t =30 t =70
t =120 t =210
t =400 t =540
121
Chapitre 6. Résultats numériques
Nous avons
onsidéré une population non homogène de petits disques et de gros disques
(diamètre triple de
elui des petits), en supposant que les petits avan
ent trois fois plus
vite que les autres, ou plus pré
isément que leur vitesse souhaitée a un module trois fois
supérieur (
f. g. 6.3). Le pas de temps h est pris de telle manière qu'un petit disque libre
par
ourt en un pas de temps, une distan
e égale à son propre diamètre. On remarque
i
i l'importan
e de gérer les
ontraintes de non-
hevau
hement entre les disques et les
obsta
les. En eet, même si les personnes veulent éviter l'obsta
le près de la sortie, elles
sont poussées vers
elui-
i par les individus situés derrière elles.
Par ailleurs, lors de
es simulations, on observe qu'au
un prin
ipe du maximum n'est
vérié : le module de la vitesse d'un individu peut notamment être supérieur au module
de la vitesse souhaitée. I
i, l'allure des gros disques (poussés par les petits) peut être plus
de 2 fois supérieure au module de leur vitesse souhaitée.
122
6.1. Résultats re
ouvrant les phénomènes d'auto-organisation
t =1
t =40
tel-00346035, version 1 - 10 Dec 2008
t =80
t =120
123
Chapitre 6. Résultats numériques
124
6.1. Résultats re
ouvrant les phénomènes d'auto-organisation
on quittait la piè
e, on n'était plus soumis à de fortes pressions,
omme protégé par
les personnes situées à l'arrière (formant des ar
hes en amont de la sortie).
Ces
al
uls ont été réalisés à l'aide du logi
iel SCoPI (Simulation de Colle
tions de Par-
ti
ules en Intera
tion) présenté à la sous-se
tion 5.1.3.
125
Chapitre 6. Résultats numériques
tel-00346035, version 1 - 10 Dec 2008
126
6.2. Vitesse souhaitée dirigée par le plus
ourt
hemin
127
Chapitre 6. Résultats numériques
tel-00346035, version 1 - 10 Dec 2008
128
6.2. Vitesse souhaitée dirigée par le plus
ourt
hemin
tel-00346035, version 1 - 10 Dec 2008
129
Chapitre 6. Résultats numériques
Nous présentons i
i une autre idée pour dénir un
hamp de vitesse souhaitée prenant
en
ompte les obsta
les. Ce
hoix a été testé avant
elui de la se
tion pré
édente et bien
qu'il donne des résultats raisonnables, il reste moins justié en termes de modélisation
que le ot géodésique et n'a pas été plus développé. Nous l'illustrons simplement par
l'éva
uation d'une salle
ontenant deux obsta
les rond et
arré.
Nous avons d'abord
onsidéré le
hamp de vitesse F de norme 1 visant la sortie et soumis
à au
une
ontrainte (
f. g 6.8(b)). Ensuite, à l'aide de FreeFem++, nous avons
al
ulé
obs
le
hamp F
omme proje
tion de F sur un espa
e
ontraint prenant en
ompte les
obs
obsta
les. Plus pré
isément, F vérie
ave
des
onditions de Diri
hlet aux bords des obsta
les. Après renormalisation, nous
obtenons le
hamp W représenté sur la gure 6.8(
), interpolé par le
hamp V sur un
maillage
artésien (
f. g 6.8(d)). Ensuite, nous ré
upérons les données du maillage
ar-
tésien et le
hamp V pour intégrer
e
hoix de vitesse dans le logi
iel SCoPI (de la même
tel-00346035, version 1 - 10 Dec 2008
manière que pour le
hoix de la se
tion 6.2). À
haque instant, la vitesse souhaitée de
toute personne est
al
ulée en fon
tion de sa position
omme une interpolation du
hamp
V. Sur la gure 6.9, nous avons représenté les
ongurations obtenues à diérents instants
lors de l'éva
uation de 700 personnes.
130
6.3. Vitesse souhaitée en tant que solution d'une e.d.p.
tel-00346035, version 1 - 10 Dec 2008
131
Chapitre 6. Résultats numériques
tel-00346035, version 1 - 10 Dec 2008
132
6.4. Ajout de stratégies individuelles
6.4.1 Modélisation
Nous supposons maintenant que les personnes peuvent élaborer des stratégies
om-
plexes dans des zones fortement en
ombrées. Nous avons
hoisi de modéliser deux
as
de gures lorsqu'un individu se retrouve fa
e à un embouteillage : soit il dé
élère pour
ne pas aggraver la situation, soit il développe une stratégie d'évitement pour traverser
ou
ontourner la foule. La vitesse de
et individu dépend alors de la position des per-
sonnes qu'il voit devant lui. Plus pré
isément, nous dénissons l'ensemble Ni (
f. g. 6.10)
ontenant les personnes pro
hes de l'individu i et se trouvant dans son
hamp de vision :
souhaitée dirigée par le plus
ourt
hemin (
f. dénition dans la se
tion 5.2). On peut aussi
prendre un
hamp de vitesse souhaitée
onstruit à la main ,
e qui a été appliqué dans
les exemples de la sous-se
tion 6.4.2. Détaillons maintenant les deux possibilités laissées
ℓprox
PSfrag repla
ements α di
à l'individu i lorsque ses voisins (appartenant à Ni ) se dépla ent plus lentement que lui.
133
Chapitre 6. Résultats numériques
di = dnew
i di dnew
i
di dnew
i
qj r
−e⊥
ij r e⊥
qj l ij l
eij r eij l
(
) Contournement.
2. Il peut aussi être pressé et dé
ider de ne pas ralentir. Dans
e
as, il
onserve son
allure souhaitée et modie sa dire
tion (si besoin est) an d'emprunter un
hemin
peu en
ombré. Pré
isons
e point. Si le
hemin dans la dire
tion de di est libre,
l'individu i l'emprunte (
f. g. 6.11(a)). Sinon, le
hamp de vision de l'individu est
dé
oupé en se
teurs angulaires et le se
teur le plus pro
he de la dire
tion souhaitée
di initiale et
ontenant le moins de voisins est déterminé. Si
e se
teur
ontient au
new
plus 3 personnes, l'individu i part dans la dire
tion di donnée par la bisse
tri
e
du se
teur angulaire
hoisi (
f. g. 6.11(b)). Sinon, il
hoisit de
ontourner le groupe
new
Ni . Là en
ore, il prend la dire
tion possible di la plus pro
he de sa dire
tion di
voulue au départ :
où j r (j l ) est le voisin le plus à droite (à gau he) de l'individu i ( f. g. 6.11( )).
134
6.4. Ajout de stratégies individuelles
tel-00346035, version 1 - 10 Dec 2008
Fig. 6.12 Comparaison des traje
toires sans (haut) ou ave
(bas) la stratégie d'évite-
ment.
Nous souhaitons maintenant illustrer la tendan
e à dé
élérer (
f. se
tion 6.4
as 1). Pour
e faire, nous
onsidérons 100 personnes initialement bloquées qui veulent aller à gau
he
à l'instant t = 0. Sur la gure 6.13, nous traçons la
onguration à diérents instants et
observons une onde de détente : les individus
ommen
ent à se dépla
er l'un après l'autre.
135
Chapitre 6. Résultats numériques
Nous avons également
onsidéré l'éva
uation de trois populations distin
tes par leur
omportement et représenté sur la gure 6.14 la
onguration à diérents instants. Les
disques bleus représentent une
entaine de personnes développant une stratégie d'évite-
ment, les disques magentas
on
ernent environ 200 personnes préférant dé
élérer, quant
aux 300 disques rouges, ils traitent des individus n'ayant au
une stratégie. Ils ont tous
la même dire
tion souhaitée (
f. g. 6.2 p. 122), mais les deux premières
atégories d'in-
dividus veulent aller 3 fois plus vite que la dernière. Le paramètre ℓprox a été xé à 5
diamètres. On peut remarquer la nette tendan
e des bleus (
ausée par leur stratégie), à se
dépla
er aux bords du ux piétonnier. Par ailleurs, en examinant les
ongurations aux
instants t = 55 et t = 110, on observe que
ette stratégie permet à la plupart des bleus
de s'é
happer du
ouloir plus rapidement que les magentas.
tel-00346035, version 1 - 10 Dec 2008
136
6.4. Ajout de stratégies individuelles
t =1
t =55
tel-00346035, version 1 - 10 Dec 2008
t =110
t =170
137
tel-00346035, version 1 - 10 Dec 2008
tel-00346035, version 1 - 10 Dec 2008
139
Annexes
tel-00346035, version 1 - 10 Dec 2008
Annexe A
Quelques résultats d'analyse
onvexe
tel-00346035, version 1 - 10 Dec 2008
141
Annexe A. Quelques résultats d'analyse
onvexe
Soit H un espa
e de Hilbert. Le produit s
alaire entre les ve
teurs x et y de H est noté
(x, y) et la norme du ve
teur x est notée |x|. On
onsidère dans la suite K un ensemble
onvexe fermé non vide de H.
Théorème A.1 (Proje
tion sur un
onvexe fermé) Pour tout z ∈ H , il existe un
tel-00346035, version 1 - 10 Dec 2008
Le ve
teur x est appelé projeté de z sur K et sera noté PK (z). De plus, le projeté x est
ara
térisé par la propriété
(
x ∈ K,
(z − x, y − x) ≤ 0 ∀y ∈ K.
Propriété A.1 La fon
tion IK est
onvexe, propre et semi-
ontinue inférieurement.
Dénition A.3 Soit x ∈ H , on appelle sous-diérentiel de la fon
tion IK au point x
l'ensemble
∂IK (x) = {v ∈ H , IK (x) + (v, h) ≤ IK (x + h) , ∀h ∈ H}.
142
Proposition A.4 Pour x ∈ ∂K , on a les égalités suivantes
déf
∂IK (x) = (K − x)◦ = {v ∈ H , ∀y ∈ K , (v, y − x) ≤ 0} (a)
!◦
[
= λ(K − x) (b)
λ>0
= {v ∈ H , x = PK (x + v)}. (c)
Démonstration :
Comme x ∈ ∂K ⊂ K , on a par dénition,
On a don
prouvé l'égalité (a) (
f. dénition du
ne polaire C.1 p. 150). On en déduit
aisément l'égalité (b). L'égalité (
) provient de la
ara
térisation de la proje
tion sur un
onvexe fermé dans un espa
e de Hilbert (
f. théorème A.1).
Remarque A.5 D'après la proposition pré
édente, l'ensemble ∂IK (x), pour x ∈ ∂K , est
un
ne
onvexe fermé de H .
La proposition suivante pré
ise le sous-diérentiel de l'indi
atri
e de K en des points
quel
onques de H.
143
Annexe A. Quelques résultats d'analyse
onvexe
Proposition A.8 Soit K ⊂ H un
onvexe fermé non vide de H , l'égalité suivante est
vraie,
∀x ∈ K , ∂IK (x) = N(K, x).
Démonstration :
On
ommen
e par montrer l'in
lusion : ∂IK (x) ⊂ N(K, x).
Soit v ∈ ∂IK (x) , v 6= 0. Comme x ∈ K, on a par dénition du sous-diérentiel,
∀α > 0 , x 6= PK (x + αv).
Ce
i implique
∀α > 0 , dK (x + αv) < α|v|.
Notons kα = PK (x + αv) , kα 6= x. On a alors dK (x + αv) = |x + αv − kα |. Par
onséquent,
tel-00346035, version 1 - 10 Dec 2008
|x + αv − kα |2 < α2 |v|2 ,
e qui équivalent à
Or d'après (A.1),
(v, kα − x) ≤ IK (x + kα − x) ≤ IK (kα ) = 0.
Ce
i ajouté à (A.2) donne l'inégalité suivante, |x − kα |2 < 0,
e qui est absurde. Ainsi, on
a montré le résultat suivant
∃α > 0 , x ∈ PK (x + αv).
On en
on
lut que v ∈ N(K, x).
Il reste à montrer l'autre in
lusion : N(K, x) ⊂ ∂IK (x) .
Soit v ∈ N(K, x) , v 6= 0, on a par dénition,
∀k ∈ K , (k − x, x + αv − x) ≤ 0,
e qui est équivalent à
∀k ∈ K , α(k − x, v) ≤ 0,
et implique
∀k ∈ K , (k − x, v) ≤ 0.
On en déduit d'après la proposition A.4 (a), que v ∈ ∂IK (x).
144
tel-00346035, version 1 - 10 Dec 2008
145
Annexe B
Lemme de Farkas
Annexe B. Lemme de Farkas
Le lemme de Farkas est utilisé lors de la preuve de la proposition 2.6 p. 25. On rappelle
sa démonstration issue de [All05℄
ar le sous-lemme B.2 qu'elle utilise, est né
essaire pour
prouver la proposition H.11 p. 185.
Dans la suite, on
onsidère V un espa
e de Hilbert muni de son produit s
alaire noté ( , ).
Lemme B.1 (Lemme de Farkas) Soient a1, a2 , ..., aM ∈ V , on note les ensembles
( M
)
X
E = {v ∈ V , ∀i ∈ {1, .., M} , (ai , v) ≤ 0} et Ê = v ∈ V , ∃ λ1 , ., λM ≥ 0 , v = − λi ai .
i=1
p ∈ Ê ⇐⇒ ∀w ∈ E, (p, w) ≥ 0.
Démonstration :
L'impli
ation dire
te est évidente. Prouvons l'impli
ation ré
iproque. On va pour
ela
tel-00346035, version 1 - 10 Dec 2008
démontrer la ontraposée :
p∈
/ Ê ⇒ ∃w ∈ E, (p, w) < 0.
d'où
∀i ∈ {1, .., M} , ∀λ ≥ 0 , α < −λ(w, ai ).
En faisant tendre λ vers+∞, on observe que (w, ai ) ≤ 0 pour tout i ∈ {1, .., M}. En
on
lusion, w∈E et (p, w) < 0,
e qui prouve le résultat annon
é.
146
as 1 : les ve
teurs(ai )i∈{1..M }sont indépendants.
P
Soit
n
(v )n∈N = − M n
i=1 λi ai qui
onverge vers v ∈ V . Cette
onver-
une suite de Ê
n∈N
gen
e implique la
onvergen
e
oordonnée par
oordonnée dans la base de l'espa
e en-
gendré par les ve
teurs (ai )i∈{1,..,M }. Par
onséquent, pour tout i ∈ {1, .., M}, il existe
λi ∈ R tel que
λni −−−→ λi .
n→∞
λi0 λi
= min .
µi0 i∈J µi
tel-00346035, version 1 - 10 Dec 2008
λi0
Alors en posant t=− < 0, on obtient
µi0
Ainsi,
M
( M
)
[ X
Ê = v ∈ V, ∃ λ1 , .., λM ≥ 0, v = − λi ai .
i0 =1 i6=i0
Par hypothèse de ré
urren
e,
haque ensemble apparaissant dans le membre de droite est
fermé. Par
onséquent, Ê est fermé, en tant qu'union nie d'ensembles fermés.
147
tel-00346035, version 1 - 10 Dec 2008
tel-00346035, version 1 - 10 Dec 2008
149
Annexe C
Cne polaire
Annexe C. Cne polaire
Dans
ette annexe, on rappelle quelques résultats
lassiques
on
ernant les
nes po-
laires qu'on trouve dans [Mau04℄. Soit H un espa
e de Hilbert muni du produit s
alaire
( , ), on
onsidère dans toute la suite C⊂H
un
ne
onvexe fermé non vide de sommet
◦
0. On note PC la proje
tion sur C . On dénit C le
ne polaire de C de la façon suivante,
La proposition suivante démontrée dans [Mor62℄ est fondamentale, elle est, par exemple,
utilisée lors de la preuve de la proposition 3.9 p. 48.
Proposition C.3 Soit C ⊂ H un
ne
onvexe fermé non vide de sommet 0, alors
PC + PC ◦ = I. De plus, si f = u + ũ où u = PC (f ) et ũ = PC ◦ (f ) alors (u, ũ) = 0.
Démonstration :
Soit f ∈ H, on note u = PC f , le projeté de f sur C qui est
ara
térisé par,
tel-00346035, version 1 - 10 Dec 2008
(
u ∈ C,
∀v ∈ C, (f − u, v − u) ≤ 0.
étape 1 : f − u ∈ C◦
1
Soit w ∈ C, on pose v= (2w + 2u) = w + u ∈ C
ar C est un
ne
onvexe. On a don
2
(f − u, w) = (f − u, v − u) ≤ 0.
Ce
i étant vrai pour tout w ∈ C, on a bien que f − u ∈ C ◦.
étape 2 : (u, f − u) = 0
Comme u ∈ C et f − u ∈ C ◦ , on a (u, f − u) ≤ 0. Par ailleurs,
∀v ∈ C, (f − u, v − u) ≤ 0.
1 1
En parti
ulier pour v = u, on obtient que − (u, f − u) ≤ 0. Finalement, (u, f − u) = 0.
2 2
étape 3 : f − u = PC ◦ f
On veut montrer que
∀w ∈ C ◦ , (f − (f − u) , w − (f − u)) ≤ 0,
e qui est équivalent à
∀w ∈ C ◦ , (u, w) − (u, f − u) ≤ 0,
et don
à
∀w ∈ C ◦ , (u, w) ≤ 0.
Ce
i est vrai par dénition de C ◦.
150
Proposition C.4 Soit C ⊂ H un
ne
onvexe fermé non vide de sommet 0 et soit C ◦◦
le
ne polaire de C ◦ , alors C ◦◦ = C.
Démonstration :
C ◦◦ = {v ∈ H, ∀u ∈ C ◦ , (u, v) ≤ 0}, d'où C ◦◦ ⊃ C . L'autre in
lusion s'appuie sur le
⋆
lemme suivant où IC est l'indi
atri
e de C (
f. dénition A.2 p. 142) et IC la fon
tion
onjuguée de IC dénie par,
déf
IC⋆ (x) = sup [(x, y) − IC (y)] = sup (x, y) .
y∈H y∈C
Lemme C.5 Soit C ⊂ H un ne onvexe fermé non vide de sommet 0, alors IC⋆ = IC ◦ .
Si x∈
/C alors d'après la proposition C.3, on peut é
rire x sous la forme,
x = xC + z où xC ∈ C et z ∈ C ◦ , z 6= 0.
De plus, toujours d'après la proposition C.3, (x, z) = (xC , z) + (z, z) = |z|2 . Or,
151
tel-00346035, version 1 - 10 Dec 2008
Annexe D
Opérateurs maximaux monotones
tel-00346035, version 1 - 10 Dec 2008
153
Annexe D. Opérateurs maximaux monotones
Dans
ette annexe, on présente deux résultats sur les opérateurs maximaux monotones
issus de [Bre73℄ qui permettent de justier les
on
lusions de la se
tion 2.2. Dans la suite,
on se pla
e dans un espa
e de Hilbert H muni d'un produit s
alaire noté ( , ). On note
I l'identité sur H et on
onsidère A un opérateur multivalué de H.
Dénition D.1 (Domaine d'un opérateur) On appelle domaine de l'opérateur A l'en-
semble
déf
D(A) = {x ∈ H, Ax 6= ∅}.
Dénition D.2 (Opérateur monotone) L'opérateur A est monotone si
∀ x1 , x2 ∈ D(A) , ∀ y1 ∈ Ax1 , ∀ y2 ∈ Ax2 , (y1 − y2 , x1 − x2 ) ≥ 0.
Alors, pour tout u0 ∈ D (A), il existe une unique fon
tion u ∈ W 1,1 ([0, T ], H) solution de
du (t) + Au(t) + B(t, u(t)) ∋ 0 p.p.
dt
u(0) = u0 .
Théorème D.5 Soit K un
onvexe fermé non vide de H , on
onsidère l'opérateur maxi-
mal monotone A = ∂IK . Pour toute fon
tion f ∈ C 0 ([0, T ], H) et pour tout u0 ∈ D(A),
il existe une unique fon
tion u ∈ W 1,∞ ([0, T ], H) vériant
du (t) + Au(t) ∋ f (t) p.p.
dt
u(0) = u0 .
De plus, u est dérivable à droite en tout point t de ]0, T [ et
ette dérivée vaut
d+ u
(t) = f (t) − PAu(t) (f (t)).
dt
154
Annexe E
Étude du gradient de la fon
tion D12
tel-00346035, version 1 - 10 Dec 2008
155
Annexe E. Étude du gradient de la fon
tion D12
Propriété E.1 L'appli
ation G̃12 est diérentiable en tout point de Q12 et sa diéren-
tielle au point q vérie
1
DG̃12 (q) : h 7→ √ (−Pe12 ⊥ (h2 − h1 ), Pe12 ⊥ (h2 − h1 ), 0, . . . , 0) ,
2|q2 − q1 |
tel-00346035, version 1 - 10 Dec 2008
où Pe12 ⊥ est la proje
tion sur e⊥12 , ve
teur unitaire de R2 , orthogonal (dire
t) à e12 . Au-
trement dit,
Pe12 ⊥ (v) = v − (v · e12 )e12 .
Démonstration :
On dénit la fon
tion f
omme suit : f(q) = |q2 − q1 |. On a,
156
Propriété E.2 L'appli
ation G̃12 est lips
hitzienne ave
une
onstante de Lips
hitz,
√
2
CG̃12 ≤ .
r1 + r2
Démonstration :
D'après la proposition E.1, on a,
1
|DG̃12 (q)[h]|2 ≤ 2|h2 − h1 |2 ,
2|q2 − q1 |2
et en
onséquen
e,
|h2 − h1 |
|DG̃12 (q)[h]| ≤ .
|q2 − q1 |
Or, on a |h2 − h1 |2 = (hx2 − hx1 )2 + (hy2 − hy1 )2 ≤ 2 ((hx2 )2 + (hy2 )2 + (hx1 )2 + (hy1 )2 ) = 2|h|2.
D'où,
√ |h|
|DG̃12 (q)[h]| ≤ 2
|q2 − q1 |
tel-00346035, version 1 - 10 Dec 2008
√
2
≤ |h|.
r1 + r2
On obtient don
le résultat annon
é.
la fon
tion D12 est
onvexe et on retrouve bien le fait que la hessienne
D2 D12 (q)[·, ·] = D2 f(q)[·, ·]
157
tel-00346035, version 1 - 10 Dec 2008
Annexe F
Autre preuve de la prox-régularité de
Q12
tel-00346035, version 1 - 10 Dec 2008
159
Annexe F. Autre preuve de la prox-régularité de Q12
Voi
i une autre façon de démontrer les propositions 3.3 et 3.6 p. 45, sans utiliser
des notions de géométrie diérentielle. On rappelle la dénition de Q12 et l'énon
é de la
première proposition.
4
X 2N
X
v= αi vi + βj wj ,
tel-00346035, version 1 - 10 Dec 2008
i=1 j=5
où les
oe
ients αi et βj sont des réels. En eet, on retrouve les 4 premiers ve
teurs de
la base
anonique de R2N ave
les ve
teurs vi ,
1
(1, 0, 0, 0, 0, . . . , 0) = (v1 + v3 )
2
1
(0, 1, 0, 0, 0, . . . , 0) = (v2 + v4 )
2
1
(0, 0, 1, 0, 0, . . . , 0) = (v1 − v3 )
2
1
(0, 0, 0, 1, 0, . . . , 0) = (v2 − v4 ).
2
Etape 1 : On va d'abord montrer que
N(Q12 , q) ⊂ R+ v3 .
et tels que
2N
X
v = α1 v1 + α2 v2 + α3 v3 + α4 v4 + βj wj .
j=5
On
her
he à savoir, sous quelles
onditions, le ve
teur v ∈ N(Q12 , q), plus pré
isément,
sous quelles
onditions, il existe t>0 tel que q ∈ PQ12 (q + tv).
On
onsidère t > 0, alors
y
q+tv = (tα1 +tα3 , tα2 +tα4 , r1 +r2 +tα1 −tα3 , tα2 −tα4 , q3x +tβ5 , q3y +tβ6 , . . . , q2N +tβ2N ).
160
Soit maintenant,
q̃ = q+tv−tα3 v3 = (tα1 , tα2 +tα4 , r1 +r2 +tα1 , tα2 −tα4 , q3x +tβ5 , q3y +tβ6 , . . . , q2N
y
+tβ2N ),
al ulons :
D12 (q̃) = |(r1 + r2 + tα1 , tα2 − tα4 ) − (tα1 , tα2 + tα4 )| − (r1 + r2 )
= |(r1 + r2 , −2tα4 )| − (r1 + r2 ) ≥ 0.
v = α3 v3 .
√
tel-00346035, version 1 - 10 Dec 2008
v = v3 .
R+ v3 ⊂ N(Q12 , q).
r1 + r2 √
Soit t≤ , montrons que dQ12 (q + tv3 ) = t 2,
'est-à-dire que
2
√
B(q + tv3 , t 2) ∩ Q12 = ∅.
√
Soit q̃ ∈ B(q + tv3 , t 2), il existe (α1 , α2 , α3 , α4 , β5 , . . . , β2N ) ∈ R2N , vériant
1
α12 + α22 + α32 + α42 + (β52 + · · · + β2N
2
)<1
2
et tels que
Cal ulons
D12 (q̃) = |(r1 + r2 + tα1 − tα3 − t, tα2 − tα4 ) − (tα1 + tα3 + t, tα2 + tα4 )| − (r1 + r2 )
= |(r1 + r2 − 2tα3 − 2t, −2tα4 )| − (r1 + r2 ).
161
Annexe F. Autre preuve de la prox-régularité de Q12
Par onséquent,
D12 (q̃) < 0 ⇔ |(r1 + r2 − 2tα3 − 2t, −2tα4 )|2 < (r1 + r2 )2
⇔ (2t(α3 + 1))2 − 4t(α3 + 1)(r1 + r2 ) + (2tα4 )2 < 0
⇔ (t(α3 + 1))2 − t(α3 + 1)(r1 + r2 ) + (tα4 )2 < 0.
P (X) < 0 ⇔ X ∈ ]s− , s+ [. Il reste par
onséquent à vérier que t(α3 + 1) ∈ ]s− , s+ [. On
2 2
a α3 + α4 < 1 don
,
q q
− 1 − α4 < α3 < 1 − α42 .
2
D'où,
q q
t − t 1 − α4 < t(α3 + 1) < t + t 1 − α42 .
2
On en déduit que,
s 2 s 2
q
r1 + r2 r1 + r2 r1 + r2
t + t 1 − α42 ≤ t + − (tα4 )2 ≤ + − (tα4 )2 .
2 2 2
162
t(α3 + 1) > f (t) ≥ s− .
r1 + r2
En
on
lusion, D12 (q̃) < 0. On a démontré que pour tout t≤ ,
2
√
B(q + tv3 , t 2) ∩ Q12 = ∅, (F.2)
√
e qui implique que dQ12 (q + tv3 ) = t 2 et q ∈ PQ12 (q + tv3 ). Or,
omme
q = (0, 0, r1 + r2 , 0, q3 , . . . , q2N ),
le ve
teur e12 (q) est égal à (1, 0) et le ve
teur v3 n'est autre que le ve
teur −G12 (q), d'où
le résultat.
r1 + r2
Remarque F.1 Cette valeur limite de t = est asso
iée à la
onguration limite
2
où les 2
entres des parti
ules sont
onfondus q1 = q2 .
tel-00346035, version 1 - 10 Dec 2008
Dans la preuve pré
édente et grâ
e à la
ara
térisation des ensembles prox-réguliers (
f
proposition 2.23 p. 36), on a aussi montré la proposition 3.6 p. 45 :
r1 + r2
Proposition 3.6 L'ensemble Q12 est η-prox-régulier ave
η = √ .
2
Démonstration : √ r1 + r2
On a montré (voir (F.2)) que B(q + tv3 , t 2) ∩ Q12 = ∅ dès que t≤ . Ave
les
2
√ r1 + r2
notations de la proposition 2.23 p. 36, η = t 2 = √ .
2
163
tel-00346035, version 1 - 10 Dec 2008
Annexe G
Autre démonstration de l'inégalité
triangulaire inverse
tel-00346035, version 1 - 10 Dec 2008
165
Annexe G. Autre démonstration de l'inégalité triangulaire inverse
Dans
ette annexe, se trouve une démonstration de l'existen
e d'une inégalité triangulaire
inverse vériée par les ve
teurs Gij (q), aboutissant à une autre
onstante que
elle obtenue
à la proposition 3.14 p. 52.
où
Icontact = {(i, j), i < j, Dij (q) = 0} et les αij sont des réels positifs quel onques.
Nnv
tel-00346035, version 1 - 10 Dec 2008
4
2
γ=
.
1 − s 1
2N
1
1+
2nv
Justions tout de suite qu'une inégalité inverse pour deux ve
teurs peut être obtenue en
minorant leur produit s
alaire.
Démonstration :
Si cos θ = 1, νθ = 1 et |u1| + |u2| = |u1 + u2|. Le résultat est alors vrai. Si cos θ < 1, νθ > 1
166
et on
onsidère ν ≥ νθ . On a
Par
onséquent,
2 2 1 − ν 2 cos θ
|u1 | + |u2 | ≥ 2|u1||u2| ≥ 2 |u1||u2 |.
ν2 − 1
Pour établir l'inégalité triangulaire inverse (ave
un nombre quel
onque de ve
teurs),
on propose une méthode basée sur une estimation des angles entre les ve
teurs Gij (q)
omme on l'avait déjà pressenti au début de la sous-se
tion 3.2.2. La preuve sera faite par
ré
urren
e sur le nombre de ve
teurs intervenant dans la somme. On veut montrer qu'il
existe δ > 1 (qui sera déni plus loin), tel que pour tout I sous-ensemble de Icontact et
pour tout αij > 0,
X X
αij |Gij (q)| ≤ δ card(I) αij Gij (q) .
(i,j)∈I⊂Icontact (i,j)∈I⊂Icontact
Hypothèse de ré
urren
e :
Si le
ardinal de I ⊂ Icontact est égal à p, alors on a
X X
p
αij |Gij (q)| ≤ δ αij Gij (q) (Hp )
(i,j)∈I⊂Icontact (i,j)∈I⊂Icontact
167
Annexe G. Autre démonstration de l'inégalité triangulaire inverse
où les αij sont des réels stri
tement positifs. Soit (k, l) ∈ I , on dénit J = I \ {(k, l)}
ainsi que
X
w1 = αij Gij (q)
(i,j)∈J
et
w2 = αkl Gkl (q),
de telle sorte qu'on ait
w = w 1 + w2 .
On utilise alors le lemme suivant démontré plus loin.
2
|w1 | + |w2 | ≤ |w1 + w2 |,
1−κ
ave
1
κ= s 2N .
1
1+
2nv
Or,
omme δ > 1, on peut initialiser la ré
urren
e ave
e
oe
ient δ et par hypothèse
de ré
urren
e, on a
X
αij |Gij (q)| ≤ δ p |w1 |.
(i,j)∈J
Par onséquent,
X
p p 1
αkl |Gkl (q)| + αij |Gij (q)| ≤ αkl |Gkl (q)| + δ |w1 | = δ |w2 | + |w1 | .
δp
(i,j)∈J
X
αij |Gij (q)| ≤ δ p (|w2 | + |w1 |) ≤ δ p+1 |w|.
(i,j)∈Icontact
168
La propriété (Hp+1 ) est don
vraie,
e qui prouve l'hérédité de
ette propriété. Par
onsé-
quent, il existe δ > 1, tel que
X X
card(Icontact )
αij |Gij (q)| ≤ δ αij Gij (q) ,
(i,j)∈Icontact (i,j)∈Icontact
Nnv
pour tout αij ≥ 0. Comme le
ardinal de Icontact est inférieur à (on rappelle que nv
2
est le nombre maximal de voisins que peut avoir une personne), la proposition 3.14 est
vériée en prenant
Nnv
γ=δ 2
Ce résultat repose sur le lemme G.2 qui établit une inégalité triangulaire inverse entre
deux ve
teurs, sous réserve d'une minoration de leur produit s
alaire, qui est établie par
le lemme suivant.
Par onséquent, en utilisant les notations du lemme G.2, on a d'après le lemme G.4,
w1 · w 2
= cos θ ≥ −κ.
|w1 ||w2 |
Aussi,
1 + cos θ ≥ 1 − κ,
e qui implique
r r
2 2
≥ .
1−κ 1 + cos θ
Le lemme G.3 est don
une
onséquen
e immédiate du lemme G.2.
169
Annexe G. Autre démonstration de l'inégalité triangulaire inverse
où les
oe
ients intervenant dans
es deux é
ritures sont stri
tement positifs. Cependant,
il sut de prouver
ette inégalité pour
w2 = Gkl (q).
On pose (
αij si i<j
βij =
αji sinon,
on a alors X
w1 = (F1 , F2 , ..., FN ) où Fp = βip eip .
Ainsi, Fk est un ve
teur de R2 k ième
qui peut être interprété
omme la for
e exer
ée sur la
tel-00346035, version 1 - 10 Dec 2008
elk ekl
ql qk
−Fk
|Fl · elk |
pP ≤ 1.
|Fi |2
170
Finalement, on en déduit que
−Fl · elk −1
∆kl ≥ √ pP ≥√ .
2 |Fi |2 2
Dans
e
as, on peut prendre
1
κ= √ .
2
Cas 2 : −Fk · ekl < 0 et −Fl · elk < 0 (
f gure G.2)
ekl elk
−Fl
tel-00346035, version 1 - 10 Dec 2008
qk ql
1 1
Cas 2a : −Fk · ekl ≥ − |Fk | ou−Fl · elk ≥ − |Fl |
4 4
1
Supposons, par exemple (
f gure G.3), que −Fk · ekl ≥ − |Fk |. On a
4
−Fk
PSfrag repla
ements
ekl elk
−Fl
qk ql
qX
|Fk | ≤ |Fi |2 ,
171
Annexe G. Autre démonstration de l'inégalité triangulaire inverse
Par
onséquent,
1 −Fk · ekl
− ≤ pP
4 |Fi |2
et
omme
−F · e
pPl lk ≥ −1,
|Fi |2
1 1 5
∆kl ≥ √ − − 1 = − √ > −1.
2 4 4 2
Dans
e
as, on peut prendre
5
κ= √ .
4 2
1 1
Cas 2b : −Fk · ekl < − |Fk | et −Fl · elk < − |Fl | (
f gure G.4)
4 4
tel-00346035, version 1 - 10 Dec 2008
−Fk
PSfrag repla
ements
ekl elk
−Fl
qk ql
X
|Fi |2 ≥ |Fk |2 + |Fl |2 + |Fk̃2 | + |Fl̃ |2 ≥ (1 + ǫ2 ) |Fk |2 + |Fl |2 .
172
Aussi,
1 1 1
pP ≤√ p
|Fi | 2 1+ǫ2 |Fk | + |Fl |2
2
et !
1 |Fk | + |Fl | 1
|∆kl | ≤ √ √ p ≤√ .
1 + ǫ2 2 |Fk |2 + |Fl |2 1 + ǫ2
Finalement, on
on
lut que
1
∆kl ≥ − √ > −1.
1 + ǫ2
Dans
e
as, on peut don
prendre
1
κ= √ .
1 + ǫ2
tel-00346035, version 1 - 10 Dec 2008
1 5 1 1
κ = max √ , √ ,√ =√ ,
2 4 2 1 + ǫ2 1 + ǫ2
à
ondition de prouver le sous-lemme G.5.
Remarque G.6 On peut tout de suite
onstater que, pour une
onguration q xée et
des
oe
ient αij xés, l'existen
e d'un réel ǫ, vériant
es deux inégalités est triviale. En
eet, par l'absurde, on obtient que sinon
173
Annexe G. Autre démonstration de l'inégalité triangulaire inverse
1
βkk1 ekk1 · ekl < − Fk · ekl ,
nv
1
et
omme −Fk · ekl < − |Fk |, on obtient
4
1
βkk1 ekk1 · ekl < − |Fk |.
4nv
En interprétant, l'individu k1 est la personne qui exer
e la plus forte pression sur k et la
personne k se trouve entre les individus l et k1
ar ekk1 · ekl < 0 (la personne k1 se trouve
à gau
he de k sur la gure G.5).
1
Si |Fk1 | ≥ |Fk |, alors on pose
8nv
tel-00346035, version 1 - 10 Dec 2008
k̃ = k1 .
1
Sinon |Fk1 | < |Fk |, et on pro
ède de manière analogue ave
Fk1 . On sait que
8nv
Vk1
X
−Fk1 = βk1 k ek1 k + βk1 j1,i ek1 j1,i ,
i=1
Vk1
X
−Fk1 · ekl = βk1 k ek1 k · ekl + βk1 j1,i ek1 j1,i · ekl .
i=1
1 1
Comme −βk1 k ek1 k · ekl < − |Fk | et −Fk1 · ekl ≤ |Fk1 | < |Fk |, on en déduit que
4nv 8nv
Vk1
X 1
βk1 j1,i ek1 j1,i · ekl = −Fk1 · ekl − βk1 k ek1 k · ekl < − |Fk |.
i=1
8nv
1
βk1 k2 ek1 k2 · ekl < − |Fk |
8n2v
(Là en
ore sur la gure G.5, la personne k2 se trouve à gau
he de l'individu k1 ).
2
1 1
Si |Fk2 | ≥ |Fk |, alors on pose
4 2nv
k̃ = k2 .
174
PSfrag repla
ements qk1
qki
ekl elk
−Fl
qk ql
qk2
Sinon, on
ontinue. On
onstruit alors une suite ki (
f gure G.5) telle que
k0 = k
i+1
tel-00346035, version 1 - 10 Dec 2008
1 1
|Fki+1 | < |Fk |
4 2nv
i
1 1 1
βki ki+1 eki ki+1 · ekl < − |Fk |.
4 2nv nv
On a alors
ki+1 ∈
/ {k0 , k1 , ..ki }.
En eet,
omme on a par
onstru
tion (point 3 du système) :
ek0 k1 · ekl < 0
ek1 k2 · ekl < 0
.
.
.
eki ki+1 · ekl < 0
il sut de montrer que
∀j ∈ J0, iK, eki+1 kj · ekl > 0.
On a pour j ∈ J0, iK,
1
eki+1 kj ·ekl = |qki+1 − qki |eki+1 ki + |qki − qki−1 |eki ki−1 + ... + |qkj+1 − qkj |ekj+1 kj ·ekl .
|qki+1 − qkj |
Don
1
eki+1 kj · ekl = |qki+1 − qki |eki+1 ki · ekl + ... + |qkj+1 − qkj |ekj+1 kj · ekl > 0.
|qki+1 − qkj |
On
on
lut alors que
ki+1 ∈
/ {k0 , k1 , ..ki−1 },
175
Annexe G. Autre démonstration de l'inégalité triangulaire inverse
ki+1 ∈
/ {k0 , k1 , ..ki }.
On pro
ède de manière analogue ave
Fl , en
onstruisant une suite li vériant le même
genre de propriétés (les personnes li se trouveront à droite de l'individu l toujours dans
le
adre de la gure G.5). Il reste à montrer que 6 ˜l.
k̃ = Pour
ela, on a juste besoin de
vérier que
es deux suites sont disjointes,
'est-à- dire que,
Comme pré
édemment, le ve
teur eki l pour i ∈ {0..m}, s'é
rit
omme
ombinaison linéaire
à
oe
ients positifs des ve
teurs eki ki−1 , .., ek1 k0 et ek0 l . Grâ
e à (G.2) et
omme ek0 l ·ekl =
|ekl |2 = 1 > 0, on
on
lut alors que
Ensuite, le ve
teur eki lj i ∈ {0..m} et j ∈ {0..p}, s'é
rit
omme
ombinaison linéaire
pour
à
oe
ients positifs des ve
teurs eki l0 , el0 l1 , .., et elj−1 lj . Grâ
e à (G.3) et (G.4), on obtient
176
Le sous-lemme G.5 est vérié pour
N
1
ǫ=
2nv
Remarque G.8 Pour se xer les idées, on peut
al
uler un équivalent de η quand N tend
vers l'inni (nv
onstant). On obtient
2
Nnv N nv
ri + rj 1 4 1 2
η ∼ min √ .
N →∞ (i,j) 2 4 2n v
Cette
onstante de prox-régularité est inférieure à
elle annon
ée par la proposition 3.12
p. 51.
177
tel-00346035, version 1 - 10 Dec 2008
tel-00346035, version 1 - 10 Dec 2008
179
Annexe H
Formulation point-selle
Annexe H. Formulation point-selle
Cette annexe a pour obje
tif de rappeler les résultats
lassiques qu'on peut retrouver
dans [Mau04℄, jusqu'à la proposition H.9. Pour la proposition H.11, on renvoit le le
teur
vers [All05℄ ou [Cia90℄. On
onsidère V un espa
e de Hilbert muni de son produit s
a-
laire ( , ) et de sa norme | |, M un espa
e de Bana
h, B ∈ L (V, M) et z ∈ M . On note
′ ′
le
ro
het de dualité entre M et M par hφ, mi ave
φ ∈ M et m ∈ M et on note k k la
′
norme naturelle sur M . On dénit ensuite l'ensemble des
ontraintes qui sera l'ensemble
onvexe fermé suivant,
K = {u ∈ V, hµ, Bu − zi ≤ 0, ∀µ ∈ C},
où C ⊂ M′ est un
ne
onvexe fermé non vide de sommet 0. Soit f ∈V, on
onsidère la
fon
tionnelle
1
J (v) = |v|2 − (f, v)
2
ainsi que le problème de minimisation sous
ontrainte suivant :
(
u ∈ K,
(Q)
tel-00346035, version 1 - 10 Dec 2008
L: V ×C → R
(v, µ) 7→ L (v, µ) = J (v) + hµ, Bv − zi.
(
′
(u, λ) ∈ V × C,
(Q )
∀ (v, µ) ∈ V × C, L (u, µ) ≤ L (u, λ) ≤ L (v, λ) .
Proposition H.2 Le problème (Q) possède une unique solution que l'on notera u.
Démonstration :
Il sut de remarquer que la fon
tionnelle J est stri
tement
onvexe et
oer
ive, puis que
K est un ensemble
onvexe fermé de V.
Remarque H.4 Par dénition du
ne polaire (dénition C.1 p. 150), on sait que u ∈ K
si et seulement si Bu − z ∈ C ◦ .
180
Proposition H.5 Si (u, λ) ∈ V × C est solution du problème de point-selle (Q′ ), alors u
est solution du problème de minimisation (Q).
Démonstration :
On raisonne par l'absurde en supposant que u∈
/ K,
'est-à-dire en supposant qu'il existe
µ0 ∈ C , tel que hµ0 , Bu − zi > 0. Alors
On obtient don une ontradi tion ave le fait que L (u, µ) soit majoré. Par onséquent,
∀µ ∈ C, hµ, Bu − zi ≤ 0.
Autrement dit, u ∈ K . Ensuite, on sait que pour tout µ ∈ C, hµ, Bu−zi ≤ hλ, Bu−zi ≤ 0.
En prenant µ = 0, on voit que né
essairement
hλ, Bu − zi = 0.
tel-00346035, version 1 - 10 Dec 2008
En
onséquen
e,
∀v ∈ V, J (u) ≤ J (v) + hλ, Bv − zi.
Comme pour tout v ∈ K , hλ, Bv − zi ≤ 0, on obtient,
∀v ∈ K, J (u) ≤ J (v) .
Autrement dit,
J (u) = inf J (v) .
v∈K
Démonstration :
Si (u, λ) est solution de (Q′ ), alors on sait déjà que Bu − z ∈ C ◦
ar u∈K ainsi que
181
Annexe H. Formulation point-selle
e qui implique
∀v ∈ V , (u, v) − (f, v) + (B ⋆ λ, v) = 0.
D'où,
u + B ⋆ λ = f.
Ainsi, (u, λ) est solution de (Q′′ ).
Ré
iproquement, si (u, λ) est solution de (Q′′ ), alors Bu − z ∈ C ◦
e qui revient à dire
que u ∈ K. Aussi,
omme hλ, Bu − zi = 0, on a
Par
onséquent,
∀µ ∈ C, L (u, µ) ≤ L (u, λ) .
tel-00346035, version 1 - 10 Dec 2008
⋆
Ensuite, l'équation u + B λ = f implique, d'après le théorème de Lax-Milgram, que u
1 2
minimise J (v) = |v| − (f, v) + hλ, Bvi sur V don
2
∀v ∈ V, J (u) ≤ J (v) .
∀v ∈ V, L (u, λ) ≤ L (v, λ) .
Démonstration :
Soit u la solution de (Q), montrons dans un premier temps que
◦
∀v ∈ B ⋆ (C) , ∀t ≥ 0 , u + tv ∈ K.
◦
Soit v ∈ B ⋆ (C) , on a par dénition du
ne polaire (dénition C.1 p. 149),
∀µ ∈ C, (B ⋆ µ, v) ≤ 0,
e qui équivaut à
∀µ ∈ C, hµ, Bvi ≤ 0.
182
Ainsi,
hµ, B(u + tv) − zi = hµ, Bu − zi + thµ, Bvi ≤ 0, ∀t ≥ 0.
Don
pour tout t ≥ 0, u + tv ∈ K . Dans un se
ond temps, montrons que
◦◦
f − u ∈ B ⋆ (C) .
◦
Soient v ∈ B ⋆ (C) et t ≥ 0,
omme u est solution de (Q) et u + tv ∈ K d'après
e qui
pré
ède, on a
J(u) ≤ J(u + tv).
Par dénition de J, on a don
1 2 2
t |v| + t (u, v) − t (f, v) ≥ 0,
2
e qui implique
1 2
t t|v| − (f − u, v) ≥ 0.
tel-00346035, version 1 - 10 Dec 2008
2
Par
onséquent,
1
t|v|2 − (f − u, v) ≥ 0.
2
Ce
i étant vrai pour tout t ≥ 0, on en déduit que
(f − u, v) ≤ 0.
◦
Cette inégalité étant vériée pour tout v ∈ B ⋆ (C) , on a démontré que
◦◦
f −u∈ B ⋆ (C) .
Comme B ⋆ (C) est un
ne
onvexe fermé non vide de sommet 0, on a d'après la proposition
C.4 p. 151,
◦◦
B ⋆ (C) = B ⋆ (C).
Ainsi, f − u ∈ B ⋆ (C).
Proposition H.9 Soit u la solution du problème de minimisation (Q), si B est surje
tif
de V dans M , alors il existe un unique λ ∈ C tel que (u, λ) soit solution du problème de
point-selle (Q′ ).
Démonstration :
Montrons que B ⋆ (C) est un fermé. Comme B est surje
tif de V dans M, on sait (
f.
théorème II.19 p.29 dans [Bre73℄) que
183
Annexe H. Formulation point-selle
où µn ∈ C . L'inégalité pré
édente implique que la suite (µn ) est de Cau
hy dans M ′.
′
Ainsi, il existe λ ∈ M tel que
µn −−−→ λ.
n→∞
′
Or Cest un fermé de M don
λ ∈ C. Par
ontinuité de B⋆, on a v = B ⋆ λ ∈ B ⋆ (C). En
⋆
on
lusion, B (C) est un fermé.
Soit u la solution du problème (Q), d'après
e qui pré
ède et la proposition H.8, on a
f − u ∈ B ⋆ (C). Par
onséquent, il existe λ ∈ C tel que f − u = B ⋆ λ. Comme B est
⋆
surje
tif, B est inje
tif et on
on
lut alors que
∃ ! λ ∈ C, u + B ⋆ λ = f.
u − a = PK−a (f − a)
(
e
i est évident lorsqu'on pense à la
ara
térisation de la proje
tion sur un
onvexe fermé
f. théorème A.1 p. 142). Enn,
omme K−a⊂V est un
ne
onvexe fermé non vide
de sommet 0, on a don
d'après la proposition C.3 p. 150,
(u − a, f − u) = 0.
Ce
i implique
(u − a, B ⋆ λ) = 0
et par
onséquent
hλ, B (u − a)i = hλ, Bu − zi = 0.
Ainsi, il existe un unique λ ∈ C tel que (u, λ) soit solution du problème (Q′′ ),
e qui
implique d'après la proposition H.7 qu'il existe un unique λ ∈ C tel que (u, λ) soit
′
solution du problème (Q ).
184
Proposition H.11 (Cas d'un nombre ni de
ontraintes)
On suppose que C est niment généré, autrement dit,
p
X
C= R+ µi , avec µi ∈ M ′ .
i=1
Démonstration :
Soit u la solution de (Q), on dénit l'ensemble, que l'on suppose dans un premier temps
non vide,
Iu = {i ∈ {1, .., p}, hµi, Bu − zi = 0},
et le
ne
onvexe fermé in
lus dans M ′,
X
Cu = {µ ∈ C , hµ, Bu − zi = 0} = R+ µ i .
i∈Iu
tel-00346035, version 1 - 10 Dec 2008
Par
onséquent,
X
B ⋆ (Cu ) = R+ B ⋆ (µi ).
i∈Iu
On utilise une proposition analogue à la proposition H.8, qui sera démontrée ultérieure-
ment, à savoir :
X
f − u = B ⋆ (λ) = λi B ⋆ (µi ).
i∈Iu
185
Annexe H. Formulation point-selle
◦
Soit v ∈ B ⋆ (Cu ) , on a
∀µ ∈ Cu , (B ⋆ µ, v) ≤ 0,
e qui équivaut à
∀µ ∈ Cu , hµ, Bvi ≤ 0.
En
onséquen
e, si µ ∈ Cu , on a
−hµj , Bu − zi
tv = min > 0.
j ∈I(u)
/ |hµj , Bvi|
D'après
e qui pré
ède, la première somme est négative et par dénition de tv , la deuxième
aussi. Par
onséquent, on en déduit que
◦◦
⋆
f − u ∈ B (Cu ) .
◦
Soient v ∈ B ⋆ (Cu ) et t ∈ [0, tv [,
omme u est solution de (Q), on a
1 2 2
t |v| + t (u, v) − t (f, v) ≥ 0,
2
e qui implique
1
t|v|2 − (f − u, v) ≥ 0.
2
Ce
i étant vrai pour tout t ∈ [0, tv [, on en déduit que
(f − u, v) ≤ 0,
186
autrement dit que
◦◦
f − u ∈ B ⋆ (Cu ) .
Comme B ⋆ (Cu ) est un
ne
onvexe fermé non vide de sommet 0, on a d'après la propo-
sition C.4 p. 151,
◦◦
⋆
B (Cu ) = B ⋆ (Cu ).
Ainsi, f − u ∈ B ⋆ (Cu ).
tel-00346035, version 1 - 10 Dec 2008
187
tel-00346035, version 1 - 10 Dec 2008
tel-00346035, version 1 - 10 Dec 2008
189
Annexe I
Algorithme d'Uzawa
Annexe I. Algorithme d'Uzawa
∀k ≥ 0, λk+1 = PC λk + ρ B f − B ⋆ λk − z . (I.1)
La proposition suivante montre que si la suite dénie par (I.1)
onverge alors il y a
existen
e d'un point-selle qui peut être exprimé en fon
tion de la limite de la suite.
Proposition I.1 On suppose que z = Ba. Si la suite λk dénie par (I.1)
onverge vers
λ ∈ M , alors (f − B ⋆ λ, λ) est solution du problème de point-selle (Q′ ) déni p. 179.
Démonstration :
tel-00346035, version 1 - 10 Dec 2008
Comme PC est une appli ation ontinue (1-lips hitz), on a à la limite l'équation,
λ = PC (λ + ρB (f − B ⋆ λ − a)) ar z = Ba.
hµ − λ, ρB (f − B ⋆ λ − a)i ≤ 0,
hµ − λ, B (f − B ⋆ λ − a)i ≤ 0.
Ce
i équivaut aussi à
(B ⋆ (µ − λ) , f − B ⋆ λ − a) ≤ 0 , ∀µ ∈ C,
et par onséquent
B⋆λ = P B ⋆ (C) (f − a) .
Comme B ⋆ (C) est un
ne
onvexe fermé non vide de sommet 0, d'après la proposition C.3
p. 150, on a
190
On en déduit que
f − a − B ⋆ λ = PK−a (f − a),
e qui équivaut à
f − B ⋆ λ = PK f.
(Ce
i est évident lorsqu'on pense à la
ara
térisation de la proje
tion sur un
onvexe fermé
f. théorème A.1 p. 142). On pose maintenant u = f − B ⋆ λ, u est bien un élément de
K . Il reste à vérier la relation de
omplémentarité hλ, Bu − zi = 0 pour montrer que
(u, λ) est solution du problème (Q′′ ) déni dans l'annexe H page 181. Comme u − a est la
proje
tion de f − a sur K − a et d'après la proposition C.3 p. 150, on a (u − a, f − u) = 0.
D'où,
(u − a, B ⋆ λ) = 0 = hλ, Bu − zi.
Ainsi, (u, λ) est solution du problème (Q′′ ) et don
(
f. proposition H.7 p. 181) du problème
(Q′ ).
Remarque I.3 L'hypothèse importante est que z ∈ ImB , il n'est pas né
essaire de sup-
poser que B ⋆ (C) est fermé
omme dans la proposition H.10 p. 184.
tel-00346035, version 1 - 10 Dec 2008
K = {v ∈ V , hµ, Bv − zi ≤ 0 , ∀µ ∈ C}.
En é
rivant que z = Ba, on obtient que
K = {v ∈ V , (B ⋆ µ, v − a) ≤ 0 , ∀µ ∈ C}.
Par
onséquent,
K − a = {w ∈ V , (B ⋆ µ, w) ≤ 0 , ∀µ ∈ C}.
Autrement dit,
◦
K − a = B ⋆ (C) ◦ = B ⋆ (C) .
191
Annexe I. Algorithme d'Uzawa
Démonstration :
Si (u, λ) est solution de (Q′ ) alors (u, λ) est aussi solution de (Q′′ ), d'après la proposi-
tion H.7 p. 181. Par
onséquent, hλ, Bu − zi = 0. Montrons que l'élément λ vérie
hµ − λ, Bu − zi ≤ 0 , ∀µ ∈ C.
λk+1 = PC λk + ρ Buk − z . (I.3)
|λk+1 − λ|2 = |PC λk + ρ Buk − z − PC (λ + ρ (Bu − z)) |2 (I.4)
tel-00346035, version 1 - 10 Dec 2008
≤ |λk − λ + ρB uk − u |2
≤ |λk − λ|2 + 2ρ B ⋆ λk − λ , uk − u + ρ2 |B uk − u |2
≤ |λk − λ|2 − 2ρ|uk − u|2 + ρ2 |B uk − u |2
≤ |λk − λ|2 − 2ρ|uk − u|2 + ρ2 kBk2 |uk − u|2
≤ |λk − λ|2 − ρ 2 − ρkBk2 |uk − u|2. (I.5)
2
Si on suppose ρ ∈ 0, , on a don
kBk2
La suite |λk − λ| est alors dé
roissante, positive. Elle
onverge don
vers un réel positif,
et on a d'après (I.5),
2 k ⋆ k
En
on
lusion, pour tout ρ ∈ 0, , la suite u = f − B λ
onverge vers u, solution
kBk2
de (Q).
Dans le
as qui nous intéresse (nombre ni de
ontraintes), on peut même montrer que la
suite des multipli
ateurs de Lagrange
onstruite par l'algorithme d'Uzawa
onverge.
(I.1) onverge vers un λ ∈ C tel que (u, λ) soit solution du problème (Q′ ) (déni p. 179).
192
Démonstration :
La preuve repose essentiellement sur le lemme d'Opial qui sera démontré plus loin.
Pour montrer que (u, µ) est une solution de (Q′ ), il sut de prouver la relation de
om-
plémentarité,
hµ, Bu − zi = 0.
Par dénition de λk+1 , on a pour tout µ̃ ∈ C,
Comme C
est niment généré, il est in
lus dans un espa
e hilbertien de dimension nie.
k
Par
onséquent, la suite des (λ )
onverge fortement et on peut passer à la limite dans
l'équation pré
édente . En prenant enn µ̃ = 0, on obtient
hµ, Bu − zi ≥ 0.
193
Annexe I. Algorithme d'Uzawa
On é
rit alors
|λk − λ1 |2 − |λk − λ2 |2 = hλ2 − λ1 , 2λk − λ1 − λ2 i.
On passe à la limite dans l'identité pré
édente pour la sous-suite (λmk ) puis pour (λnk ).
Il vient
|ℓ1 |2 − |ℓ2 |2 = −|λ2 − λ1 |2 et |ℓ1 |2 − |ℓ2 |2 = |λ2 − λ1 |2 .
On a don
né
essairement |λ2 − λ1 | = 0, d'où le résultat.
tel-00346035, version 1 - 10 Dec 2008
194
Bibliographie
[All05℄ G. Allaire. Analyse numérique et optimisation : Une introdu
tion à la
modélisation mathématique et à la simulation numérique. Les Editions de
l'E
ole polyte
hnique, 2005.
[BA01℄ V. Blue and J.L. Adler. Cellular automata mi
rosimulation for modeling bi-
dire
tional pedestrian walkways. Transportation Resear
h B, 35 :293312,
2001.
[Bat97℄ M. Batty. Predi
ting where we walk. Nature, 388 :1920, 1997.
[Ben00℄ H. Benabdellah. Existen
e of solutions to the non
onvex sweeping pro
ess.
J. Dierential Equations, 164 :286295, 2000.
[BKSZ01℄ C. Burstedde, K. Klau
k, A. S
hads
hneider, and J. Zittartz. Simulation of
pedestrian dynami
s using a two-dimensional
ellular automaton. Physi
a
A, 295 :507525, 2001.
[Bol98℄ K. Bolay. Ni
htlineare phänomene in einem uid-dynamis
hen verkehrs-
model. Master's thesis, Department of theori
al Physi
s II, University of
Stuttgart, 1998.
[BS90℄ P.H.L. Bovy and E. Stern. Route
hoi
e waynding in transport networks.
Kluwer a
ademi
publishers, Dordre
ht, 1990.
[BT86a℄ A. Borgers and H. Timmermans. City
entre entry points, store lo
ation
patterns and pedestrian route
hoi
e behaviour : A mi
rolevel simulation
model. So
io-E
onomi
Planning S
ien
es, 20 :2531, 1986.
[BT86b℄ A. Borgers and H. Timmermans. A model of pedestrian route
hoi
e and
demand for retail fa
ilities within inner-
ityshopping areas. Geography
al
Analysis, 18 :115128, 1986.
[BT01℄ M. Bounkhel and L. Thibault. Non
onvex sweeping pro
ess and prox-
regularity in Hilbert spa
e. J. Nonlinear Convex Anal., 6 :359374, 2001.
195
Bibliographie
[CG99℄ G. Colombo and V.V. Gon
harov. The sweeping pro
esses without
onvexity. Set-Valued Anal., 7 :357374, 1999.
[Cia90℄ P.G. Ciarlet. Introdu
tion à l'analyse numérique matri
ielle et à l'optimi-
sation. Masson, Paris, 1990.
[CLSW98℄ F.H. Clarke, Y.S. Ledyaev, R.J. Stern, and P.R. Wolenski. Nonsmooth
Analysis and Control Theory. Springer-Verlag, New York, In
., 1998.
[CM95℄ C. Castaing and M.D.P. Monteiro Marques. BVperiodi
solutions of an
evolution problem asso
iated with
ontinuous moving
onvex sets. Set-
Valued Anal., 3(4) :381399, 1995.
[CM03℄ G. Colombo and M.D.P. Monteiro Marques. Sweeping by a
ontinuous
prox-regular set. J. Dierential Equations, 187(1) :4662, 2003.
[CSW95℄ F.H. Clarke, R.J. Stern, and P.R. Wolenski. Proximal smoothness and the
tel-00346035, version 1 - 10 Dec 2008
2
lower-c property. J. Convex Anal., 2 :117144, 1995.
[ET06℄ J.F. Edmond and L. Thibault. BVsolutions of non
onvex sweeping pro-
ess dierential in
lusion with perturbation. J. Dierential Equations,
226(1) :135179, 2006.
196
[GM85℄ P.G. Gipps and B. Marksjo. A mi
ro-simulation model for pedestrian ows.
Mathemati
s and Computers in Simulation, 27 :95105, 1985.
[Har81℄ A. Haraux. Nonlinear evolution equations - global behaviour of solutions.
Springer Verlag, 1981.
[HB00℄ S.P. Hoogendoorn and P.H.L. Bovy. Gas-kineti
modeling and simulation
of pedestrian ows. Transportation Resear
h Re
ord, 1710 :2836, 2000.
[HB04a℄ S.P. Hoogendoorn and P.H.L. Bovy. Dynami
user-optimal assignment in
ontinuous time and spa
e. Transportation Resear
h B, 38 :571592, 2004.
[HB04b℄ S.P. Hoogendoorn and P.H.L. Bovy. Pedestrian route-
hoi
e and a
tivity
s
heduling theory and models. Transportation Resear
h B, 38 :169190,
2004.
[Hen74℄ L.F. Henderson. On the uid me
hani
s of human
rowd motion. Trans-
portation Resear
h, 8 :509515, 1974.
[HFV00a℄ D. Helbing, I.J. Farkas, and T. Vi
sek. Freezing by heating in a driven
mesos
opi
system. Physi
al Review Letters, 84 :12401243, 2000.
[HFV00b℄ D. Helbing, I.J. Farkas, and T. Vi
sek. Simulating dynami
al features of
es
ape pani
. Nature, 407 :487, 2000.
197
Bibliographie
[HMK03℄ H.Klüpfel and T. Meyer-König. Chara
teristi
s of the pedgo software for
rowd movement and egress simulation. In E. Galea, editor, Pedestrian and
Eva
uation Dynami
s 2003, pages 331340, University of Greenwi
h, 2003.
CMS Press, London.
[KKWS01℄ A. Keÿel, H. Klüpfel, J. Wahle, and M. S
hre
kenberg. Mi
ros
opi
simu-
lation of pedestrian
rowd motion. In M. S
hre
kenberg and S. D. Sharma,
editors, Pedestrian and Eva
uation Dynami
s, pages 193202. Springer Ber-
lin, 2001.
[KS02℄ A. Kir
hner and A. S
hads
hneider. Simulation of eva
uation pro
esses
using a bioni
s-inspired
ellular automaton model for pedestrians dynami
s.
Physi
a A, 312 :260276, 2002.
[Lef07℄ A. Lefebvre. Modélisation numérique d'é
oulements uide/parti
ules, Prise
en
ompte des for
es de lubri
ation. PhD thesis, Université Paris-Sud XI,
Fa
ulté des s
ien
es d'Orsay, 2007.
198
[Løv94℄ G.G. Løvås. Modelling and simulation of pedestrian tra
ow. Transpor-
tation Resear
h B, 28 :429443, 1994.
[Mau04℄ B. Maury. Analyse Fon
tionnelle, exer
i
es et problèmes
orrigés. Ellipses,
2004.
[Mor62℄ J.J. Moreau. Dé
omposition orthogonale d'un espa
e hilbertien selon deux
nes mutuellement polaires. C. R. A
ad. S
i, Ser. I, 255 :238240, 1962.
tel-00346035, version 1 - 10 Dec 2008
[Mor77℄ J.J. Moreau. Evolution problem asso
iated with a moving
onvex set in a
Hilbert spa
e. J. Dierential Equations, 26(3) :347374, 1977.
[MV07℄ B. Maury and J. Venel. Un modèle de mouvements de foule. In ESAIM :
Pro
., volume 18, pages 143152, 2007.
[Nag98℄ K. Nagel. From parti
le hopping models to tra
ow theory. Transporta-
tion Resear
h Re
ord, 1644 :19, 1998.
[NW69℄ P.D. Navin and R.J. Wheeler. Pedestrian ow
hara
teristi
s. Tra
En-
gineering, 39 :3136, 1969.
[PRL00℄ R.A. Poliquin, R.T. Ro
kafellar, and L.Thibault. Lo
al dierentiability of
distan
e fun
tions. Trans. Amer. Math. So
., 352 :52315249, 2000.
[S
h01℄ A. S
hads
hneider. Cellular automaton approa
h to pedestrian dynami
s-
theory. In M. S
hre
kenberg and S. D. Sharma, editors, Pedestrian and
Eva
uation Dynami
s, pages 7585. Springer Berlin, 2001.
[SKN03℄ A. S
hads
hneider, A. Kir
hner, and K. Nishinari. From ant trails to pe-
destrian dynami
s. Applied Bioni
s and Biome
hani
s, 1 :1119, 2003.
[Sti93℄ G.K. Still. New
omputer system
an predi
t human behavior response to
building res. Fire, 84 :4041, 1993.
[Sti00℄ G.K. Still. Crowd Dynami
s. PhD thesis, University of Warwi
k,
http ://www.
rowddynami
s.
om/Thesis/Contents.htm, 2000.
[Thi03℄ L. Thibault. Sweeping pro
ess with regular and nonregular sets. J. Die-
rential Equations, 193(1) :126, 2003.
[TN01℄ Y. Tajima and T. Nagatani. S
aling behavior of
rowd ow outside a hall.
Physi
a A, 292 :545554, 2001.
[Ven09℄ J. Venel. Integrating strategies in numeri
al modelling of
rowd motion. In
Pedestrian and Eva
uation Dynami
s '08. Springer, 2009. To appear.
199
Bibliographie
[YS89℄ S.J. Yuhaski and J.M. Ma
gregor Smith. Modelling
ir
ulation systems
in buildings using state dependent queueing models. Queueing Systems,
4 :319338, 1989.
tel-00346035, version 1 - 10 Dec 2008
200
tel-00346035, version 1 - 10 Dec 2008
N
o d'impression 2870
4ème trimestre 2008
tel-00346035, version 1 - 10 Dec 2008
Résumé
Modélisation mathématique et numérique de mouvements de foule
Nous nous intéressons à la modélisation des mouvements de foule
ausés par des situa-
tions d'éva
uation d'urgen
e. L'obje
tif de
ette thèse est de proposer un modèle mathé-
matique et une méthode numérique de gestion des
onta
ts, an de traiter les intera
tions
lo
ales entre les personnes pour nalement mieux rendre
ompte de la dynamique globale
du tra
piétonnier.
Nous proposons un modèle mi
ros
opique de mouvements de foule qui repose sur
deux prin
ipes. D'une part,
haque personne a une vitesse souhaitée,
elle qu'elle aurait
en l'absen
e des autres. D'autre part, la vitesse réelle des individus prend en
ompte
une
ertaine
ontrainte d'en
ombrement maximal. Plus pré
isément, la vitesse réelle est
la proje
tion de la vitesse souhaitée sur un ensemble dit de vitesses admissibles (qui
respe
tent une
ontrainte de non-
hevau
hement des disques représentant les individus).
Nous proposons d'étudier
e modèle en trois parties.
La première partie est
onsa
rée à son étude théorique. Après reformulation, le pro-
blème prend la forme d'une in
lusion diérentielle du premier ordre. Nous démontrons
tel-00346035, version 1 - 10 Dec 2008
alors son
ara
tère bien posé : tout d'abord dans un
as parti
ulier (où les individus se
dépla
ent dans un
ouloir) grâ
e à la théorie des opérateurs maximaux monotones, puis
en toute généralité, en utilisant des résultats sur les pro
essus de rae par un ensemble
uniformément prox-régulier.
La se
onde partie est dédiée à la résolution numérique du problème pré
édent. Nous
proposons un s
héma numérique en se basant sur le se
ond prin
ipe du modèle, à savoir
en
al
ulant une vitesse réelle dis
rète qui soit la proje
tion de la vitesse souhaitée sur un
ensemble de vitesses admissibles au premier ordre. En reformulant
ette proje
tion sous
la forme d'un problème point-selle, nous démontrons sa
onvergen
e par une méthode de
ompa
ité, en prouvant le
ara
tère uniformément borné des multipli
ateurs de Lagrange.
La troisième partie est
onsa
rée à la programmation et à la présentation des résultats
numériques. Nous proposons d'utiliser l'algorithme d'Uzawa an de
al
uler la vitesse
réelle dis
rète
omme proje
tion de la vitesse souhaitée. Ensuite, nous nous intéressons
au premier point du modèle en
hoisissant une vitesse souhaitée parti
ulière (
elle dirigée
par le plus
ourt
hemin évitant les obsta
les). Pour
ela, nous présentons une program-
mation orientée objet in
luant une méthode de type Fast Mar
hing et ayant pour but de
simuler l'éva
uation d'une stru
ture de plusieurs étages présentant une géométrie quel-
onque. Nous nissons ave
d'autres
hoix de vitesse souhaitée (par exemple, en ajoutant
des stratégies individuelles) et présentons les résultats numériques asso
iés. Ces simula-
tions numériques permettent de retrouver les phénomènes observés lors de dépla
ements
piétonniers mais aussi de pré
iser le rle des multipli
ateurs de Lagrange. Apparaissant
omme un moyen de quantier le non-respe
t des
ontraintes par la vitesse souhaitée,
es
derniers peuvent être interprétés
omme des termes de pression subie par les individus.
Mots
lés : mouvements de foule,
onta
ts, analyse
onvexe, in
lusion diérentielle,
pro
essus de rae, ensemble prox-régulier, minimisation sous
ontrainte, algorithme de
rattrapage, programmation orientée objet.