Minimaler Geradenabstand < Nichtlineare Gleich. < Numerik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Es existieren drei Geraden [mm] f_i(t_i) [/mm] = [mm] a_i t_i [/mm] + [mm] b_i. [/mm] Ziel ist es, sämtliche [mm] t_i [/mm] zu finden, die den Abstand zwischen den Geraden minimieren:
[mm] min_{t_1,t_2,t_3} \left(\left| f_1 - f_2 \right|^2 + \left| f_1 - f_3 \right|^2 + \left| f_2 - f_3 \right|^2\right).
[/mm]
Nebenbedingungen sind [mm] t_1 \in [u_1, o_1], t_2 \in [u_2, o_2] [/mm] und [mm] t_3 \in [u_3, o_3] [/mm] |
Ohne die Nebenbedingungen würde es ja unendlich viele Lösungen geben, da die Geraden den kompletten reellen Bereich abbilden. Hat jemand eine Idee, wie man das Optimierungsproblem mit den NB lösen kann? Ich habe es mit den Karush–Kuhn–Tucker Bedingungen versucht, aber das scheint nicht zu klappen. In der Regel wird das Minimum innerhalb der Grenzen liegen und die Multiplier werden $0$. Damit erhalte ich ein Lösungssystem der Form $At=b$. Das kann ich nach $t$ auflösen. Das liefert mir allerdings dann aufgrund der unbeschränkten Lösungsmenge irgendwelche Werte, die in der Regel außerhalb der NB liegen.
Ich hoffe ich habe mich klar genug ausgedrückt. Ich wäre jedenfalls über einen Tipp dankbar, wie ich die Lösung dieses Problems angehen könnte.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:03 Mi 26.03.2014 | | Autor: | leduart |
Hallo
a) sind die [mm] a_i,b:i [/mm] Vektoren in [mm] R^2 [/mm] oder [mm] R^3, [/mm] dabei die [mm] a_i, [/mm] b:i fest?
b) du meinst wohl die Summe der Abstände soll minimal sein?
c) warum es unendlich viele Lösungen geben soll, sehe ich nicht.
d) du betrachtest die geraden ur innerhalb eines Quaders, der das Bereich begrent, suchst also nur nach Abstanden innerhalb des Quaders, und auf dem Rand.
Gruss leduart
|
|
|
| |
|
a) [mm] a_i [/mm] und [mm] b_i [/mm] sind beliebig, aber fest. Außerdem sind es reelle Zahlen und keine Vektoren. Für Vektoren ist mein System auch ohne Nebenbedingungen lösbar (weil die Geraden nicht den ganzen Wertebereich einnehmen).
b) Ja.
c) Nur wenn man das System ohne Nebenbedingungen betrachtet. Dann gibt es nämlich für jeden beliebigen Wert [mm] y_i [/mm] = [mm] a_i t_i [/mm] + [mm] b_i [/mm] drei Werte [mm] t_{1,2,3}, [/mm] sodass die Summe der Abstände 0 wird. Aus diesem Grund habe ich die Nebenbedingungen eingeführt.
d) Genau. Siehe c)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:22 Do 27.03.2014 | | Autor: | leduart |
Hallo
du hast 3 Geraden im [mm] R^2, [/mm] die sind
a) alle parallel, dann ist die Abstandssumme konstant, also sicher nicht 0
b) 2 sind parallel haben also festen Abstand, die dritte schneidet, hat also zu beiden den Minimalabstand 0
c) alle 3 nicht parallel, d.h. [mm] a1\not= a2\not=a3 [/mm] Summe der Abstände 0
Oder ich verstehe dein Problem überhaupt nicht.
Gruß leduart
|
|
|
| |
|
Ja, im Falle c) ist der Abstand 0. Das Problem ist aber, dass ich in dem Quader der Nebenbedingungen den geringsten Abstand finden möchte. Und der ist nicht unbedingt 0. Für diese Problemstellung suche ich einen Ansatz.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:45 Do 27.03.2014 | | Autor: | chrisno |
Es mangelt sicher an der Eleganz, aber so kommst Du meiner Meinung nach zum Ziel:
1. Minimum ohne Randbedingungen suchen, liegt dies innerhalb der Grenzen bist Du fertig
sonst wird das Extremum an der Grenze angenommen
2. Für alle 6 Werte der Intervallgrenzen einzeln durchführen:
diesen einen Wert festlegen und dann den Extremwert suchen.
2.1 liegt dieser außerhalb der Grenzen -> verwerfen, liegt dieser innerhalb der Grenzen -> merken
3. Wie 2 bloß immer zwei Werte festlegen und für alle möglichen 12 Paare durchführen
4. Nun musst Du noch für alle acht Tripel die Werte bestimmen und merken.
5. Aus diesen, maximal 26 gemerkten Werten den kleinsten heraussuchen.
|
|
|
| |
|
Das Problem ist auch hier wieder das Minimum ohne Randbedingungen. Wenn die drei Geraden nicht parallel sind, ist die Summe der minimalen Abstände 0 und es gibt beliebig viele [mm] t_1, t_2, t_3, [/mm] mit denen dieser Abstand erreicht werden kann. Ich hätte gerne eine Möglichkeit, nach dem minimalen Wert innerhalb des Quaders zu suchen. Dazu fällt mir jedoch kein Ansatz ein.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:47 Do 27.03.2014 | | Autor: | chrisno |
> Das Problem ist auch hier wieder das Minimum ohne
> Randbedingungen. Wenn die drei Geraden nicht parallel sind,
> ist die Summe der minimalen Abstände 0 und es gibt
> beliebig viele [mm]t_1, t_2, t_3,[/mm] mit denen dieser Abstand
> erreicht werden kann.
Bitte gib ein konkretes Beispiel für diesen Fall an. Das würde meinem Verständnis sehr weiterhelfen.
> Ich hätte gerne eine Möglichkeit,
> nach dem minimalen Wert innerhalb des Quaders zu suchen.
> Dazu fällt mir jedoch kein Ansatz ein.
|
|
|
| |
|
Nehmen wir als Beispiel mal nur zwei Geraden/Funktionen an:
[mm] $f_1(t_1) [/mm] = [mm] t_1$
[/mm]
[mm] $f_2(t_2) [/mm] = [mm] -\frac{1}{2}t_2 [/mm] + 2$
Beide Funktionen nehmen Werte aus dem kompletten Bereich der reellen Zahlen an. Es gibt daher unendlich viele Kombinationen von [mm] t_1 [/mm] und [mm] t_2, [/mm] für die [mm] $f_1(t_1) [/mm] - [mm] f_2(t_2) [/mm] = 0$ gilt.
Beispiel 1:
[mm] $f_1(t_1) [/mm] = 1 [mm] \arrow \Rightarrow t_1 [/mm] = 1$
[mm] $-\frac{1}{2}t_2 [/mm] + 2 = 1 [mm] \Rightarrow t_2 [/mm] = 2$
Beispiel 2:
[mm] $f_1(t_1) [/mm] = 0 [mm] \arrow \Rightarrow t_1 [/mm] = 0$
[mm] $-\frac{1}{2}t_2 [/mm] + 2 = 0 [mm] \Rightarrow t_2 [/mm] = 4$
In beiden Fällen ist der Abstand zwischen beiden Funktionswerten 0. Ich würde jetzt gerne aber nur in einem bestimmten Wertebereich von [mm] t_1 [/mm] und [mm] t_2 [/mm] nach dem minimalen Abstand suchen, sagen wir [mm] $t_1$ [/mm] und [mm] $t_2 \in [/mm] [0,1]$. Bei diesem einfachen Beispiel ist klar, dass der minimale Abstand hier bei [mm] $t_1 [/mm] = [mm] t_2 [/mm] = 1$ erreicht wird und dort $0,5$ ist. Ich suche nach einer allgemeinen Lösung für den Fall, dass man beliebig viele Geraden gegeben hat. Die [mm] $t_i$s [/mm] sind dabei auf einen bestimmten Wertebereich beschränkt.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:30 Do 27.03.2014 | | Autor: | chrisno |
Danke, nun verstehe ich es und denke.
Ich schreibe einfach hier weiter.
Das Problem entsteht erst durch die dritte Gerade. Bei zwei Geraden musst Du nur die beiden Wertebereiche vergleichen. Überlappen sie sich,ist der minimale Abstand Null. Andernfalls ist es der Abstand zwischen den Grenzen die sich näher liegen.
---
Bei drei Geraden nun der Fall, dass alle drei Wertebereiche paarweise disjunkt sind.
Es gibt also einen "unteren", einen "mittleren" und einen "oberen" Wertebereich.
Vom unteren und oberen Wertebereich werden die Grenzen genommen, die zur Mitte liegen.
Von diesen beiden Werten wird der Mittelwert gebildet. Liegt er in mittleren Bereich, ist hier das Minimum. Sonst ist es die nächstgelegene Grenze des mittleren Bereichs.
---
Das gilt auch, wenn sich die Wertebereiche überlappen, bis sie alle drei einen gemeinsamen Punkt haben. Ab dann ist das Minimum Null.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:52 Do 27.03.2014 | | Autor: | leduart |
Hallo
im ersten post schriebst du, du willst den Abstand zwischen den Geraden minimieren, . in deinem Beispiel aber minimierst du nicht den Abstand der Geraden, sondern den Abstand der Funktionswerte, die Geraden haben einen Abstand ungleich 0 in den betrachteten Punkten. Für Strecken innerhalb eines Intervalls (u1,u2) gibt es, wenn beide Geraden durch das Rechteck laufen wieder unendlich viele Punkte, wo die Funktionswerte gleich sind, falls sich die Geraden als [mm] f_i(t) [/mm] geschrie ben in den Intervall schneiden, schneiden sie sich ausserhalb liegt ihr nimimaler Funktionsabstand auf dem Rand.,
mach doch mal eine Skizze von 3 beliebigen Geraden im der Ebene, Deine NB beschreiben dann 3 Intervalle durch die die Geraden laufen, an denen kann man ablesen, wann man Abstandssumme 0 der Funktionswerte oder Minimalabstand auf den Rändern hat .
vielleicht ist meine Vorstellung auch falsch, dann korrigiere sie bitte.
Gruß leduart
|
|
|
| |
|
Nein deine Annahme stimmt und macht Sinn, danke. Lässt sich das auch auf mehr Geraden/Funktionen erweitern? Eigentlich brauche ich nämlich den allgemeinen Fall.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:00 Sa 29.03.2014 | | Autor: | leduart |
Hallo
Wenn ich dich jetzt richtig verstanden habe hast du n Intervalle [mm] [f_I(u_i),f(,o_i)] [/mm] du willst das Minimum der Abstande der Intervalle?
Dann geht das graphisch sehr einfach, uund du suchst nur nach einem Verfahren das in ein Programm zu übersetzen.
Gruß leduart
|
|
|
| |
|
Ja du hast recht. Geht tatsächlich relativ einfach. Danke für eure Hilfe.
|
|
|
|
