matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

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
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenOperations Researchkonische bwz lin. Hülle
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
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.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]