Approximation durch Zonotope

In diesem Paragraphen wollen wir an das Problem des fünften Paragraphen anknüpfen.
Die Ungleichung (III.5.8) von Betke-McMullen benützt auf der linken Seite den Ausdruck:

$${\mathcal F}_n({\mathbf u}):=\vert \frac{1}{\omega_d} \cdot... ...\sum_{i=1}^n \vert {\mathbf x}_i \cdot {\mathbf u}\vert \Vert$$ (3.36)

Dieser Ausdruck bezeichnet den Fehler der Approximation des Cauchy'schen Oberflächenintegrales durch dessen korrespondierende Summe [55].
Die in diesem Ausdruck auftretende Summe ist gleich der $2\kappa_{d-1}/\omega_d$-fachen Stützfunktion des Zonotopes Z mit Generator $\{{\mathbf x}_1,...,{\mathbf x}_n \}$, das Integral ist nach (II.5) gleich $2\kappa_{d-1}$.
Daher ist ${\mathcal F}_n({\mathbf u})=(\omega_d/2\kappa_{d-1}) \cdot \vert 1-{\mathit h}({\mathbf u})\vert$ gleich einer Konstanten mal der Differenz von Kugelradius und Abstand des Zonotopes in Richtung ${\mathbf u}$. Aus (III.5) folgt [ ${\mathbf u} \in S^{d-1}$ ]:

$$\eta(B^d,Z)= (\omega_d / 2\kappa_{d-2}) \cdot \sup_{{\mathbf u}} {\mathcal F}({\mathbf u}).$$ (3.37)

Die Funktion $f: S^{d-1} \to [-1,+1]: {\mathbf x} \to {\mathbf x} \cdot {\mathbf u}$ kann als Orthogonalprojektion von $S^{d-1}$ auf die Linie [-1,+1] betrachtet werden.
Diese Projektion soll so ''gestört'' werden, daß das Maß einer beliebigen sphärischen Kappe

$${\mathbf{\mathit C}}_t := \{{\mathbf x} \in S^{d-1}: {\math... ...\mathbf x} \in S^{d-1}: f_{{\mathbf u}}({\mathbf x})\geq t \}$$

mit Mittelpunkt ${\mathbf u}$ invariant bleibt.
Die Oberfläche $\omega$ von ${\mathbf{\mathit C}}_t$ ist [55] gegeben durch das Integral:

$\omega( {\mathbf{\mathit C}}_t ) = \omega_{d-1} \cdot \int_{-1}^{+1} (1-\tau^2)^{(d-3)/2} {\mathit d}\tau$, für d = 3 ist dies $\frac{1}{2} \cdot (1-t)$.

Es ist nun ${\mathit g}(t):= \omega^*({\mathbf{\mathit C}}_t):=\omega({\mathbf{\mathit C}}_t)/\omega_d$ eine streng fallende Funktion, die [-1,+1] auf [0,1] abbildet und die für $s>t$ stets die Gleichung $\omega^*({\mathbf{\mathit C}}_s \backslash {\mathbf{\mathit C}}_t) = {\mathit g}(s)-{\mathit g}(t)$ erfüllt. Die Funktion ${\mathit q}:= {\mathit g} \circ f_{{\mathbf u}}$ bildet $S^{d-1}$ auf [0,1] ab und ist in folgendem Sinne maßtreu:
für jedes Intervall ${\mathit I} \subset [0,1]$ und für das Lebesguemaß $\lambda$ gilt:

$$\omega ({\mathit q}^{-1}({\mathit I} ))/\omega_d = \omega^*({\mathit q}^{-1}({\mathit I} )) = \lambda({\mathit I}).$$ (3.38)

Diese Maßtreue ist ersichtlich aus:

$$\omega^* ({\mathit q}^{-1} ([t,s])) = \omega^* (f_{{\math... ...mathbf u}}^{-1} ([{\mathit g}^{-1}(t),{\mathit g}^{-1}(s)]))$$

$$= \omega^* ({\mathbf{\mathit C}}_{\mathit g^{-1}(t)} \\ ... ...t))-{\mathit g}({\mathit g}^{-1}(s)) = s-t = \lambda([s,t]).$$

Wegen ${\mathit g}^{-1} \circ {\mathit q} = f$ impliziert die Maßtreue:

$$\int_{S^{d-1}} \vert f_{{\mathbf u}}(x) \vert {\mathit d}\o... ...) = \int_0^1 \vert {\mathit g}^{-1}(z) \vert {\mathit d}z .$$

Um dies einsehen zu können, benötigt man den Integraltransformationssatz der Maßtheorie:
Es seien $(\Omega_0,{\mathcal B}_0)$ und $(\Omega_1,{\mathcal B}_1)$ zwei Meßräume, $\mu_0$ sei ein Maß auf $(\Omega_0,{\mathcal B}_0)$, ${\mathit g}: (\Omega_0,{\mathcal B}_0 ) \to (\Omega_1,{\mathcal B}_1)$ und $f: (\Omega_1,{\mathcal B}_1) \to {\rm I\mkern-3mu R}$ seien zwei Funktionen. Dann ist:

$$\int_{\Omega_0} f \circ {\mathit g}(t) {\mathit d}t = \in... ...d}t = \int_{\Omega_1} f(x) {\mathit d}({\mathit g}(\mu_0)).$$

Das durch $\mu_1(A):= \mu_0(g^{-1}(A)) \; \forall A \in {\mathcal B}$ definierte Maß nennt man Bildmaß von $\mu_0$ unter der Abbildung g.

Setzen wir $z_i:= {\mathit q}({\mathbf x}_i)$, so ist: ${\mathbf x}_i \cdot {\mathbf u} = f_{{\mathbf u}}({\mathbf x}_i) = {\mathit g}^{-1}(z_i)$. Aufgrund der Invarianzgleichung schreibt sich ${\mathcal F}_n({\mathbf u})$ an als:

$${\mathcal F}_n({\mathbf u}) = \vert \frac{1}{\omega_d} \cdo... ...m_{i=1}^n \vert {\mathbf x}_i \cdot {\mathbf u} \vert \vert =$$

$$\vert \int_0^1 \vert {\mathit g}^{-1}(z) \vert {\mathit d}z... ...} \cdot \sum_{i=1}^n \vert {\mathit g}^{-1}(z_i) \vert \vert.$$

Das bedeutet, daß wir ${\mathcal F}_n({\mathbf u})$ als den Fehler einer eindimensionalen numerischen Integration betrachten können, auf den wir die Ungleichung von Koksma (II.1) ( s.[48]) anwenden.
Die totale Variation ${\mathit V}({\mathit f})$ einer stetigen und monotonen Funktion auf einem Intervall ist gleich der Differenz der Beträge der Intervallenden. In unserem Fall ist ${\mathit V}(g) = 2$ und wir erhalten aus der Ungleichung von Koksma [55]:

$$E_n({\mathbf u}) \leq 2 \cdot D^*(z_1,..,z_n)$$

Also ist der Fehler kleiner gleich der zweifachen Sterndiskrepanz in Bezug auf Intervalle der Form [0,a] mit $0 \leq a \leq 1$. Da wir mit $t = {\mathit g}^{-1}(a)$ auch ${\mathit q}^{-1}([0,a]) = {\mathbf{\mathit C}}_t$ und $a = \omega({\mathbf{\mathit C}}_t)$ haben, gilt mit ${\mathcal Z} := \{z_1,...,z_n \}$ und $a \in [0,1]$:

$$D^*({\mathcal Z}) = \sup_{a} \vert \char93 ( {\mathcal Z} ... ...3 ( {\mathcal Z} \cap {\mathit q}^{-1}([0,a])) /n - a \vert$$

$$= \sup_{t \in [0,1] } \vert \char93 ({\mathcal Z} \cap {\m... ...thbf{\mathit C}}_t) - \omega({\mathbf{\mathit C}}_t) \vert$$

Also können wir ${\mathcal F}_n({\mathbf u})$ abschätzen durch die sphärische Kappendiskrepanz von (II.2). Wir brauchen nur das dortige Ergebnis zu übernehmen und erhalten so den Satz:
Für jede natürliche Zahl $n > 0$ gibt es eine Menge von Punkten $\{P_1,..,P_n \} \in S^{d-1}$, sodaß gilt:

$$\zeta(n,d) \leq c_d \cdot n^{1/2-1/(2d-2)} \cdot (\log n)^{1/2}.$$ (3.39)

Die Beck'sche Methode kann man aber auch direkt auf unsere Aufgabenstellung anwenden [11]:
Für jede beliebige ganze Zahl n sei $\eta = n^{-1/(d-1)}$ Wir zerlegen analog zu (II.2) die $S^{d-1}$ in n kompakte, zusammenhängende und paarweise disjunkte Mengen $\{Q_l\}_{l=1}^n$. Das Lebesguemaß von jeder dieser Mengen sei $\ll n$ und ihr Durchmesser sei $\leq const \cdot \eta$.
In jedem $Q_l$ wählen wir zufällig und unabhängig voneinander d+2 Punkte aus. Dann hat für jede stetige Funktion f auf $S^{d-1}$ bei geeignetem Maß $\mu_l$ auf $Q_l$ der Ausdruck

$${\mathit h}({\mathcal P},f) := \sum_{i=1}^{d+2} \lambda(Q_l)\cdot f({\mathit p}_l)-\int_{Q_l} f d\mu_l$$

einen Betrag $\leq const \cdot \eta$.
Durch die Anwendung der Bernstein'schen Ungleichung und durch Einsetzen der obigen Werte erhält man den Satz [11]:
Für $n \geq 3$ gibt es stets ein Zonotop und eine Konstante $c_d$ mit:

$$\zeta( n,d ) \leq c_d \cdot n^{-(d+2)/(2d-2)} \cdot \sqrt{ \log n }$$ (3.40)

Die Güte der gefundenen Abschätzung bestätigt uns :
s gibt für $n \geq 3$ stets eine Konstante $C_d$ und ein Zonotop mit:

$$\zeta( n,d ) \geq C_d \cdot n^{-(d+2)/(2d-2)}$$ (3.41)

Zum Beweis ( s.[12],[13]) verwenden wir ein positives und symmetrisches Maß $\rho$ auf $S^{d-1}$. Das heißt, es ist für alle ${\mathbf x}$ auf der $S^{d-1}: \rho({\mathbf x})$ größer Null und weiters ist $\int_{S^{d-1}} {\mathbf x} \cdot \rho({\mathbf x}) {\mathit d}{\mathbf x} = 0$.
Es ist dann ${\mathit h}({\mathbf x}):= \int_{S^{d-1}} \vert{\mathbf x} \cdot {\mathbf y} \vert \rho ({\mathit d}{\mathbf y})$ die Stützfunktiom eines konvexen Körpers. Ist $\rho$ ein diskretes Maß, so ist ${\mathit h}$ die Stützfunktion eines Zonotopes.
Die Funktion ${\mathit h}$ läßt sich in der Theorie der sphärischen Fourieranalyse [67] darstellen als $\sum Y_k$. Die Funktion $Y_k$ ist dabei eine sphärische harmonische Funktion von Ordnung k. Die $Y_k$'s erfüllen folgende Orthogonalitätsrelation [67]:

$$\int_{S^{d-1}} Y_n({\mathbf x}) \cdot Y_m({\mathbf x}) {\mathit d}\omega({\mathbf x}) = 0 \; f\uml {u}r \, n \neq m.$$

Der Theorie der sphärischen harmonischen Analyse entnimmt man [12,13,67], daß man das Maß $\rho$ formal anschreiben kann als:

$$\rho = \sum \lambda_k \cdot Y_k$$

Die $\lambda_k$'s sind dabei geeignete Gewichte der Ordnung ${\mathit O}(k^{(d/2)+1})$.
Für $0\leq r<1$ setzen wir $\rho_r:= \sum r^k \cdot \lambda_k \cdot Y_k$ [12]. Aufgrund der Orthogonalität der $Y_k$'s gilt der Satz von Pythagoras und damit:

$$\sum \Vert Y_k-Y_k'\Vert^2_2 = \Vert {\mathit h}-{\mathit h}'\Vert^2_2$$

Es sei $\rho'$ ein zweites Maß auf $S^{d-1}$, das dieselben Eigenschaften wir $\rho$ besitzt. Analog zu oben bilden wir die zu $\rho'$ zugehörigen Funktionen ${\mathit h}'$,$\rho_k'$ und $Y_k'$ und können dann das Quadrat des $L_2$-Abstandes dieser beiden Maße abschätzen durch:

$$\parallel \rho_r - \rho_r' \parallel _2^2 =$$

$$= \int_{S^{d-1}} (\rho_r -\rho_r')^2 {\mathit d}{\mathit d... ... \sum r^k \cdot \lambda_k \cdot Y_k')^2 {\mathit d}\omega =$$

$$= \int_{S^{d-1}} [\sum r^k \cdot \lambda_k \cdot (Y_k-Y_k')... ... [r^k \cdot \lambda_k \cdot (Y_k-Y_k')] {\mathit d}\omega =$$

$$\leq \sum (r^k \cdot \lambda_k )^2 \cdot \int_{S^{d-1}}... ...cdot \lambda_k )^2 \cdot \parallel Y_k-Y_k' \parallel ^2 \leq$$

$$\leq \sum \max_k (r^k \cdot \lambda_k )^2 \cdot \parallel Y... ...cdot \lambda_k )^2 \cdot \sum \parallel Y_k-Y_k' \parallel ^2$$

$$= \max_k (r^k \cdot \lambda_k )^2 \cdot \parallel {\mathit h}-{\mathit h}' \parallel _2^2.$$

Also ist:

$$\parallel \rho_r - \rho'_r \parallel \leq \max_k (r^k \cdo... ...bda_k)^2 \cdot \parallel {\mathit h} - {\mathit h}' \parallel$$ (3.42)

Wegen $\lambda_k = {\mathit O}(k^{(d/2)+1})$ läßt sich das Maximum abschätzen durch:

$$\max_k (r^k \cdot \lambda_k ) \leq C \cdot \max_k (r^k \cdot k^{d+2})$$

Die Funktion $r^k \cdot k^{d+2}$ hat ihr Maximum an der Stelle $\frac{d+2}{-\log r}$ wie man durch Differentiation und aus Monotonieüberlegungen ersieht. (Man beachte, daß für $r < 1$ der Logarithmus negativ, und damit der Ausdruck $-\log r$ positiv ist.) Es ist somit:

$$\max_k (r^k \cdot k^{d+2} ) \leq$$

$$(r^{\frac{d+2}{-\log r}}) \cdot (\frac{d+2}{-\log r})^{d+2... ...+2)} \cdot (d+2)^{(d+2)} \cdot (\frac{1}{-\log r})^{d+2} =$$

$$= (e^{-\log r \cdot (1/\log r) })^{(d+2)} \cdot (d+2)^{(d+2)} \cdot (\frac{1}{-\log r})^{d+2} =$$

$$= (e^{-(d+2)} \cdot (d+2)^{(d+2)} \cdot (-\frac{1}{\log r})^{d+2} = C \cdot (-\frac{1}{\log r})^{d+2} \leq$$

$$\leq C \cdot \Bigl( \frac{1}{1-r} \Bigr) ^{d+2}.$$

Da die Funktion $x - \log x$ auf [0,1] monoton fällt, ist $1 \leq r - \log r$ und damit:

$$(-1/\log r)^{d+2} \leq (1/1-r)^{d+2}.$$

Also haben wir:

$$\parallel \rho_r - \rho'_r \parallel \leq C_d \cdot (1-r)^{-(d+2)} \cdot \parallel {\mathit h} - {\mathit h}' \parallel$$ (3.43)

Es sei nun $\delta$ das durch ${\mathcal P}=\{P_1,..,P_n\}$ induzierte Maß. Es hat für $P \notin {\mathcal P}$ den Wert Null und für $P_i \in {\mathcal P}$ ist $\delta = \alpha$. Diese Werte $\alpha_i$ sind alle positiv und so gewählt, daß gilt: $\sum \alpha_i = 1$. Für das induzierte Maß $\delta$ und das Oberflächenmaß $\omega$ kann man zeigen [12,13], daß für $(1-r)^{-1} \geq C \cdot n^{1/(d-1)}$ mit einer Konstanten C gilt:

$$\parallel \omega_r - \delta_r \parallel^2 > 1.$$

Damit können wir den Beweis von (3.41) vervollständigen. Denn es gilt [12,13]:

$$\zeta(n,d) = \inf_{\eta} \{\eta(B^d,Z) \} \geq$$

$$\parallel \int_{S^{d-1}} \vert {\mathbf x} \cdot {\mathbf ... ...{\mathit h}_{\omega} - {\mathit h}_{\delta} \parallel _2 \geq$$

$$C_d \cdot (1-r)^{(d+2)/2} \cdot \parallel \omega_r - \delta... ...1 \geq C_d \cdot C \cdot n^{\frac{d+2}{2(d-1)}} \diamondsuit$$