Kurs:Numerik I/8 Numerische Integration

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).

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  
 

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  

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)  

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)  

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)  

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
 

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
 

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)  

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)  

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  
 

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  .

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
 

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.

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  .

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)  

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  :
 

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)  

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.