Gauss–Legendre kvadratur

I numerisk analys är Gauss-Legendre-kvadratur en form av Gaussisk kvadratur för att approximera den bestämda integralen av en funktion . För att integrera över intervallet [−1, 1] tar regeln formen:

$\int _{-1}^{1}f(x)\,dx\approx \sum _{ i=1}^{n}w_{i}f(x_{i})$

var

• n är antalet provpunkter som används,
• w _i är kvadraturvikter, och
• x _i är rötterna till det n :te Legendre-polynomet .

Detta val av kvadraturvikter w _i och kvadraturnoder x _i är det unika valet som tillåter kvadraturregeln att integrera grad 2 n − 1 polynom exakt.

Många algoritmer har utvecklats för att beräkna Gauss-Legendre-kvadraturregler. Golub–Welsch-algoritmen som presenterades 1969 reducerar beräkningen av noderna och vikterna till ett egenvärdeproblem som löses av QR-algoritmen . Denna algoritm var populär, men det finns betydligt effektivare algoritmer. Algoritmer baserade på Newton-Raphson-metoden kan beräkna kvadraturregler för betydligt större problemstorlekar. Under 2014 presenterade Ignace Bogaert explicita asymptotiska formler för Gauss–Legendre kvadraturvikter och noder, som är exakta inom dubbelprecision maskin epsilon för alla val av n ≥ 21. Detta möjliggör beräkning av noder och vikter för värden på n som överstiger en miljard.

Historia

Carl Friedrich Gauss var den förste som härledde Gauss–Legendre kvadraturregeln, och gjorde det genom en beräkning med fortsatta bråk 1814. Han beräknade noderna och vikterna till 16 siffror upp till ordningen n =7 för hand. Carl Gustav Jacob Jacobi upptäckte sambandet mellan kvadraturregeln och den ortogonala familjen av legendrepolynom . Eftersom det inte finns någon formel i sluten form för kvadraturvikterna och noderna, kunde människor under många decennier bara använda handberäkna dem för små n , och att beräkna kvadraturen var tvungen att göras genom att referera till tabeller som innehöll vikten och nodvärdena. År 1942 var dessa värden bara kända för upp till n =16.

Definition

Grafer av Legendre polynom (upp till n = 5)

För att integrera f över $[-1,1]$ med Gauss–Legendre-kvadraturen är de associerade ortogonala polynomen Legendre-polynom , betecknade med P _n ( x ) . Med det n :e polynomet normaliserat så att P _n (1) = 1 , är den i :te Gauss-noden, x _{i , den} i:te roten av P _n och vikterna ges av formeln ( Abramowitz & Stegun 1972 , s. 887)

$w_{i}={\frac {2}{\left(1-x_{i}^{2}\right)\left[P'_{n}(x_{i})\right]^ {2}}}.$

Några lågordnings kvadraturregler är tabellerade nedan för att integrera över $[-1,1]$ .

Antal poäng, n	Poäng, x i		Vikter, m i
1	0		2
2	$\pm {\frac {1}{\sqrt {3}}}$	±0,57735…	1
3	0		${\frac {8}{9}}$	0,888889…
	$\pm {\sqrt {\frac {3}{5}}}$	±0,774597…	${\frac {5}{9}}$	0,555556…
4	$\pm {\sqrt {{\frac {3}{7}}-{\frac {2}{7}}{\sqrt {\frac {6}{5} }}}}$	±0,339981…	${\frac {18+{\sqrt {30}}}{36}}$	0,652145…
	$\pm {\sqrt {{\frac {3}{7}}+{\frac {2}{7}}{\sqrt {\frac {6}{5} }}}}$	±0,861136…	${\frac {18-{\sqrt {30}}}{36}}$	0,347855…
5	0		${\frac {128}{225}}$	0,568889…
	$\pm {\frac {1}{3}}{\sqrt {5-2{\sqrt {\frac {10}{7}}}}}$	±0,538469…	${\frac {322+13{\sqrt {70}}}{900}}$	0,478629…
	$\pm {\frac {1}{3}}{\sqrt {5+2{\sqrt {\frac {10}{7}}}}}$	±0,90618…	${\frac {322-13{\sqrt {70}}}{900}}$	0,236927…

För att integrera över ett allmänt reellt intervall $[a,b]$ , kan en ändring av intervallet tillämpas för att konvertera problemet till ett med integration över $[-1 ,1]$ .

Algoritmer

Newton-Raphson metoder

Flera forskare har utvecklat algoritmer för att beräkna Gauss-Legendre-kvadraturnoder och vikter baserade på Newton-Raphson-metoden för att hitta funktioners rötter. Olika optimeringar för detta specifika problem används. Till exempel, vissa metoder beräknar $\theta _{i}=\arccos x_{i}$ för att undvika problem associerade med klustring av rötterna $x_{i}$ nära ändarna av intervallet $-1$ och $1$ . Vissa metoder använder formler för att approximera vikterna och använder sedan några iterationer av Newton-Raphson för att sänka approximationens fel till under maskinprecisionen.

Golub–Welsch

År 1969 publicerade Golub och Welsch sin metod för att beräkna Gaussiska kvadraturregler med tanke på de tre termer återkommande relationen som de underliggande ortogonala polynomen uppfyller. De reducerar problemet med att beräkna noderna för en Gaussisk kvadraturregel till problemet att hitta egenvärdena för en viss symmetrisk tridiagonal matris . QR -algoritmen används för att hitta egenvärdena för denna matris. Genom att dra fördel av den symmetriska tridiagonala strukturen kan egenvärdena beräknas i ${\mathcal {O}}(n^{2})$ tid, i motsats till ${ \displaystyle {\mathcal {O}}(n^{3})}$ förväntad tid för ett generiskt egenvärdeproblem.

Asymptotiska formler

Olika metoder har utvecklats som använder ungefärliga uttryck i sluten form för att beräkna noderna. Som nämnts ovan används i vissa metoder formler som approximationer till noderna, varefter några Newton-Raphson-iterationer utförs för att förfina approximationen. I en artikel från 2014 härleder Ignace Bogaert asymptotiska formler för noderna som är exakta upp till maskinprecision för $n\geq 21$ och för vikterna som är exakta upp till maskinprecision för $n\geq 30$ . Denna metod kräver inga Newton-Raphson-iterationer eller utvärderingar av Bessel-funktioner som andra metoder gör. Som framgår av artikeln kunde metoden beräkna noderna vid en problemstorlek på en miljard på 11 sekunder. Eftersom noderna nära ändpunkterna för $[-1,1]$ blir mycket nära varandra vid denna problemstorlek, är denna metod för att beräkna noderna tillräcklig för i princip alla praktiska tillämpningar i dubbel- precision flytande punkt.

Högre precision

Johansson och Mezzarobba beskriver en strategi för att beräkna Gauss–Legendre-kvadraturregler i aritmetik med godtycklig precision, vilket tillåter både små och stora $n$ . En ordningsregel $n=1000$ med 1000 siffrors precision kan beräknas på cirka en sekund. Deras metod använder Newton-Raphson iteration tillsammans med flera olika tekniker för att utvärdera Legendre polynom. Algoritmen tillhandahåller också en certifierad felbunden.

Jämförelse med andra kvadraturregler

Gauss–Legendre-kvadratur är optimal i mycket snäv mening för att beräkna integraler av en funktion f över [−1, 1] , eftersom ingen annan kvadraturregel integrerar alla grad 2 n − 1 polynom exakt när n sampelpunkter används. Detta mått på noggrannhet är dock i allmänhet inte särskilt användbart --- polynom är mycket enkla att integrera och detta argument garanterar inte i sig bättre noggrannhet när det gäller att integrera andra funktioner.

Clenshaw–Curtis-kvadraturen är baserad på approximering av f med en polynominterpolant vid Chebyshev-noder och integrerar polynom med grader upp till n exakt när de ges n sampel. Även om den inte integrerar polynom eller andra funktioner som är analytiska i ett stort område av [−1, 1] såväl som Gauss–Legendre-kvadraturen, konvergerar Clenshaw–Curtis med ungefär samma hastighet som Gauss–Legendre-kvadraturen för de flesta (icke -analytiska) integrander. Clenshaw–Curtis delar också egenskaperna som Gauss–Legendre-kvadraturen åtnjuter av konvergens för alla kontinuerliga integrander f och robusthet mot numeriska avrundningsfel. Clenshaw–Curtis är enkel att implementera i ${\displaystyle {\mathcal {O}}(n\log n)}-$ tid med FFT -baserade metoder.

Newton–Cotes kvadratur är baserad på att approximera f av en polynominterpolant vid punkter med lika mellanrum i [−1, 1] , och liksom Clenshaw–Curtis integrerar även polynom av grader upp till n exakt när de ges n sampel. Den lider dock av Runges fenomen då n ökar; Newton–Cotes konvergerar inte för vissa kontinuerliga integrander f , och när den konvergerar kan den drabbas av numeriska avrundningsfel. Sålunda åtnjuter både Clenshaw–Curtis och Gauss–Legendre betydande fördelar jämfört med Newton–Cotes för måttlig till stor n .