jump to navigation

Елементарна нумеричка интеграција May 29, 2008

Posted by admin in Информатика, Математика.
Tags: , , , , ,
add a comment

Често се среќаваме со функции кои се многу тешки за аналитичко интегрирање или чиј неопределен интеграл не може да се изрази преку елементарните функции (пример \int_{}^{}e^{-x^2}dx). Функциите кои се интегрираат аналитички се исклучок, а не правило. Постојат повеќе алгоритми кои нумерички ги пресметуваат интегралите, меѓутоа овој запис ќе зборува само за дел од нив. Денес, ваквите пресметки се прават со помош на компјутер, па со секој метод приложена е и функција во програмскиот јазик C која ја нумерички ја интегрира функцијата со прототип

float f(float x);

на истиот интервал. Да претпоставиме дека имаме функција f(x) која сакаме да ја интегрираме на интервалот \left[a,b\right], односно сме заинтересирани за \int_{a}^{b}f(x)dx. Главната логика на алгоритмите е

  1. да се раздели интервалот \left[a,b\right] на повеќе субинтервали
  2. да се пресмета плоштината на секој од овие интервали (помеѓу x-оската и функцијата)
  3. да се соберат сите плоштини

Во оваа статија интервалот \left[a,b\right] ќе го делиме на n еднакви субинтервали од големина h=\frac{b-a}{n}, x_i=a+hi.  Плоштината на секој субинтервал ја пресметуваме со приближување на функцијата со некоја друга која е лесно интеграбилна. Дел од алгоритмите кои користат линеарно приближување се:

  • Правило на правоаголник

Плоштината на секој сегмент \left[x_i,x_{i+1}\right] ја пресметуваме со помош на правоаголник со ширина h и висина f(\frac{x_i+x_{i+1}}{2}), односно P_i=f(\frac{x_i+x_{i+1}}{2})h. 

float i_pravoagolnik(float a, float b, unsigned int n) {
/**
 * Ја интегрира f(x) на интервалот [a,b] a<b
 * користејќи n интервали
 */
 float p=0f, h=(b-a)/n;
 int i;
 for(i=0; i<n; i++) {
          /* не е оптимизирано за кодот да е појасен */
          p += f((a+i*h+a*(i+1)*h)/2)*h
 }

 return p;
}

Нешто попрецизен метод е:

  • Правило на трапез

Како што налага името и сликата – за плоштините на субинтервалите се користи формула на трапез (основи паралелни на y-оската со должина f(x_i) и f(x_{i+1}) и висина h). Односно P_i=\frac{f(x_i)+f(x_{i+1})}{2}h

float i_trapez(float a, float b, unsigned int n) {
/**
 * Ја интегрира f(x) на интервалот [a,b] a<b
 * користејќи n интервали
 */
 float p=0f, h=(b-a)/n;
 int i;
 for(i=0; i<n; i++) {
          /* не е оптимизирано за кодот да е појасен */
          p += ((f(a+i*h)+f(a+(i+1)*h))/2)*h
 }

 return p;
}

Следен чекор е собирање на сите овие интервали, односно \int_{a}^{b}f(x)dx\approx\sum_{i=0}^{n-1}P_i.

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

Кулите од Ханои May 28, 2008

Posted by admin in Математика.
Tags: , , ,
add a comment

Првиот пост на овој блог ќе биде посветен за еден многу познат проблем од доменот на дискретната математика. Се работи за проблемот познат како Tower of Hanoi. Значи, на еден стап имаме N различни по големина дискови и треба да ги префрлиме на друг стап со минимален број на операции, а имаме уште еден помошен стап. Или, како што се гледа на сликата:

undefined

Со k(n) го бележиме минималниот број операции за да се префрлат n дискови. Јасно е дека k(1)=1 и k(2)=2:

  1. горниот диск го префрламе на помошниот стап
  2. долниот диск го префрламе на вториот стап
  3. горниот диск го префрламе од помошниот на вториот стап

За случајот k(3), постапката е слична:

  1. ги префрламе сите дискови освен последниот на помошниот стап = k(2) чекори
  2. го префлраме најголемиот диск на вториот стап = 1 чекор
  3. ги префрламе дисковите од помошниот стап на вториот стап = k(2) чекори

Односно, k(3)=2k(2)+1=7, аналогно k(4)=2k(3)+1=15, k(5)=2k(4)+1=31, а тоа воопштено е k(n)=2k(n-1)+1. Се забележува дека k(n)=2^n-1. По пат на индукција (ќе го презентирам само последниот чекор):

k(n)=2k(n-1)+1=2(2^ {n-1}-1)+1=2^n-1

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