Numerisk integration

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 10 mars 2020; kontroller kräver 10 redigeringar .

Numerisk integration (historiskt namn: (numerisk) kvadratur ) är beräkningen av värdet av en bestämd integral (vanligtvis ungefärlig). Numerisk integration förstås som en uppsättning numeriska metoder för att hitta värdet av en viss integral.

Numerisk integration tillämpas när:

Integranden i sig definieras inte analytiskt. Till exempel presenteras den som en tabell (matris) av värden vid noderna i något beräkningsnät.
Den analytiska representationen av integranden är känd, men dess antiderivata uttrycks inte i termer av analytiska funktioner. Till exempel . $f(x)=\exp(-x^{2})$

I dessa två fall är det omöjligt att beräkna integralen med hjälp av Newton-Leibniz formel . Det är också möjligt att formen av antiderivatan är så komplex att det går snabbare att beräkna värdet på integralen numeriskt.

Endimensionellt fall

Huvudidén med de flesta metoder för numerisk integration är att ersätta integranden med en enklare, vars integral lätt kan beräknas analytiskt. I det här fallet, för att uppskatta värdet av integralen, formler av formen

I\approx \summa _{{i=1}}^{{n}}w_{i}\,f(x_{i}),

där är antalet poäng vid vilka integrandens värde beräknas. Punkterna kallas för metodens noder, siffrorna är nodernas vikter. När integranden ersätts av ett polynom av noll, första och andra graden, erhålls metoderna för rektanglar , trapetser och paraboler (Simpson) respektive. Ofta kallas formler för att uppskatta integralens värde kvadraturformler. $n$ $x_{i}$ $w_{i}$

Ett specialfall är metoden för att konstruera integrala kvadraturformler för enhetliga rutnät, kända som Cotes-formlerna . Metoden är uppkallad efter Roger Coates . Huvudidén med metoden är att ersätta integranden med någon form av interpolationspolynom . Efter att ha tagit integralen kan vi skriva

\int \limits _{a}^{b}f(x)\,dx=\summa _{{i=0}}^{{n}}H_{i}\,f(x_{i})+ r_{n}(f),

där talen kallas Cotes-koefficienter och beräknas som integraler av motsvarande polynom i det ursprungliga interpolationspolynomet för integranden vid värdet av funktionen vid noden ( är rutsteget; är antalet rutnätsnoder och nodindexet är ). Termen är metodens fel, som kan hittas på olika sätt. För udda kan felet hittas genom att integrera felet för integrandens interpolationspolynom. $Hej$ $x_{i}=a+ih$ $h=(ba)/n$ $n$ $i=0\ldots n$ $r_{n}(f)$ $n\geqslant 1$

Specialfall av Cotes formler är: rektangelformler ( ), trapetsformler ( ), Simpsons formel ( ), Newtons formel ( ), etc. $n=0$ $n=1$ $n=2$ $n=3$

Rektangelmetoden

Låt det krävas att bestämma värdet på integralen av funktionen på intervallet . Detta segment delas med punkter i lika långa segment . Beteckna med värdet av funktionen vid punkter . Därefter gör vi upp summorna Var och en av summorna är integralsumman för on och uttrycker därför ungefär integralen $\left[{a},{b}\right]$ $x_{0},x_{1},\ldots ,x_{{n-1}},x_{n}$ $n$ $\Delta {x}={\frac {ba}{n}}.$ $y_{0},y_{1},\ldots ,y_{{n-1}},y_{n}$ $f\vänster(x\höger)$ $x_{0},x_{1},\ldots,x_{{n-1}},x_{n}.$ $y_{0}\,\Delta {x}+y_{1}\,\Delta {x}+\ldots +y_{{n-1}}\,\Delta {x}.$ $f\vänster(x\höger)$ $\left[{a},{b}\right]$

\int \limits _{a}^{b}f(x)\,dx\approx {\frac {ba}{n}}(y_{0}+y_{1}+\ldots +y_{{n- ett}}).

Om den givna funktionen är positiv och ökande, uttrycker denna formel arean av en stegad figur som består av "inkommande" rektanglar, även kallad formeln för vänster rektanglar, och formeln

\int \limits _{a}^{b}f(x)\,dx\approx {\frac {ba}{n}}(y_{1}+y_{2}+\ldots +y_{n})

uttrycker arean av en stegad figur som består av "utgående" rektanglar, även kallad formeln för räta rektanglar. Ju kortare längden på segmenten som segmentet är uppdelat i, desto mer exakt är värdet som beräknas med denna formel för den önskade integralen. $\left[{a},{b}\right]$

Självklart ska man räkna med större noggrannhet om man tar punkten i mitten av intervallet som referenspunkt för att hitta höjden. Som ett resultat får vi formeln för de mellersta rektanglarna:

\int \limits _{a}^{b}f(x)\,dx\approx h\sum _{{i=1}}^{{n}}f\left(x_{{i-1}} +{\frac {h}{2}}\right)=h\summa _{{i=1}}^{{n}}f\left(x_{i}-{\frac {h}{2} }\höger),

var $h={\frac {ba}{n}}$

Med tanke på den a priori större noggrannheten av den sista formeln med samma volym och karaktär av beräkningar, kallas den rektanglars formel

Trapetsformad metod

Om funktionen på vart och ett av de partiella segmenten approximeras av en rät linje som går genom de slutliga värdena, får vi trapetsmetoden.

Arean av trapetsen på varje segment:

I_{i}\approx {\frac {f(x_{i-1})+f(x_{i})}{2}}(x_{i}-x_{i-1}).

Approximationsfel för varje segment:

\left|R_{i}\right|\leqslant {\frac {\left(ba\right)^{3}}{12n^{2}}}M_{2,i},

var

M_{2,i}=\max _{x\in [x_{i-1},\,x_{i}]}{\left|f''(x)\right|}.

Den fullständiga formeln för trapetser vid uppdelning av hela integrationsintervallet i segment med samma längd : $h$

I\approx h\left({\frac {f(x_{0})+f(x_{n})}{2}}+\sum _{i=1}^{n-1}f (x_{i})\höger),

var

h={\frac {ba}{n}}.

Trapetsformelfel:

\left|R\right|\leqslant {\frac {\left(ba\right)^{3}}{12n^{2}}}M_{2},

var

M_{2}=\max _{x\in [a,\,b]}{\left|f''(x)\right|}.

Parabolmetod (Simpsons metod)

Med hjälp av tre punkter i integrationssegmentet kan vi ersätta integranden med en parabel. Vanligtvis används segmentets ändar och dess mittpunkt som sådana punkter. I det här fallet är formeln väldigt enkel

I\approx {\frac {ba}{6}}\left(f(a)+4f\left({\frac {a+b}{2}}\right)+f(b)\right)

Om vi delar upp integrationsintervallet i lika delar så har vi det $2N$

I\approx {\frac {ba}{6N}}\left(f_{0}+4\left(f_{1}+f_{3}+\ldots +f_{2N-1}\right) +2\left(f_{2}+f_{4}+\ldots +f_{2N-2}\right)+f_{2N}\right),

var . $f_{i}=f\left(a+{\frac {(ba)i}{2N}}\höger)$

Ökar noggrannheten

Approximation av en funktion med ett polynom över hela integrationsintervallet leder som regel till ett stort fel vid uppskattningen av integralens värde.

För att minska felet delas integrationssegmentet upp i delar och en numerisk metod används för att utvärdera integralen på var och en av dem.

Eftersom antalet partitioner tenderar till oändligt, tenderar uppskattningen av integralen till dess verkliga värde för analytiska funktioner för vilken numerisk metod som helst.

Ovanstående metoder möjliggör en enkel procedur för att halvera steget, medan det vid varje steg krävs att endast beräkna funktionsvärdena vid nytillkomna noder. För att uppskatta beräkningsfelet används Runge-regeln .

Gauss-metoden

Metoderna som beskrivs ovan använder fasta punkter i segmentet (ändar och mitten) och har en låg noggrannhetsordning (0 - metoder för höger och vänster rektanglar, 1 - metoder för mellersta rektanglar och trapezoider, 3 - paraboler (Simpson) metod). Om vi kan välja de punkter där vi beräknar funktionens värden , kan vi erhålla metoder med högre noggrannhetsordning med samma antal beräkningar av integranden. Så för två (som i trapetsmetoden) beräkningar av integrandens värden kan du få en metod som inte är den andra utan den tredje noggrannhetsordningen: $f(x)$

I\approx {\frac {ba}{2}}\left(f\left({\frac {a+b}{2}}-{\frac {ba}{2{\sqrt {3}}}} \right)+f\left({\frac {a+b}{2}}+{\frac {ba}{2{\sqrt {3}}}}\right)\right)

I det allmänna fallet, med hjälp av punkter, kan formeln användas för att erhålla en metod med noggrannhetsordningen , det vill säga exakta värden erhålls för polynom av grad som inte är högre än . $n$ $I\approx \sum _{{i=1}}^{{n}}a_{i}\,f(x_{i})$ $2n-1$ $2n-1$

Nodvärdena för Gauss-metoden efter punkter är rötterna till Legendre- gradpolynomet . Viktvärdena beräknas med formeln , där är den första derivatan av Legendre-polynomet . $x_{i}$ $n$ $n$ ${\displaystyle a_{i}={\frac {2}{(1-x_{i}^{2})\,[P_{n}'(x_{i})]^{2))))$ $P_{n}'$

För noder och vikter har följande betydelser: vikter: $n=3$ $x_{{1,3}}=\pm {\sqrt {0.6}},x_{2}=0,$ $a_{1,3}={\frac {5}{9)),a_{2}={\frac {8}{9}}$

(polynomet definieras på segmentet ). $[-1,1]$

Den mest kända är den Gaussiska fempunktsmetoden.

Gauss-Kronrod-metoden

Nackdelen med Gauss-metoden är att den inte har ett enkelt (ur beräkningssynpunkt) sätt att uppskatta felet för det erhållna värdet av integralen. Användningen av Runges regel kräver beräkning av integranden vid ungefär samma antal poäng, samtidigt som det praktiskt taget inte ger någon vinst i noggrannhet, till skillnad från enkla metoder, där noggrannheten ökar flera gånger med varje ny partition. Kronrod föreslog följande metod för att uppskatta värdet av integralen

I\approx \sum _{{i=1}}^{{n}}a_{i}\,f(x_{i})+\summa _{{i=1}}^{{n+1} }b_{i}\,f(y_{i})

var är Gauss-metodens noder efter punkter, och parametrarna , , väljs på ett sådant sätt att metodens noggrannhetsordning är lika med . $x_{i}$ $n$ $3n+2$ $a_{i}$ $bi}$ $y_{i}$ $3n+1$

Sedan, för att uppskatta felet, kan du använda den empiriska formeln :

\Delta =\left(200|I-I_{G}|\right)^{{1.5}}

där är det ungefärliga värdet av integralen som erhålls med Gauss-metoden över punkter. gsl- och SLATEC -biblioteken för beräkning av bestämda integraler innehåller rutiner som använder Gauss-Kronrod-metoden för 15, 21, 31, 41, 51 och 61 poäng. ALGLIB -biblioteket använder Gauss-Kronrod-metoden för 15 poäng . $I_{G}$ $n$

Chebyshevs metod

Chebyshev-metoden (eller som den ibland kallas Gauss-Chebyshev) är en av representanterna för Gauss metoder med högsta algebraiska noggrannhet. Dess utmärkande drag är att integranden har en multiplikator , dvs. kärnan är detta: $\left({\frac {1}{\sqrt {1-x^{2))))\right)$

\int \limits _{-1}^{1}f(x)\left({\frac {1}{\sqrt {1-x^{2))))\right)\,dx= \sum _{i=1}^{N}C_{i}f(x_{i})

där , , är antalet metodnoder. $C_{i}=\pi /N$ $x_{i}=cos\left({\frac {(2i-1)\pi }{2N}}\right)$ $N$

Gauss-Lager-metoden

Gauss-Hermite-metoden

Integration över oändliga gränser

För att integrera över oändliga gränser måste du införa ett olikformigt rutnät, vars steg ökar när du går till oändligheten, eller så kan du göra en sådan förändring av variabler i integralen, varefter gränserna blir ändliga. Man kan gå tillväga på liknande sätt om funktionen är singular i slutet av integrationsintervallet.

Se även Samokish Method .

Monte Carlo Methods

För att bestämma arean under funktionsdiagrammet kan du använda följande stokastiska algoritm:

vi begränsar funktionen till en rektangel (en n - dimensionell parallellepiped i fallet med många dimensioner), vars area lätt kan beräknas; $Mast}}$
"klottra" i denna rektangel (parallellepipedum) ett visst antal punkter ( bitar), vars koordinater vi kommer att välja slumpmässigt; $N$
bestämma antalet punkter ( bitar) som faller under funktionens graf; $K$
arean av området som begränsas av funktions- och koordinataxlarna ges av uttrycket ; $S$ $S=S_{{par}}{\frac {K}{N}}$

Denna algoritm kräver bestämning av funktionens extrema värden på intervallet och använder inte det beräknade exakta värdet för funktionen förutom för jämförelse, och är därför olämplig för övning. De versioner av Monte Carlo-metoden som ges i huvudartikeln är fria från dessa brister. $f(x)$

För ett litet antal dimensioner av den integrerbara funktionen är prestandan för Monte Carlo-integration mycket lägre än prestandan för deterministiska metoder. Men i vissa fall, när funktionen är specificerad implicit, men det är nödvändigt att bestämma arean specificerad i form av komplexa ojämlikheter, kan den stokastiska metoden vara mer att föredra.

Runge-Kutta metoder

Runge-Kutta-metoder - en viktig familj av numeriska algoritmer för att lösa vanliga differentialekvationer och deras system - iterativa metoder för explicita och implicita ungefärliga beräkningar, utvecklade omkring 1900 av de tyska matematikerna K. Runge och M. V. Kutta .

Spline-metod

Flerdimensionellt fall

I små dimensioner kan man också tillämpa kvadraturformler baserade på interpolationspolynom . Integration utförs på samma sätt som endimensionell integration. För stora dimensioner blir dessa metoder oacceptabla på grund av den snabba ökningen av antalet rutnätspunkter och/eller regionens komplexa gräns. I det här fallet tillämpas Monte Carlo-metoden . Slumpmässiga poäng genereras i vårt område och funktionsvärdena i dem är medelvärde. Du kan också använda ett blandat tillvägagångssätt - dela upp området i flera delar, i var och en av dem (eller endast i de där integralen inte kan beräknas på grund av en komplex gräns), tillämpa Monte Carlo-metoden .

Implementeringsexempel

Nedan är Python 3-implementeringen av medelrektangelmetoden, medeltrapetsmetoden, Simpson-metoden och Monte Carlo-metoden.

import math , slumpmässigt från numpy import arange def get_i (): returnera matematik . e ** 1 - matematik . e ** 0 def method_of_rektanglar ( func , min_lim , max_lim , delta ): def integrera ( func , min_lim , max_lim , n ) : integral = 0.0 steg = ( max_lim - min_lim ) / n för x i arrangemang ( min_lim , max_lim - steg ) : integral += steg * func ( x + steg / 2 ) returnerar integral d , n = 1 , 1 medan abs ( d ) > delta : d = ( integrera ( func , min_lim , max_lim , n * 2 ) - integrera ( func , min_lim , max_lim , n )) / 3 n *= 2 a = abs ( integrera ( func , min_lim , max_lim , n )) b = abs ( integrera ( func , min_lim , max_lim , n )) + d om a > b : a , b = b , en utskrift ( 'Rektanglar:' ) print ( ' \t %s \t %s \t %s ' % ( n , a , b )) def trapezium_metod ( func , min_lim , max_lim , delta ): def integrera ( func , min_lim , max_lim , n ) : integral = 0.0 steg = ( max_lim - min_lim ) / n för x i arange ( min_lim , max_lim - steg ) : integral += steg * ( func ( x ) + func ( x + steg )) / 2 returnera integral d , n = 1 , 1 medan abs ( d ) > delta : d = ( integrera ( func , min_lim , max_lim , n * 2 ) - integrera ( func , min_lim , max_lim , n )) / 3 n *= 2 a = abs ( integrera ( func , min_lim , max_lim , n )) b = abs ( integrera ( func , min_lim , max_lim , n )) + d om a > b : a , b = b , ett tryck ( 'Trapes:' ) print ( ' \t %s \t %s \t %s ' % ( n , a , b )) def simpson_metod ( func , min_lim , max_lim , delta ): def integrera ( func , min_lim , max_lim , n ): integral = 0.0 steg = ( max_lim - min_lim ) / n för x i arange ( min_lim + step / 2 - step , max_lim / 2 , steg ): integral += steg / 6 * ( func ( x - steg / 2 ) + 4 * func ( x ) + func ( x + steg / 2 )) returnera integral d , n = 1 , 1 medan abs ( d ) > delta : d = ( integrera ( func , min_lim , max_lim , n * 2 ) - integrera ( func , min_lim , max_lim , n )) / 15 n *= 2 a = abs ( integrera ( func , min_lim , max_lim , n )) b = abs ( integrera ( func , min_lim , max_lim , n )) + d om a > b : a , b = b , en utskrift ( 'Simpson:' ) print ( ' \t %s \t %s \t %s ' % ( n , a , b )) def monte_karlo_method ( func , n ): in_d , out_d = 0. , 0. for i in arange ( n ): x , y = slumpmässigt . enhetlig ( 0 , 1 ), slumpmässig . uniform ( 0 , 3 ) om y < func ( x ): in_d += 1 print ( 'MK:' ) print ( ' \t %s \t %s ' % ( n , abs ( in_d / n * 3 ))) metod_av_rektanglar ( lambda x : matte . e ** x , 0,0 , 1,0 , 0,001 ) trapeziummetod ( lambda x : matte . e ** x , 0,0 , 1,0 , 0,001 ) simpson _ xod , ** da , 0 _ _ _ _ _ 1,0 , 0,001 ) monte_karlo_method ( lambda x : math . e ** x , 100 ) print ( 'Sant värde: \n\t %s ' % get_i ())

Litteratur

Kahaner D., Mowler K., Nash S. Numeriska metoder och programvara (översatt från engelska) .. - Ed. andra, stereotyp .. - M . : Mir, 2001. - 575 sid. — ISBN 5-03-003392-0 .
Samarsky A. A. , Gulin A. V. Numeriska metoder: Proc. ersättning för universitet. - M . : Vetenskap. Ch. ed. fysik och matematik lit., 1989. - 432 sid. — ISBN 5-02-013996-3 .
Piskunov N. S. Differential- och integralkalkyl: Proc. ersättning för universitet: I 2 volymer - 13:e uppl. - M . : Nauka. Ch. ed. fysik och matematik lit., 1985. - 432 sid.
Boltachev G.Sh. Numeriska metoder inom termisk fysik. Föreläsningskurs Föreläsning 3: Numerisk integration

Se även

Integralkalkyl

Main

Generaliseringar
av Riemann-integralen

Integrerade
transformationer

Numerisk
integration

måttteori

Relaterade ämnen

Listor över integraler