<<

. 54
( 63 .)



>>


(b) M heißt konvex, falls fur alle x, y ∈ M und a ∈ [0, 1] ax + (1 ’ a)y ∈ M
¨
gilt.
2

Klar, jeder lineare Teilraum und jeder a¬ne Unterraum eines IR “ Vektorraums ist konvex.

Beispiel 9.2
Sei (X, · ) normierter IR “ Vektorraum. Die o¬enen Kugeln
Br (x0) := {x ∈ X| x ’ x0 < r}
0


und die abgeschlossenen Kugeln
Br (x0) := {x ∈ X| x ’ x0 ¤ r}
sind konvex. Dies folgt mit der Dreiecksungleichung. Hier ist der Beweis zu Br (x0 ).
Seien x, y ∈ Br (x0 ), d.h. x ’ x0 ¤ r, y ’ x0 ¤ r. Sei a ∈ [0, 1].
ax + (1 ’ a)y ’ x0 = a(x ’ x0) + (1 ’ a)y
¤ a(x ’ x0) + (1 ’ a)(y ’ x0 )
= |a| x ’ x0 + |1 ’ a| y ’ x0
¤ ar + (1 ’ a)r = r.

224
Baumeister: Lineare Algebra II / Stand: August 1996 225


2
Dies zeigt: ax + (1 ’ a)y ∈ Br (x0).


Lemma 9.3
Seien X, Y IR “ Vektorr¨ume, sei L : X ’’ Y linear, seien K1 , K2 ‚ X, K3 ‚ Y
a
konvex und seien a, b ∈ IR . Dann gilt

(a) K1 © K2 ist konvex.

(b) K1 — L(K2 ) := {(u, v) ∈ X — Y |u ∈ K1 , v ∈ L(K1 )} ist konvex (in X — Y ).

(c) L’1 (K3 ) := {u ∈ X|L(x) ∈ K3 } ist konvex.

(d) aK1 + bK2 := {au + bv|u ∈ K1 , v ∈ K2 } ist konvex.
Beweis:
Trivial



Beispiel 9.4
Sei X IR “ Vektorraum mit Dualraum X . Sei » ∈ X , ± ∈ IR . Dann sind

H»,± := {x ∈ X| < »x > ≥ ±} , H»,± := {x ∈ X| < », x > ≥ ±} ,
+



H»,± := {x ∈ X| < », x > = ±} , H»,± \H»,±, H»,± \H»,±
+


konvex. Dies folgt im wesentlichen aus der Linearitat von < ·, · > im 2. Argument.
¨

Die Mengen
’ ’
H»,±, H».± bzw. H»,±\H»,± , H»,±\H»,±
+ +


werden Halbr¨ume bzw. o¬ene Halbr¨ume genannt. Bekanntlich ist H»,± eine Hyper-
a a
2
ebene, falls » = θ und H»,± = … ist.


De¬nition 9.5
Sei (X, σ) ein euklidischer Raum und sei P ‚ X, P = ….

(a) P heißt Polyhedron, genau dann, wenn es Halbraume
¨

Hi := {x ∈ X|σ(zi, x) ¤ ai } (zi ∈ X, ai ∈ IR) , 1 ¤ i ¤ k,

gibt mit
k
P= Hi .
i=1

(b) P heißt Polytop, genau dann, wenn P ein beschr¨nktes Polyhedron ist.
a
2
Baumeister: Lineare Algebra II / Stand: August 1996 226


Es ist unmittelbar klar, daß jedes Polyeder und jedes Polytop konvex ist.


Beispiel 9.6
Sei X IR ’Vektorraum und sei A ‚ X. Setze

A := {» ∈ X | < », u > ¤ 1 fur alle u ∈ A}.
¨

2
Dann ist A eine konvexe Teilmenge von X . A heißt die zu A polare Menge.


Lemma 9.7
Sei (X, · ) normierter IR “ Vektorraum und sei K ‚ X konvex. Dann ist auch

K( ) := K + B (θ) := {u ∈ X| ∃ x ∈ K( u ’ x ¤ } ,

Abschluß von K und das Innere von K konvex.
Beweis:
Trivial

Ist eine Teilmenge A eines IR “ Vektorraumes X nicht konvex, so kann man versuchen,
eine kleinste“ (im Sinne der Inklusion) konvexe Menge K zu ¬nden, die A enthalt. Da
¨

der Raum X sicherlich konvex ist, macht dies Sinn.


De¬nition 9.8
Sei X ein IR “ Vektorraum und sei A ‚ X. Die Menge

{C | C ⊃ A , C konvex}
K :=

heißt konvexe Hulle von A. Wir schreiben
¨

K = co(A).
2
Eine naheliegende Verallgemeinerung der Regel (a) aus Lemma 9.3 fur beliebige Durch-
¨
schnitte belegt, daß co(A) stets konvex ist.


Folgerung 9.9
Sei X IR “ Vektorraum, A ‚ X. Dann gilt
n n
co(A) = {x ∈ X|x = aiu , u , . . . , u ∈ A, a1, . . . , an ∈ [0, 1], ai = 1, n ∈ IN }
i 1 n

i=1 i=1

Beweis: n n
Sei K := {x ∈ X|x = ai u , u , . . . , u ∈ A, a1, . . . , an ∈ [0, 1], ai = 1, n ∈ IN } .
i 1 n
i=1 i=1
K ist o¬enbar konvex und A ist in K enthalten. Daraus folgt sofort co(A) ‚ K. Ist x ∈ K,
dann ist o¬enbar x ∈ co(A). Also gilt co(A) = K.
Baumeister: Lineare Algebra II / Stand: August 1996 227


Folgerung 9.10

Sei X IR “ Vektorraum und seien A1 ‚ A2 ‚ X. Dann gilt co(A1) ‚ co(A2) .
Beweis:
Trivial mit Folgerung 9.9.


Beispiel 9.11
Wir betrachten die Menge S := {(eσ(1)| . . . |eσ(n)) ∈ IR n,n |σ ∈ Sn }
Wir wissen #S = n! . Setze
D := co(S).
Man rechnet nach, daß fur eine Matrix D = (dij ) ∈ D gilt:
¨
n n
dik = 1 , dij ≥ 0 , 1 ¤ i, j ¤ n.
dkj =
k=1 k=1

2
Die Matrizen in D nennt man doppeltstochastische Matrizen.


Satz 9.12
Sei X ein n’dimensionaler IR “ Vektorraum, sei A ‚ X, A = …. Dann gilt
m m
ai x | ai = 1, xi ∈ A, ai ∈ [0, 1], 1 ¤ i ¤ m , m ¤ n + 1
i
co(A) = x =
i=1 i=1

Beweis:
n
O.E. sei X = IRm . m
Sei K := {x = aixi |xi ∈ A, ai ∈ [0, 1], 1 ¤ i ¤ m, ai = 1 , m ¤ n + 1}.
i=1 i=1
k k
Sei x ∈ co(A), d. h. x = ai xi, xi ∈ A, ai ∈ A, ai ∈ [0, 1], 1 ¤ i ¤ k, und ai = 1. Ist
i=1 i=1
k ¤ n + 1, ist x ∈ K und nichts ist mehr zu zeigen. Sei also nun k > n + 1. Da dim X = n
x1 . . . xk
und k > n + 1 ist, ist rg(M) ¤ n + 1, wobei M := ∈ IR n+1,k ist. Also
1 ... 1
gibt es b1 , . . . , bk ∈ IR mit
k k k
i
b2 = 0.
bi x = θ , bi = 0 , i
i=1 i=1 i=1

Setze
Q := {q ∈ IR |qbi + ai ≥ 0, 1 ¤ i ¤ k}
Q ist abgeschlossen, nichtleer, da 0 ∈ Q, und verschieden von IR, da nicht alle bi ver-
schwinden. Sei q ∈ Q, sodaß qbj + aj = 0 fur mindestens ein j ∈ {1, . . . , k} ist. Ein solches
¨
q existiert, da Q = IR und Q abgeschlossen ist. Dann ist
k k k
i i
(ai + qbi)xi = (ai + qbi)xi
x= ai x + q bi x =
i=1 i=1 i=1 i=j
Baumeister: Lineare Algebra II / Stand: August 1996 228


und wir haben eine Darstellung von x als Konvexkombination durch k ’ 1 Vektoren, da
(ai + qbi ) = 1 und daher ai + qbi ∈ [0, 1], 1 ¤ i ¤ k, gilt.
i=j

Der obige Satz 9.12 wird Satz von Carath´odory genannt. An einem Dreieck in der
e
Ebene kann man ihn sich gut veranschaulichen. Etwa erh¨lt man den Schwerpunkt x eines
a
Dreiecks mit den Endpunkten

P1 : a1 , P2 : a2 , P3 : a3

(Koordinaten ai bzgl. der Standardbasis) als
1 1 1
x = a1 + a2 + a3
3 3 3
(Je nach Betrachtungsweise, kann man dies auch als de¬nierende Gleichung fur den
¨
Schwerpunkt ansehen.)


Aus dem Satz von Carath´odory schließt man sehr einfach, daß co(A) beschr¨nkt (kom-
e a
pakt) ist, falls A beschr¨nkt (kompakt) ist.
a

Jede konvexe Menge
K = co({x1 , . . . , xk })
in einem IR “ Vektorraum X wird ein konvexes Viel¬‚ach in X genannt.



Beispiel 9.13
D aus Beispiel 9.11 ist ein konvexes Viel¬‚ach.


De¬nition 9.14
Sei X ein IR “ Vektorraum und seien x0, . . . , xk ∈ X a¬n linear unabh¨ngig. Dann
a
nennen wir das Viel¬‚ach

Σ(x0 , . . . , xk ) := co({x0 , . . . , xk })

einen k “ Simplex.
2

Ist K eine Teilmenge des IR “ Vektorraums X, dann gibt es einen kleinsten a¬nen Teil-
raum A (bzgl. der Inklusion) mit K ‚ A; man nennt dieses A a¬ne Hulle von K. Als
¨
Dimension k¨nnen wir dann K die a¬ne Dimension der a¬nen Hulle von K zuweisen.
o ¨

<<

. 54
( 63 .)



>>