Д.Р.-обмен выс-ями, порождаемыми одно другим в процессе разговора м/у 2мя или несколькими собеседниками –реплики

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

Метод определения размера кольца

 

Положите Ваше самое удобное кольцо на круг. Убедитесь,что внутренний диаметр кольца совпадает с контуром на рисунке.

Рис. 3.1.1

Этапы вычисления функционала:

1. Задаются детерминированные входные переменные .
2. Проводится серия из N испытаний .

Количество испытаний N выбирается исходя из заданной точности и достоверности вычислений.

В каждом i-ом испытании:

* с помощью датчиков случайных чисел подчиненных простому (ПЗР) или заданному (ЗЗР) закону распределения моделируются значения случайных параметров .

* определяются значения выходных параметров и запоминаются для последующей обработки.

Отметим, что вместо запоминания всего множества выходных параметров можно запоминать только накопленные суммы исходов за i реализаций.

Количество испытаний N выбирается исходя из требуемой точности и достоверности результата.

3. После всех испытаний методами математической статистики определяются оценки числовых характеристик выходных параметров и, соответственно, оценка искомой величины , при этом .

Поясним сущность статистического моделирования конкретными примерами.

Пример1. Исследуется стохастическая система, выходной параметр которой , где - детерминированный входной параметр, а - случайный параметр, закон распределения которого задан.

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

Данная задача является вероятностной. Искомая величина - , т.е. выражена через математическое ожидание выходного параметра.

Определение приближенного значения величины состоит в следующем:

- задается значение параметра ;

- проводится серия из , в каждом из которых с помощью ДСЧ

с ЗЗР получаем некоторое значение СВ - , и определяем

значение ;

- на основании полученной выборки значений

вычисляется оценка искомой величины

.

Пример 2: Необходимо вычислить площадь произвольной области s, расположенной внутри единичного квадрата (рис. 3.1.2).

 

Рис. 3.1.2.

 

Границы области описаны аналитически:

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

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

Воспользуемся понятием геометрической вероятности попадания точки в область.

Если моделировать случайную точку () равномерно распределенную в единичном квадрате, то вероятность попадания её в область будет численно равна площади области :

Таким образом, эквивалентная вероятностная модель вычисления площади области будет иметь вид:

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

По результатам N испытаний , где - количество точек, попавших в область .

Особенности метода СИ:

1. Вычислительный процесс метода СИ не является детерминированным, т.е. является случайным.

2. Возможность применения метода для решения задач, не сформулированных в виде уравнений или формул.

3. Метод применим только в том случае, если возможно построение вероятностной модели процесса.

4. Метод является своего рода сходящимся; чем больше проведено испытаний, тем вероятнее получение точного результата.

5. Эффективное применение метода возможно при использовании ЭВМ.

6. Для решения задач методом СИ необходимо иметь последовательности случайных чисел подчиненным разным законам распределения.

При исследовании операций, связанных со стрельбой по воздушным целям используются:

- последовательности случайных чисел равномерно распределенных в интервале [0,1];

- последовательности случайных чисел подчиненных нормальному закону распределения.

 

3.1.2. Точность метода статистических испытаний.

 

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

не отклонится результат с заданной вероятностью, т.е.

(1)

- истинное значение параметра;

- оценка искомого параметра;

e - заданная абсолютная погрешность (точность);

a - заданная вероятность (достоверность).

Установим зависимость между достоверностью с одной стороны и числом проводимых испытаний с другой стороны, т.е.

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

Пусть: X - некоторая СВ,

A - некоторое событие,

- истинное значение параметра ( или ),

- оценка искомого параметра ( или ).

P(A): Введем СВ Тогда оценка вероятности появления некоторого события А имеет вид:

M[X]:Задана СВ X Оценка математического ожидания некоторой СВ X имеет вид:

где -значение СВ X, которое она принимает в каждом i-ом испытании (). Таким образом можно записать:

Совокупность величин представляют собой N независимых СВ, каждая из которых распределена по тому же закону, что и сама X.

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

Поэтому для достаточно большого N имеет место соотношение:

(2),

или

Для определения по заданному a решается уравнение

,

где erf - табличная функция (функция ошибок):

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

Из выражений (1) и (2) следует, что для заданной точности e с достоверностью a должно выполняться неравенство

(3)

Вычислим значение через известное :

и подставив его в выражение (3) находим зависимость количества испытаний от требуемой точности

.

P(A):если значение P известно, то

M[X]: - задано

Окончательно получаем, что для вычисления оценок M[X] и P(A) с требуемой точностью и достоверностью необходимое количество испытаний должно быть:

, (4) - при вычислении M[X]:

, (5) - при вычислении P(A).

Если искомая величина W выражается одновременно через M[X] и P(A) и при этом для вычисления должно быть проведено испытаний, а для вычисления - испытаний, то количество испытаний для вычисления W должно выбираться таким, чтобы обеспечить данные точность и достоверность вычисления и одновременно.

Если значение вероятности P(A) и среднеквадратичное отклонение заранее неизвестны, требуемое количество испытаний N в общем случае определяется методом подбора.

Определение N методом подбора.

Задаются значения начиная с с шагом . По результатам N испытаний определяются приближенные значения

и проверяется выполнение соответственно условия (4) или (5).

При невыполнении условия необходимо увеличить N и провести дополнительные испытания. Если же условие выполняется, то число испытаний N обеспечивает с доверительной вероятностью a заданную точность вычисления параметра Ф, поскольку

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

Выбор максимального значения числа испытаний.

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

Сущность способа: в выражение (5) для определения количества испытаний N, подставляется максимальное значение функции Из рис. 3.1.13 видно, что

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

 

Рис. 3.1.13

 

 

3.1.3 Моделирование последовательностей случайных чисел с простым законом распределения.

3.1.3.1 Последовательности случайных чисел и способы их формирования.

Для решения задач методом статистических испытаний необходимо иметь последовательности случайных чисел (СЧ), подчиненных различным законам распределения.

Говоря о последовательности СЧ с определенным законом распределения мы подразумеваем, что каждое число было получено самым произвольным образом, без всякой связи с другими членами последовательности, и что у него есть определенная вероятность появления в заданном числовом интервале. Так при равномерном распределении появление каждого возможного числа в заданном интервале равновероятно.

Описывая (характеризуя) последовательность СЧ необходимо указывать следующие ее основные характеристики:

Ряд распределения.

Дифференциальный закон распределения f(x).

Интегральный закон распределения F(x).

Математическое ожидание M[X].

Дисперсию D[X].

Основным (простым) законом распределения случайных чисел, используемых в методах статистических испытаний, является закон равномерного распределения случайных чисел в интервале [0,1].

Последовательность СЧ X называется равномерно распределенной в интервале [0,1], если плотность распределения вероятностей f(x) определяется как:

.

В этом случае функция распределения F(x) имеет вид:

.

Математическое ожидание M[X] и дисперсия D[X] соответственно равны:

Существуют различные способы получения случайных чисел:

* генерирование случайных чисел специальными датчиками

(механическими, физическими);

* табличное задание случайных чисел;

* аналитический способ получения случайных чисел

(программные датчики случайных чисел).

К простейшим механическим датчикам относятся: бросание монеты, извлечение пронумерованных шаров из урны, “рулетка” и т. д.

Например, результат каждого бросания монеты можно рассматривать, как двоичный знак некоторой бесконечной двоичной дроби. Так как вероятность таким появления 0 или 1 одинакова, то полученное число будет распределено равномерно в интервале [0,1].

Механические датчики могут быть применены при расчетах вручную и не пригодны для ЭВМ.

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

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

В 1927 году Леонард Типпет опубликовал таблицы, содержащие свыше 40000 случайных цифр, произвольно взятых из отчета

з

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

Первую такую машину в 1939 году использовали М. Дж. Кендалл и Б. Бебингтон - Смит при создании таблиц, включающих 100000 случайных цифр.

В 1955 году компания RAND Corporation опубликовала таблицы с 1 млн. случайных чисел, полученных другой такой машиной.

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

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

В специализированных ЭВМ, предназначенных для решения задач методом статистических испытаний, могут быть использованы физические датчики в виде специальных приставок к ЭВМ, работа которых чаще всего на использовании шумов в электронных лампах. Например, если за некоторый промежуток времени уровень шума превысил заданный порог четное число раз, то записывается нуль, а если нечетное число раз, то записывается единица (рис. 3.1.4).

Рис. 3.1.4

 

Если несколько генераторов работают параллельно, то в каждом такте будет вырабатываться k-разрядное двоичное число.

Недостатки физических датчиков:

* трудность осуществления контроля за их работой в процессе решения задачи,

* невозможно воспроизвести повторно одну и ту же последовательность случайных чисел.

* Наибольшее распространение получил аналитический способ формирования последовательностей случайных чисел, то есть случайные числа вырабатываются на ЭВМ программным способом с помощью какого-либо рекурентного соотношения. При этом каждое число , вырабатываемое программным ДСЧ, образуется из предыдущего в результате вычислений.

* Получаемая при этом последовательность чисел, не являясь случайной, может удовлетворять различным статистическим критериям, т. е. вести себя как случайная. Такие числа называются псевдослучайными (ПСЧ).

* Кроме того, в виду ограниченности разрядной сетки, в машине может быть представлено конечное число псевдослучайных чисел, а значит последовательность ПСЧ с некоторого момента начинает периодически повторяться и невозможно получить последовательность ПСЧ с идеально равномерным законом распределения. В данном случае закон распределения называют квазиравномерным.

* Рассмотрим основные характеристики ПСЧ с квазиравномерным законом распределения.

* В ЭВМ с длинной машинного слова - k ПСЧ представляются в виде:

* ,

* где принимает значения 0 или 1 с одинаковой вероятностью , при этом:

* , тогда

* ,

* .

* Заметим, что и при , то есть с увеличением количества разрядов мантиссы чисел x закон распределения асимптотически приближается к равномерному.

* 3.1.3.2 Аналитические методы получения последовательностей псевдослучайных чисел.

*

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

* Рассмотрим некоторые методы получения последовательности ПСЧ.

*

* Метод середины квадратов.

* Берется k-разрядное число (k кратно четырем), возводится в квадрат и выбирается k средних разрядов. В результате получается первое псевдослучайное число. Затем это число берется в качестве исходного и действия повторяются для получения второго псевдослучайного числа и т. д.

* Например:

i
	0,9876	0,97 5353 76
	0,5353	0,28 6546 09
	0,6546	0,42 8501 16
	0,8501	0,72 2670 01
	0,2670	0,07 1289 00

* Этот самый первый метод предложил в 1946 году математик Джон фон Нейман.

* В начале 50-х годов некоторые ученые проводили эксперименты с методом середины квадратов. Оказалось, что вырабатываемые последовательности имеют

* тенденцию вырождаться в короткие циклы повторяющихся чисел.

* Вместе с тем, отметим, что работая с 38-ми разрядными двоичными числами, Н. Метрополис обнаружил последовательность, состоящую из 750000 неодинаковых ПСЧ. Это подтверждает, что применяя данный метод, можно получить полезные результаты. Тем не менее без предварительных трудоемких вычислений ему не стоит излишне доверять.

* Метод выделения дробной части произведения натуральных чисел на иррациональное число.

* Последовательность ПСЧ вырабатывается с помощью соотношения:

* , где - дробная часть числа z, или или и т. д.

* Числа полученной последовательности имеют хорошую равномерность, но неудовлетворительную случайность.

*

* Метод перемешивания.

* Метод основан на перемешивании содержимого разрядов мантиссы ПСЧ и использовании логических операций ЭВМ (сдвига, сложения по модулю 2, логического сложения).

* Например: случайное число x сдвигается вправо и влево на j разрядов и результаты сдвига поразрядно складываются по модулю 2. Существуют и более сложные алгоритмы получения ПСЧ методом перемешивания.

* Недостаток данного метода, как и методов рассмотренных выше, в том, что для него нельзя теоретически гарантировать выполнение определенных свойств случайной последовательности и отсутствие вырождения.

*

* Метод вычетов.

* Наилучшие из известных сегодня датчиков случайных чисел представляют собой частные случаи следующей схемы, предложенной Д. Х. Леммером в 1948 году. Искомая последовательность ПСЧ x получается из соотношения:

* , где .

* Специального упоминания заслуживает частный случай С=0 (то есть ), тогда процесс выработки случайных чисел происходит несколько быстрее. Ограничение С=0 уменьшает длину периода последовательности, но при этом все еще можно получить большой период.

* Вырабатываемая последовательность ПСЧ не всегда оказывается удовлетворительной, если выбирать значения произвольно.

* Например, при , m=10 последовательность выглядит:

i						...
						...
	0,6	0,9		0,7	0,6	...

При выборе необходимо соблюдать некоторые правила, руководствуясь следующими теоретически обоснованными принципами:

1) В качестве начального значения X необходимо брать целое число , причем для случая С=0 числа и должны быть взаимно простыми.

2) Число m должно быть достаточно велико, поскольку количество различных значений не может быть больше m. Другой фактор, влияющий на выбор m: скорость выработки чисел. Так как деление - сравнительно медленная операция, то ее можно избежать при вычислении mod m за счет удобного выбора m, приняв его равным размеру слова (то есть на единицу больше максимального числа, размещающегося в слове ЭВМ).

Однако при выборе младшие разряды чисел ведут себя менее случайно, чем старшие.

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

Другая возможность - это выбор в качестве m наибольшего простого числа, меньшего чем .

Для большинства приложений младшие биты не существенны и выбор является вполне удовлетворительным.

3) Выбор значения . Для того, чтобы получить последовательность ПСЧ с максимально возможным периодом равным m, необходимо выполнить условия:

* ( -1) должно быть кратно r, для любого простого r, являющегося делителем m,

* ( -1) должно быть кратно 4, если m кратно 4.

 

Если , то значение выбирается таким, чтобы . При таком выборе величины гарантируется, что датчик случайных чисел выдаст все ( при С=0) возможных различных значений x прежде, чем они начнут повторяться.

Множитель должен превосходить величину , желательно чтобы он был больше чем , но меньше чем .

4) Выбор значения С:

Числа С и m должны быть взаимно простыми, если кроме того , коэффициент корреляции между числами последовательности будет небольшим. С обоснованием этих принципов можно ознакомиться в [3].

Метод вычетов может быть реализован по-разному путем обобщения схемы, предложенной Д. Х. Леммером.

Например: Для случая, когда m представляется степенью двойки интересный квадратичный метод предложил Р. Ковэю.

mod .

Этот метод почти идентичен методу середины квадратов с той разницей, что он гарантирует большой период.

Простейший случай зависимости от более чем одного из предыдущих значений реализуется в последовательности Фибоначчи:

mod m.

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

Метод вычетов позволяет получить достаточно большие последовательности неповторяющихся ПСЧ. Обычно, если m приближается к размеру машинного слова, мы имеем дело с периодами порядка и больше.

Программные ДСЧ равномерно распределенные в [0,1] оформляются в виде процедур с именем RAND.

Пример: Формализованная форма ДСЧ по методу вычетов имеет вид:

.

Отметим, что ; - начальное значение X. должно принадлежать , иначе первое значение X будет

неслучайным.

С помощью данного датчика можно получить две последовательности чисел максимальной длинны если - нечетное число.

Для перехода от одной нечетной последовательности к другой, необходимо прибавить к любому числу первой последовательности число 2.

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

Это обусловленно следующим. Если кратно , то и все числа последовательности так же будут кратны .

Работа ДСЧ в цикле может быть представлена следующим образом:

Рис. 3.1.5

 

3.1.4 Проверка ДСЧ RAND.

3.1.4.1 Этапы проверки качества равномерно

распределенных ПСЧ.

Многие предлагаемые ДСЧ недостаточно хороши. Пользователи как правило используют эти датчики ничего не зная об их недостатках, что приводит к ошибочным результатам вычислений.

Например, в математическое обеспечение ЭВМ серии EC был включен датчик RANDU, рекомендованный специалистами IBM:

Позже было дано строгое доказательство непригодности датчика. Поэтому, прежде чем использовать ДСЧ в решении задачи методом статистических испытаний с заданной точностью e и достоверностью a необходимо исследовать его на пригодность.

 

 

В первую очередь необходимо определить количество всех различных чисел ПСЧ (длину отрезка апериодичности - L), вырабатываемых ДСЧ.

Дело в том, что ДСЧ может быть использован в той или иной задаче лишь в случае, если выполняется условие , где N - количество случайных чисел необходимое для решения задачи статистическим методом с учетом заданной точности e и достоверности a.

Длину отрезка апериодичности можно определить либо опытным путем, либо, если это возможно, теоретически.

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

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

В качестве таких предположений принимаются:

1) гипотеза о “случайности” ПСЧ;

2) гипотеза о “равномерности” закона распределения ПСЧ;

3) гипотеза о некоррелированности ПСЧ и отдельных разрядов этих чисел.

Для проверки гипотез о “случайности” и “равномерности” закона распределения ПСЧ наиболее часто применяется критерий согласия (“хи-квадрат”).

 

1.1.4.2. Критерий согласия - Пирсона.

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

Идея применения критерия согласия заключается в следующем.

Предположим, что произведено N независимых опытов, в каждом из которых СВ X приняла определенное значение. Результаты опытов оформлены в виде статистического ряда:

			...
			...
			...

 

На основании данного статистического материала необходимо проверить гипотезу H, состоящую в том, что СВ X подчиняется некоторому определенному теоретическому закону распределения. Этот закон может быть задан в той или иной форме: например, в виде плотности распределения вероятностей f(x), или же в виде совокупности вероятностей , где - вероятность того, что СВ X попадает в пределы j-ого разряда.

Между статистическим и теоретическим распределениями неизбежны некоторые расхождения.

Необходимо ответить на вопрос: объясняются ли эти расхождения только случайными обстоятельствами, связанными с ограниченным числом наблюдений, или они являются существенными и связаны с тем, что гипотеза о подчинении СВ X данному закону распределения не верна.

Для того, чтобы принять или опровергнуть гипотезу H, рассмотрим некоторую величину U, характеризующую степень расхождения теоретического и статического распределений. В качестве величины U, например, можно взять сумму квадратов отклонений теоретических вероятностей от соответствующих наблюдаемых частот с некоторыми коэффициентами (“весами”) :

.

Коэффициенты (“веса” разрядов) вводятся потому, что в общем случае отклонения, относящиеся к различным разрядам, нельзя считать равноправными по значимости.

Действительно, одно и то же по абсолютной величине отклонение может быть малозначительным,

если сама вероятность велика, и очень заметным, если она мала. Поэтому естественно “веса” взять обратно пропорциональным вероятностям разрядов .

К. Пирсон показал, что если , то при больших N закон распределения величины U обладает весьма простыми свойствами: он практически не зависит от функции распределения F(x) и от числа опытов N, а зависит только от числа разрядов M, а именно, этот закон при увеличении N приближается к так называемому “распределению ”.

При таком выборе коэффициентов мера расхождения обычно обозначается :

12Следующая ⇒