Numerikus módszerek 2. 12. előadás: Numerikus integrálás I.
Krebsz Anna ELTE IK
2015. május 5.
Tartalomjegyzék
1 Numerikus integrálás
2 Newton–Cotes típusú kvadratúra formulák
3 Hibaformulák
4 Összetett formulák
Tartalomjegyzék
1 Numerikus integrálás
2 Newton–Cotes típusú kvadratúra formulák
3 Hibaformulák
4 Összetett formulák
Numerikus integrálás
Feladat: az Z
a
b
f (x) dx
illetve az
Z
b
f (x)w (x) dx
a
Riemann integrál közelítő kiszámítása, ahol w (x) ≥ 0 súlyfüggvény. Kézenfekvő lenne a definícióval (alsó- és felső közelítő összegekkel vagy Riemann közelítő összeggel) számolni, azonban így túl sokat kellene számolnunk a pontosabb eredmény eléréséhez. → Nem gazdaságos.
Numerikus integrálás Alkalmazási területei a matematikában: • Amikor a primitív függvény nem állítható elő zárt alakban. • Az analitikus integrálás túl bonyolult lenne. • Terület, térfogat, ívhossz számításnál. • Differenciálegyeletek numerikus módszereinél a módszerek
konstrukciójakor. Példa: Számítsuk ki a következő integrálok értékét! Z
0
1
2
e −x dx =?,
Z
π 0
cos(x 2 ) dx =?
Numerikus integrálás
Alkalmazási területei a fizikában: : • Pl. forgatónyomaték, sűrűség, görbület számításnál. • Ha a függvény csak mintavételezéssel adott.
Példa: Egy gazdaság területe egy folyó egyenes 10 km hosszú partszakaszának egyik partján fekszik. A folyó mentén kilométerenként megmérték, hogy a folyóra merőleges irányban hány kilométerre nyúlik a gazdaság területe. A kapott 11 értékből számítsuk ki közelítően a gazdaság területét!
Numerikus integrálás Ötlet: Tekintsük az a ≤ x0 < x1 < . . . < x ≤ b felosztást és w (x) ≥ 0 R n súlyfüggvényt. Feltesszük, hogy ab w (x) dx < ∞. Közelítsük az f (x) függvényt az interpolációs polinomjának Lagrange-alakjával, Ln (x)-el. Z
a
b
f (x)w (x) dx ≈ =
Z
b
Ln (x)w (x) dx =
a
n X
k=0
Z
b
n X
a k=0
f (xk )
Z |
b a
f (xk )ℓk (x)w (x) dx =
ℓk (x)w (x) dx = {z
=:Ak
}
n X
Ak f (xk )
k=0
Megj.: Ak csak az alappontoktól és a súlyfüggvénytől függ, f -től nem. Szingularitással rendelkező függvények esetén lesz szerepe a súlyfüggvénynek.
Numerikus integrálás Definíció: Interpolációs kvadratúra formulák Pn
1
A
2
A kvadratúra formula interpolációs típusú, ha Rb Ak = a ℓk (x)w (x) dx (k = 0, . . . , n).
k=0 Ak f
(xk ) formulát kvadratúra formulának nevezzük.
Tétel: Pontossági tétel
∀ f ∈ Pn -re
Z
b
f (x)w (x) dx =
a
⇔ Biz.: Táblán.
Ak =
n X
k=0 Z b a
Ak f (xk ) ℓk (x)w (x) dx (k = 0, . . . , n)
Numerikus integrálás
Következmény: 1
f ≡ 1-re pontos a formula: n X
Ak =
k=0 2
Z
a
b
w (x) dx =: µ0 .
Ha w (x) ≡ 1, akkor n X
k=0
Ak = b − a.
Numerikus integrálás P
Megjegyzés.: A nk=0 Ak f (xk ) képletben 2(n + 1) szabad paraméter van (Ak , xk ), a legfeljebb n + 1-edfokú polinomokra való pontosság kevésnek tűnik. Kvadratúra formula típusok: 1
Newton–Cotes típus: w (x) ≡ 1 és az {xi : i = 0, . . . , n} alappontok egyenletes felosztású pontok [a; b]-n.
2
Csebisev típus: Ak ≡ A (k = 0, . . . , n).
3
Gauss típus: maximális fokszámig (2n + 1) pontos formulák.
Tartalomjegyzék
1 Numerikus integrálás
2 Newton–Cotes típusú kvadratúra formulák
3 Hibaformulák
4 Összetett formulák
Newton–Cotes formulák Newton–Cotes típusú kvadratúra formulák: w (x) ≡ 1 és
xk = x0 + kh
• Zárt formulák (Z (n)): a és b alappont
x0 = a, xn = b, h =
b−a és xk = a + kh (k = 0, . . . , n) n
• Nyílt formulák (Ny (n)): a és b nem alappont
h=
b−a , xk = a+kh (k = 0, . . . , n) azaz x0 = a+h, xn = b−h n+2
Newton–Cotes formulák A zárt N-C együtthatók számítása: x = a + th, t ∈ [0; n]
x − xj = (t − j)h
xk − xj = (k − j)h Ak = At=
x −a h
Z
b a
ℓk (x) dx =
Z
a
b
(x − x0 ) . . .
√ k
. . . (x − xn ) dx √ (xk − x0 ) . . . k . . . (xk − xn )
helyettesítést bevezetve a 7→ 0, b 7→ n és dx = h dt:
Ak = h ·
Z
0
n
(t − 0)(t − 1) . . .
(k − 0)(k − 1) . . .
√ k
√ k
. . . (t − n)
. . . (k − n)
dt
Newton–Cotes formulák
Ak = h ·
Z
0
n
(t − 0)(t − 1) . . .
(k − 0)(k − 1) . . . Z
√ k
√ k
. . . (t − n)
. . . (k − n)
dt =
n t(t − 1) . . . (t − n) (−1)n−k · dt = k!(n − k)! 0 (t − k) Z n (−1)n−k t(t − 1) . . . (t − n) = (b − a) · dt n · k!(n − k)! 0 (t − k)
=h·
(z)
A Bk
|
{z
(z) =Bk
együtthatók függetlenek az [a; b] intervallumtól.
}
Newton–Cotes formulák A nyílt N-C együtthatók számítása. x = a + th, t ∈ [0; n + 2]
x − xj = (t − (j + 1)) h
xk − xj = (k − j)h Ak = At=
x −a h
Z
a
b
ℓk (x) dx =
Z
a
b
(x − x0 ) . . .
(xk − x0 ) . . .
√
k+1
√ k+1
. . . (x − xn )
. . . (xk − xn )
dx
helyettesítést bevezetve a 7→ 0, b 7→ n + 2 és dx = h dt:
Ak = h ·
Z
0
n+2
((t − 1) . . .
√
. . . (t − (n + 1)) dt √ (k − 1) . . . k+1 . . . (k − (n + 1)) k+1
Newton–Cotes formulák
Ak = h ·
Z
n+2
((t − 1) . . . (k − 1) . . .
0
Z
√
k+1
√ k+1
. . . (t − (n + 1))
. . . (k − (n + 1))
dt =
n+2 (t − 1) . . . (t − (n + 1)) (−1)n−k · dt = k!(n − k)! 0 (t − (k + 1)) Z n+2 (−1)n−k (t − 1) . . . (t − (n + 1)) = (b − a) · dt (n + 2) · k!(n − k)! 0 (t − (k + 1))
=h·
(ny )
A Bk
|
{z
(ny)
=Bk
együtthatók függetlenek az [a; b] intervallumtól.
}
Newton–Cotes formulák
Tétel: 1 2
Pn
k=0 Bk
=1
Bk = Bn−k , k = 0, . . . , n
Biz: 1 2
f ≡ 1-re pontos a formula illetve
az alappontok szimmetriájából következik. (y := n − t változó bevezetésével az integrálból.)
Newton–Cotes formulák A N-C formulák együtthatóit más módon is meghatározhatjuk. A Pn -re való pontosság az integrál linearitása miatt azonos az 1, x, x 2 , . . . , x n hatványfüggvényekre való pontossággal. Ebből Ak -ra LER-t írhatunk fel: Z
a
Z
a
Z
a
b
x n dx =
b
b
1 dx = b − a = A0 + A1 + . . . + An
1 x dx = (b 2 − a2 ) = A0 x0 + A1 x1 + . . . + An xn 2 ......
1 (b n+1 − an+1 ) = A0 x0n + A1 x1n + . . . + An xnn n+1
A kapott LER mátrixa a Vandermonde-mátrix transzponáltja, tehát a fenti módszer csak kézi számolásra használható.
Érintő formula (Ny(0)) Érintő formula (Ny(0)) Z
a
b
f ≈ (b − a) · f
a+b 2
=: E (f )
Biz: Táblán. 2.5
2
1.5
1
0.5
0
1
1.5
2
2.5
3
Trapéz formula (Z(1)) Trapéz formula (Z(1)) Z
a
b
f ≈
b−a · (f (a) + f (b)) =: T (f ) 2
Biz: Táblán. 2.5
2
1.5
1
0.5
0
1
1.5
2
2.5
3
Simpson formula (Z(2)) Simpson formula (Z(2)) Z
a
b
b−a f ≈ · f (a) + 4 · f 6
a+b 2
+ f (b) =: S(f )
Biz: Elég A1 -et a definícióból számolni. A1 =
Z
a
b
ℓ1 (x) dx =
Z
a
b
(x − a)(x − b)
a+b 2
−a
Z
a+b 2
−b
dx =
b −4 = (x − a)(x − b) dx = (b − a)2 a Z b −4 = (x 2 − (a + b)x + ab) dx (b − a)2 a
Simpson formula (Z(2)) "
#b
1 3 1 (b − a3 ) − (a + b)(b 2 − a2 ) + ab(b − a) = 3 2
−4 x3 x2 = − (a + b) + ab · x (b − a)2 3 2 = = = =
−4 (b − a)2 −4 6(b − a)2 −4 6(b − a)2 −4 6(b − a)2
=
a
2(b 3 − a3 ) − 3(a + b)(b 2 − a2 ) + 6ab(b − a) =
2b 3 − 2a3 − (3ab 2 − 3a3 + 3b 3 − 3a2 b) + 6ab 2 − 6a2 b =
−b 3 + a3 + 3ab 2 − 3a2 b =
4(b − a)3 4 = (b − a) = A1 2 6(b − a) 6
Innen A0 + A1 + A2 = b − a,
A0 = A2
⇒
1 A0 = A2 = (b − a). 6
Tartalomjegyzék
1 Numerikus integrálás
2 Newton–Cotes típusú kvadratúra formulák
3 Hibaformulák
4 Összetett formulák
Hibaformulák Tétel (Emlékeztető): Az integrálszámítás középértéktétele Ha f ∈ C [a; b] és g ≥ 0, ekkor ∃ ξ ∈ (a; b): Z
a
b
fg = f (ξ) ·
Z
b
g.
a
Tétel: Az érintő formula hibája Ha f ∈ C 2 [a; b], ekkor ∃ η ∈ [a; b]: Z
Biz.: Táblán.
b a
f − E (f ) =
(b − a)3 ′′ · f (η). 24
Hibaformulák Tétel: A trapéz formula hibája Ha f ∈ C 2 [a; b], ekkor ∃ η ∈ [a; b]: Z
b a
f − T (f ) = −
(b − a)3 ′′ · f (η). 12
Biz.: Táblán.
Tétel: A Simpson formula hibája Ha f ∈ C 4 [a; b], ekkor ∃ η ∈ [a; b]: Z
a
Biz.: Táblán.
b
f − S(f ) = −
(b − a)5 (4) · f (η). 2880
Hibaformulák Tétel: A N-C formulák hibája Jelölje I(f ) jelöli a N-C kvadratúra formulát. 1
Ha n páratlan és f ∈ C n+1 [a; b], akkor Z
a
2
b
f (n+1) f − I(f ) = (n + 1)!
Z
b
ωn (x) dx.
a
Ha n páros és f ∈ C n+2 [a; b], akkor Z
a
b
f (n+2) f − I(f ) = (n + 2)!
Z
a
b
x · ωn (x) dx.
Megjegyzés: Vagyis páros n esetén a formula nagyobb pontosságot tud, mint amit elvárunk tőle. (Lásd érintő és Simpson formula.) Nem biz.
Tartalomjegyzék
1 Numerikus integrálás
2 Newton–Cotes típusú kvadratúra formulák
3 Hibaformulák
4 Összetett formulák
Trapéz összetett formula [a; b]-t m egyenlő részre osztjuk és minden részintervallumon trapéz formulát (T (f )) alkalmazunk.
Trapéz összetett formula (Trapéz szabály) Z
a
b
!
m−1 X b−a f ≈ f (xk ) + f (b) · f (a) + 2 2m k=1
=: Tm (f )
Megj.: A megjegyzendő együttható sorozat: 1, 2, 2, . . . , 2, 2, 1.
Tétel: A trapéz összetett formula hibája Ha f ∈ C 2 [a; b], ekkor ∃ η ∈ [a; b]: Z
a
Biz.: Táblán.
b
f − Tm (f ) = −
(b − a)3 ′′ · f (η). 12m2
Simpson összetett formula Legyen m páros és [a; b]-t m egyenlő részre osztjuk, majd az Ik := [x2k−2 , x2k ], (k = 1, . . . , m2 ) részintervallumokra Simpson formulát (S(f )) alkalmazunk. Vagyis a belső felezőpontokat is megszámoztuk, így m2 Simpson formulát használunk.
Simpson összetett formula (Simpson szabály)
Sm (f ) := Z
a
b
m 2 X
m −1 2
b−a · f (a) + 4 f (x2k−1 ) + 2 f (x2k ) + f (b) 3m k=1 k=1
f ≈ Sm (f )
Megj.: A megjegyzendő együttható sorozat: 1, 4, 2, 4, . . . , 4, 2, 4, 1.
X
Simpson összetett formula Tétel: A Simpson összetett formula hibája Ha f ∈ C 4 [a; b], ekkor ∃ η ∈ [a; b]: Z
b
a
f − Sm (f ) = −
(b − a)5 (4) · f (η). 180m4
Biz.: Táblán. Megjegyzés: • Az érintő formulából is készíthető összetett formula az előzőekhez hasonlóan. • Ha f ∈ C 2 [a; b] illetve f ∈ C 4 [a; b], akkor m → ∞ esetén Tm (f ) →
Z
a
b
f , illetve Sm (f ) →
m2 illetve m4 nagyságrendben.
Z
a
b
f
Richardson-féle extrapoláció Richardson-féle extrapoláció a trapéz összetett formulára: Írjuk fel a trapéz összetett formulát m-re és 2m-re: (b − a)3 ′′ · f (η1 ) 12m2 a Z b (b − a)3 ′′ f − T2m (f ) = − · f (η2 ) 48m2 a Z
b
f − Tm (f ) = −
Ha f ′′ elég sima, akkor f ′′ (η1 ) ≈ f ′′ (η2 ), így a 2. egyenlet 4-szereséből kivonva az 1. egyenletet 3
Z
a
b
f − 4T2m (f ) + Tm (f ) ≈ 0 Z
b a
f ≈
1 (4T2m (f ) − Tm (f )) 3
Richardson-féle extrapoláció
A trapéz szabály javító formulája 1 (4T2m (f ) − Tm (f )) = Sm (f ) 3 A közelítés hibája O(h4 ). R
Példa: Az 01 x 1/3 dx integrál kiszámításához a Richardson-féle extrapoláció nem használható, mert f nem deriválható a 0-ban. Az ehhez hasonló szingularitások kezeléséhez más típusú módszerek kellenek. (Lásd Gauss-kvadratúra formulák.)
Richardson-féle extrapoláció Richardson-féle extrapoláció a Simpson összetett formulára: Írjuk fel a Simpson összetett formulát m-re és 2m-re: (b − a)5 (4) · f (η1 ) 180 m4 a Z b (b − a)5 f − S2m (f ) = − · f (4) (η2 ) 180 · 16 m4 a Z
b
f − Sm (f ) = −
Ha f (4) elég sima, akkor f (4) (η1 ) ≈ f (4) (η2 ), így a 2. egyenlet 16-szorosából kivonva az 1. egyenletet 15
Z
b a
f − 16 S2m (f ) + Sm (f ) ≈ 0 Z
b a
f ≈
1 (16 S2m (f ) − Sm (f )) 15
Richardson-féle extrapoláció
A Simpson szabály javító formulája 1 (16 S2m (f ) − Sm (f )) 15 A közelítés hibája O(h6 ).
Richardson-féle extrapoláció Megjegyzés: • A Richarson-féle extrapolációból készített rekurzió a Romberg integrálás alapja. • A gyakorlati számítások során jól használhatók a következő tételek:
Tétel: • Ha f ′′ korlátos [a; b]-n, akkor Z b f − Tm (f ) ≤ |Tm (f ) − T2m (f )|. a • Ha f (4) korlátos [a; b]-n, akkor Z b f − Sm (f ) ≤ |Sm (f ) − S2m (f )|. a
