Zobrazení zdroje stránky Lichoběžníková metoda

[[Soubor:Trapezoidal rule illustration.svg|vpravo|náhled|Funkce ''f''(''x'') (modře) je aproximována lineární funkcí (červeně).]]
'''Lichoběžníková metoda''' je technika používaná v [[Matematika|matematice]] pro [[Numerická matematika|přibližný numerický]] výpočet [[Integrál|určitého integrálu]]

:<math>\int_a^b f(x) \, dx</math>.

Jejím principem je [[aproximace]] plochy pod grafem funkce <math>f(x)</math> [[lichoběžník]]em a použitím jeho plochy jako přibližné hodnoty určitého integrálu funkce <math>f(x)</math> na intervalu <math>\langle a,b\rangle </math>:

:<math>\int_{a}^{b} f(x) \, dx \approx (b-a) \cdot \tfrac{f(a)+f(b)}{2}</math>.

Lichoběžníkovou metodu můžeme považovat za výsledek získaný průměrováním [[Riemannův součet|levého]] a [[Riemannův součet|pravého]] [[Riemannův součet|Riemannova součtu]] a někdy se lichoběžníková metoda takto definuje. Pro získání přesnějšího výsledku se obvykle integrační interval [[Dělení intervalu|rozděluje]] na podintervaly, pro každý se spočítá plocha lichoběžníka a výsledky se sečtou. V praxi se „integrováním lichoběžníkovou metodou“ zpravidla myslí tato „zřetězená“ (nebo „kompozitní“) lichoběžníková metoda. Jestliže <math>(x_k)</math> je dělení intervalu <math>\langle a,b\rangle </math> takové, že <math>a=x_0 < x_1 < \cdots < x_{N-1} < x_N = b</math> a <math>\Delta x_k</math> je délka <math>k</math>-tého podintervalu (tj. <math>\Delta x_k = x_k - x_{k-1}</math>), pak
:<math>\int_a^b f(x) \, dx \approx \sum_{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)\right)</math>.

[[Soubor:Integration num trapezes notation.svg|náhled|Ilustrace „zřetězené lichoběžníkové metody“ použité na nepravidelně rozděleném intervalu <math>\langle a,b\rangle </math>.]]

Pro jemnější dělení intervalu bude aproximace přesnější. Často se používá pravidelné dělení, které umožňuje vzorec pro výpočet dále zjednodušit.

Protože se jedná o pouze o aproximaci hodnoty určitého integrálu, je důležité, že na základě vlastností integrované funkce lze určit maximální chybu vypočítané hodnoty.

== Historie ==
V roce 2016 vyšel článek, který uvádí, že lichoběžníkovou metodu používali již před rokem 50 před naším letopočtem [[Babylón|Babyloňané]] pro výpočet polohy planety [[Jupiter (planeta)|Jupiter]] na [[Ekliptika|ekliptice]] integrováním její rychlosti.<ref>{{Citace periodika
 | příjmení = Ossendrijver
 | jméno = Mathieu
 | datum = 2016-01-29
 | titul = Ancient Babylonian astronomers calculated Jupiter's position from the area under a time-velocity graph
 | periodikum = Science
 | doi = 10.1126/science.aad8085
 | pmid=26823423
 | ročník = 351
 | číslo = 6272
 | strany = 482–484
 | url = http://science.sciencemag.org/content/351/6272/482.full
 | ref = harv
}}</ref>

== Numerická implementace ==

=== Nerovnoměrné dělení intervalu ===
Je-li dělení intervalu nerovnoměrné, můžeme použít vzorec

:<math> \int_{a}^{b} f(x)\, dx \approx \sum_{k=1}^N \frac{f(x_{k-1}) + f(x_k)}{2} \Delta x_k</math>

=== Rovnoměrné dělení ===
Je-li integrační interval rozdělený na <math>N</math> stejně velkých podintervalů, je možné vzorec pro výpočet zjednodušit. Pokud
:<math>\Delta x_k = \Delta x = \frac{b-a}{N},</math>
dostaneme vzorec
:<math>\int_{a}^{b} f(x)\, dx \approx \frac{\Delta x}{2} \sum_{k=1}^{N} \left( f(x_{k-1}) + f(x_{k}) \right)</math>
::<math>{}= \frac{\Delta x}{2} ( f(x_0) + 2f(x_1) + 2f(x_2) + 2f(x_3) + \dotsb + 2f(x_{N-1}) + f(x_N) )</math>
::<math>{}= \frac{\Delta x}{2} \left( f(x_0) +  f(x_N) +2\sum_{k=1}^{N-1} f(x_k) \right) </math>
::<math>{}= \Delta x \left( \sum_{k=1}^{N-1} f(x_k) + \frac{f(x_N) + f(x_0) }{2}  \right) .</math>

== Analýza chyb ==
[[Soubor:Trapezium2.gif|vpravo|náhled|Animace ukazující, jak se přesnost výsledku výpočtu integrálu lichoběžníkovou metodou zlepšuje při zjemňování dělení intervalu pro <math>a=2</math> a <math>b=8</math>.]]
Chyba kompozitní lichoběžníkové metody je rozdíl mezi skutečnou hodnotou integrálu a numerickým výsledkem:

:<math> \text{chyba} = \int_a^b f(x)\,dx - \frac{b-a}{N} \left[ {f(a) + f(b) \over 2} + \sum_{k=1}^{N-1} f \left( a+k \frac{b-a}{N} \right) \right]</math>

Existuje číslo ''ξ'' mezi ''a'' a ''b'' takové, že{{Sfn|Atkinson|1989|loc=equation (5.1.7)}}

:<math> \text{chyba} = -\frac{(b-a)^3}{12N^2} f''(\xi)</math>

To znamená, že pokud je integrand [[konvexní funkce]] (a tedy má kladnou druhou derivaci), pak lichoběžníková metoda přeceňuje skutečnou hodnotu (chyba je záporná). To je dobře vidět na kresbě: lichoběžníky pokrývají celou plochu pod křivkou a přesahují ji. Naopak u [[konkávní funkce]] dává výpočet menší hodnotu, protože se nepočítá celá plocha pod křivkou. Pokud integrační interval obsahuje [[inflexní bod]], je těžší chybu identifikovat.

Asymptotický odhad chyby pro ''N'' → ∞ je
:<math> \text{chyba} = -\frac{(b-a)^2}{12N^2} \big[ f'(b)-f'(a) \big] + O(N^{-3}). </math>
Další členy tohoto odhadu chyby jsou dané Eulerovým–Maclaurinovým sumačním vzorcem.

Pro analýzu chyb lze použít několika technik, mezi něž patří:{{Sfn|Weideman|2002|loc=p. 23, section 2}}
# [[Fourierova řada]]
# [[Residuový počet]]
# [[Eulerův–Maclaurinův sumační vzorec]]:{{Sfn|Atkinson|1989|loc=equation (5.1.9)}}{{Sfn|Atkinson|1989|s=285}}
# [[Polynomiální interpolace]]:{{Sfn|Faires|2011|s=194}}

Udává se, že rychlost konvergence lichoběžníkové metody lze používat jako definici třídy hladkosti funkcí.{{Sfn|Rahman|Schmeisser|1990}}

=== Důkaz ===
Předpokládejme, že <math>h=\frac{b-a}{N}</math> a <math>a_k=a+(k-1)h</math>.

Nechť <math> g_k(t)=\frac{1}{2}t[f(a_k)+f(a_k+t)]-\int_{a_k}^{a_k+t}f(x)dx</math> je funkce taková, že <math> |g_k(h)| </math> je chyba lichoběžníkové metody na jednom z intervalů, <math> \langle a_k, a_k+h\rangle</math>. Pak

<math> {dg_k \over dt}={1 \over 2}[f(a_k)+f(a_k+t)]+{1\over2}t\cdot f'(a_k+t)-f(a_k+t),</math>

a

<math> {d^2g_k \over dt^2}={1\over 2}t\cdot f''(a_k+t).</math>

Nyní předpokládejme, že <math> \left\vert f''(x) \right\vert \leq f''(\xi),</math> což platí, pokud je <math>f</math> dostatečně hladká. Odtud dostáváme

<math> \left\vert f''(a_k+t) \right\vert \leq f''(\xi)</math>

což je ekvivalentní s
<math> -f''(\xi) \leq f''(a_k+t) \leq f''(\xi)</math> nebo <math> -\frac{f''(\xi)t}{2} \leq g_k''(t) \leq \frac{f''(\xi)t}{2}.</math>

Protože <math> g_k'(0)=0</math> a <math> g_k(0)=0</math>,

<math> \int_0^tg_k''(x)dx=g_k'(t)</math> a <math> \int_0^tg_k'(x)dx=g_k(t).</math>

Při použití těchto výsledků dostáváme

<math> -\frac{f''(\xi)t^2}{4} \leq g_k'(t) \leq \frac{f''(\xi)t^2}{4}</math>

a

<math> -\frac{f''(\xi)t^3}{12} \leq g_k(t) \leq \frac{f''(\xi)t^3}{12}</math>

Pokud položíme <math>t=h</math>, dostaneme

<math> -\frac{f''(\xi)h^3}{12} \leq g_k(h) \leq \frac{f''(\xi)h^3}{12}.</math>

Sečtením všech částečných chyb dostáváme

<math> \sum_{k=1}^{N}g_k(h)=\frac{b-a}{N} \left[ {f(a) + f(b) \over 2} + \sum_{k=1}^{N-1} f \left( a+k \frac{b-a}{N} \right) \right]-\int_a^bf(x)dx.</math>

přičemž platí

<math> - \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}</math>

a

<math> \sum_{k=1}^N \frac{f''(\xi)h^3}{12}=\frac{f''(\xi)h^3N}{12},</math>

takže

<math> -\frac{f''(\xi)h^3N}{12} \leq \frac{b-a}{N} \left[ {f(a) + f(b) \over 2} + \sum_{k=1}^{N-1} f \left( a+k \frac{b-a}{N} \right) \right]-\int_a^bf(x)dx \leq \frac{f''(\xi)h^3N}{12}.</math>

Celková chyba je tedy omezena výrazem

<math> \text{chyba}=\int_a^bf(x)dx - \frac{b-a}{N} \left[ {f(a) + f(b) \over 2} + \sum_{k=1}^{N-1} f \left( a+k \frac{b-a}{N} \right) \right] = \frac{f''(\xi)h^3N}{12}=\frac{f''(\xi)(b-a)^3}{12N^2}.</math>

=== Periodické funkce ===
Pro periodické funkce lichoběžníková metoda konverguje velmi rychle. Je to jednoduchý důsledek Eulerova–Maclaurinova sumačního vzorce, který říká, že pokud funkce <math>f</math> je <math>p</math>-krát spojitě derivovatelná s periodou <math>T</math>, pak
:<math>\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,
</math>

kde <math>h:=T/N</math> a <math>\tilde{B}_{p}</math> je periodické rozšíření <math>p</math>-tého Bernoulliho polynomu.<ref>{{Citace monografie
 | titul = Numerical Analysis
 | svazek = 181
 | edice = Graduate Texts in Mathematics
 | jméno = Rainer
 | příjmení = Kress
 | rok = 1998
 | vydavatel = Springer-Verlag
 | ref = harv
}}</ref> U periodických funkcí se derivace v koncových bodech vyruší a jak je patrné ze vzorce, chyba je řádu <math>O(h^p)</math>.

=== Funkce s jedním vrcholem ===
Podobný efekt jako u periodických funkcí se projevuje u funkcí s jedním vrcholem, jako je například [[Gaussova funkce]], [[Exponenciálně modifikované normální rozdělení|exponenciálně modifikovaná Gaussova funkce]] nebo další funkce, které mají v integračních mezích derivace, které lze zanedbat.<ref>{{Citace periodika
 | příjmení = Goodwin
 | jméno = E. T.
 | rok = 1949
 | titul = The evaluation of integrals of the form
 | periodikum = Mathematical Proceedings of the Cambridge Philosophical Society
 | jazyk = en
 | ročník = 45
 | číslo = 2
 | strany = 241–245
 | doi = 10.1017/S0305004100024786
 | issn = 1469-8064
 | ref = harv
}}</ref> Pro výpočet integrálu gaussovské funkce lichoběžníkovou metodou s 1% přesností stačí použít pouze čtyři body.<ref name=":0">{{Citace periodika
 | příjmení = Kalambet
 | jméno = Yuri
 | příjmení2 = Kozmin
 | jméno2 = Yuri
 | příjmení3 = Samokhin
 | jméno3 = Andrey
 | rok = 2018
 | titul = Comparison of integration rules in the case of very narrow chromatographic peaks
 | periodikum = Chemometrics and Intelligent Laboratory Systems
 | ročník = 179
 | strany = 22–30
 | doi = 10.1016/j.chemolab.2018.06.001
 | issn = 0169-7439
 | ref = harv
}}</ref> [[Simpsonovo pravidlo]] vyžaduje pro dosažení stejné přesnosti 1,8krát více bodů.<ref name=":0" />{{Sfn|Weideman|2002}}

Přes určité úsilí rozšířit Eulerův–Maclaurinův sumační vzorec na více dimenzí,<ref>{{Citace elektronické monografie
 | url = https://math.stackexchange.com/questions/30384/euler-maclaurin-summation-formula-for-multiple-sums
 | vydavatel = math.stackexchange.com
 | titul = Euler-Maclaurin Summation Formula for Multiple Sums
}}</ref> k přímočařejšímu důkazu velmi rychlé konvergence lichoběžníkové metody v prostorech s mnoha rozměry stačí omezit problém na konvergenci Fourierovy řady. Tímto způsobem lze ukázat, že pokud je <math>f</math> periodická na <math>n</math>-rozměrném prostoru s <math>p</math> spojitými derivacemi, bude rychlost konvergence <math>O(h^{p/d})</math>. Při velmi vysokém počtu dimenzí je integrace Monte-Carlo pravděpodobně lepší volbou, ale pro dvou nebo trojrozměrný případ je efektivní rovnoměrné vzorkování. Toho se využívá při výpočtech ve fyzice pevné fáze, kde rovnoměrné vzorkování přes primitivní buňky v převrácená mřížce je známé jako ''Monkhorstova-Packova integrace''.<ref>{{Citace elektronické monografie
 | url = https://bandgap.io/blog/numerical_integration_bz/
 | jméno = Nick
 | příjmení = Thompson
 | vydavatel = bandgap.io
 | datum přístupu = 2017-12-19
 | titul = Numerical Integration over Brillouin Zones
 | ref = harv
 }}{{Nedostupný zdroj}}</ref>

=== „Drsné“ funkce ===
U funkcí, které nemají spojitou druhou derivaci, nelze použít výše uvedený odhad chyby. Pro málo hladké funkce je však možné odvodit jiná omezení chyby, která však typicky svědčí, že při zvyšování počtu bodů <math>N</math>, v nichž se počítá hodnota integrované funkce je konvergence pomalejší než výše uvedené <math>O(N^{-2})</math>. Je zajímavé, že v tomto případě má lichoběžníková metoda často ostřejší meze při stejném počtu vyhodnocování funkce než [[Simpsonovo pravidlo]].{{Sfn|Cruz-Uribe|Neugebauer|2002}}

== Použitelnost a alternativy ==
Lichoběžníková metoda patří do skupiny metod pro [[Numerická integrace|numerickou integraci]] nazývaných [[Newtonovy–Cotesovy vzorce]], z nichž [[Riemannův součet]] se podobá lichoběžníkovému pravidlu. Jiným členem této skupiny je [[Simpsonovo pravidlo]], které pro funkce mající dvě spojité derivace konverguje obecně rychleji než lichoběžníková metoda, existují však výjimky; u některých tříd méně hladkých funkcí (splňujících slabší podmínky hladkosti) lichoběžníková metoda konverguje obecně rychleji než Simpsonova metoda.{{Sfn|Cruz-Uribe|Neugebauer|2002}}

Lichoběžníková metoda je obvykle velmi přesná při integraci [[Periodická funkce|periodických funkcí]] na intervalu shodném s jejich periodou, který lze [[#Periodické funkce|analyzovat různými způsoby]].{{Sfn|Rahman|Schmeisser|1990}}{{Sfn|Weideman|2002}} Podobný efekt existuje u funkcí s jedním vrcholem.<ref name=":0" />{{Sfn|Weideman|2002}}

Metody s nestejně vzdálenými body, jako je [[Gaussovo kvadraturní pravidlo]] a [[Clenshawova–Curtisova kvadratura]], jsou však obecně mnohem přesnější pro neperiodické funkce; Clenshawovu–Curtisovu kvadraturu lze považovat za substituci, kterou lze vyjádřit libovolný integrál pomocí periodických integrálů, pro které je lichoběžníková metoda přesnější.

== Odkazy ==

=== Poznámky ===
<references/>

=== Reference ===
{{Překlad|en|Trapezoidal rule|999842103}}

{{Refbegin}}
* {{Citace monografie
 | příjmení = Atkinson
 | jméno = Kendall E.
 | rok = 1989
 | titul = An Introduction to Numerical Analysis
 | vydání = 2
 | vydavatel = John Wiley & Sons
 | místo = New York
 | isbn = 978-0-471-50023-0
 | ref = harv
}}
* {{Citace periodika
 | příjmení = Rahman
 | jméno = Qazi I.
 | příjmení2 = Schmeisser
 | jméno2 = Gerhard
 | datum = prosinec 1990
 | titul = Characterization of the speed of convergence of the trapezoidal rule
 | periodikum = Numerische Mathematik
 | issn = 0945-3245
 | doi = 10.1007/BF01386402
 | ročník = 57
 | číslo = 1
 | strany = 123–138
 | ref = harv
}}
* {{Citace monografie
 | příjmení = Burden
 | jméno = Richard L.
 | příjmení2 = Faires
 | jméno2 = J. Douglas
 | rok = 2000
 | titul = Numerical Analysis
 | vydání = 7
 | vydavatel = Brooks/Cole
 | isbn = 978-0-534-38216-2
 | url-access=registration
 | url = https://archive.org/details/numericalanalysi0000burd
 | ref = harv
}}
* {{Citace periodika
 | příjmení = Weideman
 | jméno = J. A. C.
 | datum = leden 2002
 | titul = Numerical Integration of Periodic Functions: A Few Examples
 | periodikum = The American Mathematical Monthly
 | doi = 10.2307/2695765
 | jstor = 2695765
 | ročník = 109
 | číslo = 1
 | strany = 21–36
 | ref = harv
}}
* {{Citace periodika
 | příjmení = Cruz-Uribe
 | jméno = D.
 | příjmení2 = Neugebauer
 | jméno2 = C. J.
 | rok = 2002
 | titul = Sharp Error Bounds for the Trapezoidal Rule and Simpson's Rule
 | periodikum = Journal of Inequalities in Pure and Applied Mathematics
 | ročník = 3
 | číslo = 4
 | url = http://www.emis.de/journals/JIPAM/images/031_02_JIPAM/031_02.pdf
 | ref = harv
}}
{{Refend}}

=== Související články ===
* [[Gaussovo kvadraturní pravidlo]]
* [[Newtonovy–Cotesovy vzorce]]
* [[Riemannův součet]]
* [[Rombergova metoda]]
* [[Simpsonovo pravidlo]]
* [[Volterrova integrální rovnice#Numerické řešení pomocí lichoběžníkové metody]]

=== Externí odkazy ===
* {{Commonscat}}
* {{Wikiknihy|kniha=en:A-level Mathematics/OCR/C2/Integration#Trapezium_Rule}}
* [http://www.encyclopediaofmath.org/index.php?titul=Trapezium_formula&oldid=12696 Trapezium formula. I.P. Mysovskikh] – ''Lichoběžníková metoda'' v ''Encyclopedia of Mathematics'', ed. M. Hazewinkel
* [http://dedekind.mit.edu/~stevenj/trapezoidal.pdf Notes on the convergence of trapezoidal-rule quadrature] {{Wayback|url=http://dedekind.mit.edu/~stevenj/trapezoidal.pdf |date=20210209003347 }} – poznámky ke konvergenci výpočtů integrálů lichoběžníkovou metodou
* [http://www.boost.org/doc/libs/1_66_0/libs/math/doc/html/math_toolkit/trapezoidal.html An implementation of trapezoidal quadrature provided by Boost.Math] – implementace kvadratury lichoběžníkovou metod z Boost.Math
{{Autoritní data}}

{{Portály|Matematika}}

[[Kategorie:Numerická integrace]]