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

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

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

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

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

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

Нумеричка интеграција се заснива на интеграцији интерполационих полинома. Нпр. уколико се жели да се нађе неки одређени интеграл, може се послужити Њутн-Лајбницовом формулом. Међутим, уколико је функција дата табелом својих вредности у чворовима, или ако се њена примитивна функција не може изразити преко елементарних функција, тада се могу применити нумерички методи интеграције. Формуле преко којих се врши нумеричко израчунавање једноструких интеграла се називају квадратурне формуле.

Историја

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

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

Стара метода тражења геометријске средине

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

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

Површина сегмента параболе

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

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

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

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

Дон Волис је „алгебризирао” овај метод: написао је у својим Arithmetica Infinitorum (1656) серијама оно што се данас зове одређеним интегралом, те израчунао њихове вредности. Ајзак Бароу и Џејмс Грегори су направили даљи напредак: квадратуре за неке алгебарске кривуље и спирале. Кристијан Хајгенс је успешно извео квадратуре неких „материјала револуције”.

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

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

Разлози за нумеричку интеграцију

Постоји више разлога зашто се користи нумеричка интеграција.

• Функција која се интегрише f(x) може бити позната само на појединим местима, што се ради узимањем узорка. Неки уграђени рачунари и остале рачунарске апликације стога користе нумеричку интеграцију из тог разлога.
• Формула за функцију која се интегрише може бити позната, али може бити тешко или немогуће наћи антидеривацију која је елементарна функција. Један примјер је функција f(x) = exp(−x²), чија антидеривација (функција грешке пута константа) се не може написати у елементарној форми.
• Могуће је наћи антидеривацију симболично, али је много једноставније наћи нумеричку апроскимацију него рачунати антидеривацију (антиизвод). Ово може бити случај ако је антидеривација дата као неограничени низ производа, или ако би прорачун захтевао специјалне функције које нису доступне рачунарима.

Методе за једнодимензионе интеграле

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

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

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

Квадратурна правила базирана на интерполацији функција

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

Илустрација квадратног правила.

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

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

Илустрација трапезног правила.

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

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

Илустрација Симпсоновог правила.

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

$\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.

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

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

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

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

Прилагодљиви алгоритми

Ако f(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

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

Метода екстраполације

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

Конзервативна (а приори) процјена грешке

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

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

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

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

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

$\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|$ (**)

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

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

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

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

Интеграли са бесконачним интервалима

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

$\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,$

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

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

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

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

Вишедимензиони интеграли

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

Монте Карло

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

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

Литература

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

Спољашње везе

• Интегратион: Бацкгроунд, Симулатионс, етц. ат Холистиц Нумерицал Метходс Институте
• Лобатто Qуадратуре фром Wолфрам Матхwорлд
• Лобатто qуадратуре формула фром Енцyцлопедиа оф Матхематицс
• Имплементатионс оф манy qуадратуре анд цубатуре формулае wитхин тхе фрее Трацкер Цомпонент Либрарy.