Numerička analiza

Vavilonska glinena pločica (c. 1800–1600 p.n.e.) sa anotacijama. Aproksimacija kvadratnog korena iz 2 sa četiri šezdesetne cifre, koje su oko šest decimalnih cifara. 1 + 24/60 + 51/60² + 10/60³ = 1.41421296...

Numerička analiza je grana numeričke matematike koja se bavi pronalaženjem i unapređivanjem algoritama za numeričko izračunavanje vrijednosti vezanih uz matematičku analizu, poput numeričkog integriranja, numeričkog deriviranja i numeričkog rješavanja diferencijalnih jednadžbi. Sastavni dio numeričke analize je i ocjenjivanje grešaka metoda (algoritama) i to na dvije razine—analiza grešaka same metode, te analiza grešaka koje nastaju izvrednjavanjem, a vezane su uz arhitekturu računala .

Potrebe za numeričkim rješavanjem matematičkih problema su višestruke. Kod nekih problema, dokazano je da analitičko rješenje (rješenje zapisano pomoću elementarnih funkcija) ne postoji—primjerice rješenje integrala $\int e^{x^{2}}\,dx$ nemoguće je zapisati pomoću elementarnih funkcija. Pa ipak, određeni integral $\int _{a}^{b}e^{x^{2}}\,dx$ predstavlja konkretnu, jedinstveno određenu površinu. Do te vrijednosti, koja ima široku upotrebu npr. u statistici, moguće je doći samo numeričkim metodama. Osim toga, numeričke metode često se koriste za određivanje rješenja matematičkih problema koji bi zbog svoje veličine, kroz standardni postupak rješavanja, predugo trajali—primjerice, kada je potrebno riješiti sustav od 10 000 jednadžbi s 10 000 nepoznanica. I konačno, numeričke metode su nezaobilazne u aproksimativnom računu, kada se aproksimacijama (i ocjenama pripadnih grešaka) zamjenjuje stvarna vrijednost funkcije do koje je nemoguće ili preteško doći. To su metode poput metode konačnih elemenata ili pak kubičnih splineova kojima se aproksimira ponašanje nepoznate funkcije o kojoj znamo tek konačan broj vrijednosti, najčešće dobijenih mjerenjima.

Opšti uvod

Sveukupni cilj polja numeričke analize je razvoj i analiza tehnika koje daju aproksimativna ali precizna rešenja teških problema. Njihova raznovrstnost je sumirana sledećim pregledom:

• Napredni numerički metodi su esencijalni u omogućavanju numeričkih metereoloških predviđanja.
• Proračunavanje putanje svemirske letilice se vrši putem numeričkog rešavanja sistema običnih diferencijalnih jednačina.
• Automobilske kompanije mogu da poprave bezbednost vozila koristeće računarske simulacije automobilskih udesa. Takve simulacije se esencijalno sastoje od numeričkog rešavanja parcijalnih diferencijalnih jednačina.
• Hedž fondovi (privatni investicioni fondovi) koriste oruđa iz svih polja numeričke analize u proračunima vrednosti akcija i derivata.
• Aviokompanije koriste sofisticirane optimizacione algoritme u određivanju ceni karti, raspodele aviona i posade, i potrebe za gorivom. Istorijski, takvi algoritmi su razvijeni u okviru preklapajućeg polja operacionih istraživanja.
• Družtva za osiguranje koriste numeričke programe za aktuarne analize.

Ostatak ove sekcije razmatra nekoliko važnih tema numeričke analize.

Istorija

Polje numeričke analize prethodi razvoju modernih računara za par milenijuma. Linearna interpolacija je bila u upotrebi pre više od 2000 godina. Mnogi veliki matematičari su se bavili numeričkom analizom, kao što sledi iz imena važnih algoritama, kao što su Njutnov metod, Lagranžov interpolacioni polinom, Gausova eliminacija, ili Ojlerov method.

Da bi se omogućili ručni proračuni, proizvedene su velike knjige sa formulama i tabelama podataka kao što su interpolacione tačke i koeficijenti funkcija. Koristeći te tabele, koje su često računate sa 16 decimalnih mesta ili više za pojedine funkcije, mogle su se naći vrednosti za uključivanje u formule i tim putem su se mogle ostvariti veoma dobre numeričke procene nekih funkcija. Kanonički rad u polju je NIST publikacija koji su uredili Abramowitz and Stegun. To je knjiga sa više od 1000 strana, u kojoj je obrađen veoma veliki broj ćesto korišćenih formula i funkcija i njihove vrednosti u mnogim tačkama. Štampane vrednosti funkcija više nisu od velike koristi jer su dostupni računari, mada su veliki spiskovi formula još uvek podesni za upotrebu.

Mehanički računar je razvijen kao oruđe za ručno računanje. Ti kalkulatori su evoluirali u elektronske računare tokom 1940-tih, i nakon toga je uočeno da su takvi računari isto tako korisni za administrativne svrhe. Izum računara je takođe uticao na polje numeričke analize, pošto su se sad mogli vršiti duži i kompkovaniji proračuni.

Direktni i iterativni metodi

Direktni vs iterativni metodi Razmotrimo problem rešavanja 3x3 + 4 = 28 za nepoznatu promenljivu x. Direktni metod 3x3 + 4 = 28. Oduzmi 4 3x3 = 24. Podeli sa 3 x3 = 8. Uradi kubni koren x = 2. Za iterativni metod, primeni bisekcioni metod na f(x) = 3x3 − 24. Inicijalne vrednosti su a = 0, b = 3, f(a) = −24, f(b) = 57. Iterativni metod a b mid f(mid) 0 3 1.5 −13.875 1.5 3 2.25 10.17... 1.5 2.25 1.875 −4.22... 1.875 2.25 2.0625 2.32... Iz ove tabele zaključujemo da je rešenje između 1,875 i 2,0625. Algoritam može da vrati bilo koji broj u tom opsegu sa greškom manjom od 0,2. Diskretizacija i numerička integracija Tokom dvočasovne trke smo izmerili brzinu kola tri puta, i zapisali smo merenja u sledećoj tabeli. Vreme 0:20 1:00 1:40 km/h 140 150 180 Diskretizacija bi bila da se kaže da je brzina kola bila konstantna od 0:00 do 0:40, zatim od 0:40 do 1:20 i konačno od 1:20 do 2:00. Na primer, totalno rastojanje pređeno u prvih 40 minuta je aproksimativno (2/3h &puta; 140 km/h) = 93.3 km. To bi nam omogučilo da procenimo totalno pređeno rastojanje kao 93.3 km + 100 km + 120 km = 313.3 km, što je primer numeričke integracije (vidite ispod) koristeći Rimanovu sumu, pošto je rastojanje integral brzine. Nestabilan problem: Uzmimo funkciju f(x) = 1/(x − 1). Uočimo da f(1,1) = 10 i f(1,001) = 1000: promena x od manje od 0,1 odgovara promeni f(x) od skoro 1000. Evaluacija f(x) u blizini x = 1 je nestabilni problem. Stabilan problem: U kontrastu s tim evaluacija iste funkcije f(x) = 1/(x − 1) u blizini x = 10 je stabilan problem. Na primer, f(10) = 1/9 ≈ 0,111 i f(11) = 0,1: skromna promena x dovodi do skromne promene f(x).

Direktni metodi računaju rešenja problema u konačnom broju koraka. Ti metodi bi dali precizan odgovor, kad bi se izvodili aritmetikom beskonačne preciznosti. Primeri obuhvataju Gausovu eliminaciju, metod QR faktorizacije za rešavanje sistema linearnih jednačina, i simpleks metod linearnog programiranja. U praksi se koristi konačna preciznost i rezultat je aproksimacija istinskog rešenja (podrazumevajući stabilnost).

U kontrastu sa direktnim metodima, od iterativnih metoda se ne očekuje da završe u konačnom broju koraka. Počevši od inicijalne pretpostavke, iterativni metodi formiraju sukcesivne aproksimacije koje konvergiraju do preciznog rešenja jedino u limitu. Test konvergencije, koji obično obuhvata ostatak, se specificira da bi se odredilo kad je dovoljno precizno rešenje nađeno. Čak kad bi se koristila i aritmetika beskonačne preciznosti ovi metodi (generalno) ne bi dostigli rešenje u konačnom broju koraka. Primeri obuhvataju Njutnov metod, bisekcioni metod, i Jakobijevu iteraciju. U računarskoj matričnoj algebri, iterativni metodi su generalno neophodni za velike probleme.

Iterativni metodi se češće sreću od direktnih u numeričkoj analizi. Neki metodi su direktni u principu, ali se obično koriste kao da nisu, e.g. GMRES i metod konjugovanog gradijenta. Za te metode broj koraka koji su neophodni da bi dobilo precizno rešenje je toliko veliki da se aproksimacija prihvata u istom maniru kao kod iterativnog metoda.

Diskretizacija

Kontinualni problemi se ponekad moraju zameniti diskretnim problemima čije rešenje je poznato da bi se aproksimiralo rešenje kontinualnog problema; taj proces se naziva diskretizacijom. Na primer, rešenje diferencijalne jednačine je funkcija. Ta funkcija se mora zameniti konačnom količinom podataka, na primer njenom vrednošću u konačnom broju tačaka njenog domena, mada je taj domen kontinuum.

Generacija i propagacija grešaka

Izučavanje grešaka sačinjava važan deo numeričke analize. Postoji nekoliko načina na koji se može uneti greška u rešenje problema.

Zaokruživanje

Greške zaokruživanja nastaju zato što je nemoguće precizno predstaviti sve realne brojeve na mašini sa konačnom memorijom (što je slučaj sa praktično svim digitalnim računarima).

Skraćivanje i greške diskretizacije

Greške skraćivanja nastaju kad se iterativni metod završi ili kad se matematička procedura aproksimira, i približno rešenje se razlikuje od tačnog rešenja. Slično tome, diskretizacija unosi grešku diskretizacije zato što se rešenje diskretnog problema ne poklapa sa rešenjem kontinualnog problema. Na primer, u iteraciji prikazanoj na desnoj strani da bi se izračunalo rešenje jednačine $''3x^{3}+4=28''$, nakon 10 ili više iteracija, zaključuje se (na primer) da je koren oko 1,99. Stoga imamo grešku skraćivanja od 0,01.

Nakon generisanja greške, ona se generalno uvećava tokom proračuna. Na primer, već smo napomenuli da operacija + na kalkulatoru (ili računaru) nije precizna. Iz toga sledi da je sabiranje tipa a+b+c+d+e još nepreciznije.

Gore je pomenuto da dolazi do greške skraćivanja, kad se aproksimira matematička procedura. Poznato je da je za preciznu integraciju funkcije neophodno naći zbir beskonačno velikog broja trapezoida. U praksi se međutim može odrediti jedino zbir konačnog broja trapezoida, i stoga dolazi do aproksimacije matematičke procedure. Slično tome, da bi se diferencirala funkcija, diferencijalni element treba da teži nuli, dok je numerički moguće jedino izabrati konačnu vrednost diferencijalnog elementa.

Numerička stabilnost i dobro postulirani problemi

Numerička stabilnost je važan pojam u numeričkoj analizi. Algoritam se smatra numerički stabilnim ako se greška, nezavisno od izvora, znatno ne uvećava tokom proračuna. Do toga dolazi ako je problem stabilan, što znači da se rešenje malo menja sa malom promenom ulaznih podataka. U kontrastu s tim, ako je problem nestabilan, onda svaka mala greška u ulaznim podacima narasta u veliku grešku u rešenju.

Originalni problem i algoritam koji se koriste za rešavanje problema mogu da budu stabilni i/ili nestabilni, ili bilo koja kombinacija. Stoga algoritam koji rešava stabilni problem može da bude bilo numerički stabilan ili numerički nestabilan. Umetnost numeričke analize je da se nađe stabilan algoritam za rešavanje dobro postavljenog matematičkog problema. Na primer, izračunavanje kvadratnog korena iz 2 (koji je oko 1,41421) je stabilan problem. Mnogi algoritmi rešavaju taj problem počevši od inicijalne aproksimacije x₁ od ${\sqrt {2}}$, na primer x₁=1,4, i zatim izračunavaju poboljšanje pretpostavke x₂, x₃, etc.. Jedan takav metod je poznati Vavilonski metod, koji je dat sa x_k+1 = x_k/2 + 1/x_k. Još jedan iterativni pristup, koji ćemo zvati Metod X, je dat sa x_{k + 1} = (x_k²−2)² + x_k. Izračunali smo nekoliko iteracija ovog algoritma u donjoj tabeli, sa inicijalnim pretpostavkama x₁ = 1,4 i x₁ = 1,42.

Vavilonski metod	Vavilonski metod	Metod X	Metod X
x1 = 1.4	x1 = 1.42	x1 = 1.4	x1 = 1.42
x2 = 1.4142857...	x2 = 1.41422535...	x2 = 1.4016	x2 = 1.42026896
x3 = 1.414213564...	x3 = 1.41421356242...	x3 = 1.4028614...	x3 = 1.42056...
		...	...
		x1000000 = 1.41421...	x28 = 7280.2284...

Može se uočiti da Vaviloniski metod brzo konvergira nezavisno od inicijalne pretpostavke, dok Metod X konvergira ekstremno sporo sa inicijalnom pretpostavkom od 1,4 i divergira počevši od inicijalne pretpostavke 1,42. Stoga je Vavilonski metod numerički stabilan, dok je Metod X numerički nestabilan.

Numerička stabilnost je zavisna od broja značajnih cifara koje data mašina podržava, ako se koristi mašina koja radi sa prve četiri cifre pokretnog zareza dolazi do znatnog gubitka preciznosti

$f(x)=x\left({\sqrt {x+1}}-{\sqrt {x}}\right){\text{ and }}g(x)={\frac {x}{{\sqrt {x+1}}+{\sqrt {x}}}}.$

Ako se uporede rezultati od

$f(500)=500\left({\sqrt {501}}-{\sqrt {500}}\right)=500\left(22.3830-22.3607\right)=500(0.0223)=11.1500$

i

${\begin{alignedat}{3}g(500)&={\frac {500}{{\sqrt {501}}+{\sqrt {500}}}}\\&={\frac {500}{22.3830+22.3607}}\\&={\frac {500}{44.7437}}=11.1748\end{alignedat}}$

uočava se da gubitak značaja, koji se takođe naziva poništavanja oduzimanjem, ima ogromni efekat na rezultate, mada su funkcije ekvivalentne; da bi se pokazalo da su ekvivalentne jednostavno se polazi od f(x) i završava sa g(x), tako da je

${\begin{alignedat}{4}f(x)&=x\left({\sqrt {x+1}}-{\sqrt {x}}\right)\\&=x\left({\sqrt {x+1}}-{\sqrt {x}}\right){\frac {{\sqrt {x+1}}+{\sqrt {x}}}{{\sqrt {x+1}}+{\sqrt {x}}}}\\&=x{\frac {({\sqrt {x+1}})^{2}-({\sqrt {x}})^{2}}{{\sqrt {x+1}}+{\sqrt {x}}}}\\&=x{\frac {x+1-x}{{\sqrt {x+1}}+{\sqrt {x}}}}\\&=x{\frac {1}{{\sqrt {x+1}}+{\sqrt {x}}}}\\&={\frac {x}{{\sqrt {x+1}}+{\sqrt {x}}}}\end{alignedat}}$

Istinska vrednost rezultata je 11,174755..., što je tačno g(500) = 11,1748 nakon zaokruživanja rezultata na 4 decimalna mesta.

Sad zamislimo da se koristi mnoštvo članova kao što su ove funkcije u programu; greške će se uvećavati tokom rada programa, osim ako se koristi podesna formula za ove dve funkcije svaki put kad se izračunavaju f(x), ili g(x); izbor je zavistan od pariteta  x.

• Primer je uzet iz: Mathew; Numerical methods using matlab, 3rd ed.

Oblasti izučavanja

Polje numeričke analize obuhvata mnoštvo potdisciplina. Neke od glavnih su:

Izračunavanje vrednosti funkcija

Interpolacija: Primećeno je da temperatura varira od 20 stepeni Celzijusa u 1:00 do 14 stepeni u 3:00. Linearnom interpolacijom tih podataka se dolazi do zaključka da je bilo 17 stepeni u 2:00 i 18,5 stepeni u 1:30 pm. Ekstrapolacija: Ako je bruto domaći proizvod zemlje prosečno rastao sa 5% godišnje i ako je bio 100 milijarde dolara prošle godine, ekstrapolacijom možemo zaključiti da će biti 105 milijarde dolara ove godine. Linija kroz 20 tačaka Regresija: U linearnoj regresiji, polazeći od n tačka, izračunavamo liniju koja prolazi koliko god je moguće blizo tih n tačaka. Koliko košta čaša limunade? Optimizacija: Recimo da prodajemo limunadu na tezgi, i uočimo da pri ceni $1, možemo da prodamo 197 čaša lemunade na dana, i da za svakih $0,01 povećanja cene, prodaja opada za jednu čašu linumanade na dan. Ako prodajemo po ceni od $1,485, dolazi do maksimizacije profita, ali zbog ograničenja da je neophodno napaćivati celobrojnu cenu, naplaćivanje $1,48 ili $1,49 po čaši će proizvesti maksimalni prihod od $220,52 na dan. Pravac vetra je označen plavom bojom, istinska trajektorija crno, rezultat Ojlerovog metoda crveno. Diferencijalna jednačina: Ako se 100 fanova podesi da duvaju vetar sa jednog kraja sobe na drugu i zatim se pusti pero u vetar, šta se događa? Pero će slediti struju vazduha, koja može da bude veoma kompleksna. Jedna aproksimacija je da se izmeri brzina kojom se duva vazduh u blizini pera u svakoj sekundi, i da se simulisano pomera pero kao da se kreće u pravoj liniji istom brzinom tokom jedne sekunde, pre nego što se ponovo izmeri brzina vetra. To se naziva Ojlerovim metodom rešavanja obične diferencijalne jednačine.

Jedan od najjednostavnijih problema je evaluacija funkcije u datoj tački. Najprostiji pristup unošenja broja u formulu nije uvek veoma efikasan. Za polinome, bolji pristup je korišćenje Hornerove šeme, pošto se time redukuje broj neophodnih množenja i sabiranja. Generalno je važno da se proceni i kontroliše greška zaokruživanja koja nastaje pri upotrebi aritmentike pokretnog zareza.

Interpolacija, ekstrapolacija, i regresija

Interpolacija rešava sledeći problem: polazeći od vrednosti neke nepoznate funkcije u više tačaka, koju će vrednost ta funkcija imati u nekoj drugoj tački između poznatih tačaka?

Ekstrapolacija je veoma slična interpolaciji, izuzev da je ovde cilj da se nađe vrednost nepoznate funkcije u tački koja je izvan opsega poznatih tačaka.

Regresija je takođe slična, izuzev da uzima u obzir podatke kao da su neprecizni. Polazeći od datog broja tačaka i izmerenih vrednosti neke funkcije u tim tačkama (sa greškom), cilj je da se odredi nepoznata funkcija. Metod najmanjih kvadrata je jedan od popularnih pristupa regresione analize.

Rešavanje jednačina i sistema jednačina

Još jedan fundamentalni problem je izračunavanje rešenja date jednačine. Dva slučaja se obično razlikuju, u zavisnosti od toga da li je jednačina linearna ili nije. Na primer, jednačina $2x+5=3$ je linearna, dok $2x^{2}+5=3$ nije.

Znatne količine truda su uložene u razvoj metoda za rešavanje sistema linearnih jednačina. Standardni direktni metodi, i.e., metodi koji koriste neku od dekompozicija matrica su Gausova eliminacija, LU dekompozicija, Čoleskijeva dekompozicija za simetrične (ili hermitijanske) ili pozitivno-konačne matrice, i QR dekompozicija za nekvadratne matrice. Iterativni metodi kao što je Jakobijev metod, Gaus-Zajdelova metod, sukcesivna prekomerna relaksacija i metod konjugovanog gradijenta su obično preferentni za velike sisteme. Opšti iterativni metodi se mogu razviti koristići podele matrice.

Algoritmi nalaženja korena se koriste za rešavanje nelinearnih jednačina (oni su tako nazvani zato što je koren funkcije argument za koji je vrednost funkcije nula). Ako je funkcija diferencijabilna i ako su derivati poznati, onda je Njutnov metod popularni izvor. Linearizacija je još jedna tehnika za rešavanje nelinearnih jenačina.

Rešavanje svojstvene vrednositi ili singularne vrednosti problema

Nekoliko važnih problema se može izraziti u obliku dekompozicija svojstvenim vrednostima ili dekompozicija singularne vrednosti. Na primer, algoritam spektralne kompresije slike je baziran na dekompoziciji singularne vredsnosti. Korespondiraći alat u statistici se naziva analiza principalnih komponenti.

Optimizacija

Optimizacioni problemi se bave određivanjem tačke u kojoj dolazi do maksimizacije (minimizacije) date funkcije. Obično ta tačka mora da zadovolji izvesna ograničenja.

Polje optimizacije se dalje deli u nekoliko potpolja, u zavisnosti od forme ciljne funkcije i ograničenja. Na primer, linearno programiranje se bavi sličajem gde su ciljna funkcija i ograničanja linearni. Poznati metod linearnog programiranja je simpleks metod.

Metod Langranžovih množioca se može koristiti za redukovanje optimizacionih problema sa ograničenjima do optimizacionih problema bez ograničenja.

Diferencijalne jednačine

Numerička analiza se isto tako bavi izračunavanjem (na aproksimativan način) rešenja diferencijalnih jednačina, običnih diferencijalnih jednačina i parcijalnih diferencijalnih jednačina.

Parcijalne differencijalne jednačine se rešavaju tako što se prvo diskretizuje jednačina, čime se dovodi u konačno-dimenzioni potprostor. To se može uraditi metodom konačinih elemenata, metodom konačnih razlika, ili (posebno u inženjerstvu) metodom konačnih zapremina. Teoretska zaleđina tih metoda obično obuhvata teoreme funkcione analize. Time se redukuje problem do rešavanja algebraske jednačine.

Softver

Od kasnog dvadesetog veka, većina algoritama je implementirana u više različitih programskih jezika. Netlib repozitorija sadrži razne kolekcije softverskih rutina za numeričke probleme, uglavnom u jezicima Fortran i C. Proizvodi u prodaji sadrže implementacije mnoštva različitih numeričkih algoritama uključujući IMSL u NAG biblioteke; slobodna alternativa je GNU naučna biblioteka.

Postoji nekoliko popularnih numeričkih računarskih aplikacija, kao što su MATLAB, TK Solver, S-PLUS, LabVIEW, i IDL, kao i alternative besplatnog i otvorenog izvornog koda: FreeMat, Scilab, GNU Octave (slično Matlabu), IT++ (C++ biblioteka), R (slično sa S-PLUS) i pojedine varijante Python jezika. Performance znatno variraju: dok su vektorske i matrične operacije obično brze, skalarne petlje mogu da variraju po brzini za više od jednog reda veličine.

Mnogi računarski algebarski sistemi, kao što je Mathematica, takođe koriste dostupnost arbitrane aritmetičke preciznosti koja može da omogući tačnije rezultate.

Softver za elektronske tabele (npr. Excel) isto tako može da se koristi za rešavanje jednostavnih problema iz polja numeričke analize.

Numeričko integriranje

Površina ispod funkcije f(x) (označene plavom) aproksimira se površinom trapeza ispod po dijelovima linearne aproksimacije (označene crvenom).

Jedan od najčešćih problema s kojima se susrećemo u numeričkoj analizi je računanje vrijednosti određenog integrala: $\int _{a}^{b}f(x)\,dx$. Numerička integracija je u nekim okolnostima poznata kao numerička kvadratura. Popularne metode koriste jednu od Njutn–Koutsovih formula (poput pravila srednje tačke ili Simpsonovog pravila) ili Gausove kvadrature. Te metode se oslanjaju na strategiju „podeli i pokori“, tako što se integral na relativno velikom setu podeli u integrale na manjim setovima. U slučajevima velikog broja dimenzija, gde su ti metodi nedopustivo skupi u pogledu računarskih zahteva, pribegava se primeni Monte Karlovog ili kvazi-Monte Karlovog metoda (pogledajte Monte Karlo integracija), ili, kod umereno velikog broja dimenzija, metoda retke mreže.

Dve osnovne metode numeričke integracije su proširena trapezna formula i proširena Simpsonova formula.

Kod proširene trapezne formule, interval integracije [a,b] podijeli se u n podintervala uz slijedeću oznaku: a=x₀<x₁<...<x_n=b. U svim se točkama razdiobe izračunaju vrijednosti podintegralne funkcije y_i=f(x_i), te se nad svakim podintegralom formira trapez spajanjem točaka T_i(x_i,y_i) i T_i+1(x_i+1,y_i+1). Tim se trapezom, čija je površina jednaka P_i=(x_i+1-x_i)(y_i+y_i+1)/2, aproksimira stvarna površina ispod funkcije f(x) na tom intervalu. Uz uobičajen postupak ekvidistantne razdiobe, tj razdiobe intervala na n jednakih podintervala (kod kojeg je x_i+1-x_i=(b-a)/n ), te zbrajanjem površina trapeza konstruiranih nad svim intervalima razdiobe dobijamo trapeznu formulu:

$\int _{a}^{b}f(x)\,dx\,\approx \,{\frac {b-a}{2n}}\cdot (y_{0}+2y_{1}+2y_{2}+\ldots +2y_{n-1}+y_{n})$

Ocjena greške ove numeričke aproksimacije dana je s:

$E(f)=\max _{\xi \in [a,b]}{\frac {(b-a)^{3}}{12n^{2}}}|f''(\xi )|.$

Površina ispod funkcije f(x) (označene plavom) aproksimira se površinom ispod parabole koja interpolira funkciju u tri zadane točke (označene crvenom).

Proširena Simpsonova formula, kao i trapezna formula počinje razdiobom intervala [a,b] na n, ne nužno, jednakih podintervala. No ovoga puta se na svaka dva podintervala, odnosno kroz točke T_i-1(x_i-1,y_i-1), T_i(x_i,y_i) i T_i+1(x_i+1,y_i+1) povlači jedinstveno određena kvadratna funkcija (parabola). Zbog toga kod provođenja Simpsonove formule imamo dodatni zahtjev da je broj podintervala n paran. Računanjem površina ispod tako kontruiranih parabola, te njihovim zbrajanjem dobijamo proširenu Simpsonovu formulu:

$\int _{a}^{b}f(x)\,dx\approx {\frac {b-a}{3n}}{\bigg [}y_{0}+4y_{1}+2y_{2}+4y_{3}y+2y_{4}+\cdots +4y_{n-1}+y_{n}{\bigg ]}.$

Ocena greške proširene Simpsonove formule data je izrazom:

$E(f)=\max _{\xi \in [a,b]}{\frac {(b-a)^{5}}{180n^{4}}}|f^{(4)}(\xi )|.$

Kako u pravilu parabola bolje aprokisimira nasumične funkcije od pravca, Simpsonova formula u pravilu daje tačniji rezultat od trapezne formule.

Numeričko rješavanje diferencijalnih jednadžbi

U numeričku analizu spadaju i metode kojima se traži numeričko aproksimativno rješenje "Cauchyjevog problema"; diferencijalne jednadžbe s zadanim početnim uvjetom. Razvijene su metode za numeričko rješavanje običnih, ali i parcijalnih diferencijalnih jednadžbi. Dvije osnovne metode su Eulerova metoda, i familija Runge-Kutta metoda.

Povezano

• Analiza algoritama
• Naučno računarstvo
• Spisak tema numeričke analize
• Numerička diferencijacija
• Numerički recepti
• Simboličko-numeričko računarstvo

Literatura

• Golub, Gene H. and Charles F. Van Loan (1986). Matrix Computations (3. izd.). Johns Hopkins University Press. ISBN 0-8018-5413-X. 
• Higham, Nicholas J. (1996). Accuracy and Stability of Numerical Algorithms. Society for Industrial and Applied Mathematics. ISBN 0-89871-355-2. 
• Hildebrand, F. B. (1974). Introduction to Numerical Analysis (2nd edition izd.). McGraw-Hill. ISBN 0-07-028761-9. 
• Leader, Jeffery J. (2004). Numerical Analysis and Scientific Computation. Addison Wesley. ISBN 0-201-73499-0. 
• Wilkinson, J.H. (1965). The Algebraic Eigenvalue Problem (Clarendon Press). 
• Kahan, W. (1972). "A survey of error-analysis," in Info. Processing 71 (Proc. IFIP Congress 71 in Ljubljana), vol. 2, pp. 1214–39, North-Holland Publishing, Amsterdam.  (examples of the importance of accurate arithmetic).
• Lloyd N. Trefethen (2006). "Numerical analysis", 20 pages. In: Timothy Gowers and June Barrow-Green (editors), Princeton Companion of Mathematics, Princeton University Press.

Vanjske veze

• Numerische Mathematik, volumes 1-66, Springer, 1959-1994 (searchable; pages are images). (en) (de)
• Numerische Mathematik at SpringerLink Arhivirano 2012-12-08 na Archive.is-u, volumes 1-112, Springer, 1959–2009
• SIAM Journal on Numerical Analysis, volumes 1-47, SIAM, 1964–2009
• Numerical Recipes, William H. Press (free, downloadable previous editions)
• First Steps in Numerical Analysis (internet archivearchived), R.J.Hosking, S.Joe, D.C.Joyce, and J.C.Turner
• CSEP (Computational Science Education Project) Arhivirano 2017-08-01 na Wayback Machine-u, U.S. Department of Energy
• Numerical Methods, Stuart Dalziel University of Cambridge
• Lectures on Numerical Analysis, Dennis Deturck and Herbert S. Wilf University of Pennsylvania
• Numerical methods, John D. Fenton University of Karlsruhe
• Numerical Methods for Science, Technology, Engineering and Mathematics, Autar Kaw University of South Florida
• Numerical Analysis Project, John H. Mathews California State University, Fullerton
• Numerical Methods - Online Course Arhivirano 2007-04-28 na Wayback Machine-u, Aaron Naiman Jerusalem College of Technology
• Numerical Methods for Physicists, Anthony O’Hare Oxford University
• Lectures in Numerical Analysis , R. Radok Mahidol University
• Introduction to Numerical Analysis for Engineering, Henrik Schmidt Massachusetts Institute of Technology
• Numerical Methods for time-dependent Partial Differential Equations Arhivirano 2014-10-26 na Wayback Machine-u, J.W. Haverkort, based on a course by P.A. Zegeling Utrecht_University
• Numerical Analysis for Engineering, D. W. Harder University of Waterloo