Wybór metody dla kwadratury numerycznej

Istnieje kilka rodzin metod kwadratur numerycznych. Jeśli mam określoną klasę integrandów, jak wybrać idealną metodę?

Jakie pytania należy zadać zarówno na temat całki (np. Czy jest gładka? Czy ma osobliwości?), Jak i problemu obliczeniowego (np. Tolerancja błędów, budżet obliczeniowy)?

W jaki sposób odpowiedzi na te pytania wykluczają lub promują różne rodziny metod? Dla uproszczenia rozważmy tylko całki jedno- lub niskowymiarowe.

Na przykład artykuł Wikipedii na temat QUADPACK stwierdza, że dość ogólna QAGSprocedura „ wykorzystuje globalną kwadraturę adaptacyjną opartą na 21-punktowej kwadraturze Gaussa-Kronroda w każdej podsekcji, z przyspieszeniem przez algorytm epsilon Petera Wynna ”

Jak podjęto tę decyzję? Jak podejmować podobne decyzje, skoro wiadomo więcej?

quadrature

— MRocklin
źródło

Prawdopodobnie potrzebne są bardziej szczegółowe informacje, aby odpowiedzieć na to poprawnie. Nie ma jednego uniwersalnego kryterium dla wszystkich, kwadratura gaussowska często działa dobrze w przypadku bardzo gładkich problemów, podczas gdy inne kwadratury mogą być stosowane w obecności łagodnych osobliwości. Ale jeśli jesteś okresowy, prosty trapezoid może go przeciąć.

— Reid.Atcheson

@ Reid.Atcheson, myślę, że odpowiadasz teraz na pytanie. Nie pytam, jaka jest najlepsza metoda, pytam, jakie pytania byś zadał i jakie odpowiedzi ci powiedziały? Jak ogólnie można podejść do tego rodzaju problemów?

— MRocklin

Przede wszystkim musisz zadać sobie pytanie, czy potrzebujesz wszechstronnej procedury kwadraturowej, która powinna przyjmować całkę jako czarną skrzynkę. Jeśli tak, nie możesz przejść na kwadraturę adaptacyjną, w której masz nadzieję, że adaptacja złapie „trudne” miejsca w integrandzie. I to jest jeden z powodów, dla których Piessens i in. wybrał regułę Gaussa-Kronroda (ten typ reguły pozwala obliczyć przybliżenie całki i oszacować błąd przybliżenia przy użyciu tych samych ocen funkcji) o skromnym porządku zastosowanym w schemacie adaptacyjnym (z podziałem przedziału z najwyższy błąd) aż do osiągnięcia wymaganych tolerancji. Algorytm Wynn-epsilon pozwala zapewnić przyspieszenie zbieżności i zazwyczaj pomaga w przypadkach, w których występują osobliwości punktu końcowego.

Ale jeśli znasz „formę” lub „typ” integrandu, możesz dostosować metodę do potrzeb, aby koszt obliczeniowy był ograniczony z punktu widzenia wymaganej dokładności. Więc na co musisz spojrzeć:

Integrand:

Gładkość: czy można ją aproksymować (dobrze) wielomianem z ortogonalnej rodziny wielomianów (jeśli tak, kwadratura Gaussa da sobie radę)
Osobliwości: czy całkę można podzielić na całki z osobliwościami tylko punktu końcowego (jeśli tak, to reguła IMT lub podwójna kwadratura wykładnicza będzie dobra na każdym podokresie)
Koszt obliczeniowy oceny?
Czy można obliczyć całkę? Czy dostępne są tylko ograniczone dane punktowe?
Wysoce oscylacyjna całka: poszukaj metod typu Levina.

$|x-c|^{-\alpha}$ $c$ $\alpha$

Interwał całkowania: skończony, pół-nieskończony lub nieskończony. Czy w przypadku przedziałów częściowo nieskończonych lub nieskończonych można je zredukować do przedziału skończonego za pomocą transformacji zmiennej? Jeśli nie, wielomianów Laguerre'a lub Hermite'a można zastosować w podejściu do kwadratury Gaussa.

Nie mam odniesienia do prawdziwego schematu blokowego dla kwadratury w ogóle, ale książka QUADPACK (nie strony Netlib, ale prawdziwa książka) ma schemat blokowy do wyboru odpowiedniej procedury na podstawie całki, którą chcesz ocenić. Książka opisuje również wybory w algorytmach dokonane przez Piessensa i in. dla różnych procedur.

W przypadku całek niskowymiarowych zwykle stosuje się zagnieżdżoną jednowymiarową kwadraturę. W szczególnym przypadku całek dwuwymiarowych (kubatura) istnieją reguły integracji dla różnych przypadków domen integracji. R. Cools zebrał wiele zasad w swojej Encyklopedii wzorów kubaturowych i jest głównym autorem pakietu Cubpack . W przypadku całek wielowymiarowych zwykle stosuje się metody typu Monte Carlo. Jednak, aby uzyskać rozsądną dokładność, zwykle wymagana jest bardzo duża liczba ocen całki. W przypadku całek niskowymiarowych metody aproksymacyjne, takie jak kwadratura / kubatura / kwadratura zagnieżdżona, często przewyższają te metody stochastyczne.

Ogólne interesujące referencje:

Quadpack, Piessens, Robert; de Doncker-Kapenga, Elise; Überhuber, Christoph W .; Kahaner, David (1983). QUADPACK: Pakiet podprogramu do automatycznej integracji. Springer-Verlag. ISBN 978-3-540-12553-2
Metody integracji numerycznej: drugie wydanie, Ph. Davis i Ph. Rabinowitz, 2007, Dover Books on Mathematics, ISBN 978-0486453392

— GertVdE
źródło

Niezła odpowiedź. Dlaczego QUADPACK wybrałby w szczególności 21-punktową metodę Gaussa-Kronroda? Dlaczego magiczna liczba?

— MRocklin

@MRocklin: Wydaje mi się, że był to dobry kompromis między dokładnością a wydajnością: nie chcesz przesadzać z zasadą kwadratury (kosztowną), ale nie chcesz, aby była zbyt słaba (zbyt duże podziały w części adaptacyjnej ). Aby zakończyć: w procedurze QAG użytkownik musi określić regułę kwadratury; w QAGS (z ekstrapolacją) domyślnie jest reguła 21-punktowa, ale można to zmienić, używając procedury rozszerzonego wywoływania QAGSE.

— GertVdE

@GertVdE Rzeczywiście bardzo miła odpowiedź. Czy możesz rozwinąć stosowanie Clenshaw-Curtis do przechwytywania osobliwości w środkowych odstępach czasu lub podać odniesienia? Nie słyszałem o tym wcześniej i nie mogłem znaleźć żadnych szczegółów po szybkim googlowaniu. Dziękuję Ci!

— OscarB

@OscarB: przepraszam za duże opóźnienie, nie było dostępu do sieci (ah dobre życie). Zobacz książkę Quadpack §2.2.3.3 i dalsze; Branders, Piessens, „Rozszerzenie kwadratury Clenshawa-Curtisa”, 1975, J.Comp.Appl.Math., 1, 55-65; Piessens, Branders, „Ocena i zastosowanie niektórych zmodyfikowanych momentów”, 1973, BIT, 13, 443-450; Piessens, Branders, „Obliczanie całek oscylacyjnych”, 1975, J.Comp.Appl.Math., 1, 153-164. Jeśli poszukasz literatury „Robert Piessens” gdzieś między 1972 a 1980 rokiem, znajdziesz wiele interesujących artykułów.

— GertVdE