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

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

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

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

---

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

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

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

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

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

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

---

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

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

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

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

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

[math]\displaystyle{ \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]\displaystyle{ I }[/math] найденным с точностью [math]\displaystyle{ \epsilon }[/math], если выполнено условие:

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

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

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