Beste Integralapprox. Wurzel < Integr.+Differenz. < Numerik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Wir haben das Einheitsquadrat [mm] [0,1]^{2} [/mm] und verteilen darauf 4 Punkte völlig zufällig. Mit welcher Wahrscheinlichkeit entsteht als konvexe Hülle der 4 Punkte ein Dreieck, mit welcher Wahrscheinlichkeit ein Viereck? |
Hallo!
Hier ein wenig Erklärung, die eigentliche Frage ist unten!
Ich beschäftige mich jetzt schon eine Weile mit obiger Fragestellung. Ich habe dazu die Überlegung:
P(konv. Hülle = Dreieck)
= P(Ein Punkt liegt in dem Dreieck der restlichen drei Punkte)
= 4*P(X1 liegt in dem Dreieck von X2,X3,X4)
= 4*Fläche Dreieck von X2,X3,X4 im Einheitsquadrat [mm] [0,1]^{2}
[/mm]
Das heißt es geht darum, herauszufinden, welchen Flächeninhalt ein Dreieck hat, dass von drei zufälligen Punkten aufgespannt wird.
Dafür wiederum habe ich den Ansatz gemacht: X2 = (x2,y2),X3 = (x3,y3),X4 = (x4,y4) sind gleichverteilt auf [mm] [0,1]^{2}, [/mm] damit gelange ich mit der Heron-Formel zu dem Sechsfach-Integral:
[mm]s1(x2,y2,x3,y3,x4,y4) = \sqrt{(x2-x3)^2+(y2-y3)^2}[/mm]
[mm]s2(x2,y2,x3,y3,x4,y4) = \sqrt{(x2-x4)^2+(y2-y4)^2}[/mm]
[mm]s3(x2,y2,x3,y3,x4,y4) = \sqrt{(x3-x4)^2+(y3-y4)^2}[/mm]
[mm]s = \frac{s1+s2+s3}{2}[/mm]
[mm]\int_{0}^{1}\int_{0}^{1}\int_{0}^{1}\int_{0}^{1}\int_{0}^{1}\int_{0}^{1} \sqrt{s*(s-s1)*(s-s2)*(s-s3)} dx2\ dx3\ dx4\ dy2\ dy3\ dy4[/mm].
Nun meine Fragen:
- Maple will mir keine Näherung für dieses Integral berechnen. Kennt ihr ein Programm, dass solch ein Integral annähern kann?
- Ich habe aufgrund des Maple-Problems selbst versucht, ein Programm zu schreiben, dass das Integral löst. Dabei geht es vor allem um die Wurzel-Funktion, die möglichst exakt integriert werden müsste. Gibt es ein Verfahren, dass Wurzeln möglichst exakt integriert (bei Polynomen ist immer das Problem, dass sie bei Approximation von [mm] \sqrt{x} [/mm] bei "0" über das Ziel hinausschießen (unendliche Steigung...)?
- Gibt es eine einfachere Möglichkeit für die Lösung des Problems als das Sechsfachintegral???
Vielen Dank für Eure Hilfe!
Grüße,
Stefan
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:45 Sa 28.08.2010 | | Autor: | abakus |
> Wir haben das Einheitsquadrat [mm][0,1]^{2}[/mm] und verteilen
> darauf 4 Punkte völlig zufällig. Mit welcher
> Wahrscheinlichkeit entsteht als konvexe Hülle der 4 Punkte
> ein Dreieck, mit welcher Wahrscheinlichkeit ein Viereck?
> Hallo!
>
> Hier ein wenig Erklärung, die eigentliche Frage ist
> unten!
> Ich beschäftige mich jetzt schon eine Weile mit obiger
> Fragestellung. Ich habe dazu die Überlegung:
>
> P(konv. Hülle = Dreieck)
> = P(Ein Punkt liegt in dem Dreieck der restlichen drei
> Punkte)
> = 4*P(X1 liegt in dem Dreieck von X2,X3,X4)
> = 4*Fläche Dreieck von X2,X3,X4 im Einheitsquadrat
> [mm][0,1]^{2}[/mm]
>
> Das heißt es geht darum, herauszufinden, welchen
> Flächeninhalt ein Dreieck hat, dass von drei zufälligen
> Punkten aufgespannt wird.
> Dafür wiederum habe ich den Ansatz gemacht: X2 =
> (x2,y2),X3 = (x3,y3),X4 = (x4,y4) sind gleichverteilt auf
> [mm][0,1]^{2},[/mm] damit gelange ich mit der Heron-Formel zu dem
> Sechsfach-Integral:
>
> [mm]s1(x2,y2,x3,y3,x4,y4) = \sqrt{(x2-x3)^2+(y2-y3)^2}[/mm]
>
> [mm]s2(x2,y2,x3,y3,x4,y4) = \sqrt{(x2-x4)^2+(y2-y4)^2}[/mm]
>
> [mm]s3(x2,y2,x3,y3,x4,y4) = \sqrt{(x3-x4)^2+(y3-y4)^2}[/mm]
>
> [mm]s = \frac{s1+s2+s3}{2}[/mm]
>
> [mm]\int_{0}^{1}\int_{0}^{1}\int_{0}^{1}\int_{0}^{1}\int_{0}^{1}\int_{0}^{1} \sqrt{s*(s-s1)*(s-s2)*(s-s3)} dx2\ dx3\ dx4\ dy2\ dy3\ dy4[/mm].
>
> Nun meine Fragen:
> - Maple will mir keine Näherung für dieses Integral
> berechnen. Kennt ihr ein Programm, dass solch ein Integral
> annähern kann?
> - Ich habe aufgrund des Maple-Problems selbst versucht,
> ein Programm zu schreiben, dass das Integral löst. Dabei
> geht es vor allem um die Wurzel-Funktion, die möglichst
> exakt integriert werden müsste. Gibt es ein Verfahren,
> dass Wurzeln möglichst exakt integriert (bei Polynomen ist
> immer das Problem, dass sie bei Approximation von [mm]\sqrt{x}[/mm]
> bei "0" über das Ziel hinausschießen (unendliche
> Steigung...)?
> - Gibt es eine einfachere Möglichkeit für die Lösung
> des Problems als das Sechsfachintegral???
>
> Vielen Dank für Eure Hilfe!
> Grüße,
> Stefan
Hallo Stefan,
könntest du nicht als Näherungslösung das Quadrat mit einem Gitternetz überziehen und als Eckpunkte nur Gitterpunkte zulassen?
Variante 2: Dem entstehenden Dreieck kann ein achsenparalleles Rechteck umbeschrieben werden, dessen Begrenzungen durch das Max. bzw. Min. der Koordinaten der drei Punkte vorgegeben sind. Von diesem Rechteck müssen dann noch drei Dreiecksflächen subtrahiert werden.
Wenn du nur ein numerisches Ergebnis brauchst, sollte doch eine Simulation genügen, oder?
Gruß Abakus
|
|
|
| |
|
Hallo abakus,
danke für deine Anregungen!
Mein Ziel ist es, das Ergebnis "genau genug (und möglichst exakt)" berechnen zu können.
> Hallo Stefan,
> könntest du nicht als Näherungslösung das Quadrat mit
> einem Gitternetz überziehen und als Eckpunkte nur
> Gitterpunkte zulassen?
Das werde ich mal ausprobieren. Danke 
Dann werden ja die Integrale zu Summen.
> Variante 2: Dem entstehenden Dreieck kann ein
> achsenparalleles Rechteck umbeschrieben werden, dessen
> Begrenzungen durch das Max. bzw. Min. der Koordinaten der
> drei Punkte vorgegeben sind. Von diesem Rechteck müssen
> dann noch drei Dreiecksflächen subtrahiert werden.
Da verstehe ich ehrlich gesagt noch nicht, wie mir das weiterhelfen soll? Wenn ich min und max von Zufallsvariablen bilde, werden auch die Verteilungsfunktionen nicht mehr so schön einfach bleiben.
> Wenn du nur ein numerisches Ergebnis brauchst, sollte doch
> eine Simulation genügen, oder?
Haben wir ausprobiert. Allerdings bekommt man selbst mit 100.000.000 Versuchen noch Probleme bei der 3. Nachkommastelle, und ich wollte eigentlich eine "sicheres Ergebnis" bis zur sagen wir 6.ten Nachkommastelle haben.
---------
Mich würde auch vom Prinzip her einfach interessieren, wie man das Integral der Wurzel möglichst gut approximieren kann.
Vielen Dank für Eure Hilfe!
Grüße,
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:20 Mo 30.08.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:21 Sa 28.08.2010 | | Autor: | felixf |
Moin!
> - Maple will mir keine Näherung für dieses Integral
> berechnen.
Vielleicht kann ich hier weiterhelfen 
Die meisten Leute wissen nicht, dass man bei Maple Integrale numerisch loesen lassen sollte, indem man evalf(Int(...)) benutzt und nicht evalf(int(...)) oder einfach nur int(...) -- bei int (mit kleinem i) versucht Maple das erst symbolisch zu integrieren, und scheitert vermutlich klaeglich. Int (mit grossem i) ist ein Platzhalter fuer das Integral, der erstmal gar nichts tut, und evalf wertet das ganze dann numerisch aus.
Also vielleicht mal alle ints in Ints umwandeln, falls du das nicht schon gemacht hattest :)
LG Felix
|
|
|
| |
|
Hallo Felix!
> Moin!
>
> > - Maple will mir keine Näherung für dieses Integral
> > berechnen.
>
> Vielleicht kann ich hier weiterhelfen
>
> Die meisten Leute wissen nicht, dass man bei Maple
> Integrale numerisch loesen lassen sollte, indem man
> evalf(Int(...)) benutzt und nicht evalf(int(...)) oder
> einfach nur int(...) -- bei int (mit kleinem i) versucht
> Maple das erst symbolisch zu integrieren, und scheitert
> vermutlich klaeglich. Int (mit grossem i) ist ein
> Platzhalter fuer das Integral, der erstmal gar nichts tut,
> und evalf wertet das ganze dann numerisch aus.
Danke für diese Tipps! Das wusste ich alles noch nicht, ich habe immer die Symbole zum Anklicken benutzt. Jetzt habe ich mich mal reingelesen. Und tatsächlich ist Maple zumindest nicht abgeschmiert, als ich das Integral zum Berechnen freigegeben habe. Allerdings ist nach 6 Stunden noch kein Ergebnis rausgekommen - ich habe jetzt abgebrochen.
Mein Programm benutzt die Gauß-Quadratur und hat zur Zeit eine Approximation von 0.07638 als "feste" Stellen raus. Das muss jetzt noch mal 4 genommen werden --> 0.30552 ist die gesuchte Wahrscheinlichkeit - schade, ich dachte, es kommt was Schönes raus :-(
Grüße,
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:13 So 29.08.2010 | | Autor: | felixf |
Moin Stefan!
> Danke für diese Tipps! Das wusste ich alles noch nicht,
> ich habe immer die Symbole zum Anklicken benutzt. Jetzt
> habe ich mich mal reingelesen. Und tatsächlich ist Maple
> zumindest nicht abgeschmiert, als ich das Integral zum
> Berechnen freigegeben habe. Allerdings ist nach 6 Stunden
> noch kein Ergebnis rausgekommen - ich habe jetzt
> abgebrochen.
Bei Mehrfachintegralen bietet sich auch oft ein Monte-Carlo-Verfahren an.
> Mein Programm benutzt die Gauß-Quadratur und hat zur Zeit
> eine Approximation von 0.07638 als "feste" Stellen raus.
Ich hab das mal testweise implementiert, bei 10 Millionen Stuetzstellen komme ich auf [mm] $\approx [/mm] 0.0763$.
> Das muss jetzt noch mal 4 genommen werden --> 0.30552 ist
> die gesuchte Wahrscheinlichkeit - schade, ich dachte, es
> kommt was Schönes raus :-(
Ich glaube, dein Ansatz hat ein kleines Problem. Ich schreib gleich mehr dazu...
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:23 So 29.08.2010 | | Autor: | felixf |
Moin!
> P(Ein Punkt liegt in dem Dreieck der restlichen drei Punkte)
> = 4*P(X1 liegt in dem Dreieck von X2,X3,X4)
Bei dieser Gleichheit frage ich mich, ob das ueberhaupt stimmt.
Ich denke, die Wahrscheinlichkeit ist P(X1 liegt in dem Dreieck von X2,X3,X4), also ohne den Faktor 4.
Sei $A$ die Menge ``X2,X3,X4 bilden ein echtes Dreieck'' und $B$ das Komplement. Dann gilt $P(A) = 1$ und $P(B) = 0$.
Ist $C$ die Menge ``die konvexe Huelle von X1,X2,X3,X4 ist ein Dreieck'', so ist ja $P(C)$ gesucht. Sei $D$ weiterhin die Menge ``X1 liegt im vom X2,X3,X4 aufgespannten Dreieck''.
Nun ist $P(C) = P(A [mm] \cap [/mm] C) + P(B [mm] \cap [/mm] C)$, und $0 [mm] \le [/mm] P(B [mm] \cap [/mm] C) [mm] \le [/mm] P(B) = 0$, womit $P(C) = P(A [mm] \cap [/mm] C)$ ist. Analog folgt $P(D) = P(A [mm] \cap [/mm] D)$. Nun ist jedoch $A [mm] \cap [/mm] C = A [mm] \cap [/mm] D$.
Also folgt: $P(C) = P(D)$, womit die gesuchte Wahrscheinlichkeit gleich P(X1 liegt in dem Dreieck von X2,X3,X4) ist.
LG Felix
|
|
|
| |
|
Hallo Felix,
zunächst auch hier vielen Dank für deine Mühe.
Allerdings kommen wir eben auch mit Simulation auf 0.3 als Wahrscheinlichkeit, da muss ja was dran sein...
> > P(Ein Punkt liegt in dem Dreieck der restlichen drei
> Punkte)
> > = 4*P(X1 liegt in dem Dreieck von X2,X3,X4)
>
> Bei dieser Gleichheit frage ich mich, ob das ueberhaupt
> stimmt.
>
> Ich denke, die Wahrscheinlichkeit ist P(X1 liegt in dem
> Dreieck von X2,X3,X4), also ohne den Faktor 4.
>
> Sei [mm]A[/mm] die Menge ''X2,X3,X4 bilden ein echtes Dreieck'' und
> [mm]B[/mm] das Komplement. Dann gilt [mm]P(A) = 1[/mm] und [mm]P(B) = 0[/mm].
>
> Ist [mm]C[/mm] die Menge ''die konvexe Huelle von X1,X2,X3,X4 ist
> ein Dreieck'', so ist ja [mm]P(C)[/mm] gesucht. Sei [mm]D[/mm] weiterhin die
> Menge ''X1 liegt im vom X2,X3,X4 aufgespannten Dreieck''.
>
> Nun ist [mm]P(C) = P(A \cap C) + P(B \cap C)[/mm], und [mm]0 \le P(B \cap C) \le P(B) = 0[/mm],
> womit [mm]P(C) = P(A \cap C)[/mm] ist. Analog folgt [mm]P(D) = P(A \cap D)[/mm].
> Nun ist jedoch [mm]A \cap C = A \cap D[/mm].
Mir ist nicht klar, woraus du [mm]A\cap C = A\cap D[/mm] folgst. Kannst du mir das genauer erklären?
Grüße,
Stefan
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:47 So 29.08.2010 | | Autor: | felixf |
Moin Stefan!
> zunächst auch hier vielen Dank für deine Mühe.
> Allerdings kommen wir eben auch mit Simulation auf 0.3 als
> Wahrscheinlichkeit, da muss ja was dran sein...
>
> > > P(Ein Punkt liegt in dem Dreieck der restlichen drei
> > Punkte)
> > > = 4*P(X1 liegt in dem Dreieck von X2,X3,X4)
> >
> > Bei dieser Gleichheit frage ich mich, ob das ueberhaupt
> > stimmt.
> >
> > Ich denke, die Wahrscheinlichkeit ist P(X1 liegt in dem
> > Dreieck von X2,X3,X4), also ohne den Faktor 4.
> >
> > Sei [mm]A[/mm] die Menge ''X2,X3,X4 bilden ein echtes Dreieck'' und
> > [mm]B[/mm] das Komplement. Dann gilt [mm]P(A) = 1[/mm] und [mm]P(B) = 0[/mm].
> >
> > Ist [mm]C[/mm] die Menge ''die konvexe Huelle von X1,X2,X3,X4 ist
> > ein Dreieck'', so ist ja [mm]P(C)[/mm] gesucht. Sei [mm]D[/mm] weiterhin die
> > Menge ''X1 liegt im vom X2,X3,X4 aufgespannten Dreieck''.
> >
> > Nun ist [mm]P(C) = P(A \cap C) + P(B \cap C)[/mm], und [mm]0 \le P(B \cap C) \le P(B) = 0[/mm],
> > womit [mm]P(C) = P(A \cap C)[/mm] ist. Analog folgt [mm]P(D) = P(A \cap D)[/mm].
> > Nun ist jedoch [mm]A \cap C = A \cap D[/mm].
>
> Mir ist nicht klar, woraus du [mm]A\cap C = A\cap D[/mm] folgst.
> Kannst du mir das genauer erklären?
Oh, ich merke gerade wo das Problem liegt. Die Mengen sind nicht gleich.
Wenn X2,X3,X4 ein echtes Dreieck bilden, kann X1 sehr wohl ausserhalb dieses Dreiecks liegen, und die konvexe Huelle ist trotzdem wieder ein Dreieck. Da hab ich nicht ganz aufgepasst...
LG Felix
|
|
|
| |
|
Hallo Felix,
ich war schon drauf und dran zu meckern, als ich noch deine
neue Mitteilung entdeckte. Wenn man die ersten drei Punkte
in das Quadrat gesetzt hat, entsteht durch den vierten Punkt
genau dann als konvexe Hülle nur ein Dreieck, wenn der
vierte Punkt in den schattierten Bereich fällt:
[Dateianhang nicht öffentlich]
Man könnte also auch versuchen, den Durchschnittswert des
Flächeninhalts dieses Gebietes (wenn [mm] P_1, P_2, P_3 [/mm] zufällig
gesetzt werden) durch ein Integral darzustellen.
Falls ich eure übrigen Überlegungen richtig verstanden habe,
käme man nun noch zu einem interessanten Nebenergebnis:
Sind die Punkte [mm] P_1, P_2, P_3 [/mm] zufällig (gleichmässig verteilt
und unabhängig voneinander) in das Quadrat gesetzt, so
nimmt das innere Dreieck durchschnittlich genau ein Viertel
der gesamten schraffierten Fläche ein.
LG Al-Chw.
Dateianhänge:
Anhang Nr. 1 (Typ: unbekannt) [nicht öffentlich]
|
|
|
| |
|
Falls die Punkte [mm] P_1, P_2, P_3 [/mm] zufällig (gleichmäßig auf die
Fläche verteilt und unabhängig) in einem Quadrat verteilt
werden, kommt anscheinend allen 4 schraffierten Teilstücken
der folgenden Figur:
[Dateianhang nicht öffentlich]
im Mittel derselbe Flächeninhalt zu.
Ich frage mich und alle Interessierten nun:
Es scheint irgendwie zu speziell, dass dieses Ergebnis nur für
den Fall eines Quadrates als umfassende Figur gelten sollte.
Meine Vermutung ist, dass es auch für einen Kreis oder viel-
leicht sogar für eine beliebige konvexe Figur zutreffen sollte.
Über einen allfälligen Beweis habe ich mir allerdings noch
keine Gedanken gemacht.
Für die Untersuchung möchte ich gerade ein paar Bezeich-
nungen vorschlagen:
$\ \ [mm] \,k\ [/mm] \ :$ umfassende (konvexe) Kurve
[mm] A_0: [/mm] Flächeninhalt des Dreiecks [mm] P_1P_2P_3
[/mm]
[mm] A_1: [/mm] Flächeninhalt des schraffierten Gebiets zwischen [mm] P_1 [/mm] und k
[mm] A_2: [/mm] Flächeninhalt des schraffierten Gebiets zwischen [mm] P_2 [/mm] und k
[mm] A_3: [/mm] Flächeninhalt des schraffierten Gebiets zwischen [mm] P_3 [/mm] und k
LG Al-Chwarizmi
Dateianhänge:
Anhang Nr. 1 (Typ: unbekannt) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:20 Di 14.09.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:53 So 29.08.2010 | | Autor: | felixf |
Moin!
> Das heißt es geht darum, herauszufinden, welchen
> Flächeninhalt ein Dreieck hat, dass von drei zufälligen
> Punkten aufgespannt wird.
> Dafür wiederum habe ich den Ansatz gemacht: X2 =
> (x2,y2),X3 = (x3,y3),X4 = (x4,y4) sind gleichverteilt auf
> [mm][0,1]^{2},[/mm] damit gelange ich mit der Heron-Formel zu dem
> Sechsfach-Integral:
Das geht doch viel einfacher :)
Das Dreieck wird von den Vektoren [mm]X4 - X2 = \pmat{ x4 - x2 \\
y4 - y2} }[/mm] und [mm]X4 - X3 = \pmat{ x4 - x3 \\
y4 - y3 }[/mm] aufgespannt, womit sein Flaecheninhalt durch [mm]\frac{1}{2} |(x4 - x2) (y4 - y3) - (x4 - x3) (y4 - y2)|[/mm] gegeben ist laut ![[]](/images/popup.gif) dem hier.
Damit erhaelt man das Sechsfachintegral [mm]\frac{1}{2}\int_{0}^{1}\int_{0}^{1}\int_{0}^{1}\int_{0}^{1}\int_{0}^{1}\int_{0}^{1}|(x4-x2)(y4-y3)-(y4-y2)(x4-x3)|dx2\,dx3\,dx4\,dy2\,dy3\,dy4[/mm]. Das sieht doch gleich viel schoener aus
Damit laesst sich das ganze etwas effizienter implementieren, da der Ausdruck einfacher ist... Eventuell hat man sogar eine Chance, das Integral etwas expliziter auszurechnen oder es zumindest von einem Sechsfach- auf ein Vierfachintegral zu reduzieren.
Bei [mm] $10^9$ [/mm] Stuetzstellen komme ich uebrigens auf [mm] $\approx [/mm] 0.07638551$, mein stupides ![[a]](/images/paperclip.gif "Dateianhänge") Test-Java-Programm hat dafuer etwas ueber 4 Minuten gerechnet...
LG Felix
Dateianhänge:
Anhang Nr. 1 (Typ: java) [nicht öffentlich]
|
|
|
| |
|
Hallo Felix,
vielen, vielen Dank für deine Antworten !
Das Problem hat dich wohl auch nicht ganz losgelassen.
Allerdings haben wir auch eine "Live-Simulation" gemacht (also vier zufällige Punkte, dann konvexe Hülle bilden), und da kommt man auf 0.305.
Das heißt, mein Ansatz mit den mal 4 nehmen muss stimmen.
Ich schau' mir gleich mal deine ganzen anderen Tipps an!
Grüße,
Stefan
|
|
|
|
