На мой взгляд, оптимальный алгоритм такой.
Считаем для начала интеграл по промежутку
, где
, скажем.
Потом добавляем к нему интеграл по
.
Потом -- по
.
Потом -- по
, и т.д.
Контролируя добавки по правилу Рунге. Т.е. до тех пор, пока добавка превышает требуемую точность -- до тех пор и считаем.
Прелесть подхода в том, что на каждом шаге условия применения квадратурной формулы благоприятны. В том смысле, что относительные перепады самой подынтегральной функции (а также максимумы всех мыслимых производных) ведут себя регулярно. В типичных ситуациях. Поэтому и требуемое к-во шагов численного интегрирования на каждом внешнем шаге -- одного порядка.
Правда. Мы заранее не знаем, сколько таких (внешних) шагов придётся сделать. Ну что ж. Сперва грубо оценим необходимое к-во шагов (вычисляя интеграл на каждом шаге с относительной точностью, ну допустим,
). Пусть потребуется
таких шагов. А потом пересчитываем всё заново, вычисляя численно интеграл на каждом шаге с точностью
и до тех пор, пока оценка правилом Рунге не даст результат не хуже, чем
.
Где-то типа так.
Накладные расходы на предварительную прикидку -- будут малы по сравнению со временем уточняющего счёта.