2 Beweise zu Konvexen Mengen

Neue Frage »

SharkyShark Auf diesen Beitrag antworten »
2 Beweise zu Konvexen Mengen
Meine Frage:
Hallo zusammen - ich muss zwei Beweise zu konvexen Mengen führen, habe aber Probleme damit und wollte mich an Euch wenden.
Vorher aber folgendes:
sei K eine Teilmenge des R^n. K ist Konvex. und ein Punkt p aus K heißt Extremalpunkt, wenn er nicht innerer Punkt irgendeiner Strecke ist, er ist also ein Eckpunkt. K ist nebenbei ein konvexes Polyeder.

Nun aber zum ersten Beweis:
es soll gezeigt werden, p aus K ist genau dann ein Extremalpunkt, WENN K\{p} konvex ist.


Zu Beweis 2:
vorab: S=K heißt K-Simplex, wenn es affin unabhängige Punkte P0 bis Pk im R^n gibt, so dass S=kon(P0,..,Pk)

damit ist auch jeder Punkt in S eindeutig als Konvexkombination dieser Punkte beschreibar.

Nun aber zu dem was in Beweis 2 gelöst werden soll:
In einem kK-Simplex (also S) kon(P0,...,Pk) sind alle Punkte P0,...,Pk Ecken.


Könnt ihr mir da weiter helfen?

Meine Ideen:
zu Beweis 1 habe ich erstmal die Frage: wenn ich einen Punkt aus der menge des Konvexen Polyeders weg lasse, dann verschwinden die Verbindungsgeraden der anderen Ecken zu dieser Ecke ja nicht, sondern nur der eine Punkt p um den es in Beweis 1 geht.
Das heißt ja, dass wir dann eine Lücke haben?
Wenn also nur der eine Punkt fehlt, dann sinda lle anderen noch da, und damit bleibt der Polyeder doch eigentlich konveex, da ich mit alle anderen Punkt, die ja Innerhalb des Polyeders liegen immernoch mit anderen Punkten aus dem polyeder verbinden kann und die Verbindungsstrecke immernoch im Polyeder liegt.
Ist da so richtig vorgestellt?

Zu Beweis 2 - da hatte ich mal so eine Idee einen der Punkte der Pi als Konvexkombination der anderen Pi darzustellen, bin aber nicht ganz zu rande gekommen.
Reksilat Auf diesen Beitrag antworten »
RE: 2 Beweise zu Konvexen Mengen
Hi Sharky,

Zu 1): Deine Überlegungen überzeugen mich noch nicht. Wo genau verwendest Du denn, dass der entfernte Punkt ein Eckpunkt ist? Wenn ich einen beliebigen anderen Punkt entferne, ist die Menge ja nicht mehr konvex.
Für einen Beweis solltest Du außerdem formaler arbeiten.
Die eine Richtung ist auch wirklich schnell erledigt. Sei K\{p} konvex und nun nimm an, dass p keine Ecke sei. Dann gibt es nach Definition eine Strecke in K\{p}, auf der p ein innerer Punkt ist. Führe das zum Widerspruch.

Zu 2): Nein, nach der Definition des K-Simplex lässt sich keiner der als Konvexkombination der anderen Punkte darstellen.
Nimm doch einfach mal an, dass (oBdA) keine Ecke ist. Dann ist es ein innerer Punkt irgendeiner Strecke, nennen wir sie . Also gibt es mit .

Nach Definition des K-Simplex lassen sich aber A und B als Konvexkombination der schreiben. Damit kann man zeigen, dass sein muss.

Gruß,
Reksilat.
SharkyShark Auf diesen Beitrag antworten »

So - hallo nochmal, hatte die Woche viel zu tun und konnte mich nicht groß um die Sachen hier weiter kümmern.

Die eine Richtung des Beweises 1 ist klar. K\{p} ist konvex ==> P muss ein Eckpunkt gewesen sein, ansonsten währe er Punkt innerhalb einer Strecke von Punkten aus K und wen der wegfallen würde dann wäre K nicht mehr konvex.

Für die andere Richtung hab ich mir folgendes überlegt:

Annahme: K ist konvex, P aus K ist Extremalpunkt.
das heißt ja, dass alle Strecken aus K, auf denen P liegt P als einen der beiden Endpunkte haben müssen, da P ja nicht innerer Punkt einer Strecke sein kann auf Grund der Eigenschaft, dass er ein Eckpunkt / Extremalpunkt ist.
Betrachte ich nun K\{p} besitzt K weiterhin alle Punkte r, die innerer Punkt einer beliebigen Strecke zwier Punkte sind, die in K enthalten sind. Damit ist dann die Bedingung der Konvexität bzgl. K\{p} erfüllt und auch die andere Richtung gezeigt.

Mit dem Beweis 2 werde ich mich Heute noch beschäftigen

MFG - Sharky
Reksilat Auf diesen Beitrag antworten »

Sieht bisher ganz gut aus. smile
SharkyShark Auf diesen Beitrag antworten »

Jut - damit währe Beweis 1 dann abgehakt.

Nun habe ich mir folgendes zu Beweis zwei überlegt:
In einem S-Simplex sind laut Definition P0 bis Pk Affin unabhängig
und S=kon(P0,...,Pk)

Annahme ich habe ein Punkt P aus S, der eine Ecke sein soll, aber nicht aus P0,..,Pk stammt, dann weis ich ja, dass sich P als Konvexkombination der Lambda0P0 +..+ LambdakPk schreiben lässt. OBdA brauche ich mind zwei lambdai, die größer null sind, um eine Konvexkombination zu bauen, bei der ein anderer Punkt als einer der Pi von kon(P0,...,Pk) heraus kommt.

seien nun Lambda0 und Lambda1 diese beiden die ich brauche so dass P=Lambda0P0 + Lambda1P1.

da Lambda0+lambda1 =1 sind wegen der Eigenschaft der konvexkombination muss P auf der Strecke von P0 bis P1 liegen. (Strecke zwischen zwei Punkten q und r ist ja definiert als lambda0*q + lambda1*r wobei lambda0+lambda1=1 und die beiden lambdas größer gleich 0).

Nun ist P also innerer Punkt einer Strecke, nämlich der von P0 und P1, das ist aber ein Widerspruch zur Voraussetzung, dass P ein Eckpunkt ist. Damit folgt, dass alle Pi von S=konv(P0,...,Pk) Ecken sein müssen.

MFG - Sharky
Reksilat Auf diesen Beitrag antworten »

Was sollst Du denn nun zeigen? Du versuchst hier zu beweisen, dass es keine Ecken gibt, die nicht in der Menge liegen. Oben steht aber was anderes.
Oder sollte da "...sind die Punkte genau die Ecken" stehen?
Dann wäre das bisher nur eine Richtung.

Zitat:
OBdA brauche ich mind zwei lambdai

Nein! Nicht oBdA! Wenn Der Punkt P nicht aus der angegebenen Menge stammt, dann sind immer mindestens zwei ungleich Null.
Die Annahme, dass der Punkt sich als Konvexkombination von genau zwei darstellen lässt, ist dagegen eine unzulässige Einschränkung. Die Darstellung als Konvexkombination der ist eindeutig und wenn sich mit drei oder mehr darstellen lässt, so kannst Du das nicht auf den Fall zurückführen.

btw.: So was wie "lambdai" finde ich sehr schwer lesbar. In meiner Signatur findest Du einen Link zum Formelnschreiben.

Gruß,
Reksilat.
 
 
SharkyShark Auf diesen Beitrag antworten »

hmm ok Mist - nein ich soll laut Aufgabe zeigen:
In einem k-Simplex kon(P0,...,Pk) sind alle Punkte P0,...,Pk Ecken.

Ich nehme mal an deinen Hinweis aus deiner ersten Antwort

Zu 2): Nein, nach der Definition des K-Simplex lässt sich keiner der als Konvexkombination der anderen Punkte darstellen.
Nimm doch einfach mal an, dass (oBdA) keine Ecke ist. Dann ist es ein innerer Punkt irgendeiner Strecke, nennen wir sie . Also gibt es mit .
(latex codes von dir).....
Nach Definition des K-Simplex lassen sich aber A und B als Konvexkombination der schreiben. Damit kann man zeigen, dass sein muss.

usw.

Also ich versuche mal das, das ist ja schon praktisch die Beweisskizze und ich muss das nur einmal sauber aufschreiben.
SharkyShark Auf diesen Beitrag antworten »

So ich habe deine Beweisskizze nun Verfolgt und in Kurzform folgendes:
S=kon(P0,...,Pk) wobei die Pi affin unabhängig sind.

zzu zeigen, alle Pi sind Ecken
Annahme: OBdA sei P0 nun keine Ecke
==> P0 ist Punkt einer inneren Strecke
also ist P0=y*R +(1-y)*Q

R und Q lassen sich aber als konvexkombination der Pi schreiben - also haben wir:

R=n0*P0+...+nk*Pk
Q=m0*P0+...+mk*Pk

also gilt
P0=y*(n0*P0+...+nk*Pk) + (1-y)*(m0*P0+...+mk*Pk)
dann ist also
P0=a0*P0+...+ak*Pk + b0*P0+...+bk*Pk
(1-a0-b0)P0=a1*P1+...+ak*Pk + b1*P1+...+bk*Pk
P0=c1*P1+,,,+ck*Pk

damit ist also P0 eine Affinkombination der aneren P1,..,Pk, was ein Wiederspruch zur Affinen unabhängigkeit dieser Punkte ist, also ist P0 eine Ecke, analog geht man mit allen anderen punkten vor und hat so gezeigt, dass alle Pi ecken sein müssen.
Reksilat Auf diesen Beitrag antworten »

Sieht gut aus, nur der Widerspruch ist noch nicht ganz ausgereift.
Aus der Gleichung:

folgt erstmal nur (aufgrund der affinen Unabhängigkeit), dass alle Koeffizienten 0 sein müssen. Also:


...

Darin musst Du nun den Widerspruch finden.
SharkyShark Auf diesen Beitrag antworten »

die Koeffizienten können nicht alle gleich Null sein, da es sich um eine Konvexkombination in unserem S=konv(P0,...,Pk) handelt, und bei Konvexkombinationen ist die Summe der Koeffizienten immer gleich 1.
Reksilat Auf diesen Beitrag antworten »

Die Koeffizienten können mit Sicherheit alle 0 sein und sind es auch. Du hast doch auf der rechten Seite auch keinen Punkt, sondern nur die Null da stehen.

Alternativ könntest Du auch über die Gleichung
P0=a0*P0+...+ak*Pk + b0*P0+...+bk*Pk
argumentieren.
Dann steht dort eben eine Konvexkombination von und aufgrund der Eindeutigkeit sind eben und alle anderen . Ist das gleiche wie oben.

Bei Deiner Argumentation versuchst Du letztlich, die Gleichung zum Widerspruch zu bringen und das kann nicht funktionieren. Augenzwinkern

Gruß,
Reksilat.
SharkyShark Auf diesen Beitrag antworten »

Also momentan stehe ich auf dem Schlauch.
Zitat von dir:
Sieht gut aus, nur der Widerspruch ist noch nicht ganz ausgereift.
Aus der Gleichung:

folgt erstmal nur (aufgrund der affinen Unabhängigkeit), dass alle Koeffizienten 0 sein müssen. Also:


Hast du da noch einen Tip wie du das genau meinst?
Reksilat Auf diesen Beitrag antworten »

Wir können die Gleichung doch auch schreiben als:

Und diese Gleichung kann nach Definition der affinen Unabhängigkeit nur dann erfüllt sein, wenn alle Koeffizienten vor den gleich 0 sind.

Dass wir auf diese Weise tatsächlich eine Lösung der Gleichung haben, sollte klar sein. Einen Widerspruch kann man also noch nicht direkt ablesen, sondern muss erst die Information, dass die Koeffizienten 0 sind, zum Widerspruch führen.
SharkyShark Auf diesen Beitrag antworten »

Ah - ok.
Also dass man bei linear / affin unabhängigen Vektoren / Punkten die Null nur dann erzeugen kann, wenn alle Koeffizienten gleich Null sind ist klar (so ist ja auch die Definition der linearen / afinen Unabhängigkeit).

Ich dachte in meinem vorherigen Beitrag folgendes:
Ich wollte mich hier bei dieser Gleichung, die du niedergeschrieben / umgeschrieben hast noch zusätzlich auf die Tatsache beziehen, dass wir bei unserem Beweis ja ein k-Simplex betrachten, dass aus dieser Affin Kombination entstehen soll. Damit das klappt, unterliegt für unser k-Simplex unsere Affinkombination aber den Bedingungen einer Konvexkombination. Und in einer Konvexkombination muss die Summe der Koeffizienten, die vor den Punkten stehen, ja eins ergeben. Damit könnte ich im Fall des k-Simplex in dem ich diese Gleichung als Konvexkombination betrachte / betrachten muss ja die Null nicht auf diese Weise erzeugen, da ich nicht alle koeffizienten Null setzen darf, die Punkte aber trotzdem weiterhin affin unabhängig sind.

Oder habe ich jetzt nur Müll geredet ?
Reksilat Auf diesen Beitrag antworten »

In Deiner Gleichung taucht ja nicht unbedingt ein Punkt aus dem Simplex auf. Da steht schließlich nicht , sondern und das liegt eben nicht unbedingt im Simplex, genausowenig wie die 0. - Deshalb kann man diese Argumentation hier nicht verwenden.

Außerdem hast Du ja nur eine affine Kombination dort stehen und diese ist im allgemeinen keine Konvexkombination. Die einzige Konvexkombination, die ich in dieser Gleichung sehe, ist diese:
Zitat:
P_0=(a_0+b_0)P_0+...+(a_k+b_k)P_k

Und dafür kann man eben eine Lösung angeben.

Letztlich habe ich Dir jetzt mehrfach gesagt, dass die obige Gleichung eine Lösung besitzt. Du wirst daraus also nicht direkt einen Widerspruch konstruieren können, sondern musst eben verstehen, warum es nur diese eine Lösung gibt und was aus dieser Lösung dann folgt.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »