Нумеричка интеграција

У нумерици, нумеричка интеграција се састоји од велике породице алгоритама за рачунање нумеричке вриједности одређеног интеграла, а термин је такођер кориштен да опише нумеричко рјешење диференцијалне једначине. Термин нумеричка квадратура је мање-више синоним за нумеричку интеграцију, поготово за једнодимензионалне интеграле. Нумеричка интеграција у више димензија се описује као кубатура,^[1] иако се изразом квадратура подразумијева и вишедимензиона интеграција.

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

${\displaystyle I=\int _{a}^{b}\!f(x)\,dx}$

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

Главни чланак: Квадратура (математика)

Квадратура је математички хисторијски појам, а значи рачунање површине. Квадратурни проблеми су били главни задаци који су задавани као извор за математичку анализу. Математичари Старе Грчке, према Питагориној доктрини, схватили су рачунање површине као процес конструкције геометријског квадрата који има једнаку површину (квадрирање). То је разлог зашто је процес назван квадратура. Напримјер: квадратура круга, хипократов мјесец и квадратура параболе. Ова конструкција мора бити изведена једино употребом шестара и лењира.

За квадратуру правоугаоника са страницама а и б потребно је конструисати квадрат са страницом: ${\displaystyle x={\sqrt {ab}}}$

У ову сврху, могуће је користити сљедећу чињеницу: ако се нацрта круг са збиром страница а и б као пречник, онда је висина БХ (са тачке њиховог додира до пресјецања са кругом) једнака њиховој геометријској средини. Једнака геометријска конструкција рјешава проблем квадратуре паралелограма и троугла.

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

• Површина лопте је једнака четверострукој површини великог круга ове лопте.
• Површина дијела параболе одсјечена правцем је 4/3 површине од троугла који је уписан у овај сегмент.

За доказ резултата, Архимед је користио методу Еудокса.

У средњовјековној Европи, квадратура је значила прорачун површине користећи било коју методу. Чешће је метода недјељивости кориштена; мање је ригорозна, а једноставнија и добра. Помоћу ње, Галилео Галилеи и Гиллес де Робервал су нашли површину свода циклоиде, Грéгоире де Саинт-Винцент је истражио површину испод хиперболе (Опус Геометрицум, 1647.), а Алпхонсе Антонио де Сараса, де Саинт-Винцентов ученик и коментатор, је успоставио релацију ове површине са логаритмима.

Јохн Wаллис је "алгебризирао" овај метод: написао је у својим Аритхметица Инфиниторум (1656.) серијама оно што се данас зове одређеним интегралом, те израчунао њихове вриједности. Исаац Барроw и Јамес Грегорy су направили даљи напредак: квадратуре за неке алгебарске кривуље и спирале. Цхристиаан Хуyгенс је успјешно извео квадратуре неких "материјала револуције".

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

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

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

Формула за функцију која се интегрише може бити позната, али може бити тешко или немогуће наћи антидеривацију која је елементарна функција. Један примјер је функција ф(x) = еxп(−x²), антидеривација која се не може написати у елементарној форми.

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

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

Важан дио анализе било које нумеричке интеграционе методе је проучавање понашања грешке апроксимације као функција броја процјене интегранда. Метода која има малу грешку за мали број процјена је често сматрана супериорном. Смањењем броја процјена интегранда, смањује се и број кориштених аритметичких операција, те се смањује укупна грешка прорачуна. Такође, свака процјена узима вријеме, а интегранд може бити својевољно компликован.

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

Велики број квадратурних правила се може наћи извођењем функција које су једноставне за интегрирање. Најчешће функције које се интерполирају су полиноми.

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

${\displaystyle \int _{a}^{b}f(x)\,dx\approx (b-a)\,f\left({\frac {a+b}{2}}\right)}$

Интерполацијска функција може бити полином првог степена која пролази кроз тачке: (а, ф(а)) и (б, ф(б)). Ово се зове трапезно правило.

${\displaystyle \int _{a}^{b}f(x)\,dx\approx (b-a)\,{\frac {f(a)+f(b)}{2}}.}$

За било које од ових правила се може направити прецизнија апроксимација прекидањем интервала [а, б] на већи број подинтервала, рачунајући апроксимацију за сваки подинтервал, те сабирајући све у један резултат. Ово се зове композитно правило, проширено правило или итеративно правило. Напримјер, композитно трапезно правило има слиједећи облик:

${\displaystyle \int _{a}^{b}f(x)\,dx\approx {\frac {b-a}{n}}\left({f(a) \over 2}+\sum _{k=1}^{n-1}\left(f\left(a+k{\frac {b-a}{n}}\right)\right)+{f(b) \over 2}\right)}$

гдје подинтервали имају облик [к х, (к+1) х], са х = (б−а)/н и к = 0, 1, 2, ..., н−1.

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

Квадратурна правила са једнако размакнутим тачкама имају веома погодну особину гнијежђења. Одговарајуће правило са сваким подподијељеним интервалом садржи све тренутне тачке, па ове вриједности интегранда могу бити поново искориштене.

Ако се допусти да интервали између интерполационих тачака варирају, онда се налази нова група квадратурних формула, као што је Гаусова квадратурна формула. Гаусово квадратурно правило је још прецизније од Неwтон-Цотесовог правила које захтјева једнак број итерација ако је функција која се интегрише (интегранд) глатка кривуља (нпр, ако је довољно диференцијабилна). Остале квадратурне методе са варијацијом интервала укључују Цленсхаw–Цуртис квадратурне методе (такођер зване Фејéр кваратуре), које се гнијезде.

Гаусова квадратурна правила немају особину гнијежђења, али Гаусс–Кронрод квадратурне формуле имају.

Ако ф(x) нема пуно извода на свим тачкама, или ако изводи постану огромни, онда Гаусова квадратура је често недовољна. У том случају, алгоритам испод ће боље урадити задатак:

def racunanje_odredjenog_integrala(f, initial_step_size):
    '''
    Ovaj algoritam računa određeni integral (onaj koji ima granice)
    funkcije od 0 do 1, birajući manje korake kod problematičnih
    tačaka.
    '''
    x = 0.0
    h = initial_step_size
    akumulator= 0.0
    while x < 1.0:
        if x + h > 1.0:
            h = 1.0 - x
        quad_this_step =
        if error_too_big_in_quadrature_of_over_range(f, [x,x+h]):
            h = make_h_smaller(h)
        else:
            akumulator+= quadrature_of_f_over_range(f, [x,x+h])
            x += h
            if error_too_small_in_quadrature_of_over_range(f, [x,x+h]):
                h = make_h_larger(h) # Izbjegavanje dangubljenja na malim koracima.
    return akumulator

Неки детаљи алгоритма захтјевају пажљив приступ. За више случајева, проналазак грешке квадратуре на интервалу за функцију ф(x) није очита. Једна позната солуција је да се користе два правила квадратура и кориштењем разлике се може процијенити грешка квадратуре. Чест проблем је одлучити шта означава "премало" или "превелико". Локални критериј за "превелико" је да квадратурна грешка не смије бити већа од т · х, гдје је т, реални број, толеранција која се жели подесити за глобалну грешку. Опет, ако је х већ мало, онда може бити беспотребно правити га чак мањим иако је квадратурна грешка велика. Глобални критериј је да збир грешака на свим интервалима буде мањи од т. Овај тип анализе грешке се често назива "постериори" зато што се након сваке процјене рачуна и грешка.

Прецизност квадратурног правила код Неwтон-Цотес типа је углавном функција броја на тачкама процене. Резултат је често више поуздан кад се број тачака повећа, или, еквивалентно, кад се размаци између тачака смање. Намеће се питање какав би резултат био када би размаци међу тачкама били једнаки нула. Ово се може одговорити екстраполацијом резултата од два до н размака користећи убрзавајуће методе као нпр. Рицхардсонове екстраполације. Екстраполациона функција може бити полином или рационална функција. Екстраполационе методе су описање детаљније у од стране Стоера и Булирсцха (Секција 3.4) и имплементиране су у више метода у QУАДПАЦК библиотеци.

Ако се пусти да ф има ограничен први извод на затвореном интервалу [а,б]. Теорема средње вриједности за ф, гдје је x < б, даје:

${\displaystyle (x-a)f'(v_{x})=f(x)-f(a)\,}$

за неке в_x из интервала [а,x] зависне од x. Ако се интегрише по x од а до б на обје стране и узму апсолутне вриједности, добије се:

${\displaystyle \left|\int _{a}^{b}f(x)\,dx-(b-a)f(a)\right|=\left|\int _{a}^{b}(x-a)f'(v_{x})\,dx\right|}$ (*)

Може се даље апроксимирати интеграл на десној страни неједнакости убацујући апсолутну вриједност у интегранд и смјеном слова у ф' према горњој граници:

${\displaystyle \left|\int _{a}^{b}f(x)\,dx-(b-a)f(a)\right|\leq {(b-a)^{2} \over 2}\sup _{a\leq x\leq b}\left|f'(x)\right|}$ (**)

Ако апроксимирамо интеграл ∫_а^б ф(x) дx са квадратурним правилом (б − а)ф(а), наша грешка није већа од оне на десној страни код (**). Ово се може претворити у анализу грешке за Риеманнову суму (*), давајући горњу границу од

${\displaystyle {n^{-1} \over 2}\sup _{0\leq x\leq 1}\left|f'(x)\right|}$

за изражавање грешке од одређене апроксимације. (Коментар: У овом примјеру је ово грешка која је израчуната за примјер ${\displaystyle f(x)=x}$.) Користећи више извода и поправљања квадратуре може се добити иста грешка анализе користећи се Таyлоровим редовима (користећи парцијалну суму са остатком) за ф. Ова анализа грешке даје стриктну горњу границу грешке ако постоје изводи за ф.

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

Постоји неколико метода за апроксимацију интеграције код неограничених интервала. Уобичајена техника укључује посебно изведена квадратурна правила, попут Гаусс-Хермите квадратура за интеграле на читавој линији реалних бројева и Гаусс-Лагуерре квадратуре за интеграле на позитивним реалним бројевима.^[2] Монте Царло методе могу такођер бити кориштене, или мијењањем промјенљивих на коначан интервал. То се може представити овако за неограничене интервале с обје стране:

${\displaystyle \int _{-\infty }^{+\infty }f(x)\,dx=\int _{-1}^{+1}f\left({\frac {t}{1-t^{2}}}\right){\frac {1+t^{2}}{(1-t^{2})^{2}}}\,dt,}$

или полу-бесконачне интервале:

${\displaystyle \int _{a}^{+\infty }f(x)\,dx=\int _{0}^{1}f\left(a+{\frac {t}{1-t}}\right){\frac {dt}{(1-t)^{2}}}}$

${\displaystyle \int _{-\infty }^{a}f(x)\,dx=\int _{0}^{1}f\left(a-{\frac {1-t}{t}}\right){\frac {dt}{t^{2}}}}$

као могуће трансформације.

Квадратурна правила су која су разматрана досад су прављена с циљем да рачунају једнодимензионе интеграле. За рачунање истих у више димензија, један приступ је изразити вишеструки интеграл као поновљени једнодимензиони интеграл користећи се Фубинијевом теоремом. Овај приступ тражи функцијске прорачуне да расту експоненцијално како се повећава број димензија. Двије методе су познате за постизање овога тзв. проклетства димензионалности.

Методе Монте Царла и квази методе истог су једноставне за користити на вишедимензионим интегралима и могу добивати већу прецизност за исти број од прорачуна функција него методом поновљених интеграција користећи се једнодимензионим методама.

Велики број корисних Монте Царло метода су тзв. Марков ланац за Монте Царло алгоритме, који садрже Метрополис-Хастингс алгоритам и Гиббсово узимање узорка.

Спарсове решетке су оригинално развијене од стране Смолyака за квадратуре вишедимензионих функција. Ова метода је увијек базирана на једнодимензионом правилу квадратуре, али обавља више софистицирану комбинацију једноваријантних резултата.

Проблем тражења интеграла:

${\displaystyle F=\int _{a}^{b}f(x)\,dx}$

може бити редуциран на проблем почетне вриједност за уобичајену диференцијалну једначину. Ако је горњи интеграл обиљежен са Ф(x), онда функција Ф задовољава:

${\displaystyle {\frac {dF(x)}{dx}}=f(x),\quad F(a)=0.}$

Методе развијене за уобичајене диференцијалне једначине, као Рунге-Кутта, може бити искориштено на поновљени проблем и за прорачун интеграла. Напримјер, стандардна Рунге-Кутта метода искориштена на диференцијалну једначину креира Симпсоново правило одозго.

Диференцијална једначина Ф ' (x) = ƒ(x) има специфичан облик: десна страна садржи само зависну варијаблу (овдје x) и независну (овдје Ф). Ово поједностављује теорију и алгоритме знатно.

• Нумеричко рјешавање диференцијалних једначина
• Грешка заокруживања (нумерика)
• Трапезно правило

• Пхилип Ј. Давис анд Пхилип Рабиноwитз, Метходс оф Нумерицал Интегратион. - (бос. Методе нумеричке интеграције)
• Георге Е. Форсyтхе, Мицхаел А. Малцолм, анд Цлеве Б. Молер, Цомпутер Метходс фор Матхематицал Цомпутатионс. Енглеwоод Цлиффс, НЈ: Прентице-Халл, 1977. (Погледати Поглавље 5.)
• Пресс, W.Х.; Теуколскy, С.А.; Веттерлинг, W.Т.; Фланнерy, Б.П. (2007), „Цхаптер 4. Интегратион оф Фунцтионс”, Нумерицал Реципес: Тхе Арт оф Сциентифиц Цомпутинг (3рд изд.), Неw Yорк: Цамбридге Университy Пресс, ИСБН 978-0-521-88068-8, архивирано из оригинала на датум 2016-03-04, приступљено 2015-05-17 
• Јосеф Стоер анд Роланд Булирсцх, Интродуцтион то Нумерицал Аналyсис. Неw Yорк: Спрингер-Верлаг, 1980. (Погледати Поглавље 3.)
• Боyер, C. Б., А Хисторy оф Матхематицс, 2нд ед. рев. бy Ута C. Мерзбацх, Неw Yорк: Wилеy, 1989 ИСБН 0-471-09763-2 (1991 пбк ед. ИСБН 0-471-54397-7).
• Евес, Хоwард, Ан Интродуцтион то тхе Хисторy оф Матхематицс, Саундерс, 1990, ИСБН 0-03-029558-0,

• Интеграција: Позадина, симулације, итд. (ен) на Холистиц Нумерицал Метходс Институте

Бесплатан софтвер за нумеричку интеграцију

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

• QУАДПАЦК (дио СЛАТЕЦ-а): опис [1], изворни код [2]. QУАДПАЦК је колекција алгоритама, у Фортрану, за нумеричку интеграцију базирану на Гаусовим квадратурама.
• интералг Архивирано 2012-03-13 на Wаyбацк Мацхине-у: софтвер од ОпенОпт/ФунцДесигнер фрамеwоркса, базиран на анализи интервала, гарантованој прецизности, лиценци: БСД (бесплатан за сваку сврху)
• ГСЛ: Тхе ГНУ Сциентифиц Либрарy (ГСЛ) јесте нумеричка библиотека написана у програмском језику C која пружа велики обим математичких рутина, као Монте Царло интеграција.
• Алгоритми нумеричке интеграције се могу наћи у ГАМС разреду Х2.
• АЛГЛИБ је колекција алгоритама написаних у C# / C++ / Делпхи / Висуал Басиц / итд. за нумеричку интеграцију (укључује Булирсцх-Стоер и Рунге-Кутта интеграторе).
• Цуба Архивирано 2014-04-07 на Wаyбацк Мацхине-у је библиотека бесплатног софтвера од неколико вишедимензионих интеграционих алгоритама.
• Цубатуре код за вишедимензиону интеграцију.
• Сцилаб софтвер отвореног кода под ЦеЦИЛЛ лиценцом (компатибилна са ГПЛ лиценцом), пружа моћне могућности укључујући нумеричку интеграцију.