Алговики - Вклад [ru]

Участник:Без имени/Алгоритм параллельного вычисления интеграла с использованием составной формулы трапеций

2025-11-22T08:52:40Z

Без имени: /* Результаты прогонов */

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

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

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

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

<math>I = \int_a^b f(x)dx</math>

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

<math>x_0 = a, x_n = b</math>

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

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

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

<math>\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>h_i = h = \frac{b-a}{n}</math>), формула принимает вид:

<math>\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>x_i = a + ih, i = 0,1,\dots,n</math>

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

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

Вычислительное ядро метода трапеций представляет собой вычисление суммы значений в узлах сетки:

<math> S = f(x_0) + f(x_1) + ... + f(x_n) </math>

Где

<math> f(x) </math> - подынтегральная функция

<math> x_i = a+ih </math> - узлы сетки

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

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

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

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

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

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

<source> INIT(a, b, n) → h, sum_initial </source>

Вычисление шага сетки: <source> h = (b - a) / n </source>

Инициализация суммы: <source> sum_initial = 0.5 * (f(a) + f(b)) </source>

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

<source> SUM_FUNCTION_VALUES(a, h, n) -> sum_core </source>

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

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

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

<source> FINALIZE(sum_initial, sum_core, h) -> integral </source>

Объединение результатов: <source> total_sum = sum_initial + sum_core </source>

Финальное вычисление: <source> integral = total_sum * h </source>

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

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

<source lang="C">
// Параметры интегрирования
double a = 0.0; // нижний предел
double b = 10.0; // верхний предел
int n = 1000000; // количество интервалов
</source>

2. Вычисление шага сетки
<source lang="C">
double h = (b - a) / n;
</source>

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

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

3. Инициализация суммы граничных значений
<source lang="C">
double integral = 0.5 * (f(a) + f(b));
</source>

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

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

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

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

<source lang="C">
for (int i = 1; i < n; i++)
{
double x = a + i * h;
integral += f(x);
}
</source>

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

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

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

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

<source lang="python">
result = integral * h
</source>

Полная схема алгоритма
<source>
НАЧАЛО
│
|- Ввод параметров: 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
</source>

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

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

=== Информационный граф ===
[[File:Graph_1456.png|center|V1 - получение параметров интегрирования, V2.i - рассылка границ на каждый процесс, V3.i - вычисление площадей на каждом отрезке, V4 - итоговое суммирование]]
Рис. 1. - Информационный граф, V1 - получение параметров интегрирования, V2.i - рассылка границ на каждый процесс, V3.i - вычисление площадей на каждом отрезке, V4 - итоговое суммирование
=== Ресурс параллелизма алгоритма ===
Основная вычислительная нагрузка сосредоточена в полностью независимых операциях вычисления значений функции в узлах сетки. Параллельная сложность составляет <math> O(1) </math> для основной расчетной части при использовании достаточного количества процессоров. Структура параллелизма обеспечивает балансировку нагрузки и простоту реализации. При больших n доля последовательных операций стремится к нулю.

=== Входные и выходные данные алгоритма ===

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

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===
Для большинства практических применений метода трапеций достаточно одинарной точности (float). В большинстве практических случаев не требует двойной точности вычислений, поскольку его основная погрешность определяется теоретической ошибкой метода O(1/n²), а не вычислительной ошибкой округления.

=== Возможные способы и особенности параллельной реализации алгоритма ===

Основной способ распределения данных. Весь диапазон [a, b] разбивается на p блоков (где p - количество процессов), каждый процесс получает свой непрерывный блок интервалов. Для балансировки нагрузки при неравномерном количестве интервалов применяется циклическое распределение остатка - первые r процессов получают на один интервал больше.

Ключевая коммуникационная операция - глобальная редукция (MPI_Reduce) для суммирования частичных интегралов. Объем пересылаемых данных минимален - каждый процесс отправляет всего одно вещественное число (свой частичный интеграл).

Параллельная эффективность ограничена последовательной долей по закону Амдала, которая включает инициализацию и финальную редукцию. При больших n эта доля становится пренебрежимо малой. Для достижения максимальной производительности рекомендуется выбирать размер задачи n таким, чтобы каждый процесс/поток получал достаточно большую порцию работы (обычно тысячи интервалов), минимизируя относительные накладные расходы.

=== Результаты прогонов ===
Processes: 2, Time: 0.080949 seconds

Processes: 2, Time: 0.074890 seconds

Processes: 2, Time: 0.058663 seconds

Processes: 2, Time: 0.058114 seconds

Processes: 4, Time: 0.047105 seconds

Processes: 4, Time: 0.043581 seconds

Processes: 4, Time: 0.048686 seconds

Processes: 4, Time: 0.046107 seconds

Processes: 8, Time: 0.024348 seconds

Processes: 8, Time: 0.022984 seconds

Processes: 8, Time: 0.021923 seconds

Processes: 8, Time: 0.024774 seconds

Processes: 16, Time: 0.013365 seconds

Processes: 16, Time: 0.011646 seconds

Processes: 16, Time: 0.011226 seconds

Processes: 16, Time: 0.010894 seconds

Processes: 20, Time: 0.008676 seconds

Processes: 20, Time: 0.009282 seconds

Processes: 20, Time: 0.009332 seconds

Processes: 20, Time: 0.010975 seconds

Processes: 24, Time: 0.008456 seconds

Processes: 24, Time: 0.008577 seconds

Processes: 24, Time: 0.008664 seconds

Processes: 24, Time: 0.009281 seconds

Processes: 28, Time: 0.007415 seconds

Processes: 28, Time: 0.007020 seconds

Processes: 28, Time: 0.007767 seconds

Processes: 28, Time: 0.006456 seconds

=== Выводы для классов архитектур ===

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

[2] Якобовский М.В. Введение в параллельные методы решения задач, 2013. - 328 с.

[3] Антонов А.С. Технологии параллельного программирования MPI и OpenMP, 2012. - 344 с.

#[[Категория:Алгоритмы численного интегрирования]]

Участник:Без имени/Алгоритм параллельного вычисления интеграла с использованием составной формулы трапеций

2025-11-22T08:52:26Z

Без имени: /* Результаты прогонов */

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

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

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

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

<math>I = \int_a^b f(x)dx</math>

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

<math>x_0 = a, x_n = b</math>

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

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

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

<math>\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>h_i = h = \frac{b-a}{n}</math>), формула принимает вид:

<math>\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>x_i = a + ih, i = 0,1,\dots,n</math>

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

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

Вычислительное ядро метода трапеций представляет собой вычисление суммы значений в узлах сетки:

<math> S = f(x_0) + f(x_1) + ... + f(x_n) </math>

Где

<math> f(x) </math> - подынтегральная функция

<math> x_i = a+ih </math> - узлы сетки

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

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

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

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

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

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

<source> INIT(a, b, n) → h, sum_initial </source>

Вычисление шага сетки: <source> h = (b - a) / n </source>

Инициализация суммы: <source> sum_initial = 0.5 * (f(a) + f(b)) </source>

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

<source> SUM_FUNCTION_VALUES(a, h, n) -> sum_core </source>

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

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

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

<source> FINALIZE(sum_initial, sum_core, h) -> integral </source>

Объединение результатов: <source> total_sum = sum_initial + sum_core </source>

Финальное вычисление: <source> integral = total_sum * h </source>

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

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

<source lang="C">
// Параметры интегрирования
double a = 0.0; // нижний предел
double b = 10.0; // верхний предел
int n = 1000000; // количество интервалов
</source>

2. Вычисление шага сетки
<source lang="C">
double h = (b - a) / n;
</source>

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

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

3. Инициализация суммы граничных значений
<source lang="C">
double integral = 0.5 * (f(a) + f(b));
</source>

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

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

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

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

<source lang="C">
for (int i = 1; i < n; i++)
{
double x = a + i * h;
integral += f(x);
}
</source>

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

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

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

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

<source lang="python">
result = integral * h
</source>

Полная схема алгоритма
<source>
НАЧАЛО
│
|- Ввод параметров: 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
</source>

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

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

=== Информационный граф ===
[[File:Graph_1456.png|center|V1 - получение параметров интегрирования, V2.i - рассылка границ на каждый процесс, V3.i - вычисление площадей на каждом отрезке, V4 - итоговое суммирование]]
Рис. 1. - Информационный граф, V1 - получение параметров интегрирования, V2.i - рассылка границ на каждый процесс, V3.i - вычисление площадей на каждом отрезке, V4 - итоговое суммирование
=== Ресурс параллелизма алгоритма ===
Основная вычислительная нагрузка сосредоточена в полностью независимых операциях вычисления значений функции в узлах сетки. Параллельная сложность составляет <math> O(1) </math> для основной расчетной части при использовании достаточного количества процессоров. Структура параллелизма обеспечивает балансировку нагрузки и простоту реализации. При больших n доля последовательных операций стремится к нулю.

=== Входные и выходные данные алгоритма ===

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

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===
Для большинства практических применений метода трапеций достаточно одинарной точности (float). В большинстве практических случаев не требует двойной точности вычислений, поскольку его основная погрешность определяется теоретической ошибкой метода O(1/n²), а не вычислительной ошибкой округления.

=== Возможные способы и особенности параллельной реализации алгоритма ===

Основной способ распределения данных. Весь диапазон [a, b] разбивается на p блоков (где p - количество процессов), каждый процесс получает свой непрерывный блок интервалов. Для балансировки нагрузки при неравномерном количестве интервалов применяется циклическое распределение остатка - первые r процессов получают на один интервал больше.

Ключевая коммуникационная операция - глобальная редукция (MPI_Reduce) для суммирования частичных интегралов. Объем пересылаемых данных минимален - каждый процесс отправляет всего одно вещественное число (свой частичный интеграл).

Параллельная эффективность ограничена последовательной долей по закону Амдала, которая включает инициализацию и финальную редукцию. При больших n эта доля становится пренебрежимо малой. Для достижения максимальной производительности рекомендуется выбирать размер задачи n таким, чтобы каждый процесс/поток получал достаточно большую порцию работы (обычно тысячи интервалов), минимизируя относительные накладные расходы.

=== Результаты прогонов ===
Processes: 2, Time: 0.080949 seconds

Processes: 2, Time: 0.074890 seconds

Processes: 2, Time: 0.058663 seconds

Processes: 2, Time: 0.058114 seconds

Processes: 4, Time: 0.047105 seconds

Processes: 4, Time: 0.043581 seconds

Processes: 4, Time: 0.048686 seconds

Processes: 4, Time: 0.046107 seconds

Processes: 8, Time: 0.024348 seconds

Processes: 8, Time: 0.022984 seconds

Processes: 8, Time: 0.021923 seconds

Processes: 8, Time: 0.024774 seconds

Processes: 16, Time: 0.013365 seconds

Processes: 16, Time: 0.011646 seconds

Processes: 16, Time: 0.011226 seconds

Processes: 16, Time: 0.010894 seconds

Processes: 20, Time: 0.008676 seconds

Processes: 20, Time: 0.009282 seconds

Processes: 20, Time: 0.009332 seconds

Processes: 20, Time: 0.010975 seconds

Processes: 24, Time: 0.008456 seconds

Processes: 24, Time: 0.008577 seconds

Processes: 24, Time: 0.008664 seconds

Processes: 24, Time: 0.009281 seconds

Processes: 28, Time: 0.007415 seconds

Processes: 28, Time: 0.007020 seconds

Processes: 28, Time: 0.007767 seconds
Processes: 28, Time: 0.006456 seconds

=== Выводы для классов архитектур ===

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

[2] Якобовский М.В. Введение в параллельные методы решения задач, 2013. - 328 с.

[3] Антонов А.С. Технологии параллельного программирования MPI и OpenMP, 2012. - 344 с.

#[[Категория:Алгоритмы численного интегрирования]]

Участник:Без имени/Алгоритм параллельного вычисления интеграла с использованием составной формулы трапеций

2025-11-22T08:51:45Z

Без имени: /* Результаты прогонов */

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

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

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

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

<math>I = \int_a^b f(x)dx</math>

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

<math>x_0 = a, x_n = b</math>

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

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

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

<math>\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>h_i = h = \frac{b-a}{n}</math>), формула принимает вид:

<math>\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>x_i = a + ih, i = 0,1,\dots,n</math>

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

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

Вычислительное ядро метода трапеций представляет собой вычисление суммы значений в узлах сетки:

<math> S = f(x_0) + f(x_1) + ... + f(x_n) </math>

Где

<math> f(x) </math> - подынтегральная функция

<math> x_i = a+ih </math> - узлы сетки

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

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

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

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

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

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

<source> INIT(a, b, n) → h, sum_initial </source>

Вычисление шага сетки: <source> h = (b - a) / n </source>

Инициализация суммы: <source> sum_initial = 0.5 * (f(a) + f(b)) </source>

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

<source> SUM_FUNCTION_VALUES(a, h, n) -> sum_core </source>

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

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

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

<source> FINALIZE(sum_initial, sum_core, h) -> integral </source>

Объединение результатов: <source> total_sum = sum_initial + sum_core </source>

Финальное вычисление: <source> integral = total_sum * h </source>

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

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

<source lang="C">
// Параметры интегрирования
double a = 0.0; // нижний предел
double b = 10.0; // верхний предел
int n = 1000000; // количество интервалов
</source>

2. Вычисление шага сетки
<source lang="C">
double h = (b - a) / n;
</source>

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

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

3. Инициализация суммы граничных значений
<source lang="C">
double integral = 0.5 * (f(a) + f(b));
</source>

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

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

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

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

<source lang="C">
for (int i = 1; i < n; i++)
{
double x = a + i * h;
integral += f(x);
}
</source>

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

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

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

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

<source lang="python">
result = integral * h
</source>

Полная схема алгоритма
<source>
НАЧАЛО
│
|- Ввод параметров: 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
</source>

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

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

=== Информационный граф ===
[[File:Graph_1456.png|center|V1 - получение параметров интегрирования, V2.i - рассылка границ на каждый процесс, V3.i - вычисление площадей на каждом отрезке, V4 - итоговое суммирование]]
Рис. 1. - Информационный граф, V1 - получение параметров интегрирования, V2.i - рассылка границ на каждый процесс, V3.i - вычисление площадей на каждом отрезке, V4 - итоговое суммирование
=== Ресурс параллелизма алгоритма ===
Основная вычислительная нагрузка сосредоточена в полностью независимых операциях вычисления значений функции в узлах сетки. Параллельная сложность составляет <math> O(1) </math> для основной расчетной части при использовании достаточного количества процессоров. Структура параллелизма обеспечивает балансировку нагрузки и простоту реализации. При больших n доля последовательных операций стремится к нулю.

=== Входные и выходные данные алгоритма ===

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

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===
Для большинства практических применений метода трапеций достаточно одинарной точности (float). В большинстве практических случаев не требует двойной точности вычислений, поскольку его основная погрешность определяется теоретической ошибкой метода O(1/n²), а не вычислительной ошибкой округления.

=== Возможные способы и особенности параллельной реализации алгоритма ===

Основной способ распределения данных. Весь диапазон [a, b] разбивается на p блоков (где p - количество процессов), каждый процесс получает свой непрерывный блок интервалов. Для балансировки нагрузки при неравномерном количестве интервалов применяется циклическое распределение остатка - первые r процессов получают на один интервал больше.

Ключевая коммуникационная операция - глобальная редукция (MPI_Reduce) для суммирования частичных интегралов. Объем пересылаемых данных минимален - каждый процесс отправляет всего одно вещественное число (свой частичный интеграл).

Параллельная эффективность ограничена последовательной долей по закону Амдала, которая включает инициализацию и финальную редукцию. При больших n эта доля становится пренебрежимо малой. Для достижения максимальной производительности рекомендуется выбирать размер задачи n таким, чтобы каждый процесс/поток получал достаточно большую порцию работы (обычно тысячи интервалов), минимизируя относительные накладные расходы.

=== Результаты прогонов ===
Processes: 2, Time: 0.080949 seconds
Processes: 2, Time: 0.074890 seconds
Processes: 2, Time: 0.058663 seconds
Processes: 2, Time: 0.058114 seconds

Processes: 4, Time: 0.047105 seconds
Processes: 4, Time: 0.043581 seconds
Processes: 4, Time: 0.048686 seconds
Processes: 4, Time: 0.046107 seconds

Processes: 8, Time: 0.024348 seconds
Processes: 8, Time: 0.022984 seconds
Processes: 8, Time: 0.021923 seconds
Processes: 8, Time: 0.024774 seconds

Processes: 16, Time: 0.013365 seconds
Processes: 16, Time: 0.011646 seconds
Processes: 16, Time: 0.011226 seconds
Processes: 16, Time: 0.010894 seconds

Processes: 20, Time: 0.008676 seconds
Processes: 20, Time: 0.009282 seconds
Processes: 20, Time: 0.009332 seconds
Processes: 20, Time: 0.010975 seconds

Processes: 24, Time: 0.008456 seconds
Processes: 24, Time: 0.008577 seconds
Processes: 24, Time: 0.008664 seconds
Processes: 24, Time: 0.009281 seconds

Processes: 28, Time: 0.007415 seconds
Processes: 28, Time: 0.007020 seconds
Processes: 28, Time: 0.007767 seconds
Processes: 28, Time: 0.006456 seconds

=== Выводы для классов архитектур ===

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

[2] Якобовский М.В. Введение в параллельные методы решения задач, 2013. - 328 с.

[3] Антонов А.С. Технологии параллельного программирования MPI и OpenMP, 2012. - 344 с.

#[[Категория:Алгоритмы численного интегрирования]]

Участник:Без имени/Алгоритм параллельного вычисления интеграла с использованием составной формулы трапеций

2025-11-22T08:22:20Z

Без имени: Новая страница: «{{algorithm | name = Алгоритм параллельного вычисления интеграла с использованием составной формулы трапеций. }} Основные авторы описания: Участник: Кузнецова Д. Д. == Свойства и структура алгоритма == === Общее описание алгоритма === Метод трапеций являе...»

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

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

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

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

<math>I = \int_a^b f(x)dx</math>

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

<math>x_0 = a, x_n = b</math>

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

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

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

<math>\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>h_i = h = \frac{b-a}{n}</math>), формула принимает вид:

<math>\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>x_i = a + ih, i = 0,1,\dots,n</math>

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

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

Вычислительное ядро метода трапеций представляет собой вычисление суммы значений в узлах сетки:

<math> S = f(x_0) + f(x_1) + ... + f(x_n) </math>

Где

<math> f(x) </math> - подынтегральная функция

<math> x_i = a+ih </math> - узлы сетки

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

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

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

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

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

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

<source> INIT(a, b, n) → h, sum_initial </source>

Вычисление шага сетки: <source> h = (b - a) / n </source>

Инициализация суммы: <source> sum_initial = 0.5 * (f(a) + f(b)) </source>

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

<source> SUM_FUNCTION_VALUES(a, h, n) -> sum_core </source>

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

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

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

<source> FINALIZE(sum_initial, sum_core, h) -> integral </source>

Объединение результатов: <source> total_sum = sum_initial + sum_core </source>

Финальное вычисление: <source> integral = total_sum * h </source>

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

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

<source lang="C">
// Параметры интегрирования
double a = 0.0; // нижний предел
double b = 10.0; // верхний предел
int n = 1000000; // количество интервалов
</source>

2. Вычисление шага сетки
<source lang="C">
double h = (b - a) / n;
</source>

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

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

3. Инициализация суммы граничных значений
<source lang="C">
double integral = 0.5 * (f(a) + f(b));
</source>

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

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

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

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

<source lang="C">
for (int i = 1; i < n; i++)
{
double x = a + i * h;
integral += f(x);
}
</source>

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

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

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

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

<source lang="python">
result = integral * h
</source>

Полная схема алгоритма
<source>
НАЧАЛО
│
|- Ввод параметров: 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
</source>

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

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

=== Информационный граф ===
[[File:Graph_1456.png|center|V1 - получение параметров интегрирования, V2.i - рассылка границ на каждый процесс, V3.i - вычисление площадей на каждом отрезке, V4 - итоговое суммирование]]
Рис. 1. - Информационный граф, V1 - получение параметров интегрирования, V2.i - рассылка границ на каждый процесс, V3.i - вычисление площадей на каждом отрезке, V4 - итоговое суммирование
=== Ресурс параллелизма алгоритма ===
Основная вычислительная нагрузка сосредоточена в полностью независимых операциях вычисления значений функции в узлах сетки. Параллельная сложность составляет <math> O(1) </math> для основной расчетной части при использовании достаточного количества процессоров. Структура параллелизма обеспечивает балансировку нагрузки и простоту реализации. При больших n доля последовательных операций стремится к нулю.

=== Входные и выходные данные алгоритма ===

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

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===
Для большинства практических применений метода трапеций достаточно одинарной точности (float). В большинстве практических случаев не требует двойной точности вычислений, поскольку его основная погрешность определяется теоретической ошибкой метода O(1/n²), а не вычислительной ошибкой округления.

=== Возможные способы и особенности параллельной реализации алгоритма ===

Основной способ распределения данных. Весь диапазон [a, b] разбивается на p блоков (где p - количество процессов), каждый процесс получает свой непрерывный блок интервалов. Для балансировки нагрузки при неравномерном количестве интервалов применяется циклическое распределение остатка - первые r процессов получают на один интервал больше.

Ключевая коммуникационная операция - глобальная редукция (MPI_Reduce) для суммирования частичных интегралов. Объем пересылаемых данных минимален - каждый процесс отправляет всего одно вещественное число (свой частичный интеграл).

Параллельная эффективность ограничена последовательной долей по закону Амдала, которая включает инициализацию и финальную редукцию. При больших n эта доля становится пренебрежимо малой. Для достижения максимальной производительности рекомендуется выбирать размер задачи n таким, чтобы каждый процесс/поток получал достаточно большую порцию работы (обычно тысячи интервалов), минимизируя относительные накладные расходы.

=== Результаты прогонов ===
=== Выводы для классов архитектур ===

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

[2] Якобовский М.В. Введение в параллельные методы решения задач, 2013. - 328 с.

[3] Антонов А.С. Технологии параллельного программирования MPI и OpenMP, 2012. - 344 с.

#[[Категория:Алгоритмы численного интегрирования]]

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

2025-11-16T14:07:22Z

Без имени:

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

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

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

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

<math>I = \int_a^b f(x)dx</math>

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

<math>x_0 = a, x_n = b</math>

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

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

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

<math>\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>h_i = h = \frac{b-a}{n}</math>), формула принимает вид:

<math>\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>x_i = a + ih, i = 0,1,\dots,n</math>

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

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

Вычислительное ядро метода трапеций представляет собой вычисление суммы значений в узлах сетки:

<math> S = f(x_0) + f(x_1) + ... + f(x_n) </math>

Где

<math> f(x) </math> - подынтегральная функция

<math> x_i = a+ih </math> - узлы сетки

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

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

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

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

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

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

<source> INIT(a, b, n) → h, sum_initial </source>

Вычисление шага сетки: <source> h = (b - a) / n </source>

Инициализация суммы: <source> sum_initial = 0.5 * (f(a) + f(b)) </source>

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

<source> SUM_FUNCTION_VALUES(a, h, n) -> sum_core </source>

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

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

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

<source> FINALIZE(sum_initial, sum_core, h) -> integral </source>

Объединение результатов: <source> total_sum = sum_initial + sum_core </source>

Финальное вычисление: <source> integral = total_sum * h </source>

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

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

<source lang="C">
// Параметры интегрирования
double a = 0.0; // нижний предел
double b = 10.0; // верхний предел
int n = 1000000; // количество интервалов
</source>

2. Вычисление шага сетки
<source lang="C">
double h = (b - a) / n;
</source>

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

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

3. Инициализация суммы граничных значений
<source lang="C">
double integral = 0.5 * (f(a) + f(b));
</source>

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

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

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

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

<source lang="C">
for (int i = 1; i < n; i++)
{
double x = a + i * h;
integral += f(x);
}
</source>

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

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

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

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

<source lang="python">
result = integral * h
</source>

Полная схема алгоритма
<source>
НАЧАЛО
│
|- Ввод параметров: 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
</source>

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

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

=== Информационный граф ===
[[File:Graph_1456.png|center|V1 - получение параметров интегрирования, V2.i - рассылка границ на каждый процесс, V3.i - вычисление площадей на каждом отрезке, V4 - итоговое суммирование]]
Рис. 1. - Информационный граф, V1 - получение параметров интегрирования, V2.i - рассылка границ на каждый процесс, V3.i - вычисление площадей на каждом отрезке, V4 - итоговое суммирование
=== Ресурс параллелизма алгоритма ===
Основная вычислительная нагрузка сосредоточена в полностью независимых операциях вычисления значений функции в узлах сетки. Параллельная сложность составляет <math> O(1) </math> для основной расчетной части при использовании достаточного количества процессоров. Структура параллелизма обеспечивает балансировку нагрузки и простоту реализации. При больших n доля последовательных операций стремится к нулю.

=== Входные и выходные данные алгоритма ===

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

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===
Для большинства практических применений метода трапеций достаточно одинарной точности (float). В большинстве практических случаев не требует двойной точности вычислений, поскольку его основная погрешность определяется теоретической ошибкой метода O(1/n²), а не вычислительной ошибкой округления.

=== Возможные способы и особенности параллельной реализации алгоритма ===

Основной способ распределения данных. Весь диапазон [a, b] разбивается на p блоков (где p - количество процессов), каждый процесс получает свой непрерывный блок интервалов. Для балансировки нагрузки при неравномерном количестве интервалов применяется циклическое распределение остатка - первые r процессов получают на один интервал больше.

Ключевая коммуникационная операция - глобальная редукция (MPI_Reduce) для суммирования частичных интегралов. Объем пересылаемых данных минимален - каждый процесс отправляет всего одно вещественное число (свой частичный интеграл).

Параллельная эффективность ограничена последовательной долей по закону Амдала, которая включает инициализацию и финальную редукцию. При больших n эта доля становится пренебрежимо малой. Для достижения максимальной производительности рекомендуется выбирать размер задачи n таким, чтобы каждый процесс/поток получал достаточно большую порцию работы (обычно тысячи интервалов), минимизируя относительные накладные расходы.

=== Результаты прогонов ===
=== Выводы для классов архитектур ===

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

[2] Якобовский М.В. Введение в параллельные методы решения задач, 2013. - 328 с.

[3] Антонов А.С. Технологии параллельного программирования MPI и OpenMP, 2012. - 344 с.

#[[Категория:Алгоритмы численного интегрирования]]

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

2025-11-16T14:00:45Z

Без имени:

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

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

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

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

<math>I = \int_a^b f(x)dx</math>

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

<math>x_0 = a, x_n = b</math>

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

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

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

<math>\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>h_i = h = \frac{b-a}{n}</math>), формула принимает вид:

<math>\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>x_i = a + ih, i = 0,1,\dots,n</math>

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

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

Вычислительное ядро метода трапеций представляет собой вычисление суммы значений в узлах сетки:

<math> S = f(x_0) + f(x_1) + ... + f(x_n) </math>

Где

<math> f(x) </math> - подынтегральная функция

<math> x_i = a+ih </math> - узлы сетки

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

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

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

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

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

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

<source> INIT(a, b, n) → h, sum_initial </source>

Вычисление шага сетки: <source> h = (b - a) / n </source>

Инициализация суммы: <source> sum_initial = 0.5 * (f(a) + f(b)) </source>

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

<source> SUM_FUNCTION_VALUES(a, h, n) -> sum_core </source>

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

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

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

<source> FINALIZE(sum_initial, sum_core, h) -> integral </source>

Объединение результатов: <source> total_sum = sum_initial + sum_core </source>

Финальное вычисление: <source> integral = total_sum * h </source>

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

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

<source lang="C">
// Параметры интегрирования
double a = 0.0; // нижний предел
double b = 10.0; // верхний предел
int n = 1000000; // количество интервалов
</source>

2. Вычисление шага сетки
<source lang="C">
double h = (b - a) / n;
</source>

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

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

3. Инициализация суммы граничных значений
<source lang="C">
double integral = 0.5 * (f(a) + f(b));
</source>

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

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

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

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

<source lang="C">
for (int i = 1; i < n; i++)
{
double x = a + i * h;
integral += f(x);
}
</source>

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

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

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

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

<source lang="python">
result = integral * h
</source>

Полная схема алгоритма
<source>
НАЧАЛО
│
|- Ввод параметров: 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
</source>

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

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

=== Информационный граф ===

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

=== Входные и выходные данные алгоритма ===

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

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===
Для большинства практических применений метода трапеций достаточно одинарной точности (float). В большинстве практических случаев не требует двойной точности вычислений, поскольку его основная погрешность определяется теоретической ошибкой метода O(1/n²), а не вычислительной ошибкой округления.

=== Возможные способы и особенности параллельной реализации алгоритма ===

Основной способ распределения данных. Весь диапазон [a, b] разбивается на p блоков (где p - количество процессов), каждый процесс получает свой непрерывный блок интервалов. Для балансировки нагрузки при неравномерном количестве интервалов применяется циклическое распределение остатка - первые r процессов получают на один интервал больше.

Ключевая коммуникационная операция - глобальная редукция (MPI_Reduce) для суммирования частичных интегралов. Объем пересылаемых данных минимален - каждый процесс отправляет всего одно вещественное число (свой частичный интеграл).

Параллельная эффективность ограничена последовательной долей по закону Амдала, которая включает инициализацию и финальную редукцию. При больших n эта доля становится пренебрежимо малой. Для достижения максимальной производительности рекомендуется выбирать размер задачи n таким, чтобы каждый процесс/поток получал достаточно большую порцию работы (обычно тысячи интервалов), минимизируя относительные накладные расходы.

=== Результаты прогонов ===
=== Выводы для классов архитектур ===

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

[2] Якобовский М.В. Введение в параллельные методы решения задач, 2013. - 328 с.

[3] Антонов А.С. Технологии параллельного программирования MPI и OpenMP, 2012. - 344 с.

#[[Категория:Алгоритмы численного интегрирования]]

Файл:Graph 1456.png

2025-11-06T14:32:50Z

Без имени:

Информационный граф

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

2025-11-06T09:22:34Z

Без имени:

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

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

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

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

<math>I = \int_a^b f(x)dx</math>

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

<math>x_0 = a, x_n = b</math>

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

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

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

<math>\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>h_i = h = \frac{b-a}{n}</math>), формула принимает вид:

<math>\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>x_i = a + ih, i = 0,1,\dots,n</math>

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

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

Вычислительное ядро метода трапеций представляет собой вычисление суммы значений в узлах сетки:

<math> S = f(x_0) + f(x_1) + ... + f(x_n) </math>

Где

<math> f(x) </math> - подынтегральная функция

<math> x_i = a+ih </math> - узлы сетки

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

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

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

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

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

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

<source> INIT(a, b, n) → h, sum_initial </source>

Вычисление шага сетки: <source> h = (b - a) / n </source>

Инициализация суммы: <source> sum_initial = 0.5 * (f(a) + f(b)) </source>

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

<source> SUM_FUNCTION_VALUES(a, h, n) -> sum_core </source>

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

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

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

<source> FINALIZE(sum_initial, sum_core, h) -> integral </source>

Объединение результатов: <source> total_sum = sum_initial + sum_core </source>

Финальное вычисление: <source> integral = total_sum * h </source>

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

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

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

2. Вычисление шага сетки
<source lang="python">
# Входные параметры
h = (b - a) / n
</source>

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

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

3. Инициализация суммы граничных значений
<source lang="python">
integral = 0.5 * (f(a) + f(b))
</source>

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

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

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

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

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

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

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

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

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

<source lang="python">
result = integral * h
</source>

Полная схема алгоритма
<source>
НАЧАЛО
│
|- Ввод параметров: 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
</source>

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

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

=== Информационный граф ===

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

=== Входные и выходные данные алгоритма ===

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

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===
Для большинства практических применений метода трапеций достаточно одинарной точности (float). В большинстве практических случаев не требует двойной точности вычислений, поскольку его основная погрешность определяется теоретической ошибкой метода O(1/n²), а не вычислительной ошибкой округления.

=== Возможные способы и особенности параллельной реализации алгоритма ===

Основной способ распределения данных. Весь диапазон [a, b] разбивается на p блоков (где p - количество процессов), каждый процесс получает свой непрерывный блок интервалов. Для балансировки нагрузки при неравномерном количестве интервалов применяется циклическое распределение остатка - первые r процессов получают на один интервал больше.

Ключевая коммуникационная операция - глобальная редукция (MPI_Reduce) для суммирования частичных интегралов. Объем пересылаемых данных минимален - каждый процесс отправляет всего одно вещественное число (свой частичный интеграл).

Параллельная эффективность ограничена последовательной долей по закону Амдала, которая включает инициализацию и финальную редукцию. При больших n эта доля становится пренебрежимо малой. Для достижения максимальной производительности рекомендуется выбирать размер задачи n таким, чтобы каждый процесс/поток получал достаточно большую порцию работы (обычно тысячи интервалов), минимизируя относительные накладные расходы.

=== Результаты прогонов ===
=== Выводы для классов архитектур ===

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

[2] Якобовский М.В. Введение в параллельные методы решения задач, 2013. - 328 с.

[3] Антонов А.С. Технологии параллельного программирования MPI и OpenMP, 2012. - 344 с.

#[[Категория:Алгоритмы численного интегрирования]]

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

2025-11-06T08:54:40Z

Без имени:

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

2025-11-06T08:14:07Z

Без имени:

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

2025-10-28T10:45:57Z

Без имени:

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

2025-10-28T10:38:11Z

Без имени: /* Вычислительное ядро алгоритма */

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

2025-10-28T10:37:37Z

Без имени: /* Вычислительное ядро алгоритма */

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

2025-10-28T10:36:27Z

Без имени:

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

2025-10-28T10:35:25Z

Без имени:

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

2025-10-28T10:32:43Z

Без имени: Новая страница: «{{algorithm | name = Алгоритм параллельного вычисления интеграла с использованием состав...»

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

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

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

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

<math>I = \int_a^b f(x)dx</math>

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

<math>x_0 = a, x_n = b</math>

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

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

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

<math>\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>h_i = h = \frac{b-a}{n}</math>), формула принимает вид:

<math>\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>x_i = a + ih, i = 0,1,\dots,n</math>

Погрешность метода <math>R_n = I - I_h</math> оценивается по формуле:

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

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

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

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

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

Вычисление трех интегральных оценок:
<math>I_1 = I_h(f, x_i, x_{i+1})</math> - оценка по формуле трапеций на каждом отрезке
<math>I_2 = I_h(f, x_i, m) + I_n(f, m, x_{i+1})</math> - сумма оценок на двух половинках, где <math>m = \frac{x_i + x_{i+1}}{2}</math>

Оценка погрешности:
<math>\varepsilon = |I_1 - I_2|</math>

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

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

<math>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>k = 1,\dots,n-1</math>