Участник:Без имени

Алгоритм параллельного вычисления интеграла с использованием составной формулы трапеций.

Основные авторы описания: Участник: Кузнецова Д. Д.

Свойства и структура алгоритма

Общее описание алгоритма

Метод трапеций является отдельным представителем класса алгоритмов численного интегрирования (приближённого вычисления определённых интегралов), также известных как квадратурные формулы. Алгоритм предназначен для решения задачи нахождения приближённого значения определённого интеграла от функции [math]\displaystyle{ f(x) }[/math] на отрезке [math]\displaystyle{ [a,b] }[/math]: [math]\displaystyle{ I = \int_a^b f(x)dx }[/math]

Математическое описание алгоритма

Требуется найти приближённое значение определённого интеграла от функции [math]\displaystyle{ f(x) }[/math] на отрезке [math]\displaystyle{ [a,b] }[/math]:

[math]\displaystyle{ I = \int_a^b f(x)dx }[/math]

Исходный отрезок [math]\displaystyle{ [a,b] }[/math] разбивается на [math]\displaystyle{ n }[/math] элементарных отрезков с помощью узлов интегрирования [math]\displaystyle{ x_i }[/math], где [math]\displaystyle{ i = 0,1,\dots,n }[/math], таких что:

[math]\displaystyle{ x_0 = a, x_n = b }[/math]

На каждом элементарном отрезке [math]\displaystyle{ [x_i,x_{i+1}] }[/math], где [math]\displaystyle{ i = 0,1,\dots,n-1 }[/math], применяется формула трапеций:

[math]\displaystyle{ \int_{x_i}^{x_{i+1}} f(x)dx \approx \frac{f(x_i) + f(x_{i+1})}{2} h_i }[/math]

Где [math]\displaystyle{ h_i = x_{i+1} - x_i }[/math] – длина элементарного отрезка. Суммируя приближённые значения интегралов по всем элементарным отрезкам, получаем составную формулу трапеций:

[math]\displaystyle{ \int_a^b f(x)dx \approx \sum_{i=0}^{n-1} \frac{f(x_i) + f(x_{i+1})}{2} h_i }[/math]

В частности, когда все элементарные отрезки имеют одинаковую длину ([math]\displaystyle{ h_i = h = \frac{b-a}{n} }[/math]), формула принимает вид:

[math]\displaystyle{ \int_a^b f(x)dx \approx I_h = \frac{h}{2} [f(x_0) + 2\sum_{i=1}^{n-1} f(x_i) + f(x_n)] }[/math]

[math]\displaystyle{ x_i = a + ih, i = 0,1,\dots,n }[/math]

Погрешность метода [math]\displaystyle{ R_n = I - I_h }[/math] оценивается по формуле:

[math]\displaystyle{ R_n = -\frac{(b-a)}{12} h^2 f''(\xi), \xi \in [a,b] }[/math] Или:

[math]\displaystyle{ |R_n| \leq \frac{(b-a)}{12} h^2 \max_{x \in [a,b]} |f''(x)| }[/math]

Метод трапеций имеет второй порядок точности и является точным для многочленов степени не выше первой.

Вычислительное ядро алгоритма

На вычислительное ядро алгоритма приходится рекурсивное применение формулы трапеций на каждом из разбитых сегментов, пока не достигается требуемая точность.

Вычисление трех интегральных оценок:

[math]\displaystyle{ I_1 = I_h(f, x_i, x_{i+1}) }[/math] - оценка по формуле трапеций на каждом отрезке

[math]\displaystyle{ I_2 = I_h(f, x_i, m) + I_n(f, m, x_{i+1}) }[/math] - сумма оценок на двух половинках, где [math]\displaystyle{ m = \frac{x_i + x_{i+1}}{2} }[/math]

Оценка погрешности: [math]\displaystyle{ \varepsilon = |I_1 - I_2| }[/math]

Критерий остановки рекурсии: Если [math]\displaystyle{ \varepsilon \gt |I_1 - I_2| }[/math], возвращается [math]\displaystyle{ I_2 }[/math] Иначе: рекурсивный вызов для [math]\displaystyle{ [x_i, m] }[/math] и [math]\displaystyle{ [m, x_{i+1}] }[/math]

Формула трапеций. Суммирование всех значений интегралов с каждого элементарного отрезка: Для отрезка [math]\displaystyle{ [x_i, x_{i+1}] }[/math] с [math]\displaystyle{ h = \frac{x_{i+1} - x_i}{n} }[/math]:

[math]\displaystyle{ I_h(f, x_i, x_{i+1}) = h \times [\frac{f(x_i)}{2} + \frac{f(x_{i+1})}{2} + \sum_{k=1}^{n-1} f(x_i + k \times h)] }[/math]

где суммирование ведется по [math]\displaystyle{ k = 1,\dots,n-1 }[/math]