|
|
| (не показаны 2 промежуточные версии этого же участника) |
| Строка 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>
| |
| − |
| |
| − | === Вычислительное ядро алгоритма ===
| |
| − |
| |
| − | === Макроструктура алгоритма ===
| |
| − |
| |
| − | === Последовательная сложность алгоритма ===
| |
| − |
| |
| − | === Информационный граф ===
| |
| − |
| |
| − | === Ресурс параллелизма алгоритма ===
| |
| − |
| |
| − | === Входные и выходные данные алгоритма ===
| |
| − |
| |
| − | === Свойства алгоритма ===
| |
| − |
| |
| − | == Программная реализация алгоритма ==
| |
| − |
| |
| − | === Особенности реализации последовательного алгоритма ===
| |
| − |
| |
| − | === Локальность данных и вычислений ===
| |
| − |
| |
| − | === Возможные способы и особенности параллельной реализации алгоритма ===
| |
| − |
| |
| − | === Масштабируемость алгоритма и его реализации ===
| |
| − |
| |
| − | === Динамические характеристики и эффективность реализации алгоритма ===
| |
| − |
| |
| − | === Выводы для классов архитектур ===
| |
| − |
| |
| − | === Существующие реализации алгоритма ===
| |
| − |
| |
| − | == Литература ==
| |
