Введение во фракталы

Английские военные топографы еще до войны заметили, что длина побережья Великобритании зависит от длины линейки, которой ее измеряют. Аналогичная зависимость определяет длину некоторых рек, побережье многих островов, путь, проходимый частицей при броуновском движении, и многое другое. В качестве наглядного примера можно привести так называемый «остров Коха». На рис. 5.5 показано, как можно построить такую фигуру.

Рис. 5.5. Схема построения острова Коха

На первом шаге берем обычный равносторонний треугольник (рис. 5.5). Потом на каждой стороне достраиваем по треугольнику, сторона которого в три, а значит, площадь в девять раз меньше, чем у исходного треугольника и так далее. То, что получится после бесконечного количества таких шагов, называется островом Коха. При этом длина его побережья бесконечна, поскольку на втором шаге периметр фигуры увеличится в 4/3 раза, на третьем - еще в 4/3 и т. д. Это происходит потому, что каждый отрезок мы заменили ломаной, длина которой в 4/3 раза больше. Таким образом, периметр данной фигуры

p = (4/3) n = ¥. При этом с помощью формул геометрической прогрессии можно убедиться, что площадь острова Коха конечна.

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

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

Рис. 5.6. Пример фрактальной масштабной инвариантности

На это математики могут ответить просто и остроумно: «Важна не сама длина, а то, как она зависит от размеров линейки, т. е. важно некое число, называемое фрактальной размерностью». Для отрезка размерность равна 1, для квадрата - 2, для куба - 3. Для фракталов размерность - дробное число. Отсюда и само название «фрактал», происходящее от английского «fractal» - дробный, неполный, частичный. Например, для острова Коха оно лежит между 1 и 2 - полоса в двумерном пространстве, т. е. уже не обычная кривая, но еще не плоскость (дробная размерность).

5.2.2. Самоподобные (фрактальные) случайные процессы

Представленный пример фрактала (кривая Коха) относится к классу детерминированных фракталов, т. е. когда объект непосредственно составляется из своих малых копий. В теории телетрафика для описания поведения величины нагрузки в сетях связи с пакетной коммутацией применяется класс случайных (стохастических) фракталов. В этом случае свойство самоподобия (масштабной инвариантности) наблюдается лишь «в среднем», т. е. подобными являются не сами отсчеты сигнала, а, например, его КФ или ПРВ в разных временных масштабах. Три характерные особенности самоподобных процессов выражены в медленном убывании дисперсии, долгосрочной зависимости и флуктуационном характере спектра мощности таких процессов.

Рассмотрим дискретную случайную последовательность отсчетов:

X={xi,i=1,2,...},

где xi - СВ с заданным законом распределения. Будем предполагать, что все рассматриваемые СП имеют ограниченную ковариацию B (xi, xi +t)< ¥,"t и следовательно дисперсию s xi = B (xi, xi)< ¥.СП будет обладать свойством самоподобия, если агрегированный процесс m-го порядка

будет иметь КФ r (m)(k)совпадающую с КФ r(k)исходного СП для любых m. При выполнении данного условия можно утверждать, что дисперсия агрегированного процесса X (m)убывает согласно выражению

D (X (m))» m -b, 0<b<1, m ®¥,

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

å r (k)®¥, r (k)» k -b

Наконец энергетический спектр самоподобных процессов описывается выражением

f (w)=å r (k) e - j w k» c w-(1-b),w®0.

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

Важнейшим параметром, характеризующим «степень» самоподобия СП, является параметр Хёрста.

Для выборочного случайного набора Xj (j =1,..., N) можно определить выборочное среднее

выборочную дисперсию

и интегральное отклонение

Определим изменчивость СП на интервале N как неубывающую функцию длины интервала

RN= maxDj- minDj. 1< j<N 1<j<N

Хёрстом было показано, что для большинства естественных процессов при больших значениях N выполняется соотношение

или иначе

Величина H получила название параметра Хёрста и лежит в интервале 0.5 1.0 H <<. Для процессов, не обладающих свойством самоподобия, H =0.5. Для самоподобных процессов с долгосрочной зависимостью этот параметр изменяется в пределах 0.7…0.9. Параметр β, который был введен выше для задания асимптотических свойств характеристик самоподобных СП, может быть выражен через параметр Хёрста:

b= 2-2 H.

Степень самоподобия процесса можно оценить другим способом: параметр Херста можно определить путем построения графика отношения log(R_N/S_N) в зависимости от log(N /2) при разных N и вычислить величину H как тангенс угла наклона полученной линии. Следует заметить, что полученное множество точек не будут лежать на одной линии, поэтому их следует аппроксимировать линией, например, по методу наименьших квадратов. Данная методика определения параметра Херста получила название R/S-метод.

R/S-метод дает лишь приближенное значение показателя Херста, поэтому для его вычисления целесообразно пользоваться несколькими методиками и сравнения полученных результатов. Рассмотрим метод определения величины H на основе периодограммного анализа.

Для самоподобного СП X = { xi } вычисляется периодограмма

где N - количество отсчетов временного ряда. Учитывая, что самоподобие влияет на характер спектра S (w), должен получаться график зависимости спектральной плотности вида

IN (w)»[w]1-2 H, приw®0.

Из последнего выражения следует, что множество случайных точек (log[ IN (w)];log(w)) будет располагаться линейно с коэффициентом наклона линии 1-2 H. На практике для вычисления оценки должны использоваться только нижние 10% частот, т. к. описанное выше поведение справедливо только для области частот, близких к нулю. Основным недостатком данного метода является большой объем вычислений при построении оценки показателя Херста.

5.3. Модели систем массового обслуживания

Допущения о пуассоновском характере потока заявок и о показательном распределении времени обслуживания позволяют применить в теории массового обслуживания аппарат марковских СП. Процесс, протекающий в физической системе, называется марковским (или процессом без последействия), если для каждого момента времени вероятность любого состояния системы в будущем p (t 0+ ∆ t) зависит только от состояния системы в настоящий момент p (t 0) и не зависит от того, каким образом система пришла в это состояние.

Рассмотрим СМО с конечным дискретным множеством состояний (рис. 5.9). Определим состояние xk как состояние СМО, соответствующее наличию в данный момент k занятых каналов. При этом система может изменять свое состояние xk дискретно в соответствующие дискретные моменты времени ti. При поступлении на вход СМО одной заявки система изменяет свое состояние с xk на xk +1, а при уходе одной заявки из системы и соответствующем освобождении одного канала - с xk на xk -1.

Рис. 5.9. Диаграмма состояний и переходов СМО

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

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

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