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

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

2016-11-25T07:27:36Z

Sannikovats:

Основные авторы описания:[[Участница:Sannikovats| Санникова Татьяна Сергеевна]](п. 1.1-1.6),[[Участник:Plukshin| Лукшин Петр Андреевич]](п. 1.7-1.10, 2.4, 2.7).
{{algorithm
| name = Вычисление определённого интеграла с использованием адаптивно сгущающейся сетки
| input_data = 1 функция,зависящая от 1 переменной, 3 числа ( точность ε и границы отрезка интегрирования[A,B])
| output_data = 1 число
}}

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

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

Допустим, нам дана функция <math>f(x)</math> , определенная на отрезке, и возможность получать ее численное значение в любой из точек области определения за фиксированное время. Задача — вычислить определенный интеграл данной функции по заданной области и дать оценку погрешности вычисления. В случае, когда можно вычислить интеграл по формуле Ньютона-Лейбница, зная первообразную искомой функции, проблем не возникает. Однако, если первообразной нет, решение можно получить благодаря численным методам. Так определенному интегралу можно дать простую геометрическую интерпретацию - он равен площади криволинейной трапеции, ограниченной слева и справа вертикальными прямыми x=a, x=b, снизу - прямой y=0, а сверху – кривой y=f(x).

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

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

Простейший из них - это метод рекурсивного деления, выигрыш от применения которого достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Интервал интегрирования разбивается на две части и независимо интегрируется функция <math>f(x)</math> на каждой из них при соответствующих шагах интегрирования. Процедуру разбиения отрезков можно рекурсивно повторить до получения отрезков, на которых подынтегральная функция имеет простой вид и может быть аппроксимирована отрезком прямой с заданной точностью. Но при распараллеливании этого алгоритма (т.е. при запуске попарно подпрограмм, обрабатывающих половинки разбиваемого интервала) можно столкнуться со следующей проблемой: в реальной системе число процессоров ограничено и время, необходимое для порождения параллельных процессов существенно не равно нулю. А значит, запуск процессов, число которых значительно превышает число физических процессов системы при решении рассматриваемой задачи, приводит к увеличению времени ее решения по сравнению с последовательной программой. Основная сложность построения параллельного алгоритма на основе рассмотренного последовательного алгоритма, кроется в том, что, хотя несколько ветвей программы могли бы одновременно обрабатывать разные части интервала интегрирования, координаты концов этих отрезков хранятся в программном стеке процесса и фактически недоступны программисту. Если бы они были расположены в некотором явно описанном массиве, можно было бы передать их по частям для обработки разным нитям программы. Поэтому, необходимо рассмотреть метод локального стека, позволяющий распределить вычислительную работу между ограниченным числом процессов.

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

В основе этого алгоритма лежит описанный выше метод рекурсивного деления. Только данный метод использует массив данных, доступ к которым осуществляется по принципу стека - первым удаляется последний из добавленных элементов. В рассматриваемом алгоритме вместо стека можно было использовать и другие способы хранения заданий, например очередь. Стек выбран исключительно из соображений простоты реализации. Времена выполнения рассмотренных алгоритмов отличаются примерно на 5% в пользу локального стека, таким образом, алгоритм "локального стека" будем считать наилучшим из имеющихся в нашем распоряжении последовательных методов и на его примере построим дальнейшее описание.

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 
В качестве модельной задачи рассматривается проблема вычисления с точностью ε значения определенного интеграла 
[[Файл:1sann.jpg]]

Пусть на отрезке <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> J_n(A,B)=\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>

[[Файл: 2sann.jpg]][[Файл:3sann.jpg]]

Будем полагать значение <math> J </math> найденным с точностью <math> \epsilon </math>, если выполнено условие:

<math> |J_{n_1} - J_{n_2}| \leq \epsilon |J_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Используемые в алгоритме формулы: 
*Из метода трапеций <math>sAB=\frac{f(A)+f(B)}{2}*(B-A)</math>

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

Основное время работы алгоритма приходится на: 
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала,
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

=== Макроструктура алгоритма ===
Как уже упоминалось в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть рассматриваемого метода составляют рекурсивные операции нахождения середины отрезка <math> C=(A+B)/2 </math>, вычисление значения функции в этой точке <math> fC=function(C)</math>, нахождение площадей трапеций, образованных после разбиение отрезка и их суммирование <math> sAC=(fA+fC)*(C-A)/2, sCB=(fC+fB)*(B-C)/2, sACB=sAC+sCB </math>, а также нахождение отношения модуля разности площади трапеции до разбиения отрезка и результату, полученному после разбиения, к сумме площадей после разбиения <math> |sAB - sACB|\leq \epsilon * |sACB| </math>, что обеспечивает проверку условия устойчивости. 

=== Схема реализации последовательного алгоритма ===
В реализации алгоритма используется такая структура данных, как стек, в котором хранятся координаты концов отрезков:
<source lang="cpp">
//Данные, описывающие стек
int sp = 0; // Указатель вершины стека

// Массив структур, в которых хранятся отложенные задания
struct mstk {
double A;//координата левой границы отрезка интегрирования
double B;//координата правой границы отрезка интегрирования
double fA;//значение функции на границе A
double fB;//значение функции на границе B
double s;//частичная сумма
} mstk[N];
</source>
В процедурах работы со стеком доступны следующие операции: 
1)Проверка наличия элементов в стеке:
<source lang="cpp">
#define STACK_IS_NOT_FREE (sp > 0)
</source>
2)Операция "положить в стек":
<source lang="cpp">
#define PUT_INTO_STACK(A, B, fA, fB, s) {
mstk[sp].A = A;
mstk[sp].B = B;
mstk[sp].fA = fA;
mstk[sp].fB = fB;
mstk[sp].s = s;
++sp;
}
</source>
3)Операция "взять из стека верхний элемент":

<source lang="cpp">
#define GET_FROM_STACK(A, B, fA, fB, s) {
--sp;
A = mstk[sp].A;
B = mstk[sp].B;
fA = mstk[sp].fA;
fB = mstk[sp].fB;
s = mstk[sp].s;
}

</source>

// Заданная функция f(x)
double f(double x);

Рассмотрим функцию JLS, вычисляющую определенный интеграл от f(x) на [A,B] с заданной точностью eps методом локального стека, которая является вычислительным ядром алгоритма:
<source lang="cpp">
//на вход функции подаются границы отрезка и точность
int JLS(double A, double B, double eps) {
double J = 0;//значение интеграла
double fA = f(A);//значение функции f(x)на границе A
double fB = f(B);//значение функции f(x)на границе B
double C;//середина отрезка [A,B]
double fC;//значение функции f(x)в середине отрезка [A,B]
double sAB = (fA + fB)*(B - A)/2;//вычисление площади трапеции с основанием AB
double sAC;//площадь трапеции с основанием AС
double sCB;//площадь трапеции с основанием СВ
double sACB;//сумма sAC и sCB
//бесконечный цикл с предусловием, прерывающийся при выполнении условия на порядок точности
while(1) {
C = (A + B)/2;//середина отрезка
fC = f(C);
sAC = (fA + fC)*(C - A)/2;
sCB = (fC + fB )*(B - C)/2;
sACB = sAC + sCB;
//проверка выполнения условия на порядок точности:
if(abs(sAB - sACB) >= eps*abs(sACB)) {
PUT_INTO_STACK(A, C, fA, fC, sAC);
A = C;
fA = fC;
sAB = sCB;
}
else {
J += sACB;
if(STACK_IS_NOT_FREE) {
break;
}
GET_FROM_STACK(A, B, fA, fB, sAB);
}
}
return J;
}
</source>
В рамках этой функции поэтапно выполняются следующие операции:
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала (возвращение к пункту 2),
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

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

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

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

*Пусть есть доступный всем параллельным процессам список отрезков интегрирования,организованный в виде стека. Назовем его глобальным стеком.
*Пусть у каждого процесса есть свой, доступный только этому процессу локальный стек
*Перед запуском параллельных процессов в глобальный стек помещается единственная запись (в дальнейшем "отрезок"):
координаты концов отрезка интегрирования,
значения функции на концах,
приближенное значение интеграла на этом отрезке.
*Тогда, предлагается следующая схема алгоритма, выполняемого каждым из параллельных процессов:

Пока в глобальном стеке есть отрезки:
*взять один отрезок из глобального стека
*выполнить алгоритм локального стека, но,если при записи в локальный стек в нем есть несколько отрезков, а в глобальном стеке отрезки отсутствуют, то переместить часть отрезков из локального стека в глобальный стек
* по исчерпании локального стека добавить полученную частичную сумму к общему значению интеграла. 

[[Файл:Lukshin_01.png|1260px|thumb|left|Рис. Информационная структура алгоритма глобального стека]] 

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

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

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

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 

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

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===
В настоящее время проблемой вычисления определенного графа на адаптивной сетке по нашим сведениям занимались только М.В. Якобовский и Е.Ю. Кулькова, рассматривавшие в своей работе "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ" методы локального и глобального стеков.

==Литература==
#Якобовский М.В.
Введение в параллельные методы решения задач
#М.В. Якобовский и Е.Ю. Кулькова "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ"

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

2016-11-25T07:15:55Z

Sannikovats:

Основные авторы описания:[[Участница:Sannikovats| Санникова Татьяна Сергеевна]](п. 1.1-1.6),[[Участник:Plukshin| Лукшин Петр Андреевич]](п. 1.7-1.10, 2.4, 2.7).
{{algorithm
| name = Вычисление определённого интеграла с использованием адаптивно сгущающейся сетки
| input_data = 1 функция,зависящая от 1 переменной, 3 числа ( точность ε и границы отрезка интегрирования[A,B])
| output_data = 1 число
}}

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

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

Допустим, нам дана функция <math>f(x)</math> , определенная на отрезке, и возможность получать ее численное значение в любой из точек области определения за фиксированное время. Задача — вычислить определенный интеграл данной функции по заданной области и дать оценку погрешности вычисления. В случае, когда можно вычислить интеграл по формуле Ньютона-Лейбница, зная первообразную искомой функции, проблем не возникает. Однако, если первообразной нет, решение можно получить благодаря численным методам. Так определенному интегралу можно дать простую геометрическую интерпретацию - он равен площади криволинейной трапеции, ограниченной слева и справа вертикальными прямыми x=a, x=b, снизу - прямой y=0, а сверху – кривой y=f(x).

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

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

Простейший из них - это метод рекурсивного деления, выигрыш от применения которого достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Интервал интегрирования разбивается на две части и независимо интегрируется функция <math>f(x)</math> на каждой из них при соответствующих шагах интегрирования. Процедуру разбиения отрезков можно рекурсивно повторить до получения отрезков, на которых подынтегральная функция имеет простой вид и может быть аппроксимирована отрезком прямой с заданной точностью. Но при распараллеливании этого алгоритма (т.е. при запуске попарно подпрограмм, обрабатывающих половинки разбиваемого интервала) можно столкнуться со следующей проблемой: в реальной системе число процессоров ограничено и время, необходимое для порождения параллельных процессов существенно не равно нулю. А значит, запуск процессов, число которых значительно превышает число физических процессов системы при решении рассматриваемой задачи, приводит к увеличению времени ее решения по сравнению с последовательной программой. Основная сложность построения параллельного алгоритма на основе рассмотренного последовательного алгоритма, кроется в том, что, хотя несколько ветвей программы могли бы одновременно обрабатывать разные части интервала интегрирования, координаты концов этих отрезков хранятся в программном стеке процесса и фактически недоступны программисту. Если бы они были расположены в некотором явно описанном массиве, можно было бы передать их по частям для обработки разным нитям программы. Поэтому, необходимо рассмотреть метод локального стека, позволяющий распределить вычислительную работу между ограниченным числом процессов.

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

В основе этого алгоритма лежит описанный выше метод рекурсивного деления. Только данный метод использует массив данных, доступ к которым осуществляется по принципу стека - первым удаляется последний из добавленных элементов. В рассматриваемом алгоритме вместо стека можно было использовать и другие способы хранения заданий, например очередь. Стек выбран исключительно из соображений простоты реализации. Времена выполнения рассмотренных алгоритмов отличаются примерно на 5% в пользу локального стека, таким образом, алгоритм "локального стека" будем считать наилучшим из имеющихся в нашем распоряжении последовательных методов и на его примере построим дальнейшее описание.

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 
В качестве модельной задачи рассматривается проблема вычисления с точностью ε значения определенного интеграла 
[[Файл:1sann.jpg]]

Пусть на отрезке <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> J_n(A,B)=\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>

[[Файл: 2sann.jpg]][[Файл:3sann.jpg]]

Будем полагать значение <math> J </math> найденным с точностью <math> \epsilon </math>, если выполнено условие:

<math> |J_{n_1} - J_{n_2}| \leq \epsilon |J_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Используемые в алгоритме формулы: 
*Из метода трапеций <math>sAB=\frac{f(A)+f(B)}{2}*(B-A)</math>

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

Основное время работы алгоритма приходится на: 
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала,
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

=== Макроструктура алгоритма ===
Как уже упоминалось в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть рассматриваемого метода составляют рекурсивные операции нахождения середины отрезка <math> C=(A+B)/2 </math>, вычисление значения функции в этой точке <math> fC=function(C)</math>, нахождение площадей трапеций, образованных после разбиение отрезка и их суммирование <math> sAC=(fA+fC)*(C-A)/2, sCB=(fC+fB)*(B-C)/2, sACB=sAC+sCB </math>, а также нахождение отношения модуля разности площади трапеции до разбиения отрезка и результату, полученному после разбиения, к сумме площадей после разбиения <math> |sAB - sACB|\leq \epsilon * |sACB| </math>, что обеспечивает проверку условия устойчивости. 

=== Схема реализации последовательного алгоритма ===
В реализации алгоритма используется такая структура данных, как стек, в котором хранятся координаты концов отрезков:
<source lang="cpp">
//Данные, описывающие стек
int sp = 0; // Указатель вершины стека

// Массив структур, в которых хранятся отложенные задания
struct mstk {
double A;//координата левой границы отрезка интегрирования
double B;//координата правой границы отрезка интегрирования
double fA;//значение функции на границе A
double fB;//значение функции на границе B
double s;//частичная сумма
} mstk[N];
</source>
В процедурах работы со стеком доступны следующие операции: 
1)Проверка наличия элементов в стеке:
<source lang="cpp">
#define STACK_IS_NOT_FREE (sp > 0)
</source>
2)Операция "положить в стек":
<source lang="cpp">
#define PUT_INTO_STACK(A, B, fA, fB, s) {
mstk[sp].A = A;
mstk[sp].B = B;
mstk[sp].fA = fA;
mstk[sp].fB = fB;
mstk[sp].s = s;
++sp;
}
</source>
3)Операция "взять из стека верхний элемент":

<source lang="cpp">
#define GET_FROM_STACK(A, B, fA, fB, s) {
--sp;
A = mstk[sp].A;
B = mstk[sp].B;
fA = mstk[sp].fA;
fB = mstk[sp].fB;
s = mstk[sp].s;
}

</source>

// Заданная функция f(x)
double f(double x);

Рассмотрим функцию JLS, вычисляющую определенный интеграл от f(x) на [A,B] с заданной точностью eps методом локального стека, которая является вычислительным ядром алгоритма:
<source lang="cpp">
//на вход функции подаются границы отрезка и точность
int JLS(double A, double B, double eps) {
double J = 0;//значение интеграла
double fA = f(A);//значение функции f(x)на границе A
double fB = f(B);//значение функции f(x)на границе B
double C;//середина отрезка [A,B]
double fC;//значение функции f(x)в середине отрезка [A,B]
double sAB = (fA + fB)*(B - A)/2;//вычисление площади трапеции с основанием AB
double sAC;//площадь трапеции с основанием AС
double sCB;//площадь трапеции с основанием СВ
double sACB;//сумма sAC и sCB
//бесконечный цикл с предусловием, прерывающийся при выполнении условия на порядок точности
while(1) {
C = (A + B)/2;//середина отрезка
fC = f(C);
sAC = (fA + fC)*(C - A)/2;
sCB = (fC + fB )*(B - C)/2;
sACB = sAC + sCB;
//проверка выполнения условия на порядок точности:
if(abs(sAB - sACB) >= eps*abs(sACB)) {
PUT_INTO_STACK(A, C, fA, fC, sAC);
A = C;
fA = fC;
sAB = sCB;
}
else {
J += sACB;
if(STACK_IS_NOT_FREE) {
break;
}
GET_FROM_STACK(A, B, fA, fB, sAB);
}
}
return J;
}
</source>
В рамках этой функции поэтапно выполняются следующие операции:
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала (возвращение к пункту 2),
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

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

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

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

*Пусть есть доступный всем параллельным процессам список отрезков интегрирования,организованный в виде стека. Назовем его глобальным стеком.
*Пусть у каждого процесса есть свой, доступный только этому процессу локальный стек
*Перед запуском параллельных процессов в глобальный стек помещается единственная запись (в дальнейшем "отрезок"):
координаты концов отрезка интегрирования,
значения функции на концах,
приближенное значение интеграла на этом отрезке.
*Тогда, предлагается следующая схема алгоритма, выполняемого каждым из параллельных процессов:

Пока в глобальном стеке есть отрезки:
*взять один отрезок из глобального стека
*выполнить алгоритм локального стека, но,если при записи в локальный стек в нем есть несколько отрезков, а в глобальном стеке отрезки отсутствуют, то переместить часть отрезков из локального стека в глобальный стек
* по исчерпании локального стека добавить полученную частичную сумму к общему значению интеграла. 

[[Файл:Lukshin_01.png|1000px|thumb|left|Рис. Информационная структура алгоритма глобального стека]] 
На рисунке изображена информационная структура алгоритма, на которой заметна его внутренняя цикличность.

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

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

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 

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

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===
В настоящее время проблемой вычисления определенного графа на адаптивной сетке по нашим сведениям занимались только М.В. Якобовский и Е.Ю. Кулькова, рассматривавшие в своей работе "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ" методы локального и глобального стеков.

==Литература==
#Якобовский М.В.
Введение в параллельные методы решения задач
#М.В. Якобовский и Е.Ю. Кулькова "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ"

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

2016-11-20T18:18:51Z

Sannikovats:

{{algorithm
| name = Вычисление определённого интеграла с использованием адаптивно сгущающейся сетки
| input_data = 1 функция,зависящая от 1 переменной, 3 числа ( точность ε и границы отрезка интегрирования[A,B])
| output_data = 1 число
}}

Основные авторы описания:[[Участница:Sannikovats| Санникова Татьяна Сергеевна]](п.1.1-1.6),[[Участник:Plukshin| Лукшин Петр Андреевич]](п.1.7-1.10,2.4,2.7).

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

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

Допустим, нам дана функция <math>f(x)</math> , определенная на отрезке, и возможность получать ее численное значение в любой из точек области определения за фиксированное время. Задача — вычислить определенный интеграл данной функции по заданной области и дать оценку погрешности вычисления. В случае, когда можно вычислить интеграл по формуле Ньютона-Лейбница, зная первообразную искомой функции, проблем не возникает. Однако, если первообразной нет, решение можно получить благодаря численным методам. Так определенному интегралу можно дать простую геометрическую интерпретацию - он равен площади криволинейной трапеции, ограниченной слева и справа вертикальными прямыми x=a, x=b, снизу - прямой y=0, а сверху – кривой y=f(x).

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

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

Простейший из них - это метод рекурсивного деления, выигрыш от применения которого достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Интервал интегрирования разбивается на две части и независимо интегрируется функция <math>f(x)</math> на каждой из них при соответствующих шагах интегрирования. Процедуру разбиения отрезков можно рекурсивно повторить до получения отрезков, на которых подынтегральная функция имеет простой вид и может быть аппроксимирована отрезком прямой с заданной точностью. Но при распараллеливании этого алгоритма (т.е. при запуске попарно подпрограмм, обрабатывающих половинки разбиваемого интервала) можно столкнуться со следующей проблемой: в реальной системе число процессоров ограничено и время, необходимое для порождения параллельных процессов существенно не равно нулю. А значит, запуск процессов, число которых значительно превышает число физических процессов системы при решении рассматриваемой задачи, приводит к увеличению времени ее решения по сравнению с последовательной программой. Основная сложность построения параллельного алгоритма на основе рассмотренного последовательного алгоритма, кроется в том, что, хотя несколько ветвей программы могли бы одновременно обрабатывать разные части интервала интегрирования, координаты концов этих отрезков хранятся в программном стеке процесса и фактически недоступны программисту. Если бы они были расположены в некотором явно описанном массиве, можно было бы передать их по частям для обработки разным нитям программы. Поэтому, необходимо рассмотреть метод локального стека, позволяющий распределить вычислительную работу между ограниченным числом процессов.

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

В основе этого алгоритма лежит описанный выше метод рекурсивного деления. Только данный метод использует массив данных, доступ к которым осуществляется по принципу стека - первым удаляется последний из добавленных элементов. В рассматриваемом алгоритме вместо стека можно было использовать и другие способы хранения заданий, например очередь. Стек выбран исключительно из соображений простоты реализации. Времена выполнения рассмотренных алгоритмов отличаются примерно на 5% в пользу локального стека, таким образом, алгоритм "локального стека" будем считать наилучшим из имеющихся в нашем распоряжении последовательных методов и на его примере построим дальнейшее описание.

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 
В качестве модельной задачи рассматривается проблема вычисления с точностью ε значения определенного интеграла 
[[Файл:1sann.jpg]]

Пусть на отрезке <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> J_n(A,B)=\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>

[[Файл: 2sann.jpg]] [[Файл:3sann.jpg]]

Будем полагать значение <math> J </math> найденным с точностью <math> \epsilon </math>, если выполнено условие:

<math> |J_{n_1} - J_{n_2}| \leq \epsilon |J_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Используемые в алгоритме формулы: 
*Из метода трапеций <math>sAB=\frac{f(A)+f(B)}{2}*(B-A)</math>

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

Основное время работы алгоритма приходится на: 
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала,
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

=== Макроструктура алгоритма ===
Как уже упоминалось в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть рассматриваемого метода составляют рекурсивные операции нахождения середины отрезка <math> C=(A+B)/2 </math>, вычисление значения функции в этой точке <math> fC=function(C)</math>, нахождение площадей трапеций, образованных после разбиение отрезка и их суммирование <math> sAC=(fA+fC)*(C-A)/2, sCB=(fC+fB)*(B-C)/2, sACB=sAC+sCB </math>, а также нахождение отношения модуля разности площади трапеции до разбиения отрезка и результату, полученному после разбиения, к сумме площадей после разбиения <math> |sAB - sACB|\leq \epsilon * |sACB| </math>, что обеспечивает проверку условия устойчивости. 

=== Схема реализации последовательного алгоритма ===
В реализации алгоритма используется такая структура данных, как стек, в котором хранятся координаты концов отрезков:
<source lang="cpp">
//Данные, описывающие стек
int sp = 0; // Указатель вершины стека

// Массив структур, в которых хранятся отложенные задания
struct mstk {
double A;//координата левой границы отрезка интегрирования
double B;//координата правой границы отрезка интегрирования
double fA;//значение функции на границе A
double fB;//значение функции на границе B
double s;//частичная сумма
} mstk[N];
</source>
В процедурах работы со стеком доступны следующие операции: 
1)Проверка наличия элементов в стеке:
<source lang="cpp">
#define STACK_IS_NOT_FREE (sp > 0)
</source>
2)Операция "положить в стек":
<source lang="cpp">
#define PUT_INTO_STACK(A, B, fA, fB, s) {
mstk[sp].A = A;
mstk[sp].B = B;
mstk[sp].fA = fA;
mstk[sp].fB = fB;
mstk[sp].s = s;
++sp;
}
</source>
3)Операция "взять из стека верхний элемент":

<source lang="cpp">
#define GET_FROM_STACK(A, B, fA, fB, s) {
--sp;
A = mstk[sp].A;
B = mstk[sp].B;
fA = mstk[sp].fA;
fB = mstk[sp].fB;
s = mstk[sp].s;
}

</source>

// Заданная функция f(x)
double f(double x);

Рассмотрим функцию JLS, вычисляющую определенный интеграл от f(x) на [A,B] с заданной точностью eps методом локального стека, которая является вычислительным ядром алгоритма:
<source lang="cpp">
//на вход функции подаются границы отрезка и точность
int JLS(double A, double B, double eps) {
double J = 0;//значение интеграла
double fA = f(A);//значение функции f(x)на границе A
double fB = f(B);//значение функции f(x)на границе B
double C;//середина отрезка [A,B]
double fC;//значение функции f(x)в середине отрезка [A,B]
double sAB = (fA + fB)*(B - A)/2;//вычисление площади трапеции с основанием AB
double sAC;//площадь трапеции с основанием AС
double sCB;//площадь трапеции с основанием СВ
double sACB;//сумма sAC и sCB
//бесконечный цикл с предусловием, прерывающийся при выполнении условия на порядок точности
while(1) {
C = (A + B)/2;//середина отрезка
fC = f(C);
sAC = (fA + fC)*(C - A)/2;
sCB = (fC + fB )*(B - C)/2;
sACB = sAC + sCB;
//проверка выполнения условия на порядок точности:
if(abs(sAB - sACB) >= eps*abs(sACB)) {
PUT_INTO_STACK(A, C, fA, fC, sAC);
A = C;
fA = fC;
sAB = sCB;
}
else {
J += sACB;
if(STACK_IS_NOT_FREE) {
break;
}
GET_FROM_STACK(A, B, fA, fB, sAB);
}
}
return J;
}
</source>
В рамках этой функции поэтапно выполняются следующие операции:
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала (возвращение к пункту 2),
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

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

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

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

*Пусть есть доступный всем параллельным процессам список отрезков интегрирования,организованный в виде стека. Назовем его глобальным стеком.
*Пусть у каждого процесса есть свой, доступный только этому процессу локальный стек
*Перед запуском параллельных процессов в глобальный стек помещается единственная запись (в дальнейшем "отрезок"):
координаты концов отрезка интегрирования,
значения функции на концах,
приближенное значение интеграла на этом отрезке.
*Тогда, предлагается следующая схема алгоритма, выполняемого каждым из параллельных процессов:

Пока в глобальном стеке есть отрезки:
*взять один отрезок из глобального стека
*выполнить алгоритм локального стека, но,если при записи в локальный стек в нем есть несколько отрезков, а в глобальном стеке отрезки отсутствуют, то переместить часть отрезков из локального стека в глобальный стек
* по исчерпании локального стека добавить полученную частичную сумму к общему значению интеграла.

[[Файл:luksh.jpg]]
На рисунке изображен информационный граф, где k - это глубина алгоритма, а + обозначено суммирование площадей трапеций.

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

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

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 

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

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===
В настоящее время проблемой вычисления определенного графа на адаптивной сетке по нашим сведениям занимались только М.В. Якобовский и Е.Ю. Кулькова, рассматривавшие в своей работе "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ" методы локального и глобального стеков.

==Литература==
#Якобовский М.В.
Введение в параллельные методы решения задач
#М.В. Якобовский и Е.Ю. Кулькова "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ"

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

2016-11-15T19:49:43Z

Sannikovats:

{{algorithm
| name = Вычисление определённого интеграла с использованием адаптивно сгущающейся сетки
| input_data = 1 функция,зависящая от 1 переменной, 3 числа ( точность ε и границы отрезка интегрирования[A,B])
| output_data = 1 число
}}

Основные авторы описания:[[Участница:Sannikovats| Санникова Татьяна Сергеевна]](п.1.1-1.6),[[Участник:Plukshin| Лукшин Петр Андреевич]](п.1.7-2.2).

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

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

Допустим, нам дана функция <math>f(x)</math> , определенная на отрезке, и возможность получать ее численное значение в любой из точек области определения за фиксированное время. Задача — вычислить определенный интеграл данной функции по заданной области и дать оценку погрешности вычисления. В случае, когда можно вычислить интеграл по формуле Ньютона-Лейбница, зная первообразную искомой функции, проблем не возникает. Однако, если первообразной нет, решение можно получить благодаря численным методам. Так определенному интегралу можно дать простую геометрическую интерпретацию - он равен площади криволинейной трапеции, ограниченной слева и справа вертикальными прямыми x=a, x=b, снизу - прямой y=0, а сверху – кривой y=f(x).

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

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

Простейший из них - это метод рекурсивного деления, выигрыш от применения которого достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Интервал интегрирования разбивается на две части и независимо интегрируется функция <math>f(x)</math> на каждой из них при соответствующих шагах интегрирования. Процедуру разбиения отрезков можно рекурсивно повторить до получения отрезков, на которых подынтегральная функция имеет простой вид и может быть аппроксимирована отрезком прямой с заданной точностью. Но при распараллеливании этого алгоритма (т.е. при запуске попарно подпрограмм, обрабатывающих половинки разбиваемого интервала) можно столкнуться со следующей проблемой: в реальной системе число процессоров ограничено и время, необходимое для порождения параллельных процессов существенно не равно нулю. А значит, запуск процессов, число которых значительно превышает число физических процессов системы при решении рассматриваемой задачи, приводит к увеличению времени ее решения по сравнению с последовательной программой. Основная сложность построения параллельного алгоритма на основе рассмотренного последовательного алгоритма, кроется в том, что, хотя несколько ветвей программы могли бы одновременно обрабатывать разные части интервала интегрирования, координаты концов этих отрезков хранятся в программном стеке процесса и фактически недоступны программисту. Если бы они были расположены в некотором явно описанном массиве, можно было бы передать их по частям для обработки разным нитям программы. Поэтому, необходимо рассмотреть метод локального стека, позволяющий распределить вычислительную работу между ограниченным числом процессов.

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

В основе этого алгоритма лежит описанный выше метод рекурсивного деления. Только данный метод использует массив данных, доступ к которым осуществляется по принципу стека - первым удаляется последний из добавленных элементов. В рассматриваемом алгоритме вместо стека можно было использовать и другие способы хранения заданий, например очередь. Стек выбран исключительно из соображений простоты реализации. Времена выполнения рассмотренных алгоритмов отличаются примерно на 5% в пользу локального стека, таким образом, алгоритм "локального стека" будем считать наилучшим из имеющихся в нашем распоряжении последовательных методов и на его примере построим дальнейшее описание.

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 
В качестве модельной задачи рассматривается проблема вычисления с точностью ε значения определенного интеграла 
[[Файл:1sann.jpg]]

Пусть на отрезке <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> J_n(A,B)=\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>

[[Файл: 2sann.jpg]] [[Файл:3sann.jpg]]

Будем полагать значение <math> J </math> найденным с точностью <math> \epsilon </math>, если выполнено условие:

<math> |J_{n_1} - J_{n_2}| \leq \epsilon |J_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Используемые в алгоритме формулы: 
*Из метода трапеций <math>sAB=\frac{f(A)+f(B)}{2}*(B-A)</math>

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

Основное время работы алгоритма приходится на: 
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала,
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

=== Макроструктура алгоритма ===
Как уже упоминалось в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть рассматриваемого метода составляют рекурсивные операции нахождения середины отрезка <math> C=(A+B)/2 </math>, вычисление значения функции в этой точке <math> fC=function(C)</math>, нахождение площадей трапеций, образованных после разбиение отрезка и их суммирование <math> sAC=(fA+fC)*(C-A)/2, sCB=(fC+fB)*(B-C)/2, sACB=sAC+sCB </math>, а также нахождение отношения модуля разности площади трапеции до разбиения отрезка и результату, полученному после разбиения, к сумме площадей после разбиения <math> |sAB - sACB|\leq \epsilon * |sACB| </math>, что обеспечивает проверку условия устойчивости. 

=== Схема реализации последовательного алгоритма ===
В реализации алгоритма используется такая структура данных, как стек, в котором хранятся координаты концов отрезков:
<source lang="cpp">
//Данные, описывающие стек
int sp = 0; // Указатель вершины стека

// Массив структур, в которых хранятся отложенные задания
struct mstk {
double A;//координата левой границы отрезка интегрирования
double B;//координата правой границы отрезка интегрирования
double fA;//значение функции на границе A
double fB;//значение функции на границе B
double s;//частичная сумма
} mstk[N];
</source>
В процедурах работы со стеком доступны следующие операции: 
1)Проверка наличия элементов в стеке:
<source lang="cpp">
#define STACK_IS_NOT_FREE (sp > 0)
</source>
2)Операция "положить в стек":
<source lang="cpp">
#define PUT_INTO_STACK(A, B, fA, fB, s) {
mstk[sp].A = A;
mstk[sp].B = B;
mstk[sp].fA = fA;
mstk[sp].fB = fB;
mstk[sp].s = s;
++sp;
}
</source>
3)Операция "взять из стека верхний элемент":

<source lang="cpp">
#define GET_FROM_STACK(A, B, fA, fB, s) {
--sp;
A = mstk[sp].A;
B = mstk[sp].B;
fA = mstk[sp].fA;
fB = mstk[sp].fB;
s = mstk[sp].s;
}

</source>

// Заданная функция f(x)
double f(double x);

Рассмотрим функцию JLS, вычисляющую определенный интеграл от f(x) на [A,B] с заданной точностью eps методом локального стека, которая является вычислительным ядром алгоритма:
<source lang="cpp">
//на вход функции подаются границы отрезка и точность
int JLS(double A, double B, double eps) {
double J = 0;//значение интеграла
double fA = f(A);//значение функции f(x)на границе A
double fB = f(B);//значение функции f(x)на границе B
double C;//середина отрезка [A,B]
double fC;//значение функции f(x)в середине отрезка [A,B]
double sAB = (fA + fB)*(B - A)/2;//вычисление площади трапеции с основанием AB
double sAC;//площадь трапеции с основанием AС
double sCB;//площадь трапеции с основанием СВ
double sACB;//сумма sAC и sCB
//бесконечный цикл с предусловием, прерывающийся при выполнении условия на порядок точности
while(1) {
C = (A + B)/2;//середина отрезка
fC = f(C);
sAC = (fA + fC)*(C - A)/2;
sCB = (fC + fB )*(B - C)/2;
sACB = sAC + sCB;
//проверка выполнения условия на порядок точности:
if(abs(sAB - sACB) >= eps*abs(sACB)) {
PUT_INTO_STACK(A, C, fA, fC, sAC);
A = C;
fA = fC;
sAB = sCB;
}
else {
J += sACB;
if(STACK_IS_NOT_FREE) {
break;
}
GET_FROM_STACK(A, B, fA, fB, sAB);
}
}
return J;
}
</source>
В рамках этой функции поэтапно выполняются следующие операции:
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала (возвращение к пункту 2),
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

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

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

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

*Пусть есть доступный всем параллельным процессам список отрезков интегрирования,организованный в виде стека. Назовем его глобальным стеком.
*Пусть у каждого процесса есть свой, доступный только этому процессу локальный стек
*Перед запуском параллельных процессов в глобальный стек помещается единственная запись (в дальнейшем "отрезок"):
координаты концов отрезка интегрирования,
значения функции на концах,
приближенное значение интеграла на этом отрезке.
*Тогда, предлагается следующая схема алгоритма, выполняемого каждым из параллельных процессов:

Пока в глобальном стеке есть отрезки:
*взять один отрезок из глобального стека
*выполнить алгоритм локального стека, но,если при записи в локальный стек в нем есть несколько отрезков, а в глобальном стеке отрезки отсутствуют, то переместить часть отрезков из локального стека в глобальный стек
* по исчерпании локального стека добавить полученную частичную сумму к общему значению интеграла.

[[Файл:luksh.jpg]]
На рисунке изображен информационный граф, где k - это глубина алгоритма, а + обозначено суммирование площадей трапеций.

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

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

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 

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

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===
В настоящее время проблемой вычисления определенного графа на адаптивной сетке по нашим сведениям занимались только М.В. Якобовский и Е.Ю. Кулькова, рассматривавшие в своей работе "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ" методы локального и глобального стеков.

==Литература==
#Якобовский М.В.
Введение в параллельные методы решения задач
#М.В. Якобовский и Е.Ю. Кулькова "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ"

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

2016-11-09T06:30:02Z

Sannikovats:

{{algorithm
| name = Вычисление определённого интеграла с использованием адаптивно сгущающейся сетки
| input_data = 1 функция,зависящая от 1 переменной, 3 числа ( точность ε и границы отрезка интегрирования[A,B])
| output_data = 1 число
}}

Основные авторы описания:[[Участница:Sannikovats| Санникова Татьяна Сергеевна]](п.1.1-1.6),[[Участник:Plukshin| Лукшин Петр Андреевич]](п.1.7-2.2).

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

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

Допустим, нам дана функция <math>f(x)</math> , определенная на отрезке, и возможность получать ее численное значение в любой из точек области определения за фиксированное время. Задача — вычислить определенный интеграл данной функции по заданной области и дать оценку погрешности вычисления. В случае, когда можно вычислить интеграл по формуле Ньютона-Лейбница, зная первообразную искомой функции, проблем не возникает. Однако, если первообразной нет, решение можно получить благодаря численным методам. Так определенному интегралу можно дать простую геометрическую интерпретацию - он равен площади криволинейной трапеции, ограниченной слева и справа вертикальными прямыми x=a, x=b, снизу - прямой y=0, а сверху – кривой y=f(x).

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

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

Простейший из них - это метод рекурсивного деления, выигрыш от применения которого достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Интервал интегрирования разбивается на две части и независимо интегрируется функция <math>f(x)</math> на каждой из них при соответствующих шагах интегрирования. Процедуру разбиения отрезков можно рекурсивно повторить до получения отрезков, на которых подынтегральная функция имеет простой вид и может быть аппроксимирована отрезком прямой с заданной точностью. Но при распараллеливании этого алгоритма (т.е. при запуске попарно подпрограмм, обрабатывающих половинки разбиваемого интервала) можно столкнуться со следующей проблемой: в реальной системе число процессоров ограничено и время, необходимое для порождения параллельных процессов существенно не равно нулю. А значит, запуск процессов, число которых значительно превышает число физических процессов системы при решении рассматриваемой задачи, приводит к увеличению времени ее решения по сравнению с последовательной программой. Основная сложность построения параллельного алгоритма на основе рассмотренного последовательного алгоритма, кроется в том, что, хотя несколько ветвей программы могли бы одновременно обрабатывать разные части интервала интегрирования, координаты концов этих отрезков хранятся в программном стеке процесса и фактически недоступны программисту. Если бы они были расположены в некотором явно описанном массиве, можно было бы передать их по частям для обработки разным нитям программы. Поэтому, необходимо рассмотреть метод локального стека, позволяющий распределить вычислительную работу между ограниченным числом процессов.

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

В основе этого алгоритма лежит описанный выше метод рекурсивного деления. Только данный метод использует массив данных, доступ к которым осуществляется по принципу стека - первым удаляется последний из добавленных элементов. В рассматриваемом алгоритме вместо стека можно было использовать и другие способы хранения заданий, например очередь. Стек выбран исключительно из соображений простоты реализации. Времена выполнения рассмотренных алгоритмов отличаются примерно на 5% в пользу локального стека, таким образом, алгоритм "локального стека" будем считать наилучшим из имеющихся в нашем распоряжении последовательных методов и на его примере построим дальнейшее описание.

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 
В качестве модельной задачи рассматривается проблема вычисления с точностью ε значения определенного интеграла 
[[Файл:1sann.jpg]]

Пусть на отрезке <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> J_n(A,B)=\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>

[[Файл: 2sann.jpg]] [[Файл:3sann.jpg]]

Будем полагать значение <math> J </math> найденным с точностью <math> \epsilon </math>, если выполнено условие:

<math> |J_{n_1} - J_{n_2}| \leq \epsilon |J_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Используемые в алгоритме формулы: 
*Из метода трапеций <math>sAB=\frac{f(A)+f(B)}{2}*(B-A)</math>

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

Основное время работы алгоритма приходится на: 
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала,
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

=== Макроструктура алгоритма ===
Как уже упоминалось в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть рассматриваемого метода составляют рекурсивные операции нахождения середины отрезка <math> C=(A+B)/2 </math>, вычисление значения функции в этой точке <math> fC=function(C)</math>, нахождение площадей трапеций, образованных после разбиение отрезка и их суммирование <math> sAC=(fA+fC)*(C-A)/2, sCB=(fC+fB)*(B-C)/2, sACB=sAC+sCB </math>, а также нахождение отношения модуля разности площади трапеции до разбиения отрезка и результату, полученному после разбиения, к сумме площадей после разбиения <math> |sAB - sACB|\leq \epsilon * |sACB| </math>, что обеспечивает проверку условия устойчивости. 

Также в реализации алгоритма используется такая структура данных, как стек, в котором хранятся координаты концов отрезков:
<source lang="cpp">
//Данные, описывающие стек
int sp = 0; // Указатель вершины стека

// Массив структур, в которых хранятся отложенные задания
struct mstk {
double A;//координата левой границы отрезка интегрирования
double B;//координата правой границы отрезка интегрирования
double fA;//значение функции на границе A
double fB;//значение функции на границе B
double s;//частичная сумма
} mstk[N];
</source>
В процедурах работы со стеком доступны следующие операции: 
1)Проверка наличия элементов в стеке:
<source lang="cpp">
#define STACK_IS_NOT_FREE (sp > 0)
</source>
2)Операция "положить в стек":
<source lang="cpp">
#define PUT_INTO_STACK(A, B, fA, fB, s) {
mstk[sp].A = A;
mstk[sp].B = B;
mstk[sp].fA = fA;
mstk[sp].fB = fB;
mstk[sp].s = s;
++sp;
}
</source>
3)Операция "взять из стека верхний элемент":

<source lang="cpp">
#define GET_FROM_STACK(A, B, fA, fB, s) {
--sp;
A = mstk[sp].A;
B = mstk[sp].B;
fA = mstk[sp].fA;
fB = mstk[sp].fB;
s = mstk[sp].s;
}

</source>

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

// Заданная функция f(x)
double f(double x);

Рассмотрим функцию JLS, вычисляющую определенный интеграл от f(x) на [A,B] с заданной точностью eps методом локального стека, которая является вычислительным ядром алгоритма:
<source lang="cpp">
//на вход функции подаются границы отрезка и точность
int JLS(double A, double B, double eps) {
double J = 0;//значение интеграла
double fA = f(A);//значение функции f(x)на границе A
double fB = f(B);//значение функции f(x)на границе B
double C;//середина отрезка [A,B]
double fC;//значение функции f(x)в середине отрезка [A,B]
double sAB = (fA + fB)*(B - A)/2;//вычисление площади трапеции с основанием AB
double sAC;//площадь трапеции с основанием AС
double sCB;//площадь трапеции с основанием СВ
double sACB;//сумма sAC и sCB
//бесконечный цикл с предусловием, прерывающийся при выполнении условия на порядок точности
while(1) {
C = (A + B)/2;//середина отрезка
fC = f(C);
sAC = (fA + fC)*(C - A)/2;
sCB = (fC + fB )*(B - C)/2;
sACB = sAC + sCB;
//проверка выполнения условия на порядок точности:
if(abs(sAB - sACB) >= eps*abs(sACB)) {
PUT_INTO_STACK(A, C, fA, fC, sAC);
A = C;
fA = fC;
sAB = sCB;
}
else {
J += sACB;
if(STACK_IS_NOT_FREE) {
break;
}
GET_FROM_STACK(A, B, fA, fB, sAB);
}
}
return J;
}
</source>
В рамках этой функции поэтапно выполняются следующие операции:
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала (возвращение к пункту 2),
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

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

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

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

*Пусть есть доступный всем параллельным процессам список отрезков интегрирования,организованный в виде стека. Назовем его глобальным стеком.
*Пусть у каждого процесса есть свой, доступный только этому процессу локальный стек
*Перед запуском параллельных процессов в глобальный стек помещается единственная запись (в дальнейшем "отрезок"):
координаты концов отрезка интегрирования,
значения функции на концах,
приближенное значение интеграла на этом отрезке.
*Тогда, предлагается следующая схема алгоритма, выполняемого каждым из параллельных процессов:

Пока в глобальном стеке есть отрезки:
*взять один отрезок из глобального стека
*выполнить алгоритм локального стека, но,если при записи в локальный стек в нем есть несколько отрезков, а в глобальном стеке отрезки отсутствуют, то переместить часть отрезков из локального стека в глобальный стек
* по исчерпании локального стека добавить полученную частичную сумму к общему значению интеграла.

[[Файл:luksh.jpg]]
На рисунке изображен информационный граф, где k - это глубина алгоритма, а + обозначено суммирование площадей трапеций.

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

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

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 

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

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===
В настоящее время проблемой вычисления определенного графа на адаптивной сетке по нашим сведениям занимались только М.В. Якобовский и Е.Ю. Кулькова, рассматривавшие в своей работе "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ" методы локального и глобального стеков.

==Литература==
#Якобовский М.В.
Введение в параллельные методы решения задач
#М.В. Якобовский и Е.Ю. Кулькова "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ"

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

2016-11-03T14:18:53Z

Sannikovats:

{{algorithm
| name = Вычисление определённого интеграла с использованием адаптивно сгущающейся сетки
| input_data = 1 функция,зависящая от 1 переменной, 3 числа ( точность ε и границы отрезка интегрирования[A,B])
| output_data = 1 число
}}

Основные авторы описания:[[Участница:Sannikovats| Санникова Татьяна Сергеевна]](п.1.1-1.6),[[Участник:Plukshin| Лукшин Петр Андреевич]](п.1.7-2.2).

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

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

Допустим, нам дана функция <math>f(x)</math> , определенная на отрезке, и возможность получать ее численное значение в любой из точек области определения за фиксированное время. Задача — вычислить определенный интеграл данной функции по заданной области и дать оценку погрешности вычисления. В случае, когда можно вычислить интеграл по формуле Ньютона-Лейбница, зная первообразную искомой функции, проблем не возникает. Однако, если первообразной нет, решение можно получить благодаря численным методам. Так определенному интегралу можно дать простую геометрическую интерпретацию - он равен площади криволинейной трапеции, ограниченной слева и справа вертикальными прямыми x=a, x=b, снизу - прямой y=0, а сверху – кривой y=f(x).

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

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

Простейший из них - это метод рекурсивного деления, выигрыш от применения которого достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Интервал интегрирования разбивается на две части и независимо интегрируется функция <math>f(x)</math> на каждой из них при соответствующих шагах интегрирования. Процедуру разбиения отрезков можно рекурсивно повторить до получения отрезков, на которых подынтегральная функция имеет простой вид и может быть аппроксимирована отрезком прямой с заданной точностью. Но при распараллеливании этого алгоритма (т.е. при запуске попарно подпрограмм, обрабатывающих половинки разбиваемого интервала) можно столкнуться со следующей проблемой: в реальной системе число процессоров ограничено и время, необходимое для порождения параллельных процессов существенно не равно нулю. А значит, запуск процессов, число которых значительно превышает число физических процессов системы при решении рассматриваемой задачи, приводит к увеличению времени ее решения по сравнению с последовательной программой. Основная сложность построения параллельного алгоритма на основе рассмотренного последовательного алгоритма, кроется в том, что, хотя несколько ветвей программы могли бы одновременно обрабатывать разные части интервала интегрирования, координаты концов этих отрезков хранятся в программном стеке процесса и фактически недоступны программисту. Если бы они были расположены в некотором явно описанном массиве, можно было бы передать их по частям для обработки разным нитям программы. Поэтому, необходимо рассмотреть метод локального стека, позволяющий распределить вычислительную работу между ограниченным числом процессов.

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

В основе этого алгоритма лежит описанный выше метод рекурсивного деления. Только данный метод использует массив данных, доступ к которым осуществляется по принципу стека - первым удаляется последний из добавленных элементов. В рассматриваемом алгоритме вместо стека можно было использовать и другие способы хранения заданий, например очередь. Стек выбран исключительно из соображений простоты реализации. Времена выполнения рассмотренных алгоритмов отличаются примерно на 5% в пользу локального стека, таким образом, алгоритм "локального стека" будем считать наилучшим из имеющихся в нашем распоряжении последовательных методов и на его примере построим дальнейшее описание.

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 
В качестве модельной задачи рассматривается проблема вычисления с точностью ε значения определенного интеграла 
[[Файл:1sann.jpg]]

Пусть на отрезке <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> J_n(A,B)=\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>

[[Файл: 2sann.jpg]] [[Файл:3sann.jpg]]

Будем полагать значение <math> J </math> найденным с точностью <math> \epsilon </math>, если выполнено условие:

<math> |J_{n_1} - J_{n_2}| \leq \epsilon |J_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Используемые в алгоритме формулы: 
*Из метода трапеций <math>sAB=\frac{f(A)+f(B)}{2}*(B-A)</math>

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

Основное время работы алгоритма приходится на: 
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала,
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

=== Макроструктура алгоритма ===
Как уже упоминалось в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть рассматриваемого метода составляют рекурсивные операции нахождения середины отрезка <math> C=(A+B)/2 </math>, вычисление значения функции в этой точке <math> fC=function(C)</math>, нахождение площадей трапеций, образованных после разбиение отрезка и их суммирование <math> sAC=(fA+fC)*(C-A)/2, sCB=(fC+fB)*(B-C)/2, sACB=sAC+sCB </math>, а также нахождение отношения модуля разности площади трапеции до разбиения отрезка и результату, полученному после разбиения, к сумме площадей после разбиения <math> |sAB - sACB|\leq \epsilon * |sACB| </math>, что обеспечивает проверку условия устойчивости. 

Также в реализации алгоритма используется такая структура данных, как стек, в котором хранятся координаты концов отрезков:
<source lang="cpp">
//Данные, описывающие стек
int sp = 0; // Указатель вершины стека

// Массив структур, в которых хранятся отложенные задания
struct mstk {
double A;//координата левой границы отрезка интегрирования
double B;//координата правой границы отрезка интегрирования
double fA;//значение функции на границе A
double fB;//значение функции на границе B
double s;//частичная сумма
} mstk[N];
</source>
В процедурах работы со стеком доступны следующие операции: 
1)Проверка наличия элементов в стеке:
<source lang="cpp">
#define STACK_IS_NOT_FREE (sp > 0)
</source>
2)Операция "положить в стек":
<source lang="cpp">
#define PUT_INTO_STACK(A, B, fA, fB, s) {
mstk[sp].A = A;
mstk[sp].B = B;
mstk[sp].fA = fA;
mstk[sp].fB = fB;
mstk[sp].s = s;
++sp;
}
</source>
3)Операция "взять из стека верхний элемент":

<source lang="cpp">
#define GET_FROM_STACK(A, B, fA, fB, s) {
--sp;
A = mstk[sp].A;
B = mstk[sp].B;
fA = mstk[sp].fA;
fB = mstk[sp].fB;
s = mstk[sp].s;
}

</source>

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

// Заданная функция f(x)
double f(double x);

Рассмотрим функцию JLS, вычисляющую определенный интеграл от f(x) на [A,B] с заданной точностью eps методом локального стека, которая является вычислительным ядром алгоритма:
<source lang="cpp">
//на вход функции подаются границы отрезка и точность
int JLS(double A, double B, double eps) {
double J = 0;//значение интеграла
double fA = f(A);//значение функции f(x)на границе A
double fB = f(B);//значение функции f(x)на границе B
double C;//середина отрезка [A,B]
double fC;//значение функции f(x)в середине отрезка [A,B]
double sAB = (fA + fB)*(B - A)/2;//вычисление площади трапеции с основанием AB
double sAC;//площадь трапеции с основанием AС
double sCB;//площадь трапеции с основанием СВ
double sACB;//сумма sAC и sCB
//бесконечный цикл с предусловием, прерывающийся при выполнении условия на порядок точности
while(1) {
C = (A + B)/2;//середина отрезка
fC = f(C);
sAC = (fA + fC)*(C - A)/2;
sCB = (fC + fB )*(B - C)/2;
sACB = sAC + sCB;
//проверка выполнения условия на порядок точности:
if(abs(sAB - sACB) >= eps*abs(sACB)) {
PUT_INTO_STACK(A, C, fA, fC, sAC);
A = C;
fA = fC;
sAB = sCB;
}
else {
J += sACB;
if(STACK_IS_NOT_FREE) {
break;
}
GET_FROM_STACK(A, B, fA, fB, sAB);
}
}
return J;
}
</source>
В рамках этой функции поэтапно выполняются следующие операции:
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала (возвращение к пункту 2),
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

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

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

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

*Пусть есть доступный всем параллельным процессам список отрезков интегрирования,организованный в виде стека. Назовем его глобальным стеком.
*Пусть у каждого процесса есть свой, доступный только этому процессу локальный стек
*Перед запуском параллельных процессов в глобальный стек помещается единственная запись (в дальнейшем "отрезок"):
координаты концов отрезка интегрирования,
значения функции на концах,
приближенное значение интеграла на этом отрезке.
*Тогда, предлагается следующая схема алгоритма, выполняемого каждым из параллельных процессов:

Пока в глобальном стеке есть отрезки:
*взять один отрезок из глобального стека
*выполнить алгоритм локального стека, но,если при записи в локальный стек в нем есть несколько отрезков, а в глобальном стеке отрезки отсутствуют, то переместить часть отрезков из локального стека в глобальный стек
* по исчерпании локального стека добавить полученную частичную сумму к общему значению интеграла.

[[Файл:luksh.jpg]]
На рисунке изображен информационный граф, где k - это глубина алгоритма, а + обозначено суммирование площадей трапеций.

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

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

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 

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

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

=== Масштабируемость алгоритма и его реализации ===

=== Существующие реализации алгоритма ===
В настоящее время проблемой вычисления определенного графа на адаптивной сетке по нашим сведениям занимались только М.В. Якобовский и Е.Ю. Кулькова, рассматривавшие в своей работе "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ" методы локального и глобального стеков.

==Литература==
#Якобовский М.В.
Введение в параллельные методы решения задач
#М.В. Якобовский и Е.Ю. Кулькова "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ"

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

2016-11-02T10:34:21Z

Sannikovats: /* Макроструктура алгоритма */

{{algorithm
| name = Вычисление определённого интеграла с использованием адаптивно сгущающейся сетки
| input_data = 1 функция,зависящая от 1 переменной, 3 числа ( точность ε и границы отрезка интегрирования[A,B])
| output_data = 1 число
}}

Основные авторы описания:[[Участница:Sannikovats| Санникова Татьяна Сергеевна]](п.1.1-1.6),[[Участник:Plukshin| Лукшин Петр Андреевич]](п.1.7-2.2).

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

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

Допустим, нам дана функция <math>f(x)</math> , определенная на отрезке, и возможность получать ее численное значение в любой из точек области определения за фиксированное время. Задача — вычислить определенный интеграл данной функции по заданной области и дать оценку погрешности вычисления. В случае, когда можно вычислить интеграл по формуле Ньютона-Лейбница, зная первообразную искомой функции, проблем не возникает. Однако, если первообразной нет, решение можно получить благодаря численным методам. Так определенному интегралу можно дать простую геометрическую интерпретацию - он равен площади криволинейной трапеции, ограниченной слева и справа вертикальными прямыми x=a, x=b, снизу - прямой y=0, а сверху – кривой y=f(x).

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

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

Простейший из них - это метод рекурсивного деления, выигрыш от применения которого достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Интервал интегрирования разбивается на две части и независимо интегрируется функция <math>f(x)</math> на каждой из них при соответствующих шагах интегрирования. Процедуру разбиения отрезков можно рекурсивно повторить до получения отрезков, на которых подынтегральная функция имеет простой вид и может быть аппроксимирована отрезком прямой с заданной точностью. Но при распараллеливании этого алгоритма (т.е. при запуске попарно подпрограмм, обрабатывающих половинки разбиваемого интервала) можно столкнуться со следующей проблемой: в реальной системе число процессоров ограничено и время, необходимое для порождения параллельных процессов существенно не равно нулю. А значит, запуск процессов, число которых значительно превышает число физических процессов системы при решении рассматриваемой задачи, приводит к увеличению времени ее решения по сравнению с последовательной программой. Основная сложность построения параллельного алгоритма на основе рассмотренного последовательного алгоритма, кроется в том, что, хотя несколько ветвей программы могли бы одновременно обрабатывать разные части интервала интегрирования, координаты концов этих отрезков хранятся в программном стеке процесса и фактически недоступны программисту. Если бы они были расположены в некотором явно описанном массиве, можно было бы передать их по частям для обработки разным нитям программы. Поэтому, необходимо рассмотреть метод локального стека, позволяющий распределить вычислительную работу между ограниченным числом процессов.

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

В основе этого алгоритма лежит описанный выше метод рекурсивного деления. Только данный метод использует массив данных, доступ к которым осуществляется по принципу стека - первым удаляется последний из добавленных элементов. В рассматриваемом алгоритме вместо стека можно было использовать и другие способы хранения заданий, например очередь. Стек выбран исключительно из соображений простоты реализации. Времена выполнения рассмотренных алгоритмов отличаются примерно на 5% в пользу локального стека, таким образом, алгоритм "локального стека" будем считать наилучшим из имеющихся в нашем распоряжении последовательных методов и на его примере построим дальнейшее описание.

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 
В качестве модельной задачи рассматривается проблема вычисления с точностью ε значения определенного интеграла 
[[Файл:1sann.jpg]]

Пусть на отрезке <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> J_n(A,B)=\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>

[[Файл: 2sann.jpg]] [[Файл:3sann.jpg]]

Будем полагать значение <math> J </math> найденным с точностью <math> \epsilon </math>, если выполнено условие:

<math> |J_{n_1} - J_{n_2}| \leq \epsilon |J_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Используемые в алгоритме формулы: 
*Из метода трапеций <math>sAB=\frac{f(A)+f(B)}{2}*(B-A)</math>

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

Основное время работы алгоритма приходится на: 
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала,
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

=== Макроструктура алгоритма ===
Как уже упоминалось в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть рассматриваемого метода составляют рекурсивные операции нахождения середины отрезка <math> C=(A+B)/2 </math>, вычисление значения функции в этой точке <math> fC=function(C)</math>, нахождение площадей трапеций, образованных после разбиение отрезка и их суммирование <math> sAC=(fA+fC)*(C-A)/2, sCB=(fC+fB)*(B-C)/2, sACB=sAC+sCB </math>, а также нахождение отношения модуля разности площади трапеции до разбиения отрезка и результату, полученному после разбиения, к сумме площадей после разбиения <math> abs(sAB-sACB)≥ε*abs(sACB) </math>, что обеспечивает проверку условия устойчивости. 

Также в реализации алгоритма используется такая структура данных, как стек, в котором хранятся координаты концов отрезков:
<source lang="cpp">
//Данные, описывающие стек
int sp = 0; // Указатель вершины стека

// Массив структур, в которых хранятся отложенные задания
struct mstk {
double A;//координата левой границы отрезка интегрирования
double B;//координата правой границы отрезка интегрирования
double fA;//значение функции на границе A
double fB;//значение функции на границе B
double s;//частичная сумма
} mstk[N];
</source>
В процедурах работы со стеком доступны следующие операции: 
1)Проверка наличия элементов в стеке:
<source lang="cpp">
#define STACK_IS_NOT_FREE (sp > 0)
</source>
2)Операция "положить в стек":
<source lang="cpp">
#define PUT_INTO_STACK(A, B, fA, fB, s) {
mstk[sp].A = A;
mstk[sp].B = B;
mstk[sp].fA = fA;
mstk[sp].fB = fB;
mstk[sp].s = s;
++sp;
}
</source>
3)Операция "взять из стека верхний элемент":

<source lang="cpp">
#define GET_FROM_STACK(A, B, fA, fB, s) {
--sp;
A = mstk[sp].A;
B = mstk[sp].B;
fA = mstk[sp].fA;
fB = mstk[sp].fB;
s = mstk[sp].s;
}

</source>

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

// Заданная функция f(x)
double f(double x);

Рассмотрим функцию JLS, вычисляющую определенный интеграл от f(x) на [A,B] с заданной точностью eps методом локального стека, которая является вычислительным ядром алгоритма:
<source lang="cpp">
int JLS(double A, double B, double eps) {
double J = 0;//значение интеграла
double fA = f(A);//значение функции f(x)на границе A
double fB = f(B);//значение функции f(x)на границе B
double C;//середина отрезка [A,B]
double fC;//значение функции f(x)в середине отрезка [A,B]
double sAB = (fA + fB)*(B - A)/2;//вычисление площади трапеции с основанием AB
double sAC;//площадь трапеции с основанием AС
double sCB;//площадь трапеции с основанием СВ
double sACB;//сумма sAC и sCB
while(1) {
C = (A + B)/2;//середина отрезка
fC = f(C);
sAC = (fA + fC)*(C - A)/2;
sCB = (fC + fB )*(B - C)/2;
sACB = sAC + sCB;
//проверка выполнения условия на порядок точности:
if(abs(sAB - sACB) >= eps*abs(sACB)) {
PUT_INTO_STACK(A, C, fA, fC, sAC);
A = C;
fA = fC;
sAB = sCB;
}
else {
J += sACB;
if(STACK_IS_NOT_FREE) {
break;
}
GET_FROM_STACK(A, B, fA, fB, sAB);
}
}
return J;
}
</source>
В рамках этой функции поэтапно выполняются следующие операции:
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала (возвращение к пункту 2),
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

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

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

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

*Пусть есть доступный всем параллельным процессам список отрезков интегрирования,организованный в виде стека. Назовем его глобальным стеком.
*Пусть у каждого процесса есть свой, доступный только этому процессу локальный стек
*Перед запуском параллельных процессов в глобальный стек помещается единственная запись (в дальнейшем "отрезок"):
координаты концов отрезка интегрирования,
значения функции на концах,
приближенное значение интеграла на этом отрезке.
*Тогда, предлагается следующая схема алгоритма, выполняемого каждым из параллельных процессов:

Пока в глобальном стеке есть отрезки:
*взять один отрезок из глобального стека
*выполнить алгоритм локального стека, но,если при записи в локальный стек в нем есть несколько отрезков, а в глобальном стеке отрезки отсутствуют, то переместить часть отрезков из локального стека в глобальный стек
* по исчерпании локального стека добавить полученную частичную сумму к общему значению интеграла.

[[Файл:luksh.jpg]]
На рисунке изображен информационный граф, где k - это глубина алгоритма, а + обозначено суммирование площадей трапеций.

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

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

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 

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

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

=== Масштабируемость алгоритма и его реализации ===

=== Существующие реализации алгоритма ===
В настоящее время проблемой вычисления определенного графа на адаптивной сетке по нашим сведениям занимались только М.В. Якобовский и Е.Ю. Кулькова, рассматривавшие в своей работе "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ" методы локального и глобального стеков.

==Литература==
#Якобовский М.В.
Введение в параллельные методы решения задач
#М.В. Якобовский и Е.Ю. Кулькова "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ"

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

2016-11-02T10:32:50Z

Sannikovats:

{{algorithm
| name = Вычисление определённого интеграла с использованием адаптивно сгущающейся сетки
| input_data = 1 функция,зависящая от 1 переменной, 3 числа ( точность ε и границы отрезка интегрирования[A,B])
| output_data = 1 число
}}

Основные авторы описания:[[Участница:Sannikovats| Санникова Татьяна Сергеевна]](п.1.1-1.6),[[Участник:Plukshin| Лукшин Петр Андреевич]](п.1.7-2.2).

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

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

Допустим, нам дана функция <math>f(x)</math> , определенная на отрезке, и возможность получать ее численное значение в любой из точек области определения за фиксированное время. Задача — вычислить определенный интеграл данной функции по заданной области и дать оценку погрешности вычисления. В случае, когда можно вычислить интеграл по формуле Ньютона-Лейбница, зная первообразную искомой функции, проблем не возникает. Однако, если первообразной нет, решение можно получить благодаря численным методам. Так определенному интегралу можно дать простую геометрическую интерпретацию - он равен площади криволинейной трапеции, ограниченной слева и справа вертикальными прямыми x=a, x=b, снизу - прямой y=0, а сверху – кривой y=f(x).

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

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

Простейший из них - это метод рекурсивного деления, выигрыш от применения которого достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Интервал интегрирования разбивается на две части и независимо интегрируется функция <math>f(x)</math> на каждой из них при соответствующих шагах интегрирования. Процедуру разбиения отрезков можно рекурсивно повторить до получения отрезков, на которых подынтегральная функция имеет простой вид и может быть аппроксимирована отрезком прямой с заданной точностью. Но при распараллеливании этого алгоритма (т.е. при запуске попарно подпрограмм, обрабатывающих половинки разбиваемого интервала) можно столкнуться со следующей проблемой: в реальной системе число процессоров ограничено и время, необходимое для порождения параллельных процессов существенно не равно нулю. А значит, запуск процессов, число которых значительно превышает число физических процессов системы при решении рассматриваемой задачи, приводит к увеличению времени ее решения по сравнению с последовательной программой. Основная сложность построения параллельного алгоритма на основе рассмотренного последовательного алгоритма, кроется в том, что, хотя несколько ветвей программы могли бы одновременно обрабатывать разные части интервала интегрирования, координаты концов этих отрезков хранятся в программном стеке процесса и фактически недоступны программисту. Если бы они были расположены в некотором явно описанном массиве, можно было бы передать их по частям для обработки разным нитям программы. Поэтому, необходимо рассмотреть метод локального стека, позволяющий распределить вычислительную работу между ограниченным числом процессов.

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

В основе этого алгоритма лежит описанный выше метод рекурсивного деления. Только данный метод использует массив данных, доступ к которым осуществляется по принципу стека - первым удаляется последний из добавленных элементов. В рассматриваемом алгоритме вместо стека можно было использовать и другие способы хранения заданий, например очередь. Стек выбран исключительно из соображений простоты реализации. Времена выполнения рассмотренных алгоритмов отличаются примерно на 5% в пользу локального стека, таким образом, алгоритм "локального стека" будем считать наилучшим из имеющихся в нашем распоряжении последовательных методов и на его примере построим дальнейшее описание.

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 
В качестве модельной задачи рассматривается проблема вычисления с точностью ε значения определенного интеграла 
[[Файл:1sann.jpg]]

Пусть на отрезке <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> J_n(A,B)=\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>

[[Файл: 2sann.jpg]] [[Файл:3sann.jpg]]

Будем полагать значение <math> J </math> найденным с точностью <math> \epsilon </math>, если выполнено условие:

<math> |J_{n_1} - J_{n_2}| \leq \epsilon |J_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Используемые в алгоритме формулы: 
*Из метода трапеций <math>sAB=\frac{f(A)+f(B)}{2}*(B-A)</math>

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

Основное время работы алгоритма приходится на: 
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала,
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

=== Макроструктура алгоритма ===
Как уже упоминалось в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть рассматриваемого метода составляют операции нахождения середины отрезка <math> C=(A+B)/2 </math>, вычисление значения функции в этой точке <math> fC=function(C)</math>, нахождение площадей трапеций, образованных после разбиение отрезка и их суммирование <math> sAC=(fA+fC)*(C-A)/2, sCB=(fC+fB)*(B-C)/2, sACB=sAC+sCB </math>, а также нахождение отношения модуля разности площади трапеции до разбиения отрезка и результату, полученному после разбиения, к сумме площадей после разбиения <math> abs(sAB-sACB)≥ε*abs(sACB) </math>, что обеспечивает проверку условия устойчивости. 

Также в реализации алгоритма используется такая структура данных, как стек, в котором хранятся координаты концов отрезков:
<source lang="cpp">
//Данные, описывающие стек
int sp = 0; // Указатель вершины стека

// Массив структур, в которых хранятся отложенные задания
struct mstk {
double A;//координата левой границы отрезка интегрирования
double B;//координата правой границы отрезка интегрирования
double fA;//значение функции на границе A
double fB;//значение функции на границе B
double s;//частичная сумма
} mstk[N];
</source>
В процедурах работы со стеком доступны следующие операции: 
1)Проверка наличия элементов в стеке:
<source lang="cpp">
#define STACK_IS_NOT_FREE (sp > 0)
</source>
2)Операция "положить в стек":
<source lang="cpp">
#define PUT_INTO_STACK(A, B, fA, fB, s) {
mstk[sp].A = A;
mstk[sp].B = B;
mstk[sp].fA = fA;
mstk[sp].fB = fB;
mstk[sp].s = s;
++sp;
}
</source>
3)Операция "взять из стека верхний элемент":

<source lang="cpp">
#define GET_FROM_STACK(A, B, fA, fB, s) {
--sp;
A = mstk[sp].A;
B = mstk[sp].B;
fA = mstk[sp].fA;
fB = mstk[sp].fB;
s = mstk[sp].s;
}

</source>

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

// Заданная функция f(x)
double f(double x);

Рассмотрим функцию JLS, вычисляющую определенный интеграл от f(x) на [A,B] с заданной точностью eps методом локального стека, которая является вычислительным ядром алгоритма:
<source lang="cpp">
int JLS(double A, double B, double eps) {
double J = 0;//значение интеграла
double fA = f(A);//значение функции f(x)на границе A
double fB = f(B);//значение функции f(x)на границе B
double C;//середина отрезка [A,B]
double fC;//значение функции f(x)в середине отрезка [A,B]
double sAB = (fA + fB)*(B - A)/2;//вычисление площади трапеции с основанием AB
double sAC;//площадь трапеции с основанием AС
double sCB;//площадь трапеции с основанием СВ
double sACB;//сумма sAC и sCB
while(1) {
C = (A + B)/2;//середина отрезка
fC = f(C);
sAC = (fA + fC)*(C - A)/2;
sCB = (fC + fB )*(B - C)/2;
sACB = sAC + sCB;
//проверка выполнения условия на порядок точности:
if(abs(sAB - sACB) >= eps*abs(sACB)) {
PUT_INTO_STACK(A, C, fA, fC, sAC);
A = C;
fA = fC;
sAB = sCB;
}
else {
J += sACB;
if(STACK_IS_NOT_FREE) {
break;
}
GET_FROM_STACK(A, B, fA, fB, sAB);
}
}
return J;
}
</source>
В рамках этой функции поэтапно выполняются следующие операции:
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала (возвращение к пункту 2),
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

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

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

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

*Пусть есть доступный всем параллельным процессам список отрезков интегрирования,организованный в виде стека. Назовем его глобальным стеком.
*Пусть у каждого процесса есть свой, доступный только этому процессу локальный стек
*Перед запуском параллельных процессов в глобальный стек помещается единственная запись (в дальнейшем "отрезок"):
координаты концов отрезка интегрирования,
значения функции на концах,
приближенное значение интеграла на этом отрезке.
*Тогда, предлагается следующая схема алгоритма, выполняемого каждым из параллельных процессов:

Пока в глобальном стеке есть отрезки:
*взять один отрезок из глобального стека
*выполнить алгоритм локального стека, но,если при записи в локальный стек в нем есть несколько отрезков, а в глобальном стеке отрезки отсутствуют, то переместить часть отрезков из локального стека в глобальный стек
* по исчерпании локального стека добавить полученную частичную сумму к общему значению интеграла.

[[Файл:luksh.jpg]]
На рисунке изображен информационный граф, где k - это глубина алгоритма, а + обозначено суммирование площадей трапеций.

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

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

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 

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

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

=== Масштабируемость алгоритма и его реализации ===

=== Существующие реализации алгоритма ===
В настоящее время проблемой вычисления определенного графа на адаптивной сетке по нашим сведениям занимались только М.В. Якобовский и Е.Ю. Кулькова, рассматривавшие в своей работе "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ" методы локального и глобального стеков.

==Литература==
#Якобовский М.В.
Введение в параллельные методы решения задач
#М.В. Якобовский и Е.Ю. Кулькова "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ"

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

2016-11-01T16:15:29Z

Sannikovats:

{{algorithm
| name = Вычисление определённого интеграла с использованием адаптивно сгущающейся сетки
| input_data = 1 функция,зависящая от 1 переменной, 3 числа ( точность ε и границы отрезка интегрирования[A,B])
| output_data = 1 число
}}

Основные авторы описания:[[Участница:Sannikovats| Санникова Татьяна Сергеевна]](п.1.1-1.6),[[Участник:Plukshin| Лукшин Петр Андреевич]](п.1.7-2.2).

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

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

Допустим, нам дана функция <math>f(x)</math> , определенная на отрезке, и возможность получать ее численное значение в любой из точек области определения за фиксированное время. Задача — вычислить определенный интеграл данной функции по заданной области и дать оценку погрешности вычисления. В случае, когда можно вычислить интеграл по формуле Ньютона-Лейбница, зная первообразную искомой функции, проблем не возникает. Однако, если первообразной нет, решение можно получить благодаря численным методам. Так определенному интегралу можно дать простую геометрическую интерпретацию - он равен площади криволинейной трапеции, ограниченной слева и справа вертикальными прямыми x=a, x=b, снизу - прямой y=0, а сверху – кривой y=f(x).

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

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

Простейший из них - это метод рекурсивного деления, выигрыш от применения которого достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Интервал интегрирования разбивается на две части и независимо интегрируется функция <math>f(x)</math> на каждой из них при соответствующих шагах интегрирования. Процедуру разбиения отрезков можно рекурсивно повторить до получения отрезков, на которых подынтегральная функция имеет простой вид и может быть аппроксимирована отрезком прямой с заданной точностью. Но при распараллеливании этого алгоритма (т.е. при запуске попарно подпрограмм, обрабатывающих половинки разбиваемого интервала) можно столкнуться со следующей проблемой: в реальной системе число процессоров ограничено и время, необходимое для порождения параллельных процессов существенно не равно нулю. А значит, запуск процессов, число которых значительно превышает число физических процессов системы при решении рассматриваемой задачи, приводит к увеличению времени ее решения по сравнению с последовательной программой. Основная сложность построения параллельного алгоритма на основе рассмотренного последовательного алгоритма, кроется в том, что, хотя несколько ветвей программы могли бы одновременно обрабатывать разные части интервала интегрирования, координаты концов этих отрезков хранятся в программном стеке процесса и фактически недоступны программисту. Если бы они были расположены в некотором явно описанном массиве, можно было бы передать их по частям для обработки разным нитям программы. Поэтому, необходимо рассмотреть метод локального стека, позволяющий распределить вычислительную работу между ограниченным числом процессов.

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

В основе этого алгоритма лежит описанный выше метод рекурсивного деления. Только данный метод использует массив данных, доступ к которым осуществляется по принципу стека - первым удаляется последний из добавленных элементов. В рассматриваемом алгоритме вместо стека можно было использовать и другие способы хранения заданий, например очередь. Стек выбран исключительно из соображений простоты реализации. Времена выполнения рассмотренных алгоритмов отличаются примерно на 5% в пользу локального стека, таким образом, алгоритм "локального стека" будем считать наилучшим из имеющихся в нашем распоряжении последовательных методов и на его примере построим дальнейшее описание.

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 
В качестве модельной задачи рассматривается проблема вычисления с точностью ε значения определенного интеграла 
[[Файл:1sann.jpg]]

Пусть на отрезке <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> J_n(A,B)=\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>

[[Файл: 2sann.jpg]] [[Файл:3sann.jpg]]

Будем полагать значение <math> J </math> найденным с точностью <math> \epsilon </math>, если выполнено условие:

<math> |J_{n_1} - J_{n_2}| \leq \epsilon |J_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Используемые в алгоритме формулы: 
*Из метода трапеций <math>sAB=\frac{f(A)+f(B)}{2}*(B-A)</math>

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

Основное время работы алгоритма приходится на: 
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала,
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

=== Макроструктура алгоритма ===
В реализации алгоритма используется такая структура данных, как стек, в котором хранятся координаты концов отрезков.
<source lang="cpp">
//Данные, описывающие стек
int sp = 0; // Указатель вершины стека

// Массив структур, в которых хранятся отложенные задания
struct mstk {
double A;//координата левой границы отрезка интегрирования
double B;//координата правой границы отрезка интегрирования
double fA;//значение функции на границе A
double fB;//значение функции на границе B
double s;//частичная сумма
} mstk[N];
</source>
В процедурах работы со стеком доступны следующие операции: 
1)Проверка наличия элементов в стеке:
<source lang="cpp">
#define STACK_IS_NOT_FREE (sp > 0)
</source>
2)Операция "положить в стек":
<source lang="cpp">
#define PUT_INTO_STACK(A, B, fA, fB, s) {
mstk[sp].A = A;
mstk[sp].B = B;
mstk[sp].fA = fA;
mstk[sp].fB = fB;
mstk[sp].s = s;
++sp;
}
</source>
3)Операция "взять из стека верхний элемент":

<source lang="cpp">
#define GET_FROM_STACK(A, B, fA, fB, s) {
--sp;
A = mstk[sp].A;
B = mstk[sp].B;
fA = mstk[sp].fA;
fB = mstk[sp].fB;
s = mstk[sp].s;
}

</source>

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

// Заданная функция f(x)
double f(double x);

Рассмотрим функцию JLS, вычисляющую определенный интеграл от f(x) на [A,B] с заданной точностью eps методом локального стека, которая является вычислительным ядром алгоритма:
<source lang="cpp">
int JLS(double A, double B, double eps) {
double J = 0;//значение интеграла
double fA = f(A);//значение функции f(x)на границе A
double fB = f(B);//значение функции f(x)на границе B
double C;//середина отрезка [A,B]
double fC;//значение функции f(x)в середине отрезка [A,B]
double sAB = (fA + fB)*(B - A)/2;//вычисление площади трапеции с основанием AB
double sAC;//площадь трапеции с основанием AС
double sCB;//площадь трапеции с основанием СВ
double sACB;//сумма sAC и sCB
while(1) {
C = (A + B)/2;//середина отрезка
fC = f(C);
sAC = (fA + fC)*(C - A)/2;
sCB = (fC + fB )*(B - C)/2;
sACB = sAC + sCB;
//проверка выполнения условия на порядок точности:
if(abs(sAB - sACB) >= eps*abs(sACB)) {
PUT_INTO_STACK(A, C, fA, fC, sAC);
A = C;
fA = fC;
sAB = sCB;
}
else {
J += sACB;
if(STACK_IS_NOT_FREE) {
break;
}
GET_FROM_STACK(A, B, fA, fB, sAB);
}
}
return J;
}
</source>
В рамках этой функции поэтапно выполняются следующие операции:
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала (возвращение к пункту 2),
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

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

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

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

*Пусть есть доступный всем параллельным процессам список отрезков интегрирования,организованный в виде стека. Назовем его глобальным стеком.
*Пусть у каждого процесса есть свой, доступный только этому процессу локальный стек
*Перед запуском параллельных процессов в глобальный стек помещается единственная запись (в дальнейшем "отрезок"):
координаты концов отрезка интегрирования,
значения функции на концах,
приближенное значение интеграла на этом отрезке.
*Тогда, предлагается следующая схема алгоритма, выполняемого каждым из параллельных процессов:

Пока в глобальном стеке есть отрезки:
*взять один отрезок из глобального стека
*выполнить алгоритм локального стека, но,если при записи в локальный стек в нем есть несколько отрезков, а в глобальном стеке отрезки отсутствуют, то переместить часть отрезков из локального стека в глобальный стек
* по исчерпании локального стека добавить полученную частичную сумму к общему значению интеграла.

[[Файл:luksh.jpg]]
На рисунке изображен информационный граф, где k - это глубина алгоритма, а + обозначено суммирование площадей трапеций.

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

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

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 

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

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

=== Масштабируемость алгоритма и его реализации ===

=== Существующие реализации алгоритма ===
В настоящее время проблемой вычисления определенного графа на адаптивной сетке по нашим сведениям занимались только М.В. Якобовский и Е.Ю. Кулькова, рассматривавшие в своей работе "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ" методы локального и глобального стеков.

==Литература==
#Якобовский М.В.
Введение в параллельные методы решения задач
#М.В. Якобовский и Е.Ю. Кулькова "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ"

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

2016-11-01T14:44:20Z

Sannikovats:

{{algorithm
| name = Вычисление определённого интеграла с использованием адаптивно сгущающейся сетки
| input_data = 1 функция,зависящая от 1 переменной, 3 числа ( точность ε и границы отрезка интегрирования[A,B])
| output_data = 1 число
}}

Основные авторы описания:[[Участница:Sannikovats| Санникова Татьяна Сергеевна]](п.1.1-1.6),[[Участник:Plukshin| Лукшин Петр Андреевич]](п.1.7-2.2).

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

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

Допустим, нам дана функция <math>f(x)</math> , определенная на отрезке, и возможность получать ее численное значение в любой из точек области определения за фиксированное время. Задача — вычислить определенный интеграл данной функции по заданной области и дать оценку погрешности вычисления. В случае, когда можно вычислить интеграл по формуле Ньютона-Лейбница, зная первообразную искомой функции, проблем не возникает. Однако, если первообразной нет, решение можно получить благодаря численным методам. Так определенному интегралу можно дать простую геометрическую интерпретацию - он равен площади криволинейной трапеции, ограниченной слева и справа вертикальными прямыми x=a, x=b, снизу - прямой y=0, а сверху – кривой y=f(x).

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

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

Простейший из них - это метод рекурсивного деления, выигрыш от применения которого достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Интервал интегрирования разбивается на две части и независимо интегрируется функция <math>f(x)</math> на каждой из них при соответствующих шагах интегрирования. Процедуру разбиения отрезков можно рекурсивно повторить до получения отрезков, на которых подынтегральная функция имеет простой вид и может быть аппроксимирована отрезком прямой с заданной точностью. Но при распараллеливании этого алгоритма (т.е. при запуске попарно подпрограмм, обрабатывающих половинки разбиваемого интервала) можно столкнуться со следующей проблемой: в реальной системе число процессоров ограничено и время, необходимое для порождения параллельных процессов существенно не равно нулю. А значит, запуск процессов, число которых значительно превышает число физических процессов системы при решении рассматриваемой задачи, приводит к увеличению времени ее решения по сравнению с последовательной программой. Основная сложность построения параллельного алгоритма на основе рассмотренного последовательного алгоритма, кроется в том, что, хотя несколько ветвей программы могли бы одновременно обрабатывать разные части интервала интегрирования, координаты концов этих отрезков хранятся в программном стеке процесса и фактически недоступны программисту. Если бы они были расположены в некотором явно описанном массиве, можно было бы передать их по частям для обработки разным нитям программы. Поэтому, необходимо рассмотреть метод локального стека, позволяющий распределить вычислительную работу между ограниченным числом процессов.

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

В основе этого алгоритма лежит описанный выше метод рекурсивного деления. Только данный метод использует массив данных, доступ к которым осуществляется по принципу стека - первым удаляется последний из добавленных элементов. В рассматриваемом алгоритме вместо стека можно было использовать и другие способы хранения заданий, например очередь. Стек выбран исключительно из соображений простоты реализации. Времена выполнения рассмотренных алгоритмов отличаются примерно на 5% в пользу локального стека, таким образом, алгоритм "локального стека" будем считать наилучшим из имеющихся в нашем распоряжении последовательных методов и на его примере построим дальнейшее описание.

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 
В качестве модельной задачи рассматривается проблема вычисления с точностью ε значения определенного интеграла 
[[Файл:1sann.jpg]]

Пусть на отрезке <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> J_n(A,B)=\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>

[[Файл: 2sann.jpg]] [[Файл:3sann.jpg]]

Будем полагать значение <math> J </math> найденным с точностью <math> \epsilon </math>, если выполнено условие:

<math> |J_{n_1} - J_{n_2}| \leq \epsilon |J_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Используемые в алгоритме формулы: 
*Из метода трапеций <math>sAB=\frac{f(A)+f(B)}{2}*(B-A)</math>

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

Основное время работы алгоритма приходится на: 
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала,
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

=== Макроструктура алгоритма ===
В реализации алгоритма используется такая структура данных, как стек, в котором хранятся координаты концов отрезков.
<source lang="cpp">
//Данные, описывающие стек
int sp = 0; // Указатель вершины стека

// Массив структур, в которых хранятся отложенные задания
struct mstk {
double A;//координата левой границы отрезка интегрирования
double B;//координата правой границы отрезка интегрирования
double fA;//значение функции на границе A
double fB;//значение функции на границе B
double s;//частичная сумма
} mstk[N];
</source>
В процедурах работы со стеком доступны следующие операции: 
1)Проверка наличия элементов в стеке:
<source lang="cpp">
#define STACK_IS_NOT_FREE (sp > 0)
</source>
2)Операция "положить в стек":
<source lang="cpp">
#define PUT_INTO_STACK(A, B, fA, fB, s) {
mstk[sp].A = A;
mstk[sp].B = B;
mstk[sp].fA = fA;
mstk[sp].fB = fB;
mstk[sp].s = s;
++sp;
}
</source>
3)Операция "взять из стека верхний элемент":

<source lang="cpp">
#define GET_FROM_STACK(A, B, fA, fB, s) {
--sp;
A = mstk[sp].A;
B = mstk[sp].B;
fA = mstk[sp].fA;
fB = mstk[sp].fB;
s = mstk[sp].s;
}

</source>

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

// Заданная функция f(x)
double f(double x);

Рассмотрим функцию JLS, вычисляющую определенный интеграл от f(x) на [A,B] с заданной точностью eps методом локального стека, которая является вычислительным ядром алгоритма:
<source lang="cpp">
int JLS(double A, double B, double eps) {
double J = 0;//значение интеграла
double fA = f(A);//значение функции f(x)на границе A
double fB = f(B);//значение функции f(x)на границе B
double C;//середина отрезка [A,B]
double fC;//значение функции f(x)в середине отрезка [A,B]
double sAB = (fA + fB)*(B - A)/2;//вычисление площади трапеции с основанием AB
double sAC;//площадь трапеции с основанием AС
double sCB;//площадь трапеции с основанием СВ
double sACB;//сумма sAC и sCB
while(1) {
C = (A + B)/2;//середина отрезка
fC = f(C);
sAC = (fA + fC)*(C - A)/2;
sCB = (fC + fB )*(B - C)/2;
sACB = sAC + sCB;
//проверка выполнения условия на порядок точности:
if(abs(sAB - sACB) >= eps*abs(sACB)) {
PUT_INTO_STACK(A, C, fA, fC, sAC);
A = C;
fA = fC;
sAB = sCB;
}
else {
J += sACB;
if(STACK_IS_NOT_FREE) {
break;
}
GET_FROM_STACK(A, B, fA, fB, sAB);
}
}
return J;
}
</source>

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

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

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

*Пусть есть доступный всем параллельным процессам список отрезков интегрирования,организованный в виде стека. Назовем его глобальным стеком.
*Пусть у каждого процесса есть свой, доступный только этому процессу локальный стек
*Перед запуском параллельных процессов в глобальный стек помещается единственная запись (в дальнейшем "отрезок"):
координаты концов отрезка интегрирования,
значения функции на концах,
приближенное значение интеграла на этом отрезке.
*Тогда, предлагается следующая схема алгоритма, выполняемого каждым из параллельных процессов:

Пока в глобальном стеке есть отрезки:
*взять один отрезок из глобального стека
*выполнить алгоритм локального стека, но,если при записи в локальный стек в нем есть несколько отрезков, а в глобальном стеке отрезки отсутствуют, то переместить часть отрезков из локального стека в глобальный стек
* по исчерпании локального стека добавить полученную частичную сумму к общему значению интеграла.

[[Файл:luksh.jpg]]
На рисунке изображен информационный граф, где k - это глубина алгоритма, а + обозначено суммирование площадей трапеций.

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

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

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 

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

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

=== Масштабируемость алгоритма и его реализации ===

=== Существующие реализации алгоритма ===
В настоящее время проблемой вычисления определенного графа на адаптивной сетке по нашим сведениям занимались только М.В. Якобовский и Е.Ю. Кулькова, рассматривавшие в своей работе "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ" методы локального и глобального стеков.

==Литература==
#Якобовский М.В.
Введение в параллельные методы решения задач
#М.В. Якобовский и Е.Ю. Кулькова "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ"

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

2016-10-29T17:58:47Z

Sannikovats:

{{algorithm
| name = Вычисление определённого интеграла с использованием адаптивно сгущающейся сетки
| input_data = 1 функция,зависящая от 1 переменной, 3 числа ( точность ε и границы отрезка интегрирования[A,B])
| output_data = 1 число
}}

Основные авторы описания:[[Участница:Sannikovats| Санникова Татьяна Сергеевна]](п.1.1-1.6),[[Участник:Plukshin| Лукшин Петр Андреевич]](п.1.7-2.2).

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

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

Допустим, нам дана функция <math>f(x)</math> , определенная на отрезке, и возможность получать ее численное значение в любой из точек области определения за фиксированное время. Задача — вычислить определенный интеграл данной функции по заданной области и дать оценку погрешности вычисления. В случае, когда можно вычислить интеграл по формуле Ньютона-Лейбница, зная первообразную искомой функции, проблем не возникает. Однако, если первообразной нет, решение можно получить благодаря численным методам. Так определенному интегралу можно дать простую геометрическую интерпретацию - он равен площади криволинейной трапеции, ограниченной слева и справа вертикальными прямыми x=a, x=b, снизу - прямой y=0, а сверху – кривой y=f(x).

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

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

Простейший из них - это метод рекурсивного деления, выигрыш от применения которого достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Интервал интегрирования разбивается на две части и независимо интегрируется функция <math>f(x)</math> на каждой из них при соответствующих шагах интегрирования. Процедуру разбиения отрезков можно рекурсивно повторить до получения отрезков, на которых подынтегральная функция имеет простой вид и может быть аппроксимирована отрезком прямой с заданной точностью. Но при распараллеливании этого алгоритма (т.е. при запуске попарно подпрограмм, обрабатывающих половинки разбиваемого интервала) можно столкнуться со следующей проблемой: в реальной системе число процессоров ограничено и время, необходимое для порождения параллельных процессов существенно не равно нулю. А значит, запуск процессов, число которых значительно превышает число физических процессов системы при решении рассматриваемой задачи, приводит к увеличению времени ее решения по сравнению с последовательной программой. Основная сложность построения параллельного алгоритма на основе рассмотренного последовательного алгоритма, кроется в том, что, хотя несколько ветвей программы могли бы одновременно обрабатывать разные части интервала интегрирования, координаты концов этих отрезков хранятся в программном стеке процесса и фактически недоступны программисту. Если бы они были расположены в некотором явно описанном массиве, можно было бы передать их по частям для обработки разным нитям программы. Поэтому, необходимо рассмотреть метод локального стека, позволяющий распределить вычислительную работу между ограниченным числом процессов.

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

В основе этого алгоритма лежит описанный выше метод рекурсивного деления. Только данный метод использует массив данных, доступ к которым осуществляется по принципу стека - первым удаляется последний из добавленных элементов. В рассматриваемом алгоритме вместо стека можно было использовать и другие способы хранения заданий, например очередь. Стек выбран исключительно из соображений простоты реализации. Времена выполнения рассмотренных алгоритмов отличаются примерно на 5% в пользу локального стека, таким образом, алгоритм "локального стека" будем считать наилучшим из имеющихся в нашем распоряжении последовательных методов и на его примере построим дальнейшее описание.

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 
В качестве модельной задачи рассматривается проблема вычисления с точностью ε значения определенного интеграла 
[[Файл:1.jpg]]

Пусть на отрезке <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> J_n(A,B)=\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>

[[Файл: 2sann.jpg]] [[Файл:3sann.jpg]]

Будем полагать значение <math> J </math> найденным с точностью <math> \epsilon </math>, если выполнено условие:

<math> |J_{n_1} - J_{n_2}| \leq \epsilon |J_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Используемые в алгоритме формулы: 
*Из метода трапеций <math>sAB=\frac{f(A)+f(B)}{2}*(B-A)</math>

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

Основное время работы алгоритма приходится на: 
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала,
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

=== Макроструктура алгоритма ===
В реализации алгоритма используется такая структура данных, как стек, в котором хранятся координаты концов отрезков.
<source lang="cpp">
//Данные, описывающие стек
int sp = 0; // Указатель вершины стека

// Массив структур, в которых хранятся отложенные задания
struct mstk {
double A;//координата левой границы отрезка интегрирования
double B;//координата правой границы отрезка интегрирования
double fA;//значение функции на границе A
double fB;//значение функции на границе B
double s;//частичная сумма
} mstk[N];
</source>
В процедурах работы со стеком доступны следующие операции: 
1)Проверка наличия элементов в стеке:
<source lang="cpp">
#define STACK_IS_NOT_FREE (sp > 0)
</source>
2)Операция "положить в стек":
<source lang="cpp">
#define PUT_INTO_STACK(A, B, fA, fB, s) {
mstk[sp].A = A;
mstk[sp].B = B;
mstk[sp].fA = fA;
mstk[sp].fB = fB;
mstk[sp].s = s;
++sp;
}
</source>
3)Операция "взять из стека верхний элемент":

<source lang="cpp">
#define GET_FROM_STACK(A, B, fA, fB, s) {
--sp;
A = mstk[sp].A;
B = mstk[sp].B;
fA = mstk[sp].fA;
fB = mstk[sp].fB;
s = mstk[sp].s;
}

</source>

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

// Заданная функция f(x)
double f(double x);

Рассмотрим функцию JLS, вычисляющую определенный интеграл от f(x) на [A,B] с заданной точностью eps методом локального стека, которая является вычислительным ядром алгоритма:
<source lang="cpp">
int JLS(double A, double B, double eps) {
double J = 0;//значение интеграла
double fA = f(A);//значение функции f(x)на границе A
double fB = f(B);//значение функции f(x)на границе B
double C;//середина отрезка [A,B]
double fC;//значение функции f(x)в середине отрезка [A,B]
double sAB = (fA + fB)*(B - A)/2;//вычисление площади трапеции с основанием AB
double sAC;//площадь трапеции с основанием AС
double sCB;//площадь трапеции с основанием СВ
double sACB;//сумма sAC и sCB
while(1) {
C = (A + B)/2;//середина отрезка
fC = f(C);
sAC = (fA + fC)*(C - A)/2;
sCB = (fC + fB )*(B - C)/2;
sACB = sAC + sCB;
//проверка выполнения условия на порядок точности:
if(abs(sAB - sACB) >= eps*abs(sACB)) {
PUT_INTO_STACK(A, C, fA, fC, sAC);
A = C;
fA = fC;
sAB = sCB;
}
else {
J += sACB;
if(STACK_IS_NOT_FREE) {
break;
}
GET_FROM_STACK(A, B, fA, fB, sAB);
}
}
return J;
}
</source>

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

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

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

*Пусть есть доступный всем параллельным процессам список отрезков интегрирования,организованный в виде стека. Назовем его глобальным стеком.
*Пусть у каждого процесса есть свой, доступный только этому процессу локальный стек
*Перед запуском параллельных процессов в глобальный стек помещается единственная запись (в дальнейшем "отрезок"):
координаты концов отрезка интегрирования,
значения функции на концах,
приближенное значение интеграла на этом отрезке.
*Тогда, предлагается следующая схема алгоритма, выполняемого каждым из параллельных процессов:

Пока в глобальном стеке есть отрезки:
*взять один отрезок из глобального стека
*выполнить алгоритм локального стека, но,если при записи в локальный стек в нем есть несколько отрезков, а в глобальном стеке отрезки отсутствуют, то переместить часть отрезков из локального стека в глобальный стек
* по исчерпании локального стека добавить полученную частичную сумму к общему значению интеграла.

[[Файл:luksh.jpg]]
На рисунке изображен информационный граф, где k - это глубина алгоритма, а + обозначено суммирование площадей трапеций.

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

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

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 

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

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

=== Масштабируемость алгоритма и его реализации ===

=== Существующие реализации алгоритма ===
В настоящее время проблемой вычисления определенного графа на адаптивной сетке по нашим сведениям занимались только М.В. Якобовский и Е.Ю. Кулькова, рассматривавшие в своей работе "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ" методы локального и глобального стеков.

==Литература==
#Якобовский М.В.
Введение в параллельные методы решения задач
#М.В. Якобовский и Е.Ю. Кулькова "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ"

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

2016-10-15T20:56:37Z

Sannikovats:

{{Assignment}}
{{algorithm
| name = Вычисление определённого интеграла с использованием адаптивно сгущающейся сетки
| input_data = 1 функция,зависящая от 1 переменной, 3 числа ( точность ε и границы отрезка интегрирования[A,B])
| output_data = 1 число
}}

Основные авторы описания:[[Участница:Sannikovats| Санникова Татьяна Сергеевна]],[[Участник:Plukshin| Лукшин Петр Андреевич]].

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

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

Допустим, нам дана функция <math>f(x)</math> , определенная на отрезке, и возможность получать ее численное значение в любой из точек области определения за фиксированное время. Задача — вычислить определенный интеграл данной функции по заданной области и дать оценку погрешности вычисления. В случае, когда можно вычислить интеграл по формуле Ньютона-Лейбница, зная первообразную искомой функции, проблем не возникает. Однако, если первообразной нет, решение можно получить благодаря численным методам. Так определенному интегралу можно дать простую геометрическую интерпретацию - он равен площади криволинейной трапеции, ограниченной слева и справа вертикальными прямыми x=a, x=b, снизу - прямой y=0, а сверху – кривой y=f(x).

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

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

Простейший из них - это метод рекурсивного деления, выигрыш от применения которого достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Интервал интегрирования разбивается на две части и независимо интегрируется функция <math>f(x)</math> на каждой из них при соответствующих шагах интегрирования. Процедуру разбиения отрезков можно рекурсивно повторить до получения отрезков, на которых подынтегральная функция имеет простой вид и может быть аппроксимирована отрезком прямой с заданной точностью. Но при распараллеливании этого алгоритма (т.е. при запуске попарно подпрограмм, обрабатывающих половинки разбиваемого интервала) можно столкнуться со следующей проблемой: в реальной системе число процессоров ограничено и время, необходимое для порождения параллельных процессов существенно не равно нулю. А значит, запуск процессов, число которых значительно превышает число физических процессов системы при решении рассматриваемой задачи, приводит к увеличению времени ее решения по сравнению с последовательной программой. Основная сложность построения параллельного алгоритма на основе рассмотренного последовательного алгоритма, кроется в том, что, хотя несколько ветвей программы могли бы одновременно обрабатывать разные части интервала интегрирования, координаты концов этих отрезков хранятся в программном стеке процесса и фактически недоступны программисту. Если бы они были расположены в некотором явно описанном массиве, можно было бы передать их по частям для обработки разным нитям программы. Поэтому, необходимо рассмотреть метод локального стека, позволяющий распределить вычислительную работу между ограниченным числом процессов.

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

В основе этого алгоритма лежит описанный выше метод рекурсивного деления. Только данный метод использует массив данных, доступ к которым осуществляется по принципу стека - первым удаляется последний из добавленных элементов. В рассматриваемом алгоритме вместо стека можно было использовать и другие способы хранения заданий, например очередь. Стек выбран исключительно из соображений простоты реализации. Времена выполнения рассмотренных алгоритмов отличаются примерно на 5% в пользу локального стека, таким образом, алгоритм "локального стека" будем считать наилучшим из имеющихся в нашем распоряжении последовательных методов и на его примере построим дальнейшее описание.

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 
В качестве модельной задачи рассматривается проблема вычисления с точностью ε значения определенного интеграла 
[[Файл:1.jpg]]

Пусть на отрезке <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> J_n(A,B)=\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>

[[Файл: 2sann.jpg]] [[Файл:3sann.jpg]]

Будем полагать значение <math> J </math> найденным с точностью <math> \epsilon </math>, если выполнено условие:

<math> |J_{n_1} - J_{n_2}| \leq \epsilon |J_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Используемые в алгоритме формулы: 
*Из метода трапеций <math>sAB=\frac{f(A)+f(B)}{2}*(B-A)</math>

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

Основное время работы алгоритма приходится на: 
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала,
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

=== Макроструктура алгоритма ===
В реализации алгоритма используется такая структура данных, как стек, в котором хранятся координаты концов отрезков.
<source lang="cpp">
//Данные, описывающие стек
int sp = 0; // Указатель вершины стека

// Массив структур, в которых хранятся отложенные задания
struct mstk {
double A;//координата левой границы отрезка интегрирования
double B;//координата правой границы отрезка интегрирования
double fA;//значение функции на границе A
double fB;//значение функции на границе B
double s;//частичная сумма
} mstk[N];
</source>
В процедурах работы со стеком доступны следующие операции: 
1)Проверка наличия элементов в стеке:
<source lang="cpp">
#define STACK_IS_NOT_FREE (sp > 0)
</source>
2)Операция "положить в стек":
<source lang="cpp">
#define PUT_INTO_STACK(A, B, fA, fB, s) {
mstk[sp].A = A;
mstk[sp].B = B;
mstk[sp].fA = fA;
mstk[sp].fB = fB;
mstk[sp].s = s;
++sp;
}
</source>
3)Операция "взять из стека верхний элемент":

<source lang="cpp">
#define GET_FROM_STACK(A, B, fA, fB, s) {
--sp;
A = mstk[sp].A;
B = mstk[sp].B;
fA = mstk[sp].fA;
fB = mstk[sp].fB;
s = mstk[sp].s;
}

</source>

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

// Заданная функция f(x)
double f(double x);

Рассмотрим функцию JLS, вычисляющую определенный интеграл от f(x) на [A,B] с заданной точностью eps методом локального стека, которая является вычислительным ядром алгоритма:
<source lang="cpp">
int JLS(double A, double B, double eps) {
double J = 0;//значение интеграла
double fA = f(A);//значение функции f(x)на границе A
double fB = f(B);//значение функции f(x)на границе B
double C;//середина отрезка [A,B]
double fC;//значение функции f(x)в середине отрезка [A,B]
double sAB = (fA + fB)*(B - A)/2;//вычисление площади трапеции с основанием AB
double sAC;//площадь трапеции с основанием AС
double sCB;//площадь трапеции с основанием СВ
double sACB;//сумма sAC и sCB
while(1) {
C = (A + B)/2;//середина отрезка
fC = f(C);
sAC = (fA + fC)*(C - A)/2;
sCB = (fC + fB )*(B - C)/2;
sACB = sAC + sCB;
//проверка выполнения условия на порядок точности:
if(abs(sAB - sACB) >= eps*abs(sACB)) {
PUT_INTO_STACK(A, C, fA, fC, sAC);
A = C;
fA = fC;
sAB = sCB;
}
else {
J += sACB;
if(STACK_IS_NOT_FREE) {
break;
}
GET_FROM_STACK(A, B, fA, fB, sAB);
}
}
return J;
}
</source>

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

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

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

*Пусть есть доступный всем параллельным процессам список отрезков интегрирования,организованный в виде стека. Назовем его глобальным стеком.
*Пусть у каждого процесса есть свой, доступный только этому процессу локальный стек
*Перед запуском параллельных процессов в глобальный стек помещается единственная запись (в дальнейшем "отрезок"):
координаты концов отрезка интегрирования,
значения функции на концах,
приближенное значение интеграла на этом отрезке.
*Тогда, предлагается следующая схема алгоритма, выполняемого каждым из параллельных процессов:

Пока в глобальном стеке есть отрезки:
*взять один отрезок из глобального стека
*выполнить алгоритм локального стека, но,если при записи в локальный стек в нем есть несколько отрезков, а в глобальном стеке отрезки отсутствуют, то переместить часть отрезков из локального стека в глобальный стек
* по исчерпании локального стека добавить полученную частичную сумму к общему значению интеграла.

[[Файл:luksh.jpg]]
На рисунке изображен информационный граф, где k - это глубина алгоритма, а + обозначено суммирование площадей трапеций.

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

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

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 

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

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

=== Масштабируемость алгоритма и его реализации ===

=== Существующие реализации алгоритма ===
В настоящее время проблемой вычисления определенного графа на адаптивной сетке по нашим сведениям занимались только М.В. Якобовский и Е.Ю. Кулькова, рассматривавшие в своей работе "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ" методы локального и глобального стеков.

==Литература==
Якобовский М.В.
Введение в параллельные методы решения задач
М.В. Якобовский и Е.Ю. Кулькова "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ"

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

2016-10-15T20:49:51Z

Sannikovats:

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

2016-10-15T20:36:50Z

Sannikovats:

{{algorithm
| name = Вычисление определённого интеграла с использованием адаптивно сгущающейся сетки
| input_data = 1 функция,зависящая от 1 переменной, 3 числа ( точность ε и границы отрезка интегрирования[A,B])
| output_data = 1 число
}}

Основные авторы описания:[[Участница:Sannikovats| Санникова Татьяна Сергеевна]],[[Участник:Plukshin| Лукшин Петр Андреевич]].

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

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

Допустим, нам дана функция <math>f(x)</math> , определенная на отрезке, и возможность получать ее численное значение в любой из точек области определения за фиксированное время. Задача — вычислить определенный интеграл данной функции по заданной области и дать оценку погрешности вычисления. В случае, когда можно вычислить интеграл по формуле Ньютона-Лейбница, зная первообразную искомой функции, проблем не возникает. Однако, если первообразной нет, решение можно получить благодаря численным методам. Так определенному интегралу можно дать простую геометрическую интерпретацию - он равен площади криволинейной трапеции, ограниченной слева и справа вертикальными прямыми x=a, x=b, снизу - прямой y=0, а сверху – кривой y=f(x).

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

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

Простейший из них - это метод рекурсивного деления, выигрыш от применения которого достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Интервал интегрирования разбивается на две части и независимо интегрируется функция <math>f(x)</math> на каждой из них при соответствующих шагах интегрирования. Процедуру разбиения отрезков можно рекурсивно повторить до получения отрезков, на которых подынтегральная функция имеет простой вид и может быть аппроксимирована отрезком прямой с заданной точностью. Но при распараллеливании этого алгоритма (т.е. при запуске попарно подпрограмм, обрабатывающих половинки разбиваемого интервала) можно столкнуться со следующей проблемой: в реальной системе число процессоров ограничено и время, необходимое для порождения параллельных процессов существенно не равно нулю. А значит, запуск процессов, число которых значительно превышает число физических процессов системы при решении рассматриваемой задачи, приводит к увеличению времени ее решения по сравнению с последовательной программой. Основная сложность построения параллельного алгоритма на основе рассмотренного последовательного алгоритма, кроется в том, что, хотя несколько ветвей программы могли бы одновременно обрабатывать разные части интервала интегрирования, координаты концов этих отрезков хранятся в программном стеке процесса и фактически недоступны программисту. Если бы они были расположены в некотором явно описанном массиве, можно было бы передать их по частям для обработки разным нитям программы. Поэтому, необходимо рассмотреть метод локального стека, позволяющий распределить вычислительную работу между ограниченным числом процессов.

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

В основе этого алгоритма лежит описанный выше метод рекурсивного деления. Только данный метод использует массив данных, доступ к которым осуществляется по принципу стека - первым удаляется последний из добавленных элементов. В рассматриваемом алгоритме вместо стека можно было использовать и другие способы хранения заданий, например очередь. Стек выбран исключительно из соображений простоты реализации. Времена выполнения рассмотренных алгоритмов отличаются примерно на 5% в пользу локального стека, таким образом, алгоритм "локального стека" будем считать наилучшим из имеющихся в нашем распоряжении последовательных методов и на его примере построим дальнейшее описание.

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 
В качестве модельной задачи рассматривается проблема вычисления с точностью ε значения определенного интеграла 
[[Файл:1.jpg]]

Пусть на отрезке <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> J_n(A,B)=\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>

[[Файл: 2sann.jpg]] [[Файл:3sann.jpg]]

Будем полагать значение <math> J </math> найденным с точностью <math> \epsilon </math>, если выполнено условие:

<math> |J_{n_1} - J_{n_2}| \leq \epsilon |J_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Используемые в алгоритме формулы: 
*Из метода трапеций <math>sAB=\frac{f(A)+f(B)}{2}*(B-A)</math>

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

Основное время работы алгоритма приходится на: 
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала,
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

=== Макроструктура алгоритма ===
В реализации алгоритма используется такая структура данных, как стек, в котором хранятся координаты концов отрезков.
<source lang="cpp">
//Данные, описывающие стек
int sp = 0; // Указатель вершины стека

// Массив структур, в которых хранятся отложенные задания
struct mstk {
double A;//координата левой границы отрезка интегрирования
double B;//координата правой границы отрезка интегрирования
double fA;//значение функции на границе A
double fB;//значение функции на границе B
double s;//частичная сумма
} mstk[N];
</source>
В процедурах работы со стеком доступны следующие операции: 
1)Проверка наличия элементов в стеке:
<source lang="cpp">
#define STACK_IS_NOT_FREE (sp > 0)
</source>
2)Операция "положить в стек":
<source lang="cpp">
#define PUT_INTO_STACK(A, B, fA, fB, s) {
mstk[sp].A = A;
mstk[sp].B = B;
mstk[sp].fA = fA;
mstk[sp].fB = fB;
mstk[sp].s = s;
++sp;
}
</source>
3)Операция "взять из стека верхний элемент":

<source lang="cpp">
#define GET_FROM_STACK(A, B, fA, fB, s) {
--sp;
A = mstk[sp].A;
B = mstk[sp].B;
fA = mstk[sp].fA;
fB = mstk[sp].fB;
s = mstk[sp].s;
}

</source>

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

// Заданная функция f(x)
double f(double x);

Рассмотрим функцию JLS, вычисляющую определенный интеграл от f(x) на [A,B] с заданной точностью eps методом локального стека, которая является вычислительным ядром алгоритма:
<source lang="cpp">
int JLS(double A, double B, double eps) {
double J = 0;//значение интеграла
double fA = f(A);//значение функции f(x)на границе A
double fB = f(B);//значение функции f(x)на границе B
double C;//середина отрезка [A,B]
double fC;//значение функции f(x)в середине отрезка [A,B]
double sAB = (fA + fB)*(B - A)/2;//вычисление площади трапеции с основанием AB
double sAC;//площадь трапеции с основанием AС
double sCB;//площадь трапеции с основанием СВ
double sACB;//сумма sAC и sCB
while(1) {
C = (A + B)/2;//середина отрезка
fC = f(C);
sAC = (fA + fC)*(C - A)/2;
sCB = (fC + fB )*(B - C)/2;
sACB = sAC + sCB;
//проверка выполнения условия на порядок точности:
if(abs(sAB - sACB) >= eps*abs(sACB)) {
PUT_INTO_STACK(A, C, fA, fC, sAC);
A = C;
fA = fC;
sAB = sCB;
}
else {
J += sACB;
if(STACK_IS_NOT_FREE) {
break;
}
GET_FROM_STACK(A, B, fA, fB, sAB);
}
}
return J;
}
</source>

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

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

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

*Пусть есть доступный всем параллельным процессам список отрезков интегрирования,организованный в виде стека. Назовем его глобальным стеком.
*Пусть у каждого процесса есть свой, доступный только этому процессу локальный стек
*Перед запуском параллельных процессов в глобальный стек помещается единственная запись (в дальнейшем "отрезок"):
координаты концов отрезка интегрирования,
значения функции на концах,
приближенное значение интеграла на этом отрезке.
*Тогда, предлагается следующая схема алгоритма, выполняемого каждым из параллельных процессов:

Пока в глобальном стеке есть отрезки:
*взять один отрезок из глобального стека
*выполнить алгоритм локального стека, но,если при записи в локальный стек в нем есть несколько отрезков, а в глобальном стеке отрезки отсутствуют, то переместить часть отрезков из локального стека в глобальный стек
* по исчерпании локального стека добавить полученную частичную сумму к общему значению интеграла.

[[Файл:luksh.jpg]]

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

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

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 

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

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

=== Масштабируемость алгоритма и его реализации ===

=== Существующие реализации алгоритма ===
В настоящее время проблемой вычисления определенного графа на адаптивной сетке по нашим сведениям занимались только М.В. Якобовский и Е.Ю. Кулькова, рассматривавшие в своей работе "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ" методы локального и глобального стеков.

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

2016-10-15T20:33:01Z

Sannikovats:

{{algorithm
| name = Вычисление определённого интеграла с использованием адаптивно сгущающейся сетки
| input_data = 1 функция,зависящая от 1 переменной, 3 числа ( точность ε и границы отрезка интегрирования[A,B])
| output_data = 1 число
}}

Основные авторы описания:[[Участница:Sannikovats| Санникова Татьяна Сергеевна]],[[Участник:Plukshin| Лукшин Петр Андреевич]].

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

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

Допустим, нам дана функция <math>f(x)</math> , определенная на отрезке, и возможность получать ее численное значение в любой из точек области определения за фиксированное время. Задача — вычислить определенный интеграл данной функции по заданной области и дать оценку погрешности вычисления. В случае, когда можно вычислить интеграл по формуле Ньютона-Лейбница, зная первообразную искомой функции, проблем не возникает. Однако, если первообразной нет, решение можно получить благодаря численным методам. Так определенному интегралу можно дать простую геометрическую интерпретацию - он равен площади криволинейной трапеции, ограниченной слева и справа вертикальными прямыми x=a, x=b, снизу - прямой y=0, а сверху – кривой y=f(x).

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

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

Простейший из них - это метод рекурсивного деления, выигрыш от применения которого достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Интервал интегрирования разбивается на две части и независимо интегрируется функция <math>f(x)</math> на каждой из них при соответствующих шагах интегрирования. Процедуру разбиения отрезков можно рекурсивно повторить до получения отрезков, на которых подынтегральная функция имеет простой вид и может быть аппроксимирована отрезком прямой с заданной точностью. Но при распараллеливании этого алгоритма (т.е. при запуске попарно подпрограмм, обрабатывающих половинки разбиваемого интервала) можно столкнуться со следующей проблемой: в реальной системе число процессоров ограничено и время, необходимое для порождения параллельных процессов существенно не равно нулю. А значит, запуск процессов, число которых значительно превышает число физических процессов системы при решении рассматриваемой задачи, приводит к увеличению времени ее решения по сравнению с последовательной программой. Основная сложность построения параллельного алгоритма на основе рассмотренного последовательного алгоритма, кроется в том, что, хотя несколько ветвей программы могли бы одновременно обрабатывать разные части интервала интегрирования, координаты концов этих отрезков хранятся в программном стеке процесса и фактически недоступны программисту. Если бы они были расположены в некотором явно описанном массиве, можно было бы передать их по частям для обработки разным нитям программы. Поэтому, необходимо рассмотреть метод локального стека, позволяющий распределить вычислительную работу между ограниченным числом процессов.

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

В основе этого алгоритма лежит описанный выше метод рекурсивного деления. Только данный метод использует массив данных, доступ к которым осуществляется по принципу стека - первым удаляется последний из добавленных элементов. В рассматриваемом алгоритме вместо стека можно было использовать и другие способы хранения заданий, например очередь. Стек выбран исключительно из соображений простоты реализации. Времена выполнения рассмотренных алгоритмов отличаются примерно на 5% в пользу локального стека, таким образом, алгоритм "локального стека" будем считать наилучшим из имеющихся в нашем распоряжении последовательных методов и на его примере построим дальнейшее описание.

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 
В качестве модельной задачи рассматривается проблема вычисления с точностью ε значения определенного интеграла 
[[Файл:1.jpg]]

Пусть на отрезке <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> J_n(A,B)=\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>

[[Файл: 2sann.jpg]] [[Файл:3sann.jpg]]

Будем полагать значение <math> J </math> найденным с точностью <math> \epsilon </math>, если выполнено условие:

<math> |J_{n_1} - J_{n_2}| \leq \epsilon |J_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Используемые в алгоритме формулы: 
*Из метода трапеций <math>sAB=\frac{f(A)+f(B)}{2}*(B-A)</math>

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

Основное время работы алгоритма приходится на: 
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала,
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

=== Макроструктура алгоритма ===
В реализации алгоритма используется такая структура данных, как стек, в котором хранятся координаты концов отрезков.
<source lang="cpp">
//Данные, описывающие стек
int sp = 0; // Указатель вершины стека

// Массив структур, в которых хранятся отложенные задания
struct mstk {
double A;//координата левой границы отрезка интегрирования
double B;//координата правой границы отрезка интегрирования
double fA;//значение функции на границе A
double fB;//значение функции на границе B
double s;//частичная сумма
} mstk[N];
</source>
В процедурах работы со стеком доступны следующие операции: 
1)Проверка наличия элементов в стеке:
<source lang="cpp">
#define STACK_IS_NOT_FREE (sp > 0)
</source>
2)Операция "положить в стек":
<source lang="cpp">
#define PUT_INTO_STACK(A, B, fA, fB, s) {
mstk[sp].A = A;
mstk[sp].B = B;
mstk[sp].fA = fA;
mstk[sp].fB = fB;
mstk[sp].s = s;
++sp;
}
</source>
3)Операция "взять из стека верхний элемент":

<source lang="cpp">
#define GET_FROM_STACK(A, B, fA, fB, s) {
--sp;
A = mstk[sp].A;
B = mstk[sp].B;
fA = mstk[sp].fA;
fB = mstk[sp].fB;
s = mstk[sp].s;
}

</source>

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

// Заданная функция f(x)
double f(double x);

Рассмотрим функцию JLS, вычисляющую определенный интеграл от f(x) на [A,B] с заданной точностью eps методом локального стека, которая является вычислительным ядром алгоритма:
<source lang="cpp">
int JLS(double A, double B, double eps) {
double J = 0;//значение интеграла
double fA = f(A);//значение функции f(x)на границе A
double fB = f(B);//значение функции f(x)на границе B
double C;//середина отрезка [A,B]
double fC;//значение функции f(x)в середине отрезка [A,B]
double sAB = (fA + fB)*(B - A)/2;//вычисление площади трапеции с основанием AB
double sAC;//площадь трапеции с основанием AС
double sCB;//площадь трапеции с основанием СВ
double sACB;//сумма sAC и sCB
while(1) {
C = (A + B)/2;//середина отрезка
fC = f(C);
sAC = (fA + fC)*(C - A)/2;
sCB = (fC + fB )*(B - C)/2;
sACB = sAC + sCB;
//проверка выполнения условия на порядок точности:
if(abs(sAB - sACB) >= eps*abs(sACB)) {
PUT_INTO_STACK(A, C, fA, fC, sAC);
A = C;
fA = fC;
sAB = sCB;
}
else {
J += sACB;
if(STACK_IS_NOT_FREE) {
break;
}
GET_FROM_STACK(A, B, fA, fB, sAB);
}
}
return J;
}
</source>

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

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

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

*Пусть есть доступный всем параллельным процессам список отрезков интегрирования,организованный в виде стека. Назовем его глобальным стеком.
*Пусть у каждого процесса есть свой, доступный только этому процессу локальный стек
*Перед запуском параллельных процессов в глобальный стек помещается единственная запись (в дальнейшем "отрезок"):
координаты концов отрезка интегрирования,
значения функции на концах,
приближенное значение интеграла на этом отрезке.
*Тогда, предлагается следующая схема алгоритма, выполняемого каждым из параллельных процессов:

Пока в глобальном стеке есть отрезки:
*взять один отрезок из глобального стека
*выполнить алгоритм локального стека, но,если при записи в локальный стек в нем есть несколько отрезков, а в глобальном стеке отрезки отсутствуют, то переместить часть отрезков из локального стека в глобальный стек
* по исчерпании локального стека добавить полученную частичную сумму к общему значению интеграла.

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

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

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 

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

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

=== Масштабируемость алгоритма и его реализации ===

=== Существующие реализации алгоритма ===
В настоящее время проблемой вычисления определенного графа на адаптивной сетке по нашим сведениям занимались только М.В. Якобовский и Е.Ю. Кулькова, рассматривавшие в своей работе "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ" методы локального и глобального стеков.

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

2016-10-15T20:29:49Z

Sannikovats:

{{algorithm
| name = Вычисление определённого интеграла с использованием адаптивно сгущающейся сетки
| serial_complexity = <math>...</math>
| pf_height = <math>...</math>
| pf_width = <math>...</math>
| input_data = <math>...</math>
| output_data = <math>...</math>
}}

Основные авторы описания:[[Участница:Sannikovats| Санникова Татьяна Сергеевна]],[[Участник:Plukshin| Лукшин Петр Андреевич]].

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

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

Допустим, нам дана функция <math>f(x)</math> , определенная на отрезке, и возможность получать ее численное значение в любой из точек области определения за фиксированное время. Задача — вычислить определенный интеграл данной функции по заданной области и дать оценку погрешности вычисления. В случае, когда можно вычислить интеграл по формуле Ньютона-Лейбница, зная первообразную искомой функции, проблем не возникает. Однако, если первообразной нет, решение можно получить благодаря численным методам. Так определенному интегралу можно дать простую геометрическую интерпретацию - он равен площади криволинейной трапеции, ограниченной слева и справа вертикальными прямыми x=a, x=b, снизу - прямой y=0, а сверху – кривой y=f(x).

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

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

Простейший из них - это метод рекурсивного деления, выигрыш от применения которого достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Интервал интегрирования разбивается на две части и независимо интегрируется функция <math>f(x)</math> на каждой из них при соответствующих шагах интегрирования. Процедуру разбиения отрезков можно рекурсивно повторить до получения отрезков, на которых подынтегральная функция имеет простой вид и может быть аппроксимирована отрезком прямой с заданной точностью. Но при распараллеливании этого алгоритма (т.е. при запуске попарно подпрограмм, обрабатывающих половинки разбиваемого интервала) можно столкнуться со следующей проблемой: в реальной системе число процессоров ограничено и время, необходимое для порождения параллельных процессов существенно не равно нулю. А значит, запуск процессов, число которых значительно превышает число физических процессов системы при решении рассматриваемой задачи, приводит к увеличению времени ее решения по сравнению с последовательной программой. Основная сложность построения параллельного алгоритма на основе рассмотренного последовательного алгоритма, кроется в том, что, хотя несколько ветвей программы могли бы одновременно обрабатывать разные части интервала интегрирования, координаты концов этих отрезков хранятся в программном стеке процесса и фактически недоступны программисту. Если бы они были расположены в некотором явно описанном массиве, можно было бы передать их по частям для обработки разным нитям программы. Поэтому, необходимо рассмотреть метод локального стека, позволяющий распределить вычислительную работу между ограниченным числом процессов.

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

В основе этого алгоритма лежит описанный выше метод рекурсивного деления. Только данный метод использует массив данных, доступ к которым осуществляется по принципу стека - первым удаляется последний из добавленных элементов. В рассматриваемом алгоритме вместо стека можно было использовать и другие способы хранения заданий, например очередь. Стек выбран исключительно из соображений простоты реализации. Времена выполнения рассмотренных алгоритмов отличаются примерно на 5% в пользу локального стека, таким образом, алгоритм "локального стека" будем считать наилучшим из имеющихся в нашем распоряжении последовательных методов и на его примере построим дальнейшее описание.

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 
В качестве модельной задачи рассматривается проблема вычисления с точностью ε значения определенного интеграла 
[[Файл:1.jpg]]

Пусть на отрезке <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> J_n(A,B)=\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>

[[Файл: 2sann.jpg]] [[Файл:3sann.jpg]]

Будем полагать значение <math> J </math> найденным с точностью <math> \epsilon </math>, если выполнено условие:

<math> |J_{n_1} - J_{n_2}| \leq \epsilon |J_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Используемые в алгоритме формулы: 
*Из метода трапеций <math>sAB=\frac{f(A)+f(B)}{2}*(B-A)</math>

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

Основное время работы алгоритма приходится на: 
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала,
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

=== Макроструктура алгоритма ===
В реализации алгоритма используется такая структура данных, как стек, в котором хранятся координаты концов отрезков.
<source lang="cpp">
//Данные, описывающие стек
int sp = 0; // Указатель вершины стека

// Массив структур, в которых хранятся отложенные задания
struct mstk {
double A;//координата левой границы отрезка интегрирования
double B;//координата правой границы отрезка интегрирования
double fA;//значение функции на границе A
double fB;//значение функции на границе B
double s;//частичная сумма
} mstk[N];
</source>
В процедурах работы со стеком доступны следующие операции: 
1)Проверка наличия элементов в стеке:
<source lang="cpp">
#define STACK_IS_NOT_FREE (sp > 0)
</source>
2)Операция "положить в стек":
<source lang="cpp">
#define PUT_INTO_STACK(A, B, fA, fB, s) {
mstk[sp].A = A;
mstk[sp].B = B;
mstk[sp].fA = fA;
mstk[sp].fB = fB;
mstk[sp].s = s;
++sp;
}
</source>
3)Операция "взять из стека верхний элемент":

<source lang="cpp">
#define GET_FROM_STACK(A, B, fA, fB, s) {
--sp;
A = mstk[sp].A;
B = mstk[sp].B;
fA = mstk[sp].fA;
fB = mstk[sp].fB;
s = mstk[sp].s;
}

</source>

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

// Заданная функция f(x)
double f(double x);

Рассмотрим функцию JLS, вычисляющую определенный интеграл от f(x) на [A,B] с заданной точностью eps методом локального стека, которая является вычислительным ядром алгоритма:
<source lang="cpp">
int JLS(double A, double B, double eps) {
double J = 0;//значение интеграла
double fA = f(A);//значение функции f(x)на границе A
double fB = f(B);//значение функции f(x)на границе B
double C;//середина отрезка [A,B]
double fC;//значение функции f(x)в середине отрезка [A,B]
double sAB = (fA + fB)*(B - A)/2;//вычисление площади трапеции с основанием AB
double sAC;//площадь трапеции с основанием AС
double sCB;//площадь трапеции с основанием СВ
double sACB;//сумма sAC и sCB
while(1) {
C = (A + B)/2;//середина отрезка
fC = f(C);
sAC = (fA + fC)*(C - A)/2;
sCB = (fC + fB )*(B - C)/2;
sACB = sAC + sCB;
//проверка выполнения условия на порядок точности:
if(abs(sAB - sACB) >= eps*abs(sACB)) {
PUT_INTO_STACK(A, C, fA, fC, sAC);
A = C;
fA = fC;
sAB = sCB;
}
else {
J += sACB;
if(STACK_IS_NOT_FREE) {
break;
}
GET_FROM_STACK(A, B, fA, fB, sAB);
}
}
return J;
}
</source>

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

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

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

*Пусть есть доступный всем параллельным процессам список отрезков интегрирования,организованный в виде стека. Назовем его глобальным стеком.
*Пусть у каждого процесса есть свой, доступный только этому процессу локальный стек
*Перед запуском параллельных процессов в глобальный стек помещается единственная запись (в дальнейшем "отрезок"):
координаты концов отрезка интегрирования,
значения функции на концах,
приближенное значение интеграла на этом отрезке.
*Тогда, предлагается следующая схема алгоритма, выполняемого каждым из параллельных процессов:

Пока в глобальном стеке есть отрезки:
*взять один отрезок из глобального стека
*выполнить алгоритм локального стека, но,если при записи в локальный стек в нем есть несколько отрезков, а в глобальном стеке отрезки отсутствуют, то переместить часть отрезков из локального стека в глобальный стек
* по исчерпании локального стека добавить полученную частичную сумму к общему значению интеграла.

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

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

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 

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

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

=== Масштабируемость алгоритма и его реализации ===

=== Существующие реализации алгоритма ===
В настоящее время проблемой вычисления определенного графа на адаптивной сетке по нашим сведениям занимались только М.В. Якобовский и Е.Ю. Кулькова, рассматривавшие в своей работе "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ" методы локального и глобального стеков.

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

2016-10-15T19:30:08Z

Sannikovats:

{{algorithm
| name = Вычисление определённого интеграла с использованием адаптивно сгущающейся сетки
| serial_complexity = <math>...</math>
| pf_height = <math>...</math>
| pf_width = <math>...</math>
| input_data = <math>...</math>
| output_data = <math>...</math>
}}

Основные авторы описания:[[Участница:Sannikovats| Санникова Татьяна Сергеевна]],[[Участник:Plukshin| Лукшин Петр Андреевич]].

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

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

Допустим, нам дана функция <math>f(x)</math> , определенная на отрезке, и возможность получать ее численное значение в любой из точек области определения за фиксированное время. Задача — вычислить определенный интеграл данной функции по заданной области и дать оценку погрешности вычисления. В случае, когда можно вычислить интеграл по формуле Ньютона-Лейбница, зная первообразную искомой функции, проблем не возникает. Однако, если первообразной нет, решение можно получить благодаря численным методам. Так определенному интегралу можно дать простую геометрическую интерпретацию - он равен площади криволинейной трапеции, ограниченной слева и справа вертикальными прямыми x=a, x=b, снизу - прямой y=0, а сверху – кривой y=f(x).

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

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

Простейший из них - это метод рекурсивного деления, выигрыш от применения которого достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Интервал интегрирования разбивается на две части и независимо интегрируется функция <math>f(x)</math> на каждой из них при соответствующих шагах интегрирования. Процедуру разбиения отрезков можно рекурсивно повторить до получения отрезков, на которых подынтегральная функция имеет простой вид и может быть аппроксимирована отрезком прямой с заданной точностью. Но при распараллеливании этого алгоритма (т.е. при запуске попарно подпрограмм, обрабатывающих половинки разбиваемого интервала) можно столкнуться со следующей проблемой: в реальной системе число процессоров ограничено и время, необходимое для порождения параллельных процессов существенно не равно нулю. А значит, запуск процессов, число которых значительно превышает число физических процессов системы при решении рассматриваемой задачи, приводит к увеличению времени ее решения по сравнению с последовательной программой. Основная сложность построения параллельного алгоритма на основе рассмотренного последовательного алгоритма, кроется в том, что, хотя несколько ветвей программы могли бы одновременно обрабатывать разные части интервала интегрирования, координаты концов этих отрезков хранятся в программном стеке процесса и фактически недоступны программисту. Если бы они были расположены в некотором явно описанном массиве, можно было бы передать их по частям для обработки разным нитям программы. Поэтому, необходимо рассмотреть метод локального стека, позволяющий распределить вычислительную работу между ограниченным числом процессов.

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

В основе этого алгоритма лежит описанный выше метод рекурсивного деления. Только данный метод использует массив данных, доступ к которым осуществляется по принципу стека - первым удаляется последний из добавленных элементов. В рассматриваемом алгоритме вместо стека можно было использовать и другие способы хранения заданий, например очередь. Стек выбран исключительно из соображений простоты реализации. Времена выполнения рассмотренных алгоритмов отличаются примерно на 5% в пользу локального стека, таким образом, алгоритм "локального стека" будем считать наилучшим из имеющихся в нашем распоряжении последовательных методов и на его примере построим дальнейшее описание.

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 
В качестве модельной задачи рассматривается проблема вычисления с точностью ε значения определенного интеграла 
[[Файл:1.jpg]]

Пусть на отрезке <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> J_n(A,B)=\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>

[[Файл: 2sann.jpg]] [[Файл:3sann.jpg]]

Будем полагать значение <math> J </math> найденным с точностью <math> \epsilon </math>, если выполнено условие:

<math> |J_{n_1} - J_{n_2}| \leq \epsilon |J_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Используемые в алгоритме формулы: 
*Из метода трапеций <math>sAB=\frac{f(A)+f(B)}{2}*(B-A)</math>

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

Основное время работы алгоритма приходится на: 
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала,
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

=== Макроструктура алгоритма ===
В реализации алгоритма используется такая структура данных, как стек, в котором хранятся координаты концов отрезков.
<source lang="cpp">
//Данные, описывающие стек
int sp = 0; // Указатель вершины стека

// Массив структур, в которых хранятся отложенные задания
struct mstk {
double A;//координата левой границы отрезка интегрирования
double B;//координата правой границы отрезка интегрирования
double fA;//значение функции на границе A
double fB;//значение функции на границе B
double s;//частичная сумма
} mstk[N];
</source>
В процедурах работы со стеком доступны следующие операции: 
1)Проверка наличия элементов в стеке:
<source lang="cpp">
#define STACK_IS_NOT_FREE (sp > 0)
</source>
2)Операция "положить в стек":
<source lang="cpp">
#define PUT_INTO_STACK(A, B, fA, fB, s) {
mstk[sp].A = A;
mstk[sp].B = B;
mstk[sp].fA = fA;
mstk[sp].fB = fB;
mstk[sp].s = s;
++sp;
}
</source>
3)Операция "взять из стека верхний элемент":

<source lang="cpp">
#define GET_FROM_STACK(A, B, fA, fB, s) {
--sp;
A = mstk[sp].A;
B = mstk[sp].B;
fA = mstk[sp].fA;
fB = mstk[sp].fB;
s = mstk[sp].s;
}

</source>

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

// Заданная функция f(x)
double f(double x);

Рассмотрим функцию JLS, вычисляющую определенный интеграл от f(x) на [A,B] с заданной точностью eps методом локального стека, которая является вычислительным ядром алгоритма:
<source lang="cpp">
int JLS(double A, double B, double eps) {
double J = 0;//значение интеграла
double fA = f(A);//значение функции f(x)на границе A
double fB = f(B);//значение функции f(x)на границе B
double C;//середина отрезка [A,B]
double fC;//значение функции f(x)в середине отрезка [A,B]
double sAB = (fA + fB)*(B - A)/2;//вычисление площади трапеции с основанием AB
double sAC;//площадь трапеции с основанием AС
double sCB;//площадь трапеции с основанием СВ
double sACB;//сумма sAC и sCB
while(1) {
C = (A + B)/2;//середина отрезка
fC = f(C);
sAC = (fA + fC)*(C - A)/2;
sCB = (fC + fB )*(B - C)/2;
sACB = sAC + sCB;
//проверка выполнения условия на порядок точности:
if(abs(sAB - sACB) >= eps*abs(sACB)) {
PUT_INTO_STACK(A, C, fA, fC, sAC);
A = C;
fA = fC;
sAB = sCB;
}
else {
J += sACB;
if(STACK_IS_NOT_FREE) {
break;
}
GET_FROM_STACK(A, B, fA, fB, sAB);
}
}
return J;
}
</source>

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

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

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

*Пусть есть доступный всем параллельным процессам список отрезков интегрирования,организованный в виде стека. Назовем его глобальным стеком.
*Пусть у каждого процесса есть свой, доступный только этому процессу локальный стек
*Перед запуском параллельных процессов в глобальный стек помещается единственная запись (в дальнейшем "отрезок"):
координаты концов отрезка интегрирования,
значения функции на концах,
приближенное значение интеграла на этом отрезке.
*Тогда, предлагается следующая схема алгоритма, выполняемого каждым из параллельных процессов:

Пока в глобальном стеке есть отрезки:
*взять один отрезок из глобального стека
*выполнить алгоритм локального стека, но,если при записи в локальный стек в нем есть несколько отрезков, а в глобальном стеке отрезки отсутствуют, то переместить часть отрезков из локального стека в глобальный стек
* по исчерпании локального стека добавить полученную частичную сумму к общему значению интеграла.

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

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

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

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

=== Масштабируемость алгоритма и его реализации ===

=== Существующие реализации алгоритма ===
В настоящее время проблемой вычисления определенного графа на адаптивной сетке по нашим сведениям занимались только М.В. Якобовский и Е.Ю. Кулькова, рассматривавшие в своей работе "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ" методы локального и глобального стеков.

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

2016-10-15T19:24:44Z

Sannikovats:

{{algorithm
| name = Вычисление определённого интеграла с использованием адаптивно сгущающейся сетки
| serial_complexity = <math>...</math>
| pf_height = <math>...</math>
| pf_width = <math>...</math>
| input_data = <math>...</math>
| output_data = <math>...</math>
}}

Основные авторы описания:[[Участница:Sannikovats| Санникова Татьяна Сергеевна]],[[Участник:Plukshin| Лукшин Петр Андреевич]].

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

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

Допустим, нам дана функция <math>f(x)</math> , определенная на отрезке, и возможность получать ее численное значение в любой из точек области определения за фиксированное время. Задача — вычислить определенный интеграл данной функции по заданной области и дать оценку погрешности вычисления. Определенному
интегралу можно дать простую геометрическую интерпретацию - он равен площади криволинейной трапеции, ограниченной слева и справа вертикальными прямыми x=a, x=b, снизу - прямой y=0, а сверху – кривой y=f(x).

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

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

Простейший из них - это метод рекурсивного деления, выигрыш от применения которого достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Интервал интегрирования разбивается на две части и независимо интегрируется функция <math>f(x)</math> на каждой из них при соответствующих шагах интегрирования. Процедуру разбиения отрезков можно рекурсивно повторить до получения отрезков, на которых подынтегральная функция имеет простой вид и может быть аппроксимирована отрезком прямой с заданной точностью. Но при распараллеливании этого алгоритма (т.е. при запуске попарно подпрограмм, обрабатывающих половинки разбиваемого интервала) можно столкнуться со следующей проблемой: в реальной системе число процессоров ограничено и время, необходимое для порождения параллельных процессов существенно не равно нулю. А значит, запуск процессов, число которых значительно превышает число физических процессов системы при решении рассматриваемой задачи, приводит к увеличению времени ее решения по сравнению с последовательной программой. Основная сложность построения параллельного алгоритма на основе рассмотренного последовательного алгоритма, кроется в том, что, хотя несколько ветвей программы могли бы одновременно обрабатывать разные части интервала интегрирования, координаты концов этих отрезков хранятся в программном стеке процесса и фактически недоступны программисту. Если бы они были расположены в некотором явно описанном массиве, можно было бы передать их по частям для обработки разным нитям программы. Поэтому, необходимо рассмотреть метод локального стека, позволяющий распределить вычислительную работу между ограниченным числом процессов.

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

В основе этого алгоритма лежит описанный выше метод рекурсивного деления. Только данный метод использует массив данных, доступ к которым осуществляется по принципу стека - первым удаляется последний из добавленных элементов. В рассматриваемом алгоритме вместо стека можно было использовать и другие способы хранения заданий, например очередь. Стек выбран исключительно из соображений простоты реализации. Времена выполнения рассмотренных алгоритмов отличаются примерно на 5% в пользу локального стека, таким образом, алгоритм "локального стека" будем считать наилучшим из имеющихся в нашем распоряжении последовательных методов и на его примере построим дальнейшее описание.

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 
В качестве модельной задачи рассматривается проблема вычисления с точностью ε значения определенного интеграла 
[[Файл:1.jpg]]

Пусть на отрезке <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> J_n(A,B)=\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>

[[Файл: 2sann.jpg]] [[Файл:3sann.jpg]]

Будем полагать значение <math> J </math> найденным с точностью <math> \epsilon </math>, если выполнено условие:

<math> |J_{n_1} - J_{n_2}| \leq \epsilon |J_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Используемые в алгоритме формулы: 
*Из метода трапеций <math>sAB=\frac{f(A)+f(B)}{2}*(B-A)</math>

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

Основное время работы алгоритма приходится на: 
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала,
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

=== Макроструктура алгоритма ===
В реализации алгоритма используется такая структура данных, как стек, в котором хранятся координаты концов отрезков.
<source lang="cpp">
//Данные, описывающие стек
int sp = 0; // Указатель вершины стека

// Массив структур, в которых хранятся отложенные задания
struct mstk {
double A;//координата левой границы отрезка интегрирования
double B;//координата правой границы отрезка интегрирования
double fA;//значение функции на границе A
double fB;//значение функции на границе B
double s;//частичная сумма
} mstk[N];
</source>
В процедурах работы со стеком доступны следующие операции: 
1)Проверка наличия элементов в стеке:
<source lang="cpp">
#define STACK_IS_NOT_FREE (sp > 0)
</source>
2)Операция "положить в стек":
<source lang="cpp">
#define PUT_INTO_STACK(A, B, fA, fB, s) {
mstk[sp].A = A;
mstk[sp].B = B;
mstk[sp].fA = fA;
mstk[sp].fB = fB;
mstk[sp].s = s;
++sp;
}
</source>
3)Операция "взять из стека верхний элемент":

<source lang="cpp">
#define GET_FROM_STACK(A, B, fA, fB, s) {
--sp;
A = mstk[sp].A;
B = mstk[sp].B;
fA = mstk[sp].fA;
fB = mstk[sp].fB;
s = mstk[sp].s;
}

</source>

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

// Заданная функция f(x)
double f(double x);

Рассмотрим функцию JLS, вычисляющую определенный интеграл от f(x) на [A,B] с заданной точностью eps методом локального стека, которая является вычислительным ядром алгоритма:
<source lang="cpp">
int JLS(double A, double B, double eps) {
double J = 0;//значение интеграла
double fA = f(A);//значение функции f(x)на границе A
double fB = f(B);//значение функции f(x)на границе B
double C;//середина отрезка [A,B]
double fC;//значение функции f(x)в середине отрезка [A,B]
double sAB = (fA + fB)*(B - A)/2;//вычисление площади трапеции с основанием AB
double sAC;//площадь трапеции с основанием AС
double sCB;//площадь трапеции с основанием СВ
double sACB;//сумма sAC и sCB
while(1) {
C = (A + B)/2;//середина отрезка
fC = f(C);
sAC = (fA + fC)*(C - A)/2;
sCB = (fC + fB )*(B - C)/2;
sACB = sAC + sCB;
//проверка выполнения условия на порядок точности:
if(abs(sAB - sACB) >= eps*abs(sACB)) {
PUT_INTO_STACK(A, C, fA, fC, sAC);
A = C;
fA = fC;
sAB = sCB;
}
else {
J += sACB;
if(STACK_IS_NOT_FREE) {
break;
}
GET_FROM_STACK(A, B, fA, fB, sAB);
}
}
return J;
}
</source>

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

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

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

*Пусть есть доступный всем параллельным процессам список отрезков интегрирования,организованный в виде стека. Назовем его глобальным стеком.
*Пусть у каждого процесса есть свой, доступный только этому процессу локальный стек
*Перед запуском параллельных процессов в глобальный стек помещается единственная запись (в дальнейшем "отрезок"):
координаты концов отрезка интегрирования,
значения функции на концах,
приближенное значение интеграла на этом отрезке.
*Тогда, предлагается следующая схема алгоритма, выполняемого каждым из параллельных процессов:

Пока в глобальном стеке есть отрезки:
*взять один отрезок из глобального стека
*выполнить алгоритм локального стека, но,если при записи в локальный стек в нем есть несколько отрезков, а в глобальном стеке отрезки отсутствуют, то переместить часть отрезков из локального стека в глобальный стек
* по исчерпании локального стека добавить полученную частичную сумму к общему значению интеграла.

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

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

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

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

=== Масштабируемость алгоритма и его реализации ===

=== Существующие реализации алгоритма ===
В настоящее время проблемой вычисления определенного графа на адаптивной сетке по нашим сведениям занимались только М.В. Якобовский и Е.Ю. Кулькова, рассматривавшие в своей работе "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ" методы локального и глобального стеков.

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

2016-10-15T19:10:24Z

Sannikovats:

{{algorithm
| name = Вычисление определённого интеграла с использованием адаптивно сгущающейся сетки
| serial_complexity = <math>...</math>
| pf_height = <math>...</math>
| pf_width = <math>...</math>
| input_data = <math>...</math>
| output_data = <math>...</math>
}}

Основные авторы описания:[[Участница:Sannikovats| Санникова Татьяна Сергеевна]],[[Участник:Plukshin| Лукшин Петр Андреевич]].

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

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

Допустим, нам дана функция <math>f(x)</math> , определенная на отрезке, и возможность получать ее численное значение в любой из точек области определения за фиксированное время. Задача — вычислить определенный интеграл данной функции по заданной области и дать оценку погрешности вычисления. Определенному
интегралу можно дать простую геометрическую интерпретацию - он равен площади криволинейной трапеции, ограниченной слева и справа вертикальными прямыми x=a, x=b, снизу - прямой y=0, а сверху – кривой y=f(x).

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

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

Простейший из них - это метод рекурсивного деления, выигрыш от применения которого достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Интервал интегрирования разбивается на две части и независимо интегрируется функция <math>f(x)</math> на каждой из них при соответствующих шагах интегрирования. Процедуру разбиения отрезков можно рекурсивно повторить до получения отрезков, на которых подынтегральная функция имеет простой вид и может быть аппроксимирована отрезком прямой с заданной точностью. Но при распараллеливании этого алгоритма (т.е. при запуске попарно подпрограмм, обрабатывающих половинки разбиваемого интервала) можно столкнуться со следующей проблемой: в реальной системе число процессоров ограничено и время, необходимое для порождения параллельных процессов существенно не равно нулю. А значит, запуск процессов, число которых значительно превышает число физических процессов системы при решении рассматриваемой задачи, приводит к увеличению времени ее решения по сравнению с последовательной программой. Основная сложность построения параллельного алгоритма на основе рассмотренного последовательного алгоритма, кроется в том, что, хотя несколько ветвей программы могли бы одновременно обрабатывать разные части интервала интегрирования, координаты концов этих отрезков хранятся в программном стеке процесса и фактически недоступны программисту. Если бы они были расположены в некотором явно описанном массиве, можно было бы передать их по частям для обработки разным нитям программы. Поэтому, необходимо рассмотреть метод локального стека, позволяющий распределить вычислительную работу между ограниченным числом процессов.

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

В основе этого алгоритма лежит описанный выше метод рекурсивного деления. Только данный метод использует массив данных, доступ к которым осуществляется по принципу стека - первым удаляется последний из добавленных элементов. В рассматриваемом алгоритме вместо стека можно было использовать и другие способы хранения заданий, например очередь. Стек выбран исключительно из соображений простоты реализации. Времена выполнения рассмотренных алгоритмов отличаются примерно на 5% в пользу локального стека, таким образом, алгоритм "локального стека" будем считать наилучшим из имеющихся в нашем распоряжении последовательных методов и на его примере построим дальнейшее описание.

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 
В качестве модельной задачи рассматривается проблема вычисления с точностью ε значения определенного интеграла 
[[Файл:1.jpg]]
 
Пусть на отрезке <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> J_n(A,B)=\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>

[[Файл: 2sann.jpg]] [[Файл:3sann.jpg]]

Будем полагать значение <math> J </math> найденным с точностью <math> \epsilon </math>, если выполнено условие:

<math> |J_{n_1} - J_{n_2}| \leq \epsilon |J_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Используемые в алгоритме формулы: 
*Из метода трапеций <math>sAB=\frac{f(A)+f(B)}{2}*(B-A)</math>

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

Основное время работы алгоритма приходится на: 
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала,
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

=== Макроструктура алгоритма ===
В реализации алгоритма используется такая структура данных, как стек, в котором хранятся координаты концов отрезков.
<source lang="cpp">
//Данные, описывающие стек
int sp = 0; // Указатель вершины стека

// Массив структур, в которых хранятся отложенные задания
struct mstk {
double A;//координата левой границы отрезка интегрирования
double B;//координата правой границы отрезка интегрирования
double fA;//значение функции на границе A
double fB;//значение функции на границе B
double s;//частичная сумма
} mstk[N];
</source>
В процедурах работы со стеком доступны следующие операции: 
1)Проверка наличия элементов в стеке:
<source lang="cpp">
#define STACK_IS_NOT_FREE (sp > 0)
</source>
2)Операция "положить в стек":
<source lang="cpp">
#define PUT_INTO_STACK(A, B, fA, fB, s) {
mstk[sp].A = A;
mstk[sp].B = B;
mstk[sp].fA = fA;
mstk[sp].fB = fB;
mstk[sp].s = s;
++sp;
}
</source>
3)Операция "взять из стека верхний элемент":

<source lang="cpp">
#define GET_FROM_STACK(A, B, fA, fB, s) {
--sp;
A = mstk[sp].A;
B = mstk[sp].B;
fA = mstk[sp].fA;
fB = mstk[sp].fB;
s = mstk[sp].s;
}

</source>

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

// Заданная функция f(x)
double f(double x);

Рассмотрим функцию JLS, вычисляющую определенный интеграл от f(x) на [A,B] с заданной точностью &epsilon методом локального стека, которая является вычислительным ядром алгоритма:
<source lang="cpp">
int JLS(double A, double B, double eps) {
double J = 0;//значение интеграла
double fA = f(A);//значение функции f(x)на границе A
double fB = f(B);//значение функции f(x)на границе B
double C;//середина отрезка [A,B]
double fC;//значение функции f(x)в середине отрезка [A,B]
double sAB = (fA + fB)*(B - A)/2;//вычисление площади трапеции с основанием AB
double sAC;
double sCB;
double sACB;
while(1) {
C = (A + B)/2;//середина отрезка
fC = f(C);
sAC = (fA + fC)*(C - A)/2;
sCB = (fC + fB )*(B - C)/2;
sACB = sAC + sCB;
if(abs(sAB - sACB) >= eps*abs(sACB)) {
PUT_INTO_STACK(A, C, fA, fC, sAC);
A = C;
fA = fC;
sAB = sCB;
}
else {
J += sACB;
if(STACK_IS_NOT_FREE) {
break;
}
GET_FROM_STACK(A, B, fA, fB, sAB);
}
}
return J;
}
</source>

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

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

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

*Пусть есть доступный всем параллельным процессам список отрезков интегрирования,организованный в виде стека. Назовем его глобальным стеком.
*Пусть у каждого процесса есть свой, доступный только этому процессу локальный стек
*Перед запуском параллельных процессов в глобальный стек помещается единственная запись (в дальнейшем "отрезок"):
координаты концов отрезка интегрирования,
значения функции на концах,
приближенное значение интеграла на этом отрезке.
*Тогда, предлагается следующая схема алгоритма, выполняемого каждым из параллельных процессов:

Пока в глобальном стеке есть отрезки:
*взять один отрезок из глобального стека
*выполнить алгоритм локального стека, но,если при записи в локальный стек в нем есть несколько отрезков, а в глобальном стеке отрезки отсутствуют, то переместить часть отрезков из локального стека в глобальный стек
* по исчерпании локального стека добавить полученную частичную сумму к общему значению интеграла.

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

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

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

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

=== Масштабируемость алгоритма и его реализации ===

=== Существующие реализации алгоритма ===
В настоящее время проблемой вычисления определенного графа на адаптивной сетке по нашим сведениям занимались только М.В. Якобовский и Е.Ю. Кулькова, рассматривавшие в своей работе "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ" методы локального и глобального стеков.

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

2016-10-15T18:35:11Z

Sannikovats:

{{algorithm
| name = Вычисление определённого интеграла с использованием адаптивно сгущающейся сетки
| serial_complexity = <math>...</math>
| pf_height = <math>...</math>
| pf_width = <math>...</math>
| input_data = <math>...</math>
| output_data = <math>...</math>
}}

Основные авторы описания:[[Участница:Sannikovats| Санникова Татьяна Сергеевна]],[[Участник:Plukshin| Лукшин Петр Андреевич]].

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

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

Допустим, нам дана функция <math>f(x)</math> , определенная на отрезке, и возможность получать ее численное значение в любой из точек области определения за фиксированное время. Задача — вычислить определенный интеграл данной функции по заданной области и дать оценку погрешности вычисления. Определенному
интегралу можно дать простую геометрическую интерпретацию - он равен площади криволинейной трапеции, ограниченной слева и справа вертикальными прямыми x=a, x=b, снизу - прямой y=0, а сверху – кривой y=f(x).

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

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

Простейший из них - это метод рекурсивного деления, выигрыш от применения которого достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Интервал интегрирования разбивается на две части и независимо интегрируется функция <math>f(x)</math> на каждой из них при соответствующих шагах интегрирования. Процедуру разбиения отрезков можно рекурсивно повторить до получения отрезков, на которых подынтегральная функция имеет простой вид и может быть аппроксимирована отрезком прямой с заданной точностью. Но при распараллеливании этого алгоритма (т.е. при запуске попарно подпрограмм, обрабатывающих половинки разбиваемого интервала) можно столкнуться со следующей проблемой: в реальной системе число процессоров ограничено и время, необходимое для порождения параллельных процессов существенно не равно нулю. А значит, запуск процессов, число которых значительно превышает число физических процессов системы при решении рассматриваемой задачи, приводит к увеличению времени ее решения по сравнению с последовательной программой. Основная сложность построения параллельного алгоритма на основе рассмотренного последовательного алгоритма, кроется в том, что, хотя несколько ветвей программы могли бы одновременно обрабатывать разные части интервала интегрирования, координаты концов этих отрезков хранятся в программном стеке процесса и фактически недоступны программисту. Если бы они были расположены в некотором явно описанном массиве, можно было бы передать их по частям для обработки разным нитям программы. Поэтому, необходимо рассмотреть метод локального стека, позволяющий распределить вычислительную работу между ограниченным числом процессов.

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

В основе этого алгоритма лежит описанный выше метод рекурсивного деления. Только данный метод использует массив данных, доступ к которым осуществляется по принципу стека - первым удаляется последний из добавленных элементов. В рассматриваемом алгоритме вместо стека можно было использовать и другие способы хранения заданий, например очередь. Стек выбран исключительно из соображений простоты реализации. Времена выполнения рассмотренных алгоритмов отличаются примерно на 5% в пользу локального стека, таким образом, алгоритм "локального стека" будем считать наилучшим из имеющихся в нашем распоряжении последовательных методов и на его примере построим дальнейшее описание.

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 
В качестве модельной задачи рассматривается проблема вычисления с точностью ε значения определенного интеграла 
[[Файл:1.jpg]]
 
Пусть на отрезке <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> J_n(A,B)=\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>

[[Файл: 2sann.jpg]] [[Файл:3sann.jpg]]

Будем полагать значение <math> J </math> найденным с точностью <math> \epsilon </math>, если выполнено условие:

<math> |J_{n_1} - J_{n_2}| \leq \epsilon |J_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Используемые в алгоритме формулы: 
*Из метода трапеций <math>sAB=\frac{f(A)+f(B)}{2}*(B-A)</math>

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

Основное время работы алгоритма приходится на: 
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала,
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

=== Макроструктура алгоритма ===
В реализации алгоритма используется такая структура данных, как стек, в котором хранятся координаты концов отрезков.
<source lang="cpp">
//Данные, описывающие стек
int sp = 0; // Указатель вершины стека

// Массив структур, в которых хранятся отложенные задания
struct mstk {
double A;//координата левой границы отрезка интегрирования
double B;//координата правой границы отрезка интегрирования
double fA;//значение функции на границе A
double fB;//значение функции на границе B
double s;//частичная сумма
} mstk[N];
</source>
В процедурах работы со стеком доступны следующие операции: 
1)Проверка наличия элементов в стеке:
<source lang="cpp">
#define STACK_IS_NOT_FREE (sp > 0)
</source>
2)Операция "положить в стек":
<source lang="cpp">
#define PUT_INTO_STACK(A, B, fA, fB, s) {
mstk[sp].A = A;
mstk[sp].B = B;
mstk[sp].fA = fA;
mstk[sp].fB = fB;
mstk[sp].s = s;
++sp;
}
</source>
3)Операция "взять из стека верхний элемент":

<source lang="cpp">
#define GET_FROM_STACK(A, B, fA, fB, s) {
--sp;
A = mstk[sp].A;
B = mstk[sp].B;
fA = mstk[sp].fA;
fB = mstk[sp].fB;
s = mstk[sp].s;
}

</source>

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

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

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

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

*Пусть есть доступный всем параллельным процессам список отрезков интегрирования,организованный в виде стека. Назовем его глобальным стеком.
*Пусть у каждого процесса есть свой, доступный только этому процессу локальный стек
*Перед запуском параллельных процессов в глобальный стек помещается единственная запись (в дальнейшем "отрезок"):
координаты концов отрезка интегрирования,
значения функции на концах,
приближенное значение интеграла на этом отрезке.
*Тогда, предлагается следующая схема алгоритма, выполняемого каждым из параллельных процессов:

Пока в глобальном стеке есть отрезки:
*взять один отрезок из глобального стека
*выполнить алгоритм локального стека, но,если при записи в локальный стек в нем есть несколько отрезков, а в глобальном стеке отрезки отсутствуют, то переместить часть отрезков из локального стека в глобальный стек
* по исчерпании локального стека добавить полученную частичную сумму к общему значению интеграла.

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

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

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

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

=== Масштабируемость алгоритма и его реализации ===

=== Существующие реализации алгоритма ===
В настоящее время проблемой вычисления определенного графа на адаптивной сетке по нашим сведениям занимались только М.В. Якобовский и Е.Ю. Кулькова, рассматривавшие в своей работе "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ" методы локального и глобального стеков.

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

2016-10-15T18:33:22Z

Sannikovats:

{{algorithm
| name = Вычисление определённого интеграла с использованием адаптивно сгущающейся сетки
| serial_complexity = <math>...</math>
| pf_height = <math>...</math>
| pf_width = <math>...</math>
| input_data = <math>...</math>
| output_data = <math>...</math>
}}

Основные авторы описания:[[Участница:Sannikovats| Санникова Татьяна Сергеевна]],[[Участник:Plukshin| Лукшин Петр Андреевич]].

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

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

Допустим, нам дана функция <math>f(x)</math> , определенная на отрезке, и возможность получать ее численное значение в любой из точек области определения за фиксированное время. Задача — вычислить определенный интеграл данной функции по заданной области и дать оценку погрешности вычисления. Определенному
интегралу можно дать простую геометрическую интерпретацию - он равен площади криволинейной трапеции, ограниченной слева и справа вертикальными прямыми x=a, x=b, снизу - прямой y=0, а сверху – кривой y=f(x).

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

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

Простейший из них - это метод рекурсивного деления, выигрыш от применения которого достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Интервал интегрирования разбивается на две части и независимо интегрируется функция <math>f(x)</math> на каждой из них при соответствующих шагах интегрирования. Процедуру разбиения отрезков можно рекурсивно повторить до получения отрезков, на которых подынтегральная функция имеет простой вид и может быть аппроксимирована отрезком прямой с заданной точностью. Но при распараллеливании этого алгоритма (т.е. при запуске попарно подпрограмм, обрабатывающих половинки разбиваемого интервала) можно столкнуться со следующей проблемой: в реальной системе число процессоров ограничено и время, необходимое для порождения параллельных процессов существенно не равно нулю. А значит, запуск процессов, число которых значительно превышает число физических процессов системы при решении рассматриваемой задачи, приводит к увеличению времени ее решения по сравнению с последовательной программой. Основная сложность построения параллельного алгоритма на основе рассмотренного последовательного алгоритма, кроется в том, что, хотя несколько ветвей программы могли бы одновременно обрабатывать разные части интервала интегрирования, координаты концов этих отрезков хранятся в программном стеке процесса и фактически недоступны программисту. Если бы они были расположены в некотором явно описанном массиве, можно было бы передать их по частям для обработки разным нитям программы. Поэтому, необходимо рассмотреть метод локального стека, позволяющий распределить вычислительную работу между ограниченным числом процессов.

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

В основе этого алгоритма лежит описанный выше метод рекурсивного деления. Только данный метод использует массив данных, доступ к которым осуществляется по принципу стека - первым удаляется последний из добавленных элементов. В рассматриваемом алгоритме вместо стека можно было использовать и другие способы хранения заданий, например очередь. Стек выбран исключительно из соображений простоты реализации. Времена выполнения рассмотренных алгоритмов отличаются примерно на 5% в пользу локального стека, таким образом, алгоритм "локального стека" будем считать наилучшим из имеющихся в нашем распоряжении последовательных методов и на его примере построим дальнейшее описание.

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 
В качестве модельной задачи рассматривается проблема вычисления с точностью ε значения определенного интеграла 
[[Файл:1.jpg]]
Пусть на отрезке <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> J_n(A,B)=\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>

[[Файл: 2sann.jpg]] [[Файл:3sann.jpg]]

Будем полагать значение <math> J </math> найденным с точностью <math> \epsilon </math>, если выполнено условие:

<math> |J_{n_1} - J_{n_2}| \leq \epsilon |J_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Используемые в алгоритме формулы: 
*Из метода трапеций <math>sAB=\frac{f(A)+f(B)}{2}*(B-A)</math>

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

Основное время работы алгоритма приходится на: 
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала,
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

=== Макроструктура алгоритма ===
В реализации алгоритма используется такая структура данных, как стек, в котором хранятся координаты концов отрезков.
<source lang="cpp">
//Данные, описывающие стек
int sp = 0; // Указатель вершины стека

// Массив структур, в которых хранятся отложенные задания
struct mstk {
double A;//координата левой границы отрезка интегрирования
double B;//координата правой границы отрезка интегрирования
double fA;//значение функции на границе A
double fB;//значение функции на границе B
double s;//частичная сумма
} mstk[N];
</source>
В процедурах работы со стеком доступны следующие операции:
1)Проверка наличия элементов в стеке:
<source lang="cpp">
1)Проверка наличия элементов в стеке
#define STACK_IS_NOT_FREE (sp > 0)
</source>
2)Операция "положить в стек":
<source lang="cpp">
#define PUT_INTO_STACK(A, B, fA, fB, s) {
mstk[sp].A = A;
mstk[sp].B = B;
mstk[sp].fA = fA;
mstk[sp].fB = fB;
mstk[sp].s = s;
++sp;
}
</source>
3)Операция "взять из стека верхний элемент":

<source lang="cpp">
#define GET_FROM_STACK(A, B, fA, fB, s) {
--sp;
A = mstk[sp].A;
B = mstk[sp].B;
fA = mstk[sp].fA;
fB = mstk[sp].fB;
s = mstk[sp].s;
}

</source>

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

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

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

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

*Пусть есть доступный всем параллельным процессам список отрезков интегрирования,организованный в виде стека. Назовем его глобальным стеком.
*Пусть у каждого процесса есть свой, доступный только этому процессу локальный стек
*Перед запуском параллельных процессов в глобальный стек помещается единственная запись (в дальнейшем "отрезок"):
координаты концов отрезка интегрирования,
значения функции на концах,
приближенное значение интеграла на этом отрезке.
*Тогда, предлагается следующая схема алгоритма, выполняемого каждым из параллельных процессов:

Пока в глобальном стеке есть отрезки:
*взять один отрезок из глобального стека
*выполнить алгоритм локального стека, но,если при записи в локальный стек в нем есть несколько отрезков, а в глобальном стеке отрезки отсутствуют, то переместить часть отрезков из локального стека в глобальный стек
* по исчерпании локального стека добавить полученную частичную сумму к общему значению интеграла.

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

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

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

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

=== Масштабируемость алгоритма и его реализации ===

=== Существующие реализации алгоритма ===
В настоящее время проблемой вычисления определенного графа на адаптивной сетке по нашим сведениям занимались только М.В. Якобовский и Е.Ю. Кулькова, рассматривавшие в своей работе "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ" методы локального и глобального стеков.

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

2016-10-15T18:28:44Z

Sannikovats:

{{algorithm
| name = Вычисление определённого интеграла с использованием адаптивно сгущающейся сетки
| serial_complexity = <math>...</math>
| pf_height = <math>...</math>
| pf_width = <math>...</math>
| input_data = <math>...</math>
| output_data = <math>...</math>
}}

Основные авторы описания:[[Участница:Sannikovats| Санникова Татьяна Сергеевна]],[[Участник:Plukshin| Лукшин Петр Андреевич]].

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

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

Допустим, нам дана функция <math>f(x)</math> , определенная на отрезке, и возможность получать ее численное значение в любой из точек области определения за фиксированное время. Задача — вычислить определенный интеграл данной функции по заданной области и дать оценку погрешности вычисления. Определенному
интегралу можно дать простую геометрическую интерпретацию - он равен площади криволинейной трапеции, ограниченной слева и справа вертикальными прямыми x=a, x=b, снизу - прямой y=0, а сверху – кривой y=f(x).

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

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

Простейший из них - это метод рекурсивного деления, выигрыш от применения которого достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Интервал интегрирования разбивается на две части и независимо интегрируется функция <math>f(x)</math> на каждой из них при соответствующих шагах интегрирования. Процедуру разбиения отрезков можно рекурсивно повторить до получения отрезков, на которых подынтегральная функция имеет простой вид и может быть аппроксимирована отрезком прямой с заданной точностью. Но при распараллеливании этого алгоритма (т.е. при запуске попарно подпрограмм, обрабатывающих половинки разбиваемого интервала) можно столкнуться со следующей проблемой: в реальной системе число процессоров ограничено и время, необходимое для порождения параллельных процессов существенно не равно нулю. А значит, запуск процессов, число которых значительно превышает число физических процессов системы при решении рассматриваемой задачи, приводит к увеличению времени ее решения по сравнению с последовательной программой. Основная сложность построения параллельного алгоритма на основе рассмотренного последовательного алгоритма, кроется в том, что, хотя несколько ветвей программы могли бы одновременно обрабатывать разные части интервала интегрирования, координаты концов этих отрезков хранятся в программном стеке процесса и фактически недоступны программисту. Если бы они были расположены в некотором явно описанном массиве, можно было бы передать их по частям для обработки разным нитям программы. Поэтому, необходимо рассмотреть метод локального стека, позволяющий распределить вычислительную работу между ограниченным числом процессов.

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

В основе этого алгоритма лежит описанный выше метод рекурсивного деления. Только данный метод использует массив данных, доступ к которым осуществляется по принципу стека - первым удаляется последний из добавленных элементов. В рассматриваемом алгоритме вместо стека можно было использовать и другие способы хранения заданий, например очередь. Стек выбран исключительно из соображений простоты реализации. Времена выполнения рассмотренных алгоритмов отличаются примерно на 5% в пользу локального стека, таким образом, алгоритм "локального стека" будем считать наилучшим из имеющихся в нашем распоряжении последовательных методов и на его примере построим дальнейшее описание.

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 
В качестве модельной задачи рассматривается проблема вычисления с точностью ε значения определенного интеграла 
[[Файл:1.jpg]]
Пусть на отрезке <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> J_n(A,B)=\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>

[[Файл: 2.jpg]] [[Файл:3.jpg]]

Будем полагать значение <math> J </math> найденным с точностью <math> \epsilon </math>, если выполнено условие:

<math> |J_{n_1} - J_{n_2}| \leq \epsilon |J_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Используемые в алгоритме формулы: 
*Из метода трапеций <math>sAB=\frac{f(A)+f(B)}{2}*(B-A)</math>

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

Основное время работы алгоритма приходится на: 
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала,
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

=== Макроструктура алгоритма ===
В реализации алгоритма используется такая структура данных, как стек, в котором хранятся координаты концов отрезков.
<source lang="cpp">
//Данные, описывающие стек
int sp = 0; // Указатель вершины стека

// Массив структур, в которых хранятся отложенные задания
struct mstk {
double A;//координата левой границы отрезка интегрирования
double B;//координата правой границы отрезка интегрирования
double fA;//значение функции на границе A
double fB;//значение функции на границе B
double s;//частичная сумма
} mstk[N];
</source>
В процедурах работы со стеком доступны следующие операции:
1)Проверка наличия элементов в стеке:
<source lang="cpp">
1)Проверка наличия элементов в стеке
#define STACK_IS_NOT_FREE (sp > 0)
</source>
2)Операция "положить в стек":
<source lang="cpp">
#define PUT_INTO_STACK(A, B, fA, fB, s) {
mstk[sp].A = A;
mstk[sp].B = B;
mstk[sp].fA = fA;
mstk[sp].fB = fB;
mstk[sp].s = s;
++sp;
}
</source>
3)Операция "взять из стека верхний элемент":

<source lang="cpp">
#define GET_FROM_STACK(A, B, fA, fB, s) {
--sp;
A = mstk[sp].A;
B = mstk[sp].B;
fA = mstk[sp].fA;
fB = mstk[sp].fB;
s = mstk[sp].s;
}

</source>

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

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

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

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

*Пусть есть доступный всем параллельным процессам список отрезков интегрирования,организованный в виде стека. Назовем его глобальным стеком.
*Пусть у каждого процесса есть свой, доступный только этому процессу локальный стек
*Перед запуском параллельных процессов в глобальный стек помещается единственная запись (в дальнейшем "отрезок"):
координаты концов отрезка интегрирования,
значения функции на концах,
приближенное значение интеграла на этом отрезке.
*Тогда, предлагается следующая схема алгоритма, выполняемого каждым из параллельных процессов:

Пока в глобальном стеке есть отрезки:
*взять один отрезок из глобального стека
*выполнить алгоритм локального стека, но,если при записи в локальный стек в нем есть несколько отрезков, а в глобальном стеке отрезки отсутствуют, то переместить часть отрезков из локального стека в глобальный стек
* по исчерпании локального стека добавить полученную частичную сумму к общему значению интеграла.

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

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

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

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

=== Масштабируемость алгоритма и его реализации ===

=== Существующие реализации алгоритма ===
В настоящее время проблемой вычисления определенного графа на адаптивной сетке по нашим сведениям занимались только М.В. Якобовский и Е.Ю. Кулькова, рассматривавшие в своей работе "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ" методы локального и глобального стеков.

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

2016-10-15T14:59:11Z

Sannikovats:

{{algorithm
| name = Вычисление определённого интеграла с использованием адаптивно сгущающейся сетки
| serial_complexity = <math>...</math>
| pf_height = <math>...</math>
| pf_width = <math>...</math>
| input_data = <math>...</math>
| output_data = <math>...</math>
}}

Основные авторы описания:[[Участница:Sannikovats| Санникова Татьяна Сергеевна]],[[Участник:Plukshin| Лукшин Петр Андреевич]].

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

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

Допустим, нам дана функция <math>f(x)</math> , определенная на отрезке, и возможность получать ее численное значение в любой из точек области определения за фиксированное время. Задача — вычислить определенный интеграл данной функции по заданной области и дать оценку погрешности вычисления. Определенному
интегралу можно дать простую геометрическую интерпретацию - он равен площади криволинейной трапеции, ограниченной слева и справа вертикальными прямыми x=a, x=b, снизу - прямой y=0, а сверху – кривой y=f(x).

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

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

Простейший из них - это метод рекурсивного деления, выигрыш от применения которого достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Интервал интегрирования разбивается на две части и независимо интегрируется функция <math>f(x)</math> на каждой из них при соответствующих шагах интегрирования. Процедуру разбиения отрезков можно рекурсивно повторить до получения отрезков, на которых подынтегральная функция имеет простой вид и может быть аппроксимирована отрезком прямой с заданной точностью. Но при распараллеливании этого алгоритма (т.е. при запуске попарно подпрограмм, обрабатывающих половинки разбиваемого интервала) можно столкнуться со следующей проблемой: в реальной системе число процессоров ограничено и время, необходимое для порождения параллельных процессов существенно не равно нулю. А значит, запуск процессов, число которых значительно превышает число физических процессов системы при решении рассматриваемой задачи, приводит к увеличению времени ее решения по сравнению с последовательной программой. Основная сложность построения параллельного алгоритма на основе рассмотренного последовательного алгоритма, кроется в том, что, хотя несколько ветвей программы могли бы одновременно обрабатывать разные части интервала интегрирования, координаты концов этих отрезков хранятся в программном стеке процесса и фактически недоступны программисту. Если бы они были расположены в некотором явно описанном массиве, можно было бы передать их по частям для обработки разным нитям программы. Поэтому, необходимо рассмотреть метод локального стека, позволяющий распределить вычислительную работу между ограниченным числом процессов.

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

В основе этого алгоритма лежит описанный выше метод рекурсивного деления. Только данный метод использует массив данных, доступ к которым осуществляется по принципу стека - первым удаляется последний из добавленных элементов. В рассматриваемом алгоритме вместо стека можно было использовать и другие способы хранения заданий, например очередь. Стек выбран исключительно из соображений простоты реализации. Времена выполнения рассмотренных алгоритмов отличаются примерно на 5% в пользу локального стека, таким образом, алгоритм "локального стека" будем считать наилучшим из имеющихся в нашем распоряжении последовательных методов и на его примере построим дальнейшее описание.

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

''Входные данные:'' заданная функция <math>f(x)</math>, определенная на отрезке <math>[A,B]</math>, заданная точность решения ε. 
''Выходные данные:'' число, представляющее собой приближенное значение интеграла. 
В качестве модельной задачи рассматривается проблема вычисления с точностью ε значения определенного интеграла 
[[Файл:1.jpg]]
Пусть на отрезке <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> J_n(A,B)=\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>

[[Файл: 2.jpg]] [[Файл:3.jpg]]

Будем полагать значение <math> J </math> найденным с точностью <math> \epsilon </math>, если выполнено условие:

<math> |J_{n_1} - J_{n_2}| \leq \epsilon |J_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Используемые в алгоритме формулы: 
*Из метода трапеций <math>sAB=\frac{f(A)+f(B)}{2}*(B-A)</math>

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

Основное время работы алгоритма приходится на: 
#нахождение середины отрезка и значения функции в этой точке; 
#вычисление частичных сумм на подобластях методом трапеций; 
#определение выполнения условия точности:
#*если не выполняется, то продолжаем дробить область,"закладывая" в стек границы нового интервала,
#*иначе добавляем к результату вычисленную сумму, завершая цикл.

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

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

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

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

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

*Пусть есть доступный всем параллельным процессам список отрезков интегрирования,организованный в виде стека. Назовем его глобальным стеком.
*Пусть у каждого процесса есть свой, доступный только этому процессу локальный стек
*Перед запуском параллельных процессов в глобальный стек помещается единственная запись (в дальнейшем "отрезок"):
координаты концов отрезка интегрирования,
значения функции на концах,
приближенное значение интеграла на этом отрезке.
*Тогда, предлагается следующая схема алгоритма, выполняемого каждым из параллельных процессов:

Пока в глобальном стеке есть отрезки:
*взять один отрезок из глобального стека
*выполнить алгоритм локального стека, но,если при записи в локальный стек в нем есть несколько отрезков, а в глобальном стеке отрезки отсутствуют, то переместить часть отрезков из локального стека в глобальный стек
* по исчерпании локального стека добавить полученную частичную сумму к общему значению интеграла.

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

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

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

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

=== Масштабируемость алгоритма и его реализации ===

=== Существующие реализации алгоритма ===
В настоящее время проблемой вычисления определенного графа на адаптивной сетке по нашим сведениям занимались только М.В. Якобовский и Е.Ю. Кулькова, рассматривавшие в своей работе "РЕШЕНИЕ ЗАДАЧ НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ" методы локального и глобального стеков.

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

2016-10-15T14:03:34Z

Sannikovats:

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

2016-10-15T13:38:27Z

Sannikovats:

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

2016-10-15T13:35:39Z

Sannikovats:

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

2016-10-15T11:29:35Z

Sannikovats:

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

2016-10-15T11:28:53Z

Sannikovats:

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

2016-10-15T11:27:41Z

Sannikovats:

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

2016-10-15T11:05:42Z

Sannikovats:

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

2016-10-15T10:43:27Z

Sannikovats:

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

2016-10-14T11:25:19Z

Sannikovats:

Обсуждение участника:Lineprinter

2016-10-14T10:07:04Z

Sannikovats: /* Перенос */

== Перенос ==
Статья: [[Алгоритм кластеризации, основанный на сетях Кохоннена]];
Выполняют: Логвиненко Александра и Адиев Тохтар

Статья: [[Ортогонализация Грама-Шмидта]];
Выполняют: [[Участник:KibAndrey| Кибанов Андрей]] и Аджиева Татьяна

Статья: [[Самоорганизующиеся карты Кохонена]];
Выполняет: [[Участник:Anton goy| Гой Антон]]

Статья:[[ЕМ-алгоритм_(Тематическое_моделирование)]];
Выполняют: Мурат Апишев и Андрей Заночкин

Статья:[[Алгоритм_Ланцоша_с_полной_переортогонализацией]];
Выполняет:[[Участник:Sfedotov| Федотов С.А.]]

Статья: [[Алгоритм_k-средних]]
Выполняют: [[Участник:Error2407|Богомазов Евгений]], [[Участник:Илья_Егоров|Егоров Илья]]

Статья: [[Решение_задачи_Коши_для_системы_ОДУ_методом_Рунге-Кутты_4_порядка]];
Выполняют: [[Участник:Алимов_Дамир_Алиевич|Алимов Дамир]] и [[Участник:Anlesnichiy|Антон Лесничий]]

Статья: [[Строгий_алгоритм_С_средних_(Hard_C-Means,_HCM)]];
Выполняют: [[Участник:Светлана_Лукьяненко|Лукьяненко Светлана]] и [[Участник:Юрий_Комаров|Комаров Юрий]]

Статья: [[Алгоритм кластеризации, основанный на минимальном остовном дереве]];
Выполняет: [[Участник:Astandrik | Стандрик Антон Сергеевич]]

Статья: [[Нахождение_собственных_чисел_квадратной_матрицы_методом_QR_разложения_(3)|Нахождение собственных чисел квадратной матрицы методом QR разложения (3)]];
Выполняют: [[Участник:Смирнова_Александра|Смирнова А.С.]], [[Участник:Александра_Киямова|Киямова А.]]

Статья: [[Метод_Якоби_вычисления_сингулярных_чисел_и_векторов]];
Выполняют: [[Участница:Почернина_Елена| Почернина Елена]] и [[Участница:Светлана|Костюкова Светлана]]

Статья: [[Метод_Ньютона_для_решения_систем_нелинейных_уравнений(2)]];
Выполняют: [[Участник:Oleggium|Гирняк О.Р.]], [[Участник:Dimx19|Васильков Д.А.]]

Статья: [[Алгоритм_кластеризации_с_использованием_представлений]];
Выполняют: [[Участник:Cookie|Шатков С.А.]], [[Антохина Ю.А.]]

Статья: [[Быстрое_преобразование_Фурье_(FFT)|Быстрое преобразование Фурье (FFT)]];
Выполняют: [[Участник:Victoria_Stepanischeva|Степанищева Виктория]] и [[Участник:Igor_Munkin|Мунькин Игорь]]

Статья: [[Быстрое_дискретное_преобразование_Фурье|Быстрое_дискретное_преобразование_Фурье]];
Выполняют: [[Участник:ivanov.kir.m | К.М.Иванов]], [[Участник:Pumpkin | А.C.Сапин]]

Статья:[[Алгоритм_k_средних]]
Выполняют: [[Участник:Parkhomenko|Пархоменко Павел]], [[Участник:ivan.mashonskiy|Машонский Иван]]

Статья:[[EM-алгоритм_кластеризации]]
Выполняет: [[Участник:Noite|Зинченко Дмитрий]]

Статья:[[Алгоритм_k_means]]
Выполняют: [[Участник:IanaV| Валуйская Яна]], [[Глотов Евгений]]

Статья: [[Метод Якоби вычисления собственных значений симметричной матрицы ЗП |Метод Якоби вычисления собственных значений симметричной матрицы ЗП]];
Выполняют: [[Участник:Зиновьев Владимир|Зиновьев В.С.]], [[Участник:Пронин Андрей|Пронин А.М.]]

Статья:[[Алгоритм_кластеризации,_основанный_на_минимальном_покрывающем_дереве]]
Выполняет: [[Участник:Kanast74|Дмитриева Анастасия]]

Статья:[[Нахождение_собственных_чисел_квадратной_матрицы_методом_QR_разложения_(4)]]
Выполняют: [[Участник:F-morozov|Морозов Ф. В.]], [[Участник:Nataliya|Пащенко Н. Ф.]]

Статья:[[Хранение_ненулевых_элементов_разреженных_матриц._Умножение_разреженной_матрицы_на_вектор]];
Выполняют: [[Участник:Trrufina|Третьякова Р.М.]] и [[Участник:Екатерина_Буторина|Буторина Е.В.]]

Статья: [[Алгоритм_кластеризации_с_использованием_представлений2]];
Выполняет: [[Участник:Лукьянова Анна|Лукьянова А.Я.]]

Статья: [[Метод Якоби вычисления собственных значений симметричной матрицы]];
Выполняют: [[Участник: Galkina|Галкина А.С.]], [[Участник: Игорь|Плахов И.А.]]

Статья: [[Метод рекурсивной координатной бисекции]];
Выполняют: [[Участник: Obirvalger|Гордеев Михаил]], [[Участник: KolmakovEA|Колмаков Евгений]]

Статья: [[Итерационный метод решения системы линейных алгебраических уравнений GMRES (обобщенный метод минимальных невязок)]];
Выполняют: [[Участник: Эльвира Ахиярова|Ахиярова Эльвира]]

Статья: [[Хранение ненулевых элементов разреженной матрицы. Умножение разреженной матрицы на вектор]];
Выполняют: [[Участник: Janyell|Сычева Евгения]], [[Участник: Ahahalin|Хахалин Анатолий]]

Статья: [[Построение матрицы Адамара произвольного размера]];
Выполняют: [[Участник: Бугаков Юрий|Бугаков Юрий]], Кужамалиев Ернур

Статья: [[Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки (1)]]
Выполняют: [[Участница:Sannikovats| Санникова Татьяна Сергеевна]], [[Участник:Plukshin| Лукшин Петр Андреевич]]

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

2016-10-12T07:00:21Z

Sannikovats:

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

2016-10-11T20:50:28Z

Sannikovats:

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

2016-10-11T19:35:45Z

Sannikovats: Новая страница: «{{algorithm | name = Вычисление определённого интеграла с использованием адаптивно сгуща…»

Участница:Sannikovats

2016-10-11T19:18:48Z

Sannikovats: Новая страница: «Санникова Татьяна - магистрантка факультета ВМК МГУ, 604 группа»

Санникова Татьяна - магистрантка факультета ВМК МГУ, 604 группа