§11. Оптимизация распределения узлов квадратурной формулы

Развитие методов численного интегрирования могло бы пойти по пути создания оптимальных методов на различных классах и создания программ на основе этих методов. Здесь и далее — класс функций с кусочно-непрерывной производной, удовлетворяющей условию

Вскоре после начала рассмотрения задач оптимизации методов стало ясно, что уже известные на этих классах методы с оценкой погрешности (8.7) недалеки от оптимальных. Как увидим в § 7 гл. 5, за счет оптимизации квадратурной формулы оценка погрешности (8.7) на рассматриваемых классах не может быть улучшена по порядку. При этом также стало ясно, что некоторые методы, практически совпадающие с методами Эйлера и Грегори (см. § 13), являются асимптотически оптимальными по оценке главного члена погрешности. Имеется в виду следующее. Для этих методов на соответствующих классах функций были получены оценки погрешности

в то время как для оптимальных на этих классах методов оценка погрешности имеет вид

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

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

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

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

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

Пусть вычисляется интеграл

и подынтегральная функция удовлетворяет условиям на отрезках , где . Для вычисления интегралов

применим составную формулу трапеций с равными отрезками разбиения длины , где :

Из результатов § 3 следует, что остаточный член оценивается величиной . Тогда суммарная погрешность при замене суммой не превзойдет величины

Поставим задачу: при заданном числе отрезков разбиения распорядиться выбором величин так, чтобы суммарная оценка погрешности Ф была минимальной.

Найдем минимум Ф при условии , не предполагая пока, что величины целые. Приравнивая нулю производные функции Лагранжа , получаем систему уравнений

Отсюда

Из условия получим следующее уравнение относительно :

Из этого уравнения определяем и затем из (1) находим . Поскольку должны быть целыми, то возьмем, например,

Очевидно, что

Мы не нашли настоящего минимума Ф по множеству всевозможных целых , удовлетворяющих условию , однако дальнейшее уточнение вряд ли разумно.

Обычно практический интерес представляет другая вариационная задача: найти минимальное значение , при котором оценка погрешности Ф не превосходит заданного . Поскольку Ф монотонно убывает с ростом величины , достаточно ограничиться случаем . Возьмем функцию Лагранжа в виде

Приравнивая нулю ее производные по , получим те же уравнения (1); подставляя значение — в уравнение , получим

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

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

По этой таблице составляется таблица разделенных разностей . Из рассмотрения этой таблицы делается вывод о наиболее целесообразном разбиении отрезка на части и значениях , соответствующих этим частям. Затем, в соответствии с (1), выбираются и производится интегрирование.

Большинство алгоритмов реально работающих стандартных программ базируется не на таком непосредственном использовании полученных соотношений, а на одном качественном выводе, являющемся следствием (1). Для этого перепишем равенство (1) в виде

Левая часть этого выражения равна оценке погрешности по элементарному отрезку интегрирования длины , на которые разбит отрезок . Таким образом, это соотношение означает, чти при оптимальном распределении узлов интегрирования оценки погрешностей, приходящиеся на элементарные отрезки интегрирования, должны, быть одинаковыми.

Для получения этого вывода достаточно было ограничиться случаем . Это обстоятельство подчеркивает общее свойство качественных характеристик методов решения задач (не обязательно математических): для их получения достаточно ограничиться рассмотрением простейших моделей, учитывающих основные стороны явления.

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

Рассмотрим еще одну, близкую постановку задачи оптимизации распределения узлов интегрирования. Чтобы не утомлять читателя второстепенными деталями, мы не будем проводить подробных оценок членов высшего порядка в оценке погрешности.

Пусть отрезок интегрирования [0, 1] разбит на части и интеграл по каждой части вычисляется по формуле трапеций

Тогда интеграл по всему отрезку [0, 1] вычисляется по формуле

с оценкой остаточного члена

Пусть известно, что на [0, 1], где непрерывна, и пусть в качестве взяты значения непрерывно дифференцируемой функции , удовлетворяющей условиям . Поскольку

то

Из этих соотношений получаем

Подставляя последние соотношения в (3), имеем

Выражение в фигурных скобках является квадратурной суммой Римана для интеграла

от непрерывной функции. Следовательно,

Рассмотрим задачу минимизации первого, главного члена выражения (4). Для удобства решения уравнения Эйлера примем за независимую переменную функцию . Тогда коэффициент при в главном члене погрешности запишется в виде

Уравнение Эйлера для функции, минимизирующей функционал

имеет вид

В рассматриваемом случае , поэтому из (5) имеем . Подставляя конкретное значение функции G, получим

или

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

Из соотношения (6) можно сделать тот же вывод о равенстве оценок погрешностей на элементарных отрезках интегрирования при оптимальном распределении узлов. В самом деле, умножим (6) на , положим и заменим и соответственно эквивалентными величинами результате получим

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