Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков - Численные методы (djvu) (1160088), страница 45
Текст из файла (страница 45)
Если точка Р„о е„принюьнежит П„, „„, то каждая |ю ее координат отличается от соответствующей координаты точки Рсы „, не более чем на и . Позюму из последнеи| неравенства следует оценка (У(р„п „„) —,У(Р, .)~ < Аен |'Рн 1|н,... б Пео...,п., и, ю|едовательно, (2) )У(Рео,ю) — о„,,„,! < Аю| Всякая случайная величина б удовлетворяет неравенству )М(Е)) < зпр)б(. Следовательно, Р(У(Рю, „.)) = М(У(Рсе „,) — и) < | /Аз| < .р 242 1лага 5. Многомерные зада ж С помощью этой оценки заключаеы, что правая часть равенства (1) ис превосходит величины и и — г (Аг/г|)2 ( 4г)г/ ьг Обозначив общее число узлов п* через )ч, получаем оценку (/)) < ~гчг/77гтг/г (3) Отсюда на основании нерввенагва Чебышева (К1) заключаем, что с вь роятвастью 1 — ц выполняется неравенства ~б .(/) — 1(/)( < Аг7у-Ч'/ /1№ Полученная оценка погрешности по порядку лучше, чгм оценка погрешности 0(1/т/И) метода Монте-Карло.
Мы получили оценку погрешвосги по вероятиости. Оказывается, гго для рассматриваемого ьюгода можно получить и гврантированнук~ оценку погрешности. умножая (2) на и ', получаем неравенство — /[Р„п,к,) — ) /(Р) дР < Аг/п'+'. Величина Юь(/) — 1(/) может быть предопгвлена в вцпе суммы таких слывемых: Сулгмируя оценка для этих слашемых, получим (ок(/) — 1(/)( < Аг/п = Аг/Ф'7". Сопоставляя зту оценку с теоремой вз з 7, заключаем, что рассматриваемый метод имеет гарантированную опенку погрешности, оптимальную по порядку на рассматриваемом классе функций. Возникает вопрос, можно ли улучшить на этолг классе оценку дисперсии (3).
Метод Монте-Карло и другие способы интпгрирования, подобные рассматриваемому, ~де приближенное звачение иппи рэпа зависит от некоторых случайных параметров, нэзывыот кедетермикиро'аккыми. Пусть Як(/) — приближенное значение интеграла 7(/), получаемое при применении некоторого недишрминнрованиого способа вычисления. Теорема (без доказательства). Сугцесте1лот дг(г, А), да > О, удоолегааш ряккцие сгедующему соотношению. Длл любого способа еычислекил интеграла, гдг икформаг1ил о подыктсгролькой функции используепюл мкаь как информация об ге гкачекпгх г 1г7 точках, кайдгтсл фуккцггл / и С„(А), д ы й )Бк(/) — Е(/)( > дг(г, А)/№Ы~г (4) 243 111.
О выборе мелим решения задачи с вероятностью дш еде 1/г = 1/г| + ° + 1/г«, а Яи(У) — приближенное эначение иннмеунла. Следствием неравенстиа (4) является неравенство ъ/п(Бл(У)) ) дз(г, А)/№«ггг, (5) которое, в частности, означает, *но оценка (3) не может быть улучшена по порядку. теорема (бел доказательства).
Можно уиа«ал1ь способы инимерировангш, для иошорих ииеегл месшо ещанягированная оцеиха оогрешносши Фл(У) — 1(У)( < д«(г, А)/№ (6] и одновременно М(зл(У)) = У(У) и/Р(Ял.(У)) < дэ(г, А)/№~нг (7) длл Всех / 6 С (А). Мы и«строили выгп< такой способ прн гг = = г, = 1. У(цея построения таких способов состоит в разбиении исхошюй области интегрирования на малые части и вычислении шантрапа по малой части при помощи некоторой «случайной квадратурной формулыв.
Задача 2. Пусть Реп „, — случайная точка в кубе П„,, (при тех же условиях на распределение и независимость точек Р„, „„как в задаче 1). Обозначим черш Р', тачку, симметричную Р„, „, относительно центра куба П„,,и., и положим е «и...,,(У) — (У(Рпп...,п,) + У(Р и .лч)) ои(У) ~ спп...,п,(У). 1 Доказать, что дл» функции из класса Сг,г(А) выполнены одновременно оценки (6), (7). (Заметим, что здесь г = 2/в.) 2 11. О выборе метода решения задачи Обсудим схему регпелия одной задачи, где оказалось выгодным использование методов Монте-Карло, обсуждавшихся в предыдущем парагрвфе. Требовалось иычислить серию ивтегралов У(ам аш аз) = (/ У(Р; оь аг, аз) дР пйи Различных значениЯх паРаметРов ам аг, аз.
Облжть интегРиРованиа С содержалась в единичном трехмерном кубе; при этом условие принадлежности точки к области С задавалось громаццкой системой неравенств. Было ясна, что нельзя Сцелать замену независиыых переменных Глава 5. Мнаюмервые задачч так, чтобы область интегрирования С приобрела гявидартный вид, где было бы возможным применение квадратурных формул выссжого поряд. ка точности.
Поэтому пршилось вне области С продолжить / нулем и рассматривать исходную задачу как задачу вычисления интеграла Г1 Г1 У(оы оъ оз) = / / / /(Р; ом оы аз)г(хы)хзг)лз, е.е.о где ЛР; ом ггз, аз) нри Р б С, /(Р; ем оз. оз) = 0 при РбС. Подынюгрвльпа» функция оказалась юперь разрывной. Для вьг~иггзения интеграла были приыелены формулы прямоугольников и 1'аусса. О целью контроля над точностью проводились расчеты с различным чн<шом узлов инюгрирования. Оказалось, что ршульзвты расчетов медленно устанавливаются (сильно ьгеняютгл при изменении числа узлов), чю указывает на малую ючность получаемых приближенных значений. При непос1юдственном применении метода МогпчьКарло установление получаемых приближенных значений было еще хуже.
Покюму было принято решение применить для вычисления описанные выше способы уменьшс ния дисперсии путем разбиения облегли на части. Выли опробюваны оба описанных выше способа. Область интегрирования 0 < хь яз, яз < 1 раъ бивалась на равные кубы с 1юбрами длиной 1/и., и далее применялись оба мсдп>да, рассмотренные в преЗз,таугцелг параграфе. Как и в случае других квадратур, иссшдовалось установление рсгзульпгтов вычислений.
Оказалось, что оба мшода могут обеспечить требуемую точность вычислений при приемлемых затратах ыашинного времени. Во многих случаях вычисленио интегралов высокой кразяссгп или белыпой серии инте рахов упагтся осу же<"гнить лишь за счет устранения покюрени я сднпаковых вычислений. Решение рвсшватриеаемай задачи представлялось сначала бесперспективным из-за бопьпюй трудоемкости проверки условия принадяелгвости узла Р облвгти С; нахождение же казклого значении /(Р; оь ог, оз) требовало существенно меныпего объеме вычиш1ений. Так ьзк все интегралы вычяшшлись шэ одной и той же области, то было принято решение применить слшзующий алгоритм. Куб 0 < яь з, з:з < 1 разбивался на кубюы с двиной ребра 1/и, в каждом кубике выбиралась случайная точка Рш,,„, н проверялось условие приналлелгнссти точки Р„, „.
области С, кгорлииаты всех точек Р„,, „, б С были записаны в памяти ЭВМ. Далю асе ивтегралы серии заменяли суммами 1 — з/(Р„оы оз, оз) с одними и теми же узлами. Отказ от проверки усзовия Р„, б С при вычислении каждого ивтегралв привел к снижению требований на затраты машинного времени примерно в 100 раз. 1 11.
О выборе метода решения заллчн Другим факторам, позволившим ршко сгоюить затраты мшпннного времени, оказался следующий. Подьпзтегральнвя функция имела внд д(хп гц)Ь(хг тз' гн аз аэ), где вычисление каждого значения функцив и требовало относительно малого числа элементарных операций ЭВМ по сравнению с вычислением ,оокдога значении функции д. 11гптому была применена следующая схема вычи~жений. Все интегралы Т(ап ах, аз), соответствующие одвому и тому же значению параметра ап «ычислялись одноврел~енно; блапщаря этому каждое значение д(эд, гхг) вычислялось при расчаге агой <нрии ннтегршюв только один раз.
Такая ор~ваизация работы позволила довести затраты мазпишюго времени при решгнии рассматриваемой задачи до приемлемых размеров. Анализ хода решения задачи, щюводевный после окончания вычисления <прин, показал ряд неиспользованных назможностсй, кгпорые предоставили бы дополнительные удабг:тва как исполнигелкд чвк и заказчику. С целью уьгеньшсния затрат машинного врелюнв заказчик гзвралгл умеяьшить число М совокупностей значений параметров (а'„аэ, аэ), прн коюрых требовалось вмчислить значение интеграла. Наиболес труда<вгкую чжть прн расчеп1х сосзннляло вычисление значений функции д(тм аг), поэтому общие аатраты лгашиниого времени были пропорциональны не числу М, а чиглу различных значений и).
Таким образам, общие затраты иремени могли бы быть снижены также за счет удачного выбора совокупности (г~), аз, а'). В рассматриваемой задаче имелся еше один неиспользованный рпэерв оовьнпения точгюстп. Труд~живость расс матрвввемого метода пропорциональна проюмдевшо числа рюличвых значений о на число различных значений координат л1 узлов интегрироышвя. Уппя ивптрированяя выбирались случайно, н поэтому чигла различных значений х1 было очень балашихе Для уменьшения э гого чв<яа можно было бы найти, например, по свелук Шеиу пу.пп аппроксимировать исходный ни птрвл по формуле пряэ1оугольвяков 1 -1 в — 1/2'1 1(ам аэ, аэ) м ) — Х ( аь а, аз; — 1 где 1(а!, аэ, аз; ) = ( 11 Х ~оо аэ, аэ, —, гэ* хэ) дхэдвэ, и примеаять метод Манн.
Карло с разбиением области иитегрярзвэння только для вычисления иитеграэо» 1(а„аэ, аз; з1). Другой подход к решению задачи: разбить отрезок (О, Ц на отразив [(ч — 1)/пь ч/т), на каждом из иих выбрать случайную точку сэ н положвть 1 Г(ап аэ, аэ] м — 'Х ' У(а„аж аэ; 4э). э — -1 Упава Э. Многомерные з«ьзачв Оба указанных выше метода имеют худшую скор«кть схолнмссти по сравнг. ни«е с примененным монщом, однако в этих методах вычисляется сущссп.енес меньше значений функции д(хн а«).
Из последних рассуждений видно, что при вычислении болыпих се рий интегралов (как, впрочем, и в случае больших серий других задач) часто больший эффект дгхтигэется не за счет поеьппсния качества мего да при решении каждой из задач серии, а за г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
