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

Kapitelübersicht 7.5.5 Gitterpunkt-Integrationsformeln

  • 7.5.5.1. Formelkonstruktion mittels harmonischer Analyse
  • 7.5.5.2. Univariate Trapezregel für periodische Integranden
  • 7.5.5.3. Multivariate Integrationsformeln für periodische Integranden
  • 7.5.5.4. Gitterpunkt-Formeln
  • 7.5.5.5. Darstellung von Gitterpunkt-Formeln in k-Zyklus-Form
  • 7.5.5.6. Verfahrensfehler der Gitterpunkt-Formeln
  • 7.5.5.7. Korobov-Räume
  • 7.5.5.8. Konvergenz von Gitterpunkt-Formeln
  • 7.5.5.9. Praktisch verwendbare Gitterpunkt-Formeln
    •

    7.5.5. Gitterpunkt-Integrationsformeln

    7.5.5.1. Formelkonstruktion mittels harmonischer Analyse

    Konstruktionsmethode für Integrationsformeln, die einer Verallgemeinerung der univariaten Trapezregel zu multivariaten Integrationsformeln mit ähnlichen Eigenschaften erlaubt, führt über die spezielle Fehlerstruktur von TN, wie sie durch die Euler- Maclaurische Summenformel sehr genau charakterisiert wird.

    7.5.5.2. Univariate Trapezregel für periodische Integranden

    wenn Funktion f hinreichend glatt ist, dann kann man sie in ihre Fourier-Reihe entwickeln. Die absolute Konvergenz in einer Fourier-Reihe ist gesichert, wenn f z.B. einer Hölder-Bedingung


    $|f(x) - f(y)| \le K|x-y|^\alpha, K>0 $

    mit einem Exponenten Alpha größer als 1/2 genügt. Es ist sogar ausreichend, daß f einer Hölder-Bedingung mit Alpha ist größer 0 genügt, wenn zusätzlich vorausgesetzt wird, daß f von beschränkter Variation ist.

    Wenn die Fourier-Reihe absolut konvergent ist, kann man sie in eine Quadraturformel QN einsetzten und die Summationsreihenfolge vertauschen:


    $ Q_Nf = \sum_{m\in Z} c_m Q_N(e^{2\pi imx}) c_0 = \int _0^1f(x)e^{-2\pi i0x}dx = \int_0^1 f(x)dx = If $

    erhält man eine Fehlerdarstellung für QN


    $Q_Nf -If = \sum_{m\in Z {\rem ohne} 0} c_m Q_N (e^{2\pi imx}) $

    Die in dieser Hinsicht optimale Quadraturformeln sind die um V Element des Intervalls [0,1] versetzten Trapezregeln


    $T_N(v)f = \frac{1}{N} \sum _{i=0}^{N-i} f({\rem fraction }(\frac{i}{N}+ v)) $

    wobei die Funktion den gebrochenen Anteil einer reellen Zahl liefert. Folglich kann der Fehler der Trapezregel durch


    $ T_N(v)f -If = \sum _{k\in {\rem ohne} 0}c_{kN}T_N(v)(e^{2\pi ikNx}) $

    dargestellt werden.

    7.5.5.3. Multivariate Integrationsformeln für periodische Integranden

    Es wird die Annahme getroffen, daß f.Rn->R periodisch von Periode 1 ist, daß also


    $ f(x) = f(x+y) {\rem für, \alle,} x \in R {\rem und} z\in Z $

    gilt und daß f in Form einer absolut konvergenten multivariaten Fourier-Reihe


    $ f(x) = \sum_{m\in Z_n} c_m e^{2\pi imx}$

    mit den Fourier-Koeffizienten


    $ c_M 0 \int_Cf(x) e^{-2\pi imx}dx $

    dargestellt werden kann, wobei m*x das innere Produkt der Vektoren m und x symbolisiert.

    Um QN nach dem dimensionalen Vorbild zu einer effizienten Formel zu machen, ist sie so zu konstruieren, daß möglichst viele Funktionen, für die der entsprechende Fourier-Koeffizient cD "groß ist, auf Null abgebildet werden. Die Schwierigkeit liegt darin, daß das Abklingen der mehrdimensionalen Fourier-Koeffizienten ein wesentlich komplizierter zu charakterisierendes, vom genauen Grad der Glattheit von f abhängiges Verhalten zeigt. Eine Anordnung, die das Abklingverhalten mehrdimensionaler Fourier-Koeffizienten für alle glatten Funktionen charakterisert, gibt es aber nicht.

    7.5.5.4. Gitterpunkt-Formeln

    ein Gitter L ist eine Teilmenge des RN mit folgenden Eigenschaften:

    1. wenn x1 und x2 zu L gehören, so trifft die auch für x1+x2 und x1-x2 zu
    2. enthält n linear unabhängige Punkte
    3. 0 ist ein isolierter Punkt von L, es gibt somit eine Umgebung von 0, deren Durchschnitt mit L nur 0 enthält

    Ein Integrationsgitter L des Rn ist ein Gitter, das Zn als Teilgitter enthält d.h. Zn echte Obermenge von L . Eine Gitterpunkt-Formel für die numerische Integration von f : o,1)n -> R ist eine multivariate Integrationsformel mit gleichen Gewichten w0 =w1 =...= wn-1 = 1/N


    $ Q_Nf := \frac{1}{N} \sum_{i=0}^{N-1} f(x_i) $

    deren Abszissen x0,..,xN-1 jene Punkte eines Integrationsgitters L sind, die innerhalb des Würfels Wn (0,1)n liegen.

    Die Abszissenmenge A(L) einer Gitterpunkt-Formel ist durch


    $ A(L) := (x_0,...,x_N-1) = L\cap W_n $

    gegeben. Jede Abszissenmenge ist wegen 0 Element von L nicht leer. Außerdem ist A(L) eine endliche Menge, weil L nur isolierte Punkte enthält.

    Die sogenannte Methode der guten Gitterpunkte ist die mehrdimensionale Verallgemeinerung der versetzten Trapezregeln


    $ Q_Nf := \frac{1}{N} \sum_{i=0}^{N-1}f({\rem fraction}(\frac{i}{N}p)) $

    7.5.5.5. Darstellung von Gitterpunkt-Formeln in k-Zyklus-Form

    durch Verallgemeinerung des Darstellung für die Produkt- Trapezregel bzw. der Methode der guten Gitterpunkte.

    Für jede Kombination der k ganzzahligen Vektoren z1,...,zk Elemente von Zn und den k Zahlen N1,...,Nk Elemente von N stellt die Menge


    $ L := (\frac{i_1}{N_1}z_1 + ... + \frac{i_k}{N_k} z_k + z : i_j = 0,1,..., N_j-1, j = 1,2,..,k z\in Z^n ) $

    ein Integrationsgitter dar. Die Abszissenmenge der entsprechenden Gitterpunkt- Formel ist durch


    $ A(L) = ({\rem fraction} ( \frac{i_1}{N_1}z_1 + ... + \frac{i_k}{N_k}z_k ) : i_j = 0,1,...,N_j-1, j = 1,2,...,k ) $

    gegeben.

    7.5.5.6. Verfahrensfehler der Gitterpunkt-Formeln

    Für Integrationsgitter L ist der Verfahrensfehler der entsprechenden Gitterpunkt- Formel Qn durch


    $ Q_Nf - IF = \sum _{m\in L^\tau {\rem ohne} 0}c_m $

    gegeben. Der Verfahrensfehler der versetzten Gitterpunkt-Formel QN(v) ist


    $ Q_N(v)f - If = \sum_{m\in L^\tau {\rem ohne} 0 } e^{2\pi imv] c_m$

    wobei L Tau das duale Gitter von L bezeichnet

    7.5.5.7. Korobov-Räume

    Menge aller Funktionen f ,deren Fourier-Koiffizienten cm der Ungleichung genügen, bezeichnet man mit Ena(c), die Vereinigung der Funktionenklassen { Ena(c) : c El. R+ } mit Ena


    $ P_\alpha(Q_N) := \sum_{ m\in L _\tau {\rem ohne} 0} \frac{1}{(\bar(m)_1...\bar(m)_n)^\alpha} $

    7.5.5.8. Konvergenz von Gitterpunkt-Formeln

    wenn Integrand f einem der Korobov-Räume angehört, lassen sich Aussagen über die Konvergenzgeschwindigkeit QNf -> If für N -> unendl. einer Folge {QN} von Gitterpunkt-Formeln machen. Mit Definition


    $ E_n^\alpha := \cup_{c\in R_+} E^\alpha_n (c)$

    erhält man unmittelbar die Fehlerabschätzung


    $ |Q_Nf - If| \le \sum_{m\in L^tau {\rem ohne} 0} \frac{c}{(\bar(m)_1...\bar(m)_n)^\apha} = cP_\alpha(Q_N) $

    Zu beliebig vorgegebenen a > 1 und n >= 2 existiert für jede natürliche Zahl N eine N-punktige Gitterpunktformel QN, so daß


    $ P_\alpha(Q_N) \le d(n,\aplha) \frac{({\rem log}N)^{c(n,\aplha)}{N^\apha} $

    gilt, wobei c und d und a , nicht aber von N abhängen.

    c*Pa(QN) ist der ungünstigste Integrationsfehler für Integranden f El. Ena (c).für f El. Ena (c) gilt, daß es für jede Dimension n eine Folge von Gitterpunkt- Formeln {QN} gibt, für das asymptotische Verhalten des Integrationsfehler durch


    $ |Q_Nf - If| = O (\frac{({\rem log}N)^\alpha}{N^\apha}) {\rem für} N\rightarrow \un $

    charakterisiert werden kann.

    7.5.5.9. Praktisch verwendbare Gitterpunkt-Formeln

    Gitterpunkt-Formeln müssen mit Hilfe von Suchverfahren am Computer ermittelt werden . Suchverfahren müssen auf bestimmte Klassen von Gitterpunkt-Formeln eingeschränkt werden. Problem: möglichst kleine Formelklassen zu finden, die mit möglichst großer Wahrscheinlichkeit effiziente Gitterpunkt-Formeln enthalten.

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