Approximation durch gerade mit minimierung der 1 bzw Unendlich Norm

21.05.2013, 19:14

NoxMortem

Approximation durch gerade mit minimierung der 1 bzw Unendlich Norm

Meine Frage:
Hallo liebes Matheboard!

Ich soll durch die Punkte (0,0),(1,1) sowie (0.5,0.25) eine Gerade legen so, dass einmal die 1-Norm minimal ist und einmal die Unendlich-Norm.

Meine Ideen:
Die Gerade anhand der euklidischen Norm (Methode der kleinsten quadrate) habe ich gelöst, die war aber auch nicht wirklich gefragt.

Für die Unendlich-Norm habe ich leider überhaupt keinen Ansatz.

Für die 1-Norm dachte ich mit Fallunterscheidung sei evtl. gemeint mir die Beträge anzusehen und daraus die 8 Fälle zu vereinfachen.

Wenn $\begin{eqnarray*} u=b,v=a+b-1,w=0.5a+b-0.25 \end{eqnarray*}$
Dann habe ich die Fälle
$\begin{eqnarray*} 1, u<0, v<0, w<0 \end{eqnarray*}$
$\begin{eqnarray*} 2, u<0, v<0, w>=0 \end{eqnarray*}$
$\begin{eqnarray*} 3, u<0, v>=0, w<0 \end{eqnarray*}$
$\begin{eqnarray*} 4, u<0, v>=0, w>=0 \end{eqnarray*}$
$\begin{eqnarray*} 5, u>=0, v<0, w<0 \end{eqnarray*}$
$\begin{eqnarray*} 6, u>=0, v<0, w>=0 \end{eqnarray*}$
$\begin{eqnarray*} 7, u>=0, v>=0, w<0 \end{eqnarray*}$
$\begin{eqnarray*} 8, u>=0, v>=0, w>=0 \end{eqnarray*}$

Da $\begin{eqnarray*} |x|<0=-1*x \end{eqnarray*}$ erhalte ich somit 8 Ebenengleichungen
$\begin{eqnarray*} z_1=-3b-1.5a+1.25 \end{eqnarray*}$
$\begin{eqnarray*} z_2=-b-0.5a+0.75 \end{eqnarray*}$
$\begin{eqnarray*} z_3=-b+0.5a-0.75 \end{eqnarray*}$
$\begin{eqnarray*} z_4=b+1.5a-1.25 \end{eqnarray*}$
$\begin{eqnarray*} z_5=-b-1.5a+1.25 \end{eqnarray*}$
$\begin{eqnarray*} z_6=b-0.5a+0.75 \end{eqnarray*}$
$\begin{eqnarray*} z_7=b+0.5a-0.75 \end{eqnarray*}$
$\begin{eqnarray*} z_8=3b+1.5a-1.25 \end{eqnarray*}$

Für jede dieser 8 Ebenengleichung muss natürlich die jeweilige Nebenbedingung gelten durch welche ich die Beträge vereinfacht habe.

Jetzt habe ich halt die folgenden 2 Fragen:
1) Macht mein Vorgehen irgendwie auch nur Sinn?
2) Wie finde ich nun jene Parameter a,b für welche die ursprüngliche Funktion minimal ist.

Ein Minimum/Extrema einer Funktion finde ich ja normal durch partielles ableiten, nullsetzen der ableitungen und lösen der Gleichungssysteme lösen (2 Variablen, 2 Gleichungen). Nur erhalte ich jetzt für die erste Ableitung jeweils Konstanten, im Falle der ersten Ebene bspw:

$\begin{eqnarray*} \frac{d}{da} z_1 = -1.5 \end{eqnarray*}$
$\begin{eqnarray*} \frac{d}{db} z_1 = -3 \end{eqnarray*}$

Damit weiß ich irgendwie nichts anzufangen, ich habe ja auch keinen "minimalen Punkt" auf einer Ebene.

Vielen Dank schon im Vorraus!

22.05.2013, 01:38

frank09

Auf diesen Beitrag antworten »

RE: Approximation durch gerade mit minimierung der 1 bzw Unendlich Norm
Wenn du a und b als x und y auffasst, entsprechen die Koordinaten der Punkte eines Bereichs den Bedingungen. So erfüllen z.B. alle Punkte unterhalb der Geraden

x+y-1=0 bzw. y=-x+1

die Bedingung x+y-1<0

Alle Bereiche entsprechen deinen Fällen 1-8 (7 geht nicht)

Deine Ebenengleichungen sind Geraden.
Alle Punkte auf diesen erfüllen die 1-Norm optimal mit Null.

z1: -3y-1,5x+1,25=0

Nun gehen sie allerdings nicht durch "ihren Bereich", d.h. es sind Punkte aus Bereich 1 zu finden, die möglichst nah an z1 liegen. Die Koordinaten werden dann in z1 eingesetzt und so wird die Norm ermittelt. Genauso verfährt man mit z2-z8.

26.05.2013, 19:25

NoxMortem

Auf diesen Beitrag antworten »

Vielen Dank schonmal!

Ich habe es leider nicht ganz verstanden. Ok, dass es Geraden sind ist eigentlich klar, weil es ja die implizite Darstellung der einzelnen Komponenten des Vektors ist. Eindeutig ein Zeichen meines Unverständnis der Thematik.

Gesucht ist ja eine Approximationsgerade welche durch die Punkte (0,0), (1,1) sowie (0.5,0.25) geht und für DIESE soll die 1Norm bzw die Unendlich-Norm minimal sein.

Aber stimmt meine Idee mit den Fallunterscheidungen für die 3 Beträge überhaupt?

Was meinst du mit "die Bereiche/ihre Bereiche"?

Wenn ich mir die Punkte ansehe kann die 1Norm doch gar nicht 0 sein. Es gibt ja keine Gerade die wirklich durch die 3 Punkte geht, daher handelt es sich ja um ein Approximationsproblem.

Nun gehen sie allerdings nicht durch "ihren Bereich", d.h. es sind Punkte aus Bereich 1 zu finden, die möglichst nah an z1 liegen. Die Koordinaten werden dann in z1 eingesetzt und so wird die Norm ermittelt. Genauso verfährt man mit z2-z8.

Was heißt sie gehen nicht durch ihren Bereich? Für jede der Geraden muss die Bedingung doch erfüllt sein, so habe ich sie ja auch aufgestellt?

Ich bin extrem dankbar für deine Hilfe aber leider komme ich damit kein Stück weiter? Langsam glaube ich nämlich dass die Fallunterscheidung die ich gemacht habe schon Schwachsinn war, denn dann habe ich zwar 8 Geraden aber jede davon ist ja nur unter gewissen Bedingungen gültig.

Offensichtlich gibt es eine Lösung, denn Wolfram Alpha findet eine nur habe ich keine Ahnung wie man auf diese kommt unglücklich

http://www.wolframalpha.com/input/?i=min...%2Bb-0.25%29%29

liebe Grüße
Nox

27.05.2013, 02:24

frank09

Auf diesen Beitrag antworten »

Die 1-Norm aller Punkte (a|b) bzw. (x|y), die deinem Fall 1 genügen, errechnet sich doch wie folgt:

$\begin{eqnarray*} N_1=-1,5x-3y+1,25 \end{eqnarray*}$

Wenn ich das als Skalarprodukt des Punktes mit dem Normalenvektor der Gerade
$\begin{eqnarray*} z1: -1,5x-3y+1,25=0 \end{eqnarray*}$ auffasse, wird deutlich, dass die Norm umso kleiner ist, je näher der Punkt an der Geraden liegt.

Gleichzeitig liegen alle Punkte, die zu Fall 1 gehören, in dem Gebiet

$\begin{eqnarray*} \left\{(x|y)| y\leq 0 \wedge y\leq -x+1\wedge y\leq -0,5x+0,25 \right\} \end{eqnarray*}$
Dieses Gebiet unten links habe ich zuvor auf der Grafik mit "1" bezeichnet.

Die Norm für alle Punkte, die Fall 8 genügen, ist
$\begin{eqnarray*} N_8=1,5x+3y-1,25 \end{eqnarray*}$
Die zugehörige Gerade ist mit z1 identisch:
$\begin{eqnarray*} z8: 1,5x+3y-1,25=0 \Leftrightarrow -1,5x-3y+1,25=0 (= z1) \end{eqnarray*}$

Der Punkt aus Gebiet 8, der dieser Gerade am nächsten ist, ist
$\begin{eqnarray*} P_{2/4/6/8}(1|0) \end{eqnarray*}$
Ein Punkt aus Gebiet 1, der dieser Gerade am nächsten ist, ist
$\begin{eqnarray*} P_{1/5}(0,5|0) \end{eqnarray*}$ .

Weil zuerst genannter offensichtlich näher dran ist, kommt als Punkt mit den "optimierten" Koordinaten aus Gebiet 1 der zweite nicht mehr infrage. Auch als bester aus Gebiet 5 hat er eine schlechtere Norm.

Der gesuchte Punkt kann/muss ein Schnittpunkt der Gebietsgrenzen sein, je nachdem, ob diese parallel zu den z-Geraden verlaufen oder nicht.
Der einzige weitere Punkt $\begin{eqnarray*} P_3 \end{eqnarray*}$ "unterliegt" ebenfalls $\begin{eqnarray*} P_{2/4/6/8} \end{eqnarray*}$ , der näher an z3/6 liegt. Damit ist die Lösung klar:
x=a=1
y=b=0

27.05.2013, 14:55

NoxMortem

Auf diesen Beitrag antworten »

Erneut vielen Dank frank09!

Danke für die ausführliche Erklärung. Es scheint als würde ich langsam vorankommen und nun langsam merke ich auch warum ich die initiale Antwort nicht verstanden habe.

Ich habe mittlerweile auch den Hinweis bekommen, dass das Minimum an einem Punkt sein muss an der sich 2 Gebietsgrenzen gleichen. Dies sind genau die 3 von dir eingezeichneten Punkte. Wie ich auf diese Punkte komme ist mir nun klar nur:

Warum muss die Lösung genau der Schnittpunkt von 2 Bereichsgrenzen sein?

Wenn du vom Abstand von einen Punkt zur Geraden sprichst dann meinst du Abstand des Schnittpunktes von der Geraden z1 bzw z8? Weil P3 sieht aus als wäre er gleich weit von z1/z8 entfernt wie auch P1? Die Bereichsgrenze 0.5a+b-0.25=0 verläuft ja parallel zu z1/z8?

Für z1 wurde angenommen dass 0.5a+b-0.25<0 ist und so der Betrag aufgelöst. Der Punkt (1,0) (x,y) erfüllt diese Bedingung aber nicht. Sollte dies nicht ein Problem sein?

Der gesuchte Punkt kann/muss ein Schnittpunkt der Gebietsgrenzen sein, je nachdem, ob diese parallel zu den z-Geraden verlaufen oder nicht.
Dies ist ja genau für z1 sowie die Bereichsgrenze 0.5a+b-0.25=0 der Fall. Die beiden sind ja paralell.

Müsste ich nicht auch die anderen Geraden Z2-7 betrachten oder werden diese ignoriert weil sie (wie man auf der grafik sieht) offensichtlich weiter von den 3 Schnittpunkten entfernt sind?

Es tut mir echt leid falls ich mich ganz besonders dämlich anstelle smile

Lösungen habe ich ja mittlerweile durch dich sowie durch LP mit Matlab und eben die Wolframalpha Lösung - nur habe ich noch keine richtig verstanden und darauf kommt es mir aber an smile

liebe Grüße

27.05.2013, 18:28

NoxMortem

Auf diesen Beitrag antworten »

Ich darf den obrigen Beitrag nicht mehr editieren weil die 15 Minuten vergangen sind.

Mir ist klar dass man nun durch simples Errechnen der Lösung und anschließend rückeinsetzen das Minimum findet weil die anderen Punkte eine Norm von 0.5 haben der richtige aber von 0.25

Kurz, die einzige Frage die ich noch geklärt bräuchte um es zu verstehen ist:

Warum bekomme ich die Lösung genau durch die Schnittpunkte der Bereichsgrenzen?

Vielen Dank Frank09! Du warst eine grandiose Hilfe. Habe das Forum jetzt sicher schon 2 Jahre oder so passiv benutzt und muss echt sagen, tolle Leute hier!

27.05.2013, 23:22

frank09

Auf diesen Beitrag antworten »

Wenn du Bereiche hast, die durch Geraden berenzt sind und eine Gerade, die nicht durch die Gebiete läuft, gibt es doch nur zwei Möglichkeiten:

1) Die Grenze, die der Geraden am nächsten liegt, ist nicht parallel zu ihr.
Es gibt deshalb genau einen Punkt P1 auf dieser Grenze, der der Geraden am nächsten ist, weil der Abstand bis zu einer "Ecke" (=Schnittpunkt zweier Grenzen) immer weiter abnimmt. Gäbe es diese Ecke nicht, würde die Grenze doch die Gerade schneiden.

2) Die Grenze, die der Geraden am nächsten liegt, ist parallel zu ihr.
Dann gäbe es zwar keinen eindeutigen Punkt (z.B. P2), aber dieser Punkt kann auch so gewählt werden (P3), dass auch dieser ein Eckpunkt ist.

In beiden Fällen reicht es also aus, nur die Eckpunkte zu untersuchen.

Zitat:

Weil P3 sieht aus als wäre er gleich weit von z1/z8 entfernt wie auch P1?

P3 liegt im Gebiet 3. Dessen Norm wird durch den Abstand von z3 bestimmt. Es werden nur die Abstände zu den entsprechenden Geraden untersucht, also P1/5 zu z1 und z5, P2/4/6/8 (liegt zugleich in 4 Gebieten) zu z2,z4,z6 und z8.

Die Maximumsnorm erfüllt übrigens der Punkt $\begin{eqnarray*} P(x_m|y_m) \end{eqnarray*}$ , dessen Abstand zu den drei Geraden y=0; x+y-1=0; 0,5x+y-0,25=0 ungefähr gleich ist.

Es muss gelten
$\begin{eqnarray*} |y_m|=|x_m+y_m-1| =|0,5x_m+y_m-0,25| \end{eqnarray*}$ .
Überleg mal warum und in welchem Gebiet der Punkt wohl liegt.

29.05.2013, 19:54

NoxMortem

Auf diesen Beitrag antworten »

Wollte nur nochmal danke sagen!
Hätte das beispiel sonst wohl nicht verstanden!

Neue Frage »

Antworten »

Approximation durch gerade mit minimierung der 1 bzw Unendlich Norm

Verwandte Themen