книги из ГПНТБ / Каретников, В. Н. Основы вычислительной техники учебное пособие

Ьг= ± ( f 3- A ) i b 3-,

Hi= ~2~( /о	fn) ~ a 3i
/о --- / з + / о —/ я ) »
где
/,,= Д О ) ; Л = /Ш ;	/ ' - - / ( т г ) ' -
/ и - /	11-2г.
	12
Для вычисления Ь2 разделим период 2я не на 12 час­
тей, как для вычисления других коэффициентов, а на

8 равных частей, допуская, что соответствующие зна­

чения

f \ = J \ 8	2г.-3	2к-5
	f s = f	/» “ /

можно снять с графика, тогда

b-2=	/з + Л ~ /г )-

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

					Т а б л и ц а 5
/о	Л	/г	h	и	h
2,714	3,042	2,134	1,273	0,788	0,495
/б	и	h	и	/ю	fn
0,370	0,540	0,191	—0,357	—0,437	0,767

Пользуясь приведенными выше формулами, находим

а° =

=0,960 ;

60

«3=0,271; Ьз—0,100; =0,915; а, = 0,901; а2 = 0,542.

Построив график функции f(x) и сняв с него орди­

наты fu fa,	f5, f7, получим 462 = / i—/з+ fs—/7 = 2,36, отку­
да &2= 0,59	(приближенно).

Таким образом, приближенная формула для иско­ мого ряда Фурье будет

/(.v)—0,96+0,90cosx-f-0,54cos2x+0,27cos3.v-f -f 0,92sinx-f-0.59sin2x+0,10sin3x.

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

Понятие о теории корреляции

Нередко наблюдаются случайные величины, между которыми имеется некоторая зависимость. Например, прочность бетона как-то зависит от количества воды, вводимой в бетонную смесь. Однако прочность зависит также от соотношения между количествами цемента и заполнителей, так что при данном количестве воды воз­ можно различное значение прочности. Зависимость та­ кого рода не функциональная, поскольку каждому зна­ чению аргумента соответствует некоторое распределе­ ние другой переменной; эга зависимость статистическая.

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

Т а б л и ц а 6

	У		X2		X			П(У})
		Х\		. . .	XI	. . .	«А
	У\	«и	«21 . . .		«а	. . .	«А1	п(У1 )
	Уч	«12	«22 . . .		«12	• • •	«А2	n(yz>
	УJ	пм	,П] . . .		«;;	. . .	«А/	nfyj)
	У1	пи	Пи . . .		«а	. . .	«А/	П(У1>
		П(Х\)	П(х2) . . .		n(Xi)	. . .	п(хк)

61

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

1 k	1 ^
л:0= — 2 Xitiixt)]	у0= — 2 >уг(у;).
п г=1	j=l

Непосредственное изучение статистической таблицы может дать лишь поверхностное представление о зави­ симости между обеими переменными (даже в пределах наблюдаемой выборки). Лучшее представление может дать сопоставление средних значений одной величины со всеми значениями другой. Такая зависимость назы­ вается корреляционной. О структуре этой зависимости первоначально судят по отображению статистической таблицы на чертеже.

Нередко оказывается, что построенные точки группи­ руются вдоль некоторой прямой, так что искомую связь предполагают линейной. Тогда ищут функцию в форме у = ах-\-Ь и подбирают коэффициенты по способу наи­

меньших квадратов, причем оказывается, что искомая прямая проходит через точку (х0,уо)- Линейное урав­ нение приводят к виду у—Уо — р(х—х0), называемому уравнением регрессии у на х. Здесь

Р=h2j (■ *i-*o)(y/-yo)V /w2

и вычисляется по статистической таблице.

Полезно (даже, если по физическому смыслу пере­ менные неравноправны) составить также уравнение регрессии х на у. взаимное расположение обеих пря­

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

2 (Xi—x0)(yi—y0)nij

Г— — ---------------------- .

При г—0 линейной корреляции нет (прямые парал­ лельны координатным осям); при |г | = 1 имеется функ­ циональная зависимость (прямые совпадают); при 0 < И < 1 есть линейная корреляционная зависимость;

62

с увеличением |г| теснота	связи возрастает.	При
|г|=0,4 считают линейную	связь слабой и ищут	дру­

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

2. Метод Монте-Карло (метод статистических испытаний)

Метод Монте-Карло — это численный метод решения математических задач при помощи моделирования слу­ чайных величин.

Хотя теоретическая основа метода была известна уже давно, однако до появления электронных вычисли­ тельных машин (ЭВМ), позволивших быстро моделиро­ вать случайные величины, этот метод не находил при­ менения. Датой его открытия считается 1949 год, когда вышла в свет статья американских математиков Дж. Неймана и С. Улама «The Monte Carlo method».

Как видим, эта дата соответствует периоду появления ЭВМ. Применение ЭВМ сделало метод Монте-Карло весьма универсальным численным методом.

Название метода происходит от названия города Монте-Карло д княжестве Монако, знаменитого своим игорным домом, так как простейшим механическим при­ бором получения случайных величин является рулетка.

Задачи, решаемые методом Монте-Карло

1)Метод Монте-Карло позволяет моделировать лю­ бой процесс, на протекание которого влияют случайные факторы.

2)Он позволяет решать многие математические за­ дачи, не связанные с какими-либо случайностями, путем искусственного создания их вероятностных моделей.

Пусть необходимо вычислить площадь плоской фи­ гуры S (рис. 11). Заключим эту фигуру в единичный квадрат. Нанесем в квадрате N случайных точек (их нужно «выработать»). При этом N' точек попадет

внутрь фигуры S. Очевидно, что площадь 5 приближен-

63

но будет равна	N'/N. Чем больше будет М, тем выше
будет точность	этой оценки. Например,	при N = 60
N' = 42. Тогда S = 0,70. «Выработать» случайные точки
для единичного	квадрата можно в простейшем случае
следующим образом. Написать на двадцати		отдельных

бумажках цифры 0,1; 0,2;...; 0,9; 1,0; 0,1; 0,2;...; 0,9; 1,0;

положить эти бумажки в закрытый ящик, перемешать

их и извлекать по две, каждый раз возвращая их назад и снова перемешивая все бумажки. Каждая такая опе­ рация дает два числа — координаты случайной точки в единичном квадрате. Точность вычисления S зависит от

количества проделанных операций.

Получение случайных величин

Различают три способа получения случайных вели­ чин: таблицы случайных чисел, генераторы случайных чисел и метод псевдослучайных чисел.

Таблицы случайных чисел составляются с помощью

специальных рулеток, оборудованных электронными устройствами (а не ящика). Простейшая схема такой

64

рулетки показана на рис. 12 (вращающийся диск резко

останавливается и выбирается та цифра, на которую указывает неподвижная стрелка).

Самая большая из опубликованных таблиц случай­ ных чисел содержит 1000000 цифр (США, 1955 г.). Та­ кие таблицы должны вводиться в ЗУ ЭВМ, что требует увеличения памяти машины.

Генераторы случайных чисел. Рулетка — механиче­ ский прибор, обладающий медленным действием, по­ этому его нельзя присоединить к ЭВМ для выработки

/	\	0 9		/ \
	1\		/		4 Д	\
г м	/				7	—
			\	\	5	/
\	/	i	s			/

Рис. 12. Схема рулетки

случайных чисел по мере надобности. Поэтому в качест­ ве генераторов случайных величин, работающих в комп­ лексе с ЭВМ, используют, например, шумы в электрон­ ных лампах: если за некоторый фиксированный про­ межуток времени At уровень шума превысил заданный

порог четное число раз, то записывается нуль, а если нечетное число раз,— то записывается единица. Всего предполагается т таких генераторов, работающих па­

раллельно и засылающих нули и единицы во все двоич­ ные разряды специальной ячейки, так что в результате каждого такта получаем случайное число, записанное в m-разрядной двоичной дроби 0, а\ а2... ат, где каждая

из величин а , является случайной величиной. Существуют и более совершенные конструкции гене­

раторов, однако все они обладают тем недостатком; что

5 2521

65

при их применении трудно проверить «качество» выра­ батываемых чисел, поэтому приходится делать периоди­ ческие проверки, а расчеты на ЭВМ с целью контроля производить дважды.

Псевдослучайные числа. При расчетах на ЭВМ наи­ более удобно использовать метод псевдослучайных чи­ сел. Числа, получаемые по какой-либо формуле и ими­ тирующие значения случайной величины, называются псевдослучайными числами. Единственным требованием к псевдослучайным числам является их удовлетворение принятой системе тестов: не противоречат ли те или иные свойства получаемой суммы чисел гипотезе о том, что эти числа — значения случайной величины.

Рассмотрим пример простейшего теста. Пусть имеет­ ся таблица цифр, содержащая нулей п0, единиц — п\, двоек — « 2 и т. д. до девяток. Чтобы считать числа таб­

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

11 (л,-0,1 Л 02,

I- о

которая не должна быть слишком большой или слиш­ ком маленькой.

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

Так, например, Дж. Нейман предложил метод сере­ дины квадратов. Задается любое ^-значное число. По­

следующие	псевдослучайные числа	получаются так:
X возводят	в квадрат, получается 2Х-	или 2Х— 1-знач-

пое число (в последнем случае впереди приписывается нуль), из которого выбираются X средних цифр, затем

образовавшееся число возводят в квадрат и т. д. Другие алгоритмы основаны на особенностях конк­

ретных ЭВМ.

Особенности метода Монте-Карло

Большинство расчетов но методу Монте-Карло в на­ стоящее время осуществляется с использованием псев­ дослучайных чисел на ЭВМ. При этом нужно иметь в виду две особенности метода Монте-Карло.

6 6

Первая особенность — простая структура вычисли­ тельного алгоритма. Как правило, составляется про­ грамма для осуществления одного случайного испыта­ ния. Так, в приведенном выше примере определения площади 5 надо выбрать случайную точку в квадрате и проверить, принадлежит ли она S. Затем это испыта­ ние повторяется N раз, причем каждый опыт не зави­

сит от всех остальных и результаты всех опытов осредняются. Поэтому имеется второе название метода Монте-Карло — «метод статистических испытаний».

Второй особенностью метода является то, что ошиб­

ка вычислений пропорциональна y o / N ,	где D — некото­
рая постоянная, a N — число испытаний.	Таким образом,

чтобы уменьшить ошибку в 10 раз, нужно увеличить N (то есть объем работы) в 100 раз. Поэтому применение

метода Монте-Карло считается наиболее эффективным

в тех задачах, где требуемая точность результата неве­ лика (5—10%).

Постоянная D зависит от удачности выбора вариан­

та метода Монте-Карло, т. е. от способа расчета. Оче­ видно, нужно стремиться к снижению величины D.

Примеры применения метода Монте-Карло

Расчеты систем массового обслуживания необходи­

мы при планировании предприятий и строек: вместо дорогостоящего" (а иногда просто невозможного) экспе­ римента в натуре они позволяют экспериментировать на ЭВМ путем моделирования разных вариантов органи­ зации работы при использовании оборудования.

Рассмотрим расчет одной из самых простых систем массового обслуживания на примере отсыпки земляной плотины самосвалами. Пусть к отсыпаемой бровке пло­ тины имеется п подъездных путей, по которым самосва­

лы могут продвигаться только задним ходом (рис. 13). К точке а подъезжают самосвалы, причем моменты их

прибытия случайные. Каждый самосвал поступает к ли­ нии № 1. Если в момент поступления k-ro самосвала

(Т к) линия	№ 1	свободна, то он разгружается	на ней
в течение i3	мин	(t3— время занятости линии).	Если в

момент Тк линия № 1 занята, то машина идет на линию № 2 и так далее... Наконец, если все п линий в момент Tk заняты, то машина простаивает. Требуется опреде­

5*

67

лить, сколько (в среднем) машин может обслужить принятая система подъездных путей за время Т и ка­

ковы возможные простои.

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

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

«вырабатываемыми» случайными (или псевдослучайны­ ми) величинами v соотношением

x = /(v ).

(1 )

Так, например, при экспоненциальном распределе­ нии случайной величины т при плотности распределения а будем иметь

т = — Inv.

а

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

Разыграем момент поступления /с+ 1-й машины. Для этого выбираем (машина «вырабатывает») очередное значение v и по формуле ( 1) вычисляем очередное зна­ чение х = х к . Момент поступления 6+ 1-й машины най­

дем из выражения

Тки — Т к + т к.

( 2)

6 8

Свободна ли в этот момент первая линия? Для уста­ новления этого нужно проверить условие

где через t\		t\ < Т к :1 ,							(3)
	обозначено		суммарное время				занятости
первой линии до прихода /г + 1-й машины.						значит,			что к
Если условие (3)		выполнено,		то	это
моменту Т,с ' I линия		уже	освободилась			и может			при­
нять £+1-ю	машину.	При этом		в программе				следует
заменить t\	на 7 Y i+ + ,		добавить		единицу		в	счетчик

принятых машин и переходить к /е+2-й машине. Если условие (3) не выполнено, то это значит, что первая линия в момент Ткл\ занята. Тогда нужно проверить,

свободна ли вторая линия из условия

где /2— суммарное			*2<	Т к ,, ,	(4)
			время занятости второй		линии до
прихода £ + 1-й машины.
Если	условие	(4)	выполнено, то в программе необ­
ходимо	заменить	/2	на	7 + ц + / 3. добавить	единицу в

счетчик принятых машин и перейти к следующей ма­ шине. Если же условие (4) не выполнено, то следует перейти к проверке условия + < Тк ,\ и т. д.

Может оказаться, что при всех i от 1 до п £ ,> 7+ . i ,

т. е. все линии в момент 7Y, i заняты. Тогда надо доба­ вить единицу в счетчик отказов и потом рассматривать

следующую заявку.		проверять еще
Каждый раз,	вычислив TKli, надо
условие окончания опыта:		(5)
Когда условие	Т к i 1 1> Т кон .
	(5) окажется выполненным, опыт за­

канчивается, в счетчике принятых машин и в счетчике

отказов будут	стоять числа	maun(j)		и	пг отк (/) (здесь
индекс обозначает номер опыта).				(с	использованием
Такой опыт	повторяется	N раз
различных v).	Результаты	всех	опытов осредняются:
	1	n
	^Дцып. ср ■=- д [ “ ^		ни:;(?)5

1 N

Мотк. ср ==^ “дГ ^ ^ о т к ( 0 -

Метод Монте-Карло позволяет рассчитывать более сложные системы. Так, величина t3 может быть не

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

69