Документ взят из кэша поисковой машины. Адрес оригинального документа : http://mph.cs.msu.su/Home/Opus/a68.doc Дата изменения: Tue Apr 6 14:57:58 2010 Дата индексирования: Sat Apr 9 23:39:35 2016 Кодировка: koi8-r

А. Н. Тихонов, С. С. Гайсарян

0 выборе оптимальных сеток при приближенном вычислении квадратур


1. В настоящей работе рассматривается проблема нахождения оптимальных
приближенных методов вычисления квадратуры
[pic].
Приближенный метод включает в себя некоторую сетку [pic], которая
подразделяет отрезок [a,b] на частичные отрезки[pic] длины [pic] [pic] и
квадратурную формулу
[pic] (1)
степени s, т.е. такую, что
[pic]. (2)
Применение приближенного метода дает приближенное значение для [pic],
равное
[pic].
Оптимальным приближенным методом назовем метод, для которого погрешность

[pic]
минимальна при фиксированном числе узлов N и фиксированной функции [pic] из
некоторого класса, который будет определен ниже.
При такой постановке задачи наиболее существенно то, что ищется
приближенный метод, который был бы оптимальным для заданной подынтегральной
функции[pic]. Задача построения оптимальных квадратур, рассматривавшаяся в
работах [1,2] и др., ставилась по-другому: в этих работах строились
квадратурные формулы, оптимальные для всех функций из заданного класса.
В дальнейшем формула (1) будет предполагаться фиксированной, так что
выбор оптимального приближенного метода сведется к выбору оптимальной
сетки, т. е. последовательности узлов [pic], которая доставляет минимум
функции [pic] или, что то же самое, функции
[pic] (3)
Итак, для построения оптимального приближенного метода нужно найти [pic]
в замкнутом ( N-1)-мерном тетраэдре[pic]. Для непрерывных [pic] в силу
теоремы Вейерштрасса [pic] всегда достигается и, следовательно, оптимальная
сетка всегда существует.
Следующий тривиальный пример показывает, что оптимальная сетка не всегда
единственна. В самом деле, пусть [pic] вычисляется по формуле трапеций

[pic], (4)

а N = 5. Ясно, что [pic] = 0, причем он достигается при [pic], при[pic] и
т.д.
В п.2 будет показано, что если [pic] принадлежит классу [pic] такому,
что [pic] и [pic] сохраняет знак на [pic], то существует единственная
оптимальная сетка (теорема 2), а также будет выведено разностное уравнение,
связывающее последовательные узлы оптимальной сетки (теорема 1).
В п. 3 устанавливается, что оптимальная сетка, построенная в п. 2, может
быть приближена сетками специального вида (теоремы 3 и 4), введенными и
изученными в [3]. В п.4 обсуждается возможность использования оптимальные
сеток для приближенного вычисления квадратур с заданной точностью [pic] и
обосновывается применимость алгоритма, предложенного в [3].

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

Лемма 1. Пусть коэффициенты[pic], квадратурной формулы (1) удовлетворяют
условиям (2) и пусть [pic]. Тогда остаточный член [pic] формулы (1)
допускает представление в виде
[pic], (5)

где
[pic]
[pic]
[pic].
Функция [pic], определенная при [pic], непрерывна и сохраняет знак,
причем [pic] монотонно убывает по [pic] и монотонно возрастает по [pic].
3амечание. Если (1) - формула Ньютона - Котеса (т. е. [pic]), то
аналогичная лемма доказана в [4].

Доказательство. По определению,
[pic]. (6)
Заменив здесь [pic] и [pic] [pic] разложениями
[pic],
[pic]
[pic], после необходимых упрощений (с учетом условий
(2)) получим формулу (5).
В [3] было установлено, что
[pic],
откуда следует, что если [pic] на [pic], то[pic]. Предположим, что[pic] не
сохраняет знака на [pic]. Тогда найдется такая непрерывная [pic], не
обращающаяся в нуль за [pic], что [pic]. Положив [pic] и восстановив [pic],
получим противоречие ([pic], хотя[pic] на [pic]), которое показывает, что
[pic] сохраняет знак на [pic].
Сдвинув начало координат в точку [pic], переведем [pic] в [pic], где
[pic],
[pic]
Имеем
[pic],
[pic]
Следовательно, если [pic], то [pic], а [pic]. Лемма доказана.

Лемма 2. Если [pic] [pic]достигается во внутренней точке тетраэдра
[pic].

Доказательство. Пусть [pic] - некоторая внутренняя точка [pic] и пусть
[pic] - проекция [pic] на грань [pic](сетки, задаваемые точками [pic]и
[pic], обозначим, соответственно, через [pic] и [pic] сетка [pic]
отличается от сетки [pic] тем, что у нее узлы [pic] и [pic] слились, так
что отрезки [pic] и [pic] заменились одним отрезком [pic]).
Для доказательства леммы достаточно установить, что
[pic][pic]
или, в силу (3), что
[pic].
Если [pic], то все [pic] имеют одинаковый знак, так что
[pic],
где
[pic].
Имеем *
[pic] (7)
[pic]
[pic]
в силу леммы 1 ( так как [pic]). Лемма доказана.
Из леммы 2 следует, что для [pic] необходимое условие минимума
[pic]имеет вид
[pic] (8)
Подставив в (8) выражение (3) для [pic] и выполнив дифференцирование,
получим

[pic] (9)

Для уравнения (9) удобно следующее сокращенное обозначение
[pic]. (9()
Таким образом, нами установлена

Теорема 1. Если [pic] , то три любых последовательных узла [pic]
оптимальной сетки удовлетворяют нелинейному разностному уравнению второго
порядка (9).

Замечание. Если в качестве формулы (1) взять формулу трапеций (4), то
уравнение (9) примет вид
[pic]
который имеет простой геометрический смысл.

Теорема 2. Если [pic], то существует единственная сетка [pic], узлы
[pic] которой удовлетворяют разностному уравнению (9).

Доказательство. Нам необходимо установить существование и единственность
решения разностной краевой задачи
[pic]Переписав уравнение (9) в виде
[pic]
и заменив в последнем соотношении [pic], [pic], разложениями по формуле
Тейлора с центром в точке [pic], получим после упрощений ( в обозначениях
леммы 1)
[pic]
или, учитывая, что [pic],
[pic] (10)
Зафиксируем [pic]и [pic]. Тогда в силу леммы 1 в левой части (10) стоит
монотонно возрастающая функция [pic], обращающаяся в нуль при [pic].
Постоянная, стоящая в правой части (10), положительна и пропорциональна
[pic]. Следовательно, если [pic]достаточно мало, то (10) определяет
единственное значение [pic], причем [pic] будет тоже мало. Следовательно,
задавшись достаточно малым [pic], получим [pic] с ростом [pic]. Следовательно, найдется такое [pic], при котором [pic]=b,
что в доказывает теорему.
Из теорем 1 и 2 следует, что для [pic] уравнение (9) определяет
единственную сетку, которая доставляет минимум функции [pic] (то, что
именно минимум, следует из вида [pic] ). Эту сетку мы будем в дальнейшем
называть абсолютно оптимальной для функции[pic] и формулы (1).

3. Рассмотрим сетки специального вида, изучавшиеся в [3].
Пусть [pic] - непрерывно дифференцируемая положительная функция,
удовлетворяющая условию
[pic]
и пусть [pic] - некоторое действительное число.
Сетку[pic], узлы которой задаются соотношениями
[pic]
назовем простейшей сеткой, а сетку [pic], у которой
[pic]
назовем усложненной сеткой с параметром [pic] и функцией [pic]
распределения шагов .
В качестве оценочной функции для [pic]возьмем главный член
асимптотического разложения [pic] по степеням [pic] и назовем оптимальной
сетку, доставляющую минимум этому главному члену при фиксированном [pic].
Тогда, как показано в [3], оптимальная простейшая и оптимальная усложненная
сетки будут определяться функцией распределения шагов
[pic].
Теорема 3. Пусть [pic]- узлы абсолютно оптимальной сетки [pic], а
[pic] - узлы оптимальной усложненной сетки [pic] с параметром [pic]. Тогда
имеют место оценки
[pic]
Доказательство. В [3] доказано, что при [pic]оптимальная усложненная
сетка содержит N+1 узел [pic], причем эти узлы удовлетворяют уравнению

[pic] (11)
и граничным условиям [pic], где [pic].
По теореме о среднем из (10) (после сокращения на общий множитель)
следует
[pic],
[pic], [pic], откуда имеем
[pic] (12)
Введем обозначения: [pic] (разность вперед), [pic] (разность назад),
[pic][pic].
Тогда (11) и (12) запишутся в виде
[pic] (11()
[pic] . (12()
Пусть [pic] . Вычитая (11() из (12() , получим для [pic]
[pic] (13)
где [pic] лежит между [pic]и [pic], а [pic]- между [pic] и [pic]. Легко
видеть, что [pic], так что в силу [4] задача (13) имеет разностную функцию
Грина с ограниченной первой разностью. Следовательно, [pic].
Легко видеть, что
[pic],
причем [pic] (это следует из (3), оценки для [pic], полученной в [3], и
оценки для [pic]). Следовательно, в силу (3)
[pic].
Теорема доказана.
Аналогично теореме 3 доказывается и
Теорема 4. Для узлов [pic]оптимальной простейшей сетки [pic] с
параметром [pic]и для погрешности [pic] имеют место оценки
[pic]
где С - постоянная, введенная в [3].

Из теорем 3 и 4 следует, что оптимальную простейшую и оптимальную
усложненную сетки можно рассматривать как первое и второе приближение к
абсолютно оптимальной.

4. Рассмотрим задачу о приближенном вычислении квадратуры [pic] с
заданной точностью [pic] в предположении, что [pic].
Пусть [pic] и [pic] - абсолютно оптимальные сетки, для которых
выполняется условие
[pic]. (14)
Тогда сетка [pic] будет обеспечивать достижение точности [pic] и содержать
наименьшее возможное число узлов.
Легко видеть, что определение N из условия (14) довольно затруднительно.
С другой стороны, из теорем 3 и 4 следует, что если вместо абсолютно
оптимальной сетки использовать оптимальную простейшую сетку или оптимальную
усложненную сетку с соответствующим параметром [pic] (выбор параметра [pic]
описан в [3] ), то абсолютно оптимальная сетка [pic], где [pic], если
используется оптимальная усложненная сетка, и [pic], если используется
оптимальная простейшая сетка, будет удовлетворять условию (14). Что
касается точности [pic], то она будет в этом случае удовлетворяться
асимптотически с точностью до величин [pic].
В [3] показано, что при этом константа при [pic] в случае оптимальной
усложненной сетки намного меньше, чем в случае оптимальной простейшей
сетки. Таким образом, алгоритм, предложенный в [3], близок к оптимальному.

Литература

1. С. М. Никольский. Квадратурные формулы. М., Физматгиз, 1958.
2. Т. А. Шайдаева. Наиболее точные квадратурные формулы для некоторых
классов функций. Тр. Матем. ин-та АН СССР, 1959, 53, 313-314.
3. С. С. Гайсарян. Об одном оптимальном алгоритме приближенного вычисления
квадратур. Ж. вычисл. матем. и матем. физ., 1969, 9, настоящий выпуск.
4. А.Н. Тихонов, А. А. Самарский. Об однородных разностных схемах. Ж.
вычисл. матем. и матем. физ., 1961,1, ? 1, 5-63.
5. В. И. Крылов. Приближенное вычисление интегралов. М., «Наука», 1967.


* Для удобства принято обозначение [pic]; [pic]- гладкая функция, так как
[pic] гладкая и сохраняет знак.