Нумеричка анализа

Из Википедије, слободне енциклопедије
Вавилонска глинена плочица (c. 1800–1600 п.н.е.) са анотацијама. Апроксимација квадратног корена из 2 са четири шездесетне цифре, које су око шест децималних цифара. 1 + 24/60 + 51/602 + 10/603 = 1.41421296...[1]

Нумеричка анализа је грана нумеричке математике која се бави проналажењем и унапређивањем алгоритама за нумеричко израчунавање вриједности везаних уз математичку анализу, попут нумеричког интегрисања, нумеричког деривисања и нумеричког решавања диференцијалних једначина. Саставни део нумеричке анализе је и оцењивање грешака метода (алгоритама) и то на два нивоа -- анализа грешака самог метода, те анализа грешака које настају извредњавањем, а везане су уз архитектуру рачунала.[2]

Потребе за нумеричким решавањем математичких проблема су вишеструке. Код неких проблема, доказано је да аналитичко решење (решење записано помоћу елементарних функција) не постоји - на пример решење интеграла немогуће је записати помоћу елементарних функција. Па ипак, одређени интеграл представља конкретну, јединствено одређену површину. До те вредности, која има широку употребу нпр. у статистици, могуће је доћи само нумеричким методама. Осим тога, нумеричке методе често се користе за одређивање решења математичких проблема који би због своје величине, кроз стандардни поступак решавања, предуго трајали - на пример, када је потребно решити систем од 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.

Дискретизација и нумеричка интеграција[уреди]

Schumacher (Ferrari) in practice at USGP 2005.jpg

Током двочасовне трке смо измерили брзину кола три пута, и записали смо мерења у следећој табели.

Време 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.[3] Израчунали смо неколико итерација овог алгоритма у доњој табели, са иницијалним претпоставкама 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 нумерички нестабилан.

Нумеричка стабилност је зависна од броја значајних цифара које дата машина подржава, ако се користи машина која ради са прве четири цифре покретног зареза долази до знатног губитка прецизности
Ако се упореде резултати од
и
уочава се да губитак значаја, који се такође назива поништавања одузимањем, има огромни ефекат на резултате, мада су функције еквивалентне; да би се показало да су еквивалентне једноставно се полази од f(x) и завршава са g(x), тако да је
Истинска вредност резултата је 11,174755..., што је тачно g(500) = 11,1748 након заокруживања резултата на 4 децимална места.
Сад замислимо да се користи мноштво чланова као што су ове функције у програму; грешке ће се увећавати током рада програма, осим ако се користи подесна формула за ове две функције сваки пут кад се израчунавају f(x), или g(x); избор је завистан од паритета  x.
  • Пример је узет из: Mathew; Numerical methods using matlab, 3rd ed.

Области изучавања[уреди]

Поље нумеричке анализе обухвата мноштво потдисциплина. Неке од главних су:

Израчунавање вредности функција[уреди]

Интерполација: Примећено је да температура варира од 20 степени Целзијуса у 1:00 до 14 степени у 3:00. Линеарном интерполацијом тих података се долази до закључка да је било 17 степени у 2:00 и 18,5 степени у 1:30 pm.

Екстраполација: Ако је бруто домаћи производ земље просечно растао са 5% годишње и ако је био 100 милијарде долара прошле године, екстраполацијом можемо закључити да ће бити 105 милијарде долара ове године.

Линија кроз 20 тачака

Регресија: У линеарној регресији, полазећи од n тачка, израчунавамо линију која пролази колико год је могуће близо тих n тачака.

Колико кошта чаша лимунаде?

Оптимизација: Рецимо да продајемо лимунаду на тезги, и уочимо да при цени $1, можемо да продамо 197 чаша лемунаде на дана, и да за сваких $0,01 повећања цене, продаја опада за једну чашу линуманаде на дан. Ако продајемо по цени од $1,485, долази до максимизације профита, али због ограничења да је неопходно напаћивати целобројну цену, наплаћивање $1,48 или $1,49 по чаши ће произвести максимални приход од $220,52 на дан.

Правац ветра је означен плавом бојом, истинска трајекторија црно, резултат Ојлеровог метода црвено.

Диференцијална једначина: Ако се 100 фанова подеси да дувају ветар са једног краја собе на другу и затим се пусти перо у ветар, шта се догађа? Перо ће следити струју ваздуха, која може да буде веома комплексна. Једна апроксимација је да се измери брзина којом се дува ваздух у близини пера у свакој секунди, и да се симулисано помера перо као да се креће у правој линији истом брзином током једне секунде, пре него што се поново измери брзина ветра. То се назива Ојлеровим методом решавања обичне диференцијалне једначине.

Један од најједноставнијих проблема је евалуација функције у датој тачки. Најпростији приступ уношења броја у формулу није увек веома ефикасан. За полиноме, бољи приступ је коришћење Хорнерове шеме, пошто се тиме редукује број неопходних множења и сабирања. Генерално је важно да се процени и контролише грешка заокруживања која настаје при употреби аритментике покретног зареза.

Интерполација, екстраполација, и регресија[уреди]

Интерполација решава следећи проблем: полазећи од вредности неке непознате функције у више тачака, коју ће вредност та функција имати у некој другој тачки између познатих тачака?

Екстраполација је веома слична интерполацији, изузев да је овде циљ да се нађе вредност непознате функције у тачки која је изван опсега познатих тачака.

Регресија је такође слична, изузев да узима у обзир податке као да су непрецизни. Полазећи од датог броја тачака и измерених вредности неке функције у тим тачкама (са грешком), циљ је да се одреди непозната функција. Метод најмањих квадрата је један од популарних приступа регресионе анализе.

Решавање једначина и система једначина[уреди]

Још један фундаментални проблем је израчунавање решења дате једначине. Два случаја се обично разликују, у зависности од тога да ли је једначина линеарна или није. На пример, једначина је линеарна, док није.

Знатне количине труда су уложене у развој метода за решавање система линеарних једначина. Стандардни директни методи, и.е., методи који користе неку од декомпозиција матрица су Гаусова елиминација, ЛУ декомпозиција, Чолескијева декомпозиција за симетричне (или хермитијанске) или позитивно-коначне матрице, и QР декомпозиција за неквадратне матрице. Итеративни методи као што је Јакобијев метод, Гаус-Зајделова метод, сукцесивна прекомерна релаксација и метод коњугованог градијента су обично преферентни за велике системе. Општи итеративни методи се могу развити користићи поделе матрице.

Алгоритми налажења корена се користе за решавање нелинеарних једначина (они су тако названи зато што је корен функције аргумент за који је вредност функције нула). Ако је функција диференцијабилна и ако су деривати познати, онда је Њутнов метод популарни извор. Линеаризација је још једна техника за решавање нелинеарних јеначина.

Решавање својствене вредносити или сингуларне вредности проблема[уреди]

Неколико важних проблема се може изразити у облику декомпозиција својственим вредностима или декомпозиција сингуларне вредности. На пример, алгоритам спектралне компресије слике[4] је базиран на декомпозицији сингуларне вредсности. Кореспондираћи алат у статистици се назива анализа принципалних компоненти.

Оптимизација[уреди]

Оптимизациони проблеми се баве одређивањем тачке у којој долази до максимизације (минимизације) дате функције. Обично та тачка мора да задовољи извесна ограничења.

Поље оптимизације се даље дели у неколико потпоља, у зависности од форме циљне функције и ограничења. На пример, линеарно програмирање се бави сличајем где су циљна функција и ограничања линеарни. Познати метод линеарног програмирања је симплекс метод.

Метод Лангранжових множиоца се може користити за редуковање оптимизационих проблема са ограничењима до оптимизационих проблема без ограничења.

Диференцијалне једначине[уреди]

Нумеричка анализа се исто тако бави израчунавањем (на апроксимативан начин) решења диференцијалних једначина, обичних диференцијалних једначина и парцијалних диференцијалних једначина.

Парцијалне дифференцијалне једначине се решавају тако што се прво дискретизује једначина, чиме се доводи у коначно-димензиони потпростор. То се може урадити методом коначиних елемената, методом коначних разлика, или (посебно у инжењерству) методом коначних запремина. Теоретска залеђина тих метода обично обухвата теореме функционе анализе. Тиме се редукује проблем до решавања алгебраске једначине.

Софтвер[уреди]

Од касног двадесетог века, већина алгоритама је имплементирана у више различитих програмских језика. Нетлиб репозиторија садржи разне колекције софтверских рутина за нумеричке проблеме, углавном у језицима Фортран и Ц. Производи у продаји садрже имплементације мноштва различитих нумеричких алгоритама укључујући ИМСЛ у НАГ библиотеке; слободна алтернатива је ГНУ научна библиотека.

Постоји неколико популарних нумеричких рачунарских апликација, као што су MATLAB, TK Solver, S-PLUS, LabVIEW, и IDL, као и алтернативе бесплатног и отвореног изворног кода: FreeMat, Scilab, GNU Octave (слично Матлабу), IT++ (C++ библиотека), R (слично са S-PLUS) и поједине варијанте Python језика. Перформанце знатно варирају: док су векторске и матричне операције обично брзе, скаларне петље могу да варирају по брзини за више од једног реда величине.[5][6]

Многи рачунарски алгебарски системи, као што је Mathematica, такође користе доступност арбитране аритметичке прецизности која може да омогући тачније резултате.

Софтвер за електронске табеле (нпр. Еxцел) исто тако може да се користи за решавање једноставних проблема из поља нумеричке анализе.

Нумеричко интегрирање[уреди]

Површина испод функције f(x) (означене плавом) апроксимира се површином трапеза испод по дијеловима линеарне апроксимације (означене црвеном).

Један од најчешћих проблема с којима се сусрећемо у нумеричкој анализи је рачунање вриједности одређеног интеграла: . Нумеричка интеграција је у неким околностима позната као нумеричка квадратура. Популарне методе користе једну од Њутн–Коутсових формула (попут правила средње тачке или Симпсоновог правила) или Гаусове квадратуре. Те методе се ослањају на стратегију „подели и покори“, тако што се интеграл на релативно великом сету подели у интеграле на мањим сетовима. У случајевима великог броја димензија, где су ти методи недопустиво скупи у погледу рачунарских захтева, прибегава се примени Монте Карловог или квази-Монте Карловог метода (погледајте Монте Карло интеграција), или, код умерено великог броја димензија, метода ретке мреже.

Две основне методе нумеричке интеграције су проширена трапезна формула и проширена Симпсонова формула[7].

Код проширене трапезне формуле, интервал интеграције [a,b] подели се у n подинтервала уз следећу ознаку: a=x0<x1<...<xn=b. У свим се тачкама раздиобе израчунају вредности подинтегралне функције yi=f(xi), те се над сваким подинтегралом формира трапез спајањем тачака Ti(xi,yi) и Ti+1(xi+1,yi+1). Тим се трапезом, чија је површина једнака Pi=(xi+1-xi)(yi+yi+1)/2, апроксимира стварна површина испод функције f(x) на том интервалу. Уз уобичајен поступак еквидистантне раздиобе, тј раздиобе интервала на n једнаких подинтервала (код којег је xi+1-xi=(b-a)/n ), те збрајањем површина трапеза конструираних над свим интервалима раздиобе добијамо трапезну формулу:

Оцјена грешке ове нумеричке апроксимације дана је с:

Површина испод функције f(x) (означене плавом) апроксимира се површином испод параболе која интерполира функцију у три задане тачке (означене црвеном).

Проширена Симпсонова формула, као и трапезна формула почиње раздеобом интервала [a,b] на n, не нужно, једнаких подинтервала. Но овога пута се на свака два подинтервала, односно кроз тачке Ti-1(xi-1,yi-1), Ti(xi,yi) и Ti+1(xi+1,yi+1) повлачи јединствено одређена квадратна функција (парабола). Због тога код провођења Симпсонове формуле имамо додатни захтев да је број подинтервала n паран. Рачунањем површина испод тако контруираних парабола, те њиховим збрајањем добијамо проширену Симпсонову формулу:

Оцена грешке проширене Симпсонове формуле дата је изразом:

Како у правилу парабола боље апрокисимира насумичне функције од правца, Симпсонова формула у правилу даје тачнији резултат од трапезне формуле.

Нумеричко рјешавање диференцијалних једнаџби[уреди]

У нумеричку анализу спадају и методе којима се тражи нумеричко апроксимативно решење "Кошиjevog problema"; diferencijalne jednaчинe s zadanim početnim условом. Razvijene su metode za numeričko rešavanje običnih, ali i parcijalnih diferencijalnih jednaчина. Dve osnovne metode su Eulerova metoda, i familija метода Рунге-Кута.

Види још[уреди]

Референце[уреди]

  1. Photograph, illustration, and description of the root(2) tablet from the Yale Babylonian Collection
  2. Numerička analiza Pristupljeno: 20. 09. 2013.
  3. This is a fixed point iteration for the equation , whose solutions include . The iterates always move to the right since . Hence converges and diverges.
  4. The Singular Value Decomposition and Its Applications in Image Compression
  5. Speed comparison of various number crunching packages
  6. Comparison of mathematical programs for data analysis Stefan Steinhaus, ScientificWeb.com
  7. str. 478, pristupljeno: 20. 9. 2013.

Литература[уреди]

  • Golub, Gene H. and Charles F. Van Loan (1986). Matrix Computations, Third Edition (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 изд.). 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.

Спољашње везе[уреди]