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

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

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

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

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

Метод трапеций является отдельным представителем класса алгоритмов численного интегрирования (приближённого вычисления определённых интегралов), также известных как квадратурные формулы. Алгоритм предназначен для решения задачи нахождения приближённого значения определённого интеграла от функции [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{ S = f(x_0) + f(x_1) + ... + f(x_n) }[/math]

Где

[math]\displaystyle{ f(x) }[/math] - подынтегральная функция

[math]\displaystyle{ x_i = a+ih }[/math] - узлы сетки

n - количество интервалов разбиения

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

Основная вычислительная нагрузка приходится на [math]\displaystyle{ \sum_{i=1}^{n-1} f(x_i) }[/math]

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

Макроструктура алгоритма

1. Инициализация параметров

 INIT(a, b, n) → h, sum_initial

Вычисление шага сетки:

 h = (b - a) / n

Инициализация суммы:

 sum_initial = 0.5 * (f(a) + f(b))

2. Вычисление суммы значений функции

 SUM_FUNCTION_VALUES(a, h, n) -> sum_core

Основная вычислительная макрооперация

Вычисление: sum_core = ∑[i=1 to n-1] f(a + i·h)

3. Финальное вычисление интеграла

 FINALIZE(sum_initial, sum_core, h) -> integral

Объединение результатов:

 total_sum = sum_initial + sum_core

Финальное вычисление:

 integral = total_sum * h

Схема реализации последовательного алгоритма

1. Инициализация параметров интегрирования

# Входные параметры
a = 0.0      # Нижний предел интегрирования
b = 10.0     # Верхний предел интегрирования  
n = 1000000  # Количество интервалов разбиения

2. Вычисление шага сетки

# Входные параметры
h = (b - a) / n

- Вычисляется равномерное расстояние между соседними узлами

- Определяет плотность разбиения области интегрирования

3. Инициализация суммы граничных значений

integral = 0.5 * (f(a) + f(b))

- Вычисляются значения функции на границах интервала

- Умножаются на коэффициент 0.5 согласно формуле трапеций

- Создается начальное приближение интеграла

4. Основной вычислительный цикл

for i in range(1, n):
    # Вычисление координаты текущего узла
    x = a + i * h
    # Вычисление значения функции в узле
    fx = f(x)
    # Накопление суммы
    integral += fx

- Для каждого i от 1 до n-1 вычисляется x_i = a + i·h

- Для каждого узла вычисляется f(x_i). Это наиболее вычислительно затратная часть алгоритма

- Накопление суммы

5. Финальное вычисление интеграла

result = integral * h

Полная схема алгоритма

НАЧАЛО
  │
  |- Ввод параметров: a, b, n
  │
  |- Проверка: n > 0, a < b
  │
  |- Вычисление: h = (b - a) / n
  │
  |- Инициализация: sum = 0.5 * [f(a) + f(b)]
  │
  |- ЦИКЛ i = 1 ДО n-1:
  │   │
  │   |-Вычисление: x = a + i * h
  │   │
  │   |- Вычисление: fx = f(x)
  │   │
  │   |─ Накопление: sum = sum + fx
  │
   Результат: integral = sum * h

Последовательная сложность алгоритма

Метод трапеций относится к классу алгоритмов с линейной сложностью [math]\displaystyle{ O(n) }[/math] по количеству интервалов разбиения n. Основной вклад в сложность вносят вычисления функции [math]\displaystyle{ f(x) }[/math] именно от неё зависит количество проводимых вычислений в процессе применения формулы трапеций от каждого участка.

Ресурс параллелизма алгоритма

Основная вычислительная нагрузка сосредоточена в полностью независимых операциях вычисления значений функции в узлах сетки. Параллельная сложность составляет [math]\displaystyle{ O(1) }[/math] для основной расчетной части при использовании достаточного количества процессоров. Структура параллелизма обеспечивает балансировку нагрузки и простоту реализации. При больших n доля последовательных операций стремится к нулю.

Литература

[1] Самарский А.А., Гулин А.В. Численные методы. М.: Наука, 1989. – 432 с.