konische bwz lin. Hülle < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:24 So 24.04.2016 | | Autor: | lisa2802 |
| Aufgabe | Sei S [mm] \subseteq \IR^n.
[/mm]
Zeigen Sie
cone S = lin S [mm] \gdw \forall [/mm] x [mm] \in [/mm] S : -x [mm] \in cone(S\setminus{ \{x\} })
[/mm]
cone S = konische Hülle von S und lin S = lineare Hülle von S |
hallo ihr lieben, :)
"Definiton" im Skript
cone [mm] \{x_1,...x_n\} [/mm] := [mm] \{\lambda_1 * x_1+...+ \lambda_n * x_n : \lambda_1,...\lambda_n \ge 0\}
[/mm]
lin [mm] \{x_1,...x_n\} [/mm] := [mm] \{\lambda_1*x_1+...+\lambda_n * x_n\}
[/mm]
Also sind in der lineare Hülle von S die Menge aller Linearkombinationen von S und in der konischen Hülle "nur" alle positiven Linearkombinationen von S. und das soll genau dann gleich sein wenn für alle Elemenet aus S gilt, dass -x aus der konischen Hülle von S ohne x ist.
wobei :
konischen Hülle=kleinster konvexer Kegel der S enthält
konvexer kegel : zwei punkte aus konv. Kegel dann auch deren verbindungstrecke
ist das erstmal so vom verständnis her korrekt?
Wenn cone S = lin S, dann wird die lineare Hülle ja auch reduziert auf die menge aller positiven lin. Komb. ( also statt [mm] \lambda \in \IR [/mm] ist [mm] \lambda \in \IR^{+}_{0}). [/mm] Naja nun wann kann das der Fall sein?
Schreibe ich das jetzt in Summenform
lin S = [mm] \{ \summe_{i=1}^{n} \lambda_i * x_i : x_i \in S, \lambda \in \IR \}
[/mm]
cone S = [mm] \{ \summe_{i=1}^{n} \lambda_i * x_i : x_i \in S, \lambda \in \IR^{+}_{0} \}
[/mm]
nun ist lin S = cone S [mm] \gdw \forall [/mm] x [mm] \in [/mm] S : -x [mm] \in cone(S\setminus{ \{x\} })
[/mm]
S = [mm] \{x_1,...,x_n\} \in \IR^n [/mm] oder verstehe ich das Falsch? S ist eine Menge von Vektoren? oder ist S eine menge von m Vektoren aus dem [mm] \IR^n??
[/mm]
betrachte ich besipielhaft :
cone [mm] S\setminus \{x_1\} [/mm] = [mm] \{ \summe_{i=2}^{n} \lambda_i * x_i : x_i \in S\setminus \{x_1\}, \lambda \in \IR^{+}_{0} \}
[/mm]
insg :
cone S = cone [mm] \{x_1,...x_n\} [/mm] = [mm] \{ \summe_{i=1}^{n} \lambda_i * x_i : x_i \in S, \lambda \in \IR^{+}_{0} \} [/mm] = [mm] \{ \summe_{i=1}^{n} \lambda_i * x_i : x_i \in S, \lambda \in \IR \} [/mm] = lin [mm] \{x_1,...x_n\} [/mm] =lin S
[mm] \gdw
[/mm]
[mm] -x_1 \in \{ \summe_{i=2}^{n} \lambda_i * x_i : x_i \in S\setminus \{x_1\}, \lambda \in \IR^{+}_{0} \} [/mm] = cone [mm] S\setminus \{x_1\}.
[/mm]
So zum Ziegen werde ich ja beide Richtungen beweisen müssen.
1.
cone S = cone [mm] \{x_1,...x_n\} [/mm] = [mm] \{ \summe_{i=1}^{n} \lambda_i * x_i : x_i \in S, \lambda \in \IR^{+}_{0} \} [/mm] = [mm] \{ \summe_{i=1}^{n} \lambda_i * x_i : x_i \in S, \lambda \in \IR \} [/mm] = lin [mm] \{x_1,...x_n\} [/mm] =lin S
[mm] \Rightarrow
[/mm]
[mm] -x_1 \in \{ \summe_{i=2}^{n} \lambda_i * x_i : x_i \in S\setminus \{x_1\}, \lambda \in \IR^{+}_{0} \} [/mm] =cone [mm] S\setminus \{x_1\}.
[/mm]
2.
cone S = cone [mm] \{x_1,...x_n\} [/mm] = [mm] \{ \summe_{i=1}^{n} \lambda_i * x_i : x_i \in S, \lambda \in \IR^{+}_{0} \} [/mm] = [mm] \{ \summe_{i=1}^{n} \lambda_i * x_i : x_i \in S, \lambda \in \IR \} [/mm] = lin [mm] \{x_1,...x_n\} [/mm] =lin S
[mm] \Leftarrow
[/mm]
[mm] -x_1 \in \{ \summe_{i=2}^{n} \lambda_i * x_i : x_i \in S\setminus \{x_1\}, \lambda \in \IR^{+}_{0} \} [/mm] =cone [mm] S\setminus \{x_1\}.
[/mm]
es ist klar, dass das nur gleich sein kann wenn das gilt, weil dadurch, dass -x auch enthalten ist habe ich ja wieder die menge aller linearkombinationen statt nur der positiven.
ich hab jetzt sehr viel durcheiander hier. entschuldigt bitte.
Könntet ihr mir bitte helfen meine Ideen zu sortieren, damit ich auf den richtigen weg komme?
vielen Dank!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:14 So 24.04.2016 | | Autor: | hippias |
Ich sage gleich, dass ich mir Deinen Text nicht allzu genau durchgelesen habe, weil er mir nicht sehr zielführend aussieht; das kann aber auch an meiner Oberflächlichkeit liegen.
Ich schlage vor den Beweis in zwei Teilen zu führen:
1. Aus $cone(S)= lin(S)$ folgt: für alle [mm] $x\in [/mm] S$ gilt [mm] $-x\in cone(S\setminus\{x\})$.
[/mm]
und umgekehrt
2. Gilt für alle [mm] $x\in [/mm] S$, dass [mm] $-x\in cone(S\setminus\{x\})$, [/mm] so folgt $cone(S)= lin(S)$.
Mache Dir zunächst klar, dass stets [mm] $cone(S)\subseteq [/mm] lin(S)$ gilt bevor es an die eigentlichen Beweise geht.
zu 1. Es sei $cone(S)= lin(S)$ vorausgesetzt (in Worten: jede beliebige Linearkombination von Vektoren aus $S$ lässt sich als Linearkombination mit nichtnegativen Koeffizienten darstellen).
Nun sei [mm] $x\in [/mm] S$.
a) Mache Dir klar, dass [mm] $-x\in [/mm] lin(S)$ gilt.
b) Wende die Voraussetzung an, um $x$ als Linearkombination von Elementen aus $S$ mit nichtnegativen Koeffizienten darszustellen.
c) Stelle die Gleichung nach $x$ um; daraus folgt der erste Teil der Behauptung.
Den Rest später.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:59 So 24.04.2016 | | Autor: | lisa2802 |
Erstmal Danke!
> Ich sage gleich, dass ich mir Deinen Text nicht allzu genau
> durchgelesen habe, weil er mir nicht sehr zielführend
> aussieht; das kann aber auch an meiner Oberflächlichkeit
> liegen.
>
Kann ich gut nachvollziehen, ist auch sehr unstrukturiert und chaotisch.
> Ich schlage vor den Beweis in zwei Teilen zu führen:
> 1. Aus [mm]cone(S)= lin(S)[/mm] folgt: für alle [mm]x\in S[/mm] gilt [mm]-x\in cone(S\setminus\{x\})[/mm].
>
> und umgekehrt
> 2. Gilt für alle [mm]x\in S[/mm], dass [mm]-x\in cone(S\setminus\{x\})[/mm],
> so folgt [mm]cone(S)= lin(S)[/mm].
>
das war auch meine Idee ;)
> Mache Dir zunächst klar, dass stets [mm]cone(S)\subseteq lin(S)[/mm]
> gilt bevor es an die eigentlichen Beweise geht.
jup ist klar. "nur pos.lin.Komb [mm] \subseteq [/mm] allen lin. Komb"
>
> zu 1. Es sei [mm]cone(S)= lin(S)[/mm] vorausgesetzt (in Worten: jede
> beliebige Linearkombination von Vektoren aus [mm]S[/mm] lässt sich
> als Linearkombination mit nichtnegativen Koeffizienten
> darstellen).
>
> Nun sei [mm]x\in S[/mm].
> a) Mache Dir klar, dass [mm]-x\in lin(S)[/mm]
> gilt.
x [mm] \in [/mm] S, dann muss -x [mm] \in [/mm] lin(S) sein ,da zb [mm] \lambda*x [/mm] = -x mit [mm] \lambda [/mm] = -1; was aber nicht funktioniert wenn lin S= cone S ist ohne " für alle [mm] x\in [/mm] S gilt [mm] -x\in cone(S\setminus\{x\})" [/mm] ?
> b) Wende die Voraussetzung an, um [mm]x[/mm] als Linearkombination
> von Elementen aus [mm]S[/mm] mit nichtnegativen Koeffizienten
> darszustellen.
[mm] S=\{s_1,...,s_m,x\} [/mm] (oder wie sieht S aus?) da [mm] x\in [/mm] S gilt nach Vorrausetzung : lin S [mm] =\{ \summe_{i=1}^{n}\lambda_i * s_i + x ; s_i, x \in S, \lambda \ge 0\}=cone [/mm] S
> c) Stelle die Gleichung nach [mm]x[/mm] um; daraus folgt der erste
> Teil der Behauptung.
>
> Den Rest später.
>
>
da ist also ebenfalls nach Vorrausetzung -x [mm] \in [/mm] cone S. da aber in der konischen Hülle nur nichtnegative lin.Komb enthalten sind muss -x [mm] \in [/mm] S sein. Warum muss aber -x [mm] \in cone(S\setminus\{x\})?
[/mm]
Ich habe irgendwo einen Denkfehler :(
edit :
ich glaub ich hab den denkfehler beseitigt.
jetzt nur in Worte fassen:
1. Sei cone S = lin S.
Sei x [mm] \in [/mm] S [mm] \Rightarrow [/mm] -x [mm] \in [/mm] lin S [mm] \Rightarrow [/mm] -x [mm] \in [/mm] cone S (Vorrausetzung cone S = lin S).
für alle x [mm] \in [/mm] S gilt -x [mm] \in cone(S\setminus\{x\}), [/mm] -x muss aus [mm] cone(S\setminus\{x\}), [/mm] da ja in der konischen Hülle nur positve lin.Komb enthalten sind und wäre -x aus cone S, mit [mm] x\in [/mm] S, wäre ja auch x [mm] \in [/mm] cone S was nicht funkioniert aufgrund der Eigenschaft [mm] \lambda \ge [/mm] 0.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:24 Mo 25.04.2016 | | Autor: | hippias |
> [...]
> Ich habe irgendwo einen Denkfehler :(
>
> edit :
> ich glaub ich hab den denkfehler beseitigt.
> jetzt nur in Worte fassen:
>
> 1. Sei cone S = lin S.
> Sei x [mm]\in[/mm] S [mm]\Rightarrow[/mm] -x [mm]\in[/mm] lin S [mm]\Rightarrow[/mm] -x [mm]\in[/mm]
> cone S (Vorrausetzung cone S = lin S).
>
> für alle x [mm]\in[/mm] S gilt
Achtung, das nachfolgende muss doch erst noch bewiesen werden.
> -x [mm]\in cone(S\setminus\{x\}),[/mm] -x
> muss aus [mm]cone(S\setminus\{x\}),[/mm] da ja in der konischen
> Hülle nur positve lin.Komb enthalten sind und wäre -x aus
> cone S, mit [mm]x\in[/mm] S, wäre ja auch x [mm]\in[/mm] cone S was nicht
> funkioniert aufgrund der Eigenschaft [mm]\lambda \ge[/mm] 0.
>
Das ist unklar.
Du hast nun [mm] $-x\in [/mm] cone(S)$ eingesehen - übrigens: wie genau $S$ aussieht, ob endlich etc. ist unerheblich. Bei b) habe ich Dich aufgefordert $-x$ als Linearkombination von Elementen aus $S$ mit nicht negativen Koeffizienten darzustellen; denn nachdem [mm] $-x\in [/mm] cone(S)$ gezeigt ist, ist so eine Darstellung zweifelsfrei möglich.
Also $-x= [mm] \sum_{s\in S} \lambda_{s} [/mm] s$, [mm] $\lambda_{s}\geq [/mm] 0$. In dieser Summe taucht wegen [mm] $x\in [/mm] S$ auch der Summand [mm] $\lambda_{x}x$ [/mm] auf. Führe nun den unter c) beschriebenen Schritt aus.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:52 Mo 25.04.2016 | | Autor: | lisa2802 |
> > [...]
> > Ich habe irgendwo einen Denkfehler :(
> >
> > edit :
> > ich glaub ich hab den denkfehler beseitigt.
> > jetzt nur in Worte fassen:
> >
> > 1. Sei cone S = lin S.
> > Sei x [mm]\in[/mm] S [mm]\Rightarrow[/mm] -x [mm]\in[/mm] lin S [mm]\Rightarrow[/mm] -x
> [mm]\in[/mm]
> > cone S (Vorrausetzung cone S = lin S).
> >
> > für alle x [mm]\in[/mm] S gilt
> Achtung, das nachfolgende muss doch erst noch bewiesen
> werden.
Das war nur zum Verständnis. Wollte erst vrstehen warum es so ist bevor ich es versuche.
>
> > -x [mm]\in cone(S\setminus\{x\}),[/mm] -x
> > muss aus [mm]cone(S\setminus\{x\}),[/mm] da ja in der konischen
> > Hülle nur positve lin.Komb enthalten sind und wäre -x aus
> > cone S, mit [mm]x\in[/mm] S, wäre ja auch x [mm]\in[/mm] cone S was nicht
> > funkioniert aufgrund der Eigenschaft [mm]\lambda \ge[/mm] 0.
> >
> Das ist unklar.
>
> Du hast nun [mm]-x\in cone(S)[/mm] eingesehen - übrigens: wie genau
> [mm]S[/mm] aussieht, ob endlich etc. ist unerheblich.
okay.
Bei b) habe
> ich Dich aufgefordert [mm]-x[/mm] als Linearkombination von
> Elementen aus [mm]S[/mm] mit nicht negativen Koeffizienten
> darzustellen; denn nachdem [mm]-x\in cone(S)[/mm] gezeigt ist, ist
> so eine Darstellung zweifelsfrei möglich.
>
> Also [mm]-x= \sum_{s\in S} \lambda_{s} s[/mm], [mm]\lambda_{s}\geq 0[/mm]. In
> dieser Summe taucht wegen [mm]x\in S[/mm] auch der Summand
> [mm]\lambda_{x}x[/mm] auf. Führe nun den unter c) beschriebenen
> Schritt aus.
-x= [mm] \sum_{s\in S} \lambda_{s}s [/mm] mit [mm] \lambda_{s}\ge0
[/mm]
[mm] \gdw-x [/mm] = [mm] \sum_{s\in S\setminus\{x\}} \lambda_{s}s+\lambda_xx
[/mm]
[mm] \gdw-x-\lambda_x x=\underbrace {\sum_{s\in S\setminus\{x\}} \lambda_{s}s }_{=cone(S\setminus\{x\})}
[/mm]
[mm] \gdw-x(\lambda_x [/mm] +1) = [mm] cone(S\setminus\{x\})
[/mm]
[mm] \Rightarrow [/mm] lin S = cone S [mm] \Rightarrow [/mm] für alle x [mm] \in [/mm] S : -x [mm] \in cone(S\setminus\{x\})
[/mm]
das Versuche ich jetzt mal eben und teile meine ergebnise gleich mit.
ist es denn bis hier hin ok?
so jetzt die Rückrichtung :
für alle x [mm] \in [/mm] S : -x [mm] \in cone(S\setminus\{x\}) \Rightarrow [/mm] lin S = cone S
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:22 Mo 25.04.2016 | | Autor: | hippias |
> > > [...]
> > > Ich habe irgendwo einen Denkfehler :(
> > >
> > > edit :
> > > ich glaub ich hab den denkfehler beseitigt.
> > > jetzt nur in Worte fassen:
> > >
> > > 1. Sei cone S = lin S.
> > > Sei x [mm]\in[/mm] S [mm]\Rightarrow[/mm] -x [mm]\in[/mm] lin S [mm]\Rightarrow[/mm]
> -x
> > [mm]\in[/mm]
> > > cone S (Vorrausetzung cone S = lin S).
> > >
> > > für alle x [mm]\in[/mm] S gilt
> > Achtung, das nachfolgende muss doch erst noch bewiesen
> > werden.
>
> Das war nur zum Verständnis. Wollte erst vrstehen warum es
> so ist bevor ich es versuche.
> >
> > > -x [mm]\in cone(S\setminus\{x\}),[/mm] -x
> > > muss aus [mm]cone(S\setminus\{x\}),[/mm] da ja in der konischen
> > > Hülle nur positve lin.Komb enthalten sind und wäre -x aus
> > > cone S, mit [mm]x\in[/mm] S, wäre ja auch x [mm]\in[/mm] cone S was nicht
> > > funkioniert aufgrund der Eigenschaft [mm]\lambda \ge[/mm] 0.
> > >
> > Das ist unklar.
> >
> > Du hast nun [mm]-x\in cone(S)[/mm] eingesehen - übrigens: wie genau
> > [mm]S[/mm] aussieht, ob endlich etc. ist unerheblich.
> okay.
>
> Bei b) habe
> > ich Dich aufgefordert [mm]-x[/mm] als Linearkombination von
> > Elementen aus [mm]S[/mm] mit nicht negativen Koeffizienten
> > darzustellen; denn nachdem [mm]-x\in cone(S)[/mm] gezeigt ist, ist
> > so eine Darstellung zweifelsfrei möglich.
> >
> > Also [mm]-x= \sum_{s\in S} \lambda_{s} s[/mm], [mm]\lambda_{s}\geq 0[/mm]. In
> > dieser Summe taucht wegen [mm]x\in S[/mm] auch der Summand
> > [mm]\lambda_{x}x[/mm] auf. Führe nun den unter c) beschriebenen
> > Schritt aus.
>
>
> -x= [mm]\sum_{s\in S} \lambda_{s}s[/mm] mit [mm]\lambda_{s}\ge0[/mm]
>
> [mm]\gdw-x[/mm] = [mm]\sum_{s\in S\setminus\{x\}} \lambda_{s}s+\lambda_xx[/mm]
>
> [mm]\gdw-x-\lambda_x x=\underbrace {\sum_{s\in S\setminus\{x\}} \lambda_{s}s }_{=cone(S\setminus\{x\})}[/mm]
>
Nein, es müsste [mm] $\in cone(S\setminus\{x\})$, [/mm] aber nicht $= [mm] cone(S\setminus\{x\})$ [/mm] heissen.
> [mm]\gdw-x(\lambda_x[/mm] +1) = [mm]cone(S\setminus\{x\})[/mm]
>
Ebenso hier. Ausserdem: wieso hörst Du an dieser Stelle auf? Willst Du etwa [mm] $-x(\lambda_x +1)\in cone(S\setminus\{x\})$ [/mm] zeigen?
Folge doch dem Beweisgang wie ich ihn vorgeschlagen habe.
> [mm]\Rightarrow[/mm] lin S = cone S [mm]\Rightarrow[/mm] für alle x [mm]\in[/mm] S :
> -x [mm]\in cone(S\setminus\{x\})[/mm]
Siehe oben.
>
> das Versuche ich jetzt mal eben und teile meine ergebnise
> gleich mit.
>
> ist es denn bis hier hin ok?
Mir ist das zu nachlässig aufgeschrieben und auch genau genommen nicht das, was zu zeigen war.
>
>
> so jetzt die Rückrichtung :
> für alle x [mm]\in[/mm] S : -x [mm]\in cone(S\setminus\{x\}) \Rightarrow[/mm]
> lin S = cone S
|
|
|
|
