[ <] [ Globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]

Kapitelübersicht 7.5.3 Zahlentheoretische Integrationsformeln

  • 7.5.3.1. Gleichverteilung
  • 7.5.3.2. Diskrepanz endlicher Folgen
  • 7.5.3.3. Variation einer Funktion
  • 7.5.3.4. Variation von Vitali
  • 7.5.3.5. Variation von Hardy und Krause
  • 7.5.3.6. Koksma-Hlawak-Ungleichung
  • 7.5.3.7. Eindimensionale Folgen mit kleiner Diskrepanz
  • 7.5.3.8. Van der Corput-Folgen
  • 7.5.3.9. Mehrdimensionale Folgen mit kleiner Diskrepanz
  • 7.5.3.10. Halton-Folgen
  • 7.5.3.11. Hammersley-Folgen
    •

    7.5.3. Zahlentheoretische Integrationsformeln

    7.5.3.1. Gleichverteilung

    Eine Folge von Vektoren x1, x2,...mit xN Element Rn heißt gleichverteilt im Würfel Wn := [0,1]n wenn für alle Riemann-integrierbaren Funktionen f : Wn -> R die entsprechende Folge { Qnf } mit den Integrationsformeln QN := [ f(x1) + f(x2) + ... + f(xN)] / N gegen I( f; WN) konvergiert.

    Die charakteristische Funktion cE eines Teilwürfels E echt Teilmenge von Wn ist offensichtlich Riemann-integrierbar.

    Jeder im Würfel gleichverteilte Folge x1, x2,... entspricht einer Folge von Integrationsformeln Q1,Q2,... für diesen Bereich


    $Q_Nf := \frac{1}{N}\sum_{i=1}^Nf(x_i), N=1,2,...,N$

    die gemäß Definition für alle Riemann-integrierbare Funktionen f: Wn -> R konvergent ist


    ${\rem lim}_{N\rightarrow\un}Q_Nf = \int_{W_n}f(x)dx $

    Dem simplen Konvergenzresultat Q1,Q2,...-> I(f,Wn) kann man keine Information über die Größe des Fehlers Qnf -IF entnehmen.

    7.5.3.2. Diskrepanz endlicher Folgen

    die Diskrepanz einer endlichen Punktmenge x1, x2, ... , xN charakterisiert die Abweichung der Punktemenge von einer hypothetischen Verteilung.

    Für eine nicht leere Menge M von Teilmengen von Wn = 0,1 n bezeichnet man


    $ D^{M_1}_N(x_1,x_2,...,x_N) := {\rem sup}_{E\in M} |\frac {A(E;N)}{N} - \int_{W_n}c_E(x)dx |$

    als die Diskrepanz der endlichen Folge x1,x2,...,xN Element von Wn .

    Mit Hilfe des Begriffes der Diskrepanz lassen sich gleichverteilte Folgen durch asymptotisch optimale Diskrepanz charakterisiert. Eine unendliche Folge von Punkten ist genau dann gleichverteilt, wenn die Diskrepanz ihrer endlichen Teilfolgen gegen Null strebt:


    ${\rem lim}_{N\rightarrow \un}D_N(x_1,x_2,...,x_N) =0 $

    7.5.3.3. Variation einer Funktion

    die Variation einer Veränderlichen f : [a,b] -> R charakterisiert das Ausmaß ihrer Variabilität auf dem Intervall [a,b].

    Zerlegt man das Intervall [a,b] in N Teilintervalle


    $P := {x_i : a=x_0<x_1<...<x_{N_1}<x_N=b }$

    so ist die Summe


    $\sum_{i=1}^N |f(x_i)-f(x_{i=1}) $

    eine Maßzahl für die diskrete Variation von f bezüglich der Zerlegung P.

    7.5.3.4. Variation von Vitali

    das univariate Konzept der Variationen kann man auf multivariate Funktionen verallgemeinern. Aus n Zerlegungen von [0,1] kann man einer Zerlegung P des Würfels WN = [0,1]n in Teilquader konstruieren.Die Variation einer Funktion im Sinn von Vitali ist durch


    $V^{(n)}(f) := {\rem sup}_p \sum_{W'_n \in P} |\delta (f;W'_n)|$

    definiert.

    7.5.3.5. Variation von Hardy und Krause

    wenn man auch das Verhalten von f auf den Seiten des Würfels WN in Betracht zieht, erhält man ein geeignetes Maß für die Regularität einer Funktion.

    Die Variation V(f) von f auf Wn = 0,1 n im Sinne von Hardy und Krause ist durch


    $V(f) := \sum_{1\le i_1\le n}V^{(1)}(f;i_1) + \sum_{1\le i_1\le i_2 \le nV^{(2)}(f;i_1,i_2) +...+ V^{(n)} (f;1,2,...,n)$

    definiert.

    7.5.3.6. Koksma-Hlawak-Ungleichung

    charakterisiert den Verfahrensfehler einer zahlentheoretischen Integrationsformel QN durch die Regularität bzw. Variabilität des Integranden f und die Gleichmäßigkeit der Abzissenverteilung.

    Für jede durch gleichverteilte Folgen definierte Integrationsformel


    $Q_Nf := \frac{1}{N} \sum_{i=1}^Nf(x_i) {\rem für} If = \int_{[0,1]^n}f(x)dx $

    gilt die Fehlerschranke


    $|Q_Nf - If| \leV(f)D_N^\star (x_1,x_2,...,x_N) $

    wobei V(f) die Variation des Integranden f im Sinne von Hardy und Krause ist und D*N(x1,x2,...,xN) die Stern-Diskrepanz der Folge x1,x2,...,xN bezeichnet.

    7.5.3.7. Eindimensionale Folgen mit kleiner Diskrepanz

    als Grundlage für mehrdimensionale Integrationsformeln

    Die Werte der Diskrepanz D*N und DN einer endlichen Folge x1,x2,...,xN in dem Intervall 0.1 erhöht man aus folgender Formeln:


    $D^\star_N(x_1,x_2,...,x_N) = \frac{1}{2N} + {\rem max} (|x_1 - \frac{2i-1}{2N} :i=1,2,...,N) D_N(x_1,x_2,...,x_N) = \frac{1}{N} + {\rem max}(\frac{i}{N} - x_i : i=1,2,...,N) - {\rem min} (\frac{i}{n} x_i : i=1,2,...,N) $

    Die entsprechende Quadraturformel mit optimalen Fehlerschranken ist die zusammengesetzte einpunktige Gauß-Legende-Formel, d.h. die zusammengesetzte Mittelpunkt-Formel .

    7.5.3.8. Van der Corput-Folgen

    Die van der Corput-Folge in der Basis b ist eine unendliche Folge x1,x2,...., die durch


    $x_i := \phi_b(i=1), i=1,2,,3... $

    festgelegt ist.Van der Corput-Folgen besitzen optimale asymptotische Diskrepanz.

    7.5.3.9. Mehrdimensionale Folgen mit kleiner Diskrepanz

    liefert die bestmögliche untere Schranke für die Diskrepanz univariater endlicher Folgen, die von der zusammengesetzten Mittelpunkt-Regel erreicht wird. Diese ist bei multivariaten Folgen nicht bekannt, kann nur geschätzt werden.

    7.5.3.10. Halton-Folgen

    sind mehrdimensionale Verallgemeinerung der eindimensionalen van der Corput-Folgen.Die Halton-Folgen in den Basen b1,b2,...,bn ist durch


    $x_i := (\phi_{b_1}(i-1), \phi_{b_2}(i-2),..., \phi_{b_n}(i-1)^\tau, i=1,2,3,... $

    definiert.

    7.5.3.11. Hammersley-Folgen

    endliche Folgen.

    Die N-punktige Hammersley-Folge in den Basen b1,b2,..., bn-1 ist durch


    $x_i := (\frac{i-1}{N},\phi_{b_i}(i-1),\phi{b_2}(i-1),...,\phi_{b_{n-1}}(i-1)), i=1,2,...,N$

    definierte Folge x1,x2,...,xN Element von Rn.

    Die Diskrepanzabschätzung einer N-Punkt-Hammersley-Folge ist daher um den Faktor

    (2logpn)-1(pn-1)logN kleiner als die entsprechende Halton-Folge.

    [ <] [ Globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]