Adaptivní kvadratura - Adaptive quadrature

Tento článek obsahuje a seznam doporučení, související čtení nebo externí odkazy, ale jeho zdroje zůstávají nejasné, protože mu chybí vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Srpna 2019) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Adaptivní kvadratura je numerická integrace metoda, ve které integrální a funkce ${displaystyle f (x)}$ je přibližný použití pravidel statické kvadratury na adaptivně rafinované podintervaly oblasti integrace. Obecně jsou adaptivní algoritmy stejně účinné a efektivní jako tradiční algoritmy pro „dobře vychované“ integrandy, ale jsou účinné také pro „špatně chované“ integrandy, u kterých tradiční algoritmy mohou selhat.

Obecné schéma

Adaptivní kvadratura se řídí obecným schématem

1. postup integrovat (f, a, b, ${displaystyle au}$ )2.    ${displaystyle Q Approx int _ {a} ^ {b} f (x), {mbox {d}} x}$
3.    ${displaystyle varepsilon cca vlevo | Q-int _ {a} ^ {b} f (x), {mbox {d}} xight |}$4.    -li ${displaystyle varepsilon> au}$ pak5. m = (a + b) / 26. Q = integrovat (f, a, m, ${displaystyle au}$/ 2) + integrovat (f, m, b, ${displaystyle au}$/2)7.    endif8.    vrátit se Q

Aproximace ${displaystyle Q}$ k integrálu ${displaystyle f (x)}$ v daném intervalu ${displaystyle [a, b]}$ je vypočítán (řádek 2), stejně jako odhad chyby ${displaystyle varepsilon}$ (řádek 3). Pokud je odhadovaná chyba větší než požadovaná tolerance ${displaystyle au}$(řádek 4), interval je rozdělen (řádek 5) a kvadratura se aplikuje na obě poloviny samostatně (řádek 6). Vrátí se buď počáteční odhad, nebo součet rekurzivně vypočítaných polovin (řádek 7).

Důležité komponenty jsou kvadratura vládnout sám

${displaystyle Q Approx int _ {a} ^ {b} f (x), {mbox {d}} x,}$

the odhad chyb

${displaystyle varepsilon cca vlevo | Q-int _ {a} ^ {b} f (x), {mbox {d}} xight |,}$

a logiku pro rozhodování, který interval rozdělit a kdy ukončit.

Existuje několik variant tohoto schématu. O nejběžnějších bude pojednáno později.

Základní pravidla

Kvadraturní pravidla mají obecně formu

${displaystyle Q_ {n} quad = quad sum _ {i = 0} ^ {n} w_ {i} f (x_ {i}) quad cca quad int _ {a} ^ {b} f (x), {mbox {d}} x}$

kde uzly ${displaystyle x_ {i}}$ a váhy ${displaystyle w_ {i}}$ jsou obecně předpočítány.

V nejjednodušším případě Newton – Cotesovy vzorce sudého stupně, kde se používají uzly ${displaystyle x_ {i}}$ jsou rovnoměrně rozmístěny v intervalu:

${displaystyle x_ {i} = a + {frac {i} {n}} (b-a)}$.

Pokud se tato pravidla použijí, body, ve kterých ${displaystyle f (x)}$ byl vyhodnocen lze znovu použít po rekurzi:

Podobná strategie se používá u Clenshaw – Curtisova kvadratura, kde jsou uzly vybrány jako

${displaystyle x_ {i} = cos left ({frac {2i} {n}} pi ight)}$.

Nebo kdy Fejérova kvadratura se používá,

${displaystyle x_ {i} = cos left ({frac {2 (i + 0,5)} {n + 1}} pi ight)}$.

Další pravidla kvadratury, jako např Gaussova kvadratura nebo Gauss-Kronrodova kvadratura, lze také použít.

Algoritmus se může rozhodnout použít různé metody kvadratury na různých podintervalech, například pomocí metody vyššího řádu pouze tam, kde je integrand hladký.

Odhad chyb

Některé kvadraturní algoritmy generují posloupnost výsledků, které by se měly blížit správné hodnotě. Jinak lze použít „nulové pravidlo“, které má formu výše uvedeného pravidla kvadratury, ale jehož hodnota by byla nulová pro jednoduchý integrand (například pokud by integrand byl polynomem příslušného stupně).

Vidět:

• Richardsonova extrapolace (viz také Rombergova metoda )
• Nulová pravidla
• Algoritmus Epsilon

Logika dělení

Díky „místní“ adaptivní kvadratuře je přijatelná chyba pro daný interval úměrná délce daného intervalu. Toto kritérium může být obtížné splnit, pokud se celá čísla špatně chovají jen v několika bodech, například s několikastupňovými diskontinuitami. Alternativně by bylo možné požadovat pouze to, aby součet chyb na každém z podintervalů byl menší než požadavek uživatele. To by byla „globální“ adaptivní kvadratura. Globální adaptivní kvadratura může být efektivnější (s použitím méně vyhodnocení integrand), ale je obecně složitější programovat a může vyžadovat více pracovního prostoru pro záznam informací o aktuální sadě intervalů.

Viz také

• Adaptivní numerická diferenciace
• Adaptivní velikost kroku v ODE
• Adaptivní Simpsonova metoda například příklad adaptivní kvadratury
• QUADPACK, knihovna FORTRAN, která využívá globální adaptivní kvadraturu

Poznámky

Reference

• McKeeman, William (Prosinec 1962). Gotlieb, Calvin (vyd.). „Algorithm 145: Adaptive numerical integration by Simpson's rule“. Komunikace ACM (Časopis). New York: ACM. 5 (12): 604–605. doi:10.1145/355580.369102. eISSN  1557-7317. ISSN  0001-0782. OCLC  1011805770.
• John R. Rice. Metalgoritmus pro adaptivní kvadraturu. Journal of the ACM 22 (1) pp 61-82 (leden 1975).
• Stiskněte, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), „Oddíl 4.7. Adaptivní kvadratura“, Numerické recepty: Umění vědecké práce na počítači (3. vyd.), New York: Cambridge University Press, ISBN  978-0-521-88068-8