Введение в компьютерное моделирование. Л. В. Горчаков в в в в е е д д е е н н и и е е в в к к о о м м п п ь ь ю ю т т е е р р н н о о е е м м о о д д е е л л и и р р о о в в а а н н и и е е учебное пособие
 Скачать 1.03 Mb.
|
|
Задачи для самостоятельной работы 1. Рассмотрим модель двух хищников, каждый из которых име- ет свою скорость увеличения a и p. Численность обоих уменьшает- ся пропорционально xy. И их численность описывается системой уравнений , 0 dx dt ax bxy a b , , 0 dy dt py cxy p c (16) Для этой модели получаем v, v du dt bp c d dt ac b u и 2 2 d u dt apu (17) 23 Решение не является периодическим и есть st st u Ae Be , где s ap . Дифференцируя это и подставив в (16), получим v st st rAe rBe , где r cs bp . Из этих формул получаем 2 2 v 2 4 u AB . Сле- довательно, траекториями первого приближения являются гипер- болы с центром в E. Используйте Mathcad для получения вида этих траекторий с теми же самыми начальными условиями. 2. На рынке товаров имеется два производителя товаров, один производит х товаров, второй – у товаров. Они обмениваются друг с другом товарами, первый отдает второму долю 0 1 q q в обмен на такую же долю товаров другого. У каждого остается по 1 p q своего товара и доля q – чужого. Изменение товаров опи- сывается системой уравнений 1 2 dx dt p px qy p , 1 2 dy dt p qx py p (18) Покажите, что, либо производство приближается к равновесию, либо один из производителей покидает рынок. Кто покидает рынок – зависит от начальной продукции обоих производителей. 3. Рассмотрим модель популяций системы паразит–хозяин. Раз- витие нападающего вида зависит от доступного ему числа пищи. Если принять, что рождаемость хозяев зависит от числа хозяев N t и что смертность хозяев пропорциональна числу паразитов P t , то скорость изменения популяций определяется уравнениями 1 t n t t dN dt r c P N , 2 t p t t dP dt r c N P , (19) где r n – собственная скорость увеличения популяции хозяина, ко- торая снижается для данного t в зависимости от численности пара- зитов P t линейно. В отсутствии хозяев паразиты гибнут со скоро- стью r p . Последняя компенсируется фактором размножения c 2 при общем числе хозяев N t . Разделив уравнения друг на друга, получим 1 2 t t n t t p t t dN dP r c P N r c N P 24 Отсюда получаем 2 1 ln ln p t t n t t R N c N r P c P const (20) Равенство соответствует набору замкнутых кривых. Достижение равновесия происходит, когда 0 t t dN dt dP dt и соответствует значениям 2 p N r c и 1 n P r c . Учтем конку- ренцию хозяев, изменив уравнение следующим образом 1 t n t t t dN dt r c P bN N Получите решение с помощью Mathcad график зависимости P t от N t 3. С ЛУЧАЙНОЕ ЧИСЛО . Г ЕНЕРАТОРЫ СЛУЧАЙНЫХ ЧИСЕЛ Случайные числа – это случайные величины, которые равно- мерно распределены на интервале [0, 1] и (стохастически) незави- симы. Случайные, или переменные, величины – это вероятностные переменные; они введены по контрасту с переменными, значения которых можно установить заранее. Случайные числа (независи- мые) – равномерные случайные величины. Случайные числа имеют следующие две характеристики: 1) Если 1, 2,3,... i r i есть случайные числа, то их кумулятив- ное распределение, обозначим его F, удовлетворяет уравнению (21) для всех i (см. рис. 28). для для для 0 1, 0 0, 1 1. i i i i i i r r F r P r r r r (21) 2) Теоретически случайные числа должны быть непрерывными переменными с функцией плотности f, определяемой следующим выражением: для иначе 1 0 1, 0 i ri f r (22) 25 Независимость случайных чисел имеет своим следствием тот факт, что знание r 1 , r 2 , …, 1 i r не дает нам никакой информации об r i Случайные числа вырабатываются в машине при помощи чисто детерминированных рекурсивных формул. При этом получаются псевдослучайные числа, их статистические свойства совпадают со статистическими свойствами чисел, генерируемых идеальным слу- чайным механизмом, вырабатывающим числа из интервала [0, 1], независимые и с одинаковой вероятностью. К идеальному генератору применяются следующие требования: полученные с его помощью последовательности должны состоять из: 1) равномерно распределенных, 2) статистически независимых, 3) воспроизводимых, 4) неповторяющихся чисел. Кроме этого генератор должен 5) работать быстро и 6) занимать мало места в памяти машины. Разработаны два основных конгруэнтных метода построения случайных чисел: мультипликативный и смешанный. Все конгруэнтные методы основаны на рекуррентной формуле 1 mod i i n n m , (23) где n i , m, , – целые положительные числа. Запишем первые чле- ны этой последовательности при i = 1, 2, 3: 1 0 mod n n m , 2 2 1 0 1 mod n n n m , 3 2 3 3 3 0 0 1 1 1 mod n n n m , (24) 0 1 1 mod i i i n n m Если дано начальное значение n 0 , множитель и аддитивная константа , то формула определяет последовательность целых чисел {n 1 , n 2 ,…n i ,…}, составленную из остатков деления на m чле- нов последовательности 0 1 1 i i n для любых 26 1, i i n m . По целым числам последовательности i n можно построить последовательность i i r n m рациональных чисел из интервала [0,1]. Обозначим через h – наименьшее положитель- ное число, при котором 0 mod h n n m . Число h называется перио- дом последовательности i n . Величина h существенна, так как выполнение равенства 0 mod h n n m влечет за собой 1 1 2 2 , h h n n n n и т.д. Таким образом, последовательность i n будет периодической, т.е. значения ее членов будут повторяться через h номеров. Необходимо выбрать такие n 0 , , и m , чтобы h был максимальным. Рассмотрим алгоритм для случая двоичных машин. В этом случае 2 b m , где b – число двоичных цифр в ма- шинном слове. Максимальным периодом такой последовательно- сти будет 2 2 b . Алгоритм построения последовательности с мак- симальным периодом: 1. Выбрать в качестве параметра n 0 произвольное нечетное чис- ло. 2. Вычислить по формуле 8 3 t , где t – любое целое положительное число. 3. Вычислить произведение n 0 . Оно содержит не более 2b зна- чащих разрядов. Взять b младших разрядов в качестве первого чле- на последовательности n 1 , остальные отбросить. 4. Вычислить дробь из интервала [0, 1] по формуле 1 1 2 b r n 5. Вычислить очередное псевдослучайное число 1 i n как b пра- вых разрядов произведения n i и вернуться к пункту 4. Рассмотрим пример для b = 4. Процедура должна определить 4 разных числа 4 2 2 4 h 1) Положим n 0 = 7, в двоичной записи n 0 = 0111. 2) При t = 1 коэффициент можно взять равным 11 или 5, выбе- рем 5 в двоичной записи t = 0101. 3) 0 5 7 0101 0111 35 00100011 n , выбираем пра- вые 4 разряда n 1 = 0011 и r 1 = 3/16 = 0,1875. 27 4) n 1 = (0101) (0011) = 00001111, отсюда n 2 = 1111 и r 2 = 15/16 = 0,9375. 5) n 2 = (0101) (1111) = 01001011, отсюда n 3 = 1011 и r 3 = 11/16 = 0.6875. 6) n 3 = (0101) (1011)=00110111, отсюда n 4 = 0111 и r 4 = 7/16 = 0,4375. Различные наборы параметров изучались на предмет идеального генератора и для 32-x разрядных машин хорошие свойства показа- ли генераторы с = 5 13 = 1220703125, n 0 = 5 13 и m = 2 31 –1. Обозна- чая n 0 = N 1 , n = N, r = R, программу генерации случайных чисел можно записать в виде 5 INPUT “ ВВЕДИТЕ N0”;N1 10 N=1220703125*N1 20 IF N>=0 THEN 40 30 N=N+214783647+1 40 N1=N 50 R=N 60 R=R*0.4656613E-9:PRINT R Число R будет искомым числом, на вход программы подается ис- ходное число n 0 = 5 13 . В языке GWbasic, к сожалению, эта програм- ма работать правильно не будет, так как максимальные целые чис- ла должны быть в диапазоне –32768, +32767. Хорошими парамет- рами показали себя также числа = 7 5 = 16807 и m = 2 31 –1. Мультипликативный метод является частным случаем преды- дущего при = 0, опирается на формулу 1 mod i i n n m (25) и задает последовательность неотрицательных целых чисел i n , не превосходящих m. Если взять m равным наибольшему простому числу, которое меньше чем 2 b и m , то максимальный период будет 1 m . Для получения случайных чисел предлагается такой алгоритм: 1. Берем число x 0 содержащее < 9 знаков. 2. Умножаем его на с числом знаков >5. 3. Умножаем результат на 1/m. 28 4. Берем дробную часть результата 3. 5. Исключить из числа, полученного на шаге 4 запятую и ис- пользовать его в качестве х, умножаемого на в шаге 2. 6. Повторять шаги 2-5 до получения нужного количества слу- чайных чисел. В работе Теннат-Смита [6] была предложена аналогичная фор- мула 1 n n n R M R D INT M R D , (26) которая при соответствующем подборе целых чисел M и D выраба- тывает случайные целые числа в интервале от 1 до D-1. Отличную пару представляют числа M = 8192 и D = 67101323. Число D долж- но быть больше M (M – 1) и меньше M 2 .Числа M = 10 и D = 97 можно взять для проверки работы нижеследующего алгоритма, ко- торый также трудно реализуем на GWBasic из-за ограниченного диапазона целых чисел. 10 M = 8192:D = 67101323 20 B = M M–D 30 INPUT”ВВЕДИТЕ ДЛИНУ СЕРИИ”;N 40 INPUT”ВВЕДИТЕ НАЧАЛЬНОЕ ЦЕЛОЕ ЧИСЛО (ОТ 1 ДО D–1);S 50 R = S 60 FOR I = 1 TO N 70 C = INT(R/M) 80 R = B C + M (R–M C) 90 IF R >D THEN R = R–D 100 PRINT R,R/D 110 NEXT 4. М ОДЕЛИ ЗАДАЧИ , ИСПОЛЬЗУЮЩИЕ ГЕНЕРАТОРЫ СЛУЧАЙНЫХ ЧИСЕЛ 4.1. Одномерная модель случайных блужданий [1] Пьяница может двигаться от фонарного столба только по пря- мой направо либо налево (рис. 5) . Все шаги одинаковы по длине и равны l. Направление движения не зависит от предыдущих шагов. Пьяница делает шаг вправо с вероятностью р и шаг влево с вероят- ностью q = 1 – p. Пусть n 1 – число шагов вправо, а n 2 – число шагов влево. Полное число шагов 1 2 N n n 29 Рис. 5. Одномерные случайные блуждания пьяницы Тогда полное смещение от фонарного столба (координата 0) по- сле N шагов равно 1 2 1 x n n , где 1 1 N x N . Определим вероятность того, что после N шагов пешеход окажется на расстоя- нии x от столба. Среднее смещение N x и дисперсия 2 N x да- ются формулами 1 1 N N N x N x xP x и 2 2 2 N N N x x x , (27) где 1 2 2 1 N N N x N x x P x и N P x есть вероятность того, что после N шагов пешеход окажется на расстоянии x от столба. Усреднение проводится по всем блужданиям из N шагов. Задача имеет аналитическое решение, полученное по марковской теории цепей, вида 1 N x p q N и 2 2 4 1 N x pqN (28) В симметричном случае 1 2 p q значение 0 N x . Про- грамма, реализующая случайное блуждание приведена ниже 5 CLS 10 SCREEN 9 20 LINE(0,175)–(640,175) 30 CIRCLE(320,150),5 40 LINE (320,155)–(320,170) 50 FOR I=0 TO 640 STEP 10 60 LINE(I,172)–(I,177) 70 NEXT 75 FOR D=1 TO 100 77 X=0 80 FOR I=1 TO 100 30 90 A=RND(1) 100 IF A>0.5 THEN X=X+10 ELSE X=X-10 110CIRCLE(320+X,175),2,I MOD 15 115 FOR I=0 TO 30000: NEXT 120 NEXT 130 PRINT X 140 NEXT Задание на самостоятельную работу Сравните точное и имитационное решение, совпадают ли они? 4.2. Двумерная модель 1 случайных блужданий [2] Пусть вероятность того, что, начав с перекрестка, пьяница пой- дет на север, юг, восток или запад одинакова. Какова вероятность того, что пройдя 10 кварталов, пьяный окажется не далее двух кварталов от исходного места? Обозначим местоположение пьяного на каждом перекрестке двумерным вектором (х, у), где х – направление с востока на запад, а у – направление с севера на юг. Каждое перемещение на восток дает +1 к х, а перемещение на запад дает –1 к х. Аналогично на се- вер +1 и на юг –1. За начальное положение возьмем начало коор- динат (0, 0). Если в конце прогулки протяженностью в 10 кварталов окажется, что сумма абсолютных значений х и у больше 2, то, сле- довательно, пьяный ушел от начальной точки дальше, чем на 2 квартала. На каждом перекрестке вероятность выбора любого направления равна 0,25. Поэтому для каждого перекрестка берем случайное двузначное число и условимся, что если получается чис- ло в интервале 00–24, то идем на восток (х+1), для 25–49 идем на запад (х–1), для 50–74 идем на север (у+1) и для 75–99 идем на юг (у –1). Алгоритм программы приведен на рис. 6. 31 Рис. 6. Блок-схема модели поведения пьяного прохожего Задание на самостоятельную работу Напишите программу и определите вероятность. 4.3. Двумерная модель 2 случайных блужданий [7] Рассмотрим блуждание пьяного на плоскости, каждый шаг ко- торого равновероятен в любую сторону и направлен под углом в 45 градусов к осям системы координат – х и у. Как далеко он будет от фонаря через n беспорядочных шагов, каково наиболее вероятное расстояние от фонаря после n шагов? Можно промоделировать кривую его движения с помощью генератора случайных чисел. По- сле моделирования большого числа таких опытов можно опреде- лить вероятное расстояние от исходной точки. 32 1. Будем считать, что фонарь расположен в начале системы ко- ординат х, у. 2. Примем, что первая цифра двузначного случайного числа означает +1 по оси х, если получается нуль или четное число и –1, если число нечётное. 3. Вторая цифра этого числа соответствует 1 по оси у анало- гичным способом. 4. Точка , n n x y определяет положение пьяного после n шагов. 5. Расстояние пьяного от фонаря после n шагов определяется выражением 2 2 2 n n n d x y Рассмотрим пример, допустим, первые 5 случайных чисел ока- зались 36, 35, 68, 90 и 35. Построим табл. 1, предполагая, что пья- ница начинает двигаться с координаты (0, 0). Таблица 1 Шаг Первая цифра Вторая цифра Расположение точки , n n x y 1 3 6 (–1, 1) 2 3 5 (–2, 0) 3 6 8 (–1, 1) 4 9 0 (–2, 2) 5 3 5 (–3, 1) То есть, после 5 шагов расстояние от центра будет 1 2 2 2 5 5 5 3,16 d x y Перемещения пьяницы для первых пяти шагов показаны на рис. 7. Рис. 7. Траектория случайного блуждания 33 Затем эта оценка усредняется по серии экспериментов. Сравните ее с аналитическим решением 1 2 n d a n . То есть, наиболее вероят- ное расстояние от фонаря после n шагов равно длине шага а, умноженной на 1 2 n . Текст программы, реализующий это моде- лирование, приведен ниже. 5 CLS 10 SCREEN 9 20 X0=320:Y0=175 30 INPUT “ВВЕДИТЕ ЧИСЛО ШАГОВ”;N 35 RANDOMIZE 40 FOR I=1 TO N 50 A=INT(RND(1)*100) 60 X=A\10 70 Y=A MOD 10 80 X1=X0:Y1=Y0 90 IF X MOD 2=0 THEN X0=X0+10 ELSE X0=X0-10 100 IF Y MOD 2=0 THEN Y0=Y0+10 ELSE Y0=Y0-10 110 LINE (X1, Y1)-(X0, Y0), I MOD 15 115 FOR J=1 TO 30000:NEXT 120 NEXT 125 PRINT X0,Y0 127 CIRCLE(X0,Y0),5 130 PRINT”РАССТОЯНИЕ ОТ СТОЛБА”;SQRT(((X0-320)/10)^2+((Y0- 175)/10)^2) 140 PRINT”ТЕОРЕТИЧЕСКИ ПРЕДСКАЗЫВАЕМОЕ”;SQR(N) |