Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

1 ЧАСТЬ. Свойства и структура алгоритмов

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

На примере задачи вычисления определенного интеграла от аналитически заданной функции рассматриваются алгоритмы, минимизирующие время решения задачи на многопроцессорной вычислительной системе. Их использование обеспечивает снижение времени решения задачи относительно «наилучшего» доступного последовательного алгоритма. Определение эффективности параллельного алгоритма относительно собственной же последовательной версии, как правило, не корректно. Обладающий высокой эффективностью параллельный алгоритм может по времени выполнения проигрывать лучшему из доступных последовательных алгоритмов решения той же задачи. Далее рассматриваются алгоритмы, минимизирующие именно время решения задачи, оперирующей относительно небольшим объемом данных. Применяемые подходы могут быть полезны при решении широкого круга проблем.

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

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

Пусть на отрезке [math] [a,b] [/math] задана равномерная сетка, содержащая [math] n+1 [/math] узел:

[math] x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n [/math]

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

формула

Будем полагать значение I найденным с точностью ε, если выполнено условие

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

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

Метод трапеций

Метод рекурсивного деления

Метод локального стека