Обчислення визначеного інтеграла

Завдання обчислення певного інтеграла

зустрічається в самих різних додатках. Чисельні методи дозволяють обчислити інтеграл із заданою точністю, зводячи обчислення інтеграла до підсумовування:

Геометрично значення інтеграла задає площу фігури, утвореної графіком підінтегральної функції f (x). Найпростіший чисельний метод - метод прямокутників - обчислює значення інтеграла, як суму площ N прямокутників, у яких основа дорівнює dx, а висота дорівнює значенню підінтегральної функції в точці . При обраному значенні N значення dx і координата обчислюються за такими формулами:

Якщо вибрати N досить великим, то формула (3.12) дає хорошу апроксимацію значення інтеграла. Рис. 3.1 ілюструє сутність методу прямокутників.

Рис.3.1.

Метод прямокутників чисельного обчислення інтеграла

На малюнку N дорівнює двом і наближене значення інтеграла дорівнює сумі площ двох виділених прямокутників. Звичайно ж, при такому малому N важко очікувати гарної апроксимації. Значення N слід істотно збільшити. Але як велике має бути N? Це залежить як від величини інтервалу інтегрування, так і від поведінки функції. Для осцилюючих функцій N може бути дуже велике.

Чисельний метод інтегрування передбачає ітерірованіе по N. Це означає побудову циклу, на кожній ітерації якого значення N збільшується (зазвичай в два рази). Якщо значення обчислених сум на сусідніх ітераціях по модулю відрізняються на величину меншу заданої точності, то ітерірованіе припиняється.

Метод прямокутників хороший тим, що неважко написати реалізацію, в якій на кожному кроці циклу по N значення функції розраховуються тільки в нових точках. Сума, обчислена на попередній ітерації, використовується для обчислення нового значення.

Послідовний алгоритм в цьому випадку має тимчасову складність, задану співвідношенням:

Тут N - це те кінцеве значення, при якому досягається необхідна точність. Цикл ітерірованія по N не вносить додаткової складності обчислення.

Давайте побудуємо реалізацію цього алгоритму. Насамперед поставимо клас, що описує підінтегральної функції:

public delegate double Integral_function (double x);

Всі функції цього класу приймають один аргумент типу double і повертають значення такого ж типу.

Побудуємо тепер клас NewIntegral, що містить різні методи обчислення інтеграла. Ось як виглядає загальна частина цього класу, що містить опис полів класу, методів властивостей і конструктора об'єктів:

/// <summary> /// Обчислення визначеного інтеграла /// різними методами /// </ summary> public class NewIntegral {double a, b; // межі інтегрування Integral_function f; // подинтегральная функція int p; // число сегментів розбиття double eps; // точність обчислення double result; // результат обчислення object locker = new object (); double [] results; public double Result {get {return result; }} /// <summary> /// конструктор /// </ summary> /// <param name = "a"> нижня межа інтегрування </ param> /// <param name = "b"> верхня межа інтегрування </ param> /// <param name = "p"> число сегментів розбиття інтервалу інтегрування </ param> /// <param name = "f"> подинтегральная функція </ param> /// <param name = " eps "> точність обчислення інтеграла </ param> public NewIntegral (double a, double b, int p, Integral_function f, double eps) {this.a = a; this.b = b; this.p = p; this.f = f; this.eps = eps; results = new double [p]; }

Додамо тепер в наш клас метод, який реалізує послідовне обчислення інтеграла за розглянутою вище схемою прямокутників:

/// <summary> /// Послідовний алгоритм /// </ summary> /// <param name = "a"> початок відрізка інтегрування </ param> /// <param name = "b"> кінець відрізка інтегрування </ param> void DefiniteIntegral (double a, double b, out double result) {int n = 2; double dx = (b - a) / 2; double S0 = 0, S = 0; double x = 0; bool success = false; for (int i = 0; i <n; i ++) {x = a + i * dx; S0 + = f (x); } S0 * = dx; while (! success) {n = 2 * n; dx = dx / 2; S = 0; for (int i = 1; i <n; i + = 2) {x = a + i * dx; S + = f (x); } S = S * dx + S0 / 2; if (Math.Abs ​​(S - S0)> eps) S0 = S; else success = true; } Result = S; } Лістинг 3.9. Послідовний алгоритм обчислення інтеграла

Простий і ефективний алгоритм 3.9 повністю реалізує описану вище ідею. Спочатку обчислюється сума при n, рівному 2. Потім в циклі по while здійснюється ітерірованіе по n. На кожній ітерації використовується раніше порахована сума, до якої додаються складові, побудовані для нових точок розбиття відрізка інтегрування.

Зауважте, підінтегральна функція f задана як поле класу.

алгоритм 3.9 простий і ефективний для послідовного виконання, але вимагає модифікації для випадку паралельного виконання. На щастя, він допускає природне розпаралелювання. Більш того, розпаралелювання можна вести на двох рівнях. По-перше, інтервал інтегрування можна розбити на р відрізків і незалежно обчислювати інтеграл на відповідному відрізку. Далі залишиться тільки підсумувати отримані значення. При цьому на кожному відрізку можна використовувати одну і ту ж послідовну версію. Оскільки обсяг необхідної роботи на кожному відрізку зменшується, то при паралельному виконанні можна очікувати зменшення загального обсягу роботи.

Розпаралелювання можна продовжити, якщо замість послідовної версії обчислення інтеграла використовувати версію, распараллелівать процес обчислення суми. Про те, як можна распараллелить кінцеву суму, досить докладно сказано в попередніх розділах цієї глави.

Наведу метод, в якому розпаралелювання ведеться за рахунок розбиття інтервалу інтегрування на p відрізків:

/// <summary> /// Послідовний алгоритм /// Обчислення з розбиттям інтервалу інтегрування /// на p сегментів /// </ summary> public void SequenceIntegralWithSegments () {double dx = (b - a) / p; double start = 0, finish = 0; for (int i = 0; i <p; i ++) {start = a + i * dx; finish = start + dx; DefiniteIntegral (start, finish, out results [i]); } Result = 0; for (int i = 0; i <p; i ++) {result + = results [i]; }} Лістинг 3.10. Послідовний алгоритм з поділом на відрізки

У циклі за кількістю відрізків викликається послідовний алгоритм, що обчислює значення інтеграла на відповідному відрізку. Цей цикл допускає розпаралелювання. При наявності декількох процесорів все вони можуть паралельно обчислювати інтеграл на своєму відрізку інтегрування.

Зауважте, цей варіант алгоритму виявляється переважно і в разі проведення обчислень одним процесором. Причина в тому, що на різних відрізках інтегрування функція може вести себе по-різному. Оскільки для кожного відрізка ефективно підбирається своє число N - число розбиття інтервалу інтегрування в методі прямокутників, то загальний час виконання завдання може бути зменшено.