Newton-Cotes-Formeln

Newton-Cotes-Formel für n = 2

Eine Newton-Cotes-Formel (nach Isaac Newton und Roger Cotes) ist eine Formel für die numerische Integration, also zur näherungsweisen Berechnung von Integralen. Diesen Formeln liegt die Idee zu Grunde, die zu integrierende Funktion durch ein Polynom zu interpolieren und dieses als Näherung exakt zu integrieren. Die Stützstellen der Interpolation werden dabei äquidistant gewählt.

Herleitung

Für das zu integrierende Interpolationspolynom pn(x) vom Grad n werden die Stützstellen

a≤x0<x1<⋯<xn≤b

äquidistant mit dem konstanten Abstand h=xi+1−xi so gewählt, dass sie symmetrisch zur Intervallmitte a+b2 des Integrationsintervalls [a,b] liegen. Somit gilt xn−i=a+b−xi.

Mit x0=a (und somit xn=b) erhält man n Intervalle der Länge h und somit h=b−an und xi=a+i⋅h. Diese Formeln werden abgeschlossene Newton-Cotes-Formeln genannt.

Mit x0≠a (und somit xn≠b) erhält man offene Newton-Cotes-Formeln:

Zur numerischen Integration von ∫abf(x)dx wird das Interpolationspolynom pn(x) der Funktion f(x) zu den gegebenen Stützstellen herangezogen. Für dieses gilt:

pn(x)=∑i=0nf(xi)li(x),

wobei li die Lagrange-Basispolynome sind. Daraus folgt:

∫abpn(x)dx=(b−a)∑i=0nf(xi)1b−a∫abli(x)dx.

Definition

Für die Newton-Cotes-Formel folgt dann:

∫abf(x)dx≈∫abpn(x)dx=(b−a)∑i=0nwif(xi)

mit den Gewichten

wi=1b−a∫abli(x)dx

Die Gewichte sind symmetrisch, das heißt wn−i=wi.

li(x)=∏0≤j≤nj≠ix−xjxi−xj=(x−x0)⋯(x−xi−1)(x−xi+1)⋯(x−xn)(xi−x0)⋯(xi−xi−1)(xi−xi+1)⋯(xi−xn)

Wegen der speziellen Wahl der Stützstellen integrieren diese Formeln bei ungeradem n Polynome bis zum Grad n, bei geradem n sogar bis zum Grad n+1 exakt. Somit sind Newton-Cotes-Formeln mit geradem n (also einer ungeraden Anzahl an Stützstellen) denen mit ungeradem n vorzuziehen. Diese Eigenschaft nennt man auch Genauigkeitsgrad.

Speziell gilt für f(x)=1, dass ∫abf(x)dx=∫ab1dx=b−a=(b−a)∑i=0nwi⋅1=(b−a)∑i=0nwi und somit ∑i=0nwi=1.

Falls ∑i=0n|wi|>∑i=0nwi=1, was bei Gewichten mit verschiedenen Vorzeichen der Fall ist, besteht die Gefahr, dass sich die Rundungsfehler aufschaukeln oder Auslöschung eintritt. Daher sind aus numerischen Gründen Formeln mit positiven Gewichten zu bevorzugen. Da für großes n das Interpolationspolynom pn(x) unbrauchbar ist, sind ebenso Formeln mit großem n nicht empfehlenswert. Will man bessere Näherungen erreichen, so empfiehlt sich die Verwendung von summierten Formeln.

E(f)=∫abf(x)dx−∫abpn(x)dx

ist der Fehler (Verfahrensfehler), der bei der Anwendung der Newton-Cotes-Formel gemacht wird. Dieser hat bei der speziellen Wahl der Stützstellen für (p+1)-mal auf [a,b] stetig differenzierbar reellwertige Funktionen f(x) immer die Form

E(f)=K⋅f(p+1)(ξ),

wobei K eine von f(x) unabhängige Konstante und ξ∈[a,b] ein nur in Ausnahmefällen bekannter Zwischenwert ist. Wäre er generell bekannt, könnte man E(f) und somit auch das Integral exakt ausrechnen, im Widerspruch zu der Tatsache, dass es unendlich viele Integrale gibt, die man nicht exakt berechnen kann. Der Fehler ist Null für alle Funktionen, deren (p+1)-te Ableitung Null ist, also für alle Polynome vom Grad kleiner oder gleich p. Somit ist p der Genauigkeitsgrad. Der Wert p+1 wird auch als (polynomiale) Ordnung der Newton-Cotes-Formel bezeichnet.

Mit Hilfe des Verfahrensfehlers erhält man die Fehlerabschätzung:

|E(f)|≤|K|⋅maxa≤ξ≤b|f(p+1)(ξ)|.

Der exakte Fehler ist immer kleiner oder gleich dieser Fehlerabschätzung, wie auch die unten angegebenen Beispiele zeigen.

Abgeschlossene Newton-Cotes-Formeln

Die angegebenen Stützstellen ti gelten für das Integrationsintervall [0,1]: t0=0,ti=in,tn=1. Für ein allgemeines Intervall [a,b] sind die Stützstellen xi=a+ti⋅(b−a).

n Name Stützstellen ti Gewichte wi E(f)
1Trapezregel
Sehnentrapezregel
01 1212 −(b−a)312f″(ξ)
2Simpson-Regel
Keplersche Fassregel
0121 164616 −(b−a2)590f(4)(ξ)
33/8-Regel
Pulcherrima
013231 18383818 −3(b−a3)580f(4)(ξ)
4Milne-Regel
Boole-Regel
01424341 790329012903290790 −8(b−a4)7945f(6)(ξ)
56-Punkt-Regel 0152535451 192887528850288502887528819288 −275(b−a5)712096f(6)(ξ)
6Weddle-Regel (nach Thomas Weddle, 1817–1853) 016263646561 41840216840278402728402784021684041840 −9(b−a6)91400f(8)(ξ)

Die gekürzten Werte aller Gewichte bis n=10 betragen:

n Gewichte
1 {12,12}
2 {16,23,16}
3 {18,38,38,18}
4 {790,1645,215,1645,790}
5 {19288,2596,25144,25144,2596,19288}
6 {41840,935,9280,34105,9280,935,41840}
7 {75117280,357717280,49640,298917280,298917280,49640,357717280,75117280}
8 {98928350,294414175,−46414175,524814175,−4542835,524814175,−46414175,294414175,98928350}
9 {285789600,1574189600,272240,12095600,288944800,288944800,12095600,272240,1574189600,285789600}
10 {16067598752,26575149688,−16175199584,567512474,−482511088,1780724948,−482511088,567512474,−16175199584,26575149688,16067598752}

Für n=8 gilt wi<0 für i=2,4,6 und ∑i=0n|wi|=1,45… Für n=10 gilt ∑i=0n|wi|=3,064794…

Beispiel: ∫131xdx=ln⁡(3)−ln⁡(1)=ln⁡(3)=1,098612…

Näherung mit Simpson-Regel (n=2). Es gilt h=b−an=22=1 und x0=a=1.

∫13p2(x)dx=2⋅(16f(1)+46f(2)+16f(3))=2⋅(16⋅1+46⋅12+16⋅13)=109=1,1‾

Verfahrensfehler: Mit f(4)(ξ)=4!ξ5 erhält man E(f)=−190⋅(22)5⋅4!ξ5=−415⋅1ξ5 mit ξ∈[1,3]

Fehlerabschätzung: |E(f)|≤415⋅max1≤ξ≤3|1ξ5|=415⋅11=0,26‾

Exakter Fehler: a˘|E(f)|=|∫131xdx−∫13p2(x)dx|=|1,098612…−1,1‾|=0,012498…<0,26‾

Offene Newton-Cotes-Formeln

Die Stützstellen ti gelten für das Integrationsintervall [0,1]: t0=1n+2,ti=i+1n+2,tn=n+1n+2. Für ein allgemeines Intervall [a,b] sind die Stützstellen xi=a+ti⋅(b−a).

n Name Stützstellen ti Gewichte wi E(f)
0Rechteckregel
Mittelpunktsregel
Tangententrapezregel
121(b−a)324f″(ξ)
11323 1212 3(b−a3)34f″(ξ)
2142434 23−1323 14(b−a4)545f(4)(ξ)
315253545 11241241241124 95(b−a5)5144f(4)(ξ)
41626364656 1120−14202620−14201120 41(b−a6)7140f(6)(ξ)
5172737475767 6111440−453144056214405621440−45314406111440 5257(b−a7)78640f(6)(ξ)
618283848586878 460945−9549452196945−24599452196945−954945460945 3956(b−a8)914175f(8)(ξ)

Für n=5 gilt ∑i=0n|wi|=32521440=2,258333… Für n=6 gilt ∑i=0n|wi|=9679945=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: ∫131xdx=ln⁡(3)−ln⁡(1)=ln⁡(3)=1,098612…

Näherung mit der Formel für n=2. Es gilt h=b−an+2=24=12 und x0=a+h=32.

∫13p2(x)dx=2⋅(23f(32)−13f(42)+23f(52))=2⋅(23⋅23−13⋅24+23⋅25)=4945=1,08‾.

Verfahrensfehler: Mit f(4)(ξ)=4!ξ5 erhält man E(f)=1445⋅(24)5⋅4!ξ5=730⋅1ξ5 mit ξ∈[1,3].

Fehlerabschätzung: |E(f)|≤730⋅max1≤ξ≤3|1ξ5|=730⋅11=0,23‾

Exakter Fehler: |E(f)|=|∫131xdx−∫13p2(x)dx|=|1,098612…−1,08‾|=0,009723…<0,23‾

Maclaurin-Formeln

Diese Formeln sind nach Colin Maclaurin benannt. Die Stützstellen ti gelten für das Integrationsintervall [0,1]: t0=12n+2,ti=2i+12n+2,tn=2n+12n+2. Für ein allgemeines Intervall [a,b] sind die Stützstellen xi=a+ti⋅(b−a).

n Name Stützstellen ti Gewichte wi E(f)
0Rechteckregel
Mittelpunktsregel
Tangententrapezregel
121(b−a)324f″(ξ)
11434 1212 (b−a2)312f″(ξ)
2161256 382838 21(b−a3)5640f(4)(ξ)
318385878 1348114811481348 103(b−a4)51440f(4)(ξ)
4110310510710910 27511521001152402115210011522751152 5575(b−a5)7193536f(6)(ξ)

Für n=6 gilt ∑i=0n|wi|=1,363… Für n=8 gilt ∑i=0n|wi|=3,433…

Beispiel: ∫131xdx=ln⁡(3)−ln⁡(1)=ln⁡(3)=1,098612…

Näherung mit der Formel für n=2. Es gilt h=b−an+1=23 und x0=a+h2=43.

∫13p2(x)dx=2⋅(38f(43)+28f(63)+38f(83))=2⋅(38⋅34+28⋅36+38⋅38)=10596=1,09375

Verfahrensfehler: Mit f(4)(ξ)=4!ξ5 erhält man E(f)=21640⋅(23)5⋅4!ξ5=14135⋅1ξ5 mit ξ∈[1,3].

Fehlerabschätzung: |E(f)|≤14135⋅max1≤ξ≤3|1ξ5|=14135⋅11=0,1037‾

Exakter Fehler: |E(f)|=|∫131xdx−∫13p2(x)dx|=|1,098612…−1,09375|=0,000486…<0,1037‾

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 im Allgemeinen 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.