Gauss–Kronrod kvadraturformel

Gauss –Kronrod kvadraturformeln är en adaptiv metod för numerisk integration . Det är en variant av Gaussisk kvadratur , där utvärderingspunkterna väljs så att en exakt approximation kan beräknas genom att återanvända informationen som produceras genom beräkningen av en mindre exakt approximation. Det är ett exempel på vad som kallas en kapslad kvadraturregel: för samma uppsättning funktionsutvärderingspunkter har den två kvadraturregler, en högre ordning och en lägre ordning (den senare kallas en inbäddad regel ) . Skillnaden mellan dessa två approximationer används för att uppskatta beräkningsfelet för integrationen.

Dessa formler är uppkallade efter Alexander Kronrod , som uppfann dem på 1960-talet, och Carl Friedrich Gauss .

Beskrivning

Problemet med numerisk integration är att approximera bestämda integraler av formen

\int _{a}^{b}f(x)\,dx.

Sådana integraler kan approximeras, till exempel med n -punkts Gaussisk kvadratur

\int _{a}^{b}f(x)\,dx\approx \summa _{i =1}^{n}w_{i}f(x_{i}),

där w _i , x _i är vikterna och punkterna vid vilka funktionen f ( x ) ska utvärderas.

Om intervallet [ a , b ] är uppdelat, sammanfaller Gauss-utvärderingspunkterna för de nya delintervallen aldrig med de tidigare utvärderingspunkterna (förutom vid mittpunkten för udda antal utvärderingspoäng), och därför måste integranden utvärderas vid varje punkt. Gauss–Kronrod-formler är förlängningar av Gauss kvadraturformler som genereras genom att lägga till $n+1$ punkter till en $n$ -punktsregel på ett sådant sätt att den resulterande regeln är av ordningen $3n+1$ ( Laurie (1997 , s. 1133); motsvarande Gauss-regel är av ordningen $2n-1$ ). Dessa extra poäng är nollorna för Stieltjes polynom . Detta gör det möjligt att beräkna uppskattningar av högre ordning samtidigt som funktionsvärdena för en uppskattning av lägre ordning återanvänds. Skillnaden mellan en Gauss-kvadraturregel och dess Kronrod-förlängning används ofta som en uppskattning av approximationsfelet.

Exempel

Ett populärt exempel kombinerar en 7-punkts Gauss-regel med en 15-punkts Kronrod-regel ( Kahaner, Moler & Nash 1989, §5.5). Eftersom Gauss-punkterna är inkorporerade i Kronrod-punkterna behövs totalt endast 15 funktionsutvärderingar.

(G7, K15) på [−1,1]
Gauss noder		Vikter
±0,94910 79123 42759	∗	0,12948 49661 68870
±0,74153 11855 99394	∗	0,27970 53914 89277
±0,40584 51513 77397	∗	0,38183 00505 05119
0,00000 00000 00000	∗	0,41795 91836 73469
Kronrodsnoder		Vikter
±0,99145 53711 20813		0,02293 53220 10529
±0,94910 79123 42759	∗	0,06309 20926 29979
±0,86486 44233 59769		0,10479 00103 22250
±0,74153 11855 99394	∗	0,14065 32597 15525
±0,58608 72354 67691		0,16900 47266 39267
±0,40584 51513 77397	∗	0,19035 05780 64785
±0,20778 49550 07898		0,20443 29400 75298
0,00000 00000 00000	∗	0,20948 21410 84728

Integralen uppskattas sedan av Kronrodsregeln $K15$ och felet kan uppskattas till $|G7-K15|$ .

För ett godtyckligt intervall ${\displaystyle [a,b]} skalas$ nodpositionerna $x_{i}$ och vikterna $w_{i}$ till intervallet enligt följande :

x_{i,{\text{scaled}}}={\frac {x_{i}+1}{2}}(ba )+a

w_{i,{\text{scaled}}}=w_{i}{\frac {ba}{2}}

Patterson (1968) visade hur man hittar ytterligare tillägg av denna typ, Piessens (1974) och Monegato (1978) föreslog förbättrade algoritmer , och slutligen föreslogs den mest effektiva algoritmen av Laurie (1997) . Fyrdubbla precisionskoefficienter (34 decimalsiffror) för (G7, K15), (G10, K21), (G15, K31), (G20, K41) och andra beräknas och tabelleras.

Genomföranden

Rutiner för Gauss–Kronrod-kvadraturen tillhandahålls av QUADPACK -biblioteket, GNU Scientific Library , NAG Numerical Libraries , R , C++ - biblioteket Boost ., samt Julia-paketet quadGK.jl

Se även

Clenshaw–Curtis quadrature , en annan kapslad kvadraturregel med liknande noggrannhet

Anteckningar

"Gauss–Kronrod quadrature formula" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
Kahaner, David; Moler, Cleve ; Nash, Stephen (1989), Numeriska metoder och programvara , Prentice–Hall , ISBN 978-0-13-627258-8
Kronrod, Aleksandr Semenovish (1965), Noder och vikter av kvadraturformler. Sexton-platsbord , New York: Consultants Bureau (Auktoriserad översättning från ryska)
Piessens, Robert; de Doncker-Kapenga, Elise; Überhuber, Christoph W. [på tyska] ; Kahaner, David K. (1983), QUADPACK, A subroutine package for automatic integration , Springer-Verlag , ISBN 978-3-540-12553-2 (Referensguide för QUADPACK)
Patterson, Thomas NL (1968), "The Optimum Addition of Points to Quadrature Formulae", Math. Comput. , 22 (104): 847–856 och C1–C11, doi : 10.2307/2004583 , JSTOR 2004583 . Erratum i matte. Comput. 23 :892.
Piessens, Robert; Branders, Maria (1974), "A Note on the Optimal Addition of Abscissas to Quadrature Formulas of Gauss and Lobatto", Mathematics of Computation , 28 (125): 135–139, doi : 10.2307/2005820 , JSTOR 200
Monegato, Giovanni (1978), "Några anmärkningar om konstruktionen av utökade Gaussiska kvadraturregler", Mathematics of Computation , 32 (141): 247–252, doi : 10.2307/2006272 , JSTOR 2006272
Laurie, Dirk (1997), "Calculation of Gauss-Kronrod quadrature rules.", Mathematics of Computation , 66 (219): 1133–1145, doi : 10.1090/s0025-5718-97-00861-2

externa länkar

QUADPACK (del av SLATEC) , källkod [1] . QUADPACK är en samling algoritmer, i Fortran , för numerisk integration baserad på Gauss-Kronrod-regler. SLATEC (på Netlib ) är ett stort offentligt bibliotek för numerisk beräkning.
ALGLIB källkod i C#, C++, Delphi & Visual Basic