Adaptacyjna kwadratura

Adaptacyjna kwadratura to numeryczna metoda całkowania $,$ w której całka funkcji jest aproksymowana adaptacyjnie podprzedziałach regionu integracji Ogólnie rzecz biorąc, algorytmy adaptacyjne są tak samo wydajne i skuteczne jak tradycyjne algorytmy dla „dobrze zachowujących się” całek, ale są również skuteczne w przypadku „źle zachowujących się” całek, dla których tradycyjne algorytmy mogą zawieść.

Schemat ogólny

Adaptacyjna kwadratura jest zgodna z ogólnym schematem

   1. całkowanie   procedury  ( fa , za , b , τ ) 2. ${\ Displaystyle Q \ w przybliżeniu \ int _ {a} ^ {b} f (x) \, \ operatorname {d} x}$ 3. ${\ Displaystyle \ varepsilon \ około \ lewo | Q- \ int _ {a} ^ {b} f (x) \, \ operatorname {d} x \ prawo |} 4. jeśli ε$ >  τ  to  5.  m  =  ( a + b) / 2 6. Q = integruj(f, a, m, τ/2) + integruj(f, m, b, τ/2) 7.  endif  8.  return  Q 

$a, b]} ($ również przybliżenie do całki po $Displaystyle$ [ za $[$ jako oszacowanie błędu $wiersz$ 3). Jeśli oszacowany błąd jest większy niż wymagana tolerancja $wiersz$ 4), przedział jest dzielony (wiersz 5) i kwadratura jest stosowana do obu połówek osobno (wiersz 6). Zwracane jest wstępne oszacowanie lub suma obliczonych rekurencyjnie połówek (wiersz 7).

Ważnymi składnikami jest sama reguła kwadraturowa

$\ Displaystyle Q \ w przybliżeniu \ int _ {a} ^ {b} f (x) \, \ operatorname {d} x,}$

estymator błędów

$\ Displaystyle \ varepsilon \ około \ lewo | Q- \ int _ {a} ^ {b} f (x) \ \ operatorname {d} x \ prawo |,}$

oraz logika decydująca, który przedział podzielić i kiedy zakończyć.

Istnieje kilka wariantów tego schematu. Najczęstsze zostaną omówione później.

Podstawowe zasady

Reguły kwadraturowe mają na ogół postać

${\ Displaystyle Q_ {n} \ quad = \ quad \ suma _ {i = 0} ^ {n} w_ { i}f(x_{i})\quad \około \quad \int _{a}^{b}f(x)\,\mathrm {d} x}$

$.$ węzły $są$ wagi obliczone

W najprostszym przypadku stosuje się wzory Newtona – Cotesa o parzystym stopniu, w których węzły są równomiernie rozmieszczone w przedziale: ${\ displaystyle x_ {i}}$

${\ Displaystyle x_ {i} = a + {\ Frac {ba} {n}} i.}$

Kiedy takie reguły są używane, punkty, w których oceniono, można ponownie wykorzystać po rekurencji: ${\ displaystyle f (x)}$

Podobna strategia jest stosowana w przypadku kwadratury Clenshawa – Curtisa , gdzie węzły są wybierane jako

${\ Displaystyle x_ {i} = \ cos \ lewo ({\ Frac {2i} {n}} \ pi \ po prawej).}$

Lub, gdy używana jest kwadratura Fejéra ,

${\ Displaystyle x_ {i} = \ cos \ lewo ({\ Frac {2 (i + 0,5)} {n + 1}} \ pi \ po prawej).}$

Można również zastosować inne reguły kwadraturowe, takie jak kwadratura Gaussa lub kwadratura Gaussa-Kronroda .

Algorytm może zdecydować się na użycie różnych metod kwadraturowych na różnych podprzedziałach, na przykład przy użyciu metody wysokiego rzędu tylko wtedy, gdy całka jest gładka.

Szacowanie błędów

Niektóre algorytmy kwadraturowe generują sekwencję wyników, która powinna zbliżyć się do prawidłowej wartości. W przeciwnym razie można użyć „reguły zerowej”, która ma postać powyższej reguły kwadraturowej, ale której wartość wynosiłaby zero dla prostej całki (na przykład, gdyby całka była wielomianem odpowiedniego stopnia).

Widzieć:

• Ekstrapolacja Richardsona (patrz także metoda Romberga )
• Zasady zerowe
• Algorytm Epsilon

Logika podziału

„Lokalna” adaptacyjna kwadratura powoduje, że dopuszczalny błąd dla danego przedziału jest proporcjonalny do długości tego przedziału. To kryterium może być trudne do spełnienia, jeśli całki zachowują się źle tylko w kilku punktach, na przykład z kilkoma nieciągłościami krokowymi. Alternatywnie, można wymagać jedynie, aby suma błędów w każdym z podprzedziałów była mniejsza niż wymaganie użytkownika. Byłaby to „globalna” adaptacyjna kwadratura. Globalna adaptacyjna kwadratura może być bardziej wydajna (przy użyciu mniejszej liczby ocen całki), ale generalnie jest bardziej złożona do zaprogramowania i może wymagać więcej przestrzeni roboczej do rejestrowania informacji o bieżącym zestawie interwałów.

Zobacz też

• Adaptacyjne różniczkowanie numeryczne
• Adaptacyjny rozmiar kroku w ODE
• Metoda Adaptive Simpsona jako przykład adaptacyjnej kwadratury
• QUADPACK , biblioteka FORTRAN, która wykorzystuje globalną adaptacyjną kwadraturę

Notatki

•     McKeeman, William (grudzień 1962). Gotlieb, Kalwin (red.). „Algorytm 145: Adaptacyjne całkowanie numeryczne według reguły Simpsona”. Komunikaty ACM (okresowe). Nowy Jork : ACM . 5 (12): 604–605. doi : 10.1145/355580.369102 . eISSN 1557-7317 . ISSN 0001-0782 . OCLC 1011805770 .
• Johna R. Rice'a. Metalgorytm dla adaptacyjnej kwadratury. Dziennik ACM 22(1) s. 61-82 (styczeń 1975).
•   Prasa, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), „Sekcja 4.7. Adaptacyjna kwadratura” , Przepisy numeryczne: sztuka obliczeń naukowych (wyd. 3), Nowy Jork: Cambridge University Press, ISBN 978-0-521-88068-8