|
|
| Строка 1: |
Строка 1: |
| {{algorithm
| |
| | name = Адаптивное интегрирование
| |
| | serial_complexity =
| |
| | input_data =
| |
| | output_data =
| |
| }}
| |
|
| |
|
| Автор: [[Участник:Valkyrie|В.А. Мастинен]]
| |
|
| |
| == Свойства и структура алгоритма ==
| |
|
| |
| === Общее описание алгоритма ===
| |
|
| |
| Адаптивное интегрирование - это метод численного интегрирования, в котором интеграл функции <math>f(x)</math> аппроксимируется с использованием статических [http://algowiki-project.org/ru/Квадратурные_формулы квадратурных формул ]<ref>Самарский А. А., Гулин А. В. Численные методы: Учеб. пособие для вузов. — М.: Наука. Гл. ред. физ-мат. лит., 1989. — 432 с.</ref> на адаптивно уточненных подынтервалах области интегрирования. Как правило, адаптивные алгоритмы столь же эффективны, как и традиционные алгоритмы для «достаточно гладких» подынтегральных функций, но также неэффективны для «плохих» подынтегральных функций, на которых традиционные алгоритмы терпят неудачу.
| |
|
| |
| Из анализа погрешностей методов численного интегрирования следует, что точность получаемых результатов зависит как от характера изменения подынтегральной функции, так и от шага интегрирования. При этом ясно, что для достижения сравнимой точности при интегрировании слабо меняющейся функции шаг можно выбирать большим, чем при интегрировании резко меняющихся функций.
| |
|
| |
| На практике нередко встречаются случаи, когда подынтегральная функция меняется по-разному на отдельных участках отрезка интегрирования. Это обстоятельство требует такой организации численного алгоритма, при котором он автоматически приспосабливался к характеру изменения функции -вводил разные значения шага интегрирования на отдельных участках отрезка интегрирования. Это позволяет уменьшить машинное время без потери точности результатов расчета. Такой подход используется обычно при задании подынтегральной функции <math>f(x)</math> в виде формулы, а не в табличном виде.
| |
|
| |
| === Математическое описание алгоритма ===
| |
|
| |
| Исходные данные : интегрируемая функция <math>f(x)</math>, определенная на отрезке <math>[a,b]</math>, допустимая погрешность интегрирования <math>\varepsilon</math>
| |
|
| |
| Вычисляемые данные : приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>
| |
|
| |
| Пусть <math>Q(a,b)</math> - квадратурная формула, аппроксимирующая значение интеграла на отрезке <math>[a,b]</math>
| |
|
| |
| Оценим <math>\tau \approx |Q(a,b) - \int\limits_a^b f(x)\,dx|</math>
| |
|
| |
| Если <math>\tau > \varepsilon</math>, поделим отрезок <math>[a,b]</math> пополам и применим этот же алгоритм к каждому из отрезков <math>[a,\frac{a+b}2]</math> и <math>[\frac{a+b}2,b]</math>, задав погрешность интегрирования на каждом из отрезков <math>\frac{\varepsilon}2</math>
| |
|
| |
| Если в качестве квадратурной формулы выбрать формулу Симпсона, то <math>\tau</math> можно положить равным <math>\frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math><ref> Lyness J. N. Notes on the adaptive Simpson quadrature routine //Journal of the ACM (JACM). – 1969. – Т. 16. – №. 3. – С. 483-495.</ref>
| |
|
| |
| === Вычислительное ядро алгоритма ===
| |
|
| |
| === Макроструктура алгоритма ===
| |
|
| |
| === Последовательная сложность алгоритма ===
| |
|
| |
| === Информационный граф ===
| |
|
| |
| === Ресурс параллелизма алгоритма ===
| |
|
| |
| === Входные и выходные данные алгоритма ===
| |
|
| |
| === Свойства алгоритма ===
| |
|
| |
| == Программная реализация алгоритма ==
| |
|
| |
| === Особенности реализации последовательного алгоритма ===
| |
|
| |
| === Локальность данных и вычислений ===
| |
|
| |
| === Возможные способы и особенности параллельной реализации алгоритма ===
| |
|
| |
| === Масштабируемость алгоритма и его реализации ===
| |
|
| |
| === Динамические характеристики и эффективность реализации алгоритма ===
| |
|
| |
| === Выводы для классов архитектур ===
| |
|
| |
| === Существующие реализации алгоритма ===
| |
|
| |
| == Литература ==
| |