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

Ne pas confondre avec le théorème d'extension de Carathéodory.

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.

Sommaire

1 Énoncé
2 Preuves
- 2.1 La preuve usuelle
- 2.2 Une preuve comme conséquence du théorème de Helly
3 Corollaire : un résultat de compacité
4 Un théorème de Fenchel et Bunt
5 Références

Énoncé

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

La preuve usuelle

Notons $Conv(A)$ l'enveloppe convexe de $A$ , et $Γ$ 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 $λ 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

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é

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 $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

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 (de) 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$ .

Démonstration

Préparons d'abord le terrain pour la preuve en envisageant la situation suivante : soit $(y_1,\ldots,y_{n+1})$ un $n + 1$ -uplet de $\R^n$ ayant pour enveloppe affine $\R^n$ tout entier, et positionné de telle sorte que $y_1+\cdots+y_{n+1}=0$ . Pour chaque indice $i$ entre $1$ et $n + 1$ , notons $C i$ l'ensemble des points $x$ de $\R^n$ qui peuvent s'écrire $x=\alpha_1 y_1+\cdots+\alpha_{i-1}y_{i-1}+\alpha_{i+1}y_{i+1}+\cdots+\alpha_{n+1}y_{n+1}$ avec des coordonnées $α k$ toutes strictement positives (et pas de terme en $y i$ ).

On vérifie alors aisément les informations suivantes :

(i) Chaque $C i$ est un ouvert de $\R^n$
(ii) Tout point de $\R^n$ peut s'écrire de façon unique comme une combinaison linéaire $x=\alpha_1 y_1+\cdots+\alpha_{n+1}y_{n+1}$ à coefficients positifs ou nuls, l'un au moins des coefficients étant nul
(iii) Pour $i\not=j$ , $C i$ et $C j$ sont disjoints.

(Pour la première, on songera que $(y_1,\ldots,y_{i-1},y_{i+1},\ldots,y_{n+1})$ est une base de $\R^n$ et qu'on peut donc écrire tout point proche d'un $\alpha_1 y_1+\cdots+\alpha_{i-1}y_{i-1}+\alpha_{i+1}y_{i+1}+\cdots+\alpha_{n+1}y_{n+1}$ de $C i$ par une formule ayant la même forme dans laquelle les coefficients sont proches des $α i$ ; pour la seconde, on s'assurera d'abord qu'étant donnée une écriture $x=\alpha_1 y_1+\cdots+\alpha_{n+1}y_{n+1}$ d'un point de $R n$ comme combinaison linéaire des $y i$ , ses autres écritures comme telles combinaisons linéaires sont exactement les écritures $x=(\alpha_1+\rho) y_1+\cdots+(\alpha_{n+1}+\rho)y_{n+1}$ où $ρ$ parcourt $\R$ , une fois ceci connu, l'ajustement requis des coefficients est atteint pour le seul choix de $ρ = - Min i (α i)$ ; la troisième découle immédiatement de la seconde, puisqu'un hypothétique point de $C_i\cap C_j$ aurait deux écritures différentes vérifiant toutes les conditions ci-dessus).

On peut alors entamer la démonstration proprement dite. Soit un point arbitraire de $Conv(A)$ , l'objectif étant de parvenir à l'écrire comme barycentre à coefficients positifs de $n$ points de $A$ ; quitte à prendre un système de coordonnées approprié sur l'espace affine ambiant, on peut supposer que celui-ci est $\R^n$ et que le point étudié est l'origine. Le théorème de Carathéodory nous fournit déjà une écriture :

$(1)\qquad 0=\lambda_i x_1+\cdots+\lambda_{n+1}x_{n+1}$

de $0$ comme combinaison linéaire à coefficients positifs de $n + 1$ points de $A$ .

Deux cas dégénérés se traitent sans difficulté : si un au moins des $λ i$ est nul, on a terminé ; si l'enveloppe affine des $x i$ n'est pas $\R^n$ tout entier, en appliquant le théorème de Carathéodory dans cette enveloppe affine on peut diminuer d'au moins un le nombre de ceux-ci dans l'écriture de $0$ .

Reste le cas sérieux, celui où les $x i$ forment un repère affine de $\R^n$ , tous les coefficients $λ i$ qui apparaissent dans $(1)$ étant strictement positifs. On pose alors pour chaque indice $i$ , $y i = - λ i x i$ : ces points sont positionnés comme sommets d'un simplexe dont le centre de gravité est à l'origine et on peut donc utiliser les $C i$ introduits en préliminaires.

Parmi les $n + 1$ points $x i$ de $A$ , qui a au plus $n$ composantes connexes, il est inévitable que deux au moins, disons $x j$ et $x k$ appartiennent à une même composante connexe $A 0$ de $A$ . Cela entraîne que $A$ ne peut être inclus dans $C_1\cup\cdots\cup C_{n+1}$ : si tel était le cas, la division de $A 0$ en les deux parties $A_0 \cap C_j$ et $A_0 \cap \left(C_1\cup \cdots C_{j-1}\cup C_{j+1}\cup\cdots\cup C_{n+1}\right)$ découperait $A 0$ en deux ouverts (dans $A 0$ ) disjoints, non vides puisque l'un contient $x j$ et l'autre $x k$ . On a donc ainsi montré que $A$ contient au moins un point $x$ qui n'est dans aucun des $C i$ .

Vu d'une part la remarque (i), et vu d'autre part la non-appartenance de $x$ aux $C i$ , c'est donc que $x$ peut être écrit comme combinaison linéaire des $y i$ à coefficients tous positifs dont deux au moins sont nuls ; quitte à renuméroter les $x i$ , on supposera pour simplifier l'écriture que ce sont les deux premiers.

On dispose alors, pour ce point $x$ de $A$ d'une écriture :

$x=\beta_3y_3+\cdots+\beta_{n+1}y_{n+1}$

dans laquelle tous les $β i$ sont positifs.

Il ne reste plus qu'à regrouper différemment celle-ci, en allant rechercher la définition des $y i$ :

$0={x+ \lambda_3\beta_3x_3+\cdots+\lambda_{n+1}\beta_{n+1}x_{n+1}\over{1+\lambda_3\beta_3+\cdots+\lambda_{n+1}\beta_{n+1}}}$

pour obtenir ce qu'on cherchait depuis le début : une écriture de $0$ comme barycentre à coefficients positifs de seulement $n$ points de $A$ .

Références

↑ 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.
↑ 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
↑ 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.

v · Ensemble convexe Outils et résultats fondamentaux : Enveloppe convexe • Adhérence, intérieur et frontière d'un convexe • Projection sur un convexe fermé • Séparation des convexes • Points remarquables à la frontière d'un convexe • Polytope • Théorème de Krein-Milman • Lemme de Farkas Géométrie combinatoire : Théorème de Carathéodory • Théorème de Radon • Théorème de Helly Géométrie métrique : Courbe de largeur constante • Théorème des quatre sommets Algorithmes de géométrie convexe : Approche polyédrique • Marche de Jarvis • Parcours de Graham • Théorème optimisation/séparation Optimisation linéaire : Optimisation linéaire • Algorithme du simplexe • Génération de colonnes
Interactions géométrie-analyse	Théorème de Hahn-Banach • Jauge
Analyse convexe	Articles principaux : Ensemble convexe • Fonction convexe Outils et résultats fondamentaux : Conditions de Kuhn-Tucker • Inégalité de Jensen Algorithmique : Méthodes de points intérieurs
Utilisations de la convexité	Inégalités de convexité : Inégalité arithmético-géométrique • Inégalité de Hölder Analyse fonctionnelle : Espace localement convexe • Théorème du point fixe de Schauder Localisation de zéros de polynômes : Théorème de Gauss-Lucas Théorie des nombres : Théorème de Minkowski

Portail de la géométrie

Catégories :

Analyse convexe
Géométrie convexe
Théorème de géométrie

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Théorème de Carathéodory (géométrie) de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

Théorème de carathéodory (géométrie) — 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. Sommaire 1 Énoncé 2 Preuves 2.1 La preuve usuelle … Wikipédia en Français
Théorème de Radon (Géométrie) — Sommaire 1 Énoncé 2 Preuve 3 Théorème de Tverberg 4 Notes et références // … Wikipédia en Français
Théorème de radon (géométrie) — Sommaire 1 Énoncé 2 Preuve 3 Théorème de Tverberg 4 Notes et références // … Wikipédia en Français
Théorème de Radon (géométrie) — Sommaire 1 Énoncé 2 Preuve 3 Théorème de Tverberg 4 Notes et références Énoncé Le théorème de … Wikipédia en Français
Théorème de Helly — dans le plan : si trois quelconques des convexes de la famille se rencontrent alors l intersection de tous ces convexes est non vide. Le théorème de Helly est un résultat combinatoire sur les convexes. Ce résultat a été prouvé en 1913 par… … Wikipédia en Français
Théorème de helly — Le théorème de Helly est un résultat combinatoire sur les convexes. Ce résultat a été prouvé en 1913 par Eduard Helly, et il a été publié par Johann Radon en 1921[1],[2]. Énoncé Théorème … Wikipédia en Français
Theoreme de Cauchy-Lipschitz — Théorème de Cauchy Lipschitz Pour les articles homonymes, voir Cauchy. Cauchy développe une première version du théorème de l article. Le … Wikipédia en Français
Théorème de Picard-Lindelöf — Théorème de Cauchy Lipschitz Pour les articles homonymes, voir Cauchy. Cauchy développe une première version du théorème de l article. Le … Wikipédia en Français
Théorème de cauchy-lipschitz — Pour les articles homonymes, voir Cauchy. Cauchy développe une première version du théorème de l article. Le … Wikipédia en Français
Theoreme de Minkowski — Théorème de Minkowski En mathématiques, le théorème de Minkowski est un résultat concernant la géométrie des réseaux. Il relie le nombre de points du réseau contenu dans une partie convexe symétrique au volume fondamental du réseau. Ce théorème… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

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

Sommaire

Énoncé

Preuves

La preuve usuelle

Une preuve comme conséquence du théorème de Helly

Corollaire : un résultat de compacité

Un théorème de Fenchel et Bunt

Références

Regardez d'autres dictionnaires:

Share the article and excerpts

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

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

Sommaire

Énoncé

Preuves

La preuve usuelle

Une preuve comme conséquence du théorème de Helly

Corollaire : un résultat de compacité

Un théorème de Fenchel et Bunt

Références

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link