Бројчена анализа: Разлика помеѓу преработките

Од Википедија — слободната енциклопедија
[непроверена преработка][непроверена преработка]
Избришана содржина Додадена содржина
Средени формули
Средено цело имам уште малку да додадам
Ред 368: Ред 368:


==== '''Оптимизациски алгоритми''' ====
==== '''Оптимизациски алгоритми''' ====
* Симплекс алгоритам од Џорџ Данциг, наменет за линеарно програмирање
* Симплекс алгоритам од Џорџ Данциг, наменет за линеарно програмирање
Проширување на симплекс алгоритмот, за квадратно програмирање и за линеарно-дробно-рационално програмирање
* Проширување на симплекс алгоритмот, за квадратно програмирање и за линеарно-дробно-рационално програмирање
Варијанти на симплекс алгоритам кои се особено погодни за оптимизација на мрежа
* Варијанти на симплекс алгоритам кои се особено погодни за оптимизација на мрежа
Комбинаторни алгоритми
* Комбинаторни алгоритми

Преработка од 14:42, 12 февруари 2017

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

Нумеричката анализа е област од математиката која изучува алгоритми кои користат нумерички апроксимации (за разлика од општите симболички манипулации) за задачите и проблемите на математичката анализа (која што се разликува од дискретна математика). Еден од најраните математички написи е Вавилонската плоча од Вавилонската колекција во Јеил (од 1800г. -1600г. п.н.е.) која дава нумерички апроксимации (приближувања) на како должина на дијагоналата во единечен квадрат во броен систем со основа 60. Од исклучително значење е да може да се пресметаат страните на еден триаголник, а со тоа да може да се пресметаат и квадратни корени. Ова е од големо значење во областа на астрономијата, столаријата и градежништвото. Нумеричката анализа ја продолжува долгогодишната традиција на практичните математички пресметки (калкулации).

Слично како Вавилонската апроксимација за , модерната нумеричка анализа не бара точни (егзактни) одговори бидејќи точните (егзактни) одговори е најчесто невозможнo да се добијат во пракса. Наместо тоа голем дел од нумеричката анализа се концентрира на добивање на приближни решенија во рамките на разумните граници на грешки. Нумеричката анализа наоѓа примена во сите области на инжeнерството и физичките науки, но во 21-от век исто така наоѓа примена и во општествените науки, па дури и во уметноста постојат усвоени елементи oд нумерички пресметки. Обичните диференцијални равенки се појавуваат во небесната механика (планети, ѕвезди и галаксии), нумеричката линеарна алгебра е важна за анализата на податоци; стохастичките диференцијални равенки и Марковите вериги се од суштинско значење во симулирањето на однесувањето на живите клетки во медицината и биологијата. Пред појавата на современите компјутери, нумеричките методи често зависеле од рачна интерполација на големи печатени табли. Наместо тоа од средината на 20-тиот век компјутерите почнале да ги пресметуваат потребните функциски вредности. Меѓутоа интерполационите формули сепак продолжуваат да се користат како дел од софтверот за решавање на диференцијални равенки.

Општ вовед

Општата цел во полето на нумеричката анализа е дизајн и анализа на техники потребни да се добијат приближни, со однапред зададена точност, решенија за сложени проблеми, чија разновидност може да се види низ следново:

  • Напредните нумерички методи се од суштинско значење за временските предвидувања да бидат нумерички изводливи
  • Пресметување на траекторијата на вселенското летало бара прецизни нумерички решенија на системи од обични диференцијални равенки.
  • Автомобилските компании можат да ја подобрат безбедноста на нивните возила од сообраќајни несреќи со користење на компјутерски симулации на истите. Симулациите во суштина се состојат од нумеричко решавање на парцијални диференцијални равенки.
  • Приватните инвестициски фондови користат алатки од сите области на нумеричката анализа за да ги пресметуваат вредностите на акциите и производите од другите учесници на пазарот.
  • Авионските линии користат софистицирани алгоритми за оптимизација при донесување на одлуките за цените на билетите, авионите и членовите на екипажот, како и потребите за гориво. Историски гледано, такви алгоритми се развиени во рамките на областите кои се преклопуваат со операционите истражувања.
  • Осигурителните компании користат нумерички програми за статистички анализи.

При решавање на многу практични проблеми, теориската математика може да докаже дека постои решение или дека е единствено, ама не и да даде постапка со која се доаѓа до тоа решение. Затоа нумеричката анализа има за цел да го пронајде приближното нумеричко решение на одреден проблем кое би можело да се искористи во различни инженерски дисциплини, како на пример софтверското инженерство. Во софтверското инженерство најчесто се користат итеративни постапки, чие решение се приближува до точното, но заради конечниот број на повторувања секогаш отстапува од точното. Отстапувањето на приближното решение од точното решение претставува грешка која може да биде:

  1. апсолутна грешка
  2. релативна грешка
  3. грешка на приближните вредности на функцијата и сл.

Грешките се јавуваат заради нумеричката постапка, како и заради грешките на дадените податоци. Според потеклото грешките можат да бидат:

  1. грешка од заокружување
  2. методска грешка
  3. системска грешка

Историја

Областа на нумеричката анализа масовно се користела пред развојот на модерните компјутери. Линеарната интерполација била во употреба пред повеќе од 2000 години. Многу големи математичари од минатото биле преокупирани со нумеричка анализа, што се гледа од имињата на некои важни алгоритми како на пример Њутнов метод, Лагранжова интерполација на полином, Гаусова елиминација или Ојлеров метод. За да се олеснат рачните пресметки, големите книги биле произведени со додатоци на формули и табели на податоци, како што се интерполација на точки и коефициенти на функции. Користењето на овие табели кои се често пресметани до 16 децимални места или повеќе за некои функции, можеле директно да се вклучат во веќе дадените формули и да се постигнат многу добри нумерички проценки и решенија на некои функции. Канонската работа во оваа област е дадена во книгата објавена од страна на Националниот институт за стандарди и технологија на САД, уредена од Абрамовиќ и Стегун. Тоа е книга со над 1000 страници во која се дадени и обработени голем број на најчесто користени формули и функции и нивните вредности во многу точки. Функциските вредности веќе не се користат многу често поради појавата на модерниот компјутер, меѓутоа голем број на формули се уште можат да бидат корисни и користени. Механичкиот калкулатор бил развиен како алатка за рачно пресметување. Овие калкулатори еволуирале во електронските компјутери во 1940 година, а потоа било откриено дека овие компјутери можат да бидат користени и за административни цели. Пронаоѓањето на компјутерите влијаело во областа на нумеричката анализа бидејќи оттогаш можеле да се вршат долги и сложени пресметки за многу кратко време.

Директни и итеративни методи

Директните методи го пресметуваат решението на еден проблем во конечен број чекори. Овие методи даваат прецизен одговор, кога би биле изведени во аритметика на бесконечна прецизност. Како пример за такви методи можат да се наведат Гаусовата елиминација, метод на QR-факторизација за решавање на систем на линеарни равенки и симплекс методот на линеарно програмирање. Во пракса се користи конечна прецизност и резултат е апроксимација на вистинското решение.

Податотека:Директни наспроти итеративни методи
Пр: Да се реши равенката: 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 средина f(средина)
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.

За разлика од директните методи кај итеративните методи не се очекува да завршат во конечен број чекори. Почнувајќи од почетно приближување, итеративните методи формираат сукцесивна апроксимација која конвергира до прецизното решение единствено во границата на однапред зададена точност. Тестот на конвергенција кој обично опфаќа остаток, се специфицира за да се одреди кога е најдено доволно прецизно решение. Дури кога би се користела и аритметика на бесконечна прецизност овие методи не би дошле до решение во конечен број чекори. Примерите ги опфаќаат Њутновиот метод, метод на преполовување и Јакобиевата итерација. Во компјутерската матрична алгебра, итеративните методи се генерално неопходни за решавање на големи проблеми. Итеративните методи почесто се среќаваат отколку директните методи во нумеричката анализа. Некои методи во принцип се директни, но обично се применуваат како итеративни на пример: GMRES (Метод за генерализација на минимални остатоци) и методот на коњугиран градиент. За овие методи бројот на чекори кои се неопходни за да се добие прецизно решение е толку голем што апроксимацијата се прифаќа исто како кај итеративната метода.

Дискретизација

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

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

Пример:Во двочасовна трка, ќе се мери брзината на автомобилот во три временски моменти и податоците се евидентирани во следната табела

Време 0:40 1:20 2:00
km/h 140 150 200

Ако се направи дискретизација, би требало да каже дека брзината на автомобилот била константна од 0:00 до 0:40, а потоа од 0:40 до 1:20 и конечно од1:20 до 2:00. На пример, вкупното растојание во првите 40 минути е апроксимативно околу (2/3 h × 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 и f(1.001) = 1000: Промената во х од помалку од 0,1 преминува во промена во f(x) од приближно 1000. Евалуацијата на f(x) за приближно x = 1 претставува лошо условен проблем.

Добро условен проблем: Спротивно на тоа, проценка на истата функција

f(x) = 1/(x − 1) во близина на  x = 10 е добро условен проблем. На пример, f(10) = 1/9 ≈ 0.111 и  f(11) = 0.1: скромна промена на х води до скромна промена во  f(x).

Генерирање и ширење на грешки

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

Заокружување

Грешките од заокружување се јавуваат бидејќи е невозможно прецизно да се претстават сите реални броеви на машина со конечна меморија (што е случај со сите дигитални компјутери).

Грешки од отсекување и дискретизација

Грешките од осекување се појавуваат тогаш кога еден итеративен метод ќе заврши или математичката постапка се апроксимира, и приближното решение се разликува од точното решение. Слично на тоа дискретизацијата вклучува дискретизациона грешка затоа што решението на дискретен проблем не се совпаѓа со решението на континуиран проблем. На пример, во итерацијата прикажана на горниот пример за да се пресмета решението на равенката 3х3+4=28, после 10 или повеќе итерации се заклучува дека се добива грубо решение на пример (1.99) . Со тоа имаме грешка од отсекување која изнесува 0.01. Откако една грешка се генерира таа се зголемува низ целата пресметка. Повторно за пример да ја истакнеме операцијата собирање (,,+,, на калкулатор или компјутер) за која веќе имаме спомнато дека не е прецизна, од тука следува дека и пресметката од видот a+b+c+d+e е уште понепрецизна. Горе е спомнато дека доаѓа до грешка од скратување кога апроксимираме математичка постапка. Познато е дека за прецизна интеграција на функција неопходно е да се најде збирот на бесконечен број трапезоиди. Но, во пракса меѓутоа можно е да се најде сумата (збирот) само на конечен број на трапезоиди, а со тоа да се приближиме кон точната вредност на интегралот. Слично на тоа, за да се најде извод на функцијата, диференцијалниот елемент се приближува кон нула, но нумерички може да се избере само ограничена вредност на диференцијалниот елемент.

Нумеричка стабилност и добро поставени проблеми

Нумеричката стабилност е важен поим во нумеричката анализа. Еден алгоритам се нарекува нумерички стабилен ако една грешка, без разлика како е предизвикана, не расте многу во текот на пресметувањето. Ова се случува кога проблемот е добро условен што значи дека решението се менува со мала промена на влезните податоци. Во спротивно, ако проблемот е лошо условен тогаш секоја мала грешка во влезните податоците ќе предизвикува поголема грешка во решението. Заедно и оригиналниот проблем и алгоритмот се користат да се реши проблем кој може да биде добро условен и/или лошо условен и секоја од овие комбинации може да биде возможна. Значи еден алгоритам кој решава добро условен проблем може да биде нумерички стабилен или нестабилен. Уметноста на нумеричката анализа е да се најде стабилниот алгоритам за решавање на добро поставен математички проблем. На пример, пресметувањето на (кој грубо изнесува 1.41421) е добро поставен проблем. Многу алгоритми го решаваат овој проблем почнувајќи со почетна апроксимација (приближување) на х1 кон , на пример х1=1.4, и потоа со х2, х3, х4 итн. Еден таков метод е познат како Вавилонски метод, кој е претставен како xk+1=xk/2 + 1/xk. Уште еден итеративен пристап, кој ќе го наречеме Метод Х, кој е даден со хк+1= (x_k^2-2)2 +x_(k.) . Пресметани се неколку итерации од секој од методите и прикажани во табелата подолу со почетни вредности за Х1=1.4 и Х2=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...

Може да се воочи дека вавилонскиот метод конвергира бргу без оглед на почетната вредност, додека пак Методот Х конвергира екстремно бавно со почетната вредност за х0=1.4 и дивергира за вредност за х0=1.42. Од тука Вавилонскиот метод претставува нумерички стабилен алгоритам за разлика од методот Х кој е нумерички нестабилен. Нумеричката стабилност е зависна од бројот на значајни цифри кој што машината (компјутерот) го поддржува. Доколку користиме компјутер кој што поддржува само четири значајни децимални цифри (после децималната точка), тоа може да претставува добар пример за губење на значајните децималните места коешто може да се увиди преку овие две еквивалентни функции:

f(x)=x(√(x+1) - √x) и g(x)=x/(√(x+1)+√x)

Ако го споредиме резултатот од:

f(500)=500(√501-√500)=500(22.3830-22.3607)=500(0.0223)=11.1500 и g(500)=500/(√501+√500)=500/(22.3830+22.3607)=500/44.7437=11.1748 се воочува дека се губат значајни цифри, кое исто така се нарекува поништување поради одземање на два многу блиски броја и има огромно влијание на резултатите иако двете функции се еквивалентни како што е покажано подолу, т.е равенството поаѓа од f(x) и завршува со g(x), така што:

f(x)=x(√(x+1)-√x)=x(√(x+1)-√x) (√(x+1)+√x)/(√(x+1)+√x)=x ((√(x+1))^2-(√x)^2)/(√(x+1)+√x)=x (x+1-x)/(√(x+1)+√x)=x 1/(√(x+1)+√x)=x/(√(x+1)+√x)


Бараната вредност е пресметана со користење на бескрајна точност и изнесува 11.174755....., што е точно g(500)=11.1748 после заокружување на резултатот на 4 децимални места. Сега да замислиме дека користиме многу операнди, како што се овие функциски вредности погоре; грешките ќе се зголемуваат во текот на програмата за работа, освен ако не користиме соодветна формула за овие две функции, секој пат кога пресметуваме f (x),или g (x); Примерот претставува модификација превземена од Mathew;Numerical methods using Mathlab 3rd (трето издание).

Области на проучување

Полето на нумеричката анализа вклучува многу поддисциплини меѓу кои едни од најважните се:

Пресметување вредности на функции

Еден од наједноставните проблеми е пресметување на функција во дадена точка. Наједноставен пристап е само додавање на број во формула меѓутоа понекогаш тој пристап не е ефикасен. За полиноми, подобар пристап е користење на Хорнеровата шема бидејќи таа ги редуцира бројот на множења и собирања. Општо земено важно е да се проценат и контролираат грешките од заокружување кои произлегуваат од употребата на аритметика на подвижна точка.

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

Податотека:Решавање на равенки и систем равенки
Интерполација: забележано е дека температурата варира од 20 степени Целзиусови во 1:00 до 14 степени во 3:00. Со линеарна интерполација на овие податоци се доаѓа до заклучок дека во 2:00 биле 17 степени и 18.5 степени во 1:30. Екстраполација: Ако бруто домашниот производ на земјата пораснал за 5% годишно и ако биле 100 милијарди денари минатата година, со екстраполација може да се заклучи дека ќе биде 105 милијарди денари оваа година. Регресија: Во линеарна регресија , поаѓајќи од n точки, пресметуваме равенка на права која поминува колку што е можно поблизу до тие n точки. Оптимизација:Да претпоставиме дека продаваме лимонада на тезга, и воочуваме дека при цена 10 денари, можеме да продадеме 197 чаши лимонади на ден, и за секои 0.1денари зголемена цена, продажбата опаѓа за една чаша лимонада на ден. Ако пак продаваме по цена од 14.85 денари, доаѓаме до максимален профит, но поради ограничувањето да нaплатуваме целобројна цена во дени (десети дел од денарот), наплатуваме 14.8 денари или 14.9 денари за чаша ќе добиеме максимален приход од 2205.2 денари на ден. Диференцијална равенка: Ако 100 луѓе се насочат да дуваат воздух од еден крај на собата на другиот крај и потоа се пушти перо во воздухот, тогаш што ќе се случи? Перото ќе ја следи струјата на воздухот, која може да биде многу комплексна. Една апроксимација е да се измери брзината со која се дува воздухот во близина на перото во секоја секунда, и да се симулира поместувањето на перото како да се движи во права линија со иста брзина во тек на една секунда, пред повторно да се измери брзината на ветерот. Тоа се нарекува Ојлерова метода на решавање на обична диференцијална равенка.

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

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

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

Решавање на равенки и систем од равенки

Друг основен проблем е пресметување на решението на дадена равенка. Два случаи најчесто се разликуваат во зависност од тоа дали равенката е линеарна или нелинеарна. На пример, равенката 2х + 5 =3 е линеарна, додека 2х2 + 5 = 3 е нелинеарна равенка. Многу напор е вложен во развојот на методи за решавање на системи од линеарни равенки. Стандардни директни методи односно методите кои користат некои матрични разложувања се Гаусовата елиминација , LU декомпозиција (на долно триаголна матрица L и горно триаголна матрица U), Клоески разложувањe, QR разложување за неквадратни матрици. Итеративните методи како што се Јакоби методот, Гаус-Сејдел метод, последователна над-релаксација и методот на коњугиран градиен најчесто се користат за поголеми системи. Алгоритмите за наоѓање на корени се користат за решавање на нелинеарни равенки (тие се така наречени затоа што коренот на функцијата е аргумент за кој вредноста на функцијата е нула). Ако функцијата е диференцијабилна и изводот е познат тогаш Њутновиот метод е популарен избор за решавање. Линеаризацијата е уште една техника за решавање на нелинеарни равенки.

Наоѓање на сопствени вредности или сингуларни вредности на даден проблем

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

Оптимизација

Оптимизирачките проблеми бараат точка во која дадената функција е достигнува максимална или минимална вредност. Често точката во која што се достигнува минимум или максимум исто така мора да задоволува некои ограничувања. Полето на оптимизација се дели на неколку подобласти, во зависност од формата на функцијата на целта и од ограничувањата. На пример, линеарното програмирање е такво што функција на целта и ограничувањата се линеарни. Познат метод во линеарното програмирање е Симплекс алгоритам (метод). Методот на Лагранжови множители може да биде користен за редуцирање на оптимизирачки проблеми со ограничување, до оптимизирачки проблеми без ограничување.

Диференцијални равенки

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

Софтвер

Од крајот на ХХ век повеќето алгоритми од нумеричка анализа се имплементираат во различни програмски јазици. Netlib-библиотеката содржи различни колекции на софтвер рутини за нумерички проблем, најмногу во FORTRAN и C. Комерцијалните производи имплементираат многу различни нумерички алгоритми вклучувајќи ги и IMSL и NAG библиотеките; бесплатен начин е GNU научната библиотека. Постојат неколку популарни нумерички компјутерски апликации како што се MATLAB , TK Solver, S-PLUS, Lab View i IDL како подобар од бесплатните и отворени алтернативни извори како што се Free MAT, Scilab, GNU Oktave, (слично како MATLAB), IT ++ (C++ библиотека), R (слично на S-PLUS) и одредени варијанти на Пајтон(Python). Перформансите значително варираат во голема мера: кога векторските и матричните операции се најчесто брзи, скаларните јамки може да се разликуваат по брзина од повеќе од еден ред на големина. Многу системи за компјутерска алгебра како Mathematica имаат достапност на аритметика со произволна прецизност која што може да обезбеди повеќе точни резултати. Исто така секој софтверот за табеларни пресметувања (како MS Excel) може да се користи за решавање на едноставни проблеми поврзани со нумеричката анализа.

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

Еден од најчестите проблеми со кои се сретнуваме во нумеричката анализа е пресметување на вредности на Нумеричката интеграција во некои случаи е позната како нумеричка квадратура. Познатите методи користат една од Њутн-Котесови формули (како правило на средна точка или Симсоново правило) или Гаусова квадратура. Тие методи се потпираат на стратегијата ,,раздели па владеј,, , т.ш интегралот на релативно голем интервал се дели на повеќе интеграли на мали интервали. Во случаите на голем број величини, каде тие методи се недопустливо скапи и во поглед на компјутерските барања, се приоѓа на примена на Монте-Карловиот или Квази Монте-Карловиот метод или кај умерено голем број величини, се применува методот на ретка мрежа.

Методите на ретки мрежи се множество од нумерички техники коишто претставуваат, интегрираат или интерполираат високо димензионални функции. Тие првично биле развиени од страна на рускиот математичар Сергеј Смолак, ученик на Лазар Листерник, и тие се базираат на конструкција на “редок” тензорски производ. Компјутерските алгоритми за ефикасно имплементирање на таквите мрежи подоцна биле развиени од страна на Мајкл Грибл и Кристоф Зенгер. Две основни методи на нумеричката интеграција се: проширената трапезна формула и проширената Симсонова формула. Кај проширената трапезна формула, интервалот на интеграција [a,b] се дели на n-подинтервали со следнава ознака: а=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) на тој интервал. Покрај вообичаената постапка на еквидистантна поделба, т.е xi+1-xi=(b-a)/n , со собирање на плоштината на трапезите конструирани над сите интервални поделби добиваме трапезна формула:

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

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

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

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

Нумеричко решавање на диференцијални равенки

Во нумеричката анализа спаѓаат и методите кои бараат нумеричко апроксимативно решение на диференцијални равенки со зададени почетни услови, т.н. ,,Кошиев проблем,,. Развиени се методи за нумеричко решавање на обични, но и парцијални диференцијални равенки. Две основни методи се Ојлеровата метода и фамилијата Рунге-Кута методи.

Применета математика

За ефикасно решение за проблемот на движење на автомобил по одредена рута, потребна е алатка од комбинаторна оптимизација и целобројно програмирање. Применетата математика е гранка од математиката која се занимава со математички методи кои наоѓаат примена во науката, инженерството, бизнисот, информатиката и индустријата. Така применетата математика е комбинација од математичка наука и знаења од специфични области. Терминот ,,применета математика,, исто така опишува професионална специјалност во која математичари работат практични проблеми преку формулирање и проучување со помош на математички модели. Во минатото, практичната примена го мотивирала развојот на математичката теорија, која тогаш станала предмет на проучување на чистата математика, каде се изучуваат апстрактни поими. Активностите во применетата математика се тесно поврзани со истражувањата во чистата математика.

Историја

Нумеричкото решение на равенки за топлина за модели на пумпа користи метод на конечни елементи. Методот на конечни елементи е нумеричка техника за наоѓање на приближни решенија на граничните проблеми кај парцијалните диференцијални равенки. Тој е исто така познат како анализа со конечни елементи. Овој метод работи на тој принцип што даден поголем проблем го дели на помали и поедноставни делови коишто се нарекуваат конечни елементи. Потоа едноставните равенки коишто ги моделираат овие конечни елементи се собираат во поголем систем на равенки кои ја моделираат целата задача. Методот на конечни елементи потоа користи методи од варијационо сметање за да се добие приближно решение со минимизирање на некоја конкретна грешка во функцијата. Историски, применетата математика главно се состои од применета анализа, пред се диференцијални равенки, теорија на апроксимации (широко толкување, вклучувајќи претставување на асимптотски методи, варијациони методи и нумеричка анализа) и применета веројатност. Овие области од математиката директно се врзани за развојот на Њутновата физика, а разликата меѓу математичарите и физичарите не е строго направена пред средината на 19 век. Оваа историја го оставила педагошкото наследство во многу држави: до почетокот на 20 век, предмети како што се класичната механика биле често предавани на катедрата за применета математика на американските универзитети, отколку на катедрите за физика, а механика на флуиди и понатаму се учи на катедрите за применета математика. Квантитативни финансии се учат на катедрите за математика на универзитетите, а математичките финансии се сметаат како целосна гранка од применета математика. Катедрата за инженерство и информатика традиционално користи применета математика.

Поделба

Механиката на флуиди често се смета за гранка на применетата математика. Денеска терминот ,,применета математика,, се користи во широка смисла. Тоа вклучува класични области кои се погоре наведени како и други области кои станале се позначајни во примените. Дури и области како што се теорија на броеви кои се дел од чиста математика сега се важни во апликациите како што се криптографија, иако генерално не се сметаат како дел од применетата математика. Понекогаш терминот ,,применета математика,, се користи за разликување на традиционалната применета математика која се развила од физиката и многуте области од математиката кои денес важат за реални животни проблеми. Не постои консензус за тоа кои се различните гранки на применета математика. Такви категоризации се отежнати заради промени во математиката и науката со тек на времето, а од друга страна универзитетите организираат катедри, курсеви и степени. Многу математичари прават разлика помеѓу ,,применета математика,, која се занимава со математички методи и ,,применета математика,, во рамки на науката и инженерството. Биолог кој користи модел на население и применува познати методи од математика не работи применета математика туку ја користи. Меѓутоа математичките биолози ги поставиле проблемите кои го стимулирале развојот на чистата математика. Математичарите, како што се Поенкаре и Арнолд негираат постоење на ,,применета математика,, и тврдат дека постои само ,,примена на математиката,,. Слично на тоа не-математичарите ја мешаат применетата математика и примените на математиката. Употребата и развојот на математиката за решавање на индустриски проблеми се нарекува ,,индустриска математика,,. Успехот на современите нумерички математички методи и софтвер довел до појава на компјутерска математика, компјутерска наука и компјутерско инженерство, кои користат високи компјутерски перформанси за симулација на појави и решавање на проблеми во науката и инженерството. Тие често се сметаат за интердисциплинарни.

Придобивки

Финансиската математика се занимава со моделирање на финансиски пазари. Историски математиката има најважна примена во природните науки и инженерство. Меѓутоа после Втората светска војна, областите надвор од физичките науки предизвикале создавање на нови области во математиката, како што се теорија на игри и теорија на општествен избор, која настанала од економски причини. Појавата на компјутерите овозможила нови апликации: проучување и користење на новите компјутери и информатика при решавање на проблеми кои се јавуваат во други области на науката (компјутерска наука) како и во компјутерска математика (на пример: теориска математика, компјутерска алгебра, нумеричка анализа). Статистиката веројатно е најраспространета математичка наука која се користи во општествените науки, но и во други области во математиката, посебно во економијата и тоа ги докажува сите нејзини придобивки од употребата во овие дисциплини.

Статус во академските кругови

Академските институции не се унифицирани во начинот на кој ги групираат и прават курсевите, програмите и степените во применетата математика. Во некои универзитети постои една математичка катедра, додека други имаат посебна катедра за применета математика и (чиста) математика. Вообичаено е катедрите за статистика да бидат одвоени во факултетите со постдипломски програми, но многу основни институции сметаат дека статистиката треба да биде под катедрата за математика. Многу програми од применета математика (за разлика од катедрите), се состојат од курсеви на заеднички факултети. Некои програми во областа на применета математика бараат малку или не бараат воопшто курсеви надвор од математика, додека други значајни курсеви бараат примена во одредена област. Од некои аспекти, оваа разлика ја отсликува разликата помеѓу ,,примена на математиката,, и ,,применета математика,,. Некои универзитети во Обединетото кралство имаат катедри за применета математика и теоретска физика, но сега многу поретко имаат одвоени катедри за чиста и применета математика. Значаен исклучок е катедрата за применета математика и теоретска физика на Универзитетот во Кембриџ во Обединетото Кралство. Универзитетите со посебни катедри за применета математика почнувајќи од Универзитетот Браун во САД, кој има голем отсек за применета математика и кој нуди дипломи до ниво на докторат, до Универзитетот Санта Клара во САД, кој нуди само мастер студии во применета математика. Универзитетот Бригам Јанг во САД, исто така нуди применета и компјутерска програма која му овозможува на студентот да дипломира математика, со акцент на применета математика. Студентите со оваа програма имаат уште една можност за учење (информатика, инженерство, физика, чиста математика и.т.н) како би ги дополниле своите вештини за применета математика.

Научни дисциплини од други области кои граничат со применета математика

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

Компјутерски науки

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

Информатика

Информатиката се потпира на логика, алгебра и комбинаторика.

Операциони истражувања и менаџмент во науките

Операционите истражувања и менаџментот во науките најчесто се учат на факултетите за технички науки, бизнис и јавна aдминистрација.

Статистика

Применетата математика има значајно преклопување со статистиката како дисциплина. Статистичките теоретичари ги проучуваат и подобруваат статистичките процедури со математика, а статистичките истражувања често се занимаваат со прашања од математика. Статистичката теорија се потпира на веројатноста и теоријата на одлучување, а интензивно користи компјутерска наука, анализа и оптимизација; за проектирање на експерименти, статистичарите користат алгебра и комбинаторен дизајн. Математичарите кои работат во областа на применета математика и статистичарите често работат на катедрите за математички науки (посебно на вишите школи и помалите универзитети).

Актуарска математика

Актуарската математика применува веројатност, статистика и економска теорија за проценка на ризикот во осигурувањето, финансиите и другите индустрии и професии.

Математичка економија

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

Други дисциплини

Линијата помеѓу применетата математика и одделни области на примена често е замаглена. Многу универзитети предаваат математички и статистички курсеви надвор од одговорните катедри, вклучувајќи бизнис, инженерство, физика, хемија, билогија, информатика, компјутерска наука и математичка физика.

Поврзаност со индустрија

Кај нас во Македонија со негување на подмладок кој би ја изучувал применетата математика и дугите технички науки, аматерски се занимава Сојузот на здруженија за техничка култура во стопанството ,,Народна техника,,. Учениците од основните и средните училишта имаат можност да учествуваат на натпревари што ги организира ,,Народна техника,, со свои изработки така што ги зголемуваат своите знаења од применета математика и други дисциплини, учат од другите, и другите од нив. Здружението за индустрија и применетата математика (SIAM) во САД е професионално здружение посветено на промовирање на интеракцијата помеѓу математиката и другите научни и технички заедници. Покрај организирањето и спонзорирањето на бројни конференции SIAM е и главен издавач на списанија и книги кои се користат во применета математика.

Математичка оптимизација

Во математиката, компјутерските науки и истражувачките активности, математичката оптимизација, (алтернативно позната и како математичко програмирање или едноставно оптимизација) е избор на најдобриот елемент (во однос на некои критериуми) од множество на достапни опции. Во наједноставен случај, оптимизацијата се состои од максимизирање и минимизирање на реална функција од страна на систематски избрани вредности во рамките на едно дозволено множество од пресметани вредности на фукцијата. Генерално оптимизациската теорија и техника е една голема област од применетата математика. Поопшто, оптимизацијата вклучува изнаоѓање на ,,најдобрата достапна,, вредност на некоја функција на целта, дефинирана во домен (или input), вклучувајќи различни видови на функција на целта и различни видови на домени.

Оптимизациски проблем

Еден оптимизациски проблем може да се претстави на следниов начин: Даденa e функција f: A → R од множеството А во множеството реални броеви, се бара елемент x0 од А таков што f(x0) ≤ f(x) за сите x кои припаѓаат на А (минимум) или таков што f(x0) ≥ f(x) за сите x кои и припаѓаат на А ( максимум). Ваквата формулација е наречена оптимизациски проблем или математичко-програмски проблем (термин кој не е директно поврзан со компјутерското програмирање, но сеуште се користи како на пример во линеарното програмирање). Многу теоретски и реални проблеми можат да се моделираат во овие рамки. Проблемите кои се формулирани користејќи ја оваа техника, а се од полето на физиката и компјутерите може да се однесуваат на техниките за минимизирање на енергијата, односно вредноста на функцијата f која ја претставува енергијата во системот кој ќе биде моделиран. Типично, А е некое подмножество на Евклидски простор Rn, често претставен со множество на ограничувања, што елементите на А мора да ги задоволуваат. Доменот на f е наречен простор за пребарување или множество од избори, додека елементите на А се наречени ,,кандидати за решенија,, или допустливи решенија. Функцијата f се именува на повеќе начини, функција на целта, функција на загуба, функција на трошоци (минимизација), алатка функција, функција на добивка (максимизација) или во некои полиња, енергетска функција, функција на енергијата. Допустливото решение што ја минимизира (или максимизира, ако тоа е целта) функцијата на целта е нареченo оптимaлно решение. Во математиката, конвенционалните проблеми на оптимизација вообичаено се наведени во условите изразени преку термини за минимизација. Поопшто земено, доколку и функцијата на целта и множеството на допустливи решенија не се конвексни во минимизацискиот проблем, можат да постојат неколку локални минимуми. Локалниот минимум x* е дефиниран како точка за која постои некој број δ > 0 така што за сите x за кои што:

    || x-x* || ≤ δ 

Неравенството:

    f(x*  ) ≤  f(x)

важи, односно, за некоја околина околу x* сите вредности на функцијата се поголеми или еднакви на функциската вредност на таа точка. Локалните максимуми се дефинираат на сличен начин. Додека локалниот минимум е барем исто толку добар колку и околните точки, глобалниот минимум е барем исто толку добар како и секоја допустлива точка. За конвексен проблем, ако постои локален минимум кој е внатрешен (не е на крајот од множестото на допустливи точки) тој е исто така и глобален минимум, но неконвексниот проблем може да има повеќе од еден локален минимум од кои не мора сите да бидат глобални минимуми. Голем број на алгоритми предложени за решавање на неконвексни проблеми вклучувајќи ги најголемиот број на комерцијално достапни решeнија не можат да направат разлика помеѓу локалното оптимално реашение, па ќе го третираат претходното како вистинско решение за првобитниот проблем. Глобалното оптимизирање е гранка на применетата математика и нумеричката анализа која се занимава со развојот на детерминистичките алгоритми коишто се способни да гарантираат конвергенција во одредено време на вистинското решение на неконвексниот проблем.

Оптимизациските проблеми често се изрази со специјална нотација

Вредноста на минимумот и максимумот на функцијата: Да ја земеме во предвид следнава формула: min┬(x∈R)⁡(x^2+1)

Ова ја означува минималната вредност на функцијата на целта x2 + 1, кога се избира x од множество на реални броеви. Минималната вредност во овој случај е 1, ако x=0. Слично, формулата : max┬(x∈R)⁡2x

ја бара максимална вредност на функцијата на целта 2x, каде што x може да биде било кој реален број. Во овој случај нема таква максимална вредност затоа што функција на целта е неограничена, така што одговорот е ,,бесконечност,, или ,,недефиниранa вредност,,.

Оптимални влезни (input) аргументи:

Да ја разгледаме следнава формула:

аrgmin┬(x∈(-∞,├ -1] )⁡x^2+1

Односно еквивалентно на:

arg min┬x⁡〖x^2+1 ,т.ш.∶ x∈(-∞,├ -1] ┤〗 Ова ја претставува вредноста (или вредностите) на аргументот x во интервалот (-∞,├ -1] ┤ што ја минимизира (или ги минимизира) функцијата на целта x^2+1 (вистинската најмала вредност на функцијата не е она што проблемот го бара). Во овој случај одговорот е x= -1, поради тоа што x= 0 е невозможно односно не припаѓа на даденото множество. Слично, 〖argmax〗┬(x∈[-5,5],y∈R)⁡〖x cos⁡(y)〗 или еквивалентно 〖argmax〗┬(x,y)⁡〖x cos⁡(y)〗  ; т.ш x∈[-5,5],y∈R го претставува подредениот пар (или паровите) (x,y), кој ја максимизира (или ги максимизира) вредноста на функцијата на целта xcos(y), со зададените ограничувања х да лежи во интервалот [-5,5], (повторно вистинската максимална вредност на функцијата во формулава не е важна). Во овој случај, решенијата се подредените парови (5, 2kπ) и (-5, (2k+1)π) каде што k прима вредност на цел број.

Историја

Ферма и Лагранж пронашле формула базирана на пресметки за идентификација на оптимумот, додека Њутн и Гаус предложиле итеративни методи за придвижување кон оптимумот. Терминот линерано програмирање за одредени оптимизациски случаи се должи на Џорџ Б. Данциг, иако голем дел од теоријата била развиена од страна на Леонид Канторович 1939 г. (Програмирањето во овој контекст не се однесува на компјутерско програмирање, туку потекнува од употребата на зборот програмирање од страна на Американската војска што се однесува на предложените тренинзи за логичко распоредување кои Данциг ги проучувал во тоа време). Данциг го објавил Симплекс алгоритмот во 1947, а Џон фон Нојман ја развил теоријата за дуалност истата година.

Поважни гранки

Конвексното програмирање ги проучува случаите кога функцијата на целта е конвексна (минимизација) или конкавна (максимизација) и допустливото множество е конвексно. Ова може да се разгледува и како специјален случај на нелинеарно програмирање или како генерализација на линеарното или конвексното квадратно програмирање. Линеарното програмирање како тип на конвексно програмирање, ги проучува случаите во кои функцијата на целта f е линеарна и ограничувањата се дадени со линеарни равенства и неравенства. Таквото множество е наречено полихедрон или политоп ако е ограничено. Конусното програмирање од втор ред вклучува одредени типови на квадратно програмирање. Семидефинитно програмирање е подгранка на конвексната оптимизација каде основните променливи се семидефинитни матрици. Тоа е генерализација на линеарното и конвексното квадратно програмирање. Геометриското програмирање е техника со која ограничувањата во облик на неравенства изразени како полиноми и ограничувњата ограничувањата во облик на равенства изразени како мономи, да можат да се трансформираат во конвексна програма. Целобројното програмирање го проучува линеарното програмирање во кое некои или сите променливи се ограничени да примаат целобројни вредности. Ова не е конвексно, и обично е многу потешко отколку вообичаеното линеарно програмирање. Квадратното програмирање е такво што и дозволува на функцијата на целта има квадратни членови, додека допустливото множество мора да биде одредено со линеарни равенстава и неравенства. За специфични форми на квадратните членови односно, ова е тип на конвексно програмирање. Дробно- рационално програмирање ја проучува оптимизацијата на количникот (односот) на две нелинеарни функции. Специјалната класа на конкавни дробно-рационални програми може да биде трансформирана во конвексен оптимизациски проблем. Нелинеарното програмирање ги проучува општите случaи во кои функцијата на целта содржи нелинеарни делови. Ова може, а и не мора да биде конвексна програма. Главно, дали програмата е конвексна или не влијае врз потешкотиите при решавањето на проблемот. Стохастичкото програмирање ги проучува случаевите во кои некои од ограничувањата или параметрите зависат од случајни променливи. Робусното програмирање е, како и стохастичкото, обид да се опфатат неодреденостите во податоците кои подлежат на оптимизацискиот проблем. Робусната оптимизација тежнее да најде решенија што се точни за сите можни реaлизации на променливите. Комбинаторската оптимизација се занимава со проблемите каде што множеството од возможни решенија е дискретно, или може да се сведе на едно дискретно множество од решенија. Стохастичката оптимизација користи случајна функција на пребарување или случајни влезни податоци во процесот на пребарување. Бескрајно-димензионалната оптимизација проучува случаеви кога множеството допустливи решенија е подмножество на бескрајно-димензионалниот простор, како што е просторот на функциите. Хевристиката и метахевристиката не тргнуваат од претпоставките дека проблемот може да биде оптимизиран. Обично, хевристиката не гарантира дека ќе се изнајде некое оптимално решение. Од друга страна, хевристиката се користи за да се најдат приближните решенија на многу комплицирани проблеми. ,,Сатисфакција на ограничувања,, проучува случаи во кои функцијата на целта f е константна (ова се користи во вештачката интелигенција, особено во автоматизираното размислување). Програмирање со ограничувања е парадигма за програмирање при што односите меѓу променливите се сведуваат во форма на ограничувања. Динамичното програмирање го проучува случајот во кој оптималната стратегија е заснована на делење на проблемот во помали подгрупи-подпроблеми. Равенките коишто ги објаснуваат врските меѓу овие подпроблеми се викаат Белманови равенки. Математичкото програмирање со урамнотежени ограничувања е всушност она во кое ограничувањето вклучува неравенства со варијации или комплементарност.

Мулти-модална оптимизација

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

Класификација на критичните точки и екстреми

Физибилити проблем

Физибилити проблемот, или поточно проблемот на допустливост, е проблемот на пронаоѓање на било кое допустливо решение воопшто, без оглед на неговата вредност на функцијата на целта. Ова може да се смета како посебен случај на математичката оптимизација каде што вредноста на функцијата на целта е иста за секое решение, и на тој начин секое решение е оптимално. Многу оптимизациски алгоритми треба да започнат од допустлива точка. Еден начин да се добие таква точка е да се олабават физибилити условите преку користење на слаба променлива, т.ш било која појдовна точка да е допустлива. Потоа се намалува слабата променлива додека вредноста стане нула или негативна.

Постоење

Теоремата на екстремна вредност на Карл Вајерштрас наведува дека непрекината реално-вредносна функција на компактно множество ја достигнува својата максимална и минимална вредност.

Потребни услови за оптималност

Една од теоремите на Ферма наведува дека најголемата вредност на проблеми без ограничување се наоѓа во стационарните точки, каде што првиот извод или градиент на функцијата на целта е нула. Поопшто, тие може да се најдат во критични точки, каде што првиот извод или градиент на функцијата на целта е нула или е недефиниран, или на границата на поставениот домен. Равенката (или множеството на равенки) која наведува дека првиот извод е еднаков на нула во внатрешен оптимум се нарекува ,,состојба од прв ред,, или збир на услови од прв ред. Оптимум на проблемите ограничени со равенства може да се најде преку Лагранжовиот метод на мултупликатор. Оптимум на проблемите ограничени со равенства или неравенства може да се најде со помош на Каруш-Кун-Такер условите.

Доволни услови за оптималност

Додека тестот на првиот извод идентификува точки кои би можеле да се екстремни, овој тест не прави разлика помеѓу точка што е минимум од точка што е максимум или точка која не претставува ниту минимум ниту максимум. Кога функцијата на целта е два пати диференцијабилна, овие случаи можат да се разликуваат преку проверка на вториот извод или матрицата на вториот извод ( наречена Хесеова матрица) кај проблеми без ограничувања, или матрицата на вториот извод на функција на целта и ограничувањата наречена ограничена Хесеова матрица кај проблеми со ограничување. Условите кои ги разликуваат максимумот или минимумот од другите стационарни точки се нарекуват ,,услови од втор ред,,. Ако решението кое е кандидат ги исполнува условите од прв ред, тогаш исполнувањето на условите од втор ред е доволно да се утврди барем локалната оптималност.

Чувствителност и континуитет на оптимумот

Писмо - Теоремата опишува како вредноста на оптимално решение се менува кога основниот параметар ќе се промени. Процесот на пресметување на оваа промена се нарекува компаративна статика. Теоремата за Максимум на Клод-Берже (1963) ја опишува непрекинатоста на оптималното решение како функција од основните (клучните) параметри.

Пресметување на оптимизација

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

Tехники за пресметување на оптимизација

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

Оптимизациски алгоритми

  • Симплекс алгоритам од Џорџ Данциг, наменет за линеарно програмирање
  • Проширување на симплекс алгоритмот, за квадратно програмирање и за линеарно-дробно-рационално програмирање
  • Варијанти на симплекс алгоритам кои се особено погодни за оптимизација на мрежа
  • Комбинаторни алгоритми