[linux-l] [OT] Gewichtete Wahrscheinlichkeit, Random
Volker Grabsch
vog at notjusthosting.com
Fr Mär 30 01:25:45 CEST 2007
On Thu, Mar 29, 2007 at 11:17:16PM +0200, Oliver Bandel wrote:
> > >Das ist doch dasselbe in grün: Es kommt drauf an, welche Symbole du
> > >zulässt. AFAIK werden dir Mathematica oder Maple da durchaus eine
> > >Lösung geben. Das ist aber einfach nicht der Punkt.
>
> Welche Lösung geben die denn?
siehe unten.
> Bei der Gaußfunktion klappt das nicht.
>
> Ingtetrierst Du die Gaußfunktion, müsste man ein Symbol für das Integral der Gaussfunktion
> erfinden. Kein Problem.
Die nehmen nimmt nicht genau die, aber eine damit verwandte Funktion
namens "erf". Siehe unten.
> Und wenn Du das Integral der Gaussfunktion wieder integrieren willst,
> musst Du ein Symbol für das Integral des Integrals der Gaußfunktion
> erfinden.
Woher willst du das wissen? Ist im Allgemeinen nämlich nicht so. Ein
menschlicher Mangel an Vorstellungskraft ist kein Beweis für die
Nichtexistenz einer Sache.
Mal ein einfacheres Beispiel, nehmen wir Zahlen statt Funktionen.
In R kannst du keine Wurzel aus -1 ziehen. Also nimmst du i als
eine Art sqrt(-1) hinzu, und alles, was sich durch +-*/ mit i
erzeugen lässt. Das sind die komplexen Zahlen.
Nun möchtest du sqrt(i) haben. Neues Symbol? Neuer Zahlenbereich?
Nein! Quadriere mal:
sqrt(1/2) * (1+i)
:-)
Solche Dinge passieren sehr oft in der Mathematik. Wiegesagt, "kann
ich mir nicht vorstellen" ist kein Argument. Früher dachte man auch,
es gäbe keine flächenfüllenden stetigen Kurven ... bis ein paar kreative
Leute für ein paar Schockierungen gesorgt haben, die das widerlegt
haben, was "anschaulich" klar schien.
> Und wenn Du das mehrmals wiederholst, musst Du entweder
> etliche Symbole erfinden, oder eines, das mithilfe eines Index' angibt,
> wie oft man diese Funktion integriert hat.
Ja, das passiert manchmal. Aber nicht bei solch einfachen Dingen
wie der Glockenkurve.
> Wenn Du dann dafür den zahlenwert haben willst, ist der Aufwand
> vermutlich wesentlich höer, als beim Berechnen der Gaußfunktion selbst.
Das habe ich nirgends bestritten.
> Jedenfalls sind die Taylorreihen der Gaussfunktion wegen der in der Gaussfunktion
> vorhandenen inneren Funktion => Kettenregel => aufwändig.
Willst du mich veralbern? Weil du beim Ableiten mehrfach die
Kettenregel anwenden musst, ist das Verfahren zu aufwändig?
Das ist ne wunderbare Regelmäßigkeit, was willst du denn mehr?
Dass es so trivial wie bei exp, sin, cos ist? Sooo billig ist
das natürlich nicht, bestreite ich gar nicht, aber daraus gleich
"schwer" und "rechenintensiv" zu schlussfolgern ...
Nee ... da kannst du genauso argumentieren, dass das Caesar-Verfahren
in der Kryptographie völlig ausreicht, weil es nicht jeder Depp in
5 Minuten knacken kann.
> Vielleicht hält sich der Aufwand auch in Grenzen und vielleicht ist meine
> Vermutung, daß der Aufwand bei geschlossen nicht lösbaren Funktionen
> besonders stark steigt falsch,
Definitiv! Wenn man so leicht für einen "besonders starken" Anstieg
des Rechenbedarfs sorgen könnte, gäbe es im Bereich der Kryptographie
nichts mehr zu forschen.
Deine ganzen "vielleichts" gehen mir solangsam auf die Nerven. Hab
mal in der Uni das Maple etwas gequält. Ich hoffe, das beantwortet
deine Fragen.
Auf dein Bauchgefühl solltest du dich grundsätzlich nur bei den Dingen
verlassen, mit denen du bereits intensiv gearbeitet hast.
----------------------------------------------------------------------
# maple
|\^/| Maple 9 (IBM INTEL LINUX)
._|\| |/|_. Copyright (c) Maplesoft, a division of Waterloo Maple Inc.
2003
\ MAPLE / All rights reserved. Maple is a trademark of
<____ ____> Waterloo Maple Inc.
| Type ? for help.
> int(exp(-x^2),x);
1/2
1/2 Pi erf(x)
> int(int(exp(-x^2),x),x);
/ 2 \
1/2 | exp(-x )|
1/2 Pi |x erf(x) + --------|
| 1/2 |
\ Pi /
----------------------------------------------------------------------
Du siehst, dass die erf-Funktion hervorragend das 1. und 2. Integral
der Glockenkurve beschreibt. Wenn du genau hinschaust, siehst du
sogar, wie die Formel des 1. Integrals in der des 2. drin steckt.
So viel zum Thema "steigende Komplexität", neue Funktionsklassen
und "nicht mehr symbolisch integrierbar". Können wir diesen Unsinn
damit bitte abschließen?
Außerdem habe ich mal die ersten paar Ableitungen der Glockenkurve
hergeholt:
----------------------------------------------------------------------
> diff(exp(-x^2),x);
2
-2 x exp(-x )
> diff(exp(-x^2),x,x);
2 2 2
-2 exp(-x ) + 4 x exp(-x )
> diff(exp(-x^2),x,x,x);
2 3 2
12 x exp(-x ) - 8 x exp(-x )
> diff(exp(-x^2),x,x,x,x);
2 2 2 4 2
12 exp(-x ) - 48 x exp(-x ) + 16 x exp(-x )
> diff(exp(-x^2),x,x,x,x,x);
2 3 2 5 2
-120 x exp(-x ) + 160 x exp(-x ) - 32 x exp(-x )
----------------------------------------------------------------------
Und jetzt erkläre mir mal bitte, was daran kompliziert ist. Alles
geht nach dem Schema P(x)*exp(-x^2), wobei P(x) ein Polynom ist.
Wenn du die Ableitungen an der Stelle 0 berechnest, fliegt der
größte Teil des Polynoms raus, bleibt nur noch der Absolutterm
übrig. Für diesen eine rekursive Formel aufzustellen ist für
Ungeübte sicher einiges an mathematischer Vorarbeit. Aber das
Endergebnis ist ganz sicher nichts, womit du irgendeinen Computer
irgendwie stressen könntest.
Die Mühe mache ich mir jetzt aber nicht, denn es gibt einen viel
einfacheren Weg: Du nimmst dir die Taylorreihe von exp(x) und
substituierst x -> -x^2. Das Ergebnis ist wieder eine Taylorreihe!
Die noch schnell integrieren (was bei analytischen Funktionen kein
Problem ist), und fertig:
exp(x)
= 1/0! + x/1! + x^2/2! + x^3/3! + ...
exp(-x^2)
= 1/0! - x^2/1! + x^4/2! - x^6/3! +- ...
Integral(exp(-x^2))
= x/0! - x^3/(3*1!) + x^5/(5*2!) - x^7/(7*3!) +- ...
So, da hast du deine unglaublich komplizierte Tailorreihe, die
so kompliziert ist, dass dir nur noch aufwändige nummerische
Integrationsverfahren übrig bleiben, um auch nur an wenige
Nachkommastellen zu gelangen.
Hier das ganze nochmal rekursiv umformuliert:
int_glockenkurve(x) = a_0 + a_1 + a_2 + ...
mit
a_0 = x
a_n = - a_(n-1) * x^2 * (1 + 1/(n-0.5)) / n
Die effiziente Implementierung davon, und einen Benchmark gegen
die system-eigenen Sinus- und Cosinus-Funktionen überlasse ich
nun dir. Ich hab auf dein Drängen hin den mathematischen Teil
ausgearbeitet, jetzt zeige bitte wenigstens so viel Respekt,
und messe den Geschwindigkeitsunterschied nach. Sollte in Ocaml
ne kleine Fingerübung sein. Du willst doch immer Gruppenarbeit.
Hier hast du (wieder mal) ne Gelegenheit. :-)
Viele Grüße,
Volker
--
Volker Grabsch
---<<(())>>---
Administrator
NotJustHosting GbR
Mehr Informationen über die Mailingliste linux-l