APPROXIMATION OF FUNCTIONS OF DENSITY OF DISTRIBUTIONS WITH HEAVY TAILS THE PRONY METHOD

Abstract

At present the actual problem in the study of traffic multiservice network is the presence of self-similarity, which influences the characteristics of the node processing packages. In the article the questions of the decomposition of arbitrary functions in series of exponents and approximation of an arbitrary density of distribution of the Prony method.

Full Text

Метод Прони - это метод моделирования выборочных данных в виде линейной комбинации экспоненциальных функций (экспонент). При помощи данного метода осуществляется аппроксимация функций с использованием некоторой детерминированной экспоненциальной модели [1]. Пусть статистические характеристики интервалов времени между пакетами и случайные длительности обслуживания подчиняются распределениям с «тяжелыми» хвостами: Вейбулла, Парето, логнормальное. Необходимо найти аппроксимацию этих законов рядами экспоненциальных функций. Функция распределения Вейбулла имеет вид: F(x) = 1 — е р ; х > О, а > О, /? > О, где а - параметр формы; ß - масштабный параметр [2], которому соответствует плотность распределения: _(—)“ f(x) = aß~axa~1e ß . (1) Используя метод Прони (общего вида), аппроксимируем функцию ПРВ Вейбулла суммой экспонент [3]. Выберем известные значения (отчеты) функции /(х) при х( -1;2...N. Будем искать аппроксимирующую функцию yr(x): к ^(х) = Z htf1, к < N12, (2) 1=1 X ± ja где Zt=e 1 1. Пусть функция /(х) такова, что существуют коэффициенты [3] ••• ак» ^'ls-^'2 ••• ^к И ®1»®2 ••• ’ при которых сумма y/fix) в (2) интерполирует /О) в узлах i = \\2...N. Пусть многочлен «Инфокоммуникационные технологии» Том 11, № 4, 2013 Киреева Н.В., Чупахина Л.Р. 25 1 + dxz + d2z2 +... + dkzk (3) Я ± j<J имеет нулями числа zt=e 1 1, I = 1; 2... к. Тогда для каждого j = \\1...k имеет место равенство [3]: Ду) + dJU +1) +... + dJU + к) = 0 . (4) Решим систему (5) при известных значениях Ду')> найдем коэффициенты dk и затем вычислим нули zt, используя многочлен (3). Отсюда найдем искомые значения величин: А = In <J1 = argzz, / = 1; 2... к. (5) Если значение Я, >0, берем его со знаком минус. Преобразуем (2) в следующем виде. Если zz - экспонента с вещественным показателем, то соответствующее слагаемое оставим без изменения. Если zl и zz+1 образуют комплексносопряженную пару A,z ± jal, то заменим zz на X X е 1 sin а ^ zz+1 на е 1scosa . Для упрощения примем Xj = і, тогда по известным значениям z; и Дг) найдем коэффициенты h, решив систему уравнений до = 2ä,z*» i=l-N- (6) 1=1 Алгоритм аппроксимации функции ПРВ с помощью метода Прони Для аппроксимации произвольной ПРВ методом Прони необходимо выполнить следующие действия. 1. Решить систему уравнений (4), чтобы найти коэффициенты dк. 2. Найти нули функции zz по формуле (3). 3. Вычислить через (5) коэффициенты A,ZH а;. 4. Решить систему уравнений (6), найти коэффициенты h и записать выражение (2). Реализуем данный алгоритм для функции ПРВ Вейбулла fix) (1) при а = 10 и /? = 2 (см. рис. 1). В нашем случае рассматриваем отчеты для случая N= 20. Численные значения искомых коэффициентов представлены в таблице 1. Таблица 1. Значения коэффициентов ПРВ Вейбулла / Искомые значения X, О/ h 1 -0,4318 -1,0001 1,232 2 -0,4318 -1,0001 -556,152 3 -0,4203 -2,8656 -13330 4 -0,4203 -0,2760 -166000 5 -0,3097 0,3813 405,396 6 -0,3097 2,7603 9444 7 -0,2216 2,2225 7111 8 -0,2216 0,9191 -48,22 9 -0,1690 1,3609 1,038 10 -0,1690 1,7807 167000 При построении модели (см. рис. 2) учтено, что аппроксимирующее выражение для ПРВ должно удовлетворять условию нормировки СО §y/ix)dx = 1. Выражение нормирующей коно станты const = 1 h к< N12. х = °о je = 0 к ^ z ln(z ) 1 I = 1 I I Результат аппроксимации ПРВ Вейбулла (const = 63371, при нижнем пределе x = 0 и верхнем X = 4) представлен на рис. 2. Аналитическое выражение аппроксимирующей функции имеет вид: ю Л (х- 1) h е ' cos((T (х -1)) і V{x)= D( і = і + ht eÀ‘<х ~1} sin(crz (х -1))) і + (7) Рис. 2. Сравнение двух ПРВ Вейбулла «Инфокоммуникационные технологии» Том 11, № 4, 2013 26 Киреева Н.В., Чупахина Л.Р. После построения аппроксимирующей функции у/{х) заметим, что некоторые ее значения находятся в отрицательной области. Для удовлетворения свойству ПРВ будем искать исправленное значение у/(х) из условий ОО \2 J{y/{x), у/(х)) = wl §(у/(х) - цг{х)) dx + о (8) + w2 J (у/(х)У dx —» min, *i где (xvx2) - это отрезок, при котором ^(х)<0, a w;,iv2 - положительные веса, определяемые экспериментально из необходимых условий минимума функционала полученной системы линейных алгебраических уравнений (СЛАУ). Находим СЛАУ, решая d J(y/(x),y/(x)) n f 1 1П ~ ~ — U, / - 1 ... і и относительно n,. d ht Для нашего случая i=i J(i//(x),ij/(x)) = Wj J (УО) - E h,z*~l)2dx + 0,5 + W2 J (E h,z*~1)2 dx 2,4 / = 1 где l = 1 ...k;k < ІУ/2; з з 10 = 2w] J(^(x)- E A;z* ])z* ldx+ 0,5 10 + 2w2 f( Efyz* l)z* 'dx, 2,4 / = 1 10 Ей (w fz* 'z* 1fiüx — 1 1 J / і 0,5 3 J z* 'z* 'dx) = wl J y/(x) z* 'dx. I = 1 2,4 2,4 Затем подставляем в (7) найденные значения А;, приравнивая весовые функции wl—w2— 1, получаем следующую аппроксимацию. Погрешность отклонения аппроксимирующей функции у/{х) от f{x) зависит от некоторых величин ^ ир. В нашем случае, если учесть при построении функции у/{х) величины отклонений Ç — 2,5 ; ц — 2,5 ; аппроксимация ПРВ Вейбулла ух{х) наиболее близка к реальной. ю у/{х) = Е (AzeA'w 1 м) cos(crz(x£ -1-м) + 1=1 + hj ея‘ sin(crz (х£ -1 - /и)). Рис. 3. Сравнение двух ПРВ Вейбулла с учетом условия (8) Для распределения Парето реализуем аналогичный алгоритм аппроксимации ПРВ методом Прони. Плотность распределения Парето имеет следующий вид (см. рис. 4): Дх) = ^(-Г\х>@ а>0, ß> 0, ß X где а - параметр формы, ß - масштабный параметр [2]. з 2.5 2 1.5 1 0,5 О X 0 12 3 4 Рис. 4. Функция ПРВ Парето при а = 10 и ß = 0,5 Таблица 2. Значения коэффициентов ПРВ Парето № пп Искомые значения / h О/ h 1 -1,705 -1,946 7,86Е+09 2 -1,705 -1,194 -1,46Е+09 3 -1,683 -2,7447 8,37Е+08 4 -1,683 -0,396 -5,85Е+09 5 -1,706 0,449 -2,74Е+07 6 -1,706 2,691 6,67Е+08 7 -1,876 1,303 8,40Е+05 8 -1,876 1,837 -3,63Е+09 9 -3,563 1,570 1,03Е+09 10 -8,0721 1,570 2,92Е+12 «Инфокоммуникационные технологии» Том 11, № 4, 2013 Киреева Н.В., Чупахина Л.Р. 27 -Л-о --- І 1 1 1 \ •л_. < G.5 1 1.5 2 2,5 3 3,5 4 Рис. 5. Сравнение двух ПРВ Парето Результат аппроксимации ПРВ Парето (const = 8,82912E+14, при нижнем пределе x = 0 и верхнем X = 4) представлен на рис. 5. С учетом отклонений £ = 1 и /л = 0,3 получим аппроксимирующую функцию которая наиболее близко приближается к реальной ПРВ Парето fix) - см. рис. 6. Рис. 6. Сравнение двух ПРВ Парето с учетом погрешности Для логнормального распределения реализуем аналогичный алгоритм аппроксимации ПРВ методом Прони. Плотность логнормального распределения имеет вид: /О) = л/ 2па2х2 -, X > 0, — 00 < fl < оо о > О, где о - параметр формы, fi - масштабный параметр [2]. Результат аппроксимации ПРВ логнормального распределения (const = 2,52725E+11, при нижнем пределе x = 0 и верхнем X = 3) представлен на рис. 8. В нашем случае, если учесть при построении функции ij/ix) условие (8) и величины отклонений Ç — 1,4 И fl = 1,7 ; получим результат, показанный на рис. 9. Рис. 7. Функция ПРВ логнормального распределения при ц = 0,1 и а = 0,2 Таблица 3. Значения коэффициентов логнормальной ПРВ Искомые значения 1 h О; hi 1 -1,182 -1,931 -2,45Е+09 2 -1,182 -1,210 2,38Е+08 3 -1,259 -0,544 1.64Е+09 4 -1,259 -2,597 1.93Е+09 5 -1,3062 0,032 7,78Е+08 6 -1,306 3,108 -8,71Е+08 7 -1,284 2,485 -1,74Е+09 8 -1,284 0,656 -1,52Е+06 9 -1,317 1,864 1,50Е+09 10 -1,317 1,276 1.66Е+05 Рис. 8. Сравнение двух ПРВ логнормального распределения Рис. 9. Сравнение двух ПРВ логнормального распределения с учетом (8) «Инфокоммуникационные технологии» Том 11, № 4, 2013 28 Заключение При реализации данного алгоритма точность аппроксимации зависит от количества выбранных на начальном этапе отчетов N функции f (х) которую необходимо интерполировать. В статье рассмотрены частные случаи для наиболее известных распределений с «тяжелым» хвостом, так как на практике и в многочисленных публикациях доказано, что реальный трафик сети по своим свойствам приближен к ним. Таким образом, аппроксимация суммой затухающих экспонент может описать функцию ПРВ. Анализ и расчет характеристик мультисервисно-го трафика, поступающего на вход и обслуживаемого в звене системы, является актуальной задачей. Данный алгоритм может также подходить для исследования частных случаев аппроксимации ПРВ, по законам которых циркулируют пакеты трафика в системе СМО типа G/G/1, при условии вещественного значения z!. При исследовании функции ПРВ [4] не