Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки: различия между версиями
| Строка 19: | Строка 19: | ||
Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>: | Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>: | ||
| − | + | <math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math> | |
Будем полагать значение I найденным с точностью ε, если выполнено условие | Будем полагать значение I найденным с точностью ε, если выполнено условие | ||
| + | |||
| + | <math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math> | ||
| + | где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки. | ||
| + | |||
| + | Данный метод неэффективен в силу ряда причин: | ||
| + | * в некоторых точках значение функции будет вычисляться несколько раз; | ||
| + | * на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования. | ||
== Вычислительное ядро алгоритма == | == Вычислительное ядро алгоритма == | ||
Версия 23:14, 15 октября 2016
Содержание
- 1 ЧАСТЬ. Свойства и структура алгоритмов
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 ЧАСТЬ. Программная реализация алгоритма
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]:
[math] \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)[/math]
Будем полагать значение I найденным с точностью ε, если выполнено условие
[math] |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 \gt n_2, [/math] где [math] n_1 [/math] и [math] n_2 [/math] - количество узлов, образующих две разные сетки.
Данный метод неэффективен в силу ряда причин:
- в некоторых точках значение функции будет вычисляться несколько раз;
- на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.
1.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
Последовательные алгоритмы
Метод трапеций
Метод рекурсивного деления
Метод локального стека
