Numerička analiza

[desno|mini|250x250piksel| Babilonska glinena ploča [YBC 7289 (oko 1800–1600. pne) s napomenama. Aproksimacija kvadratnog korijena od 2 je četiri seksagezimalne brojke, što otprilike predstavlja broj šest u dekadom sistemu. 1 + 24/60 + 51/60 2 + 10/60 3 = 1,41421296...]]
**Numerička analiza** se bavi proučavanjem algoritama koji koriste numeričku aproksimaciju (nasuprot simboličkih manipulacija) za probleme matematičke analize (za razliku od diskretne matematike). Ona proučava numeričke metode koje pokušavaju pronaći približna, a ne egzaktna  rješenja problema. Numerička analiza nalazi primjenu u svim oblastima inženjerstva i prirodnih nauka, a u 21. stoljeću i u životnim i društvenim naukama, medicini, biznisu, pa čak i umjetnosti. Trenutni rast računarske snage omogućio je upotrebu složenijih numeričkih analiza, pružajući detaljne i realistične matematičke modele u nauci i inženjerstvu. Primjeri numeričke analize uključuju: obične diferencijalne jednačine koje se mogu pronaći u nebeskoj mehanici (predviđanje kretanja planeta, zvijezda i galaksija), numeričku linearnu algebru u analizi podataka, te stohastičke diferencijalne jednačine i Markovljeve lance za simulacije živih ćelija u medicini i biologiji.

Prije modernih računara, numeričke metode su se često oslanjale na ručne interpolacijske formule, koristeći podatke iz velikih štampanih tabela. Od sredine 20. stoljeća, računari su preuzeli izračunavanje potrebnih funkcija, ali mnoge od prethodno korištenih formula i dalje se koriste u softverskim algoritmima.

Numerička tačka gledišta seže do najranijih matematičkih spisa. Ploča iz Babilonske kolekcije Yalea (YBC 7289), daje seksagesimalnu numeričku aproksimaciju kvadratnog korijena od 2, dužine dijagonale jediničnog kvadrata.

Numerička analiza nastavlja ovu dugu tradiciju: umjesto davanja tačnih simboličkih odgovora prevedenih u cifre i primjenjivih samo na mjerenja u stvarnom svijetu, koriste se približna rješenja unutar određenih granica greške.

## Primjene 
Opći cilj polja numeričke analize je dizajn i analiza tehnika za davanje približnih, ali tačnih rješenja za širok spektar teških problema, od kojih je mnoge nemoguće riješiti simbolički:

* Napredne numeričke metode su od suštinske važnosti da bi numeričko predviđanje vremena bilo izvodljivo.
* Izračunavanje putanje svemirskog broda zahtjeva tačno numeričko rješenje sistema običnih diferencijalnih jednačina.
* Automobilske kompanije mogu poboljšati sigurnost svojih vozila u slučaju sudara koristeći računarske simulacije sudara. Takve simulacije se u suštini sastoje od numeričkog rješavanja parcijalnih diferencijalnih jednačina .
* Hedge fondovi (privatni investicioni fondovi) koriste kvantitativne finansijske alate iz numeričke analize kako bi pokušali izračunati vrijednost dionica i derivata preciznije od ostalih učesnika na tržištu.
* Aviokompanije koriste sofisticirane algoritme optimizacije za odlučivanje o cijenama karata, rasporedu aviona i posada, te potrebama za gorivom. Historijski gledano, takvi algoritmi su razvijeni u okviru polja operacionih istraživanja.
* Osiguravajuća društva koriste numeričke programe za aktuarske analize.

## Historija 
Oblast numeričke analize je nastala mnogo stoljeća prije izuma modernih računara. Linearna interpolacija je već bila u upotrebi prije više od 2000 godina. Mnogi veliki matematičari u prošlosti bili su zaokupljeni numeričkom analizom, dok drugi smatraju da moderna numerička analiza počinje s radom E. T. Whittakera iz 1912.
desno|mini|166x166piksel| Publikacija NIST-a
Da bi se olakšalo ručno izračunavanje, napravljene su velike knjige sa formulama i tabelama podataka kao što su interpolacione tačke i koeficijenti funkcija. Koristeći ove tabele, često izračunate do 16 decimala ili više za neke funkcije, mogle su se pronaći vrijednosti koje bi se unosile u date formule i time bi se postigli veoma dobre numeričke procjene nekih funkcija. Kanonski rad u ovoj oblasti je publikacija NIST-a koju su uređivali Abramowitz i Stegun. To je knjiga s više od 1000 stranica s veoma velikim brojem često korištenih formula i funkcija i njihovih vrijednosti u mnogim tačkama. Vrijednosti funkcija više nisu od velike koristi kada je računar dostupan, ali veliki spisak formula i dalje može biti veoma od koristi.

Mehanički kalkulator je također razvijen kao alat za ručno računanje. Ovi kalkulatori su evoluirali u elektronske računare 1940-ih, a zatim je otkriveno da su ovi računari bili korisni i za administrativne svrhe. Ali pronalazak računara uticao je i na oblast numeričke analize,

Iterativne metode se češće koriste u numeričkoj analizi od direktnih metoda. Neke od metoda su u principu direktne, ali se obično koriste kao da nisu, npr. GMRES i metoda konjugovanog gradijenta. Za ove metode broj koraka potrebnih za dobivanje tačnog rješenja je toliko velik da se aproksimacija prihvaća na isti način kao i kod iterativnih metoda.

Kao primjer, razmotrite problem rješavanja

: 3*x*3 + 4 = 28

za nepoznatu veličinu *x*.

Za iterativnu metodu, primijenite metodu bisekcije na *f*(*x*) = 3*x*3 &#x2212; 24. Početne vrijednosti su *a* = 0, *b* = 3, *f*(*a*) = &#x2212;24, *f*(*b*) = 57.

Iz ove tabele se može zaključiti da se rješenje nalazi između 1,875 i 2,0625. Algoritam može dati bilo koji broj u tom rasponu s greškom manjom od 0,2.

### Uslovljavanje 
Loše uslovljen problem: Uzmite funkciju  . Imajte na umu da je *f*(1,1) = 10 i *f*(1,001) = 1000: promjena *x* manja od 0,1 pretvara se u promjenu *f*(*x*) od skoro 1000. Vrednovanje *f*(*x*) blizu *x* = 1 je loše uslovljen problem.

Dobro uslovljen problem: Nasuprot problemu iznad, vrednovanje iste funkcije  blizu *x* = 10 je dobro uslovljen problem. Na primjer, *f*(10) = 1/9 ≈ 0,111 i *f*(11) = 0,1: umjerena promjena u *x* dovodi do umjerene promjene u *f*(*x*).

### Diskretizacija 
Nadalje, kontinuirani problemi ponekad moraju biti zamijenjeni diskretnim problemom za čije rješenje je poznato da je približno rješenju kontinuiranog problema; ovaj proces se naziva *diskretizacija*. Na primjer, rješenje diferencijalne jednačine je funkcija. Ova funkcija mora biti predstavljena konačnom količinom podataka, na primjer njenom vrijednošću u konačnom broju tačaka u svojoj domeni, iako je ova domena kontinuum.

## Generisanje i širenje grešaka 
Proučavanje grešaka čini važan dio numeričke analize. Postoji nekoliko načina na koje se može unijeti greška u rješavanje problema.

### Zaokruživanje 
Greške zaokruživanja nastaju jer je nemoguće tačno predstaviti sve realne brojeve na mašini s konačnom memorijom (svi praktični digitalni računari).

### Greška pri skraćivanju i diskretizaciji 
Greške skraćivanja nastaju kada se iterativna metoda prekine ili se matematički postupak aproksimira i približno rješenje se razlikuje od tačnog rješenja. Slično tome, diskretizacija izaziva grešku diskretizacije jer se rješenje diskretnog problema ne poklapa s rješenjem kontinuiranog problema. U primjeru iznad kod izračunavanja rješenja jednačine 3x^3+4=28, nakon deset ponavljanja izračunati korijen je otprilike 1,99. Stoga je greška skraćivanja oko 0,01.

Jednom kada se greška generiše, ona se širi kroz proračun. Na primjer, operacija + na računaru je neprecizna. Izračun tipa a+b+c+d+e je još neprecizniji.

Greška skraćivanja se stvara kada se matematički postupak aproksimira. Da bi se funkcija precizno integrisala, mora se pronaći beskonačan zbir regiona, ali numerički se može pronaći samo konačan zbir regiona, što znači samo aproksimacija tačnog rešenja. Slično tome, da bi se diferencirala funkcija, diferencijalni element mora biti približan nuli, ali numerički se za vrijednost diferencijalnog elementa može samo odabrati vrijednost različita od nule.

### Numerička stabilnost i dobro postavljeni problemi 
Algoritam se naziva *numerički stabilnim* ako greška, bez obzira na njen uzrok, ne postaje mnogo veća tokom izračunavanja. To se dešava ako je problem *dobro uvjetovan*, što znači da se rješenje mijenja samo za malu vrijednost ako se podaci problema mijenjaju za malu vrijednost.

Regresija je također slična, ali uzima u obzir da su podaci neprecizni. Uzimajući u obzir određene tačke i mjerenje vrijednosti neke funkcije u tim tačkama (s greškom), nepoznata funkcija može biti pronađena. Metoda najmanjih kvadrata je jedan od načina da se to postigne.

### Rješavanje jednačina i sistema jednačina 
Jedan od fundamentalnih problema je izračunavanje rješenja određene jednačine. Obično se razlikuju dva slučaja, ovisno o tome da li je jednačina linearna ili ne. Na primjer, jednačina 2x+5=3 je linearna, dok 2x^2+5=3 nije.

Mnogo truda je uloženo u razvoj metoda za rješavanje sistema linearnih jednačina . Standardne direktne metode, tj. metode koje koriste neku vrstu matričnog razlaganja su Gaussova eliminacija, LU razlaganje, Choleskyjevo razlaganje za simetričnu (ili Hermiteovu) i pozitivno definitnu matricu i QR razlaganje za nekvadratne matrice. Iterativne metode kao što su Jacobijeva metoda, Gauss–Seidelova metoda, sukcesivna prekomjerna relaksacija i metoda konjugiranog gradijenta obično se preferiraju za velike sisteme. Opće iterativne metode mogu se razviti korištenjem cijepanja matrice.

Algoritmi za pronalaženje korijena koriste se za rješavanje nelinearnih jednačina (tako su nazvani jer je korijen funkcije argument za koji funkcija daje nulu). Ako je funkcija diferencibilna i izvod je poznata, onda je Newtonova metoda popularan izbor. Linearizacija je još jedna tehnika za rješavanje nelinearnih jednačina.

### Rješavanje problema svojstvenih ili singularnih vrijednosti 
Nekoliko važnih problema može se izraziti u terminima dekompozicija svojstvene vrijednosti ili dekompozicija singularne vrijednosti. Na primjer, algoritam spektralne kompresije slike temelji se na razlaganju singularnih vrijednosti. Odgovarajući alat u statistici naziva se analiza glavnih komponenti.

### Optimizacija 
 
Problemi optimizacije traže tačku u kojoj je data funkcija maksimizirana (ili minimizirana). Često tačka mora da zadovolji i neka ograničenja.

Polje optimizacije je podijeljeno na nekoliko podoblasti, ovisno o obliku ciljne funkcije i ograničenjima. Na primjer, linearno programiranje se bavi slučajem da su i ciljna funkcija i ograničenja linearni. Poznata metoda u linearnom programiranju je simpleks metoda.

Metoda Lagrangeovih množitelja može se koristiti za redukciju problema optimizacije s ograničenjima na neograničene optimizacijske probleme.

### Vrednovanje integrala 
Numerička integracija, u nekim slučajevima poznata i kao numerička kvadratura, traži vrijednost definitnog integrala. Popularne metode koriste jednu od Newton-Cotesovih formula (kao što je pravilo srednje tačke ili Simpsonovo pravilo) ili Gaussovu kvadraturu. Ove metode se oslanjaju na strategiju "zavadi pa vladaj", pri čemu se integral relativno velikog skupa razlaže na integrale manjih skupova. U višim dimenzijama, gdje ove metode postaju pretjerano skupe u smislu računskog napora, mogu se koristiti Monte Carlo ili kvazi-Monte Carlo metode (vidi Monte Carlo integracija) ili u umjereno velikim dimenzijama, metod prorijeđenih mreža.

### Diferencijalne jednačine 
 
Numerička analiza se također bavi (aproksimativnim) izračunavanjem rješenja diferencijalnih jednačina, kako običnih diferencijalnih jednadžbi, tako i parcijalnih diferencijalnih jednadžbi.

Parcijalne diferencijalne jednačine rješavaju se prvo diskretizacijom jednačine, dovodeći je u konačnodimenzionalni podprostor. Ovo se može učiniti metodom konačnih elemenata, metodom konačnih razlika ili (posebno u inženjerstvu) metodom konačnih volumena. Teorijsko obrazloženje ovih metoda često uključuje teoreme iz funkcionalne analize. Ovo svodi problem na rješenje algebarske jednačine.

## Softver 
Od kasnog dvadesetog stoljeća, većina algoritama je implementirana u različitim programskim jezicima. Netlib spremište sadrži različite kolekcije softverskih rutina za numeričke probleme, uglavnom u Fortranu i C-u. Komercijalni proizvodi koji implementiraju mnogo različitih numeričkih algoritama uključuju IMSL i NAG biblioteke; alternativa u slobodnom softveru je GNU naučna biblioteka.

Tokom godina Kraljevsko statističko društvo objavilo je brojne algoritme u svojoj *Primijenjenoj statistici* (;kod za ove "AS" funkcije se može pronaći ovdje); ACM radi slično u svojim *Transakcijama na matematičkom softveru* (; „TOMS“ kod se može pronaći ovdje). Centar za mornaričko površinsko ratovanje je nekoliko puta objavio svoju *Biblioteku matematičkih potprograma* (kod ovdje).

Postoji nekoliko popularnih aplikacija za numeričko računanje kao što su MATLAB, TK Solver, S-PLUS i IDL, te besplatne i open-source alternative kao što su FreeMat, Scilab, GNU Octave (slično Matlabu) i IT++ (C++ biblioteka). Postoje i programski jezici kao što su R (slično S-PLUS), Julia, i Python s bibliotekama kao što su NumPy, SciPy i SymPy. Performanse se uveliko razlikuju: dok su vektorske i matrične operacije obično brze, skalarne petlje mogu varirati u brzini više od jednog reda veličine.

Mnogi sistemi računarske algebre, kao što je Mathematica, također imaju korist od dostupnosti aritmetike proizvoljne preciznosti koja može pružiti tačnije rezultate.

Također bilo koji softver za proračunske tablice može se koristiti za rješavanje jednostavnih problema koji se odnose na numeričku analizu. Excel, na primjer, ima stotine dostupnih funkcija, uključujući i one za matrice, koje se mogu koristiti zajedno sa njegovim integrisanim "rješavačem".

## Reference 
### Izvori 
* 
* 
*
* 
* 
* 
*  (examples of the importance of accurate arithmetic).
*

## Vanjski linkovi
### Časopisi
**Numerische Mathematik*, volumes 1–..., Springer, 1959–
**volumes 1–66, 1959–1994 (searchable; pages are images). 
**Journal on Numerical Analysis* (SINUM), volumes 1–..., SIAM, 1964–

### Online tekstovi
*
**Numerical Recipes*, William H. Press (free, downloadable previous editions)
**First Steps in Numerical Analysis* (archived), R.J.Hosking, S.Joe, D.C.Joyce, and J.C.Turner
**CSEP* (Computational Science Education Project), U.S. Department of Energy (archived 2017-08-01) 
*Numerical Methods, ch 3. in the *Digital Library of Mathematical Functions*
*Numerical Interpolation, Differentiation and Integration, ch 25. in the *Handbook of Mathematical Functions* (Abramowitz and Stegun)

### Materijali s online kurseva
*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 Physicists, Anthony O’Hare Oxford University
*Lectures in Numerical Analysis (archived), R. Radok Mahidol University
*Introduction to Numerical Analysis for Engineering, Henrik Schmidt Massachusetts Institute of Technology
**Numerical Analysis for Engineering*, D. W. Harder University of Waterloo
*Introduction to Numerical Analysis, Doron Levy University of Maryland
*Numerical Analysis - Numerical Methods (archived), John H. Mathews California State University Fullerton

Kategorija:Računske nauke
Kategorija:Matematička fizika
Kategorija:Numerička analiza