<<

. 57
( 63 .)



>>


Folgerung 9.29
Sei X normierter Vektorraum und sei x0 ∈ X\{θ}. Dann gibt es » ∈ X — mit
< », x0 >= 0.
Beweis:
U := L({x0}), µ : U ±x0 ’’ ± ∈ IR . Wende nun Satz 9.28 an.

Eine geometrische Version des Satzes von Hahn-Banach ist


Satz 9.30
—¦
Sei X ein normierter IR ’Vektorraum, seien A, K ‚ X konvex und sei K = ….
Dann gibt es » ∈ X — \{θ} und ± ∈ IR mit

sup < », u > ¤ ± ¤ inf < », v >
v∈A
u∈K

Beweis: —¦
Sei x0 ∈ K und sei Br (x0) ‚ K. Sei u0 ∈ A beliebig. Setze

Z := u0 + K ’ A.

Klar, Z ist konvex, u0 ∈ Z, und Br (x0) ‚ Z. (Beachte θ ∈ U 0 ’ A.)
/
De¬niere
p(x) := inf{t > 0|t’1 x ∈ Z} , x ∈ X.
Da zu beliebigem x ∈ X stets ein t > 0 existiert mit t’1 x ∈ Br (x0) ‚ K ‚ Z, ist p
wohlde¬niert. Ferner gilt:
Baumeister: Lineare Algebra II / Stand: August 1996 238


1. p(θ) = 0, p(x) ≥ 0 ∀x ∈ X;

2. p(rx) = rp(x) , r ≥ 0, x ∈ X;

3. p(x + y) ¤ p(x) + p(y) ∀x, y ∈ X;
4. p(v) ≥ 1 ∀v ∈ X\Z, p(z) ¤ 1 ∀z ∈ Z.
(1 ) und (4) sind sofort einzusehen, (2) folgt aus der De¬nition von p, (3) folgt so:
Sei > 0, s := p(x) + 2 , t := p(y) + 2 . Da s > p(x), t > p(y) ist, gilt s’1 x, t’1 y ∈ Z.
Wegen der Konvexit¨t von Z folgt dann
a

(s + t)’1 (x + y) = (s + t)’1(s(s’1 x) + t(t’1 y)) ∈ Z,

also, dank p((s + t)’1 (x + y)) ¤ 1, schließlich

p(x + y) = (s + t)(p((s + t)’1(x + y)))
¤ (s + t) = p(x) + p(y) + .

Da > 0 beliebig war, folgt die Aussage (4).
Also ist p ein sublineares Funktional. De¬niere auf U := L({u0 }) das lineare Funktional

±u0 ’’ ±p(u0 ) ∈ IR .
µ:U

Wir erhalten fur a ∈ IR
¨

< µ, au0 > ¤ max(0, ap(u0 )) ¤ p(au0 ).

Also gibt es nach Satz 9.27 ein » ∈ X mit

»|U = µ, < », x > ¤ p(x) ∀x ∈ X.

Daraus folgt fur z ∈ Z :
¨

< », z > ¤ p(z) ¤ 1 ¤ p(u0 ) = < », u0 > = < µ, u0 > .

Damit ist insbesondere » = θ und fur u ∈ K, v ∈ A folgt
¨

< », u0 + u ’ v > ¤ 1, d.h < », u > ¤ < », v > .

Insbesondere haben wir
< », u > ¤ ± := inf < », v >
v∈A

fur u ∈ Br (x0). Dies zeigt » ∈ X — .
¨

Bemerkung 9.31
Das im Beweis von Satz 9.30 aufgefuhrte Funktional
¨

p(x) := inf{t > 0|t’1 x ∈ Z} , x ∈ X

2
heißt das Minkowskifunktional (der Menge Z).
Baumeister: Lineare Algebra II / Stand: August 1996 239


9.4 Lineare Ungleichungen *
Wir betrachten hier lineare Ungleichungen in IRn . Dazu benotigen wir
¨
Bezeichnungen : IR n := {x ∈ IR n | xi ≥ 0, 1 ¤ i ¤ n},
+
IR n := {x ∈ IR n | xi > 0, 1 ¤ i ¤ n}.
>

Orthogonale Komplemente sind stets bezuglich des euklidischen Skalarprodukts < ·, · >:=<
¨
·, · >2 gebildet. Beachte auch, daß der algebraische (stetige) Dualraum von IR n verm¨ge
o
n
des euklidischen Skalarprodukts mit IR identi¬ziert werden kann.


Lemma 9.32

Sei U ein linearer Teilraum von IR n mit U © IRn = {θ}. Dann gilt U ⊥ © IRn = ….
+ >

Beweis:
Annahme: U ⊥ © IRn = ….
>

w + IR n gilt, ist K := U ⊥ + IR n o¬en. O¬enbar ist K auch konvex.
n
Da U + IR > = > >
w∈U ⊥

Wegen U © IR > = …, ist θ ∈ K. Nach Satz 9.27 gibt es x ∈ IR n \{θ} mit
n
/ >

0 ¤ inf{< y, x > |y ∈ U ⊥ + IRn }. (9.3)
>

Daraus folgt
0 ¤ inf{< y, x > |y ∈ U ⊥ }
wegen der Stetigkeit von < ·, · > . Wegen ’U ⊥ = U ⊥ und θ ∈ U ⊥ folgt

sup{| < y, x > ||y ∈ U ⊥} = sup{< y, y > |y ∈ U ⊥ } = ’ inf{< ’y, x > |y ∈ U ⊥ } ¤ 0.

Dies zeigt x ∈ (U ⊥ )⊥ = U. Nun folgt aus (9.3) auch

0 ¤ inf{< u, x > |u ∈ IRn }
>

und aus Stetigkeitsgrunden
¨

0 ¤ < ei , x > , 1 ¤ i ¤ n,

also x ∈ IR n . Dies steht im Widerspruch zur Voraussetzung, da x ∈ U © IR n \{θ}.
+ +



Satz 9.33
Sei A ∈ IRm,n . Dann sind ¨quivalent:
a

(a) Es gibt x ∈ IR n mit Ax = θ.
>

(b) Es gibt kein y ∈ IR n mit Aty ∈ IR n \{θ}.
+

Beweis:
(a) =’ (b)
Es folgt aus y ∈ IR n mit At y ≥ θ stets < At y, x > = < y, Ax > = 0. Da x ∈ IR n ist, ist
>
Baumeister: Lineare Algebra II / Stand: August 1996 240


Aty = θ.
(b) =’ (a)
Setze U := Bild (At). Dann wissen wir U © IRn = {θ}. Aus Satz 9.32 folgt die Existenz
+

von x ∈ U © IR > . Damit folgt
n


< y, Ax > = < Aty, x > = 0 fur alle y ∈ IRn ,
¨

und daher Ax = θ.

Nun k¨nnen wir einen Existenzsatz fur Ungleichungen beweisen.
o ¨

Satz 9.34
Sei A ∈ IRm,n . Dann gibt es x ∈ IR n, y ∈ IR m mit

x + At y ∈ IR n , Ax = θ, x ∈ IRn , Aty ∈ IR n .
+ + +

Beweis:
Sei A = (a1| . . . |an) und Y := {y ∈ IR m |At y ∈ IR n }.
+
Betrachte

y ’’ {i ∈ {1, . . . n}|(Aty )i > 0} ∈ P OT ({1, . . . , n})
f :Y

Dann gibt es o¬enbar y ∈ Y, sodaß f(y) maximal bezuglich der Inklusion ist;
¨
k := #f(y). De¬niere Matrizen B = (b | . . . |b ) ∈ IR m,n und C = (c1 | . . . |cn ) ∈ IRm,n
1 n

durch
ai , i ∈ f(y)
i
b :=
θ , sonst
, i ∈ f(y)
θ
ci :=
ai , sonst
O¬enbar ist A = B + C , C t y = θ. Fur s ∈ IR und z ∈ IR n gilt
¨

At(sy + z) = sB ty + B t z + C t z.

Annahme: Es gibt j und z ∈ IR n mit < cj , z > > 0.
Dann ist j ∈ f(y) und wegen
/

< aj , sy + z > = < aj , y > + < aj , z >

folgt:
i ∈ f(y) =’ < aj , sy + z > > 0 fur s genugend groß,
¨ ¨
i = j ∈ f(y) =’ < aj , sy + z > = < aj , z > > 0.
/
Also haben wir einen Widerspruch zur Konstruktion von f(y).
Dies zeigt, daß die Bedingung (b) in Satz 9.33 mit C anstelle von A erfullt ist. Also gibt
¨
es w ∈ IR > mit Cw = θ. De¬niere x ∈ IR + durch
n n


, i ∈ f(y)
0
xi :=
, i ∈ f(y)
wi /
Baumeister: Lineare Algebra II / Stand: August 1996 241


Es gilt dann Cx = θ und Bx = θ, also Ax = θ. Schließlich ist auch x + Aty ∈ IR n nach
+
Konstruktion von y und De¬nition von x.

Als Folgerung erhalten wir das sogenannte Lemma von Farkas.


Lemma 9.35
Sei A ∈ IRm,n , b ∈ IR m . Dann sind aquivalent:
¨
(a) Ax = b hat eine L¨sung x ∈ IR n .
o +

(b) Aty ∈ IR n impliziert < y, b > ≥ 0.
+

Beweis:
(a) =’ (b)
Sei Aty ∈ IR n . Es folgt
+

< y, b > = < y, Ax > = < At y, x > ≥ 0.

(b) =’ (a)
Sei B := (A|b). Nach Satz 9.34 gibt es x ∈ IR n+1 , y ∈ IR m mit

<<

. 57
( 63 .)



>>