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.Stephen Blyth. "An Introduction to Quantitative Finance". 2013. page VII. 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, što je vidljivo iz naziva važnih algoritama kao što su Newtonova metoda, Lagrangeov interpolacijski polinom, Gaussova eliminacija ili Eulerova metoda. Porijeklo moderne numeričke analize često se povezuje s radom iz 1947. Johna von Neumanna i Hermana Goldstinea, 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, jer su se sada mogli raditi duži i komplikovaniji proračuni.

Leslie Fox nagradu za numeričku analizu inicirao je 1985. Institut za matematiku i njene primjene.

Ključni koncepti

Direktne i iterativne metode Direktne metode izračunavaju rješenje problema u konačnom broju koraka. Ove metode bi dale precizan odgovor ako bi se izvodile u aritmetici beskonačne preciznosti. Primjeri uključuju Gaussovu eliminaciju, metodu QR faktorizacije za rješavanje sistema linearnih jednačina, te simpleks metodu linearnog programiranja. U praksi se koristi konačna preciznost i rezultat je aproksimacija pravog rješenja (pod pretpostavkom stabilnosti).

Za razliku od direktnih metoda, od iterativnih metoda se ne očekuje da će završiti u konačnom broju koraka, čak i ako je moguća beskonačna preciznost. Počevši od početnog nagađanja, iterativne metode formiraju uzastopne aproksimacije koje konvergiraju tačnom rješenju samo u graničnoj vrijednosti. Test konvergencije, koji često uključuje ostatak, određen je kako bi se odlučilo kada je pronađeno dovoljno precizno rješenje. Čak i korištenjem aritmetike beskonačne preciznosti ove metode ne bi došle do rješenja unutar konačnog broja koraka (u općem slučaju). Primjeri uključuju Newtonovu metodu, metodu bisekcije i Jacobijevu iteraciju. U računskoj matričnoj algebri, iterativne metode su općenito potrebne za rješavanje velikih problema.

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

3x3 + 4 = 28

za nepoznatu veličinu x. +Direktna metoda 3x3 + 4 = 28. Oduzmi 4 3x3 = 24. Podijeli sa 3 x3 = 8. Izračnuaj kubni korijen x = 2. Za iterativnu metodu, primijenite metodu bisekcije na f(x) = 3x3 − 24. Početne vrijednosti su a = 0, b = 3, f(a) = −24, f(b) = 57. +Iterativna metoda a b sredina f(sredina) 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 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 , 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 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. Naprotiv, ako je problem "loše uslovljen", onda će svaka mala greška u podacima prerasti u veliku grešku. I originalni problem i algoritam koji se koristi za rješavanje tog problema mogu biti dobro uvjetovani ili loše uvjetovani, a moguća je i svaka kombinacija tih opcija. Dakle, algoritam koji rješava dobro uvjetovani problem može biti ili numerički stabilan ili numerički nestabilan. Umjetnost numeričke analize je pronaći stabilan algoritam za rješavanje dobro postavljenog matematičkog problema.

Oblasti proučavanja Područje numeričke analize uključuje mnoge poddiscipline. Neke od glavnih su:

Izračunavanje vrijednosti funkcij Interpolacija: Imajući u vidu da temperatura varira od 20 stepeni Celzijusa u 1:00 do 14 stepeni u 3:00, linearna interpolacija ovih podataka bi zaključila da je temperatura u 14:00 bila 17 stepeni i 18,5 stepeni u 13:30.

Ekstrapolacija: Ako je bruto domaći proizvod jedne zemlje rastao u prosjeku 5% godišnje i iznosio je 100 milijardi prošle godine, moglo bi se ekstrapolirati da će ove godine iznositi 105 milijardi.

desno|100x100piksel|A line through 20 points

Regresija: U linearnoj regresiji, imamo n tačaka za koje se izračunava linija koja prolazi što je moguće bliže tim n tačkama.

desno|107x107piksel|How much for a glass of lemonade?

Optimizacija: Pretpostavimo da se limunada prodaje na štandu za 1,00 € po čaši, te da se dnevno može prodati 197 čaša limunade i da će se za svako povećanje od 0,01 € prodati jedna čaša manje dnevno. Kada bi se moglo naplatiti 1,485 €, profit bi bio maksimiziran, ali zbog ograničenja da se iznos zaokružuje na cijeli cent, naplata od 1,48 € ili 1,49 € po čaši donijet će maksimalan prihod od 220,52 € po danu.

desno|Wind direction in blue, true trajectory in black, Euler method in red