Sphärische Designs

Wie bereits bemerkt wurde (2.4), besteht ein Zusammenhang zwischen der Diskrepanztheorie und der numerischen Integration.
In der Numerik will man vor allem die Polynome, die ' Grundbausteine' der Funktionen, exakt zu berechnen. Daher sucht man üblicherweise nach Stützpunkten, bei denen der Fehler ${\mathcal F}$ genau dann Null wird, wenn P ein Polynom ist.
Eine Menge $\{P_1,..,P_n\} \subseteq S^{d-1}$ soll daher d-dimensionales sphärisches t-Design ( $t \in {\rm I\mkern-3mu N}$) heißen, wenn für jedes Polynom P mit Grad $< t$ gilt:

$$\frac{1}{\omega_d} \cdot \int_{S^{d-1}}{\mathit P}({\mathbf... ... = \frac{1}{n} \cdot \sum_{i=1}^n {\mathit P}({\mathbf x}_i)$$

Die Existenz sphärischer Designs wurde erst 1984 in [77] nachgewiesen. In [23] und in [33] wird gezeigt, daß für ein festes t die Anzahl der Punkte, für die ein sphärisches Design existiert, eine untere Schranke von der Größenordnung $t^{d-1}$ besitzt. Weiters sei erwähnt, daß die Ecken eines Fußballes kein Design bilden [34].
Wir wollen jetzt ansatzweise die Existenz eines sphärischen t-Designs für $n \geq c_d \cdot t^{12 \cdot d}$ beweisen [98]. Weiters wollen wir zeigen, daß auch für rechteckige Bereiche der $S^{d-1}$ Designs existieren ( s.[99],Lemma 3). Diese Aussagen sind Korollare zu folgendem Satz der numerischen Integration [98],[99]:
Es sei $w(x) \geq 0$ eine auf [-1,+1] definierte und integrable Gewichtsfunktion für die mit $L_1 \geq 1 \geq L_2 \geq 0$ und $\beta \geq 0$ gilt:

$$\int_{-1}^{+1}{\mathit w}(x) {\mathit d}x = 1$$

$$L_2 \cdot (1-\vert x \vert^{\beta} ) \leq {\mathit w}(x) \leq L_1$$

$\phi := \{f_1,...,f_s \}$ sei eine Klasse 3-mal stetig differentierbarer Funktionen auf [-1,+1], deren erste Ableitungen in Bezug zur Gewichtsfunktion w orthogonal sind. Das heißt:

$$\int_{-1}^{+1} f'_{\mu}(x) \cdot f'_{\nu}(x) \cdot {\mathit... ...0 & \qquad f\uml {u}r \; \mu \neq \nu \end{array} \right.$$ (2.14)

Es sei für die Funktionen dieser Klasse:

$$K:= \max_{\mu,\nu} \max_{[-1,+1]} (\vert f'_{\mu} \vert ,... ...'_{\nu} )' \vert, \vert (f'_{\mu} \cdot f'_{\nu})'' \vert )$$

sowie

$$C:= \max_{-1\leq x \leq +1} \max_{\mu = 1...s} (\vert f'_{\mu} \vert,\vert f''_{\mu} \vert,\vert f'''_{\mu} \vert ).$$

Dann gilt:
(a) Für $n \geq (24 \cdot s \cdot K^2 \cdot L_1/L_2)^{\beta+2}$ bzw. $n \geq n_0(s,C,L_1,L_2,\beta)$ gibt es Punkte $-1 < \xi_1 < ... < \xi_n <1$, sodaß für alle $f \in \phi$ gilt:

$$\frac{1}{n} \cdot \sum_{i=1}^n f(\xi_i) = \int_{-1}^{+1} f(x) \cdot {\mathit w}(x) dx$$

(b) Es werde $x_j$ definiert durch die Gleichung:

$$\int_{-1}^{x_j} {\mathit w}(x) {\mathit d}x = j/n$$ (2.15)

Dann können wir annehmen, daß $x_{j-1} < \xi_j < x_j$ und daß gilt:

$$\min (\xi_j - x_{j-1}, x_j - \xi_j ) > \frac{1}{3} \cdot (x_j - x_{j-1} ).$$ (2.16)

Um die gewünschten Korollare zu erhalten, betrachten wir das Polynom ${\mathit P} = {\mathit P}(x_1,..,x_d) = x_1^{k1} \cdot ... \cdot x_d^{kd}$ mit $k_i \geq 0$ und $\sum_{i=0}^d k \leq t$.
Führen wir in der üblichen Weise Polarkoordinaten ein, und setzen wir $u_j := \cos \theta_j$, so gilt:

$$\int_{S^{d-1}}{\mathit P}({\mathbf x}){\mathit d}\omega({\... ...rod_{j=1}^{d-2} I_j = I_{d-1} \cdot \prod_{j=1}^{d-2} I_j$$

mit $I_j := \int_{-1}^{+1} (1-u_j^2)^{(kd+...+k(j+1))} \cdot u_j^{kj} \cdot (1-u_j^2)^{(d-j-2)/2} {\mathit d}u_j.$

Die Anwendung des Satzes auf die spezielle Klasse der Gegenbauerpolynome ergibt, daß es für jede Koordinate $u_j$ eine Menge $A_j$ gibt, für die das Integral $I_j$ durch eine Summe ersetzt werden kann [98].

Es sei $A:=\{(\theta_1,..,\theta{d-2},\varphi)\}$ die Menge der Punkte aus $S^{d-1}$, die entsteht, wenn $\cos \theta_1$,..., $\cos \theta_{d-1}$ und $\varphi$ unabhängig voneinander die Mengen $A_1, A_2, .., A_{d-1}$ durchlaufen. A ist dann ein sphärisches Design der Ordnung t. Daß dazu notwendigerweise $n \geq Const \cdot t^{12 \cdot t^4}$ sein muß, wird in [98] bewiesen. Auch die zweite Aussage kann man als Folgerung des Satzes beweisen [99]. Auch hier muß man man den Satz auf eine spezielle Funktionenklasse $\phi$ anwenden.

Durch die Gleichungen

$T_{2j}(x) = ((1-\cos(\epsilon x))/(\epsilon^2/2)^j)$ und $T_{2j+1} = T_{2j} \cdot \sin(\epsilon x)/\epsilon$.

erhält man eine Menge $\{T_0,..,T_t\}$ von Funktionen. Um $\phi$ zu erhalten muß man nur noch diese Menge orthogonalisieren. Dabei ist $\epsilon$ ein positiver reeller Parameter.

Es sei $D_{\mu} = \{\beta_{1\mu} \leq \theta_{\mu} \leq \beta_{2\mu} \}$ ein rechteckiger Bereich auf $S^{d-1}$. Da man ein größeres Gebiet stets in mehrere Teilgebiete zerlegen kann, können wie den Bereich D als genügend klein annehmen. Dann kann man mit ähnlichen Methoden beweisen, daß es für jeden Bereich $D \subseteq S^{d-1}$ dieser Gestalt eine von D unabhängige, natürliche Zahl $n_0(t,d)$ gibt, sodaß es für jedes (d-1)-Tupel natürlicher Zahlen $(m_1,..,m_{d-1})$ mit $m_j \geq n_0$ eine Menge von $\prod_{j=1}^{d-1} m_j$ Punkten aus D gibt, die ein sphärisches Design der Ordnung t bildet [98].

Für den Satz selbst soll nun eine Beweisskizze folgen. Die exakte Ausführung des Beweises findet sich in [98].
Wir starten bei der natürlichen Annahme, daß die Menge der Interpolationspunkte $-1 < \xi_1 < .. < \xi_n < 1$ eine Verteilung besitzt, die zu der durch die Gewichtsfunktion w induzierten Verteilung ''nahe'' steht, und verwenden dann die folgenden drei Schritte:
(1) Wir zerlegen das Intervall [-1,+1] in n Teilintervalle $I_1=[x_0,x_1]$, $I_1=[x_1,x_2]$,..., $I_n = [x_{n-1},x_n]$ von gleicher w-Länge. Das bedeutet, daß

$$\int_{x_{j-1}}^{x_j}{\mathit w}(x) {\mathit d}x = 1/n$$

sein soll. Klarerweise ist $x_0 = -1$ und $x_n = +1$ zu setzen.
Im Inneren eines jeden Intervalles $I_j$ wählen wir den eindeutig bestimmten Punkt $u_j$, für den gilt:

$$\int_{x_{j-1}}^{x_j} x \cdot {\mathit w}(x) {\mathit d}x = u_j/n$$

(2) Die Menge $\{u_1,..,u_n\}$ benützen wir als Startmenge eines Newton'schen Iterationsprozesses. Das bedeutet, daß die Punkte $u_j$ sukzessive durch die besser approximierenden Punkte $u_j +h_j^{(1)}$ $u_j+h_j^{(1)}+h_j^{(2)}$ .. ersetzt werden. Die Korrekturglieder $h_j^{(l)}$ können [98] mittels Lagrangemethode so gewählt werden, daß $\sum_{j=1}^n ( h_j^{(k)} )^2$ minimal wird. Dabei ist die geforderte w-Orthogonalität nötig, um die auftretenden Korrekturglieder klein halten zu können.
(3) Die Iterationsprozedur erzeugt rekursive Ungleichungen für die Korrekturglieder $h_j^{(l)}$ und für den Fehler

$${\mathcal F} = \max_{\nu =1...s} \vert \frac{1}{n} \cdot ... ..._{-1}^{+1} f_{\nu}(x) \cdot {\mathit w}(x) {\mathit d}x\vert.$$

Da für hinreichend große n der Fehler ${\mathcal F}$ mit wachsendem k nach Null strebt, und da die Grenzpunkte $u_j + \sum_{l=1}^{\infty} h_j^{(k)}$ existieren, paarweise disjunkt sind und in [-1,+1] liegen, können wir den Beweis schließen. $\diamondsuit$