Théorème de Carathéodory (géométrie)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le théorème de Carathéodory est un théorème de géométrie relatif aux enveloppes convexes dans le contexte des espaces affines de dimension finie.

Énoncé[modifier | modifier le code]

Le théorème, établi par le mathématicien grec Constantin Carathéodory[1] affirme que :

Théorème — Dans un espace affine de dimension n, l'enveloppe convexe d'un sous-ensemble A est l'ensemble des barycentres à coefficients positifs ou nuls de familles de n+1 points de A.

Preuves[modifier | modifier le code]

La preuve usuelle[modifier | modifier le code]

Notons \mathrm{Conv}(A) l'enveloppe convexe de A, et \Gamma l'ensemble des barycentres à coefficients positifs ou nuls d'au plus n+1 points de A. On veut montrer l'égalité de ces deux ensembles.

L'inclusion \Gamma \subset \mathrm{Conv}(A) est évidente. La démarche de la preuve est de montrer que pour tout p\ge n+1, si un élément x de l'enveloppe convexe s'écrit comme combinaison convexe de p+1 points (i.e. comme barycentre à coefficients positifs ou nuls de ces points), alors c'est une combinaison convexe de p points bien choisis parmi ces p+1 ; on réitère alors le procédé jusqu'à obtenir x \in \Gamma.

Soit x \in \mathrm{Conv}(A). Ainsi x s'écrit x = \sum_{i = 1}^{p+1} \lambda_i a_i, où p\ge 1 est un entier, les \lambda_i sont des réels positifs ou nuls de somme 1, et les a_i sont des points de A.

Si p \leq n, alors x \in \Gamma. Si p \geq n + 1, alors (a_1, \dots, a_{p+1}) est affinement lié, c'est-à-dire que l'un des points, disons par exemple a_1\,, est barycentre des autres : il existe des réels t_2,\cdots,t_{p+1} de somme 1 tels que a_1=\sum_{i=2}^{p+1}t_ia_i.

En posant \mu_1=1\, et pour i>1\,, \mu_i=-t_i\,, on obtient : \mu_1>0\,, \sum_{i=1}^{p+1} \mu_i = 0 et \sum_{i=1}^{p+1} \mu_i a_i = \overrightarrow 0.

Choisissons k tel que : \frac{\lambda_k}{\mu_k} = \inf \{ \frac{\lambda_i}{\mu_i}, 1 \leq i \leq p + 1, \mu_i > 0 \} et remplaçons, dans l'expression de x, le point a_k par \sum_{i\neq k}\frac{-\mu_i}{\mu_k}a_i.

Par "associativité du barycentre" on obtient x = \sum_{i\ne k} \delta_i a_i, où les \delta_i\,, définis par \delta_i = \lambda_i - \lambda_k \frac{\mu_i}{\mu_k}, sont des réels de somme 1, dont il reste à montrer qu'ils sont tous positifs ou nuls.

Si \mu_i > 0\,, alors \frac{\lambda_i}{\mu_i} \geq \frac{\lambda_k}{\mu_k} et donc \delta_i \geq 0. Si \mu_i \leq 0, alors \delta_i\, est positif en tant que somme de deux termes positifs.

x est donc barycentre à coefficients positifs ou nuls de p éléments de A.

Une preuve comme conséquence du théorème de Helly[modifier | modifier le code]

Les possibilités de déduire l'un de l'autre les théorèmes de Helly et de Caratheodory, le premier parlant d'intersections finies de convexes, qu'on peut ramener au seul problème d'intersections finies de demi-espaces, tandis que le second parle d'enveloppe convexe d'un nombre fini de points sont fort instructives pour illustrer les techniques de dualité en géométrie convexe, qui échangent points et demi-espaces. Deux preuves du théorème de Helly dans l'article qui lui est consacré en font une conséquence de Carathéodory, dont une fort instructive via le lemme de Farkas ; aller dans l'autre sens (tirer Carathéodory de Helly) est plutôt plus facile encore, et on peut se borner à utiliser un théorème de Gordan d'esprit voisin du lemme de Farkas, mais de démonstration nettement plus aisée.

Soit x un point de l'enveloppe convexe de A. Quitte à translater la figure, on peut supposer que x=0. Il existe donc une famille finie de points de A, soit (a_1,\ldots,a_k) dont 0 est un barycentre à coefficients positifs ou nuls. Si k\leq n+1 il n'y a rien à faire, supposons donc n+2\leq k. On munit E d'une structure euclidienne, et pour chacun des a_j on considère la forme linéaire f_j définie sur E par f_j(y)=<a_j|y> et le demi-espace R_j=\{y\in E|f_j(y)>0\}.

Le théorème de Gordan (en réalité le sens évident de celui-ci) assure que les demi-espaces R_j (j variant entre 1 et k) ont une intersection vide. Le théorème de Helly assure à son tour qu'il en existe une sous-famille avec seulement d+1 membres qui a à son tour une intersection vide. Le sens plus significatif du théorème de Gordan permet alors de conclure que les d+1 points a_j correspondant à cette liste ont à leur tour 0 dans leur enveloppe convexe[2].

Corollaire : un résultat de compacité[modifier | modifier le code]

Corollaire — Dans un espace affine de dimension finie, l'enveloppe convexe d'un compact est compacte.

En effet, soit \Delta\, l'ensemble des p+1\,-uples de nombres positifs de somme 1\,. Alors \mathrm{Conv}(A) est l'image du compact A^{p+1}\times \Delta par l'application continue

 (a_1,\cdots, a_{p+1}, u_1,\cdots, u_{p+1})\mapsto\sum_{i=1}^{p+1}u_ia_i.

Un théorème de Fenchel et Bunt[modifier | modifier le code]

Si l'on suppose en outre que A est connexe (ou même seulement qu'il n'a pas trop de morceaux), on peut limiter le nombre de sommets des simplexes nécessaires pour construire l'enveloppe convexe à la dimension de l'espace ambiant. L'énoncé précis, dû à W. Fenchel et L. Bunt est le suivant[3] :

Théorème — Dans un espace affine de dimension n, soit A un sous-ensemble ayant au plus n composantes connexes. Alors l'enveloppe convexe de A est l'ensemble des barycentres à coefficients positifs ou nuls de familles de n points de A.

Ainsi dans le cas le plus simple, celui de la dimension 2, si une figure plane A est formée d'au plus deux morceaux, on peut reconstituer son enveloppe convexe en faisant la réunion de tous les segments ayant leurs deux extrémités dans A.

Références[modifier | modifier le code]

  1. Constantin Carathéodory, Über den Variabilitätsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen, Math. Ann., 64:95-115, 1907. On trouvera un exposé moderne du théorème par exemple dans Marcel Berger, Géométrie [détail des éditions], Théorème 11.1.8.6, tome 3, p. 27.
  2. Cette preuve figure dans H.G. Eggleston, Convexity, Cambridge University Press, coll. « Tracts in Mathematics and Mathematical Physics » n° 47, 1958, réimpression avec corrections 1969, p. 40-41
  3. L'énoncé et sa démonstration figurent dans H.G. Eggleston, op. cit. p. 37-38 ; pour l'attribution du résultat à Fenchel et Butt, voir Fundamentals of convex analysis, Jean-Baptiste Hiriart-Urruty et Claude Lemaréchal, coll. « Grundlehren Text Editions », Springer, 2001 (ISBN 3540422056), Th. 1.3.7, p. 30.