Уровень алгоритма

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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 14: Строка 14:
  
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===
 
+
----
 
Будем рассматривать проблему вычисления значения определенного интеграла с некоторой заданной точностью <math> \epsilon </math>:
 
Будем рассматривать проблему вычисления значения определенного интеграла с некоторой заданной точностью <math> \epsilon </math>:
  

Версия 14:01, 15 октября 2016


Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки
Последовательный алгоритм
Последовательная сложность [math]-[/math]
Объём входных данных [math]-[/math]
Объём выходных данных [math]-[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы [math]-[/math]
Ширина ярусно-параллельной формы [math]-[/math]


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

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


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


Будем рассматривать проблему вычисления значения определенного интеграла с некоторой заданной точностью [math] \epsilon [/math]:

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

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

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

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

[math] \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f_i} + \frac{f(x_n)}{2} \right)[/math]

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

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

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

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

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

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

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

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

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

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

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

2.7 Существующие реализации алгоритма