Кафедра «Информационные технологии»

Стр 1 из 5Следующая ⇒

Донской Государственный Технический Университет

Кафедра «Информационные технологии»

«Методы исследования и моделирование

Информационных процессов и технологий»

МЕТОДИЧЕСКИЕ УКАЗАНИЯ И ЗАДАНИЯ

ДЛЯ ЛАБОРАТОРНОЙ РАБОТЫ

Ростов-на-Дону

Составил: проф., к.т.н. Каныгин Г.И.

Задания и методические указания к выполнению контрольных работ по курсу «Методы исследования и моделирование». – ДГТУ, Ростов-на-Дону, 2012, 24 с.

Методические указания предназначены для освоения технологий моделирования различных объектов и содержат варианты лабораторных работ по курсу «Методы исследования и моделирование» и рекомендации по их выполнению.

Научный редактор: проф. д.т.н. Соболь Б.В.

Лабораторная работа 5

Дискретное преобразование Фурье

5.1. Цель работы: изучение методов частотного анализа дискретных сигналов с помощью дискретного преобразования Фурье.

Теоретические сведения.

Многие сигналы удобно анализировать, раскладывая их на синусоиды (гармоники). Тому есть несколько причин. Например, подобным образом работает человеческое ухо. Оно раскладывает звук на отдельные колебания различных частот. Кроме того, синусоиды являются «собственными функциями» линейных систем (т.к. они проходят через линейные системы, не изменяя формы, а могут изменять лишь фазу и амплитуду).

Пусть дискретный сигнал имеет период N точек. В этом случае его можно представить в виде конечного ряда (т.е. линейной комбинации) дискретных синусоид:

(ряд Фурье).

Эквивалентная запись (каждый косинус раскладываем на синус и косинус, но теперь – без фазы):

(ряд Фурье).

Базисные синусоиды имеют кратные частоты. Первый член ряда (k=0) – это константа, называемая постоянной составляющей (DC offset) сигнала. Самая первая синусоида (k=1) имеет такую частоту, что ее период совпадает с периодом самого исходного сигнала. Самая высокая составляющая (k=N/2) имеет такую частоту, что ее период равен двум отсчетам. Коэффициенты и называются спектром сигнала (spektrum). Они показывают амплитуды синусоид, из которых состоит сигнал. Шаг по частоте между двумя соседними синусоидами из разложения Фурье называется частотным разрешением спектра.

На рис.5.1 показаны синусоиды, по которым происходит разложение дискретного сигнала из 8 точек. Каждая из синусоид состоит из 8 точек, то есть является обычным дискретным сигналом. Непрерывные синусоиды показаны на рисунке для наглядности.

Рис.5.1. Базовые функции ряда Фурье для 8-точечного дискретного сигнала.

Слева - косинусы, справа - синусы. Частоты увеличиваются сверху вниз.

Зная коэффициенты и , можно однозначно восстановить исходный сигнал, вычислив сумму ряда Фурье в каждой точке. Разложение сигнала на синусоиды (т.е. получение коэффициентов) называется прямым преобразование Фурье. Обратный процесс – синтез сигнала по синусоидам – называется обратным преобразованием Фурье.

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

Задание.

1. Согласно варианту задания (табл.5.1) средствами Matlab задать функцию тестового сигнала.

2. Провести процедуру прямого и обратного с использованием алгоритма быстрого преобразования Фурье (БПФ).

3. Вывести результаты в виде графиков:

· Функция сигнала (в зависимости от числа отсчетов);

· Прямое преобразование Фурье (в зависимости от частоты);

· Обратное преобразование Фурье (в зависимости от числа отсчетов).

Таблица 5.1

Вариант	Тестовый сигнал	Коэффициенты

Пример выполнения работы.

Задан тестовый сигнал

где

Воспользуемся пакетом Matlab. В этом пакете прямое и обратное преобразование Фурье осуществляется встроенными функциями:

· fft(y) – вектор прямого преобразования Фурье;

· ifft(v) – вектор обратного преобразования Фурье,

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

аргумента;

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

промежутки значений частоты.

На рис.5.2 показан фрагмент среды Matlab, на котором проиллюстрирована математическая реализация данного примера.

Рис.5.2

В результате решения задачи получили графики (рис.5.3): исходного сигнала(а), прямого преобразования Фурье (б), обратного преобразования Фурье (в).

Рис.5.3

Лабораторная работа 6

Цель работы

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

Теоретические сведения

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

- табличный (файловый) – ввод таблиц равномерно распределённых случайных чисел во внешнюю или оперативную память ЭВМ;

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

- алгоритмический (программный) – использование псевдослучайных (квазислучайных) последовательностей, реализуемых программным генератором случайных чисел.

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

Достоинства метода псевдослучайных чисел.

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

Генераторы случайных чисел

Метод Неймана. Первый алгоритм для получения псевдослучайных чисел был предложен Дж. Нейманом. Его называют методом середины квадратов.

Пусть задано четырехзначное число . Возведем его в квадрат. Получим 8-значное число . Выберем 4 средние цифры из этого числа и положим . Затем снова возведем в квадрат и извлечем из него 4 средние цифры. Получим и т.д.

а) конгруэнтные методы

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

Два целых числа А и В конгруэнтны (сравнимы) по модулю m, если их разность делится на m без остатка. То есть

В - А = km,

где k - целое. Это определение записывается так A = B (mod m).

Например:

1984 º 4 (mod10), 5008 º 8 (mod 10³⁾ и т.д.

Величина m берется равной длине машинного слова m = 2^b, где b — число бит в машинном слове.

Мультипликативный конгруэнтный метод (АлгоритмЛемера).

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

, (6.1)

где и - очередное и последующее случайное число;

m - модуль, m > 0;

a - множитель, 0 ≤ a < m;

- начальное значение, .

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

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

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

. (6.2)

Линейный конгруэнтный метод. Схема метода предложена Д.Лехмером в 1949 году. Работа этих генераторов основана на использовании формулы:

. (6.3)

Число m выбирается аналогично предыдущему пункту. Множитель а предпочтительно выбирать в интервале [0, 01m; 0, 99m]. Значение с может быть произвольным, но не должно иметь общего множителя с m. При b=0 получаем, рассмотренный выше мультипликативный метод.

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

Квадратичный конгруэнтный метод. Последовательность случайных чисел вычисляется с помощью следующего рекуррентного соотношения

. (6.4)

Наибольшее значение периода данного датчика достигается при четном a, нечетном с и если нечетное b удовлетворяет условию .

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

(6.5)

Для практических расчетов принимают .

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

(6.6)

где и - целые числа, лежащие между нулем и m .

BBS – генератор. Данный генератор вычисляется по формуле

. (6.7)

Вначале выбираются два больших простых числа p и q. Числа p и q должны удовлетворять условиям , т.е. при делении p и q на 4 должен получиться одинаковый остаток 3. Далее вычисляется число , называемое целым числом Блюма. По формуле вычисляется стартовое число генератора, где - взаимно простое число (т.е. не имеющее общих делителей, кроме 1).

Системный генератор MS Fortran.

. (6.8)

б) тригонометрические методы

Основаны на использовании ошибки вычисления косинуса больших алгоритмов.

, (6.9)

где n - целое число, определяемое типом ЭВМ;

- начальное значение, .

Варианты заданий.

Таблица 6.1

Вариант	Тип генератора	Начальные данные
	Мультипликативный конгруэнтный метод. Формула (6.1).	k=31; а=16807
	Линейный конгруэнтный метод. Формула (6.3).	а=16070093; b=453816693; k=31
	Квадратичный конгруэнтный метод. Формула (6.4).	а=6; b=7; c=3; m=4096
	Кубический конгруэнтный метод. Формула (6.5).	а=53668; b=400144; c=12211; k=15
	Генератор Фибоначчи. Формула (6.6).	k=14
	BBS – генератор. Формула (6.7).
	Системный генератор MS Fortran. Формула (6.8).	-
	Тригонометрический метод. Формула (6.9).	-
	Тригонометрический метод со счетчиком. Формула (6.10).	-
	Мультипликативный конгруэнтный метод. Формула (6.1).	k=15; а=16807
	Линейный конгруэнтный метод. Формула (6.3).	а=165; b=3463; k=14
	Квадратичный конгруэнтный метод. Формула (6.4).	а=8; b=9; c=3; m=4096
	Кубический конгруэнтный метод. Формула (6.5).	а=52774; b=40692; c=3791; k=31
	Генератор Фибоначчи. Формула (6.6).	k=14
	BBS – генератор. Формула (6.7).
	Системный генератор MS Fortran. Формула (6.8).	-
	Тригонометрический метод. Формула (6.9).	-
	Тригонометрический метод со счетчиком. Формула (6.10).	-

Лабораторная работа 7

Теоретические сведения

В процессе моделирования часто требуются имитировать случайные события с заранее известными вероятностями. Пусть имеется событие А, вероятность наступления которого равна . Требуется выработать правило, при многократном использовании которого частота появления события А стремилась бы к его вероятности. Выберем с помощью датчика случайных чисел, равномерно распределенных в интервале [0; 1) некоторое число х и определим вероятность того, что . Для случайной величины х с равномерным распределением на интервале [0; 1) справедлива следующая зависимость:

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

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

Рис.7.1

На данном рисунке в блоке 1 осуществляется к датчику случайных чисел, генерирующему случайную величину х. Блок 2 проверяет условие . Если оно выполняется, считается, что произошло событие А. В противном случае считается, что произошло противоположное событие (не А).

7.1.2. Задание. Дана вероятность события (табл.7.1). Требуется:

· Сгенерировать N случайных событий;

· Подсчитать количество успешных событий;

· Рассчитать среднестатистический разброс значений ;

· Рассчитать нижнее значение для вероятности ;

· Рассчитать верхнее значение для вероятности .

Таблица 7.1

Вариант
	0, 40
	0, 50
	0, 60
	0, 70
	0, 45
	0, 55
	0, 65
	0, 75
	0, 42
	0, 52
	0, 62
	0, 72
	0, 46
	0, 56
	0, 66
	0, 76

Систем

Теоретические сведения

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

Схематически эта модель представляет собой последовательное соединение элементов системы (рис.7.2).

Рис.7.2

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

Блок схема алгоритма

Введем обозначения:

N – количество испытаний;

k – номер испытания;

i – номер элемента;

- событие безотказной работы i –го элемента: -отказа нет; - произошел отказ.

7.2.2. Задание. Согласно варианту задания (табл.7.2) необходимо составить и отладить программу моделирования надежности сложных нерезервированных систем.

Таблица 7.2

Вариант	N	m
			0, 40
			0, 50
			0, 60
			0, 80
			0, 70
			0, 45
			0, 55
			0, 65
			0, 42
			0, 52
			0, 62
			0, 72
			0, 46
			0, 56
			0, 66
			0, 76

Теоретические сведения

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

Схематически эта модель представляет собой последовательное соединение элементов системы (рис.7.3).

Рис.7.3

Для смешанного соединения элементов системы вероятность безотказной работы равна .

7.3.2. Задание. Согласно варианту задания (табл.7.2) необходимо составить и отладить программу моделирования надежности сложных систем для смешанного соединения элементов. При выполнении работы ввести обозначения, аналогичные п.7.2.1.

Теоретические сведения

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

Подавляюще число расчетов по методу Монте-Карло осуществляется с использованием псевдослучайных чисел. От последовательности случайных чисел , равномерно распределенных в интервале [0; 1] (см. п.6), можно перейти к последовательности случайных чисел с произвольно заданным законом распределения, используя табл.7.2

Таблица 7.2

а) Вычисление площади фигур

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

Далее с помощью датчика случайных чисел с равномерным распределением генерируются случайные координаты (х, у) точки внутри прямоугольника и определяют, попала точка на фигуру или нет. Такие испытания проводятся N раз.

Пусть из N точек, полученным таким образом, М попали на фигуру. Тогда, считая, что распределение точек в прямоугольнике равномерное, можно записать пропорцию

Из этой формулы найдем площадь искомой фигуры

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

Метод Монте-Карло чрезвычайно эффективен, прост, но необходим «хороший» генератор случайных чисел. Вторая проблема применения метода заключается в определении объема выборки, то есть количества точек N, необходимых для обеспечения решения с заданной точностью. Эксперименты показывают: чтобы увеличить точность в 10 раз, объем выборки нужно увеличить в 100 раз; то есть точность примерно пропорциональна корню квадратному из объема выборки:

Пример 1. Используя метод Монте-Карло, вычислить площадь круга радиуса R=5см. с центром в точке (1; 2).

Решение. Уравнение соответствующей окружности имеет вид

(х-1)² + (у-2)² = 25.

Для решения задачи методом Монте-Карло впишем круг в квадрат. Его вершины будут иметь координаты (-4; -3); (6; -3); (-4; 7); (6; 7). Любая точка внутри квадрата или на его границе должна удовлетворять неравенствам –4 < x < 6 и –3 < у < 7.

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

S_кр= S_кв M/N = 100 M/N.

В табл.7.3 приведены оценки S_кр,полученные для разных значений N. При этом для каждого N выполнялось 5 прогонов (S_кр=78, 54 кв.см).

Таблица 7.3

Оценка площади круга

Номер прогона	Оценка площади круга S_кр
Число испытаний n
		1 000	5 000	10 000
		79, 5		79, 5
				81, 88	78, 8
		77, 3	80, 2	79, 5	79, 8
		79, 13	81, 29	78, 22	78, 6
		77, 72	77, 76		78, 26
Среднее	75, 6	78, 63	78, 77	78, 23	78, 88
Дисперсия	27, 3	0, 3	0, 0789	0, 0785	0, 01

Выводы:

1. С ростом числа генерируемых точек (т. е. продолжительности прогона модели) оценки площади круга приближаются к точному значению (78, 54 кв.см.). Это условие обычно достигается после повторения эксперимента достаточное количество раз. Наблюдаемое явление типично для результатов любой имитационной модели. Обычно в большинстве имитационных моделей нас интересуют результаты, полученные в стационарных условиях.

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

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

Замечание. Если - последовательность случайных чисел, равномерно распределенных на отрезке [0, 1], то для определения последовательности случайных чисел равномерно распределенных на отрезке [a, b] необходимо использовать формулу .

Пример 2. Используя метод Монте-Карло, вычислить приближенно число .

Решение. Известно, что площадь круга равна , где R – радиус круга. Тогда , то есть, зная радиус окружности и определив численно ее площадь, можно приближенно рассчитать значение .

Выберем окружность единичного радиуса с центром в начале координат и рассмотрим ее четверть.

Для использования метода Монте-Карло необходимо, используя датчик случайных чисел, равномерно заполнить точками (пусть их общее количество будет N ) квадрат со стороной 1 и подсчитать, сколько из них окажется внутри окружности (это число обозначим через М ). Тогда площадь всей окружности равна 4M/N, а так как ее радиус равен 1, это же число примерно равно .

Варианты заданий.

Согласно варианту задания найти площадь заштрихованной фигуры методом Монте-Карло.