Numerische Integration – Analysis I (Kap. 1-9)

9.5 Numerische Integration

Wie bereits erwähnt wurde, gibt es Integrale, die sich nicht in Ausdrücken der üblichen (den uns bisher bekannten) Funktionen darstellen lassen. Besonderes in diesen Fällen sind folgende Abschätzungen zur approximativen Berechnung von Integralen sehr nützlich. Im nächsten Abschnitt werden wir weitere Beispiele sehen, die die zugrundeliegende Idee des folgenden Satzes in anderen Überlegungen gewinnbringend einsetzen.

Satz 9.56.

Seien $a < b$ reelle Zahlen, $f : [a, b] \to ℝ$ eine Funktion, $n \in ℕ$ , $h = \frac{b - a}{n}$ die Schrittweite und $x_{ℓ} = a + ℓ h$ für $ℓ \in {0, \dots, n}$ .

(a): (Rechtecksregel) Falls $f$ stetig differenzierbar ist, dann gilt $\begin{array}{l} \int_{a}^{b} f (x) d x = h (f (x_{0}) + \dots + f (x_{n - 1})) + F_{1}, \end{array}$
wobei der Fehler $F_{1}$ durch $| F_{1} | \leq \frac{{(b - a)}^{2}}{2 n} \max_{x \in [a, b]} | f^{'} (x) |$ beschränkt ist.
(b): (Sehnentrapezregel) Falls $f$ zweimal stetig differenzierbar ist, dann gilt $\begin{array}{l} \int_{a}^{b} f (x) d x & = h (\frac{f (x_{0}) + f (x_{1})}{2} + \dots + \frac{f (x_{n - 1}) + f (x_{n})}{2}) + F_{2} \\ = \frac{h}{2} (f (x_{0}) + 2 f (x_{1}) + \dots + 2 f (x_{n - 1}) + f (x_{n})) + F_{2}, \end{array}$
wobei der Fehler $F_{2}$ durch $| F_{2} | \leq \frac{{(b - a)}^{3}}{6 n^{2}} \max_{x \in [a, b]} | f^{″} (x) |$ beschränkt ist.
(c): (Simpson-Regel) Falls $f$ viermal stetig differenzierbar ist und $n$ gerade ist, dann gilt $\begin{array}{l} \int_{a}^{b} f (x) d x = \frac{h}{3} (f (x_{0}) + 4 f (x_{1}) + 2 f (x_{2}) & + 4 f (x_{3}) + 2 f (x_{4}) + \dots \\ + 2 f (x_{n - 2}) + 4 f (x_{n - 1}) + f (x_{n}) +) F_{3}, \end{array}$
wobei der Fehler $F_{3}$ durch $| F_{3} | \leq \frac{{(b - a)}^{5}}{45 n^{4}} \max_{x \in [a, b]} | f^{(4)} (x) |$ beschränkt ist.

Insbesondere verhält sich der Fehler für das Rechtecksverfahren wie $O_{f} (n^{- 1})$ für $n \to \infty$ , für das Sehnentrapezverfahren wie $O_{f} (n^{- 2})$ für $n \to \infty$ und für das Simpson-Verfahren wie $O_{f} (n^{- 4})$ für $n \to \infty$ .

Wir möchten anmerken, dass die Konstanten in obigen Abschätzungen nicht optimal sind. Alle drei obigen Approximationsverfahren sind sogenannte Newton-Cotes-Verfahren. Die wesentliche Idee eines solchen Verfahrens ist die folgende: zuerst schreibt man nach Intervalladditivität

\begin{array}{l} \int_{a}^{b} f (x) d x = \sum_{ℓ = 0}^{n - 1} \int_{x_{ℓ}}^{x_{ℓ + 1}} f (x) d x . \end{array}

Nun approximiert man jedes obige Integralstück $\int_{x_{ℓ}}^{x_{ℓ + 1}} f (x) d x$ durch einen Ausdruck der Form $\sum_{k = 1}^{K} w_{k} f (z_{k})$ für Gewichte $w_{1}, \dots, w_{K} \in (0, 1)$ mit $\sum_{k = 1}^{K} w_{k} = 1$ und Stützpunkte $z_{1}, \dots, z_{K} \in [x_{ℓ}, x_{ℓ + 1}]$ . Beispielsweise nimmt man für die Sehnentrapezregel zwei Stützpunkte ( $K = 2$ ), nämlich die beiden Endpunkte des Intervalls $[x_{ℓ}, x_{ℓ + 1}]$ , mit den Gewichten $w_{1} = w_{2} = \frac{1}{2}$ .

Die Summe der Fehler, die auf den Stücken $\int_{x_{ℓ}}^{x_{ℓ + 1}} f (x) d x$ zustandekommen, ergeben dann den Gesamtfehler der Approximation. Obiger Satz gibt demnach an, wie dieser Fehler kontrolliert werden kann.

Vor dem Beweis des obigen Satzes möchten wir kurz erklären, wie sich die Simpson-Regel als Newton-Cotes-Verfahren auffassen lässt. Für die äquidistante Zerlegung des Intervalles $[a, b]$ mit den Punkten $y_{ℓ} = a + ℓ \frac{b - a}{m}$ für $ℓ = 0, \dots, m$ betrachtet man auf $[y_{ℓ}, y_{ℓ + 1}]$ die Gewichte $w_{1} = \frac{1}{6}$ , $w_{2} = \frac{4}{6}$ und $w_{3} = \frac{1}{6}$ und die Stützpunkte $y_{ℓ}$ , $\frac{y_{ℓ} + y_{ℓ + 1}}{2}$ und $y_{ℓ + 1}$ . Das dazugehörige Newton-Cotes-Verfahren ist genau das Simpson-Verfahren (wieso?). Wir wenden uns nun dem Beweis des obigen Satzes zu.

Beweis.

Für (a) verwenden wir den Mittelwertsatz, wonach es zu $ℓ \in {0, \dots, n - 1}$ und $x \in [x_{ℓ}, x_{ℓ + 1}]$ ein $ξ_{x} \in (x_{ℓ}, x_{ℓ + 1})$ gibt mit $f (x) - f (x_{ℓ}) = f^{'} (ξ_{x}) (x - x_{ℓ})$ . Insbesondere gilt

\begin{array}{l} | f (x) - f (x_{ℓ}) | = | f^{'} (ξ_{x}) | (x - x_{ℓ}) \leq (x - x_{ℓ}) \max_{t \in [a, b]} | f^{'} (t) | . \end{array}

Damit erhalten wir

\begin{array}{l} | \int_{x_{ℓ}}^{x_{ℓ + 1}} f (x) d x - f (x_{ℓ}) h | & \leq \int_{x_{ℓ}}^{x_{ℓ + 1}} | f (x) - f (x_{ℓ}) | d x \leq \max_{t \in [a, b]} | f^{'} (t) | \int_{x_{ℓ}}^{x_{ℓ + 1}} (x - x_{ℓ}) d x \\ \leq \frac{h^{2}}{2} \max_{t \in [a, b]} | f^{'} (t) | . \end{array}

Durch Summation, Intervalladditivität des Integrals und die Dreiecksungleichung erhalten wir

\begin{array}{l} | \int_{a}^{b} f (x) d x - \sum_{ℓ = 0}^{n - 1} f (x_{ℓ}) h | \leq \frac{n h^{2}}{2} \max_{t \in [a, b]} | f^{'} (t) | = \frac{{(b - a)}^{2}}{2 n} \max_{t \in [a, b]} | f^{'} (t) | . \end{array}

Für (b) betrachten wir zuerst zu $ℓ \in {0, \dots, n - 1}$ die Endpunkte $x_{-} = x_{ℓ}$ und $x_{+} = x_{ℓ + 1}$ und den Mittelpunkt $\tilde{x} = \frac{x_{-} + x_{+}}{2}$ des Intervalls $[x_{-}, x_{+}]$ . Des Weiteren definieren wir den Wert $M_{2} = \max_{x \in [a, b]} | f^{″} (x) |$ . Nach Korollar 9.47 gilt für die Approximation durch das erste Taylor-Polynom um $\tilde{x}$

\begin{array}{l} | f (t) - (f (\tilde{x}) + f^{'} (\tilde{x}) (t - \tilde{x})) | \leq \frac{M_{2}}{2!} {| t - \tilde{x} |}^{2} \leq \frac{M_{2}}{2} {(\frac{h}{2})}^{2} = \frac{M_{2}}{8} h^{2} \end{array}

für alle $t \in [x_{-}, x_{+}]$ . Wir verwenden dies für die Endpunkte $t = x_{-}$ und $t = x_{+}$ des Intervalls $[x_{-}, x_{+}]$ und erhalten aus der Dreiecksungleichung

\begin{matrix} | \frac{f (x_{-}) + f (x_{+})}{2} - f (\tilde{x}) | \\ = \frac{1}{2} | (f (x_{-}) - f (\tilde{x}) - f^{'} (\tilde{x}) (x_{-} - \tilde{x})) + (f (x_{+}) - f (\tilde{x}) - f^{'} (\tilde{x}) (x_{+} - \tilde{x})) | \leq \frac{M_{2} h^{2}}{8}, \end{matrix}

da sich der lineare Term wegen $x_{-} - \tilde{x} = - (x_{+} - \tilde{x})$ aufhebt.

Aus demselben Grund erhalten wir

\begin{array}{l} | \int_{x_{-}}^{x_{+}} f (t) d t - f (\tilde{x}) h | & = | \int_{x_{-}}^{x_{+}} (f (t) - f (\tilde{x})) d t | = | \int_{x_{-}}^{x_{+}} (f (t) - (f (\tilde{x}) + f^{'} (\tilde{x}) (t - \tilde{x}))) d t | \\ \leq \frac{M_{2}}{2} \int_{x_{-}}^{x_{+}} {(t - \tilde{x})}^{2} d t = \frac{M_{2}}{2} \int_{- \frac{h}{2}}^{\frac{h}{2}} s^{2} d s = \frac{M_{2} h^{3}}{3 \cdot 8} \end{array}

Zusammenfassend gilt also für $ℓ \in {0, \dots, n - 1}$ und ${\tilde{x}}_{ℓ} = \frac{x_{ℓ} + x_{ℓ + 1}}{2}$

\begin{align} | f ({\tilde{x}}_{ℓ}) - \frac{f (x_{ℓ}) + f (x_{ℓ + 1})}{2} | & \leq \frac{M_{2} h^{2}}{8} & (9.14) \\ | \int_{x_{ℓ}}^{x_{ℓ + 1}} f (t) d t - f ({\tilde{x}}_{ℓ}) h | & \leq \frac{M_{2} h^{3}}{3 \cdot 8} & (9.15) \end{align}

Wir multiplizieren (9.14) mit $h$ und summieren sowohl (9.14) als auch (9.15) über $ℓ$ in ${0, \dots, n - 1}$ . Daraus folgt mit Intervalladditivität des Riemann-Integrals

\begin{array}{l} | \int_{a}^{b} f (x) d x - h \sum_{ℓ = 0}^{n - 1} \frac{f (x_{ℓ}) + f (x_{ℓ + 1})}{2} | \leq n (\frac{M_{2} h^{3}}{8} + \frac{M_{2} h^{3}}{3 \cdot 8}) = \frac{{(b - a)}^{3} M_{2}}{6 n^{2}} . \end{array}

Für (c) betrachten wir wieder zuerst zu $k \in {0, \dots, \frac{n}{2} - 1}$ die Endpunkte $x_{-} = x_{2 k}$ und $x_{+} = x_{2 k + 2}$ und den Mittelpunkt $\tilde{x} = x_{2 k + 1}$ des Intervalls $[x_{-}, x_{+}]$ und verwenden Korollar 9.47 bei $\tilde{x}$ . Dies ergibt für $t \in [x_{-}, x_{+}]$

\begin{align} | f (t) - (f (\tilde{x}) & + f^{'} (\tilde{x}) (t - \tilde{x}) + \frac{f^{″} (\tilde{x})}{2} {(t - \tilde{x})}^{2} + \frac{f^{‴} (\tilde{x})}{6} {(t - \tilde{x})}^{3}) | \\ \leq \frac{M_{4} {(t - \tilde{x})}^{4}}{4!} \leq \frac{M_{4} h^{4}}{4!}, & (9.16) \end{align}

wobei $M_{4} = \max_{x \in [a, b]} | f^{(4)} (x) |$ . Durch Integration über $[x_{-}, x_{+}]$ erhalten wir

\begin{array}{l} | \int_{x_{-}}^{x_{+}} f (t) d t - (2 h f (\tilde{x}) + \frac{f^{″} (\tilde{x})}{2} \int_{- h}^{h} s^{2} d s) | \leq \frac{M_{4}}{4!} \int_{- h}^{h} s^{4} d s \end{array}

oder auch

\begin{array}{l} | \int_{x_{-}}^{x_{+}} f (t) d t - (2 h f (\tilde{x}) + \frac{f^{″} (\tilde{x})}{3} h^{3}) | \leq \frac{M_{4} h^{5}}{60} \end{array}

Setzen wir $t = x_{-}$ und $t = x_{+}$ in Gleichung (9.16), so erhalten wir

\begin{array}{l} \frac{h}{3} | (f (x_{-}) + f (x_{+})) - (2 f (\tilde{x}) + f^{″} (\tilde{x}) h^{2}) | \leq \frac{h \cdot 2 \cdot M_{4} h^{4}}{3 \cdot 24} = \frac{M_{4} h^{5}}{36}, \end{array}

da sich die linearen und kubischen Terme gegenseitig aufheben. Daher gilt

\begin{matrix} | \int_{x_{-}}^{x_{+}} f (t) d t - \frac{h}{3} (f (x_{-}) + 4 f (\tilde{x}) + f (x_{+})) | \\ = | \int_{x_{-}}^{x_{+}} f (t) d t - \frac{h}{3} (6 f (\tilde{x}) + f^{″} (\tilde{x}) h^{2}) + \frac{h}{3} (2 f (\tilde{x}) + f^{″} (\tilde{x}) h^{2}) - \frac{h}{3} (f (x_{-}) + f (x_{+})) | \\ \leq \frac{1}{60} M_{4} h^{5} + \frac{1}{36} M_{4} h^{5} = \frac{2}{45} M_{4} h^{5} . \end{matrix}

Nach Summation über $k \in {0, \dots, \frac{n}{2} - 1}$ ergibt sich die Folge $1, 4, 2, 4, 2, \dots, 2, 4, 1$ der Gewichte für die Funktionswerte in der Simpson-Regel wie im Satz und die Abschätzung genau wie im Beweis von (b) oben.

■

Übung 9.57.

Erklären Sie unter Verwendung der Simpson-Regel, wie man $π = 4 \int_{0}^{1} \frac{1}{1 + x^{2}} d x$ auf beliebig viele Dezimalstellen genau bestimmen kann.

9.5.1 Landau-Notation II

Wie in obigem Beweis der Simpson-Regel ersichtlich wurde, ist das genaue Buchführen der Konstanten relativ anstrengend und der eigentliche Wert, den man zum Schluss erhält, steckt nicht so sehr in der konkreten Konstante sondern in den anderen Ausdrücken. Wir möchten nun deswegen ein weiteres Stück Notation einführen, welche uns erlaubt bei Abschätzungen unsere Denkleistung auf das Wesentliche zu fokussieren.

Sei $X$ eine Menge und seien $f, g : X \to ℂ$ zwei Funktion. Wir schreiben

\begin{array}{l} f (x) = O (g (x)) für x \in X, \end{array}

falls eine Konstante $C > 0$ existiert mit $| f (x) | \leq C | g (x) |$ für alle $x \in X$ .

Die obige Notation kann leicht mit der Landau-Notation aus Abschnitt 6.6 verwirrt werden, weswegen wir uns Mühe geben werden, den Zusatz „für $x \in X$ “ auch immer anzugeben. In einem gewissen Sinne ist die Aussage $f (x) = O (g (x)) für x \in [a, \infty)$ eine „globale Aussage“, da alle Zahlen $x$ in $[a, \infty)$ betroffen sind. Hingegen ist $f (x) = O (g (x)) für x \to \infty$ eine „lokale Aussage“ , da nur Zahlen $x \in [a, \infty)$ betroffen sind, die gross genug sind (das heisst nahe genug bei unendlich sind, siehe Abschnitt 6.6).

In gewissen Situation bedeutet die Notation aber dasselbe, wie folgende Übung zeigt.

Übung 9.58.

Sei $a \in ℝ$ und seien $f, g : [a, \infty) \to ℝ$ zwei stetige Funktionen mit $g (x) > 0$ für alle $x \in [a, \infty)$ . Zeigen Sie, dass die Aussagen

\begin{array}{l} f (x) & = O (g (x)) für x \in [a, \infty) \\ f (x) & = O (g (x)) für x \to \infty \end{array}

äquivalent sind.

Die Gross-O-Notation ist per Definition also insbesondere dann nützlich, wenn wir Konstanten „verstecken“ wollen. Beispielsweise ist $100! = O (1)$ . Damit die Notation auch in Rechnungen nützlich ist, erlauben wir auch arithmetische Operationen mit ihr (vergleiche auch Abschnitt 6.6): Ist $X$ eine Menge und sind $f_{1}, f_{2}, g : X \to ℂ$ drei Funktionen, dann bedeutet

\begin{array}{l} f_{1} (x) = f_{2} (x) + O (g (x)) für x \in X, \end{array}

dass $f_{1} (x) - f_{2} (x) = O (g (x))$ für $x \in X$ oder intuitiv ausgedrückt, dass die Differenz von $f_{1}$ und $f_{2}$ durch $g$ kontrolliert ist. Des Weiteren folgt aus $f_{1} = O (g)$ für $x \in X$ , auch $f_{1} f_{2} = O (g f_{2})$ für $x \in X$ .

Die Gross-O-Notation wird auch dazu verwendet, Unabhängigkeiten von gewissen Parametern zum Ausdruck zu bringen. Wir möchten dies an einem Beispiel illustrieren.

Beispiel 9.59 (Parameterabhängigkeit bei Landau-Notation).

Sei $k \in ℕ$ und $α \in (- \infty, 2]$ .

(a)

Nach Taylorapproximation im Sinne von Korollar 9.47 gilt

\begin{array}{l} | x^{\frac{3}{2}} - (k^{\frac{3}{2}} + \frac{3}{2} k^{\frac{1}{2}} (x - k)) | \leq \frac{1}{2} \max_{t \in [1, \infty)} | \frac{3}{4} t^{- \frac{1}{2}} | {(x - k)}^{2} = \frac{3}{8} {(x - k)}^{2} \end{array}

für $x \in [1, \infty)$ . Insbesondere gilt

\begin{array}{l} x^{\frac{3}{2}} = k^{\frac{3}{2}} + \frac{3}{2} k^{\frac{1}{2}} (x - k) + O ({(x - k)}^{2}) für x \in [1, \infty), \end{array}

wobei die in $O (\cdot)$ versteckte implizite Konstante also nicht vom Parameter $k$ abhängt.

(b)

Hängt die implizite Konstante, nicht wie in (a) oben, von einem Parameter ab, so indizieren wir den Parameter bei

O (\cdot)

. Ein konkretes Beispiel: Wenn

α \in (- \infty, 2]

, dann gilt

\begin{array}{l} x^{α} = 1 + α (x - 1) + O_{α} ({(x - 1)}^{2}) \end{array}

für $x \in [\frac{1}{2}, \infty)$ auf Grund der Taylorapproximation in Korollar 9.47.

(c)

Auch eine Abhängigkeit des Definitionsbereichs vom Parameter ist denkbar und oft nützlich. Für alle Zahlen

t \in [k - \frac{1}{2}, k + \frac{1}{2}]

gilt

{(\log)}^{″} (t) = - \frac{1}{t^{2}} = O (\frac{1}{k^{2}})

und daher

\begin{array}{l} \log (t) = \log (k) + \frac{1}{k} (t - k) + O (\frac{{(t - k)}^{2}}{k^{2}}) = \log (k) + \frac{1}{k} (t - k) + O (\frac{1}{k^{2}}) \end{array}

auf Grund der Taylorapproximation in Korollar 9.47.

Im Allgemeinen sollte man die Landau-Notation sorgfältig verwenden, da sich hier oft Fehler einschleichen insbesondere bei der Frage der Abhängigkeit der impliziten Konstanten.