Один из достаточно сложных, но весьма важных этапов решения любой практической задачи связан с проблемой выбора алгоритма из нескольких известных. Очень часто скорость вычислений и точность решения задачи зависят от управляющих параметров алгоритма, задаваемых пользователем. Однако способ выбора оптимальных значений этих параметров, которые соответствовали бы индивидуальным особенностям решаемой задачи, бывает трудно формализовать или он вообще неизвестен. Поэтому особую ценность представляют алгоритмы, обладающие свойствами адаптивности, то есть умеющие учитывать индивидуальные характеристики конкретной задачи из области определения данного алгоритма. Обычно подобные алгоритмы достаточно сложны. Однако сочетание рекурсии и известных простых схем интегрирования (формула прямоугольников, трапеций, Симпсона и т. п.) позволяет построить примеры простых и изящных адаптивных алгоритмов интегрирования. Проводя численный эксперимент, можно убедиться в преимуществах таких алгоритмов перед классическими схемами как в скорости, так и в точности вычислений.

адача 45. Пусть f(x) - интегрируемая по Риману на отрезке [a, b] (a<b) функция вещественной переменной x. Составить программу-функцию, реализующую адаптивный рекурсивный алгоритм приближенного вычисления определенного интеграла от f(x) на [a, b], базирующийся на формуле Симпсона.

Решение. Для функций f(x), интегрируемых на отрезке [a, b], приближенное вычисление определенных интегралов по формуле Симпсона при количестве интервалов разбиения, равном n, можно реализовать по программе:

В процессе вычисления значения функции simpson() количество интервалов разбиения n и соответственно шаг интегрирования h=(b-a)/n остаются неизменными. Однако подобная жесткость, как правило, неприемлема. Обычно вычисления по формуле Симпсона признаются удовлетворительными, если разность приближенных значений интеграла, полученных при некоторых натуральных n=k и n=2×k, становится меньше заранее заданного числа e>0. Но этот подход никак не учитывает свойств подынтегральной функции f(x) на различных участках отрезка [a, b]. Вполне возможно, что если бы мы решали задачу отдельно для промежутков [a, r] и [r, b] (rÎ(a, b)), то требуемые значения n на них могли оказаться существенно различными. А это привело бы к уменьшению количества вычисляемых значений f(x) и общего времени вычислений.

В приведенной ниже функции adapt() реализован рекурсивный алгоритм последовательной дихотомии исходного отрезка с отдельными вычислениями интеграла на каждом из получаемых при этом промежутков:

Параметр k в adapt() задает начальное количество интервалов дробления в методе Симпсона. При фиксированных значениях a, b и k терминальная ветвь рекурсии при выполнении условия

| simpson(F, a, b, k, e) - simpson(F, a, b, 2×k, e) | £ e

возвращает значение y = simpson(F, a, b, 2×k, e). Рабочая ветвь рекурсии обеспечивает независимое решение исходной задачи на отдельных промежутках [a, (a+b)/2] и [(a+b)/2, b]. Это позволяет адаптироваться к свойствам функции F(x) на каждом из этих участков и заканчивать вычисления на них при разных значениях k.

 Контрольный пример:

Шесть цифр после десятичной точки в приведенном ниже вычислении являются верными:

adapt(F, 0, 1, 2, 10^-6) = 0.386554847043226.

Замечание. Поскольку при последовательной дихотомии ошибки вычисления интеграла на отдельных промежутках, вообще говоря, могут суммироваться, то в правой части функции adapt() аргументы e целесообразно заменить на e/2.