Numerička integracija — разлика између измена
Садржај обрисан Садржај додат
м Dcirovic преместио је страницу Нумеричка интеграција на Numerička integracija без остављања преусмерења: . |
. |
||
Ред 1:
[[Datoteka:Integral as region under curve.svg|thumb|220px|Numerička integracija se sastoji od traženja numeričke aproksimacije za neku vrednost S]]
U [[Numerička analiza|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 [[Diferencijalna jednačina|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''',<ref>{{MathWorld | urlname=Cubature | title=Cubature }}</ref> iako se izrazom ''kvadratura ''podrazumeva i višedimenziona integracija.
Osnovni problem u numeričkoj integraciji je izračunavanje približne vrednosti određenog integrala:
:<math>I=\int_a^b\! f(x)\, dx</math>
sa zadatim stepenom tačnosti. Ako je {{math|''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 [[interpolacioni polinomi|interpolacionih polinoma]]. Npr. ukoliko se želi da se nađe neki [[određeni integral]], može se poslužiti [[Njutn-Lajbnicova formula|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 ==
{{main-lat|Kvadratura (matematika)}}
{{L|rut}}
'''Kvadratura '''je matematički historijski pojam, a znači računanje površine. Kvadraturni problemi su bili glavni zadaci koji su zadavani kao izvor za [[Matematička analiza|matematičku analizu]].<ref>{{cite web|url=http://jeff560.tripod.com/q.html|title=Earliest Known Uses of Some of the Words of Mathematics (Q)|author=|date=|website=jeff560.tripod.com|accessdate=31 March 2018}}</ref> Matematičari [[Stara Grčka|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 zašto je proces nazvan '''kvadratura'''. Naprimjer: kvadratura kruga, hipokratov mjesec i kvadratura parabole. Ova konstrukcija mora biti izvedena jedino upotrebom šestara i lenjira.
[[Datoteka:Mitjana geomètrica amb teorema de l'altura.PNG|thumb|left|220px|Stara metoda traženja [[Geometrijska sredina|geometrijske sredine]]]]
Za kvadraturu pravougaonika sa stranicama ''a'' i ''b'' potrebno je konstruisati kvadrat sa stranicom: <math>x =\sqrt {ab}</math>
U ovu svrhu, moguće je koristiti sljedeć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 rješava problem kvadrature paralelograma i trougla.
[[Datoteka:Parabola and inscribed triangle.svg|thumb|200px|<p>Površina segmenta parabole</p>]]
Problemi kvadrature za krivolinijske figure su mnogo komplikovaniji. Kvadratura jednog kruga sa šestarom i lenjirom je bila dokazana u 19. vijeku kao nemoguća. Ipak, za neke oblike (naprimjer hipokratov mjesec) kvadratura se može obaviti. Kvadrature sferične površine i dijela parabole urađena od strane [[Arhimed]]<nowiki/>a je postao najveći uspjeh u antičkoj analizi.
* Površina lopte je jednaka četverostrukoj površini velikog kruga ove lopte.
* Površina dijela parabole odsječena pravcem je 4/3 površine od trougla koji je upisan u ovaj segment.
Za dokaz rezultata, Arhimed je koristio metodu Eudoksa.
U srednjovjekovnoj Evropi, kvadratura je značila proračun površine koristeći bilo koju metodu. Češće je metoda nedjeljivosti korištena; manje je rigorozna, a jednostavnija i dobra. Pomoću nje, [[Galileo Galilei]] i [[Gilles de Roberval]] su našli površinu svoda cikloide, [[Grégoire de Saint-Vincent]] je istražio površinu ispod hiperbole (''Opus Geometricum'', [[1647.]]), a [[Alphonse Antonio de Sarasa]], de Saint-Vincentov učenik i komentator, je uspostavio relaciju ove površine sa logaritmima.
[[John Wallis]] je "algebrizirao" ovaj metod: napisao je u svojim ''Arithmetica Infinitorum'' (1656.) serijama ono što se danas zove određenim integralom, te izračunao njihove vrijednosti. [[Isaac Barrow]] i [[James Gregory (mathematician)|James Gregory]] su napravili dalji napredak: kvadrature za neke algebarske krivulje i spirale. [[Christiaan Huygens]] je uspješno izveo kvadrature nekih "materijala revolucije".
Kvadratura hiperbole od strane Saint-Vincent i de Sarasa-e je ustupila novu funkciju, [[prirodni logaritam]], od kritičnog značaja.
Sa otkrićem integralnog računa došla je univerzalna metoda za računanje površine. Kao odgovor, termin '''kvadratura''' je postao tradicionalan, a umjesto toga 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 mjestima, što se radi uzimanjem uzorka. Neki super računari i ostale računarske aplikacije nekad trebaju numeričku integraciju baš radi ovog 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''<sup>''2''</sup>), antiderivacija koja 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 (anti-izvod). Ovo može biti korišteno ako je antiderivacija data kao neograničeni niz proizvoda, ili ako bi proračun zahtjevao specijalne funkcije koje nisu dostupne računarima.
== Metode za jednodimenzione integrale ==
Metode numeričke integracije se mogu generalno opisati kao kombinacije procjena integranda (funkcije) da se dobije aproksimacija integrala. Integrand je definisan kao konačan skup tačaka nazivanih '''integracione tačke''' i zbir ovih vrijednosti 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 dio analize bilo koje numeričke integracione metode je proučavanje ponašanja greške aproksimacije kao funkcija broja procjene integranda. Metoda koja ima malu grešku za mali broj procjena je često smatrana superiornom. Smanjenjem broja procjena integranda, smanjuje se i broj korištenih aritmetičkih operacija, te se smanjuje ukupna greška proračuna. Takođe, svaka procjena uzima vrijeme, a integrand može biti svojevoljno komplikovan.
''Brute force'' metoda ("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 procjenom 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.
[[Datoteka:Integration rectangle.svg|thumb|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''.
:<math>\int_a^b f(x)\,dx \approx (b-a) \, f\left(\frac{a+b}{2}\right)</math>
[[Datoteka:Integration trapezoid.svg|thumb|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 ''[[trapezno pravilo]]''.
:<math>\int_a^b f(x)\,dx \approx (b-a) \, \frac{f(a) + f(b)}{2}.</math>
[[Datoteka:Integration simpson.png|thumb|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''. Naprimjer, kompozitno trapezno pravilo ima slijedeći oblik:
:<math>\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)</math>
gdje podintervali imaju oblik [''k'' ''h'', (''k''+1) ''h''], sa ''h'' = (''b''−''a'')/''n'' i ''k'' = 0, 1, 2, ..., ''n''−1.
Interpolacija sa polinomima procijenjena sa tačkama sa jednakim rastojanjima u zatvorenom sektoru [''a'', ''b''] se radi ''[[Newton-Cotesove formule|Newton-Cotesovim formulama]]'' (njutn-kotes), od koje su primjeri trapezno i kvadratno pravilo. Simpsonovo pravilo, koje se bazira na polinomima drugog reda, je također Newton-Cotesova formula.
Kvadraturna pravila sa jednako razmaknutim tačkama imaju veoma pogodnu osobinu ''gniježđenja''. Odgovarajuće pravilo sa svakim podpodijeljenim intervalom sadrži sve trenutne tačke, pa ove vrijednosti 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 Newton-Cotesovog pravila koje zahtjeva jednak broj iteracija ako je funkcija koja se integriše (integrand) glatka krivulja (npr, ako je dovoljno diferencijabilna). Ostale kvadraturne metode sa varijacijom intervala uključuju Clenshaw–Curtis kvadraturne metode (također zvane Fejér kvarature), koje se gnijezde.
Gausova kvadraturna pravila nemaju osobinu gniježđenja, ali Gauss–Kronrod 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:
<syntaxhighlight lang="python">
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
</syntaxhighlight>
Neki detalji algoritma zahtjevaju pažljiv pristup. Za više slučajeva, pronalazak greške kvadrature na intervalu za funkciju ''f''(''x'') nije očita. Jedna poznata solucija je da se koriste dva pravila kvadratura i korištenjem razlike se može procijeniti greška kvadrature. Čest problem je odlučiti šta označava "premalo" ili "preveliko". Lokalni kriterij za "preveliko" je da kvadraturna greška ne smije biti veća od ''t'' · ''h,'' gdje je ''t,'' realni broj, tolerancija koja se želi podesiti za globalnu grešku. Opet, ako je ''h'' već malo, onda može biti bespotrebno praviti ga čak manjim iako je kvadraturna greška velika. Globalni kriterij 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 procjene računa i greška.
=== Metoda ekstrapolacije ===
Preciznost kvadraturnog pravila kod Newton-Cotes 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 nula. Ovo se može odgovoriti ekstrapolacijom rezultata od dva do ''n'' razmaka koristeći ubrzavajuće metode kao npr. Richardsonove ekstrapolacije. Ekstrapolaciona funkcija može biti polinom ili racionalna funkcija. Ekstrapolacione metode su opisanje detaljnije u od strane Stoera i Bulirscha (Sekcija 3.4) i implementirane su u više metoda u [[QUADPACK]] biblioteci.
=== Konzervativna (a priori) procjena greške ===
Ako se pusti da ''f'' ima ograničen prvi izvod na zatvorenom intervalu [''a'',''b'']. Teorema srednje vrijednosti za ''f'', gdje je ''x'' < ''b'', daje:
: <math>(x - a) f'(v_x) = f(x) - f(a)\,</math>
za neke ''v<sub>x</sub>'' iz intervala [''a'',''x''] zavisne od ''x''. Ako se integriše po ''x'' od ''a'' do ''b'' na obje strane i uzmu apsolutne vrijednosti, dobije se:
: <math>\left| \int_a^b f(x)\,dx - (b - a) f(a) \right|
= \left| \int_a^b (x - a) f'(v_x)\, dx \right|</math> (*)
Može se dalje aproksimirati integral na desnoj strani nejednakosti ubacujući apsolutnu vrijednost u integrand i smjenom slova u ''f' '' prema gornjoj granici:
: <math>\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|</math> (**)
Ako aproksimiramo integral '''∫<sub>''a''</sub><sup>''b''</sup> ''f''(''x'') d''x''''' sa kvadraturnim pravilom (''b'' − ''a'')''f''(''a''), naša greška nije veća od one na desnoj strani kod (**). Ovo se može pretvoriti u analizu greške za Riemannovu sumu (*), davajući gornju granicu od
: <math>{n^{-1} \over 2} \sup_{0 \leq x \leq 1} \left| f'(x) \right|</math>
za izražavanje greške od određene aproksimacije. (Komentar: U ovom primjeru je ovo greška koja je izračunata za primjer <math>f(x) = x</math>.) Koristeći više izvoda i popravljanja kvadrature može se dobiti ista greška analize koristeći se [[Taylorov red|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 Gauss-Hermite kvadratura za integrale na čitavoj liniji realnih brojeva i Gauss-Laguerre kvadrature za integrale na pozitivnim realnim brojevima.<ref>{{cite book |last=Leader |first=Jeffery J. | authorlink=Jeffery J. Leader| title=Numerical Analysis and Scientific Computation |year=2004 |publisher=Addison Wesley |location= |isbn= 0-201-73499-0}}</ref> Monte Carlo metode mogu također biti korištene, ili mijenjanjem promjenljivih na konačan interval. To se može predstaviti ovako za neograničene intervale s obje strane:
:<math>
\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,
</math>
ili polu-beskonačne intervale:
:<math>
\int_a^{+\infty}f(x) \, dx =\int_0^1 f\left(a + \frac{t}{1-t}\right) \frac{dt}{(1-t)^2} </math>
:<math>
\int_{-\infty}^a f(x) \, dx = \int_0^1 f\left(a - \frac{1-t}{t}\right) \frac{dt}{t^2}</math>
kao moguće transformacije.
== Višedimenzioni integrali ==
Kvadraturna pravila su koja su razmatrana dosad su pravljena s ciljem da računaju 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. Dvije metode su poznate za postizanje ovoga tzv. ''prokletstva dimenzionalnosti''.
=== Monte Karlo ===
Metode Monte Carla i kvazi metode istog su jednostavne za koristiti na višedimenzionim integralima i mogu dobivati veću preciznost za isti broj od proračuna funkcija nego metodom ponovljenih integracija koristeći se jednodimenzionim metodama.
Veliki broj korisnih Monte Carlo metoda su tzv. Markov lanac za Monte Carlo algoritme, koji sadrže Metropolis-Hastings algoritam i Gibbsovo uzimanje uzorka.
==Reference ==
{{reflist|}}
== Literatura ==
{{refbegin|30em}}
* [[Philip J. Davis]] and [[Philip Rabinowitz (mathematician)|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.)''
* {{Citation |last1=[[William H. Press|Press]]|first1=W.H.|last2=[[Saul Teukolsky|Teukolsky]]|first2=S.A.|last3=Vetterling|first3=W.T.|last4=Flannery|first4=B.P.|year=2007|title=Numerical Recipes: The Art of Scientific Computing|edition=3rd|publisher=Cambridge University Press| location=New York|isbn=978-0-521-88068-8|chapter=Chapter 4. Integration of Functions|chapter-url=http://apps.nrbook.com/empanel/index.html?pg=155}}
* [[Josef Stoer]] and [[Roland Bulirsch]], ''Introduction to Numerical Analysis''. New York: Springer-Verlag, 1980. ''(See Chapter 3.)''
* [[Carl Benjamin Boyer|Boyer, C. B.]], ''A History of Mathematics'', 2nd ed. rev. by [[Uta Merzbach|Uta C. Merzbach]], New York: Wiley, 1989 {{isbn|0-471-09763-2}} (1991 pbk ed. {{isbn|0-471-54397-7}}).
* [[Howard Eves|Eves, Howard]], ''An Introduction to the History of Mathematics'', Saunders, 1990, {{isbn|0-03-029558-0}},
{{refend}}
== Spoljašnje veze ==
{{Commonscat-lat|Numerical Integration}}
* [http://numericalmethods.eng.usf.edu/mws/gen/07int/index.html Integration: Background, Simulations, etc.] at Holistic Numerical Methods Institute
* [http://mathworld.wolfram.com/LobattoQuadrature.html Lobatto Quadrature] from Wolfram Mathworld
* [https://www.encyclopediaofmath.org/index.php/Lobatto_quadrature_formula Lobatto quadrature formula] from Encyclopedia of Mathematics
* [https://github.com/USNavalResearchLaboratory/TrackerComponentLibrary/tree/master/Mathematical%20Functions/Numerical%20Integration/Cubature%20Points Implementations of many quadrature and cubature formulae] within the free [[Tracker Component Library]].
{{Authority control-lat}}
[[Категорија:Нумеричка анализа]]
| |||