Kurs:Numerik I/8 Numerische Integration

Aus Wikiversity

8.1 Einführung[Bearbeiten]

In Anwendungen der Mathematik müssen häufig Riemann-Integrale für stückweise stetige Funktionen berechnet werden. In vielen Fällen ist eine geschlossene Lösung eines solchen Integrals nicht bekannt, so dass es näherungsweise numerisch gelöst werden muss. Die numerische Lösung eines Integrals bezeichnet man auch als numerische Quadratur. In diesem Abschnitt sollen eine Reihe von Formeln zur numerischen Integration hergeleitet und untersucht werden.

Das Integral über eine stückweise stetige Funktion kann bekanntlich als Summe von Integralen über stetige Funktionen beschrieben werden, so dass wir uns auf die Betrachtung stetiger Funktionen beschränken können. Dazu definieren wir den Operator mit

für . Dieser ist linear, da für alle und

gilt und er ist positiv, d. h. man hat

wobei bedeutet, dass ist. Gesucht sind nun einfach auszuwertende Formeln, die jedem einen Näherungswert für den Wert des Integrals zuordnen und zwar so, dass der Quadraturfehler möglichst klein ist.

Definition 8.1[Bearbeiten]

Unter einer Quadraturformel zur Berechnung des bestimmten Integrals versteht man eine Summe
(8.1)
für mit bekannten Gewichten und Stützstellen bzw. Knoten , wobei sei.

Wenn wir die Abhängigkeit der Gewichte und Stützstellen von der Wahl von darstellen wollen, schreiben wir statt und auch und . Wie ist auch eine Quadraturformel ein linearer Operator, denn man hat

(8.2)

für alle und . Sind die Gewichte nichtnegativ, d. h. hat man , so ist ferner mit auch positiv und gilt also

Wir definieren weiter:

Definition 8.2[Bearbeiten]

Eine Quadraturformel hat mindestens den Genauigkeitsgrad , wenn
(8.3)
gilt. Im Fall, dass zusätzlich richtig ist, sagt man, dass den Genauigkeitsgrad hat.

Da und lineare Operatoren sind, folgt aus (8.3)

(8.4)

für alle , und damit der folgende Satz, wobei wieder den Raum aller Polynome vom Grad bezeichnet:

Satz 8.3[Bearbeiten]

ist genau dann eine Quadraturformel von mindestens dem Genauigkeitsgrad , wenn gilt:

Wir bemerken in diesem Zusammenhang:

Satz 8.4[Bearbeiten]

Zu Stützstellen mit gibt es genau eine Quadraturformel , welche mindestens den Genauigkeitsgrad hat, d. h. für die gilt:
(8.5)
Diese hat die Gewichte
(8.6)
wobei die zu den gehörenden Lagrangeschen Basispolynome sind (vgl. Definition 6.2).

Beweis.[Bearbeiten]

Für die durch die Stützstellen und Gewichte in (8.6) definierte Quadraturformel gilt für

(8.7)

Da sich jedes Polynom vom Grad auf eindeutige Weise als Linearkombination der darstellen lässt (vgl. (6.6)) und sowie lineare Operatoren sind, folgt damit analog zu (8.4) die Beziehung (8.5). Die so definierte Quadraturformel ist eindeutig. Denn für jede andere Quadraturformel mit Gewichten und Genauigkeitsgrad hat man wegen die Identität und bekommt man analog zu (8.7) , so dass und demnach folgt.

q.e.d.

Weiter stellen wir fest:

Satz 8.5[Bearbeiten]

Ist eine Quadraturformel, die einen Genauigkeitsgrad hat, so folgt für ihre Gewichte

Beweis.[Bearbeiten]

Da einen Genauigkeitsgrad hat, folgt

q.e.d.

Bezüglich der Konvergenz der durch eine Quadraturformel

erzeugten Näherungswerte gegen den exakten Wert des Integrals für kann man allgemein den folgenden Satz angeben, den wir hier jedoch nicht beweisen können (für einen Beweis siehe H. Heuser: Funktionalanalysis, Teubner, Stuttgart, 1992, S. 268).

Satz 8.6 (Szegö)[Bearbeiten]

Man hat
genau dann, wenn gilt:
(a)
(b)

Mit Hilfe von Satz 8.5 erschließt man ferner:

Korollar 8.7[Bearbeiten]

Es sei eine Quadraturformel mit Gewichten für alle und einem Genauigkeitsgrad . Dann hat man
genau dann, wenn gilt:

8.2 Interpolatorische Quadraturformeln[Bearbeiten]

8.2.1 Allgemeines[Bearbeiten]

Es seien nun und mit gegeben und bezeichne das (eindeutige) Interpolationspolynom zu den Stützpunkten . Sind wieder die zu den Stützstellen gehörenden Lagrangeschen Basispolynome, so kann das Interpolationspolynom damit gemäß (6.7)in der Form

geschrieben werden. Wir definieren nun:

Denition 8.8[Bearbeiten]

Eine Quadraturformel mit
d. h. mit Gewichten
(8.8)
heißt interpolatorische Quadraturformel.

Wegen der Übereinstimmung der Gewichte in (8.8) und (8.6) können wir mit Satz 8.4 schließen:

Korollar 8.9[Bearbeiten]

Eine interpolatorische Quadraturformel hat mindestens den Genauigkeitsgrad und ist zu den gegebenen Stützstellen die einzige Quadraturformel mit einem Genauigkeitsgrad .

Ferner können wir zeigen:

Satz 8.10[Bearbeiten]

Eine interpolatorische Quadraturformel In besitzt die Gestalt
mit
(8.9) mit

Beweis.[Bearbeiten]

Mit wie in (8.9) lassen sich die Gewichte aus (8.8) mit Hilfe der Substitution umschreiben in

(8.10)

q.e.d.

Die Transformation von nach in (8.9) ist sinnvoll, da damit die Gewichte in einer interpolatorischen Quadraturformel von den Intervallgrenzen und unabhängig werden und nur von der relativen Verteilung der Stützstellen in abhängen.

8.2.2 Newton-Cotes-Formeln[Bearbeiten]

Wir wollen nun auf spezielle interpolatorische Quadraturformeln, die Newton-Cotes-Formeln, eingehen. Diese ergeben sich durch äquidistante Wahl der Stützstellen in . Insbesondere erhält man die abgeschlossenen Newton-Cotes-Formeln, wenn die Randpunkte des Intervalls selbst Stützstellen sind, wenn also für Bei den offenen Newton-Cotes-Formeln sind die Randpunkte von selbst keine Stützstellen, so dass man

hat. Wir wollen hier nur die abgeschlossenen Newton-Cotes-Formeln genauer untersuchen.

Lemma 8.11[Bearbeiten]

Für die Gewichte der abgeschlossenen Newton-Cotes-Formeln gilt:
(8.12)

Beweis.[Bearbeiten]

Die zweite Identität in (8.12) folgt mit

aus (8.9) mit der Substitution , denn man hat

Somit müssen wir noch die erste Identität in (8.12) zeigen. Dazu sei . Sind die Lagrangeschen Basispolynome, so ist und sowie

für . Da und demnach offenbar Interpolationspolynome zu den Punkten sind, muss wegen der Eindeutigkeit des Interpolationspolynoms gelten, so dass wir schließlich mit der Substitution Folgendes erhalten (vgl. (8.10)):

q.e.d.

Wir geben nun einige Spezialfälle der abgeschlossenen Newton-Cotes-Formeln an.

Beispiel 8.12[Bearbeiten]

(1) Für hat eine interpolatorische Quadraturformel nach Satz 8.10 die Gestalt

Dabei ergeben sich für die zugehörige abgeschlossene Newton-Cotes-Formel mit die Stützstellen und und wegen (Lemma 8.11) und (Satz 8.5) die Gewichte

Man erhält so die (Sehnen-) Trapezregel

(8.13)

(2) Für hat man mit die Stützstellen und und unter Verwendung von Lemma 8.11 und anschließend Satz 8.5 die Gewichte

Unter Verwendung von Satz 8.10 ergibt sich so die Simpson-Regel bzw. Keplersche Fassregel

(8.14)

(3) Der Fall führt auf die Newtonsche 3/8-Regel

(4) Für bekommt man die Milne-Regel

Als Beispiel berechnen wir ein Integral näherungsweise mit der Simpson-Regel.

Beispiel 8.13[Bearbeiten]

Es seien und , so dass

ist. Die Simpson-Regel liefert dafür den Näherungswert

Der exakte Wert des Integrals lautet hier

Für sind die Gewichte in den abgeschlossenen Newton-Cotes-Formeln nichtnegativ und sind diese Quadraturformeln demzufolge positiv. Für und treten negative Gewichte auf und ist damit als Folge von Satz 8.5

was zu einer Verstärkung von Rundungsfehlern bei den Funktionswerten führt. Die Verwendung der abgeschlossenen Newton-Cotes-Formeln für ist daher nicht zu empfehlen. Für die (abgeschlossenen) Newton-Cotes-Formeln lässt sich sogar

beweisen (Satz von Kusmin), so dass man aus dem Satz 8.6 von Szegö die Existenz eines schließen kann, für das die Konvergenz nicht gilt. Letzteres lässt ja auch der Satz 6.24 von Faber generell für interpolatorische Quadraturformeln vermuten. Eine Erhöhung von bei den (abgeschlossenen) Newton-Cotes-Formeln muss also nicht zwangsläufig zu einer genaueren Näherung von führen.

Wir geben hier noch einige weitere interpolatorische Quadraturformeln an.

Beispiel 8.14[Bearbeiten]

(1) Für und oder muss wegen Satz 8.5 gelten, so dass man alternativ folgende beiden Rechteckregeln erhält:

(8.15)

(2) Für bekommt man im Fall der offenen Newton-Cotes-Formeln und

und damit eine weitere Rechteckregel, die Mittelpunktregel

(3) Die offene Newton-Cotes-Formel für lautet mit ,

und den Gewichten , die man aus der Formel (8.9) errechnet, wie folgt:

(4) Die offene Newton-Cotes-Formel für lautet mit ,

und den mit Hilfe von (8.9) zu berechnenden Gewichten wie folgt:

Man beachte, dass sie ein negatives Gewicht beinhaltet.

8.2.3 Quadraturfehler und Genauigkeitsgrad[Bearbeiten]

Für den durch eine beliebige interpolatorische Quadraturformel in Bezug auf den exakten Wert des Integrals entstehenden Fehler, kann man die im folgenden Satz angegebene Abschätzung beweisen.

Satz 8.15[Bearbeiten]

Es sei eine interpolatorische Quadraturformel mit Stützstellen , welche mindestens den Genauigkeitsgrad besitze und es sei . Dann gilt
(8.16)
für
mit
(8.17)
Hat man insbesondere für die aus (8.17) und frei wählbare mit
die Beziehung oder , dann folgt mit
und einem die Fehlerdarstellung
(8.18)

Beweis.[Bearbeiten]

Seien zunächst beliebig gewählt, so dass die paarweise verschieden sind und sei das Interpolationspolynom zur den Stützpunkten . Da den Genauigkeitsgrad hat, gilt dann

und demnach

Mit

und unter Verwendung von Satz 6.11 hat man für ein

Da die linke Seite der letzten Gleichung stetig in ist, ist es auch die rechte Seite und darum hat man

(8.19)

Man beachte nun, dass die durch die Quadraturregel festgelegt sind. Wir wollen abschließend zeigen, dass für die Stützstellen die anfangs gemachte Voraussetzung hinsichtlich der paarweisen Unterschiedlichkeit fallen gelassen werden kann. Es seien daher jetzt letztere Punkte vollkommen beliebig aus [a, b] gewählt. Für jedes können wir dann Punkte finden, die zusammen mit den paarweise unterschiedlich sind und für die

gilt. Setzen wir

so hat man unter Verwendung des ersten Teils des Beweises

(8.20)

Wählt man nun so, dass der Wert des letzten Integrals minimal wird und wendet man die Substitution an, so gelangt man schließlich zu

womit die Abschätzung (8.16) gezeigt ist.
Ist nun mit gewissen Punkten

(8.21)

so erhält man aus (8.20)

Weiter gewinnt man mit (8.19)

Der Zwischenwertsatz, angewandt auf die Funktion , liefert somit für ein

so dass die Substitution in diesem Fall zu der Formel (8.18) führt. Analog schließt man im Fall, dass „“ statt „“ in (8.21) vorliegt.

q.e.d.

Beispiel 8.16[Bearbeiten]

Wir nutzen im Folgenden aus, dass nach Korollar 8.9 der Genauigkeitsgrad einer interpolatorischen Quadraturformel und die Rechteckregel aus (8.15). Aus (8.18) gewinnt man für mit , mit bzw. sowie mit

und die Fehlerdarstellung

wobei ein Punkt aus ist. Entsprechend erhält man für die Rechteckregel mit bzw. sowie mit

und die Fehlerdarstellung

(2) Im Fall der Trapezregel

gilt für mit einem die Fehlerdarstellung

Denn mit bzw. hat man

sowie

Der Genauigkeitsgrad einer interpolatorischen Quadraturformel ist mindestens . Für gerade hat man im Fall der abgeschlossenen Newton-Cotes-Formeln sogar das folgende Resultat (für den Beweis siehe Plato, S. 103):

Satz 8.17[Bearbeiten]

Die abgeschlossene Newton-Cotes-Formel besitzt für gerades den (exakten) Genauigkeitsgrad .

Letzteres Ergebnis können wir z. B. für die Fehlerdarstellung der Simpson-Regel verwenden.

Beispiel 8.18[Bearbeiten]

Es sei . Dann hat man für und mit bzw. und mit dem gewählten Punkt

sowie

Also ergibt sich für die Simpson-Regel

mit einem der Quadraturfehler

8.3 Summierte abgeschlossene Newton-Cotes-Formel[Bearbeiten]

Wie bereits in Abschnitt 8.2.2 erläutert wurde, garantiert eine Erhöhung von keineswegs, dass die Newton-Cotes-Formeln Näherungswerte zunehmender Genauigkeit für liefern. Um Letzteres zu erreichen, müssen wir daher anders vorgehen. Und zwar teilen wir zunächst das Intervall mittels Stützstellen

in gleiche Stücke auf, so dass sich insbesondere

für alle ergibt. Dann nähern wir das Integral

durch

an, wobei das (eindeutige) Interpolationspolynom zu paarweise verschiedenen, in jedem Intervall in gleichen Abständen gewählten Stützpunkten ist (vgl. Definition 8.8). Wir wählen also eine interpolatorische Quadraturformel und ersetzen jedes der Integrale durch den sich damit ergebenden Wert. Eine so gewonnene Quadraturformel bezeichnet man als summierte Quadraturformel. Wir wollen solche Formeln nun genauer betrachten, wobei wir uns hier auf die abgeschlossenen Newton-Cotes-Formeln zu deren Generierung beschränken wollen. Letztere Wahl legt die Stützpunkte in jedem Intervall durch (8.11) fest, wobei dort und zu wählen ist.

Wir beginnen mit den beiden Rechteckregeln aus (8.15). Für diese erhält man

bzw.

so dass Summation über die folgenden summierten Rechteckregeln liefert:

Für diese gelten die nachstehenden Fehlerabschätzungen.

Satz 8.19[Bearbeiten]

Es sei . Dann gibt es , so dass gilt:
(8.22)

Beweis.[Bearbeiten]

Aus Beispiel 8.16 (1) ergibt sich für die Existenz eines mit

Summation über führt auf

Aufgrund von

bzw.

existiert nach dem Zwischenwertsatz ein mit

so dass die erste Fehlerdarstellung in (8.22) folgt. Die zweite zeigt man analog.

q.e.d.

Im Fall der Trapezregel (8.13) hat man

Summation über führt auf die summierte Trapezregel

mit der im folgenden Satz angegebenen Fehlerdarstellung.

Satz 8.20[Bearbeiten]

Es sei . Dann existiert ein mit

Beweis.[Bearbeiten]

Der Beweis verläuft analog zu dem von Satz 8.19. Nach Beispiel 8.16 (2) gibt es für ein mit

Summation über liefert mit einem

wobei die Existenz eines solchen aus der Anwendung des Zwischenwertsatzes auf geschlossen werden kann.

q.e.d.

Schließlich betrachten wir noch die summierte Simpson-Regel, wobei wir die Darstellung mit für jedes verwenden, so dass insbesondere

folgt. Die Simpson-Regel, angewandt auf das Intervall , lässt sich somit in der Form

schreiben. Summation über führt auf die summierte Simpson-Regel

Für diese hat man die im folgenden Satz angegebene Fehlerdarstellung.

Satz 8.21[Bearbeiten]

Es sei . Dann existiert ein mit

Beweis.[Bearbeiten]

Der Beweis verläuft wiederum analog zu dem von Satz 8.19. Nach Beispiel 8.18 gibt es für ein mit

Summation über liefert mit einem

wobei die Existenz von aus der Anwendung des Zwischenwertsatzes auf folgt.

q.e.d.

Zur Auswertung der summierten Rechteckregeln müssen , für die der summierten Trapezregel und für die der summierte Simpson-Regel Funktionswerte bestimmt werden. Der Rechenaufwand bei Verwendung der summierten Simpson-Regel ist damit etwa doppelt so hoch wie der bei Verwendung einer der drei anderen Regeln. Dennoch ist die summierte Simpson-Regel diesen für hinreichend glatte Funktionen wegen der höheren Fehlerordnung in h vorzuziehen. Denn der Quadraturfehler verhält sich bei ihr wie , während er bei den summierten Rechteckregeln und der summierten Trapezregel proportional zu bzw. abnimmt.

Da man die in der jeweiligen Fehlerformel vorkommende Ableitung durch das Maximum des Betrages dieser Ableitung bezüglich aller nach oben abschätzen kann, implizieren die angegebenen Fehlerdarstellungen insbesondere, dass die hier angegebenen summierten Quadraturformeln für gegen den exakten Wert des Integrals konvergieren, wobei mit „“ hier „ mit und “ gemeint ist.

Wir greifen abschließend nochmals Beispiel 8.13 auf.

Beispiel 8.22[Bearbeiten]

Es seien wieder und , so dass ein Näherungswert für das Integral

gesucht ist. Weiter wählen wir und somit . Der exakte Wert des Integrals lautet . Mit der summierten Simpson-Regel ergibt sich der Wert

8.4 Extrapolationsverfahren[Bearbeiten]

8.4.1 Einführung[Bearbeiten]

Für die summierte Trapezregel gibt der folgende Satz eine asymptotische Entwicklung nach Potenzen von an, welche dazu genutzt werden soll, aus einer endlichen Zahl von Auswertungen der summierten Trapezregel eine im Hinblick auf diese Werte genauere Näherung des Integrals zu berechnen. (Der Satz ist z. B. bei Plato bewiesen.)

Satz 8.23[Bearbeiten]

Für ein sei . Die summierte Trapezregel
mit für ein besitzt die asymptotische Entwicklung
(8.23) für
mit und gewissen Koeffizienten .

Für periodische Funktionen mit Periode kann man sogar zeigen, dass gilt. In einem solchen Fall kann mit dem in diesem Abschnitt beschriebenen Verfahren keine Verbesserung erzielt werden.

Man beachte, dass man nur für mit für eine natürliche Zahl auswerten kann. Aufgrund von (8.23) (wie auch wegen Satz 8.20) gilt ferner

wobei wir mit „“ hier „ mit und “ meinen. Die Entwicklung (8.23) soll nun numerisch dazu ausgenutzt werden, von einer endlichen Zahl berechneter Werte mit auf einen noch genaueren Wert von als zu schließen.

Wir gehen dabei allgemeiner von einer beliebigen Funktion mit aus, die mit gewissen Koeffizienten und einer Zahl die asymptotische Entwicklung der Ordnung

(8.24) für

besitzt und für die der Wert

gesucht ist. Typischerweise steht für ein numerisches Verfahren, das für einen gewählten Diskretisierungsparameter einen Näherungswert für die gesuchte Größe liefert. Es sei also angenommen, dass zumindest für gewisse berechnet werden kann, wie dies z. B. im Fall der Tangententrapezregel für mit der Fall ist.

Wegen (8.24) hat man zunächst für nur die Genauigkeit

Es soll nun ein Verfahren vorgestellt werden, welches ohne großen Mehraufwand aus endlich vielen, bereits berechneten Werten mit einen genaueren Wert für die gesuchte Größe erzeugt. Setzt man , so extrapoliert dieses Verfahren also auf den Wert hin, so dass man auch von einem Extrapolationsverfahren spricht. Da die Koeffizienten in (8.24) oft nicht explizit bekannt sind oder nur unter einigem Aufwand zu berechnen sind, geht man dabei folgendermaßen vor:

  • man vernachlässigt den Restterm in (8.24) und geht davon aus, dass sich ungefähr wie ein Polynom in verhält,
  • man ersetzt das resultierende (i. A. nicht explizit bekannte) Polynom durch das Interpolationspolynom zu den Stützpunkten (schreibt man statt , so sind dies mit die Punkte ) und
  • man verwendet den Wert als Näherung für den unbekannten Wert .

Im Zusammenhang mit der summierten Trapezregel wird diese Vorgehensweise als Romberg-Verfahren bezeichnet.

8.4.2 Das Verfahren[Bearbeiten]

Wir gehen nun von der asymptotischen Entwicklung (8.24) von aus und es sei das Interpolationspolynom zu den Stützpunkten

(8.25)

Da dieses nur an einer Stelle, der Stelle 0, ausgewertet werden soll, bietet sich das Neville-Schema zur Verwendung an, wobei hier das Interpolationspolynom mit

(8.26)

bezeichnet. Wir setzen dazu

(8.27)

Satz 6.5 liefert damit

(8.28)

sowie

(8.29)

Das Schema von Neville geht damit in das folgende Extrapolationstableau über, welches zeilenweise aufgebaut wird:

Beispiel 8.24[Bearbeiten]

Für die summierte Trapezregel gilt gemäß Satz 8.23 eine Entwicklung der Form (8.24) mit . Für die Schrittweiten

erhält man die Werte

und damit

Der aus den beiden Auswertungen und der summierten Trapezregel ermittelte Wert entspricht somit dem der Simpson-Regel für .

Im folgenden Satz wird die Größenordnung des Fehlers angegeben. Diese Fehlerbetrachtung macht deutlich, dass sich die Anwendung des hier untersuchten Extrapolationsverfahrens lohnt. Als Hilfsmittel verwenden wir das nachstehende Lemma.

Lemma 8.25[Bearbeiten]

Es seien die Lagrangeschen Basispolynome zu Stützstellen mit . Dann gilt
(8.30)

Beweis.[Bearbeiten]

Für ist offenbar das Interpolationspolynom zu den Punkten und daher gemäß (6.7)

Setzen wir , so folgt die Behauptung für die ersten beiden Fälle in (8.30). Für den Fall betrachten wir das Polynom

welches wegen den Grad , den führenden Koeffizienten 1 und die Nullstellen hat, so dass insbesondere

gilt. Speziell hat man somit

Satz 8.26[Bearbeiten]

Es sei mit eine Funktion mit der asymptotischen Entwicklung (8.24) für ein und . Weiter sei eine Folge von Schrittweiten, so dass mit einer Startschrittweite gilt:
(8.31) mit
Schließlich sei das Interpolationspolynom mit (8.26) und wie in (8.27). Dann genügt der Fehler für der asymptotischen Entwicklung
(8.32)

Beweis.[Bearbeiten]

Da sich die Indizes in (8.32) auf eine Numerierung der Stützpunkte beziehen und wir den -ten als 0-ten bezeichnen können, können wir o. B. d. A. annehmen. Gemäß der Lagrangeschen Darstellung des Interpolationspolynoms gilt dann

und somit

(8.33)

für

Nun folgt wegen aus (8.24)

(8.34)

Des Weiteren schließt man mit Lemma 8.25

(8.35)

Setzt man die beiden Beziehungen (8.34) und (8.35) in (8.33) ein, so bekommt man schließlich, da die von unabhängig sind,

q.e.d.

Der Satz besagt, dass man beim Übergang von zu , d. h. bei Erhöhung der Spaltenzahl in dem Extrapolationstableau um 1, im Prinzip die Ordnung gewinnt. Diese Sichtweise ist allerdings zu optimistisch, da die Restterme der asymptotischen Entwicklung, die sich hinter verbergen, nicht bekannt sind und groß werden können.

Es bietet sich also der folgende Algorithmus an:

Algorithmus 10 (Extrapolationsverfahren)[Bearbeiten]

(0) Wähle , eine Folge wie in (8.31) und ein . Setze .
(1) Berechne .
(2) Berechne für nach der Formel
(3) Falls „der Aufwand zu groß wird“ oder
gilt, breche ab. ( ist Näherungswert für .)
(4) Setze und gehe nach (1).

Man bricht das Extrapolationsverfahren also ab, wenn der Aufwand zur Erzeugung einer neuen Zeile im Extrapolationsschema, den man meistens, wie z. B. für das summierte Trapezverfahren, genau angeben kann, zu groß wird oder die relative Abweichung zweier aufeinanderfolgender Diagonalelemente klein genug wird. In der Praxis ist es jedoch auch möglich, dass aufgrund von Rundungsfehlern Divergenz eintritt, so dass auf früher berechnete Werte im Schema zurückgegriffen werden muss.

Häufig angewandte Schrittweitenfolgen für (8.31) in diesem Zusammenhang sind die Romberg-Folge

(8.36)

die durch

definierte Bulirsch-Folge

und die harmonische Folge

Insbesondere erhält man für die Romberg-Folge :

Korollar 8.27[Bearbeiten]

Unter den Voraussetzungen von Satz 8.26 gilt für die Romberg-Folge (8.36) mit und

Beweis.[Bearbeiten]

Im Fall (8.36) hat man mit

so dass die Behauptung unmittelbar aus Satz 8.26 folgt.

q.e.d.

Wir betrachten nun nochmals die summierte Trapezregel als Beispiel.

Beispiel 8.28[Bearbeiten]

(1) Korollar 8.27 wollen wir auf die summierte Trapezregel mit (und wegen der Forderung für ) anwenden. Nach Satz 8.23 ist dann . Weiter sei vorausgesetzt. Korollar 8.27 liefert mit diesen Setzungen

(8.37)

wobei mit dem Neville-Schema

berechnet wird. Man beachte dabei, dass man bei der Berechnung von den zuvor ermittelten Wert verwenden kann und nur zusätzlich Funktionsauswertungen für die Mittelpunkte der sich aus der zu gehörenden Zerlegung von ergebenden Intervalle benötigt. Somit verlangt die Berechnung von und genauso viele Funktionsauswertungen wie die direkte Berechnung von . Für letzteren Wert alleine hat man aber im Vergleich zu (8.37) gemäß Satz 8.20 für mit einem einen Fehler der Größe :

(2) (Bader) Es soll das Integral

näherungsweise mit der summierten Trapezregel und dem Extrapolationsverfahren mit der Romberg-Folge (8.36) und berechnet werden. Es ergibt sich bei 12-stelliger Rechnung das folgende Extrapolationstableau:

Der (in der Tabelle nicht mehr einfügbare) Wert des Diagonalelementes in der 5. Spalte beträgt . Er ist offenbar ungenauer als die beiden untersten Werte in der 4. Spalte, wobei für den untersten allerdings auch die summierte Trapezregel einmal mehr ausgewertet werden musste. (Man kann auch zeigen, was für die erste Spalte z. B. aus Satz 8.20 folgt, dass die Werte in jeder einzelnen Spalte des Extrapolationsschemas, d. h. für konstantes und , gegen den gesuchten Wert konvergieren.) Für eine Diskussion über ein geeignetes Abbruchkriterium verweisen wir auf Deuflhard/Hohmann.

8.5 Gaußsche Quadraturformeln[Bearbeiten]

8.5.1 Einleitung[Bearbeiten]

In diesem Abschnitt betrachten wir Quadraturformeln für gewichtete Integrale des Typs

(8.38)

wobei das Intervall hier halbunendlich oder unendlich, d. h. und/oder sein darf und eine Gewichtsfunktion mit den folgenden Eigenschaften ist:

  • es existieren die Momente

Häufig in diesem Zusammenhang auftretende Gewichtsfunktionen sind in der folgenden Tabelle wiedergegeben, wobei auch der zuvor betrachtete Fall von Interesse ist:

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. TeX parse error: Bracket argument to \\ must be a dimension“): {\displaystyle {\begin{array}{|c|c|}\hline {\text{Intervall}}&{\text{Gewichtsfunktion }}w(x)\\\hline [-1,1]&1\\[-1,1]&1/{\sqrt {1-x^{2}}}\\[0,\infty )&e^{-x}\\(-\infty ,\infty )&e^{-x^{2}}\\[0,\infty )&e^{-x^{2}}x^{\alpha },\ \alpha >-1\\\hline \end{array}}}

Wir definieren in diesem Zusammenhang auf dem Raum aller Polynome das durch induzierte Skalarprodukt

(8.39)

Das Integral in (8.39) existiert offenbar unter den Voraussetzungen an . Für alle gilt weiter (man verifiziere dies)

Insbesondere ist also die Abbildung in beiden Eingängen linear. Wir verwenden ferner die durch das Skalarprodukt induzierte Norm auf

(8.40)

Ziel ist es nun wieder, zur numerischen Berechnung von eine Quadraturformel

(8.41)

herzuleiten. (Man beachte, dass hier der Faktor vor der Summe fehlt.) Und zwar soll eine interpolatorische Quadraturformel entwickelt werden, für welche bei geeigneter Wahl der Stützstellen und der Gewichte der Genauigkeitsgrad möglichst hoch ist, welche also Polynome bis zu einem möglichst hohen Grad exakt integriert. Man betrachte dazu die Aussagen in Satz 8.15 über den Quadraturfehler. Die Begriffe Genauigkeitsgrad und interpolatorische Quadraturformel sind hierbei analog zu den Definitionen 8.2 und 8.8 auf Integrale mit Gewichten zu übertragen.

Zunächst einmal stellen wir fest, dass man in (8.41) insgesamt 2n+2 Parameter und zur Verfügung hat, was der Anzahl der Koeffizienten eines Polynoms vom Grad entspricht. In der Tat werden wir zeigen, dass eine Quadraturformel mit diesem Genauigkeitsgrad existiert. Quadraturformeln mit einem höheren Genauigkeitsgrad kann es nicht geben. Denn wäre eine Quadraturformel mit Stützstellen und Gewichten und hätte den Genauigkeitsgrad , so folgte insbesondere für das Polynom

und daher . Wegen

ist jedoch . Wir können weiter schließen:

Lemma 8.29[Bearbeiten]

Ist eine Quadraturformel mit Stützstellen und Gewichten und hat den Genauigkeitsgrad , so gilt
für
mit beliebigem .

Beweis.[Bearbeiten]

Für folgt und somit

q.e.d.

Zwei Funktionen und , für die gilt, nennt man orthogonal zueinander. Für eine Quadraturformel mit Genauigkeitsgrad sollten die Stützstellen also gerade als Nullstellen eines Polynoms vom Grad gewählt werden, welches bezüglich des Skalarproduktes orthogonal zu dem ganzen Raum ist. Offenbar kann man ein solches Polynom gewinnen, indem man durch Anwendung des Gram-Schmidt-Orthogonalisierungsverfahren auf die Monome orthogonale Polynome hinsichtlich erzeugt. Diese Polynome haben nämlich die Eigenschaft

so dass sich insbesondere jedes mit gewissen in der Form schreiben lässt und folglich mit den zugehörigen gilt:

(8.42)

Darüber hinaus haben diese orthogonalen Polynome nur reelle und einfache Nullstellen, welche alle im Intervall liegen, wie im nächsten Unterabschnitt gezeigt wird. Die Stützstellen sollten demzufolge gerade die Nullstellen des -ten dieser orthogonalen Polynome sein. Die Gewichte einer derartigen Quadraturformel sind dann gemäß Satz 8.4, der genauso für gewichtete Integrale gilt, durch

festgelegt, wobei wieder die Lagrangeschen Basispolynome zu den Stützstellen sind. Nach Definition 8.8 (entsprechend für gewichtete Integrale formuliert) handelt es sich bei der so definierten Formel um eine interpolatorische Quadraturformel.

Bevor wir diese sog. Gaußschen Quadraturformeln noch etwas näher betrachten, wollen wir auf ihren wesentlichen Baustein, orthogonale Polynome, näher eingehen.

8.5.2 Orthogonale Polynome[Bearbeiten]

Wie bereits im vorigen Unterabschnitt gesagt wurde, erhält man eine spezielle Folge paarweise orthonormaler Polynome durch Gram-Schmidt-Orthonormalisierung der Monome :

Statt mit den orthonormalen Polynomen zu arbeiten, deren Hauptkoeffizienten i. a. von 1 verschieden sind, ist es manchmal bequemer, dies mit den orthogonalen Polynomen zu tun, d. h. mit

(8.43)

Diese unterscheiden sich von den nur durch den Skalar und haben offensichtlich den Hauptkoeffizienten 1. Für sie gilt

(8.44)

und somit (vgl. (8.42))

(8.45)

Nach Konstruktion ist also ein Polynom vom genauen Grad mit Hauptkoeffizienten 1.

Die Polynome können statt über die Formel (8.43) auch nach der im folgenden Satz angegebenen Drei-Term-Rekursionsformel berechnet werden.

Satz 8.30[Bearbeiten]

Die Orthogonalpolynome in (8.43) genügen der Drei-Term-Rekursionsformel
mit den Koeffizienten

Beweis.[Bearbeiten]

Offenbar ist die behauptete Darstellung richtig für und . Für setzen wir

und zeigen im Folgenden . Dazu stellen wir fest, dass sowie Polynome vom genauen Grad sind und beide den Hauptkoeffizienten 1 haben. Somit gilt

(8.46)

Wir zeigen nun, dass wie orthogonal zu dem ganzen Raum ist und damit

(8.47)

gilt. Die Beziehungen (8.46) und (8.47) zusammen ergeben dann

und folglich bzw., wie behauptet, .

Wir wollen nun (8.47) nachweisen. Aufgrund von erhalten wir mit der Definition von

(8.48)

und mit der Definition von

(8.49)

wobei das letzte Gleichheitszeichen wegen gilt. Schließlich folgt:

(8.50)

Da sich jedes gemäß (8.44) als Linearkombination der darstellen lässt, folgt aus (8.48), (8.49) und (8.50) für jedes mit gewissen

Damit ist alles gezeigt.

q.e.d.

Für die Nullstellen der in (8.43) hat man folgende Aussage:

Satz 8.31[Bearbeiten]

Die Nullstellen des -ten Orthogonalpolynoms in (8.43) sind reell, einfach und liegen alle in . Sie besitzen die Darstellung
(8.51)
wobei die zu den gehörenden Lagrangeschen Basispolynome sind.

Beweis.[Bearbeiten]

Es seien die Nullstellen von so durchnumeriert, dass diejenigen Nullstellen von in seien, an denen sein Vorzeichen wechselt und die somit eine ungerade Vielfachheit haben. Wäre nun bzw. , so hätte das Polynom

den Grad , so dass wegen (8.45)

(8.52)

folgte. Da die Nullstellen von mit gerader Vielfachheit wären, wäre dann aber

und demzufolge

im Widerspruch zu (8.52). Also ist .

Um zur Darstellung (8.51) zu gelangen, schreibt man für in der Form

Es folgt sowie

Daraus ergibt sich wegen

wobei sich die letzte Gleichung aus der Tatsache ergibt, dass das Polynom bis auf einen konstanten Faktor mit übereinstimmt.

q.e.d.

In folgender Tabelle sind für verschiedene Intervalle und Gewichtsfunktionen die Bezeichnungen der zugehörigen orthogonalen Polynome aufgelistet:

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. TeX parse error: Bracket argument to \\ must be a dimension“): {\displaystyle {\begin{array}{|c|c|c|}\hline {\text{Intervall}}&{\text{Gewichtsfunktion }}w(x)&{\text{Name}}\\\hline [-1,1]&1&{\text{Legendre-Polynome}}\\[-1,1]&(1-x)^{\alpha }(1+x)^{\beta },\alpha ,\beta >-1&{\text{Jacobi-Polynome}}\\[-1,1]&1/{\sqrt {1-x^{2}}}&{\text{Tschebyscheff-Pol. der 1. Art}}\\[-1,1]&{\sqrt {1-x^{2}}}&{\text{Tschebyscheff-Pol. der 2. Art}}\\[0,\infty )&e^{-x^{2}}x^{\alpha },\alpha >-1&{\text{Laguerre-Polynome}}\\(-\infty ,\infty )&e^{-x^{2}}&{\text{Hermite-Polynome}}\\\hline \end{array}}}

Man kann zeigen (siehe z. B. E. W. Cheney: Introduction to Approximation Theory, 2nd ed., Chelsea Publish. Comp., New York, 1982):

Satz 8.32[Bearbeiten]

Für aus (8.43) gilt

Unter allen Polynomen vom Grad mit Hauptkoeffizientem 1 macht also die Norm in (8.40) minimal. Im Fall der Tschebyscheff-Polynome 1. Art minimiert unter all diesen Polynomen überdies die Maximum-Norm (Satz 6.19) und im Fall der Tschebyscheff-Polynome 2. Art (s. Cheney) die (ungewichtete) -Norm

Beispiel 8.33[Bearbeiten]

Mit Satz 8.30 sollen die Legendre-Polynome für berechnet werden. Es ist somit und folglich

Mit ist

und damit weiter . Es ergeben sich ferner

und demnach sowie

so dass folgt

8.5.3 Die Quadraturformeln[Bearbeiten]

Satz 8.34[Bearbeiten]

Für seien die durch (8.43) definierten bezüglich orthogonalen Polynome, die Nullstellen von und die durch
definierten Gewichte. Dann ist die Quadraturformel
(8.53)
interpolatorisch und hat (exakt) den Genauigkeitsgrad .

Beweis.[Bearbeiten]

Nach Definition 8.8 (entsprechend für gewichtete Integrale formuliert) ist aufgrund der Wahl der Gewichte eine interpolatorische Quadraturformel. Nach Korollar 8.9 hat eine solche mindestens den Genauigkeitsgrad . Wir wollen nun zeigen, dass sie mindestens den Genauigkeitsgrad und damit exakt den Genauigkeitsgrad besitzt, wie aus den Argumenten in Abschnitt 8.5.1 hervorgeht.

Es sei beliebig. Dann lässt sich mit gewissen nach einer Polynomdivision mit Rest in der Form

schreiben. Wegen gilt dann

Mit der Lagrangeschen Interpolationsformel (6.7), angewandt auf , erhält man weiter

Somit schließt man

(8.54)

womit der Genauigkeitsgrad von mindestens für nachgewiesen ist.

q.e.d.

Die Quadraturformel in (8.53) mit den in Satz 8.34 genannten Stützstellen und Gewichten bezeichnet man als Gaußsche Quadraturformel. Ihr Genauigkeitsgrad ist optimal, da es keine Quadraturformeln mit Genauigkeitsgrad gibt (vgl. Abschnitt 8.5.1). Weiter hat man:

Lemma 8.35[Bearbeiten]

Für die Gewichte der Gaußschen Quadraturformel von Satz 8.34 gilt
und
(8.55)

Beweis.[Bearbeiten]

Wendet man die Beziehungen (8.54) auf an, so folgt

Weiter gilt sowie z. B. für alle hat. Die Beziehung (8.55) folgt nun mit Satz 8.34 aus

q.e.d.

Anders als bei den abgeschlossenen Newton-Cotes-Formeln haben also die Gaußschen Quadraturformeln für alle positive Gewichte. Mit dem folgenden Satz geben wir abschließend eine Darstellung für den bei der Gauß-Quadratur entstehenden Quadraturfehler an.

Satz 8.36[Bearbeiten]

Es sei und In die Gaußsche Quadraturformel mit Stützstellen . Dann gilt für
mit
und für ein :

Beweis.[Bearbeiten]

Den Satz 8.15 kann man auf den Fall gewichteter Integrale übertragen und dann aufgrund von Satz 8.34 auf die Gaußsche Quadraturformel mit anwenden. Man wählt dort zu den Stützpunkten von die weiteren Stützpunkte , so dass insbesondere

gilt. Weiter folge man dann dem Beweis von Satz 8.15.

q.e.d.

Natürlich ist es auch möglich, summierte Gaußsche Quadraturformeln zu definieren und zu verwenden. Die Resultate in Abschnitt 8.3 lassen sich ganz kanonisch auf solche Formeln übertragen.

8.5.4 Berechnung der Stützstellen und Gewichte[Bearbeiten]

Beispielsweise für die Tschebyscheff-Polynome 1. Art kann man die Nullstellen explizit angeben (vgl. Satz 6.18). Im allgemeinen steht man bei Verwendung der Gaußschen Quadraturformeln für größere Werte von aber vor dem Problem, die Nullstellen des Polynoms der bezüglich orthogonalen Polynome und/oder die Gewichte zu bestimmen. Wir wollen hier abschließend einen Weg zu ihrer Berechnung aufzeigen. Dazu gehen wir davon aus, dass die Koeffizienten und in der Rekursionsformel (8.43) für die orthogonalen

(8.56)
(8.57)

bereits bekannt sind und somit die symmetrische Tridiagonalmatrix

(8.58)

aufgestellt werden kann. Der folgende Satz besagt nun, dass die Stützstellen der Gaußschen Quadraturformeln die Eigenwerte von sind und sich deren Gewichte aus zugehörigen Eigenvektoren bestimmen lassen.

Satz 8.37[Bearbeiten]

Für die Stützstellen und die Gewichte der Gaußschen Quadraturformel gilt mit
für
wobei die bezüglich orthogonalen Polynome seien:
(8.59)
und
(8.60)

Beweis.[Bearbeiten]

Aus den Definitionen von und ergibt sich

Definiert man und berücksichtigt man , so erhält man aus den Rekursionsformeln (8.56) und (8.57) mit weiter

Damit ist (8.59) bewiesen.

Gleichung (8.59) besagt, dass Eigenvektor zum Eigenwert der Matrix ist. Gemäß Satz 8.31 sind diese Eigenwerte paarweise verschieden. Da für eine reelle symmetrische Matrix Eigenvektoren zu paarweise verschiedenen Eigenwerten orthogonal zueinander sind, folgt

(8.61)

Da ferner die Polynome paarweise orthogonal sind und die Gaußsche Quadraturformel alle exakt integriert, folgt weiter mit Satz 8.34

(8.62)

wobei das Kroneckersymbol ist. Multiplikation von (8.62) mit und anschließende Summation über liefert schließlich unter Verwendung von (8.61)

Damit ist auch die Gültigkeit von (8.60) bewiesen.

q.e.d.

Beispiel 8.38[Bearbeiten]

Wir verwenden Satz 8.37 für die Herleitung der Gaußschen Quadraturformel mit zur näherungsweisen Berechnung des Integrals

Beispiel 8.33 liefert

Die Eigenwerte von berechnen sich aus

so dass man die Stützstellen und erhält. Weiter hat man

sowie

Mit

hat man

und demnach

Man erhält also die Gaußsche Quadraturformel

Die gesuchten Eigenwerte von müssen aber, zumindest für größere , normalerweise mit einer numerischen Methode bestimmt werden.