Numerička integracija

Numerička integracija se sastoji od traženja numeričke aproksimacije za neku vrednost S

U numerici, numerička integracija se sastoji od velike porodice algoritama za računanje numeričke vrednosti određenog integrala, a termin je takođe korišten da opiše numeričko rešenje diferencijalne jednačine. Termin numerička kvadratura je manje-više sinonim za numeričku integraciju, pogotovo za jednodimenzionalne integrale. Numerička integracija u više dimenzija se opisuje kao kubatura, iako se izrazom kvadratura podrazumeva i višedimenziona integracija.

Osnovni problem u numeričkoj integraciji je izračunavanje približne vrednosti određenog integrala:

$I=\int _{a}^{b}\!f(x)\,dx$

sa zadatim stepenom tačnosti. Ako je f(x) glatka funkcija integrisana preko malog broja dimenzija i ako je domen integracije zatvoren, tada postoji više metoda za aproksimaciju integrala na željenu preciznost.

Numerička integracija se zasniva na integraciji interpolacionih polinoma. Npr. ukoliko se želi da se nađe neki određeni integral, može se poslužiti Njutn-Lajbnicovom formulom. Međutim, ukoliko je funkcija data tabelom svojih vrednosti u čvorovima, ili ako se njena primitivna funkcija ne može izraziti preko elementarnih funkcija, tada se mogu primeniti numerički metodi integracije. Formule preko kojih se vrši numeričko izračunavanje jednostrukih integrala se nazivaju kvadraturne formule.

Istorija

Glavni članak: Kvadratura (matematika)

Kvadratura je matematički istorijski pojam, a znači računanje površine. Kvadraturni problemi su bili glavni zadaci koji su zadavani kao izvor za matematičku analizu. Matematičari stare Grčke, prema Pitagorinoj doktrini, shvatili su računanje površine kao proces konstrukcije geometrijskog kvadrata koji ima jednaku površinu (kvadriranje). To je razlog što je proces nazvan kvadratura. Na primer: kvadratura kruga, hipokratov mesec i kvadratura parabole. Ova konstrukcija mora biti izvedena jedino upotrebom šestara i lenjira.

Stara metoda traženja geometrijske sredine

Za kvadraturu pravougaonika sa stranicama a i b potrebno je konstruisati kvadrat sa stranicom: $x={\sqrt {ab}}$

U ovu svrhu, moguće je koristiti sledeću činjenicu: ako se nacrta krug sa zbirom stranica a i b kao prečnik, onda je visina BH (sa tačke njihovog dodira do presjecanja sa krugom) jednaka njihovoj geometrijskoj sredini. Jednaka geometrijska konstrukcija rešava problem kvadrature paralelograma i trougla.

Površina segmenta parabole

Problemi kvadrature za krivolinijske figure su mnogo komplikovaniji. Kvadratura jednog kruga sa šestarom i lenjirom je bila dokazana u 19. veku kao nemoguća. Ipak, za neke oblike (na primer hipokratov mesec) kvadratura se može obaviti. Kvadrature sferične površine i dela parabole urađena od strane Arhimeda je postao najveći uspeh u antičkoj analizi.

• Površina lopte je jednaka četverostrukoj površini velikog kruga ove lopte.
• Površina dela parabole odsečena pravcem je 4/3 površine od trougla koji je upisan u ovaj segment.

Za dokaz rezultata, Arhimed je koristio metodu Eudoksa.

Greguar de Sen-VensanU srednjovekovnoj Evropi, kvadratura je značila proračun površine koristeći bilo koju metodu. Češće je metoda nedeljivosti korištena; manje je rigorozna, a jednostavnija i dobra. Pomoću nje, Galileo Galilei i Žil de Roberval su našli površinu svoda cikloide, Gregoir de Sajnt-Vinsent| je istražio površinu ispod hiperbole (Opus Geometricum, 1647), a Alfons Antonio de Sarasa, de Saint-Vincentov učenik i komentator, je uspostavio relaciju ove površine sa logaritmima.

Don Volis je „algebrizirao” ovaj metod: napisao je u svojim Arithmetica Infinitorum (1656) serijama ono što se danas zove određenim integralom, te izračunao njihove vrednosti. Ajzak Barou i Džejms Gregori su napravili dalji napredak: kvadrature za neke algebarske krivulje i spirale. Kristijan Hajgens je uspešno izveo kvadrature nekih „materijala revolucije”.

Kvadratura hiperbole od strane Saint-Vincenta i de Sarasa je pružila novu funkciju, prirodni logaritam, koja je od kritičnog značaja.

Sa otkrićem integralnog računa uspostavljena je univerzalna metoda za računanje površine. Kao odgovor, termin kvadratura je postao tradicionalan, a umesto njega moderna fraza „računanje određenog integrala” je češće upotrebljavana.

Razlozi za numeričku integraciju

Postoji više razloga zašto se koristi numerička integracija.

• Funkcija koja se integriše f(x) može biti poznata samo na pojedinim mestima, što se radi uzimanjem uzorka. Neki ugrađeni računari i ostale računarske aplikacije stoga koriste numeričku integraciju iz tog razloga.
• Formula za funkciju koja se integriše može biti poznata, ali može biti teško ili nemoguće naći antiderivaciju koja je elementarna funkcija. Jedan primjer je funkcija f(x) = exp(−x²), čija antiderivacija (funkcija greške puta konstanta) se ne može napisati u elementarnoj formi.
• Moguće je naći antiderivaciju simbolično, ali je mnogo jednostavnije naći numeričku aproskimaciju nego računati antiderivaciju (antiizvod). Ovo može biti slučaj ako je antiderivacija data kao neograničeni niz proizvoda, ili ako bi proračun zahtevao specijalne funkcije koje nisu dostupne računarima.

Metode za jednodimenzione integrale

Metode numeričke integracije se mogu generalno opisati kao kombinacije procena integranda (funkcije) da se dobije aproksimacija integrala. Integrand je definisan kao konačan skup tačaka nazivanih integracione tačke i zbir ovih vrednosti se koristi za aproksimaciju integrala. Integracione tačke i zbir zavise od posebnih metoda koje se koriste i preciznosti koja se traži aproksimacijom.

Važan deo analize bilo koje numeričke integracione metode je proučavanje ponašanja greške aproksimacije kao funkcija broja procene integranda. Metoda koja ima malu grešku za mali broj procena je često smatrana superiornom. Smanjenjem broja procena integranda, smanjuje se i broj korištenih aritmetičkih operacija, te se smanjuje ukupna greška proračuna. Takođe, svaka procena uzima vreme, a integrand može biti svojevoljno komplikovan.

Metoda grube sile („nasilna metoda” koja koristi sve kombinacije) numeričkog integrisanja može biti obavljena ako integrand ima „dobro ponašanje” (tj. ako je funkcija kontinualna i iz ograničene varijacije), sa procenom integranda sa veoma malim korakom - inkrementom.

Kvadraturna pravila bazirana na interpolaciji funkcija

Veliki broj kvadraturnih pravila se može naći izvođenjem funkcija koje su jednostavne za integriranje. Najčešće funkcije koje se interpoliraju su polinomi.

Ilustracija kvadratnog pravila.

Najjednostavnija metoda ovog tipa je dopuštanje da interpolirana funkcija bude konstantna (polinom nultog stepena) funkcija koja prolazi kroz tačku sa koordinatama ((a+b)/2, f((a+b)/2)). Ovo se zove pravilo sredine (srednje tačke) ili kvadratno pravilo.

$\int _{a}^{b}f(x)\,dx\approx (b-a)\,f\left({\frac {a+b}{2}}\right)$

Ilustracija trapeznog pravila.

Interpolacijska funkcija može biti polinom prvog stepena koja prolazi kroz tačke: (a, f(a)) i (b, f(b)). Ovo se zove trapezoidno pravilo.

$\int _{a}^{b}f(x)\,dx\approx (b-a)\,{\frac {f(a)+f(b)}{2}}.$

Ilustracija Simpsonovog pravila.

Za bilo koje od ovih pravila se može napraviti preciznija aproksimacija prekidanjem intervala [a, b] na veći broj podintervala, računajući aproksimaciju za svaki podinterval, te sabirajući sve u jedan rezultat. Ovo se zove kompozitno pravilo, prošireno pravilo ili iterativno pravilo. Na primer, kompozitno trapezno pravilo ima sledeći oblik:

$\int _{a}^{b}f(x)\,dx\approx {\frac {b-a}{n}}\left({f(a) \over 2}+\sum _{k=1}^{n-1}\left(f\left(a+k{\frac {b-a}{n}}\right)\right)+{f(b) \over 2}\right)$

gde podintervali imaju oblik [k h, (k+1) h], sa h = (b−a)/n i k = 0, 1, 2, ..., n−1.

Interpolacija sa polinomima procenjena sa tačkama sa jednakim rastojanjima u zatvorenom sektoru [a, b] se radi Njutn-Koutsovim formulama (njutn-kouts), od koje su primeri trapezno i kvadratno pravilo. Simpsonovo pravilo, koje se bazira na polinomima drugog reda, je takođe jutn-Koutsova formula.

Kvadraturna pravila sa jednako razmaknutim tačkama imaju veoma pogodnu osobinu gnežđenja. Odgovarajuće pravilo sa svakim podpodeljenim intervalom sadrži sve trenutne tačke, pa ove vrednosti integranda mogu biti ponovo iskorištene.

Ako se dopusti da intervali između interpolacionih tačaka variraju, onda se nalazi nova grupa kvadraturnih formula, kao što je Gausova kvadraturna formula. Gausovo kvadraturno pravilo je još preciznije od Njutn-Koutsovog pravila koje zahteva jednak broj iteracija ako je funkcija koja se integriše (integrand) glatka kriva (npr, ako je dovoljno diferencijabilna). Ostale kvadraturne metode sa varijacijom intervala uključuju Klenšo–Kurtisove kvadraturne metode (takođe zvane Fejerove kvarature), koje se gnezde.

Gausova kvadraturna pravila nemaju osobinu gnežđenja, ali Gaus–Kronrodove kvadraturne formule imaju.

Prilagodljivi algoritmi

Ako f(x) nema puno izvoda na svim tačkama, ili ako izvodi postanu ogromni, onda Gausova kvadratura je često nedovoljna. U tom slučaju, algoritam ispod će bolje uraditi zadatak:

def racunanje_odredjenog_integrala(f, initial_step_size):
    '''
    Ovaj algoritam računa određeni integral (onaj koji ima granice)
    funkcije od 0 do 1, birajući manje korake kod problematičnih
    tačaka.
    '''
    x = 0.0
    h = initial_step_size
    akumulator= 0.0
    while x < 1.0:
        if x + h > 1.0:
            h = 1.0 - x
        quad_this_step =
        if error_too_big_in_quadrature_of_over_range(f, [x,x+h]):
            h = make_h_smaller(h)
        else:
            akumulator+= quadrature_of_f_over_range(f, [x,x+h])
            x += h
            if error_too_small_in_quadrature_of_over_range(f, [x,x+h]):
                h = make_h_larger(h) # Izbjegavanje dangubljenja na malim koracima.
    return akumulator

Neki detalji algoritma zahtevaju pažljiv pristup. Za više slučajeva, pronalazak greške kvadrature na intervalu za funkciju f(x) nije očita. Jedno poznato rešenje je da se koriste dva pravila kvadratura i korištenjem razlike se može proceniti greška kvadrature. Čest problem je da se odluči šta označava „premalo” ili „preveliko”. Lokalni kriterijum za „preveliko” je da kvadraturna greška ne sme da bude veća od t · h, gde je t realni broj, tolerancija koja se želi podesiti za globalnu grešku. Opet, ako je h već malo, onda može biti bespotrebno učiniti ga čak manjim iako je kvadraturna greška velika. Globalni kriterijum je da zbir grešaka na svim intervalima bude manji od t. Ovaj tip analize greške se često naziva „posteriori” zato što se nakon svake procene računa i greška.

Metoda ekstrapolacije

Preciznost kvadraturnog pravila kod Njutn-Kouts tipa je uglavnom funkcija broja na tačkama procene. Rezultat je često više pouzdan kad se broj tačaka poveća, ili, ekvivalentno, kad se razmaci između tačaka smanje. Nameće se pitanje kakav bi rezultat bio kada bi razmaci među tačkama bili jednaki nuli. Odgovor se može naći ekstrapolacijom rezultata od dva do n razmaka koristeći ubrzavajuće metode kao npr. Ričardsonove ekstrapolacije. Ekstrapolaciona funkcija može biti polinom ili racionalna funkcija. Ekstrapolacione metode su opisanje detaljnije u od strane Stoera i Bulirča (Sekcija 3.4) i implementirane su u više metoda u QUADPACK biblioteci.

Konzervativna (a priori) procjena greške

Ako se dopusti da f ima ograničen prvi izvod na zatvorenom intervalu [a,b]. Teorema srednje vrednosti za f, gde je x < b, daje:

$(x-a)f'(v_{x})=f(x)-f(a)\,$

za neke v_x iz intervala [a,x] zavisne od x. Ako se integriše po x od a do b na obe strane i uzmu apsolutne vrednosti, dobije se:

$\left|\int _{a}^{b}f(x)\,dx-(b-a)f(a)\right|=\left|\int _{a}^{b}(x-a)f'(v_{x})\,dx\right|$ (*)

Može se dalje aproksimirati integral na desnoj strani nejednakosti ubacujući apsolutnu vrednost u integrand i smenom slova u f' prema gornjoj granici:

$\left|\int _{a}^{b}f(x)\,dx-(b-a)f(a)\right|\leq {(b-a)^{2} \over 2}\sup _{a\leq x\leq b}\left|f'(x)\right|$ (**)

Ako se aproksimira integral ∫_a^b f(x) dx sa kvadraturnim pravilom (b − a)f(a), greška nije veća od one na desnoj strani kod (**). Ovo se može pretvoriti u analizu greške za Rimannovu sumu (*), davajući gornju granicu od

${n^{-1} \over 2}\sup _{0\leq x\leq 1}\left|f'(x)\right|$

za izražavanje greške od određene aproksimacije. (Komentar: U ovom primeru je ovo greška koja je izračunata za primer $f(x)=x$.) Koristeći više izvoda i popravljanja kvadrature može se dobiti ista greška analize koristeći se Taylorovim redovima (koristeći parcijalnu sumu sa ostatkom) za f. Ova analiza greške daje striktnu gornju granicu greške ako postoje izvodi za f.

Ova metoda integracije može biti kombinovana sa aritmetikom intervala da kreira računarski dokaz i verificirane proračune.

Integrali sa beskonačnim intervalima

Postoji nekoliko metoda za aproksimaciju integracije kod neograničenih intervala. Uobičajena tehnika uključuje posebno izvedena kvadraturna pravila, poput Gaus-Hermitove kvadratura za integrale na čitavoj liniji realnih brojeva i Gaus-Lagerove kvadrature za integrale na pozitivnim realnim brojevima. Monte Karlove metode mogu takođe biti korištene, ili menjanjem promenljivih na konačan interval. To se može predstaviti ovako za neograničene intervale s obe strane:

$\int _{-\infty }^{+\infty }f(x)\,dx=\int _{-1}^{+1}f\left({\frac {t}{1-t^{2}}}\right){\frac {1+t^{2}}{(1-t^{2})^{2}}}\,dt,$

ili polu-beskonačne intervale:

$\int _{a}^{+\infty }f(x)\,dx=\int _{0}^{1}f\left(a+{\frac {t}{1-t}}\right){\frac {dt}{(1-t)^{2}}}$

$\int _{-\infty }^{a}f(x)\,dx=\int _{0}^{1}f\left(a-{\frac {1-t}{t}}\right){\frac {dt}{t^{2}}}$

kao moguće transformacije.

Višedimenzioni integrali

Kvadraturna pravila koja su razmatrana dosad su pravljena s ciljem primene na jednodimenzione integrale. Za računanje istih u više dimenzija, jedan pristup je izraziti višestruki integral kao ponovljeni jednodimenzioni integral koristeći se Fubinijevom teoremom. Ovaj pristup traži funkcijske proračune da rastu eksponencijalno kako se povećava broj dimenzija. Dve metode su poznate za postizanje ovoga tzv. prokletstva dimenzionalnosti.

Monte Karlo

Metode Monte Karla i kvazi metode istog su jednostavne za primenu na višedimenzionim integralima i mogu ostvariti veću preciznost za isti broj od proračuna funkcija nego metodom ponovljenih integracija koristeći se jednodimenzionim metodama.

Veliki broj korisnih Monte Karlo metoda su tzv. Markov lanac za Monte Karlo algoritme, koji sadrže Metropolis-Hejstings algoritam i Gibsovo uzimanje uzorka.

Literatura

• Philip J. Davis and Philip Rabinowitz, Methods of Numerical Integration.
• George E. Forsythe, Michael A. Malcolm, and Cleve B. Moler, Computer Methods for Mathematical Computations. Englewood Cliffs, NJ: Prentice-Hall, 1977. (See Chapter 5.)
• Press, W.H.; Teukolsky, S.A.; Vetterling, W.T.; Flannery, B.P. (2007), „Chapter 4. Integration of Functions”, Numerical Recipes: The Art of Scientific Computing (3rd изд.), New York: Cambridge University Press, ISBN 978-0-521-88068-8 
• Josef Stoer and Roland Bulirsch, Introduction to Numerical Analysis. New York: Springer-Verlag, 1980. (See Chapter 3.)
• Boyer, C. B., A History of Mathematics, 2nd ed. rev. by Uta C. Merzbach, New York: Wiley, 1989 ISBN 0-471-09763-2 (1991 pbk ed. ISBN 0-471-54397-7).
• Eves, Howard, An Introduction to the History of Mathematics, Saunders, 1990, ISBN 0-03-029558-0,

Spoljašnje veze

• Integration: Background, Simulations, etc. at Holistic Numerical Methods Institute
• Lobatto Quadrature from Wolfram Mathworld
• Lobatto quadrature formula from Encyclopedia of Mathematics
• Implementations of many quadrature and cubature formulae within the free Tracker Component Library.