Содержание к диссертации
Введение
ГЛАВА I. Оценки погрешности приближения функций полиномиальными операторами 8
1. Постановка задачи и формулировка результатов 8
2. Асимптотически наилучшее приближение непрерывных функций многих переменных операторами Бернштейна 17
3. Неравномерная оценка погрешности приближения функций многих переменных операторами Бернштейна 32
4. Оценки погрешности приближения другими операторами 35
ГЛАВА II. Анализ сложности некоторых алгоритмов 44
1. Постановка задачи и формулировка результатов 44
2. Сложности одномерных алгоритмов 51
3. Сложности многомерных алгоритмов 59
ГЛАВА III. Некоторые методы моделирования распределений и анализ их сложности 71
ГЛАВА ІV. Асимптотические оценки трудоемкостей способов "выделение главной части (ВГЧ) и "существенная выборка" (СВ) 82
1. Постановка задачи и формулировка результатов 82
2. Оценка трудоемкости способа ВГЧ 87
3. Оценка трудоемкости способа СВ 92
4. Одна модификация способа СВ 94
Численные эксперименты 102
Заключение 113
Литература 116
Приложения 121
- Асимптотически наилучшее приближение непрерывных функций многих переменных операторами Бернштейна
- Неравномерная оценка погрешности приближения функций многих переменных операторами Бернштейна
- Некоторые методы моделирования распределений и анализ их сложности
- Оценка трудоемкости способа ВГЧ
Введение к работе
В связи с появившимися широкими возможностями применения ЭВМ в вычислительной практике за последние 20-30 лет произошло формирование и бурное развитие теории приближенного интегрирования. В этой области вычислительной математики нашли свои плодотворные применения методы функционального анализа и теории вероятностей, алгебры и теории чисел, геометрии и теории дифференциальных уравнений.
Довольно плодотворным оказалось применение вероятностно-статистических методов (методы Монте-Карло). Простейший
вариант этого метода дает кубатурную формулу вида:
JlW*X*fe,/V"''j.
л/
с/'
где л - независимые, равномерно-распределенные в единичном гиперкубе SL , точки. Удобство этого метода заключается в том, что в приведенной формуле можно брать достаточно большие N , т.к. все точки X вычисляются по единому алгоритму, а порядок сходимости (по вероятности) не зависит от размерности (кратности интеграла) и равен /У~"2* для функций f(X)L Формулам такого рода посвящены работы Н.С.Бахвалова, С.М.Ермакова, Й.М.Соболя, Н.Н.Ченцова и других.
Слабой стороной этого метода является сравнительно медленная сходимость, и гладкость функции при этом не способствует улучшению сходимости.
Но, существует несколько способов интегрирования,
называемые способами понижения дисперсии, которые оправдывают применение методов Монте-Карло наряду с другими куба-турными формулами с лучшей сходимостью. 5 частности, чаще других используются следующие способы:
выделение главной части (ВГЧ);
существенная выборка (СВ);
понижение порядка интегрирования;
расслоенная выборка;
случайные квадратурные формулы и др. Применение какого-либо способа понижения дисперсии
диктуется условиями задачи. Наиболее универсальными являются способы ВГЧ и СВ.
Критерием качества метода Монте-Карло является величина, называемая трудоемкостью применяемого метода и выражаемая формулой
где t - время ЭВМ, затрачиваемое в среднем для получения одного значения Щ ; J)& - выборочная диспресия статистической оценки искомого решения (см. напр. ІІ2, с. 8 J ).
Вопросы, связанные с исследованием асимптотического поведения трудоемкости - наиболее естественного критерия качества методов Монте-Карло - являются актуальными и активно изучаются советскими и зарубежными учеными. Важность исследований в этой области обусловлено не только внутренними потребностями теории методов Монте-Карло, все более расширяющейся сферой их приложений к задачам прикладной математики,
физики, химии, биологии и экономики, но и обоснованием кон-курентно-способности этих методов по отношению к другим детерминированным численным методам.
Настоящая диссертация, состоящая из четырех глав, посвящена исследованию трудоемкостей способов ВГЧ и СВ.
В обоих способах, как правило, применяются некоторые аппроксимирующие аппараты. Например, в 35 І в качестве такого аппарата были применены полиномиальные операторы Берн-штейна. Известно 1201 , что последовательность операторов Бернштейна равномерно сходится к аппроксимируемой функции
^ в каждой точке X непрерывности / Кроме того, если / имеет непрерывную частную производную порядка /С
в точке а , то соответствующая частная производная по-
v(oJ линома Бернштейна в точке Л также сходится к значению
, которые обладают анало-), перечисленными выше для
этой производной. Таким образом, операторы Бернштейна достаточно хорошо учитывают особенности поведения функции / , Наряду с операторами Бернштейна мы будем применять полиномиальные операторы Хсу 30 гичными свойствами (см. [ЗО, 2* операторов Бернштейна. Кроме того, мы применяем аппроксимирующие аппараты вида кусочно-постоянной функции и линейного интерполяционного сплайна. Поэтому, тут возникают задачи, связанные с оценкой погрешности приближения этими операторами, оценкой сложности алгоритмов вычисления значения этих операторов в заданной точке и моделированием плотностей, имеющих структуру рассматриваемых операторов.
Первая глава посвящена исследованию различных оценок погрешности приближения полиномиальными операторами, где,
в частности, обобщены некоторые известные оценки на случай функций многих независимых переменных, а также, получено асимптотически наилучшее приближение функций многих переменных операторами Бернштейна.
Вторая глава содержит результаты, относящиеся к оценкам сложностей алгоритмов вычисления значения полиномиальных операторов. Здесь, в частности, построен алгоритм, вычисляющий значение оператора Бернштейна, имеющий асимптотически оптимальную сложность, доказана теорема о несуществовании алгоритма, вычисляющего значения оператора Хсу с асимптотически оптимальной сложностью, а также обсуждены некоторые приемы, приводящие к уменьшению сложности алгоритмов,
В третьей главе изложены некоторые известные методы моделирования случайных величин и их многомерные аналоги. Кроме того, исследованы сложности алгоритмов двух методов моделирования случайных векторов, а именно: стандартного метода моделирования дискретной случайной величины и метода суперпозиций.
Первые три параграфа четвертой главы содержат результаты, касающиеся оценок трудоемкостей обоих способов понижения дисперсии. Четвертый параграф носит самостоятельный характер и посвящен одному частному случаю, предложенного в 27 ] способа интегрирования.
В заключении перечислены основные положения, выводимые на защиту.
Приложения содержат фортран-программы, составленные
для реализации способов ВГЧ и СВ на ЭВМ, а также результатов численных экспериментов.
Результаты диссертации докладывались на всесоюзном семинаре-совещании по теории кубатурных формул и смежным вопросам (г. Бухара, 1983 г.), на семинарах кафедры статистического моделирования ЛГУ им. А.А.Жданова (г.Ленинград, 1982 г., 1983 г.), на семинарах отдела статистического моделирования ВЦ СО АН СССР (г. Новосибирск, 1980 г., 1984 г.), на семинаре отдела прикладных задач Института математики и механики Уральского филиала АН СССР (г.Свердловск, 1984 г.), а также на научных конференциях ТашГУ им. В.И.Ленина (г.Ташкент, 1978-1983 г.г.).
Автор считает своим приятным долгом выразить благодарность своему научному руководителю, профессору Азларову Т.А. за постоянное внимание во время работы над диссертацией.
Асимптотически наилучшее приближение непрерывных функций многих переменных операторами Бернштейна
При исследовании вычислительных алгоритмов, как правило, выделяется некоторая совокупность операций, называемых базисными, относительно которых проводится анализ этих алгоритмов. В качестве базисных операций мы возьмем совокупность из четырех арифметических действий, операций отношения и операции выделения целой части вещественного числа. Предположим, что каждая операция имеет единичную сложность.
Пусть задача М решается с помощью множества алгоритмов Л Величину (/J (А) , равную числу базисных операций, необходимых для решения задачи V алгоритмом А еЛ назовем сложностью алгоритма Ik
В предыдущей главе были затронуты вопросы аппроксимации полиномиальными операторами, отображающими заданное пространство функции /к в его подпространство полиномов
Для фиксированной функции 1е / значением полиномиального оператора L. ({) является полином степени Настоящая глава посвящена исследованию асимптотического поведения сложности алгоритма, вычисляющего значение этого полинома в заданной точке леи. с R
Пусть SL -мерный единичный гиперкуб, Х= (хг, -, xs)Sb Рассмотрим полиномиальный оператор полином степени /z - В дальнейшем, для кратности, произвольный алгоритм вычисления (2.1) в заданной точке будем называть л -- алгоритмом. Множество всех /Л - алгоритмов обозначим через ( Алгоритм Ln e fi называется оптимальным, если для него выполнится соотношение Очевидно, оптимальный алгоритм имеет сложность порядка /г Произвольный Z - алгоритм, имеющий сложность называется асимптотически оптимальным. Следует отметить, что сложность /.л - алгоритма существенно зависит от способа вычисления & {X) Например, при $ 1 , если считать y sxj JC и заданными, то существует оптимальный алгоритм и им является алгоритм, реализующий (2.1) по схеме Горнера (см. [l4, с. 511 ]). В этом параграфе мы сформулируем результаты относительно различных алгоритмов, реализующих (2.1). Второй параграф посвящен построению и анализу алгоритмов при s=f (одномерные алгоритмы), а третий параграф при s 2 (многомерные алгоритмы). Сначала рассмотрим случай s=-f. Пусть / () - полиномиальный оператор, отображаю щий C roij ъ Р щ Причем предположим, что /Л f/) восстанавливает функцию на всем отрезке [0.1 ] по ее значениям Вычисление (2.1), в этом случае, можно осуществить, в частности, двумя алгоритмами (описания этих алгоритмов приведены в 2), которых мы будем называть / /п и L2n - алгоритмами. / - алгоритм основан на вычислении / и Ґ ) для каждого К , в ходе выполнения цикла по параметру суммирования К . Построение .2„- алгоритма основано на следующем обстоятельстве. При вычислении Ln (/) в точке х мы используем значения ,( , / = 0,1-,/2 , которые не зависят ОТ ЛГ. Поэтому, целесообразно вычислить эти / в отдельном цикле по параметру к и запомнить их в виде отдельного массива для дальнейшего пользования. Таким образом, в / - алгоритме процесс вычисления /_п (f) разбит на две части. В первой части формируется массив элементов /, , а во второй - вычисляются только (fK /я) и используя уже готовые элемента А. накопляется сумма (2.1). Справедлива следующая /і/7 - алгоритмы имеют одинаковую сложность. Но это наблюдается только в том случае, когда /.„{JJ вычисляется в одной точке х . При вычислении J-n ff) в А/ точках суммарные сложности выражаются формулами Из (2.6) и (2.7) следует, что L2n - алгоритм имеет неоспоримое преимущество по сравнению с / п - алгоритмом. По этой причине, в дальнейшем мы будем рассматривать только алгоритмы типа L2n - алгоритма. Кроме того, формулы (2.4 - 2.7) имеют весьма неудобную форму и поэтому мы будем применять символ О ( О - большое), который делает записи довольно удобными.
Неравномерная оценка погрешности приближения функций многих переменных операторами Бернштейна
В заключении сформулируем основные положения диссертационной работы, выносимые на защиту:
Исследовано асимптотическое поведение трудоемкости способов "выделение главной части" (ВГЧ) и "существенная выборка" (СВ) при применении следующих аппроксимирующих операторов: - операторы С.Н.Бернштейна (Вп), - операторы, введенные в [ ](Н„), - кусочно-постоянные функции (Рп) - линейные интерполяционные сплайны (SPn) I. Исследованы погрешности приближения аппроксимирующими операторами, где в частности: 1) получено асимптотически наилучшее приближение непрерывных функций многих переменных операторами Бернштейна; 2) получена неравномерная оценка для погрешности приближения функций многих переменных операторами Бернштейна; 3) построены многомерные аналоги операторов Нп и получены оценки для погрешности приближения этими операторами. П. Разработаны алгоритмы вычисления значений операторов Е П} r?t /7 и Ро в заданной точке, где: 1) доказано существование асимптотически оптимального алгоритма в множестве всех алгоритмов, вычисляющих Д, ; 2) доказана невозможность построения асимптотически оптимального алгоритма в множестве всех алгоритмов, вычисляющих Н„ ; 3) для вычисления Рг, и SPn построены алгоритмы, сложности которых не зависят от л 4) предложен алгоритм для вычисления З,? , основанный на случайной выборке, с помощью которого можно добиться значительного снижения роста сложности, а также получена оценка погрешности приближения. Ш. Проведен анализ сложности двух методов моделирования случайных векторов, а именно: 1) стандартного метода моделирования дискретных случайных векторов; 2) метода суперпозиций. IV. Исследованы оценки трудоемкостей способов ВГЧ и СВ в случае применения операторов &п, Нп t Р„ и SPn . В частности, получены асимптотические функции для трудоемкостей обоих способов. V. Предложен эффективный способ решения задач типа вычисления коэффициентов Фурье. На основе этих исследований можно сделать следующие заключения. 1. Трудоемкости способов ВГЧ и СВ имеют одинаковую, возрастающую асимптотику, при применении операторов 3„ и 2. Асимптотически невозрастаюшую трудоемкость имеют способы ВГЧ и СВ, только в том случае, когда применены для вычисления Вп и Н„ алгоритмы, основанные на случайную выборку, а также способ СВ при применении операторов Рп и SPn
Некоторые методы моделирования распределений и анализ их сложности
Результаты диссертации докладывались на всесоюзном семинаре-совещании по теории кубатурных формул и смежным вопросам (г. Бухара, 1983 г.), на семинарах кафедры статистического моделирования ЛГУ им. А.А.Жданова (г.Ленинград, 1982 г., 1983 г.), на семинарах отдела статистического моделирования ВЦ СО АН СССР (г. Новосибирск, 1980 г., 1984 г.), на семинаре отдела прикладных задач Института математики и механики Уральского филиала АН СССР (г.Свердловск, 1984 г.), а также на научных конференциях ТашГУ им. В.И.Ленина (г.Ташкент, 1978-1983 г.г.).
Автор считает своим приятным долгом выразить благодарность своему научному руководителю, профессору Азларову Т.А. за постоянное внимание во время работы над диссертацией.
Как известно, прямые и обратные теоремы теории приближения устанавливают взаимосвязь между порядком убывания погрешности приближения и степенью гладкости функций приближаемого класса. В настоящей главе известные прямые теоремы, установленные для некоторых конкретных полиномиальных операторов (см. [26, 2J ), будут обобщены на случай функции многих переменных. В пределах этой главы мы будем пользоваться обозначениями и терминологией, принятыми в монографии _I7 J Пусть Р некоторое подпространство банахова пространства F Рассмотрим расстояние между элементами feF называется наилучшим приближением / элементами if ей , а элемент (f еР % для которого достигается точная нижняя граница в (1.2) называется элементом наилучшего приближения. Вопросы существования и единственности элемента наилучшего приближения довольно хорошо изучены (см. напр. ІІ7, с. 20-22 ). Задача построения элемента наилучшего приближения является одной из основных задач теории аппроксимации. Решение этой задачи связано с трудностями конструктивного характера и часто, вместо построения элемента наилучшего приближения, ограничиваются изучением оценок сверху и снизу для (I.I). Пусть Го - пространство функций, заданных в некото-рой замкнутой области JX с R , Р - подпространство . с полиномиальным базисом. Ln () - последовательность полиномиальных операторов, отображающих / в Р В этом случае (I.I) будет иметь вид Pit Пусть 1(Х)е Сг01] Как известно, функция со() , определяемая формулой называется модулем непрерывности функции J(JC)\ Она является важной характеристикой структурных свойств f{?c) . В качестве аппарата приближения / () рассмотрим операторы, введенные Бернштейном Хорошо известен следующий результат [ЗІ, 34J где С Л .в _3т[ , кроме того, доказано, что порядок в (1.5) улучшать нельзя. В \l\ для класса функций W fo, і] с конечными вторыми производными получено разложение Этот результат показывает, что никакое улучшение дифференциальных свойств функции J не обеспечит для 3 f/;jc) более высокого порядка сходимости, чем n f (за исключением линейной функции, для которой & /уу . при П 0 просто совпадает с ней). В работе Мюлбаха [Ъ2] приведена следующая неравномерная (зависящая от X ) оценка Эта оценка примечательна тем, что на концах отрезка I 0,IJ она дает лучший порядок сходимости, чем (1.5).
Оценка трудоемкости способа ВГЧ
В предыдущей главе были затронуты вопросы аппроксимации полиномиальными операторами, отображающими заданное пространство функции /к в его подпространство полиномов
Для фиксированной функции 1е / значением полиномиального оператора L. ({) является полином степени Настоящая глава посвящена исследованию асимптотического поведения сложности алгоритма, вычисляющего значение этого полинома в заданной точке леи. с R Пусть SL -мерный единичный гиперкуб, Х= (хг, -, xs)Sb Рассмотрим полиномиальный оператор полином степени /z - В дальнейшем, для кратности, произвольный алгоритм вычисления (2.1) в заданной точке будем называть л -- алгоритмом. Множество всех /Л - алгоритмов обозначим через ( Алгоритм Ln e fi называется оптимальным, если для него выполнится соотношение Очевидно, оптимальный алгоритм имеет сложность порядка /г Произвольный Z - алгоритм, имеющий сложность называется асимптотически оптимальным. Следует отметить, что сложность /.л - алгоритма существенно зависит от способа вычисления & {X) Например, при $ 1 , если считать y sxj JC и заданными, то существует оптимальный алгоритм и им является алгоритм, реализующий (2.1) по схеме Горнера (см. [l4, с. 511 ]). В этом параграфе мы сформулируем результаты относительно различных алгоритмов, реализующих (2.1). Второй параграф посвящен построению и анализу алгоритмов при s=f (одномерные алгоритмы), а третий параграф при s 2 (многомерные алгоритмы). Сначала рассмотрим случай s=-f. Вычисление (2.1), в этом случае, можно осуществить, в частности, двумя алгоритмами (описания этих алгоритмов приведены в 2), которых мы будем называть / /п и L2n - алгоритмами. / - алгоритм основан на вычислении / и Ґ ) для каждого К , в ходе выполнения цикла по параметру суммирования К . Построение .2„- алгоритма основано на следующем обстоятельстве. При вычислении Ln (/) в точке х мы используем значения ,( , / = 0,1-,/2 , которые не зависят ОТ ЛГ. Поэтому, целесообразно вычислить эти / в отдельном цикле по параметру к и запомнить их в виде отдельного массива для дальнейшего пользования. Таким образом, в / - алгоритме процесс вычисления /_п (f) разбит на две части. В первой части формируется массив элементов /, , а во второй - вычисляются только (fK /я) и используя уже готовые элемента А. накопляется сумма (2.1). Справедлива следующая Сравнивая (2.4) и (2.5) можно заключить, что L /л и /і/7 - алгоритмы имеют одинаковую сложность. Но это наблюдается только в том случае, когда /.„{JJ вычисляется в одной точке х . При вычислении J-n ff) в А/ точках суммарные сложности выражаются формулами Из (2.6) и (2.7) следует, что L2n - алгоритм имеет неоспоримое преимущество по сравнению с / п - алгоритмом. По этой причине, в дальнейшем мы будем рассматривать только алгоритмы типа L2n - алгоритма. Кроме того, формулы (2.4 - 2.7) имеют весьма неудобную форму и поэтому мы будем применять символ О ( О - большое), который делает записи довольно удобными. Например, если предполагать выполнение условий