Главная > Методы обработки сигналов > Численные методы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 7. Оценка снизу погрешности численного интегрирования

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

Величина

называется погрешностью квадратуры, величина

— погрешностью квадратуры на классе функций F, величина

— оптимальной оценкой погрешности квадратур на классе F; квадратура (если такая существует), на которой эта нижняя грань достигается, называется оптимальной. Мы будем предполагать выполненным условие: существует некоторый куб , в котором .

Теорема. .

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

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

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

Для простоты выкладок будем проводить построение для случая, когда — единичный куб . Положим и разобьем куб на прямоугольных параллелепипедов . Пусть (см. рис. 5.7.1)

Из определения следует, что , поэтому

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

Во всех остальных параллелипипедах положим .

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

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

Рис. 5.7.1

Оценим снизу значение Воспользовавшись неравенством , после замены переменных получим цепочку соотношений

здесь

Каждая точка может находиться внутри только одного из параллелепипедов . Следовательно, по крайней мере в параллелепипедах функция отлична от тождественного нуля и определяется равенством (2). Согласно (1) имеем , поэтому таких параллелепипедов не менее чем . С учетом (3) получаем оценку

где .

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

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

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

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

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

Здесь — точки области — числа. При приближенном вычислении конкретного интеграла последовательно вычисляются величины

и затем полагают

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

Так же, как в случае квадратурных формул, можно определить погрешность метода при вычислении данного интеграла

погрешность метода на классе

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

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

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

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

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

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

Из сказанного выше вытекает актуальность решения следующих задач.

Задача 1. Как правильно описать класс реально встречающихся функций?

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

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

и численное интегрирование по некоторым из переменных производится посредством одномерных алгоритмов интегрирования с автоматическим выбором шага.

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

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

Заменой переменных

интеграл превращается в интеграл по кубу

В основу метода положены кубатурные формулы

Для вычисления интеграла вычисляются и и проверятся условие

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

I. :

где

Формула точна для всех многочленов степени не больше 5. Формула точна для всех многочленов степени не больше 7.

II. :

Формулы и точны для всех многочленов степени не больше 5. Формула точна для всех многочленов степени не больше 7.

<< Предыдущий параграф Следующий параграф >>
Оглавление