Н.Н. Калиткин - Численные методы (1133437), страница 24
Текст из файла (страница 24)
20 заранее выбрать в соответствии с узлами (50). Если зто не было сделано, то придется ограничиться интегрированием Р (у) по обобщенной формуле трапеций, причем ее эффективный порядок точности в этом случае будет ниже второго (см. пример в й 1, и. 6). Кроме методов ячеек н последовательного интегрирования есть другие методы, в которых используется кубатурная формула вида т' ~ ~сг1 (гД.
г Можно поставить задачу — найти оптимальные узлы и веса, т. е. дающие,минимальную погрешность на ааданном классе функций. Частный случай этой задачи — нахождение весов н узлов, при которых формула точна для многомерного многочлена максимал~ной степенк. Оптимальные узлы и веса удается найти только дли областей наиболее простой формы, таких как квадрат, круг, сфера.
Зато их использование заметно уменьшает объем расчетов. Это хорошо видно из таблицы 15, в клетках которой приведены минимальные числа узлов, при которых т-мерная кубатурная формула может быль ~очна для многочлена степени л при последовательном интегрировании по формулам Гаусса и при использовании оптимальных ш-мерных коэффициентов.
Таблица 15 й 4. Метод статистических испытаний 1. Случайные величины. Пусть мы измеряем значение некоторой величины й (например, отклонение при стрельбе), на которую влияет большое число различных факторов. Мы не можем 114 1гл. Го ЧИСЛЕННОЕ ИНТЕГРИРОВАНИЕ учесть их действие, поэтому заранее не известно, какое значение примет эта величина. Величину $ называют случайной с плотностью рпспределения р (х), если вероятность того, что величина примет значения между хт к* и х„равна ~ р (х) йх. По смыслу вероятности, р (х) неотрицак, тельна и нормирована + ко р(х) -О, ~ р(х) йх =1.
Очевидно, если значения $ всегда заключены между а, 6, то р(х) =0 вне указанных пределов и ннтеграл (51) надо брать только по отрезку [а, о1. Величина $ может быть дискретной, т. е. принимать только определенные значения х; с вероятностями р, (например, уровни энергии квантовой системы). Дискретную величину можно формально объединять с непрерывной, если положить р (х) = ~ р,б (х — х;), р, ) О, ~', р, = 1, у (5) = ) р (х) йх.
(52) Она принимает значения 0== у =. 1 и монотонно зависит от $. Вероятность того, что т лежит между у, =у(С,) и т, =у (Ек), равна вероятности того, что $ лежит между $, и 1,. А последняя вероятность есть 1р(х) йх=у,— у„т. е. она равна длине интер- 11 вала по у и не зависит от положения этого интервала. Это значит, что у($) с равной вероятностью принимает любое значение на отрезке [О, 1]. Поэтому ее называют случайной величиной, равномерно расцоеделенной на огпрезко [О, 11.
Плотность распределения у равна р(у) =.1 при О=у=-=1 и р(у) =0 вне этого отрезка. 2. Разыгрывание случайной величины. Из всех случайных величин проще всего разыгрывать (моделировать) равномерно распределенную величину у. Рассмотрим, как это делается. где б(х — х;) есть б-функция. Если по значениям случайной величины вычисляется какая- либо функция 1К), то значения этой функции также являются случайными величинами. Такую функцию иногда называют случайной. Равномерно распределенная величина.
Рассмотрим следующую случайную функцию: МЕТОД СТАТИСТИЧЕСКИХ ИСПЫТАНИИ З 41 Возьмем какое-то устройство, на выходе которого с вероятностью '/з могут появляться цифры 0 или 1; появление той или другой цифры должно быть случайным. Таким устройством может быть бросаемая монета, игральная кость (четно — О, нечетно — 1) или специальный генератор, основанный на подсчете числа радиоактивных распадов или всплесков радиошума за определенное время (четно или нечетно).
Запишем у как двоичную дробь уи =-О, с4,сг,х, ... и на место последовательных разрядов будем ставить цифры, выдаваемые генератором: например, у~4 =0,010110... Поскольку в первом разряде с равной вероятностью могут стоять 0 или 1, это число с равной вероятностью лежит в левой или правой половине отрезка 0 -у - 1. Поскольку во втором разряде тоже 0 и 1 равновероятны, число с равной вероятностью лежит в каждой половине этих половин и т. д.
Значит, двоичная дробь со случайными цифрами действительно с равной вероятностью принимает любое значение на отрезке 0 =.у ( 1. Строго говоря, разыграть можно только конечное количество разрядов й. Поэтому распределение будет не вполне требуемым; математическое ожидание Му окажется меньше '/, на величину 2-»-' (ибо значение у =0 возможно, а значение у = 1 невозможно).
Чтобы этот фактор не сказывался, следует брать многоразрядные числа; правда, в методе статистических испытаний точность ответа обычно не бывает выше 0,144 =10-', а условие е (24А дает й ) 10, что на современных ЭВМ перевыполнено с большим запасом. Псевдосл учайные ч псла. Реальные генераторы случайных чисел не свободны от систематических ошибок: несимметричность монеты, дрейф нуля и т. д. Поэтому качество выдаваемых ими чисел проверяют специальными тестами. Простейший тест — вычисление для каждого разряда частоты появления нуля; если частота заметно отлична от '/„то имеется систематическая ошибка, а если она слишком близка к '/„то числа не случайные — есть какая-то закономерность. Более сложные тесты — это вычисление коэффициентов корреляции Последователь-' ных чисел Х,~ ~4 Ь /Я) (У444 /2) или групп разрядов внутри числа; эти коэффициенты должны быть близкими к нулю.
Если какая-то последовательность чисел удовлетворяет этим тестам, то ее можно использовать в расчетах по методу статистических испытаний, не интересуясь ее происхождением. Разработаны алгоритмы построения таких последовательностей; символи- 116 !гл. ш численное интеГРиРОВАние чески их записывают рекуррентными формулами уг=((уг 1) или (53) Уг =1(У1-1 71-» "° 71- ).
Такие числа называют псевдослучайными и вычисляют на ЭВМ. Это обычно удобнее, чем использование специальных генераторов. Но для каждого алгоритма есть свое предельное число членов последовательности, которое можно использовать в расчетах; при большем числе членов теряется случайный характер чисел, например — обнаруживается периодичность. Первый алгоритм получения псевдослучайных чисел был прелложек Нейманом. Возьмем число из 2г цифр (для определенности десятичнык) и,возведем его в квадрат, У квадрата осгавнм 2г средних цифр, откинув г последних и г (нли г — !) первых.
Полученное число снова возведем в квадрат н т. д. Значения т; получаются умножением этих чисел на 10»'. Например, положим г=1 и выберем начальное число 46; тогда получим ( 46 -« 2!16 -« 12! -« 144 -« 196 -« 361 -« 1296 ... у =0,46 О,1! 0,12 0,14 0,19 0,36 0,29 ... Но распределение чисел Неймана недостаточно равномерно (преобладают значения у ~ 111, что хороша видно на приведенном примере), и сейчас их редко употребляют. Наиболее упопгребителен сейчас несложнвгй и неплохой алгоритм, связанный с выделением дробной части произведения у,=(Ауг 1), (54) где А — очень большая константа (фигурная скобка обозначает дробную часть числа). Качество псевдослучайных чисел сильно зависит от выбора величины А: зто число в двоичной записи должно иметь достаточно аслучайный» вид,.хотя его последний разряд следует брать единицей.
Величина ув слабо влияет на качество последовательности, но было отмечено, что некоторые значения оказываются неудачными. При помощи зкспериментов и теоретического анализа исследованы и рекомендуются такие значения: А=5' и у,=2гм для БЭСМ-4; А=5" н у,=2-" для БЭСМ-6. Для некоторых американских ЭВМ рекомендуются А =5" н у„= — 2-"; зти цифры связаны с количеством разрядов в мантиссе и порядке числа, поэтому для каждого типа ЭВМ они свои. Замечание 1. В принципе формулы типа (54) могут давать очень длинные хорошие последовательности, если записывать их в нерекуррентном виде у„=(А"уо) и все умножения выполнять без округления. Обычное округление на ЭВМ ухудшает качество псевдослучайных чисел, но тем не менее до 10» членов последовательности обычно годятся.
117 МЕЛОД СТАТИСТИЧЕСКИХ ИСПЫТАНИЙ $4! 3 а м е ч а н и е 2. Качество последовательности улучшается, если ввести в алгоритм (54) небольшие случайные возмущения; например, после нормализации числа у, полезно засылать в последние двоичные разряды его мантиссы двоичный порядок числа Ау,, Строго говоря, закономерность псевдослучайных чисел должна быть незаметна по отношению к требуемому частному применению.
Поэтому в несложных или удачно сформулированных задачах можно использовать последовательности не очень хорошего качества, но при этом необходимы специальные проверки. Произвольное распре!(еление. Для разыгрывания случайной величины с неравномерным распределением р(х) можно воспользоваться формулой (52). Разыграем у и определим $ из равенства ~ р (х) с(х. Если интеграл берется в конечном виде и формула несложна, то это наиболее удобный способ. Для некоторых важных распределений — Гаусса, Пуассона — соответствующие интегралы не берутся и разработаны специальные способы разыгрывания.
3, Вычисление интеграла. Значение случайной функции 7($) заключено между !'(х) и ! (к+4(х), если $ заключено между х и х+ 4(х; вероятность этого события равна р (х) с(х. Нетрудно понять, что математическое ожидание случайной функции и ее дисперсия соответственно равны 1- ОЭ М(($) = ~ 1 (х) р (х) йх, (55) Р~ (с) = $ [7 (х) — М7 Я)] р (х) с(х = М(е (5) — [М( (ч)]з. (56) Таким образом, одномернечй интеграл можно рассматривать как математическое ожидание случаиной функции !"'(4), аргумент которой есть случайная величина с плотностью распределения р (х), На этом основан первый способ статистического вычисления интегралов. Математическое ожидание можно приближенно вычислить на основании центральной предельной теоремы теории вероятностей; если т! есть случайная величина, то среднее арифметическое многих испьипаний ! ~к= н л„'. Ч 4=! ВВ (гл.
!ч ЧИСЛЕННОЕ ИНТЕГРИРОВАНИЕ тоже есть случайная величина с о!ем же математическил! ожиданием Мьн=М!), причем при й(- со распределение ьн стремится 1 к гауссову (нормальному) распределению с дисперсией )зьн= —,П!). При большом чнсле испытаний дисперсия ьн мала, т. е. значение среднеарифметического с хорошей вероятностью будет близко к математическому Ожиданию. Поэтому можно положить ~ ) (х) р (х) ах - — лг, ) (е !), СО г=! (57) где $ — случайная величина с плотностью распределения р(х). Оценим дисперсию отдельного испытания по формуле (56), заме- няя в ней математические ожидания на суммы типа (57); тогда дисперсия среднеарифметического приближенно равна ь -~~!|!! .е-Гр~ е!!!-р ~ !!!)]) (5~! 1 1 1 1 ! 1 Появление делителя У вЂ” 1 вместо Л! перед фигурной скобкой обосновывается в теории вероятностей; правда, это существенно только при очень малых числах испытаний.
Ответ в методе статистических испытаний носит вероятностный характер и в принципе может сколь угодно сильно отличаться от точного значения интеграла. Однако, согласно свойствам нормального распределения, с вероятностью 99,7% ошибка не превосходит 3 е'Лн. Вероятной называют ошибку 0,675 ~сЛ~, соответствующую 50%-ной вероятности; реальная ошибка обычно близка к этой величине — примерно вдвое больше или меньше.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
