Nächste Seite: Kugelkappendiskrepanz, Methode von Beck Aufwärts: Diskrepanzen auf der Kugel Vorherige Seite: Diskrepanzen auf der Kugel Inhalt

Diskrepanzen

Im zweiten Kapitel wollen wir Funktionale untersuchen, die die ''Gleichmäßigkeit'' einer Verteilung von Punkten auf der Kugel ''messen''. Diese Funktionale wollen wir Gleichmäßigkeitsmaße nennen, obwohl sie normalerweise kein Maß im Sinne der Maßtheorie liefern.

Ein zentraler Begriff wird der Begriff der Diskrepanz sein, der nun definiert werden sollen [48]:
(0) Maß ist in dieser Arbeit stets ein Maß im Sinne der Maßtheorie [im Gegensatz zu ''Gleichmäßigkeitsmaß '' ]
(1) Es sei ${\mathbf{\mathit x_n}} = (x)_{n=1}^{\infty}$ eine unendliche Folge von Punkten einer kompakten Menge X. Weiters sei $\mu$ ein Maß auf X. Die Folge heißt $\mu$ - gleichverteilt auf X, wenn für alle stetigen Funktionen ${\mathit f]:X \rightarrow {\rm I\mkern-3mu R}}$ gilt:

$\begin{displaymath} \lim_{N \rightarrow \infty} \frac{1}{N} \cdot \sum_{k=1}^N {\mathit f}(x_n) = \int_X f \; {\mathit d} \mu. \end{displaymath}$

(2.1)

(2) Ist auf einer kompakten Menge X mit Maß $\mu$ eine Folge ${\mathbf{\mathit x}} = (x_n)^{\infty}_{n=1}$ und ein Funktional $D_N = D_N({\mathbf{\mathit x}})$ gegeben, so nennen wir

eine Diskrepanz, wenn gilt:

$\begin{displaymath} {\mathbf{\mathit x}} \; \mathtt{ ist } \, \mu-\mathtt{ glei... ...ad \lim_{N \rightarrow \infty} D_N({\mathbf{\mathit x}}) = 0. \end{displaymath}$

(2.2)

Diese Definition ist zwar nicht allgemein üblich, aber für unsere Zwecke vollkommend ausreichend. Nun ein paar Beispiele:

Es sei X = [0,1]. sei die Indikatorfunktion des Bereiches B, $\lambda$ sei das Lebesguemaß auf ${\rm I\mkern-3mu R}$ und ${\mathbf{\mathit x}}=(x_n)$ sei eine Folge reeller Zahlen. Unter einer Diskrepanz bis zum N-ten Glied versteht man dann üblicherweise [48] das Funktional

$\begin{displaymath} D_N({\mathbf{\mathit x}}):= \sup_{I \subset [0,1]} \vert... ..._{k=1} \\ 1_I(x_n) - \int_I \\ 1_{I} {\mathit d}x \vert = \end{displaymath}$

$\begin{displaymath} \sup_{I \subset [0,1]} \vert \frac{1}{N} \cdot \char93 \{x_i \in I:1 \leq i \leq N \}-\lambda(I)\vert = \end{displaymath}$

$\begin{displaymath} = \frac{1}{N} \cdot \sup_{I \subset [0,1]} \vert \char93 \{x_i \in I:1 \leq i \leq N \} - N \cdot \lambda(I)\vert . \end{displaymath}$

Dazu analog kann man in jedem kompakten Raum X mit Maß $\mu$ eine Diskrepanz

definieren durch:

$\begin{displaymath} D_N = \frac{1}{N} \cdot \sup_{I \subset [0,1]} \vert \char93 \{ x_i \in I: 1 \leq i \leq N \} - N \cdot \mu(I)\vert \end{displaymath}$

(2.3)

Eine Diskrepanz dieser Art werden wir im folgenden Paragraphen betrachten.
Dies ist jedoch nicht die einzig mögliche Definition einer Diskrepanz auf [0,1]. Ebenfalls von Bedeutung ist die Sterndiskrepanz

$\begin{displaymath} {\mathit D}^*_N({\mathbf{\mathit x}}) := \sup_{0 \leq X \le... ...cdot \char93 \{x_i \in [0,x]: 1 \leq i \leq N \}-x \vert. \end{displaymath}$

Sie ist mit der Diskrepanz

durch folgende Ungleichung verbunden:

$\begin{displaymath} {\mathit D}_n^*({\mathbf{\mathit x}}) \leq {\mathit D}_n({\... ...athit x}}) \leq 2 \cdot {\mathit D}^*_n({\mathbf{\mathit x}}) \end{displaymath}$

(2.4)

Mit Hilfe der Sterndiskrepanz kann man den Fehler einer eindimensionalen numerischen Integration abgeschätzen (Ungleichung von Koksma) [48]:
Ist f eine Funktion beschränkter Variation V(f) auf [0,1], und sind $x_1,..,x_n \in [0,1]$ , so gilt:

$\begin{displaymath} \vert \frac{1}{n} \sum_{k=1}^n {\mathit f}(x_k) - \int_0... ...\vert \leq {\mathit V}({\mathit f}) \cdot {\mathit D_n^*}. \end{displaymath}$

(2.5)

Als ein weiteres Beispiel definieren wir uns auf jedem separablen, zusammenhängenden, metrischen Raum $(\Omega,\delta)$ mit $\char93 \Omega > 1$ eine Diskrepanz mit Hilfe der Wahrscheinlichkeitstheorie [56]:
Für jede Teilmenge $A \subset \Omega$ und für jedes $\epsilon > 0$ sei die Menge $A^{\epsilon} :=\{ {\mathit P} \in \Omega : \delta({\mathit P},A) < \epsilon \}$ der $\epsilon$ -Bereich um A und $A^{-\epsilon}:= \Omega \backslash (\Omega \backslash A )^{\epsilon}$ .
Bezeichnet ${\mathcal B}$ die $\sigma$ -Algebra der Borelmengen über $\Omega$ und sind ${\mathbf{\mathit P}}$ und ${\mathbf{\mathit Q}}$ zwei Wahrscheinlichkeitsmaße auf dem Meßraum $(\Omega,{\mathcal B})$ , so wird mit $d_{LV} := \inf \{\epsilon>0 : {\mathbf{\mathit P}}(A) \leq {\mathbf{\mathit Q}}(A^\epsilon) \forall A \in {\mathcal B}^{\epsilon} \}$ die Lokalvariationsmetrik zwischen ${\mathbf{\mathit P}}$ und ${\mathbf{\mathit Q}}$ definiert [56].
Es sei ${\mathcal P}=\{P_1,..,P_n\}$ eine endliche Folge in $\Omega$ , es sei $\delta_P(x):= 1$ für x = P und 0 sonst und es sei:

$\begin{displaymath} {\mathbf{\mathit P}}_{{\mathcal P}} := \sum_{i=1}^n \frac{1}{n} \cdot \delta_{P_i}. \end{displaymath}$

$D_{LV} := d_{LV}({\mathbf{\mathit P}}_{{\mathcal P}},{\mathbf{\mathit P}}$ nennen wir dann LV-Diskrepanz von ${\mathbf{\mathit P}}$ [bzgl. ${\mathcal P}$ ].
Die Autoren in [56] zeigen, daß die Bedingung (1) erfüllt wird, wenn gilt: $\inf_{{\mathit P}\in \Omega} B({\mathit P},\epsilon) = 0 \Leftrightarrow \epsilon = 0.$ Dabei ist $B({\mathit P},\epsilon)$ die $\epsilon$ -Kugel um den Punkt P des Raumes $\Omega$ .
Das Gleichmäßigkeitsmaß $D_{LV}$ läßt sich auch so formulieren: Ist ${\mathcal P}=\{P_1,..,P_n\}$ , und bezeichnet ${\mathcal T}$ die Menge aller nichtleeren Teilmengen von ${\mathcal P}$ , so ist

$\begin{displaymath} D_{LV} = \inf \{ \epsilon > 0 : {\mathit Q}_{{\mathcal P}}... ... {\mathit Q}(B^{\epsilon}) \; \forall B \in {\mathcal T} \}. \end{displaymath}$

Setzen wir $\Omega = S^{d-1}$ , so können wir die die Gleichung $D_{LV} = \rho$ so interpretieren: Ziehen wir um die Punkte $\{P_1,..,P_n\}$ Kugeln mit Radius $\rho$ , so überdecken je k dieser Kugeln einen Teil der $S^{d-1}$ mit Maß $\geq k/n$ und $\rho$ ist die kleinstmögliche Zahl, die eine derartige Überdeckung erlaubt.
Die Diskrepanz $D_{LV}$ hat auch einen Bezug zum Tammes'schen Problem. Denn $D_{LV}$ ist das Infimum der $\epsilon > 0$ ist, für die gilt:
Sind von n Austrittöffnungen eines Pollenkornes nur mehr k [ $1 \leq k \leq n$ ] funktionstüchtig, so ist die Wahrscheinlichkeit, daß sich innerhalb einer $\epsilon$ -Umgebung von dem (zufälligen) Haftpunkt des Pollenkornes eine funktionsfähige Keimzelle befindet, größer gleich

, und das unabhängig davon, welche Austrittöffnungen ausgefallen sind.
Die bisher entdeckten Punktanordnungen, für die $D_{LV}$ minimal ist, sind identisch mit den optimalen Anordnungen des Überdeckungsproblems [56]. Interessant wäre es, die Frage, ob diese beiden Fragestellungen immer dasselbe Resultat liefern, beantworten zu können.

Nächste Seite: Kugelkappendiskrepanz, Methode von Beck Aufwärts: Diskrepanzen auf der Kugel Vorherige Seite: Diskrepanzen auf der Kugel Inhalt

2004-03-25