1 Властивості і структура алгоритму
1.1 Загальний опис алгоритму
Завдання одновимірного чисельного інтегрування полягає в наближеному обчисленні визначеного інтеграла по відрізку: потрібно обчислити
де [math] f (x) [/ math] - інтегрована функція, певна на відрізку [math] [a, b] [/ math].
Чисельне інтегрування оcуществляется за допомогою квадратурних формул - наближених рівностей виду
[Math] I \ approx \ sum \ limits_ ^ n C_i f (x_i). [/ Math]
Сума в правій частині називається квадратурної сумою; різні точки [math] x_i [/ math] відрізка [math] [a, b] [/ math] називаються вузлами, а числа [math] C_i [/ math] - коефіцієнтами квадратурной формули.
Значення квадратурной суми, прийняте за наближене значення інтеграла, залежить від вибору вузлів [math] x_i [/ math] і коефіцієнтів [math] C_i [/ math]. При обчисленні значення квадратурной суми основні витрати часу припадають на обчислення значень підінтегральної функції в вузлах.
Похибкою квадратурної формули називається різниця
Якщо функція [math] f (x) [/ math] така, що [math] R_n (f) = 0 [/ math]. то кажуть, що квадратурная формула точна для функції [math] f (x) [/ math].
Ціле число [math] k \ ge0 [/ math] називається алгебраїчної ступенем точності квадратурної формули, якщо квадратурная формула точна для будь-якого многочлена ступеня не вище [math] k [/ math] і не точна для многочлена ступеня [math] k + 1 [ / math].
Якщо квадратурная формула з [math] n [/ math] вузлами має алгебраїчну ступінь точності [math] k [/ math]. то [math] k \ le 2n-1 [/ math].
Широко відомі квадратурні формули, отримані за допомогою заміни підінтегральної функції [math] f (x) [/ math] алгебраїчним інтерполяційним многочленом, значення якого збігаються зі значеннями функції в [math] n [/ math] вузлах [math] x_i [/ math]; такі квадратурні формули називаються інтерполяційними. Для похибки інтерполяційної квадратурної формули справедлива оцінка
де [math] M_n = \ max \ limits_ | f ^ (x) | [/ math]. [Math] \ omega_n (x) = \ prod \ limits_ ^ n (x-x_i) [/ math].
Якщо інтерполяціонная квадратурная формула з [math] n [/ math] вузлами має алгебраїчну ступінь точності [math] k [/ math]. то [math] k \ ge n-1 [/ math].
1.1.1 Формули Ньютона-Котеса
Формулами Ньютона-Котеса називаються інтерполяційні квадратурні формули, [math] n [/ math] вузлів яких задані рівновіддаленими: [math] x_1 = \ frac2 [/ math] при [math] n = 1 [/ math] і [math] x_i = a + (i-1) \ frac, 1 \ le i \ le n [/ math] при [math] n \ gt1 [/ math].
Свою назву ці формули отримали на згадку того, що вони в досить загальній формі було розглянуто Ісааком Ньютоном, а їх коефіцієнти при [math] 1 \ le n \ le 10 [/ math] були знайдені Роджером Котес.
Найбільш відомими формулами Ньютона-Котеса є формула середніх прямокутників ([math] n = 1 [/ math])
і формула трапецій ([math] n = 2 [/ math])
алгебраїчна ступінь точності кожної з них дорівнює 1, а для їх похибок справедливі оцінки
Формулами Ньютона-Котеса при [math] n = 3 [/ math] і [math] n = 4 [/ math] є формула Сімпсона
яку називають також формулою парабол, і формула трьох восьмих
назва якої походить від коефіцієнта 3/8; алгебраїчна ступінь точності кожної з них дорівнює 3, а для їх похибок справедливі оцінки
Алгебраїчна ступінь точності формули Ньютона-Котеса з [math] n [/ math] вузлами дорівнює [math] n-1 [/ math] при парному [math] n [/ math] і дорівнює [math] n [/ math] при непарному [math] n [/ math].
Коефіцієнти формул Ньютона-Котеса позитивні при [math] 1 \ le n \ le8 [/ math] і [math] n = 10 [/ math]. а при [math] n = 9 [/ math] і [math] n \ ge11 [/ math] серед коефіцієнтів є як позитивні так і негативні.
Позитивність коефіцієнтів квадратурної формули важлива для її практичного застосування. Справа в тому, що при обчисленні інтегральної суми вплив похибок округлення на точність результату тим сильніше, чим більше [math] \ sum \ limits_ ^ n | C_i | [/ math]. Для формул Ньютона-Котеса ця сума необмежено зростає при [math] n \ to \ infty [/ math]. Тому при великих [math] n [/ math] формули Ньютона-Котеса виявляються практично непридатними.
Таким чином, для того щоб використовувати квадратурні формули з великим числом вузлів, потрібно відмовитися або від того, щоб квадратурная формула була інтерполяційної, або від того, щоб вузли задавалися рівновіддаленими.
1.1.2 Складові квадратурні формули
Складовими називаються квадратурні формули, побудова яких здійснюється наступним чином. Відрізок інтегрування [math] [a, b] [/ math] розбивається на [math] m [/ math] відрізків рівної довжини [math] h = \ dfracm [/ math]. Тоді за властивістю адитивності інтеграл може бути обчислений як сума інтегралів по відрізках розбиття. Для наближеного обчислення кожного з доданків цієї суми застосовується одна і та ж квадратурная формула, звана вихідної.
Алгебраїчна ступінь точності складовою квадратурної формули збігається з алгебри ступенем точності вихідної.
Якщо в якості вихідної квадратурной формули вибрати формулу середніх прямокутників, формулу трапецій або формулу Сімпсона, то будуть отримані наступні складові квадратурні формули:
складова формула середніх прямокутників
[Math] I \ approx h \, (\ sum \ limits_ ^ m f (a + ih- \ frac)) [/ math]з числом вузлів [math] m [/ math] і оцінкою похибки
складова формула трапецій
з числом вузлів [math] m + 1 [/ math] і оцінкою похибки
складова формула Сімпсона
[Math] I \ approx \ frac \, (f (a) + f (b) +2 \ sum \ limits_ ^ f (a + ih) +4 \ sum \ limits_ ^ mf (a + ih- \ frac)) [/ math]з числом вузлів [math] 2m + 1 [/ math] і оцінкою похибки
1.1.3 Квадратурні Формули Гауса
Як зазначалося вище, якщо квадратурная формула з [math] n [/ math] вузлами є інтерполяційної, то її алгебраїчна ступінь точності не менш [math] n-1 [/ math]; при будь-яких заданих вузлах побудова інтерполяційної квадратурної формули здійснюється за рахунок вибору її [math] n [/ math] коефіцієнтів. За рахунок же вибору [math] n [/ math] вузлів інтерполяційної квадратурної формули можна домогтися того, щоб вона мала максимально високу алгебраїчну ступінь точності, а саме [math] 2n-1 [/ math].
Завдання побудови такої квадратурной формули розглядалася Карлом Фрідріхом Гауссом; їм була доведена її разрешимость.
Квадратурна формула з [math] n [/ math] вузлами, алгебраїчна ступінь точності якої дорівнює [math] 2n-1 [/ math]. називається квадратурної формулою Гаусса або квадратурної формулою найвищої алгебраїчної ступеня точності.
У разі відрізка [math] [- 1,1] [/ math] квадратурная формула
[Math] \ int \ limits_ ^ 1 f (t) \, dt \ approx \ sum \ limits_ ^ n c_i f (t_i) [/ math]
є квадратурной формулою Гаусса тоді і тільки тоді, коли вона є інтерполяційної, а її вузли [math] t_i [/ math] є корінням багаточлена Лежандра
Зокрема, при [math] n = 2 [/ math] і [math] n = 3 [/ math] квадратурні формули Гаусса для відрізка [math] [- 1,1] [/ math] такі:
[Math] \ int \ limits_ ^ 1 f (t) \, dt \ approx f \ left (- \ frac1 \ right) + f \ left (\ frac1 \ right), [/ math] [math] \ int \ limits_ ^ 1 f (t) \, dt \ approx \ frac59 \; f \ left (- \ sqrt \ right) + \ frac89 \; f (0) + \ frac59 \; f \ left (\ sqrt \ right). [ / math]
Щоб отримати квадратурну формулу Гаусса для довільного відрізка [math] [a, b] [/ math]. слід зробити заміну змінної
в результаті якої
Скориставшись квадратурной формулою Гаусса для відрізка [math] [- 1,1] [/ math]. отримаємо квадратурну формулу Гаусса для відрізка [math] [a, b] [/ math].
[Math] I \ approx \ frac2 \ sum \ limits_ ^ n c_i f (x_i), [/ math]
де [math] x_i = 0.5 (a + b + (b-a) t_i) [/ math]. [Math] t_i [/ math] - коріння многочлена Лежандра [math] P_n (t) [/ math].
Для похибки квадратурної формули Гаусса c [math] n [/ math] вузлами справедлива оцінка
Коефіцієнти квадратурних формул Гаусса позитивні. Тому використання квадратурних формул Гаусса з великим числом вузлів не призводить до тих ускладнень, які виникають при використанні формул Ньютона-Котеса.
1.2 Математичний опис алгоритму
Якщо квадратурная формула обрана, то алгоритм наближеного обчислення інтеграла полягає в обчисленні квадратурной суми, тобто в обчисленні значень функції в [math] n [/ math] вузлах, множенні їх на відповідні коефіцієнти і підсумовуванні отриманих чисел.
Вихідні дані: функція [math] f (x) [/ math] і два одновимірних масиву [math] n [/ math] чисел - масив вузлів і масив коефіцієнтів.
Обчислювані дані: число, що є значенням квадратурной суми і представляє собою наближене значення інтеграла.