Wie kann man die Genauigkeit eines Integrals abschätzen?

11

Eine äußerst häufige Situation in der Computergrafik besteht darin, dass die Farbe eines Pixels gleich dem Integral einer reellen Funktion ist. Oft ist die Funktion zu kompliziert, um sie analytisch zu lösen, daher bleibt uns die numerische Approximation. Die Berechnung der Funktion ist jedoch häufig sehr teuer, sodass wir stark darauf beschränkt sind, wie viele Stichproben wir berechnen können. (Sie können sich beispielsweise nicht einfach dafür entscheiden, eine Million Proben zu nehmen und dabei zu belassen.)

Im Allgemeinen möchten Sie dann die Funktion an zufällig ausgewählten Punkten bewerten, bis das geschätzte Integral "genau genug" wird. Was mich zu meiner eigentlichen Frage bringt: Wie schätzen Sie die "Genauigkeit" des Integrals ein?


Insbesondere haben wir , das durch einen komplizierten, langsamen Computeralgorithmus implementiert wird. Wir wollen schätzenf:RR

k=abf(x) dx

Wir können berechnen für jede x wir uns wünschen, aber es ist teuer. Wir wollen also mehrere x- Werte zufällig auswählen und aufhören, wenn die Schätzung für k akzeptabel genau wird. Dazu müssen wir natürlich wissen, wie genau die aktuelle Schätzung tatsächlich ist.f(x)xxk

Ich bin mir nicht einmal sicher, welche statistischen Tools für diese Art von Problem geeignet wären. Aber es scheint mir, dass das Problem unlösbar ist , wenn wir absolut nichts über wissen . Wenn Sie beispielsweise tausendmal f ( x ) berechnen und es immer Null ist, ist Ihr geschätztes Integral Null. Aber, nichts zu wissen , f , dann ist es immer noch möglich , dass f ( x ) = 1 , 000 , 000 überall mit Ausnahme der Punkte , die Sie Probe passieren, so dass Ihre Schätzung schrecklich falsch ist!ff(x)ff(x)=1,000,000

ff


Bearbeiten: OK, das scheint also viele Antworten generiert zu haben, was gut ist. Anstatt auf jeden von ihnen einzeln zu antworten, werde ich versuchen, hier einen zusätzlichen Hintergrund einzufügen.

ffff

fff

f

Angesichts der Häufigkeit, mit der "Monte Carlo" aufgetaucht ist, schätze ich, dass dies der Fachbegriff für diese Art der Integration ist.

MathematicalOrchid
quelle
ff
2
Wenn Sie über eine bekannte Funktion integrieren, können Sie in der Regel viel besser als mit der Monte-Carlo-Integration arbeiten. Monte Carlo konvergiert mit einer Rate von zum wahren Wert1/NN1/N(lnN)n/Nn
1
f
1
ff
1
f

Antworten:

2

222222

Michael R. Chernick
quelle
3
0Mf
1
@Macro Ohne etwas über f zu wissen, sehe ich nicht, wie man etwas über die statistische Genauigkeit einer Schätzung des Integrals sagen könnte, wenn man es an einer festen endlichen Menge von Punkten bewertet. Meine Annahmen sind eher minimal. Wenn f auf das Intervall [a, b] begrenzt ist, sollte es ein M geben, das groß genug ist, um als Obergrenze für f verwendet zu werden.
Michael R. Chernick
M
2
Es ist eine Annahme. Ich habe den Begriff Mimimal verwendet, um zu sagen, dass ich so wenig Annahmen wie möglich mache, um eine endgültige Antwort zu erhalten.
Michael R. Chernick
f
8

f

Eine ergänzende Lektüre dazu wäre natürlich die Monographie von Niederreiter (1992) .

StasK
quelle
3
(+1) Josef Dick hat auch einige interessante, relativ aktuelle Ergebnisse.
Kardinal