Kwadratura Gaussa-Legendre'a

W analizie numerycznej kwadratura Gaussa-Legendre'a jest formą kwadratury Gaussa służącą do aproksymacji całki oznaczonej funkcji . W przypadku całkowania po przedziale [−1, 1] reguła przyjmuje postać:

${\ Displaystyle \ int _ {- 1} ^ {1} f (x) \, dx \ w przybliżeniu \ suma _ { i=1}^{n}w_{i}f(x_{i})}$

Gdzie

• n to liczba użytych punktów próbkowania,
• w _i są wagami kwadraturowymi, oraz
• x _i są pierwiastkami n -tego wielomianu Legendre'a .

Ten wybór wag kwadraturowych w _i i węzłów kwadraturowych x _i jest unikalnym wyborem, który pozwala regule kwadraturowej na dokładne całkowanie wielomianów stopnia 2 n - 1 .

Opracowano wiele algorytmów do obliczania reguł kwadratury Gaussa – Legendre'a. Algorytm Goluba-Welscha przedstawiony w 1969 r. Zmniejsza obliczanie węzłów i wag do problemu wartości własnej, który jest rozwiązywany przez algorytm QR . Algorytm ten był popularny, ale istnieją znacznie bardziej wydajne algorytmy. Algorytmy oparte na metodzie Newtona-Raphsona są w stanie obliczyć reguły kwadraturowe dla znacznie większych rozmiarów problemów. W 2014 roku Ignace Bogaert przedstawił wyraźne asymptotyczne wzory dla wag i węzłów kwadraturowych Gaussa – Legendre'a, które są dokładne z dokładnością do epsilonu maszyny podwójnej precyzji dla dowolnego wyboru n ≥ 21. Pozwala to na obliczenie węzłów i wag dla wartości n przekraczających jeden bilion.

Historia

Carl Friedrich Gauss jako pierwszy wyprowadził regułę kwadratury Gaussa-Legendre'a, robiąc to za pomocą obliczeń z ułamkami ciągłymi w 1814 r. Obliczył węzły i wagi do 16 cyfr aż do rzędu n = 7 ręcznie. Carl Gustav Jacob Jacobi odkrył związek między regułą kwadraturową a ortogonalną rodziną wielomianów Legendre'a . Ponieważ nie ma formuły w postaci zamkniętej dla wag kwadraturowych i węzłów, przez wiele dziesięcioleci ludzie mogli używać ich tylko do ręcznego obliczania dla małych n , a obliczanie kwadratury musiało odbywać się poprzez odwoływanie się do tabel zawierających wagi i wartości węzłów. Do 1942 roku wartości te były znane tylko dla n = 16.

Definicja

Wykresy wielomianów Legendre'a (do n = 5)

_W , ( x - przypadku całkowania f przez $kwadraturę$ Gaussa powiązane wielomiany ortogonalne to Legendre'a , oznaczone przez Przy n -tym wielomianie znormalizowanym tak, że P _n (1) = 1 , i -ty węzeł Gaussa, x _i , jest i -tym pierwiastkiem P _n , a wagi podane są wzorem ( Abramowitz & Stegun 1972 , p. 887)

${\ Displaystyle w_ {i} = {\ Frac {2} {\ lewo (1-x_ {i} ^ {2} \ prawo) \ lewo [P'_ {n} (x_ {i}) \ prawo] ^ {2}}}.}$

Niektóre reguły kwadraturowe niskiego rzędu są zestawione poniżej w celu całkowania po ${\ Displaystyle [-1,1]}$ .

Liczba punktów, n	Punkty, x i		Wagi , wi
1	0		2
2	${\ Displaystyle \ pm {\ Frac {1} {\ sqrt {3}}}}$	±0,57735…	1
3	0		${\ Displaystyle {\ Frac {8} {9}}}$	0,888889…
	${\ Displaystyle \ pm {\ sqrt {\ Frac {3} {5}}}}$	±0,774597…	${\ Displaystyle {\ Frac {5} {9}}}$	0,555556…
4	${\ Displaystyle \ pm {\ sqrt {{\ Frac {3} {7}} - {\ Frac {2} {7}} {\ sqrt {\ Frac {6} {5} }}}}}$	±0,339981…	${\ Displaystyle {\ Frac {18 + {\ sqrt {30}}} {36}}}$	0,652145…
	${\ Displaystyle \ pm {\ sqrt {{\ Frac {3} {7}} + {\ Frac {2} {7}} {\ sqrt {\ Frac {6} {5} }}}}}$	±0,861136…	${\ Displaystyle {\ Frac {18- {\ sqrt {30}}} {36}}}$	0,347855…
5	0		${\ Displaystyle {\ Frac {128} {225}}}$	0,568889…
	${\ Displaystyle \ pm {\ Frac {1} {3}} {\ sqrt {5-2 {\ sqrt {\ Frac {10} {7}}}}}}$	±0,538469…	${\ Displaystyle {\ Frac {322 + 13 {\ sqrt {70}}} {900}}}$	0,478629…
	${\ Displaystyle \ pm {\ Frac {1} {3}} {\ sqrt {5 + 2 {\ sqrt {\ Frac {10} {7}}}}}}$	±0,90618…	$\ sqrt {70}}} {900}}}$	0,236927…

W przypadku całkowania po ogólnym przedziale rzeczywistym można zastosować zmianę przedziału $,$$,1]}$ w problem całkowania po $\ Displaystyle$ .

Algorytmy

Metody Newtona-Raphsona

Kilku badaczy opracowało algorytmy obliczania węzłów kwadraturowych Gaussa-Legendre'a i wag w oparciu o metodę Newtona-Raphsona do znajdowania pierwiastków funkcji. Stosowane są różne optymalizacje dla tego konkretnego problemu. Na przykład niektóre metody obliczają $},$$x_ {i}$ aby uniknąć problemów związanych z grupowaniem korzeni w pobliżu końce przedziału ${\ Displaystyle -1}$ i ${\ Displaystyle 1}$ . Niektóre metody wykorzystują wzory do przybliżenia ciężarów, a następnie wykorzystują kilka iteracji Newtona-Raphsona, aby obniżyć błąd przybliżenia poniżej precyzji maszyny.

Golub-Welsch

W 1969 roku Golub i Welsch opublikowali swoją metodę obliczania reguł kwadratury Gaussa, biorąc pod uwagę trzyczłonową relację powtarzalności, którą spełniają podstawowe wielomiany ortogonalne. Redukują problem obliczania węzłów kwadratury Gaussa do problemu znajdowania wartości własnych określonej symetrycznej macierzy tridiagonalnej . Algorytm QR służy do znalezienia wartości własnych tej macierzy. Korzystając z symetrycznej struktury tridiagonalnej, wartości własne można $3$${ \displaystyle {\mathcal {O}}(n^{3})}$ do oczekiwany czas dla ogólnego problemu z wartością własną.

Formuły asymptotyczne

Opracowano różne metody, które wykorzystują przybliżone wyrażenia w formie zamkniętej do obliczania węzłów. Jak wspomniano powyżej, w niektórych metodach wzory są używane jako przybliżenia węzłów, po czym wykonuje się kilka iteracji Newtona-Raphsona w celu udoskonalenia przybliżenia. W artykule z 2014 roku Ignace Bogaert wyprowadza asymptotyczne wzory dla węzłów, które są dokładne z dokładnością do maszyny dla ${\ displaystyle n \ geq 21}$ i dla wag, które są dokładne z dokładnością do maszyny dla ${\ displaystyle n \ geq 21} n\geq 30}$ . Ta metoda nie wymaga żadnych iteracji Newtona-Raphsona ani ocen funkcji Bessela, jak robią to inne metody. Jak pokazano w artykule, metoda była w stanie obliczyć węzły przy rozmiarze problemu jednego miliarda w 11 sekund. Ponieważ węzły w pobliżu punktów końcowych $w$ węzłów jest wystarczająca do zasadniczo każdego praktycznego zastosowania precyzyjny zmiennoprzecinkowy.

Wyższa precyzja

Johansson i Mezzarobba opisują strategię obliczania reguł kwadraturowych Gaussa-Legendre'a w arytmetyce o dowolnej precyzji , pozwalając zarówno na małe, jak $duże$ . Regułę porządku $do 1000$ cyfr można obliczyć w ciągu około jednej Ich metoda wykorzystuje iterację Newtona-Raphsona wraz z kilkoma różnymi technikami oceny wielomianów Legendre'a. Algorytm zapewnia również certyfikowaną granicę błędu.

Porównanie z innymi regułami kwadraturowymi

Kwadratura Gaussa-Legendre'a jest optymalna w bardzo wąskim sensie do obliczania całek funkcji f po [-1, 1] , ponieważ żadna inna reguła kwadraturowa nie integruje dokładnie wszystkich wielomianów stopnia 2 n - 1 przy użyciu n punktów próbkowania. Jednak ta miara dokładności nie jest na ogół zbyt użyteczna - wielomiany są bardzo proste do całkowania, a ten argument sam w sobie nie gwarantuje lepszej dokładności całkowania innych funkcji.

Kwadratura Clenshawa-Curtisa opiera się na aproksymacji f przez interpolant wielomianowy w węzłach Czebyszewa i integruje wielomiany stopnia do n dokładnie przy danych n próbkach. Mimo że nie całkuje wielomianów ani innych funkcji analitycznych w dużym sąsiedztwie [-1, 1], jak również kwadratury Gaussa-Legendre'a, Clenshaw-Curtis zbiega się w przybliżeniu z taką samą szybkością jak kwadratura Gaussa-Legendre'a dla większości (nie -analityczne) całki. Ponadto Clenshaw – Curtis ma wspólne właściwości, którymi cieszy się kwadratura Gaussa – Legendre'a, takie jak zbieżność dla wszystkich ciągłych całek f i odporność na numeryczne błędy zaokrąglania. $– Curtis$ do wdrożenia metodami opartymi FFT

Kwadratura Newtona – Cotesa jest oparta na przybliżeniu f przez interpolant wielomianowy w równo rozmieszczonych punktach w [−1, 1] i podobnie jak Clenshaw – Curtis również całkuje wielomiany stopnia do n dokładnie przy danych n próbkach. Jednak cierpi na zjawisko Runge'a wraz ze wzrostem n ; Newton-Cotes nie jest zbieżny dla niektórych ciągłych całek f , a kiedy jest zbieżny, mogą wystąpić błędy zaokrągleń numerycznych. Zatem zarówno Clenshaw-Curtis, jak i Gauss-Legendre cieszą się znacznymi korzyściami w porównaniu z Newtonem-Cotesem dla średnich i dużych n .