6 Numerische Integration - TU Bergakademie Freibergernst/Lehre/Numerik_I/Folien/num1Kapitel6.pdf · Numerik I 261 6.3 Adaptive Integrationsformeln Wendet man eine zusammengesetzte

Numerik I 251

6 Numerische Integration

Ziel numerischer Integration (Quadratur): Naherungswerte fur∫ b

a

f(t) dt.

Wozu? Eine Apparatur liefere Messwerte xi = xi + εi. Angenommen, dieMessfehler εi sind standardnormalverteilt (wahle Einheiten entsprechend!):Wie groß ist die Wahrscheinlichkeit P , dass ein Messwert den wirklichenWert um weniger als zwei Einheiten uberschatzt?

P =1√2π

∫ 2

0

exp

(− t

2

2

)dt = Φ(2)− Φ(0) (≈ .477).

6 Numerische Integration TU Bergakademie Freiberg, WS 2011/12

Numerik I 252

−4 −2 0 2 40

0.2

0.4

0.6

0.8

1

exp(−.5*t2)/(2 π)1/2

−5 0 50

0.2

0.4

0.6

0.8

1

Φ(x)

Aber: Es gibt keine geschlossene Formel fur den Wert von

Φ(x) =1√2π

∫ x

−∞exp

(− t

2

2

)dt

(und vieler anderer Integrale). Selbst wenn geschlossenene Formeln be-kannt sind, ist eine numerische Approximation oft okonomischer.

6 Numerische Integration TU Bergakademie Freiberg, WS 2011/12

Numerik I 253

6.1 Newton-Cotes-Formeln

Gesucht: Wert von I =∫ baf(x) dx.

Idee der interpolatorischen Quadraturformeln:Wahle n + 1 Knoten a ≤ x0 < x1 < · · · < xn−1 < xn ≤ b, bestimme daszugehorige Interpolationspolynom pn ∈Pn fur f

pn(x) =

n∑j=0

f(xj)`j(x) mit `j(x) =

n∏i=0i6=j

x− xixj − xi

(Lagrange-Form) und betrachte∫ b

a

pn(x) dx =n∑j=0

f(xj)

∫ b

a

`j(x) dx︸︷︷︸=:γj

=n∑j=0

γjf(xj)

als Naherung fur I.γj bzw. xj heißen Gewichte bzw. Knoten der Integrationsformel.

6.1 Newton-Cotes-Formeln TU Bergakademie Freiberg, WS 2011/12

Numerik I 254

Die Newton-Cotes-Formeln

I ≈n∑j=0

γ(n)j f(xj)

sind interpolatorische Quadraturformeln mit aquidistanten Knoten

xj = a+ jh (j = 0, 1, . . . , n), wobei h = (b− a)/n.

Bestimmung der Gewichte. Mit der Substitution x = a+ ht, t ∈ [0, n]:

γ(n)j =

∫ b

a

n∏i=0i6=j

x− xixj − xi

dx = h

∫ n

0

n∏i=0i6=j

t− ij − i

dt =: hα(n)j

(α(n)j sind unabhangig von f , a und b). Fur jedes n gelten

α(n)0 + α

(n)1 + · · ·+ α(n)

n = n

und α(n)j = α

(n)n−j (j = 0, 1, . . . , n).


Numerik I 255

Tabelle der Newton-Cotes-Gewichte:

I ≈ b−an

n∑j=0

α(n)j f(a+ jh)

n Name α(n)j (j = 0, 1, . . . , n)

1 Trapezregel 12

12

2 Simpson-Regel 13

43

13

3 3/8-Regel 38

98

98

38

4 Milne-Regel 1445

6445

2445

6445

1445

5 95288

375288

250288

250288

375288

95288

6 Weddle-Regel 41140

216140

27140

272140

27140

216140

41140

Fur großere n treten negative Gewichte auf, die Newton-Cotes-Formelnwerden numerisch unbrauchbar.


Numerik I 256

Fehler der Newton-Cotes-Formeln:

En(f) =

∫ b

a

f(x) dx− hn∑j=0

α(n)j f(a+ jh) =

∫ b

a

wn+1(x)

(n+ 1)!f (n+1)(ζ(x)) dx,

wenn f ∈ C(n+1)[a, b] (vgl. Satz 5.4).

Insbesondere werden Polynome vom Grad ≤ n durch dien-te Newton-Cotes-Formel exakt integriert.

Man kann zeigen: Ist n gerade, so werden sogar Polynome vom Grad n+ 1

exakt integriert.

Exaktheitsgrad der

n-ten Newton-Cotes-Formel=

{n, falls n ungerade,

n+ 1, falls n gerade.


Numerik I 257

Fehlerschranken

|En(f)| =

∣∣∣∣∣∣∫ b

a

f(x) dx− hn∑j=0

α(n)j f(a+ jh)

∣∣∣∣∣∣ ≤ Sn(f)

n Name Sn(f)

1 Trapezregel h3 112 M2

2 Simpson-Regel h5 190 M4

3 3/8-Regel h5 380 M4

4 Milne-Regel h7 8945 M6

5 h7 27512096 M6

6 Weddle-Regel h9 91400 M8

mit Mk := maxa≤x≤b |f (k)(x)| und h = (b− a)/n.


Numerik I 258

6.2 Zusammengesetzte Integrationsformeln

Idee: Unterteile das Integrationsintervall [a, b] in N Teilintervalle der LangeH := (b− a)/N und wende auf jedes Teilintervall

[a+ jH, a+ (j + 1)H] (j = 0, 1, 2, . . . , N − 1),

d.h. zur naherungsweisen Berechnung von∫ a+(j+1)H

a+jHf(x) dx,

die n-te Newton-Cotes-Formel (mit Schrittweite h = H/n) an:∫ b

a

f(x) dx =N−1∑j=0

∫ a+(j+1)H

a+jH

f(x) dx ≈N−1∑j=0

hn∑k=0

α(n)k f(a+ jH + kh)

=N−1∑j=0

hn∑k=0

α(n)k f(a+ (jn+ k)h).

6.2 Zusammengesetzte Integrationsformeln TU Bergakademie Freiberg, WS 2011/12

Numerik I 259

Beispiel fur n = 1: zusammengesetzte Trapezregel.

Hier H = (b− a)/N = h,also N + 1 Stutzstellen: xj = a+ jh, j = 0, 1, . . . , N :

∫ b

a

f(x) dx ≈ h

2

f(x0) + 2

N−1∑j=1

f(xj) + f(xN )

=: T (h).

Fehler: ∣∣∣∣∣∫ b

a

f(x)dx− T (h)

∣∣∣∣∣ ≤ b− a12

M2 h2

mit M2 = maxa≤x≤b |f ′′(x)|.

Aufwand zur Berechnung von T (h): N + 1 Funktionsauswertungen.


Numerik I 260

Beispiel fur n = 2: zusammengesetzte Simpson-Regel.

Hier H = (b− a)/N = 2h, d.h. h = (b− a)/(2N),also 2N + 1 Stutzstellen: xj = a+ jh, j = 0, 1, . . . , 2N :

∫ b

a

f(x)dx ≈ h

3

f(x0) + 4N−1∑j=0

f(x2j+1) + 2N−1∑j=1

f(x2j) + f(x2N )

=: S(h).

Fehler: ∣∣∣∣∣∫ b

a

f(x) dx− S(h)

∣∣∣∣∣ ≤ b− a180

M4 h4 =

b− a2880

M4H4

mit M4 = maxa≤x≤b |f (4)(x)|.

Aufwand zur Berechnung von S(h): 2N + 1 Funktionsauswertungen.


Numerik I 261

6.3 Adaptive Integrationsformeln

Wendet man eine zusammengesetzte Quadraturformel auf I =∫ baf(x) dx

an, so ist es nicht immer sinnvoll, das Integrationsintervall [a, b] in gleich-lange Teilintervalle der Lange H zu unterteilen: Der Quadraturfehler hangtvon einer (hoheren) Ableitung von f ab und die kann in [a, b] stark variieren.

Fur beispielsweise

f(x) =x

x2 − 1, x ∈ [1.001, 10],

bewegt sich die vierte Ableitung (die den Fehler bei der zusammengesetz-ten Simpson-Regel kontrolliert) zwischen 1.2 · 108 (am linken Rand) und2.7·10−4 (am rechten Rand). Man erwartet, dass man am rechten Ende desIntervalls mit wesentlich weniger Stutzstellen (d.h. wesentlich geringeremRechenaufwand) eine akzeptable Naherung des Integrals bestimmen kannals in der Umgebung von 1.001.

6.3 Adaptive Integrationsformeln TU Bergakademie Freiberg, WS 2011/12

Numerik I 262

Bestimme

I =

∫ 10

1.001

x

x2 − 1dx =

1

2

[log(x+ 1) + log(x− 1)

]101.001

= 5.4046 . . .

Zusammengesetzte Simpson-Regel

N h # f(x) |I − S(h)|103 4.5 · 10−3 2 · 103 + 1 2.2 · 10−1

104 4.5 · 10−4 2 · 104 + 1 4.9 · 10−4

105 4.5 · 10−5 2 · 105 + 1 6.8 · 10−8

Adaptive Simpson-Regel

# f(x) |I − S(h)|61 1.4 · 10−4

641 1.3 · 10−10


Numerik I 263

Gegeben ist eine Quadraturformel, z.B. die Simpson-Regel S(H), mit einerFehlerabschatzung, hier:

I − S(H) = cH4 +O(H5).

Gesucht ist eine Naherung fur I, die sich zusammensetzt aus NaherungenI(j)0 fur

∫ xj+1

xjf(x) dx uber Teilintervallen unterschiedlicher Lange Hj =

xj+1 − xj , so dass ∣∣∣∣∣∣I −N∑j=0

I(j)0

∣∣∣∣∣∣ ≤ ε := tol ·∫ b

a

|f(x)| dx

gilt. Weder die Anzahl (N + 1) der Teilintervalle noch die Unterteilungs-punkte xj+1 := xj +Hj (j = 0, . . . , N − 1) sind a priori bekannt.


Numerik I 264

Wir wollen den Fehler ”gleichmaßig auf die Teilintervalle verteilen“, d.h. Hj

soll so gewahlt werden, dass∣∣∣∣∣∫ xj+Hj

xj

f(x) dx− I(j)0

∣∣∣∣∣ ≤ Hj

b− aε

erfullt ist.

Wichtige Beobachtung: Aus

I − S(H) = cH4 +O(H5) und I − S(H/2) = c (H/2)4 +O(H5)

folgtS(H/2)− S(H) = c (1− 2−4)H4 +O(H5)

also, falls H ”genugend klein“ ist,

I − S(H) ≈ S(H/2)− S(H)

1− 2−4. (∗)


Numerik I 265

Strategie zur Schrittweitenwahl (Schrittweitensteuerung):

Angenommen H0, . . . ,Hj−1 (dh. x0, . . . xj) sind bereits bestimmt. Außer-dem ist eine Vorschlagsschrittweite Hj gegeben.

1. Setze Hj = Hj . Bestimme mit I(j)0 = S(Hj) eine Naherung fur∫ xj+Hj

xjf(x) dx.

2. Bestimme mit I(j)1 = S(Hj/2) eine ”bessere“ Naherung fur∫ xj+Hj

xjf(x) dx.

3. Uberprufe, ob

|I(j)1 − I(j)0 | ≤ (1− 2−4)Hj

b− aε

erfullt ist (vgl. (∗)).• Falls ja: Akzeptiere I(j)1 als Naherung.• Falls nein: Setze Hj = Hj/2, I(j)0 = I

(j)1 und gehe zu 2.


Numerik I 266

4. Uberprufe, ob

|I(j)1 − I(j)0 | ≤ (2.5)−4(1− 2−4)Hj

b− aε

erfullt ist (2.5 = Sicherheitsfaktor).• Falls ja: Neue Vorschlagsschrittweite: Hj+1 = 2Hj .• Falls nein: Neue Vorschlagsschrittweite: Hj+1 = Hj .

Praxis: Unter- und Oberschranken fur Hj (zu kleine Schrittweiten fuhren zuverstarktem Rundungsfehlereinfluss, zu große Schrittweiten konnen dazufuhren, dass Bereiche, in denen f stark variiert, ubersprungen werden).


Numerik I 267

Beispiel. f(x) =1

(x− .3)2 + .01+

1

(x− .9)2 + .04− 6, a = 0, b = 1.

0 0.2 0.4 0.6 0.8 10

10

20

30

40

50

60

70

80

90

100Integral = 29.8583

108 Funktionsauswertungen


Numerik I 268

6.4 Gauß-Quadratur

Prinzip: Gauß-Formeln sind (wie die Newton-Cotes-Formeln) interpolatorischeQuadraturformeln ∫ b

a

f(x)w(x) dx =

n∑k=0

ωkf(xk) +Rn(f). (6.1)

Rn(f) bezeichnet den Quadraturfehler.

Man erlaubt hier sog. Gewichtsfunktionen w(x), welche gewisse Bedingungen (z.B.w(x) ≥ 0 fur alle x ∈ (a, b)) mussen. Gebrauchliche Gewichtsfunktionen sind:

[a, b] w(x) Name

[−1, 1] 1 Gauß-Legendre

[−1, 1] (1− x2)−1/2 Gauß-Tschebyscheff

[0,∞] exp(−x) Gauß-Laguerre

[−∞,∞] exp(−x2) Gauß-Hermite

6.4 Gauß-Quadratur TU Bergakademie Freiberg, WS 2011/12

Numerik I 269

Im Gegensatz zu den Newton-Cotes-Formeln wahlt man die Knoten xknicht aquidistant, sondern bestimmt Knoten xk und Gewichte ωk so, dasssich ein moglichst hoher Exaktheitsgrad ergibt.

Heuristik: ∫ b

a

xjw(x) dx =

n∑k=0

ωkxjk

ist fur jedes j = 0, 1, . . . eine nichtlineare Gleichung mit 2n + 2 freienParametern

ωk, xk, k = 0, . . . , n.

Es scheint moglich, diese Gleichung fur j = 0, . . . , 2n + 1 zu erfullen(Exaktheitsgrad 2n+ 1).


Numerik I 270

Die Gauß-Quadratur ist eng mit der Theorie der Orthogonalpolynome ver-knupft:

Definiere (fur Polynome p und q) das Innenprodukt

(p, q) :=

∫ b

a

p(x)q(x)w(x) dx.

Dann gibt es fur j = 0, 1, . . . eindeutig bestimmte Polynome (sog. Orthogo-nalpolynome) pj(x) = xj + πj,j−1x

j−1 + . . .+ πj,1x+ πj,0 mit

(pj , pk) = 0 fur alle j 6= k.

Es gilt die dreistufige Rekursionsformel p−1(x) = 0, p0(x) = 1,

pj+1(x) = (x− δj+1)pj(x)− γj+1pj−1(x) fur j = 0, 1, . . . ,

wobei δj+1 = (xpj , pj)/(pj , pj) und γj+1 = (pj , pj)/(pj−1, pj−1).


Numerik I 271

Es bezeichne P den Raum aller Polynome (beliebigen Grades) in einerVariablen.

Satz 6.1 (Jacobi,1826) Sei m ∈ N0. Die Quadraturformel (6.1) besitztgenau dann Exaktheitsgrad d = n+m, wenn folgende beide Bedingungenerfullt sind:

(a) (6.1) ist interpolatorisch.

(b) Das Knotenpolynom ωn+1(x) =∏nj=0(x − ξj) ist orthogonal zu Pm−1

bezuglich des Innenproduktes

(p, q) =

∫ b

a

p(x)q(x)w(x)dx, p, q ∈P. (6.2)

Bemerkung 6.2 Bedingung (b) ist maximal furm = n+1 erfullbar (warum?),was auf den maximalen Exaktheitsgrad d = 2n+ 1 fuhrt.


Numerik I 272

Die Nullstellen t(n)j von pn+1 sind alle reell und einfach, genauer:

a < t(n)0 < t

(n)1 · · · < t(n)n < b.

Sie sind die Knoten xk (0 ≤ k ≤ n) der Gauß-Quadraturformel.

Die Gewichte ωk wahlen wir als Losung vonp0(x0) p0(x1) . . . p0(xn)

p1(x0) p1(x1) . . . p1(xn)...

.... . .

...

pn(x0) pn(x1) . . . pn(xn)

ω0

ω1

...

ωn

=

(p0, 1) =

∫ baw(x)dx

0...

0

.

Man kann zeigen, dass dieses System eindeutig losbar ist und dass dieLosungen ωk alle positiv sind.Die Knoten und Gewichte konnen noch effizienter durch Losung einerverwandten Eigenwertaufgabe berechnet werden.


Numerik I 273

Mit dieser Wahl der Knoten und Gewichte gilt:∫ b

a

p(x)w(x) dx =

n∑k=0

ωkp(xk)

fur alle Polynome p vom Grad ≤ 2n+ 1.

Beispiel: Fur die Gewichtsfunktion w(x) = (1− x2)−1/2 erhalt man

Knoten: xk = cos

(2k + 1

2(n+ 1)π

), k = 0, 1, . . . , n,

Gewichte: ωk = π/(n+ 1), k = 0, 1, . . . , n.

(Dass die Gewichte unabhangig von k sind, trifft auf andere Gauß-Formeln nichtzu!) Gauß-Tschebyscheff-Quadraturformel:∫ 1

−1

f(x)(1− x2)−1/2 dx =π

n+ 1

n∑k=0

f

(cos

(2k + 1

2(n+ 1)π

))+Rn(f)

mit Rn(f) = f(2n+2)(ξ)(2n+2)!

(pn, pn) falls f ∈ C(2n+2)[a, b].


Documents

6 Numerische Integration - TU Bergakademie Freibergernst/Lehre/Numerik_I/Folien/num1Kapitel6.pdf · Numerik I 261 6.3 Adaptive Integrationsformeln Wendet man eine zusammengesetzte