thumb|250п|right|Вавилонска глинена плочица (c. 1800–1600. п. н. е.) са анотацијама. Апроксимација квадратног корена из 2 са четири шездесетне цифре, које су око шест децималних цифара. 1 + 24/60 + 51/602 + 10/603 = 1.41421296...
Нумеричка анализа је грана нумеричке математике која се бави проналажењем и унапређивањем алгоритама за нумеричко израчунавање вредности везаних за математичку анализу, попут нумеричког интегрисања, нумеричког деривисања и нумеричког решавања диференцијалних једначина. Саставни део нумеричке анализе је и оцењивање грешака метода (алгоритама) и то на два нивоа—анализа грешака самог метода, те анализа грешака које настају извредњавањем, а везане су уз архитектуру рачунала.Numerička analiza Pristupljeno: 20. 09. 2013.
Потребе за нумеричким решавањем математичких проблема су вишеструке. Код неких проблема, доказано је да аналитичко решење (решење записано помоћу елементарних функција) не постоји - на пример решење интеграла немогуће је записати помоћу елементарних функција. Па ипак, одређени интеграл представља конкретну, јединствено одређену површину. До те вредности, која има широку употребу нпр. у статистици, могуће је доћи само нумеричким методама. Осим тога, нумеричке методе често се користе за одређивање решења математичких проблема који би због своје величине, кроз стандардни поступак решавања, предуго трајали - на пример, када је потребно решити систем од 10.000 једначина с 10.000 непознатих. И коначно, нумеричке методе су незаобилазне у приближном рачуну, када се апроксимацијама (и оценама припадних грешака) замењује стварна вредност функције до које је немогуће или претешко доћи. То су методе попут методе коначних елемената или пак кубних сплинова којима се апроксимира понашање непознате функције о којој знамо тек коначан број вредности, најчешће добијених мерењима.
Општи увод Свеукупни циљ поља нумеричке анализе је развој и анализа техника које дају приближна али прецизна решења тешких проблема. Њихова разноврсност је сумирана следећим прегледом: Напредни нумерички методи су есенцијални у омогућавању нумеричких метереолошких предвиђања. Прорачунавање путање свемирске летилице се врши путем нумеричког решавања система обичних диференцијалних једначина. Аутомобилске компаније могу да побољшају безбедност возила користећи рачунарске симулације аутомобилских удеса. Такве симулације се есенцијално састоје од нумеричког решавања парцијалних диференцијалних једначина. Хеџ фондови (приватни инвестициони фондови) користе оруђа из свих поља нумеричке анализе у прорачунима вредности акција и деривата. Авиокомпаније користе софистиковане оптимизационе алгоритме у одређивању цени карти, расподеле авиона и посаде, и потребе за горивом. Историјски, такви алгоритми су развијени у оквиру преклапајућег поља операционих истраживања. Друштва за осигурање користе нумеричке програме за актуарне анализе.
Остатак ове секције разматра неколико важних тема нумеричке анализе.
Историја
Поље нумеричке анализе претходи развоју модерних рачунара за пар миленијума. Линеарна интерполација је била у употреби пре више од 2000 година. Многи велики математичари су се бавили нумеричком анализом, као што следи из имена важних алгоритама, као што су Њутнов метод, Лагранжов интерполациони полином, Гаусова елиминација, или Ојлеров метод.
Да би се омогућили ручни прорачуни, произведене су велике књиге са формулама и табелама података као што су интерполационе тачке и коефицијенти функција. Користећи те табеле, које су често рачунате са 16 децималних места или више за поједине функције, могле су се наћи вредности за укључивање у формуле и тим путем су се могле остварити веома добре нумеричке процене неких функција. Канонички рад у пољу је НИСТ публикација који су уредили Абрамовитз и Стегун. То је књига са више од 1000 страна, у којој је обрађен веома велики број често коришћених формула и функција и њихове вредности у многим тачкама. Штампане вредности функција више нису од велике користи јер су доступни рачунари, мада су велики спискови формула још увек подесни за употребу.
Механички рачунар је развијен као оруђе за ручно рачунање. Ти калкулатори су еволуирали у електронске рачунаре током 1940-их, и након тога је уочено да су такви рачунари исто тако корисни за административне сврхе. Изум рачунара је такође утицао на поље нумеричке анализе, пошто су се сад могли вршити дужи и компликованији прорачуни.
Директни и итеративни методи
Директни и итеративни методи
Размотримо проблем решавања
3x3 + 4 = 28
за непознату променљиву x.
+ Директни метод 3x3 + 4 = 28. Одузми 4 3x3 = 24. Подели са 3 x3 = 8. Уради кубни корен x = 2.
За итеративни метод, примени бисекциони метод на -{f(x) = 3x3}- − 24. Иницијалне вредности су -{a = 0, b = 3, f(a) = −24, f(b) = 57}-.
+ Итеративни метод 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...
Из ове табеле закључујемо да је решење између 1,875 и 2,0625. Алгоритам може да врати било који број у том опсегу са грешком мањом од 0,2.
Дискретизација и нумеричка интеграција
right|125px Током двочасовне трке смо измерили брзину кола три пута, и записали смо мерења у следећој табели.
Време 0:20 1:00 1:40 -{km/h}- 140 150 180
Дискретизација би била да се каже да је брзина кола била константна од 0:00 до 0:40, затим од 0:40 до 1:20 и коначно од 1:20 до 2:00. На пример, тотално растојање пређено у првих 40 минута је приближно -{(2/3h &puta; 140 km/h) = 93.3 km}-. То би нам омогућило да проценимо тотално пређено растојање као -{93.3 km + 100 km + 120 km = 313.3 km,}- што је пример нумеричке интеграције (видите испод) користећи Риманову суму, пошто је растојање интеграл брзине.
Нестабилан проблем: Узмимо функцију -{f(x) = 1/(x − 1)}-. Уочимо да -{f(1,1) = 10 i f(1,001) = 1000:}- промена x од мање од 0,1 одговара промени -{f(x)}- од скоро 1000. Евалуација -{f(x) u blizini x = 1}- је нестабилни проблем.
Стабилан проблем: У контрасту с тим евалуација исте функције -{f(x) = 1/(x − 1)}- у близини x = 10 је стабилан проблем. На пример, -{f(10) = 1/9 ≈ 0,111 i f(11) = 0,1:}- скромна промена x доводи до скромне промене -{f(x)}-.
Директни методи рачунају решења проблема у коначном броју корака. Ти методи би дали прецизан одговор, кад би се изводили аритметиком бесконачне прецизности. Примери обухватају Гаусову елиминацију, метод -{QR}- факторизације за решавање система линеарних једначина, и симплекс метод линеарног програмирања. У пракси се користи коначна прецизност и резултат је апроксимација истинског решења (подразумевајући стабилност).
У контрасту са директним методима, од итеративних метода се не очекује да заврше у коначном броју корака. Почевши од иницијалне претпоставке, итеративни методи формирају сукцесивне апроксимације које конвергирају до прецизног решења једино у лимиту. Тест конвергенције, који обично обухвата остатак, се специфицира да би се одредило кад је довољно прецизно решење нађено. Чак кад би се користила и аритметика бесконачне прецизности ови методи (генерално) не би достигли решење у коначном броју корака. Примери обухватају Њутнов метод, бисекциони метод, и Јакобијеву итерацију. У рачунарској матричној алгебри, итеративни методи су генерално неопходни за велике проблеме.
Итеративни методи се чешће срећу од директних у нумеричкој анализи. Неки методи су директни у принципу, али се обично користе као да нису, нпр. -{GMRES}- и метод коњугованог градијента. За те методе број корака који су неопходни да би добило прецизно решење је толико велики да се апроксимација прихвата у истом маниру као код итеративног метода.
Дискретизација
Континуални проблеми се понекад морају заменити дискретним проблемима чије решење је познато да би се апроксимирало решење континуалног проблема; тај процес се назива дискретизацијом. На пример, решење диференцијалне једначине је функција. Та функција се мора заменити коначном количином података, на пример њеном вредношћу у коначном броју тачака њеног домена, мада је тај домен континуум.
Генерација и пропагација грешака Изучавање грешака сачињава важан део нумеричке анализе. Постоји неколико начина на који се може унети грешка у решење проблема.
Заокруживање
Грешке заокруживања настају зато што је немогуће прецизно представити све реалне бројеве на машини са коначном меморијом (што је случај са практично свим дигиталним рачунарима).
Скраћивање и грешке дискретизације
Грешке скраћивања настају кад се итеративни метод заврши или кад се математичка процедура апроксимира, и приближно решење се разликује од тачног решења. Слично томе, дискретизација уноси грешку дискретизације зато што се решење дискретног проблема не поклапа са решењем континуалног проблема. На пример, у итерацији приказаној на десној страни да би се израчунало решење једначине , након 10 или више итерација, закључује се (на пример) да је корен око 1,99. Стога имамо грешку скраћивања од 0,01.
Након генерисања грешке, она се генерално увећава током прорачуна. На пример, већ смо напоменули да операција + на калкулатору (или рачунару) није прецизна. Из тога следи да је сабирање типа -{a+b+c+d+e}- још непрецизније.
Горе је поменуто да долази до грешке скраћивања, кад се апроксимира математичка процедура. Познато је да је за прецизну интеграцију функције неопходно наћи збир бесконачно великог броја трапезоида. У пракси се међутим може одредити једино збир коначног броја трапезоида, и стога долази до апроксимације математичке процедуре. Слично томе, да би се диференцирала функција, диференцијални елемент треба да тежи нули, док је нумерички могуће једино изабрати коначну вредност диференцијалног елемента.
Нумеричка стабилност и добро постулирани проблеми
Нумеричка стабилност је важан појам у нумеричкој анализи. Алгоритам се сматра нумерички стабилним ако се грешка, независно од извора, знатно не увећава током прорачуна. До тога долази ако је проблем стабилан, што значи да се решење мало мења са малом променом улазних података. У контрасту с тим, ако је проблем нестабилан, онда свака мала грешка у улазним подацима нараста у велику грешку у решењу.
Оригинални проблем и алгоритам који се користе за решавање проблема могу да буду стабилни и/или нестабилни, или било која комбинација. Стога алгоритам који решава стабилни проблем може да буде било нумерички стабилан или нумерички нестабилан. Уметност нумеричке анализе је да се нађе стабилан алгоритам за решавање добро постављеног математичког проблема. На пример, израчунавање квадратног корена из 2 (који је око 1,41421) је стабилан проблем. Многи алгоритми решавају тај проблем почевши од иницијалне апроксимације x1 од , на пример x1=1,4, и затим израчунавају побољшање претпоставке x2, x3, -{etc}-. Један такав метод је познати Вавилонски метод, који је дат са -{xk+1 = xk/2 + 1/xk}-. Још један итеративни приступ, који ћемо звати Метод X, је дат са -{xk + 1 = (xk2−2)2 + xk}-.This is a fixed point iteration for the equation , whose solutions include . The iterates always move to the right since . Hence converges and diverges. Израчунали смо неколико итерација овог алгоритма у доњој табели, са иницијалним претпоставкама -{x1 = 1,4 i x1 = 1,42}-.
Вавилонски метод Вавилонски метод Метод X Метод 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...
Може се уочити да Вавилонски метод брзо конвергира независно од иницијалне претпоставке, док Метод X конвергира екстремно споро са иницијалном претпоставком од 1,4 и дивергира почевши од иницијалне претпоставке 1,42. Стога је Вавилонски метод нумерички стабилан, док је Метод X нумерички нестабилан. Нумеричка стабилност је зависна од броја значајних цифара које дата машина подржава, ако се користи машина која ради са прве четири цифре покретног зареза долази до знатног губитка прецизности
Ако се упореде резултати од
и