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

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

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

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

---

Пусть требуется вычислить определённый интеграл [math]I = \int_a^b{f(x)dx}[/math] от непрерывной функции [math]f(x)[/math]. Если может быть найдена первообразная [math]F(x)[/math] подынтегральной функции, то по формуле Ньютона-Лейбница:

[math]\int_a^b{f(x)dx} = F(b) - F(a). [/math]

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

Приближённые методы вычисления определённого интеграла в большинстве случаев основаны на том, что определённый интеграл численно равен площади криволинейной трапеции, ограниченной кривой [math] y =f(x)[/math], сегментом [math] \left[ a,b \right] [/math] оси [math]Ox[/math] и вертикальными прямыми [math]x = a[/math] и [math]x = b[/math].

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

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] - количество узлов, образующих две разные сетки.

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

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