www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Operations Research" - konische bwz lin. Hülle
konische bwz lin. Hülle < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Operations Research"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

konische bwz lin. Hülle: Idee
Status: (Frage) beantwortet Status 
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!

        
Bezug
konische bwz lin. Hülle: Antwort
Status: (Antwort) fertig Status 
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.



Bezug
                
Bezug
konische bwz lin. Hülle: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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.

Bezug
                        
Bezug
konische bwz lin. Hülle: Antwort
Status: (Antwort) fertig Status 
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.

Bezug
                                
Bezug
konische bwz lin. Hülle: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

Bezug
                                        
Bezug
konische bwz lin. Hülle: Antwort
Status: (Antwort) fertig Status 
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


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Operations Research"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]