Benutzer:Fritz Bierbaum/Spielwiese

Übersicht

Für das zu integrierende Interpolationspolynom $\ p_{n}(x)$ vom Grad $\ n$ werden die Stützstellen

$a\leq x_{0}<x_{1}<\ldots <x_{n}\leq b$

äquidistant mit dem konstanten Abstand $\ h=x_{i+1}-x_{i}$ so gewählt, dass sie symmetrisch zur Intervallmitte $\ {\tfrac {a+b}{2}}$ des Integrationsintervalls $\ [a,b]$ liegen. Somit gilt $\textstyle x_{n-i}={\tfrac {a+b}{2}}-x_{i}$ .

Durch Integration von $\ p_{n}(x)$ erhält man eine Näherung für das gesucht Integral.

Es gilt $\textstyle \int _{a}^{b}f(x)dx=\int _{a}^{b}p_{n}(x)dx+E(f)$, wobei $\ E(f)$ der Fehler der Näherung (Verfahrensfehler) ist.

Mit $\ x_{0}=a$ (und somit $\ x_{n}=b$ ) erhält man $\ n$ Intervalle der Länge $\ h$ und somit $\ h={\tfrac {b-a}{n}}$ und $\ x_{i}=a+i\cdot h$. Diese Formeln werden abgeschlossene Newton-Cotes-Formeln genannt.

Mit $\ x_{0}\neq a$ (und somit $\ x_{n}\neq b$ ) erhält man offene Quadratur-Formeln:

• Wählt man $\ x_{0}$ (und somit $\ x_{n}=b$ ) , so dass $\ x_{0}-a=x_{1}-x_{0}=h$ , erhält man $\ n+2$ Intervalle der Länge $\ h$ und somit $\ h={\tfrac {b-a}{n+2}}$ und $\ x_{i}=a+(i+1)\cdot h$ . Diese Formeln werden offene Newton-Cotes-Formeln genannt.

• Wählt man $\ x_{0}>a$ , so dass $\ x_{0}-a={\tfrac {x_{1}-x_{0}}{2}}={\tfrac {h}{2}}$ , erhält man $\ n+1$ Intervalle der Länge $\ h$ und somit $\ h={\tfrac {b-a}{n+1}}$ und $\ x_{i}=a+({\tfrac {i}{2}}+1)\cdot h$ . Diese Formeln werden Maclaurin-Formeln genannt.

Allgemeine Formeln

Quadraturformeln

Für das Interpolationspolynom $\textstyle p_{n}(x)$ der Funktion $\ f(x)$ gilt folgende Formel nach Lagrange

$\ p_{n}(x)=\sum _{i=0}^{n}f(x_{i})L_{in}(x),$

wobei für die Lagrange-Polynome $\ L_{in}(x)$ gilt

$L_{in}(x)={\frac {(x-x_{0})\cdots (x-x_{i-1})(x-x_{i+1})\cdots (x-x_{n})}{(x_{i}-x_{0})\cdots (x_{i}-x_{i-1})(x_{i}-x_{i+1})\cdots (x_{i}-x_{n})}}.$

Durch Integration von $\ p_{n}(x)$ erhält man die Quadraturformel

$\int _{a}^{b}f(x)dx\approx \int _{a}^{b}p_{n}(x)dx=\sum _{i=0}^{n}f(x_{i})\int _{a}^{b}L_{in}(x)dx=(b-a)\sum _{i=0}^{n}w_{i}f(x_{i})$

mit den Gewichten

$w_{i}={\frac {1}{(b-a)}}\int _{a}^{b}L_{in}(x)dx.$

Da die Stützstellen symmetrisch sind, sind auch die Gewichte symmetrisch, das heißt $\ w_{n-i}=w_{i}$.

Ordnung, Genauigkeitsgrad

Durch obige Quadraturformeln werden per Konstruktion Polynome mindestens bis zum Grad n exakt integriert. Somit haben die Formeln mindestens die Ordnung (oder den Genauigkeitsgrad) n.

Speziell gilt für $\ f(x)=1$, dass $\textstyle \int _{a}^{b}f(x)dx=\int _{a}^{b}1dx=b-a=(b-a)\sum _{i=0}^{n}w_{i}\cdot 1=(b-a)\sum _{i=0}^{n}w_{i}$ und somit

$\sum _{i=0}^{n}w_{i}=1.$

Falls $\textstyle \sum _{i=0}^{n}|w_{i}|>\sum _{i=0}^{n}w_{i}=1$, was bei negativen Gewichten der Fall ist, besteht die Gefahr, dass sich die Rundungsfehler aufschaukeln oder Auslöschung eintritt. Daher sind aus numerischen Gründen Quadraturformeln mit positiven Gewichten zu bevorzugen. Da für großes n das Interpolationspolynom $\ p_{n}(x)$ unbrauchbar ist, sind ebenso Quadraturformeln mit großem n nicht empfehlenswert. Will man bessere Näherungen erreichen, so empfiehlt sich die Verwendung von zusammengesetzten Quadraturformeln.

Verfahrensfehler

Für das Interpolationspolynom $\ p_{n}(x)$ einer (n+1)-mal stetig differenzierbaren Funktion $\ f(x)$ gilt die Fehlerformel

$f(x)-p_{n}(x)={\frac {(x-x_{0})\cdots (x-x_{n})}{(n+1)!}}f^{(n+1)}(\zeta (x)),$

wobei $\ \zeta (x)$ ein nur in Ausnahmefällen bestimmbarer Wert aus dem kleinste Intervall ist, das alle Stützstellen $\ x_{i}$ und die Auswertestelle $\ x$ enthält. Durch Integration der rechten Seite erhält man den Verfahrensfehler

$\ E(f)=\int _{a}^{b}(f(x)-p_{n}(x))dx={\frac {\int _{a}^{b}(x-x_{0})\cdots (x-x_{n})f^{(n+1)}(\zeta (x))dx}{(n+1)!}}.$

Wegen der speziellen Wahl der Stützstellen bei allen oben genannten Quadraturformeln erhält man für den Fehler $\ E(f)$ die gleichen Formeln

• Falls n ungerade ist und $\ f(x)$ (n+1)-mal stetig differenzierbar ist, gilt

$E(f)={\frac {\int _{a}^{b}(x-x_{0})\cdots (x-x_{n})dx}{(n+1)!}}f^{(n+1)}(\xi )$ mit $\xi \in [a,b].$

• Falls n gerade ist und $\ f(x)$ (n+2)-mal stetig differenzierbar ist, gilt

$E(f)={\frac {\int _{a}^{b}x(x-x_{0})\cdots (x-x_{n})dx}{(n+2)!}}f^{(n+2)}(\xi )$ mit $\xi \in [a,b].$

In beiden Formeln ist der Zwischenwert $\ \xi$ nur in Ausnahmefällen bekannt. Wäre er generell bekannt, könnte man $\ E(f)$ und somit auch das Integral exakt ausrechnen, im Widerspruch zu der Tatsache, dass man die meisten Integrale nicht exakt berechnen kann.

Aus obiger Formel folgt, dass die Ordnung des Quadraturverfahrens für gerades n sogar n+1 ist. Somit sind Quadraturformeln mit geradem Grad denen mit ungeradem Grad vorzuziehen.

Konkrete Formeln

Abgeschlossene Newton-Cotes-Formeln

Die Stützstellen $t_{i}$ gelten für das Integrationsintervall [0,1]: $t_{0}=0,t_{i}={\tfrac {i}{n}},t_{n}=1$. Für ein allgemeines Intervall [a,b] sind die Stützstellen $x_{i}=a+t_{i}\cdot (b-a)$.

Grad $n$	Name	Stützstellen $t_{i}$	Gewichte $w_{i}$	Fehlerschranke
1	Trapezregel / Sekantentrapezregel	$0\quad 1$	${\frac {1}{2}}\quad {\frac {1}{2}}$	$-{\frac {(b-a)^{3}}{12}}f''(\xi )$
2	Simpsonregel / Keplersche Fassregel	$0\quad {\frac {1}{2}}\quad 1$	${\frac {1}{6}}\quad {\frac {4}{6}}\quad {\frac {1}{6}}$	$-{\frac {({\frac {b-a}{2}})^{5}}{90}}f^{(4)}(\xi )$
3	3/8 - Regel / Pulcherrima	$0\quad {\frac {1}{3}}\quad {\frac {2}{3}}\quad 1$	${\frac {1}{8}}\quad {\frac {3}{8}}\quad {\frac {3}{8}}\quad {\frac {1}{8}}$	$-{\frac {3({\frac {b-a}{3}})^{5}}{80}}f^{(4)}(\xi )$
4	Milne-Regel / Boole-Regel	$0\quad {\frac {1}{4}}\quad {\frac {2}{4}}\quad {\frac {3}{4}}\quad 1$	${\frac {7}{90}}\quad {\frac {32}{90}}\quad {\frac {12}{90}}\quad {\frac {32}{90}}\quad {\frac {7}{90}}$	$-{\frac {8({\frac {b-a}{4}})^{7}}{945}}f^{(6)}(\xi )$
5	6-Punkt-Regel	$0\quad {\frac {1}{5}}\quad {\frac {2}{5}}\quad {\frac {3}{5}}\quad {\frac {4}{5}}\quad 1$	${\frac {19}{288}}\quad {\frac {75}{288}}\quad {\frac {50}{288}}\quad {\frac {50}{288}}\quad {\frac {75}{288}}\quad {\frac {19}{288}}$	$-{\frac {275({\frac {b-a}{5}})^{7}}{12096}}f^{(6)}(\xi )$
6	Weddle-Regel	$0\quad {\frac {1}{6}}\quad {\frac {2}{6}}\quad {\frac {3}{6}}\quad {\frac {4}{6}}\quad {\frac {5}{6}}\quad 1$	${\frac {41}{840}}\quad {\frac {216}{840}}\quad {\frac {27}{840}}\quad {\frac {272}{840}}\quad {\frac {27}{840}}\quad {\frac {216}{840}}\quad {\frac {41}{840}}$	$-{\frac {9({\frac {b-a}{6}})^{9}}{1400}}f^{(8)}(\xi )$
7		$0\quad {\frac {1}{7}}\quad {\frac {2}{7}}\quad {\frac {3}{7}}\quad {\frac {4}{7}}\quad {\frac {5}{7}}\quad {\frac {6}{7}}\quad 1$	${\frac {751}{17280}}\quad {\frac {3577}{17280}}\quad {\frac {49}{640}}\quad {\frac {2989}{17280}}\quad {\frac {2989}{17280}}\quad {\frac {49}{640}}\quad {\frac {3577}{17280}}\quad {\frac {751}{17280}}$	$-{\frac {8183({\frac {b-a}{7}})^{9}}{518400}}f^{(8)}(\xi )$

Für n = 8 gilt $w_{i}<0$ für i = 2,4,6 und $\sum _{i=0}^{n}|w_{i}|=1.45...$. Für n = 10 gilt $\sum _{i=0}^{n}|w_{i}|=3.064709...$

Beispiel:$\int _{1}^{3}{\frac {1}{x}}dx=ln(3)-ln(1)=ln(3)=1.0986123...$

Näherung mit Simpson-Regel (n = 2). Es gilt $\ h={\frac {b-a}{n}}={\frac {2}{2}}=1$ und $\ x_{0}=a=1.$

$\int _{1}^{3}p_{2}(x)dx=2\cdot {\bigg (}{\frac {1}{6}}f(1)+{\frac {4}{6}}f(2)+{\frac {1}{6}}f(3){\bigg )}=2\cdot {\bigg (}{\frac {1}{6}}\cdot 1+{\frac {4}{6}}\cdot {\frac {1}{2}}+{\frac {1}{6}}\cdot {\frac {1}{3}}{\bigg )}={\frac {10}{9}}=1.{\overline {1}}$

Verfahrensfehler: Mit $f^{(4)}(\xi )={\frac {4!}{\xi ^{5}}}$ erhält man $E(f)=-{\frac {1}{90\cdot 2^{5}}}\cdot {\frac {4!}{\xi ^{5}}}=-{\frac {1}{120}}\cdot {\frac {1}{\xi ^{5}}}$ mit $\xi \in [1,3]$

Fehlerabschätzung: $|E(f)|\leq {\frac {1}{120}}\cdot \max _{1\leq \xi \leq 3}|{\frac {1}{\xi ^{5}}}|={\frac {1}{120}}=0.008{\overline {3}}$

Exakter Fehler: $|E(f)|=|\int _{1}^{3}{\frac {1}{x}}dx-\int _{1}^{3}p_{2}(x)dx|=|1.0986123...-1.{\overline {1}}|=0.00124988...<0.008{\overline {3}}$

Offene Newton-Cotes-Formeln

Die Stützstellen $t_{i}$ gelten für das Integrationsintervall [0,1]: $t_{0}={\tfrac {1}{n+2}},t_{i}={\tfrac {i+1}{n+2}},t_{n}={\tfrac {n+1}{n+2}}$. Für ein allgemeines Intervall [a,b] sind die Stützstellen $x_{i}=a+t_{i}\cdot (b-a)$.

Grad $n$	Name	Stützstellen $x_{i}$	Gewichte $w_{i}$	Fehlerschranke
0	Rechteckregel	${\frac {1}{2}}$	$1\quad$	${\frac {(b-a)^{3}}{24}}f^{''}(\xi )$
1		${\frac {1}{3}}\quad {\frac {2}{3}}$	${\frac {1}{2}}\quad {\frac {1}{2}}$	${\frac {({\frac {b-a}{3}})^{3}}{4}}f^{''}(\xi )$
2		${\frac {1}{4}}\quad {\frac {2}{4}}\quad {\frac {3}{4}}$	${\frac {2}{3}}\quad -{\frac {1}{3}}\quad {\frac {2}{3}}$	${\frac {28({\frac {b-a}{4}})^{5}}{90}}f^{(4)}(\xi )$
3		${\frac {1}{5}}\quad {\frac {2}{5}}\quad {\frac {3}{5}}\quad {\frac {4}{5}}$	${\frac {11}{24}}\quad {\frac {1}{24}}\quad {\frac {1}{24}}\quad {\frac {11}{24}}$	${\frac {95({\frac {b-a}{5}})^{5}}{144}}f^{(4)}(\xi )$
4		${\frac {1}{6}}\quad {\frac {2}{6}}\quad {\frac {3}{6}}\quad {\frac {4}{6}}\quad {\frac {5}{6}}$	${\frac {11}{20}}\quad -{\frac {14}{20}}\quad {\frac {26}{20}}\quad -{\frac {14}{20}}\quad {\frac {11}{20}}$	${\frac {41({\frac {b-a}{6}})^{7}}{140}}f^{(6)}(\xi )$
5		${\frac {1}{7}}\quad {\frac {2}{7}}\quad {\frac {3}{7}}\quad {\frac {4}{7}}\quad {\frac {6}{7}}$	${\frac {611}{1440}}\quad -{\frac {453}{1440}}\quad {\frac {562}{1440}}\quad {\frac {562}{1440}}\quad -{\frac {453}{1440}}\quad {\frac {611}{1440}}$	${\frac {5257({\frac {b-a}{7}})^{7}}{8640}}f^{(6)}(\xi )$
6		${\frac {1}{8}}\quad {\frac {2}{8}}\quad {\frac {3}{8}}\quad {\frac {4}{8}}\quad {\frac {6}{8}}\quad {\frac {7}{8}}$	${\frac {460}{945}}\quad -{\frac {954}{945}}\quad {\frac {2196}{945}}\quad -{\frac {2459}{945}}\quad {\frac {2196}{945}}\quad -{\frac {954}{945}}\quad {\frac {460}{945}}$	${\frac {3956({\frac {b-a}{8}})^{9}}{14175}}f^{(8)}(\xi )$

Für n = 5 gilt $\sum _{i=0}^{n}|w_{i}|={\frac {3252}{1440}}=2.258333..$. Für n = 6 gilt $\sum _{i=0}^{n}|w_{i}|={\frac {9679}{945}}=10.24...$

Von diesen Formeln ist nur die Rechteckregel empfehlenswert. Die Formel für n = 1 hat bei höherem Aufwand die gleiche Ordnung wie die Rechteckregel, die höheren Formeln haben negative Gewichte.

Beispiel:$\int _{1}^{3}{\frac {1}{x}}dx=ln(3)-ln(1)=ln(3)=1.0986123...$.

Näherung mit der Formel für n = 2. Es gilt $\ h={\frac {b-a}{n+2}}={\frac {2}{4}}={\frac {1}{2}}$ und $\ x_{0}=a+h={\frac {3}{2}}.$

$\int _{1}^{2}p_{2}(x)dx=2\cdot {\bigg (}{\frac {2}{3}}f({\frac {3}{2}})-{\frac {1}{3}}f({\frac {4}{2}})+{\frac {2}{3}}f({\frac {5}{2}}{\bigg )}=2\cdot {\bigg (}{\frac {2}{3}}\cdot {\frac {2}{3}}-{\frac {1}{3}}\cdot {\frac {2}{4}}+{\frac {2}{3}}\cdot {\frac {2}{5}}){\bigg )}={\frac {49}{45}}=1.0{\overline {8}}$

Verfahrensfehler: it $f^{(4)}(\xi )={\frac {4!}{\xi ^{5}}}$ erhält man $E(f)={\frac {14}{45\cdot 2^{5}}}\cdot {\frac {4!}{\xi ^{5}}}={\frac {7}{960}}\cdot {\frac {1}{\xi ^{5}}}$ mit $\xi \in [1,3]$

Fehlerabschätzung: $|E(f)|\leq {\frac {7}{960}}\cdot \max _{1\leq \xi \leq 3}|{\frac {1}{\xi ^{5}}}|={\frac {7}{960}}=0.007291{\overline {6}}$

Exakter Fehler: $|E(f)|=|\int _{1}^{3}{\frac {1}{x}}dx-\int _{1}^{3}p_{2}(x)dx|=|1.0986123...-1.0{\overline {8}}|=0.0097344...<0.007291{\overline {6}}$

Maclaurin-Quadraturformeln

Die Stützstellen $t_{i}$ gelten für das Integrationsintervall [0,1]: $t_{0}={\tfrac {1}{2n+2}},t_{i}={\tfrac {2i+1}{2n+2}},t_{n}={\tfrac {2n+1}{2n+2}}$. Für ein allgemeines Intervall [a,b] sind die Stützstellen $x_{i}=a+t_{i}\cdot (b-a)$.

Grad $n$	Name	Stützstellen $x_{i}$	Gewichte $w_{i}$	Fehlerschranke
0	Mittelpunktsregel / Rechteckregel	${\frac {1}{2}}$	$1\quad$	${\frac {(b-a)^{3}}{24}}f^{''}(\xi )$
1		${\frac {1}{4}}\quad {\frac {3}{4}}$	${\frac {1}{2}}\quad {\frac {1}{2}}$	${\frac {({\frac {b-a}{2}})^{3}}{12}}f^{''}(\xi )$
2		${\frac {1}{6}}\quad {\frac {1}{2}}\quad {\frac {5}{6}}$	${\frac {3}{8}}\quad {\frac {2}{8}}\quad {\frac {3}{8}}$	${\frac {21({\frac {b-a}{3}})^{5}}{640}}f^{(4)}(\xi )$
3		${\frac {1}{8}}\quad {\frac {3}{8}}\quad {\frac {5}{8}}\quad {\frac {7}{8}}$	${\frac {13}{48}}\quad {\frac {11}{48}}\quad {\frac {11}{48}}\quad {\frac {13}{48}}$	${\frac {103({\frac {b-a}{4}})^{5}}{1440}}f^{(4)}(\xi )$
4		${\frac {1}{10}}\quad {\frac {3}{10}}\quad {\frac {5}{10}}\quad {\frac {7}{10}}\quad {\frac {9}{10}}$	${\frac {275}{1152}}\quad {\frac {100}{1152}}\quad {\frac {402}{1152}}\quad {\frac {100}{1152}}\quad {\frac {275}{1152}}$	${\frac {5575({\frac {b-a}{5}})^{7}}{193536}}f^{(6)}(\xi )$

Für n = 6 gilt $\sum _{i=0}^{n}|w_{i}|=1.363..$. Für n = 8 gilt $\sum _{i=0}^{n}|w_{i}|=3.433...$

Beispiel:$\int _{1}^{3}{\frac {1}{x}}dx=ln(3)-ln(1)=ln(3)=1.0986123...$.

Näherung mit der Formel für n = 2. Es gilt $\ h={\frac {b-a}{n+1}}={\frac {2}{3}}$ und $\ x_{0}=a+{\frac {h}{2}}={\frac {4}{3}}.$

$\int _{1}^{3}p_{2}(x)dx=2\cdot {\bigg (}{\frac {3}{8}}f({\frac {4}{3}})+{\frac {2}{8}}f({\frac {6}{3}})+{\frac {3}{8}}f({\frac {8}{3}}){\bigg )}=2\cdot {\bigg (}{\frac {3}{8}}\cdot {\frac {3}{4}}+{\frac {2}{8}}\cdot {\frac {3}{6}}+{\frac {3}{8}}\cdot {\frac {3}{8}}{\bigg )}={\frac {105}{96}}=1.09375$

Verfahrensfehler: Mit $f^{(4)}(\xi )={\frac {4!}{\xi ^{5}}}$ erhält man $E(f)={\frac {21}{640\cdot 3^{5}}}\cdot {\frac {4!}{\xi ^{5}}}={\frac {7}{2160}}\cdot {\frac {1}{\xi ^{5}}}$ mit $\xi \in [1,3]$

Fehlerabschätzung: $|E(f)|\leq {\frac {7}{2160}}\cdot \max _{1\leq \xi \leq 3}|{\frac {1}{\xi ^{5}}}|={\frac {7}{2160}}=0.0032{\overline {407}}$

Exakter Fehler: $|E(f)|=|\int _{1}^{3}{\frac {1}{x}}dx-\int _{1}^{3}p_{2}(x)dx|=|1.0986123...-1.09375|=0.000486229...<0.0032{\overline {407}}$

Summierte Newton-Cotes-Formeln

Ab Grad 8 treten bei vielen Newton-Cotes-Formeln negative Gewichte auf, was die Gefahr der Auslöschung mit sich bringt. Außerdem kann man i.A. keine Konvergenz erwarten, da die Polynominterpolation schlecht konditioniert ist. Bei größeren Integrationsbereichen $\ [a,b]$ unterteilt man diese daher in einzelne Teilintervalle und wendet auf jedes einzelne Teilintervall eine Formel niedriger Ordnung an.

Literatur

• Hans R. Schwarz, Norbert Köckler: Numerische Mathematik. 6. Auflage. Teubner, Stuttgart 2006, ISBN 3-519-42960-8, S. 311-316.
• Roland W. Freund, Ronald H. W. Hoppe: Stoer/Bulirsch: Numerische Mathematik 1. 10. Auflage. Springer, Berlin 2007, ISBN 978-3-540-45389-5, S. 164-169.
• Michael R. Schäferkotter, Prem K. Kythe: Handbook of Computational Methods for Integration. Chapman & Hall, Boca Raton 2005, ISBN 1-58488-428-2, S. 54-62, 503-505.
• Günter Bärwolf: Numerik für Ingenieure, Physiker und Informatiker. ISBN 978-3-8274-1689-6, Spektrum, München 2007, S. 128.
• Eugene Isaacson, Herbert Bishop Keller: Analyse numerischer Verfahren. ISBN ?, Harri Deutsch, Zürich und Frankfurt a. Main 1973.
• Gisela Engeln-Müllges, Klaus Niederdrenk, Reinhard Wodicka: Numerik-Algorithmen : Verfahren, Beispiele, Anwendungen. ISBN 978-3-642-13472-2, Springer, Berlin und Heidelberg 2011.