Trapézové pravidlo - Trapezoidal rule

Funkce F(X) (modře) je aproximován lineární funkcí (červeně).

v matematika a konkrétněji v numerická analýza, lichoběžníkové pravidlo (také známý jako lichoběžníkové pravidlo nebo lichoběžníkové pravidlo-vidět Lichoběžník pro více informací o terminologii) je technika aproximace určitý integrál.

${ displaystyle int _ {a} ^ {b} f (x) , dx}$.

Lichoběžníkové pravidlo funguje aproximací oblasti pod grafem funkce${ displaystyle f (x)}$ jako lichoběžník a výpočet jeho plochy. Z toho vyplývá, že

${ displaystyle int _ {a} ^ {b} f (x) , dx cca (b-a) cdot { tfrac {f (a) + f (b)} {2}}}$.

Na lichoběžníkové pravidlo lze pohlížet jako na výsledek získaný průměrováním vlevo, odjet a že jo Riemann součty, a je někdy definována tímto způsobem. Integrál lze ještě lépe aproximovat pomocí rozdělení integračního intervalu, použití lichoběžníkového pravidla na každý subinterval a shrnutí výsledků. V praxi je toto „zřetězené“ (nebo „složené“) lichoběžníkové pravidlo obvykle to, co se rozumí „integrací s lichoběžníkovým pravidlem“. Nechat ${ displaystyle {x_ {k} }}$ být oddílem ${ displaystyle [a, b]}$ takhle ${ displaystyle a = x_ {0}$ a ${ displaystyle Delta x_ {k}}$ být délka ${ displaystyle k}$-tý podinterval (tj. ${ displaystyle Delta x_ {k} = x_ {k} -x_ {k-1}}$), pak

${ displaystyle int _ {a} ^ {b} f (x) , dx přibližně součet _ {k = 1} ^ {N} { frac {f (x_ {k-1}) + f ( x_ {k})} {2}} Delta x_ {k} = { tfrac { Delta x} {2}} left (f (x_ {0}) + 2f (x_ {1}) + 2f ( x_ {2}) + 2f (x_ {3}) + 2f (x_ {4}) + cdots + 2f (x_ {N-1}) + f (x_ {N}) vpravo)}$.

Animace, která ukazuje, co je lichoběžníkové pravidlo a jak se chyba v aproximaci zmenšuje, jak se zmenšuje velikost kroku

Ilustrace „zřetězeného lichoběžníkového pravidla“ použitého na nepravidelně rozmístěném přepážce ${ displaystyle [a, b]}$.

Aproximace se stává přesnější, jak se zvyšuje rozlišení oddílu (tj. Pro větší ${ displaystyle N}$, ${ displaystyle Delta x_ {k}}$ Pokud má oddíl pravidelné mezery, jak se často stává, lze vzorec pro efektivitu výpočtu zjednodušit.

Jak je uvedeno níže, je také možné umístit hranice chyby na přesnost hodnoty určitého integrálu odhadovaného pomocí lichoběžníkového pravidla.

Dějiny

Papír z roku 2016 uvádí, že lichoběžníkové pravidlo bylo používáno v Babylon před 50 př. n. l. pro integraci rychlosti Jupiter podél ekliptický.^[1]

Numerická implementace

Nerovnoměrná mřížka

Když je rozteč mřížek nejednotná, lze použít vzorec

${ displaystyle int _ {a} ^ {b} f (x) , dx přibližně součet _ {k = 1} ^ {N} { frac {f (x_ {k-1}) + f ( x_ {k})} {2}} Delta x_ {k}}$

Jednotná mřížka

Pro doménu diskretizovanou na ${ displaystyle N}$ stejně rozmístěné panely mohou nastat značné zjednodušení. Nechat

${ displaystyle Delta x_ {k} = Delta x = { frac {b-a} {N}}}$

stane se aproximace integrálu

${ displaystyle int _ {a} ^ {b} f (x) , dx přibližně { frac { Delta x} {2}} součet _ {k = 1} ^ {N} vlevo (f (x_ {k-1}) + f (x_ {k}) vpravo)}$

${ displaystyle {} = { frac { Delta x} {2}} (f (x_ {0}) + 2f (x_ {1}) + 2f (x_ {2}) + 2f (x_ {3}) + dotsb + 2f (x_ {N-1}) + f (x_ {N}))}$

${ displaystyle {} = { frac { Delta x} {2}} vlevo (f (x_ {0}) + f (x_ {N}) + 2 součet _ {k = 1} ^ {N- 1} f (x_ {k}) vpravo)}$

${ displaystyle {} = Delta x left ( sum _ {k = 1} ^ {N-1} f (x_ {k}) + { frac {f (x_ {N}) + f (x_ { 0})} {2}} vpravo)}$

což k výpočtu vyžaduje méně hodnocení funkce.

Analýza chyb

Animace ukazující, jak se aproximace lichoběžníkového pravidla zlepšuje s více proužky pro interval s ${ displaystyle a = 2}$ a ${ displaystyle b = 8}$. Jako počet intervalů ${ displaystyle N}$ zvyšuje se také přesnost výsledku.

Chyba složeného lichoběžníkového pravidla je rozdíl mezi hodnotou integrálu a číselným výsledkem:

${ displaystyle { text {error}} = int _ {a} ^ {b} f (x) , dx - { frac {ba} {N}} vlevo [{f (a) + f ( b) přes 2} + součet _ {k = 1} ^ {N-1} f doleva (a + k { frac {ba} {N}} doprava) doprava]}$

Existuje číslo ξ mezi A a b, takový, že^[2]

${ displaystyle { text {error}} = - { frac {(b-a) ^ {3}} {12N ^ {2}}} f '' ( xi)}$

Z toho vyplývá, že pokud je integrand konkávní (a má tedy kladnou druhou derivaci), pak je chyba záporná a lichoběžníkové pravidlo nadhodnocuje skutečnou hodnotu. To lze také vidět z geometrického obrázku: lichoběžníky zahrnují celou plochu pod křivkou a přesahují ji. Podobně, a konkávní dolů funkce poskytuje podhodnocení, protože pod křivkou není plocha započítána, ale žádná se nepočítá výše. Pokud interval aproximovaného integrálu zahrnuje inflexní bod, chybu je těžší identifikovat.

Odhad asymptotické chyby pro N → ∞ je dáno

${ displaystyle { text {error}} = - { frac {(ba) ^ {2}} {12N ^ {2}}} { big [} f '(b) -f' (a) { velký]} + O (N ^ {- 3}).}$

Další pojmy v tomto odhadu chyby jsou dány Euler-Maclaurinovým součtovým vzorcem.

K analýze chyby lze použít několik technik, včetně:^[3]

1. Fourierova řada
2. Zbytkový kalkul
3. Souhrnný vzorec Euler – Maclaurin^[4][5]
4. Polynomiální interpolace^[6]

Tvrdí se, že rychlost konvergence lichoběžníkového pravidla odráží a lze ji použít jako definici tříd hladkosti funkcí.^[7]

Důkaz

Nejprve to předpokládej ${ displaystyle h = { frac {b-a} {N}}}$ a ${ displaystyle a_ {k} = a + (k-1) h}$. Nechat ${ displaystyle g_ {k} (t) = { frac {1} {2}} t [f (a_ {k}) + f (a_ {k} + t)] - int _ {a_ {k} } ^ {a_ {k} + t} f (x) dx}$ být funkcí takovou ${ displaystyle | g_ {k} (h) |}$ je chyba lichoběžníkového pravidla v jednom z intervalů, ${ displaystyle [a_ {k}, a_ {k} + h]}$. Pak

${ displaystyle {dg_ {k} over dt} = {1 nad 2} [f (a_ {k}) + f (a_ {k} + t)] + {1 nad 2} t cdot f ' (a_ {k} + t) -f (a_ {k} + t),}$

a

${ displaystyle {d ^ {2} g_ {k} nad dt ^ {2}} = {1 nad 2} t cdot f '' (a_ {k} + t).}$

Nyní předpokládejme, že ${ Displaystyle left vert f '' (x) right vert leq f '' ( xi),}$ který platí pokud ${ displaystyle f}$ je dostatečně hladký. Z toho pak vyplývá

${ Displaystyle left vert f '' (a_ {k} + t) right vert leq f '' ( xi)}$

což odpovídá${ displaystyle -f '' ( xi) leq f '' (a_ {k} + t) leq f '' ( xi)}$nebo ${ displaystyle - { frac {f '' ( xi) t} {2}} leq g_ {k} '' (t) leq { frac {f '((xi) t} {2} }.}$

Od té doby ${ displaystyle g_ {k} '(0) = 0}$ a ${ displaystyle g_ {k} (0) = 0}$,

${ displaystyle int _ {0} ^ {t} g_ {k} '' (x) dx = g_ {k} '(t)}$ a ${ displaystyle int _ {0} ^ {t} g_ {k} '(x) dx = g_ {k} (t).}$

Pomocí těchto výsledků zjistíme

${ displaystyle - { frac {f '' ( xi) t ^ {2}} {4}} leq g_ {k} '(t) leq { frac {f' '( xi) t ^ {2}} {4}}}$

a

${ displaystyle - { frac {f '' ( xi) t ^ {3}} {12}} leq g_ {k} (t) leq { frac {f '((xi) t ^ { 3}} {12}}}$

Pronájem ${ displaystyle t = h}$ shledáváme

${ displaystyle - { frac {f '' ( xi) h ^ {3}} {12}} leq g_ {k} (h) leq { frac {f '((xi) h ^ { 3}} {12}}.}$

Shrneme-li všechny místní chybové výrazy, které najdeme

${ displaystyle sum _ {k = 1} ^ {N} g_ {k} (h) = { frac {ba} {N}} vlevo [{f (a) + f (b) nad 2} + sum _ {k = 1} ^ {N-1} f left (a + k { frac {ba} {N}} right) right] - int _ {a} ^ {b} f (x) dx.}$

Ale také máme

${ displaystyle - sum _ {k = 1} ^ {N} { frac {f '' ( xi) h ^ {3}} {12}} leq sum _ {k = 1} ^ {N } g_ {k} (h) leq sum _ {k = 1} ^ {N} { frac {f '' ( xi) h ^ {3}} {12}}}$

a

${ displaystyle sum _ {k = 1} ^ {N} { frac {f '' ( xi) h ^ {3}} {12}} = { frac {f '' ( xi) h ^ {3} N} {12}},}$

aby

${ displaystyle - { frac {f '' ( xi) h ^ {3} N} {12}} leq { frac {ba} {N}} doleva [{f (a) + f (b ) přes 2} + součet _ {k = 1} ^ {N-1} f vlevo (a + k { frac {ba} {N}} vpravo) vpravo] - int _ {a} ^ {b} f (x) dx leq { frac {f '' ( xi) h ^ {3} N} {12}}.}$

Proto je celková chyba omezena

${ displaystyle { text {error}} = int _ {a} ^ {b} f (x) dx - { frac {ba} {N}} doleva [{f (a) + f (b) nad 2} + součet _ {k = 1} ^ {N-1} f vlevo (a + k { frac {ba} {N}} vpravo) vpravo] = { frac {f '' ( xi) h ^ {3} N} {12}} = { frac {f '' ( xi) (ba) ^ {3}} {12N ^ {2}}}.}$

Periodické a špičkové funkce

Lichoběžníkové pravidlo konverguje rychle pro periodické funkce. To je snadný důsledek součtového vzorce Euler-Maclaurin, který říká, že pokud ${ displaystyle f}$ je ${ displaystyle p}$ časy průběžně diferencovatelné s obdobím ${ displaystyle T}$

${ displaystyle sum _ {k = 0} ^ {N-1} f (kh) h = int _ {0} ^ {T} f (x) , dx + sum _ {k = 1} ^ { lfloor p / 2 rfloor} { frac {B_ {2k}} {(2k)!}} (f ^ {(2k-1)} (T) -f ^ {(2k-1)} (0) ) - (- 1) ^ {p} h ^ {p} int _ {0} ^ {T} { tilde {B}} _ {p} (x / T) f ^ {(p)} (x ) , mathrm {d} x}$

kde ${ displaystyle h: = T / N}$ a ${ displaystyle { tilde {B}} _ {p}}$ je periodické rozšíření ${ displaystyle p}$Bernoulliho polynom.^[8] Kvůli periodicitě se deriváty v koncovém bodě ruší a vidíme, že chyba je ${ displaystyle O (h ^ {p})}$.

Podobný efekt je k dispozici pro funkce podobné špičkám, jako je například Gaussian, Exponenciálně upravená Gaussian a další funkce s derivacemi na integračních limitech, které lze zanedbávat.^[9] Vyhodnocení úplného integrálu Gaussovy funkce lichoběžníkovým pravidlem s přesností 1% lze provést pomocí pouhých 4 bodů.^[10] Simpsonovo pravidlo vyžaduje 1,8krát více bodů k dosažení stejné přesnosti.^[10][11]

Ačkoli bylo vyvinuto určité úsilí k rozšíření Euler-Maclaurinova součtového vzorce na vyšší dimenze,^[12] nejpřímějším důkazem rychlé konvergence lichoběžníkového pravidla ve vyšších dimenzích je snížení problému na problém konvergence Fourierových řad. Tato úvaha ukazuje, že pokud ${ displaystyle f}$ je periodický na a ${ displaystyle n}$-rozměrný prostor s ${ displaystyle p}$ spojité derivace, rychlost konvergence je ${ displaystyle O (h ^ {p / d})}$. U velmi velké dimenze ukazuje, že integrace Monte-Carlo je s největší pravděpodobností lepší volbou, ale u 2 a 3 dimenzí je efektivní vzorkování efektivní. Toto se využívá ve výpočetní fyzice pevných látek, kde je rovnoměrné vzorkování přes primitivní buňky v reciproční mřížce známé jako Integrace Monkhorst-Pack.^[13]

„Drsné“ funkce

Pro funkce, které nejsou v C², výše uvedená chyba není použitelná. Lze přesto odvodit hranice chyb pro takové hrubé funkce, které obvykle ukazují pomalejší konvergenci s počtem vyhodnocení funkcí ${ displaystyle N}$ než ${ displaystyle O (N ^ {- 2})}$ chování uvedené výše. Je zajímavé, že v tomto případě má lichoběžníkové pravidlo často ostřejší hranice než Simpsonovo pravidlo pro stejný počet vyhodnocení funkcí.^[14]

Použitelnost a alternativy

Lichoběžníkové pravidlo je jednou z rodiny vzorců pro numerická integrace volala Newton – Cotesovy vzorce, z nichž pravidlo středu je podobné lichoběžníkovému pravidlu. Simpsonovo pravidlo je dalším členem stejné rodiny a obecně má rychlejší konvergenci než lichoběžníkové pravidlo pro funkce, které jsou dvakrát spojitě diferencovatelné, i když ne ve všech konkrétních případech. Avšak pro různé třídy drsnějších funkcí (ty se slabšími hladkými podmínkami) má lichoběžníkové pravidlo obecně rychlejší konvergenci než Simpsonovo pravidlo.^[14]

Kromě toho má lichoběžníkové pravidlo tendenci být extrémně přesné, když periodické funkce jsou integrovány během jejich období, což může být analyzovány různými způsoby.^[7][11] Podobný efekt je k dispozici pro špičkové funkce.^[10][11]

Pro neperiodické funkce však platí metody s nerovnoměrně rozmístěnými body, jako např Gaussova kvadratura a Clenshaw – Curtisova kvadratura jsou obecně mnohem přesnější; Clenshaw – Curtisovu kvadraturu lze chápat jako změnu proměnných k vyjádření libovolných integrálů z hlediska periodických integrálů, kdy lze lichoběžníkové pravidlo použít přesně.

Viz také

• Gaussova kvadratura
• Newton – Cotesovy vzorce
• Obdélníková metoda
• Rombergova metoda
• Simpsonovo pravidlo
• Volterraova integrální rovnice # Numerické řešení pomocí lichoběžníkového pravidla

Poznámky

Reference

externí odkazy

• Trapézový vzorec. I.P. Mysovskikh, Encyclopedia of Mathematics, vyd. M. Hazewinkel
• Poznámky ke konvergenci kvadratury lichoběžníkového pravidla
• Implementace lichoběžníkové kvadratury poskytované Boost.Math