Адаптивное интегрирование - История изменений

Bvdmitri: Полностью удалено содержимое страницы

2016-11-13T21:32:45Z

Полностью удалено содержимое страницы

Pochtalionizm: /* Входные данные */

2016-11-13T21:31:00Z

Входные данные

← Предыдущая версия		Версия от 21:31, 13 ноября 2016
Строка 24:		Строка 24:

	* Функция.		* Функция.
	* Отрезок интегрирования [a, b].		* Отрезок интегрирования <math>[a, b]</math>.
	* Желаемая точность интегрирования ε.		* Желаемая точность интегрирования <math>\varepsilon</math>.

	=== Выходные данные ===		=== Выходные данные ===

Pochtalionizm: /* Математическое описание алгоритма */

2016-11-13T21:29:41Z

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

← Предыдущая версия		Версия от 21:29, 13 ноября 2016
Строка 11:		Строка 11:
	Формулы метода:		Формулы метода:

	# Интеграл функции вычисляется по квадратурной [https://ru.wikipedia.org/wiki/Формула_Симпсона формуле Симпсона] с числом узловых точек равным 4 и 8 на отрезке [a, b].		# Интеграл функции вычисляется по квадратурной [https://ru.wikipedia.org/wiki/Формула_Симпсона формуле Симпсона] с числом узловых точек равным 4 и 8 на отрезке <math>[a, b] </math>.
	# Вычисляется разность найденных значений		# Вычисляется разность найденных значений
	## Если разность интегралов меньше либо равна желаемой точности интегрирования ε - заканчиваем процедуру.		## Если разность интегралов меньше либо равна желаемой точности интегрирования ε - заканчиваем процедуру.
	## Если разность больше, то отрезок разбивается на два [a, (a + b~~) /~~ 2] и [(a + b~~) /~~ 2, b] и для каждого отрезка повторяется процедура 1, затем возвращается сумма полученных значений.		## Если разность больше, то отрезок разбивается на два : <math>[a, \tfrac{a + b} {2}]</math> и <math>[\tfrac{a + b} {2}, b]</math> и для каждого отрезка повторяется процедура 1, затем возвращается сумма полученных значений.
	Алгоритм имеет рекурсивную природу.		Алгоритм имеет рекурсивную природу.

Bvdmitri в 21:28, 13 ноября 2016

2016-11-13T21:28:19Z

← Предыдущая версия		Версия от 21:28, 13 ноября 2016
Строка 1:		Строка 1:
	~~Незаконченный вариант статьи~~		Основные авторы описания: [[Участник:bvdmitri\|Д.В.Багаев]]

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

Bvdmitri в 21:27, 13 ноября 2016

2016-11-13T21:27:02Z

@@ Строка 96: / Строка 96: @@
 ==== Реализация с помощью MPI для межпроцессорного взаимодействия и [https://www.threadingbuildingblocks.org Intel TBB]  для внутрипроцессорного взаимодействия ====
-[https://github.com/bvdmitri/aintegrate/blob/master/src/method/mpi_tbb/MPI_TBBMethod.cpp Исходный код]
+<source lang="c++">
 В данной реализации отрезок [a, b] делится на число доступных процессоров, каждый отрезок считается на своем процессоре, рекурсия заменяется на [https://www.threadingbuildingblocks.org/tutorial-intel-tbb-task-based-programming систему] задач библиотеки Intel MPI для более эффективного использования многоядерных процессоров.
@@ Строка 107: / Строка 163: @@
 === Тесты производительности ===
 ==== MPI + TBB ====
-[[file:Mpi_tbb_1.png|thumb|center|500px|Рисунок 1. Результаты масштабируемости для MPI + TBB реализации]]
+[[file:Mpi_tbb_1.png|thumb|center|500px|Рисунок 1. Результаты масштабируемости для первой функции]]
-[[file:Mpi_tbb_2.png|thumb|center|500px|Рисунок 2. Результаты масштабируемости для MPI + TBB реализации]]
+[[file:Mpi_tbb_2.png|thumb|center|500px|Рисунок 2. Результаты масштабируемости для второй функции]]

Pochtalionizm: /* Общее описание алгоритма */

2016-11-13T21:22:40Z

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

← Предыдущая версия		Версия от 21:22, 13 ноября 2016
Строка 5:		Строка 5:
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

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

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

Pochtalionizm: /* Входные данные */

2016-11-13T21:22:05Z

Входные данные

← Предыдущая версия		Версия от 21:22, 13 ноября 2016
Строка 24:		Строка 24:

	* Функция.		* Функция.
	* Отрезок ~~вида~~ [a, b].		* Отрезок интегрирования [a, b].
	* Желаемая точность интегрирования ε.		* Желаемая точность интегрирования ε.

Pochtalionizm: /* Математическое описание алгоритма */

2016-11-13T21:21:44Z

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

← Предыдущая версия		Версия от 21:21, 13 ноября 2016
Строка 15:		Строка 15:
	## Если разность интегралов меньше либо равна желаемой точности интегрирования ε - заканчиваем процедуру.		## Если разность интегралов меньше либо равна желаемой точности интегрирования ε - заканчиваем процедуру.
	## Если разность больше, то отрезок разбивается на два [a, (a + b) / 2] и [(a + b) / 2, b] и для каждого отрезка повторяется процедура 1, затем возвращается сумма полученных значений.		## Если разность больше, то отрезок разбивается на два [a, (a + b) / 2] и [(a + b) / 2, b] и для каждого отрезка повторяется процедура 1, затем возвращается сумма полученных значений.
			Алгоритм имеет рекурсивную природу.
	~~Из описания видно, что алгоритм~~ имеет рекурсивную природу.

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

Pochtalionizm: /* Математическое описание алгоритма */

2016-11-13T21:04:49Z

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

← Предыдущая версия		Версия от 21:04, 13 ноября 2016
Строка 11:		Строка 11:
	Формулы метода:		Формулы метода:

	# ~~Производится подсчет интеграла~~ функции квадратурной [https://ru.wikipedia.org/wiki/Формула_Симпсона ~~формулой~~ Симпсона] с числом узловых точек равным 4 и 8 на отрезке [a, b].		# Интеграл функции вычисляется по квадратурной [https://ru.wikipedia.org/wiki/Формула_Симпсона формуле Симпсона] с числом узловых точек равным 4 и 8 на отрезке [a, b].
	# ~~Считается~~ разность ~~посчитанных~~ значений		# Вычисляется разность найденных значений
	## Если разность ~~посчитанных~~ интегралов меньше либо равна желаемой точности интегрирования ε заканчиваем процедуру.		## Если разность интегралов меньше либо равна желаемой точности интегрирования ε - заканчиваем процедуру.
	## Если разность больше, то ~~происходит разбиение отрезка~~ на два [a, (a + b) / 2] и [(a + b) / 2, b] и для каждого отрезка повторяется процедура 1, затем возвращается сумма полученных значений.		## Если разность больше, то отрезок разбивается на два [a, (a + b) / 2] и [(a + b) / 2, b] и для каждого отрезка повторяется процедура 1, затем возвращается сумма полученных значений.

	Из описания видно, что алгоритм имеет рекурсивную природу.		Из описания видно, что алгоритм имеет рекурсивную природу.

Bvdmitri в 21:04, 13 ноября 2016

2016-11-13T21:04:19Z

← Предыдущая версия		Версия от 21:04, 13 ноября 2016
Строка 106:		Строка 106:

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

			=== Тесты производительности ===

			==== MPI + TBB ====

			[[file:Mpi_tbb_1.png\|thumb\|center\|500px\|Рисунок 1. Результаты масштабируемости для MPI + TBB реализации]]
			[[file:Mpi_tbb_2.png\|thumb\|center\|500px\|Рисунок 2. Результаты масштабируемости для MPI + TBB реализации]]