From Wikipedia, the free encyclopedia
Нумеричка анализа је грана нумеричке математике која се бави проналажењем и унапређивањем алгоритама за нумеричко израчунавање вредности везаних за математичку анализу, попут нумеричког интегрисања, нумеричког деривисања и нумеричког решавања диференцијалних једначина. Саставни део нумеричке анализе је и оцењивање грешака метода (алгоритама) и то на два нивоа—анализа грешака самог метода, те анализа грешака које настају извредњавањем, а везане су уз архитектуру рачунала.[2]
 | Овај чланак можда захтева чишћење и/или прерађивање како би се задовољили стандарди квалитета Википедије. (април 2019) |
Потребе за нумеричким решавањем математичких проблема су вишеструке. Код неких проблема, доказано је да аналитичко решење (решење записано помоћу елементарних функција) не постоји - на пример решење интеграла немогуће је записати помоћу елементарних функција. Па ипак, одређени интеграл представља конкретну, јединствено одређену површину. До те вредности, која има широку употребу нпр. у статистици, могуће је доћи само нумеричким методама. Осим тога, нумеричке методе често се користе за одређивање решења математичких проблема који би због своје величине, кроз стандардни поступак решавања, предуго трајали - на пример, када је потребно решити систем од 10.000 једначина с 10.000 непознатих. И коначно, нумеричке методе су незаобилазне у приближном рачуну, када се апроксимацијама (и оценама припадних грешака) замењује стварна вредност функције до које је немогуће или претешко доћи. То су методе попут методе коначних елемената или пак кубних сплинова којима се апроксимира понашање непознате функције о којој знамо тек коначан број вредности, најчешће добијених мерењима.
Свеукупни циљ поља нумеричке анализе је развој и анализа техника које дају приближна али прецизна решења тешких проблема. Њихова разноврсност је сумирана следећим прегледом:
Остатак ове секције разматра неколико важних тема нумеричке анализе.
Поље нумеричке анализе претходи развоју модерних рачунара за пар миленијума. Линеарна интерполација је била у употреби пре више од 2000 година. Многи велики математичари су се бавили нумеричком анализом, као што следи из имена важних алгоритама, као што су Њутнов метод, Лагранжов интерполациони полином, Гаусова елиминација, или Ојлеров метод.
Да би се омогућили ручни прорачуни, произведене су велике књиге са формулама и табелама података као што су интерполационе тачке и коефицијенти функција. Користећи те табеле, које су често рачунате са 16 децималних места или више за поједине функције, могле су се наћи вредности за укључивање у формуле и тим путем су се могле остварити веома добре нумеричке процене неких функција. Канонички рад у пољу је НИСТ публикација који су уредили Абрамовитз и Стегун. То је књига са више од 1000 страна, у којој је обрађен веома велики број често коришћених формула и функција и њихове вредности у многим тачкама. Штампане вредности функција више нису од велике користи јер су доступни рачунари, мада су велики спискови формула још увек подесни за употребу.
Механички рачунар је развијен као оруђе за ручно рачунање. Ти калкулатори су еволуирали у електронске рачунаре током 1940-их, и након тога је уочено да су такви рачунари исто тако корисни за административне сврхе. Изум рачунара је такође утицао на поље нумеричке анализе, пошто су се сад могли вршити дужи и компликованији прорачуни.
|
Директни и итеративни методи Размотримо проблем решавања
за непознату променљиву x.
За итеративни метод, примени бисекциони метод на − 24. Иницијалне вредности су .
Из ове табеле закључујемо да је решење између 1,875 и 2,0625. Алгоритам може да врати било који број у том опсегу са грешком мањом од 0,2. Дискретизација и нумеричка интеграција_in_practice_at_USGP_2005.jpg) Током двочасовне трке смо измерили брзину кола три пута, и записали смо мерења у следећој табели.
Дискретизација би била да се каже да је брзина кола била константна од 0:00 до 0:40, затим од 0:40 до 1:20 и коначно од 1:20 до 2:00. На пример, тотално растојање пређено у првих 40 минута је приближно . То би нам омогућило да проценимо тотално пређено растојање као што је пример нумеричке интеграције (видите испод) користећи Риманову суму, пошто је растојање интеграл брзине. Нестабилан проблем: Узмимо функцију . Уочимо да промена x од мање од 0,1 одговара промени од скоро 1000. Евалуација је нестабилни проблем. Стабилан проблем: У контрасту с тим евалуација исте функције у близини x = 10 је стабилан проблем. На пример, скромна промена x доводи до скромне промене . |
Директни методи рачунају решења проблема у коначном броју корака. Ти методи би дали прецизан одговор, кад би се изводили аритметиком бесконачне прецизности. Примери обухватају Гаусову елиминацију, метод факторизације за решавање система линеарних једначина, и симплекс метод линеарног програмирања. У пракси се користи коначна прецизност и резултат је апроксимација истинског решења (подразумевајући стабилност).
У контрасту са директним методима, од итеративних метода се не очекује да заврше у коначном броју корака. Почевши од иницијалне претпоставке, итеративни методи формирају сукцесивне апроксимације које конвергирају до прецизног решења једино у лимиту. Тест конвергенције, који обично обухвата остатак, се специфицира да би се одредило кад је довољно прецизно решење нађено. Чак кад би се користила и аритметика бесконачне прецизности ови методи (генерално) не би достигли решење у коначном броју корака. Примери обухватају Њутнов метод, бисекциони метод, и Јакобијеву итерацију. У рачунарској матричној алгебри, итеративни методи су генерално неопходни за велике проблеме.
Итеративни методи се чешће срећу од директних у нумеричкој анализи. Неки методи су директни у принципу, али се обично користе као да нису, нпр. и метод коњугованог градијента. За те методе број корака који су неопходни да би добило прецизно решење је толико велики да се апроксимација прихвата у истом маниру као код итеративног метода.
Континуални проблеми се понекад морају заменити дискретним проблемима чије решење је познато да би се апроксимирало решење континуалног проблема; тај процес се назива дискретизацијом. На пример, решење диференцијалне једначине је функција. Та функција се мора заменити коначном количином података, на пример њеном вредношћу у коначном броју тачака њеног домена, мада је тај домен континуум.
Изучавање грешака сачињава важан део нумеричке анализе. Постоји неколико начина на који се може унети грешка у решење проблема.
Грешке заокруживања настају зато што је немогуће прецизно представити све реалне бројеве на машини са коначном меморијом (што је случај са практично свим дигиталним рачунарима).
Грешке скраћивања настају кад се итеративни метод заврши или кад се математичка процедура апроксимира, и приближно решење се разликује од тачног решења. Слично томе, дискретизација уноси грешку дискретизације зато што се решење дискретног проблема не поклапа са решењем континуалног проблема. На пример, у итерацији приказаној на десној страни да би се израчунало решење једначине , након 10 или више итерација, закључује се (на пример) да је корен око 1,99. Стога имамо грешку скраћивања од 0,01.
Након генерисања грешке, она се генерално увећава током прорачуна. На пример, већ смо напоменули да операција + на калкулатору (или рачунару) није прецизна. Из тога следи да је сабирање типа још непрецизније.
Горе је поменуто да долази до грешке скраћивања, кад се апроксимира математичка процедура. Познато је да је за прецизну интеграцију функције неопходно наћи збир бесконачно великог броја трапезоида. У пракси се међутим може одредити једино збир коначног броја трапезоида, и стога долази до апроксимације математичке процедуре. Слично томе, да би се диференцирала функција, диференцијални елемент треба да тежи нули, док је нумерички могуће једино изабрати коначну вредност диференцијалног елемента.
Нумеричка стабилност је важан појам у нумеричкој анализи. Алгоритам се сматра нумерички стабилним ако се грешка, независно од извора, знатно не увећава током прорачуна. До тога долази ако је проблем стабилан, што значи да се решење мало мења са малом променом улазних података. У контрасту с тим, ако је проблем нестабилан, онда свака мала грешка у улазним подацима нараста у велику грешку у решењу.
Оригинални проблем и алгоритам који се користе за решавање проблема могу да буду стабилни и/или нестабилни, или било која комбинација. Стога алгоритам који решава стабилни проблем може да буде било нумерички стабилан или нумерички нестабилан. Уметност нумеричке анализе је да се нађе стабилан алгоритам за решавање добро постављеног математичког проблема. На пример, израчунавање квадратног корена из 2 (који је око 1,41421) је стабилан проблем. Многи алгоритми решавају тај проблем почевши од иницијалне апроксимације x1 од , на пример x1=1,4, и затим израчунавају побољшање претпоставке x2, x3, . Један такав метод је познати Вавилонски метод, који је дат са . Још један итеративни приступ, који ћемо звати Метод X, је дат са .[3] Израчунали смо неколико итерација овог алгоритма у доњој табели, са иницијалним претпоставкама .
| Вавилонски метод | Вавилонски метод | Метод 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 нумерички нестабилан.
Поље нумеричке анализе обухвата мноштво потдисциплина. Неке од главних су:
|
Интерполација: Примећено је да температура варира од 20 °C у 1:00 до 14 степени у 3:00. Линеарном интерполацијом тих података се долази до закључка да је било 17 степени у 2:00 и 18,5 степени у 1:30 . Екстраполација: Ако је бруто домаћи производ земље просечно растао са 5% годишње и ако је био 100 милијарде долара прошле године, екстраполацијом можемо закључити да ће бити 105 милијарде долара ове године.  Регресија: У линеарној регресији, полазећи од тачка, израчунавамо линију која пролази колико год је могуће близу тих тачака.  Оптимизација: Рецимо да продајемо лимунаду на тезги, и уочимо да при цени од 1 америчког долара можемо да продамо 197 чаша лимунаде на дан, и да за сваких 0,01 америчких долара повећања цене, продаја опада за једну чашу лимунаде на дан. Ако продајемо по цени од 1,485 америчких долара долази до максимизације профита, али због ограничења да је неопходно наплаћивати целобројну цену, наплаћивање 1,48 америчких долара или 1,49 америчких долара по чаши ће произвести максимални приход од 220,52 америчких долара на дан.  Диференцијална једначина: Ако се 100 фанова подеси да дувају ветар са једног краја собе на другу и затим се пусти перо у ветар, шта се догађа? Перо ће следити струју ваздуха, која може да буде веома комплексна. Једна апроксимација је да се измери брзина којом се дува ваздух у близини пера у свакој секунди, и да се симултано помера перо као да се креће у правој линији истом брзином током једне секунде, пре него што се поново измери брзина ветра. То се назива Ојлеровим методом решавања обичне диференцијалне једначине. |
Један од најједноставнијих проблема је евалуација функције у датој тачки. Најпростији приступ уношења броја у формулу није увек веома ефикасан. За полиноме, бољи приступ је коришћење Хорнерове шеме, пошто се тиме редукује број неопходних множења и сабирања. Генерално је важно да се процени и контролише грешка заокруживања која настаје при употреби аритметике покретног зареза.
Интерполација решава следећи проблем: полазећи од вредности неке непознате функције у више тачака, коју ће вредност та функција имати у некој другој тачки између познатих тачака.
Екстраполација је веома слична интерполацији, изузев да је овде циљ да се нађе вредност непознате функције у тачки која је изван опсега познатих тачака.
Регресија је такође слична, изузев да узима у обзир податке као да су непрецизни. Полазећи од датог броја тачака и измерених вредности неке функције у тим тачкама (са грешком), циљ је да се одреди непозната функција. Метод најмањих квадрата је један од популарних приступа регресионе анализе.
Још један фундаментални проблем је израчунавање решења дате једначине. Два случаја се обично разликују, у зависности од тога да ли је једначина линеарна или није. На пример, једначина је линеарна, док није.
Знатне количине труда су уложене у развој метода за решавање система линеарних једначина. Стандардни директни методи, тј., методи који користе неку од декомпозиција матрица су Гаусова елиминација, ЛУ декомпозиција, Чолескијева декомпозиција за симетричне (или хермитијанске) или позитивно-коначне матрице, и QР декомпозиција за неквадратне матрице. Итеративни методи као што је Јакобијев метод, Гаус-Зајделова метод, сукцесивна прекомерна релаксација и метод коњугованог градијента су обично преферентни за велике системе. Општи итеративни методи се могу развити користећи поделе матрице.
Алгоритми налажења корена се користе за решавање нелинеарних једначина (они су тако названи зато што је корен функције аргумент за који је вредност функције нула). Ако је функција диференцијабилна и ако су деривати познати, онда је Њутнов метод популарни извор. Линеаризација је још једна техника за решавање нелинеарних једначина.
Неколико важних проблема се може изразити у облику декомпозиција својственим вредностима или декомпозиција сингуларне вредности. На пример, алгоритам спектралне компресије слике[4] је базиран на декомпозицији сингуларне вредности. Кореспондирајући алат у статистици се назива анализа принципалних компоненти.
Оптимизациони проблеми се баве одређивањем тачке у којој долази до максимизације (минимизације) дате функције. Обично та тачка мора да задовољи извесна ограничења.
Поље оптимизације се даље дели у неколико потпоља, у зависности од форме циљне функције и ограничења. На пример, линеарно програмирање се бави случајем где су циљна функција и ограничења линеарни. Познати метод линеарног програмирања је симплекс метод.
Метод Лангранжових множиоца се може користити за редуковање оптимизационих проблема са ограничењима до оптимизационих проблема без ограничења.
Нумеричка анализа се исто тако бави израчунавањем (на приближан начин) решења диференцијалних једначина, обичних диференцијалних једначина и парцијалних диференцијалних једначина.
Парцијалне диференцијалне једначине се решавају тако што се прво дискретизује једначина, чиме се доводи у коначно-димензиони потпростор. То се може урадити методом коначних елемената, методом коначних разлика, или (посебно у инжењерству) методом коначних запремина. Теоретска залеђина тих метода обично обухвата теореме функционе анализе. Тиме се редукује проблем до решавања алгебарске једначине.
Од касног 20. века, већина алгоритама је имплементирана у више различитих програмских језика. Нетлиб репозиторија садржи разне колекције софтверских рутина за нумеричке проблеме, углавном у језицима Фортран и Ц. Производи у продаји садрже имплементације мноштва различитих нумеричких алгоритама укључујући ИМСЛ у НАГ библиотеке; слободна алтернатива је ГНУ научна библиотека.
Постоји неколико популарних нумеричких рачунарских апликација, као што су , , , , и , као и алтернативе бесплатног и отвореног изворног кода: , , (слично Матлабу), ( библиотека), (слично са ) и поједине варијанте језика. Перформансе знатно варирају: док су векторске и матричне операције обично брзе, скаларне петље могу да варирају по брзини за више од једног реда величине.[5][6]
Многи рачунарски алгебарски системи, као што је , такође користе доступност арбитрарне аритметичке прецизности која може да омогући тачније резултате.
Софтвер за електронске табеле (нпр. Еxцел) исто тако може да се користи за решавање једноставних проблема из поља нумеричке анализе.
Један од најчешћих проблема с којима се сусрећемо у нумеричкој анализи је рачунање вриједности одређеног интеграла: . Нумеричка интеграција је у неким околностима позната као нумеричка квадратура. Популарне методе користе једну од Њутн–Коутсових формула (попут правила средње тачке или Симпсоновог правила) или Гаусове квадратуре. Те методе се ослањају на стратегију „подели и покори“, тако што се интеграл на релативно великом сету подели у интеграле на мањим сетовима. У случајевима великог броја димензија, где су ти методи недопустиво скупи у погледу рачунарских захтева, прибегава се примени Монте Карловог или квази-Монте Карловог метода (погледајте Монте Карло интеграција), или, код умерено великог броја димензија, метода ретке мреже.
Две основне методе нумеричке интеграције су проширена трапезна формула и проширена Симпсонова формула.[7]
Код проширене трапезне формуле, интервал интеграције подели се у подинтервала уз следећу ознаку: . У свим се тачкама раздиобе израчунају вредности подинтегралне функције , те се над сваким подинтегралом формира трапез спајањем тачака и . Тим се трапезом, чија је површина једнака , апроксимира стварна површина испод функције на том интервалу. Уз уобичајен поступак еквидистантне раздиобе, тј раздиобе интервала на једнаких подинтервала (код којег је , те збрајањем површина трапеза конструисаних над свим интервалима раздиобе добијамо трапезну формулу:
Оцјена грешке ове нумеричке апроксимације дана је с:
Проширена Симпсонова формула, као и трапезна формула почиње раздеобом интервала на , не нужно, једнаких подинтервала. Но овога пута се на свака два подинтервала, односно кроз тачке и повлачи јединствено одређена квадратна функција (парабола). Због тога код провођења Симпсонове формуле имамо додатни захтев да је број подинтервала паран. Рачунањем површина испод тако континуираних парабола, те њиховим збрајањем добијамо проширену Симпсонову формулу:
Оцена грешке проширене Симпсонове формуле дата је изразом:
Како у правилу парабола боље апрокисимира насумичне функције од правца, Симпсонова формула у правилу даје тачнији резултат од трапезне формуле.
У нумеричку анализу спадају и методе којима се тражи нумеричко приближно решење Кошијевог проблема, диференцијалне једначине са задатим почетним условом. Развијене су методе за нумеричко решавање обичних, али и парцијалних диференцијалних једначина. Две основне методе су Ојлерова метода и фамилија метода Рунге-Кута.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
![{\displaystyle E(f)=\max _{\xi \in [a,b]}{\frac {(b-a)^{3}}{12n^{2}}}|f''(\xi )|.}](http://wikimedia.org/api/rest_v1/media/math/render/svg/e9ba68added4b25acdf7cd068cb9312d284d6069)
![{\displaystyle \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 ]}.}](http://wikimedia.org/api/rest_v1/media/math/render/svg/d6f47df5d7a5e7bcb4662f8322c010b23f29becf)
![{\displaystyle E(f)=\max _{\xi \in [a,b]}{\frac {(b-a)^{5}}{180n^{4}}}|f^{(4)}(\xi )|.}](http://wikimedia.org/api/rest_v1/media/math/render/svg/8b5f72ba81bfa764b108a11376fc94498e8b09e0)
