1. Главная
›
2. Архив
›
3. Вестник науки №12 (69) том 4
›
4. Научная статья № 224

  23 просмотров

Логинова Н.В.

  

РЕАЛИЗАЦИЯ АЛГОРИТМА ПОСТРОЕНИЯ ВЕРОЯТНОСТНЫХ ЦЕПОЧЕК С ПОЛИНОМИАЛЬНЫМ РОСТОМ С ИСПОЛЬЗОВАНИЕМ ПАКЕТА MATLAB *

  

Аннотация:
в настоящей статье представлен один из способом математического моделирования изменения динамики экономических данных – метод вероятностных цепочек. В работе подробно изучен один вид цепочек – цепочек с полиномиальным ростом. В целях реализации алгоритма построения цепочек с полиномиальным ростом автором разработана программа в пакете MATLAB. Была проведена оценка сложности разработанной программы. Кроме того, написанная программа применена к данным статьи платёжного баланса “Общие резервы” Германии, Франции, Китая и России. Показано, что с помощью разработанной автором программы можно выполнять прогноз динамики изменения исследуемых данных   

Ключевые слова:
динамические системы, вероятностные цепочки с полиномиальным ростом, анализ сложности алгоритмов, математическое моделирование, экстраполяция   

DOI 10.24412/2712-8849-2023-1269-1420-1434

УДК 004

Логинова Н.В.

старший инженер-программист в компании EPAM Systems,

выпускник аспирантуры СПбГУ по направлению подготовки

«Информатика и вычислительная техника»

(г. Санкт-Петербург, Россия)

 

РЕАЛИЗАЦИЯ АЛГОРИТМА ПОСТРОЕНИЯ

ВЕРОЯТНОСТНЫХ ЦЕПОЧЕК С ПОЛИНОМИАЛЬНЫМ

РОСТОМ С ИСПОЛЬЗОВАНИЕМ ПАКЕТА MATLAB

 

Аннотация: в настоящей статье представлен один из способом математического моделирования изменения динамики экономических данных – метод вероятностных цепочек. В работе подробно изучен один вид цепочек – цепочек с полиномиальным ростом. В целях реализации алгоритма построения цепочек с полиномиальным ростом автором разработана программа в пакете MATLAB. Была проведена оценка сложности разработанной программы. Кроме того, написанная программа применена к данным статьи платёжного баланса “Общие резервы” Германии, Франции, Китая и России. Показано, что с помощью разработанной автором программы можно выполнять прогноз динамики изменения исследуемых данных.

 

Ключевые слова: динамические системы, вероятностные цепочки с полиномиальным ростом, анализ сложности алгоритмов, математическое моделирование, экстраполяция.

 

1. Введение

В данной исследовательской работе рассмотрен метод моделирования и прогнозирования динамики изменения социально-экономических данных, используемый в контексте задач распределения ресурсов. Этот метод основан на применении одного класса дискретных динамических систем, а именно вероятностных цепочек. Если распределение ресурса между участниками процесса выражается в относительных долях, то модель динамики такого процесса описывает преобразование некоторого вероятностного вектора. Поэтому эти модели, предложенные и разработанные М. Сонисом и Д. Хьюинсом [1, 2, 3], получили название вероятностных цепочек. Таким образом, предложенные модели описываются дискретными динамическими системами, определенными на симплексе вероятностных векторов.

Вероятностные цепочки с логистическим и логарифмически-линейным ростом были успешно использованы в работах [4, 5, 6] для построения прогноза для данных различной природы. В настоящей статье детально рассмотрен один вид вероятностных цепочек – с полиномиальным ростом. В целях реализации алгоритма построения данного вида цепочек была разработана программа в пакете прикладных программ MATLAB. Кроме того, в работе рассмотрена сложность алгоритма построения цепочек с полиномиальным ростом.

Программа, написанная с использованием пакета MATLAB, применена для примера данных статьи платежного баланса “Общие резервы” Германии, Франции, Китая и России. Показано, что программа выполняет прогноз на заданный период времени, который может быть использован для исследования динамики изменения данных.

Приведём описание алгоритма построения вероятностных цепочек с полиномиальным ростом, реализованного в программе MATLAB [8].

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

Далее ставим задачу поиска матрицы коэффициентов Wmat для T+1 года.

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

N (n) – число стран, T (m) – период, для которого производится интерполяции, k – период, для которого производится экстраполяция. PData – массив исходных эмпирических данных, Temp — исследуемый в задаче период времени, по которому есть эмпирические данные. PX – подматрица матрицы PData c 1-ого года до m, PY – подматрица со второго года до m+1. PXX – матрица, состоящая из переменных , Titles — матрица, состоящая из индексов переменных . Kw – количество коэффициентов системы, Pw – количество коэффициентов в одном многочлене. Aeq – матрица, состоящая из записанных n раз единичных матриц размерности Pw. beq – вектор, состоящий их Pw элементов, где первые n элементов равны 1, оставшиеся элементы равны 2. С – блочно-диагональная матрица, состоящая из PXX, d – матрица PY, записанная в один столбец. A – матрица -E = (-1) ·E, b – нулевой вектор. w – искомый вектор, вычисляемый с помощью встроенной функции lsqlin. PY_pred — матрица, содержащая значения, полученные с помощью интерполяции. PY_prog — искомая матрица, содержащая спрогнозированные значения. ZeroCoef – матрица, состоящая из нулей и единиц, в зависимости от того, какие переменные в каждом из многочленов системы присутствуют или отсутствуют, wZeroCoef – матрица ZeroCoef, записанная в один столбец. Kw2 – количество коэффициентов системы, в случае, когда цепочки вычисляются с учётом ограничений и допущений. A2 и b2 – матрицы, заданные аналогично матрицам A и b, но с другой размерности с учетом значения Kw2. Aeq2 и C2 – матрицы, вычисляемые из матриц Aeq и C путём удаления столбцов, соответствующих нулевым элементам вектора wZeroCoef. d2 и beq2 – матрицы, содержащие те же значения, что и матрицы d и beq. w2 – вектор, вычисляемый с помощью встроенной функции lsqlin с новыми заданными матрицами C2, d2, A2, b2, Aeq2, beq2. w2tmp – искомый вектор, составленный из значений векторов wZeroCoef и w2. PY_pred2 – матрица, вычисленная аналогично матрице PY_pred с помощью матрицы Wmat2. PY_prog2 - искомая матрица, содержащая смоделированные данные, вычисленная аналогично матрице PY_prog с помощью матрицы Wmat2.

Далее алгоритм поиска приведен по шагам:

1. Задаём переменную N, в которую записываем число n, соответствующее количеству стран, переменную T, в которую записываем число m, соответствующее количеству лет.
2. Записываем в матрицу PData все значения за период Temp. Период состоит из количества лет m, для которого производится интерполяция и периода, для которых производится экстраполяция k. Тo есть Temp равно m+k лет по n странам. PData – матрица размерности (m+k) x n.
3. Разбиваем матрицу PData на две подматрицы PX (с первого года до m) и PY (со второго года до m+1) размерностями m x n.
4. Записываем матрицу PXX, которая будет содержать элементы вида и состоять из T строк, первые n столбцов матрицы соответствуют , затем n· (n-1)/2 столбцов попарных произведений . Также создаем матрицу Titles, для хранения индексов переменных. Строка названий столбцов матрицы содержит индексы переменных.
5. Записываем задачу в виде линейной системы. Задаём переменные Kw=n·n· (n+1)/2 – количество коэффициентов и Pw=n·(n+1)/2 – количество коэффициентов в одном многочлене.

Изначально есть задача в виде PXX·Wmat = PY. Мы записываем эту задачу в виде системы линейных уравнений для вектора из Kw коэффициентов в виде C·w=d.

Матрица C – это блочно-диагональная матрица PXX, записанная на главной диагонали n раз.

PXX имеет размеры m x n· (n+1)/2. Матрица C имеет размеры n·m (строк) x n·n· (n+1)/2 (столбцов). Каждый блок относится к своей стране.

Вектор d это матрица PY, столбцы которой записаны в один столбец. Матрица PY имеет размеры m · n. Вектор d имеет размеры m·n×1

6. С помощью встроенных функций MATLAB вычисляем матрицы A и b. A = -eye(Kw) и b = zeros(Kw,1). Задано ограничение типа неравенства A·w0. Задано условие неотрицательности всех коэффициентов во всех многочленах.
7. С помощью встроенных функций MATLAB вычисляем матрицы Aeq и beq. Aeq = repmat(eye(Pw),1,N). beq = [ones(N,1), 2·ones(Pw-N,1)]. Ограничение типа равенства Aeq·w = beq.
8. Таким образом, все искомые матрицы для решения системы с ограничениями с помощью встроенной функции lsqlin найдены. w=lsqlin(C,d,A,b,Aeq,beq) – решаем систему с ограничениями. Функция находит решение системы C·w=d, при ограничениях A·w<b, Aeq·w=beq, минимизируя сумму квадратов ошибок (SSE).

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

9. Полученный вектор w мы записываем по столбцам в матрицу Wmat. В каждом столбце i записаны коэффициенты многочлена для страны i. Вычисляем с помощью найденной матрицы PY_pred. PY_pred = PXX·Wmat. В отличие от PY, в матрицу PY_pred записываются значения, полученные с помощью найденных многочленов.
10. PY_prog(1:T,:) = PY_pred. PY_prog — это матрица прогнозных значений. Первые T строк берем из тренировочной задачи PY_pred остальные Temp - m -1 лет рассчитываем значения с помощью функции pred_next по предыдущему году, подставляя в уже посчитанные многочлены. Функция pred_next находит значения N многочленов с известными коэффициентами по вероятностному вектору PX.

 f = PXX·Wmat - вектор из квадратов и попарных произведений умножаем на матрицу коэффициентов, чтобы получить n новых прогнозируемых значений для следующего года [9].

 

4. Сложность построения алгоритма вероятностных цепочек с полиномиальным ростом

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

Доказательство

Сложность алгоритма определяется числом операций [10]. Рассмотрим операции, выполняемые программой, разработанной в MATLAB для построения цепочек с полиномиальным ростом:

• Операция нормирования данных имеет сложность .
• Построение вспомогательной матрицы PX имеет сложность .
• Построение вспомогательной матрицы PX имеет сложность .
• Операция вычисления матрицы PXX имеет сложность .
• Операция копирования матрицы PXX n раз имеет сложность .
• Решение системы с помощью встроенной в MATLAB функции lsqlin.

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

 

В итоге получаем, что сложность решения системы с помощью встроенной в MATLAB функции lsqlin составляет .

• Приведение решения к матричному виду имеет сложность .
• Построение прогноза имеет сложность .
• Оценка погрешности модели имеет сложность .

Общая сложность выполнения шагов 1-9 программы будет определяться выполнением функции lsqlin:
 +  +  +  +  +  +  +  +

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

• Операция копирования матрицы PXX n раз имеет сложность .
• Решение второй системы с помощью встроенной в MATLAB функции lsqlin имеет сложность .
• Приведение решения к матричному виду имеет сложность .
• Построение второго прогноза имеет сложность .
• Оценка погрешности модели имеет сложность .

Общая сложность выполнения программы будет определяться выполнением функции lsqlin:
 +  +  +  +

По итогам оценки операций выполнения алгоритма программы для построения вероятностных цепочек с полиномиальным ростом делаем вывод, что сложность определяется самой трудоемкой операцией — выполнением функции lsqlin, которая была оценена снизу как решение задачи МНК. Общая сложность составляет не менее O(n⁹) операций, где n размер вероятностного вектора.

Что и требовалось доказать.

 

5. Пример применения вероятностных цепочек с полиномиальным ростом к моделированию данных статьи платежного баланса “Общие резервы” Германии, Франции, Китая и России за 2001–2015 гг.

Рассмотрим данные по статье ПБ “Общие резервы” Германии, Франции, Китая и России за 2001–2015 гг., опубликованные Группой Всемирного банка [11]. Данные представлены в миллионах текущих долларов США. Данные с 2001 по 2010 гг. приведены в Таблице 1.

 

Таблица 1. Общие резервы (включая золото)

Германии, Франции, Китая и России

Год	Россия	Китай	Германия	Франция
2001	36303	220057	82132	58637
2002	48326	297739	89143	61697
2003	78409	416199	96835	70762
2004	126258	622949	97170	77353
2005	182272	831410	101676	74360
2006	303773	1080756	111637	98239
2007	478822	1546365	135932	115487
2008	426279	1966037	138564	103306
2009	439342	2452899	179040	131786
2010	479222	2913712	215978	165852

 

На основе представленных эмпирических данных построим цепочки с полиномиальным ростом. Построим полиномы вида степени 2, c количеством видов единиц ресурсов равным 4 в рамках одной совокупности. В качестве исходных данных, выбранных для нахождения коэффициентов системы  возьмём данные за 2001 по 2010 гг. Прогноз будем строить на 2011–2015 гг.

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

На основе полученных данных построим графики изменения показателя общих резервов (включая золото) Германии, Франции, Китая и России за 2002–2015 гг. На Рисунке 1 представлены графики изменения эмпирических данных по показателю общих резервов (включая золото) Германии, Франции, Китая и России.

 

Рисунок 1. Статья ПБ «Общие резервы» Германии, Франции,

Китая и России. Эмпирические данные.

 

На Рисунке 2 представлены графики изменения смоделированных данных по показателю общих резервов (включая золото) Германии, Франции, Китая и России.

 

Рисунок 2 - Статья ПБ «Общие резервы» Германии, Франции, Китая и России. Вероятностные цепочки с полиномиальным ростом.

 

Чтобы оценить точность построенной модели, вычислим коэффициент корреляции между эмпирической динамикой и смоделированными данными. Коэффициент корреляции между эмпирическими данными и данными, полученными в результате построения цепочек с полиномиальным ростом равен 0,998841846. Таким образом, можно сделать вывод о том, что модель вероятностных цепочек с полиномиальным ростом может быть использования для построения прогноза исследуемых данных.

 

6. Заключение

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

       В работе написанная в MATLAB программа применена к набору данных статьи платёжного баланса “Общие резервы” Германии, Франции, Китая и России за 2001–2015 гг. Интерполяция данных проведена на период с 2002 по 2010 год, и экстраполяция на период с 2011 по 2015 год. Смоделированные данные были оценены с помощью коэффициента корреляции. Найденные значения коэффициента корреляции показывают, что модель с полиномиальным ростом позволяет вычислить достаточно точный прогноз.

 

СПИСОК ЛИТЕРАТУРЫ:

 

1. Hewings, G. J. D. Regional industrial analysis and development / Goffrey J. D. Hewings. – London : Methuen & Co, 1977. – 180 p.
2. Social and demographic accounting / Geoffrey J. D. Hewings, Moss Madden. – Cambridge etc. : Cambridge univ. press, 1995. – IX, 242 p.
3. Sonis, M. The Three-sector Growth Hypothesis and the Euler-Malthus Economic growth model: Application to the analysis of GDP dynamics of Brazil, 1985–2004–2020 / M. Sonis, C. R. Azzoni, G. J. D. Hewings // The Fifth International Conference on Mathematical Modeling and Computer Simulation of Materials Technologies. – 2008. – P. 153–163.
4. Афанасьева Е.В. Моделирование процессов потребления экономических ресурсов с помощью вероятностных цепочек (на примере стран Западной Европы)//Научно - технические ведомости СПбГПУ: Информатика. Телекоммуникации. Управление. — СПб.: Политехн. ун-та, 2011. — № 3. — С. 93-97.
5. Афанасьева Е.В. Моделирование процессов распределения ресурсов с помощью вероятностных цепочек // Дифференциальные уравнения и процессы управления. — 2011. — № 3.
6. Логинова, Н. В. Об одном методе моделирования динамики социально-экономических процессов / Н. В. Логинова // Компьютерные инструменты в образовании. – 2018. – № 2. – С. 14–24.
7. Sonis, M. Discrete Non-Linear Probabilistic Chains / M. Sonis // Functional-Differential Equations. – Ariel, Israel 2003.
8. Archived documentation for previous versions of Matlab. // Instruction – URL: https://www.mathworks.com/help/documentation-center (дата обращения: 23.11.2023).
9. Логинова, Н. В. Вероятностные цепочки с полиномиальным ростом как модель распределения ресурсов / Н. В. Логинова // Компьютерные инструменты в образовании. – 2020. – № 3. – С. 56–69.
10. Вирт Никлаус. Алгоритмы и структуры данных. / Никлаус Вирт – М.: ДМК Пресс, 2010. – 272 с.
11. World Bank Open Data: official site. – Washington, D.C. – URL: https://data.worldbank.org (дата обращения: 06.12.2023).

 

Loginova N.V.

EPAM Systems

St. Petersburg State University

(St. Petersburg, Russia)

 

IMPLEMENTATION OF ALGORITHM

FOR CONSTRUCTING PROBABILITY CHAINS WITH

POLYNOMIAL GROWTH USING MATLAB PACKAGE

 

Abstract: this article presents one of the methods of mathematical modeling of changes in the dynamics of economic data – the method of probabilistic chains. In this paper, one type of chains is studied in detail – chains with polynomial growth. In order to implement an algorithm for building chains with polynomial growth, the author has developed a program in the MATLAB package. The complexity of the developed program was assessed. In addition, the written program is applied to the data of the balance of payments item “General Reserves" of Germany, France, China and Russia. It is shown that with the help of the program developed by the author, it is possible to predict the dynamics of changes in the studied data.

 

Keywords: dynamic systems, probability chains with polynomial growth, algorithm complexity analysis, mathematical modeling, extrapolation.

  

Полная версия статьи PDF

Номер журнала Вестник науки №12 (69) том 4

  

Ссылка для цитирования:

Логинова Н.В. РЕАЛИЗАЦИЯ АЛГОРИТМА ПОСТРОЕНИЯ ВЕРОЯТНОСТНЫХ ЦЕПОЧЕК С ПОЛИНОМИАЛЬНЫМ РОСТОМ С ИСПОЛЬЗОВАНИЕМ ПАКЕТА MATLAB // Вестник науки №12 (69) том 4. С. 1420 - 1434. 2023 г. ISSN 2712-8849 // Электронный ресурс: https://www.вестник-науки.рф/article/12042 (дата обращения: 19.05.2024 г.)

Альтернативная ссылка латинскими символами: vestnik-nauki.com/article/12042

---

Нашли грубую ошибку (плагиат, фальсифицированные данные или иные нарушения научно-издательской этики) ?
- напишите письмо в редакцию журнала: zhurnal@vestnik-nauki.com

Вестник науки СМИ ЭЛ № ФС 77 - 84401 © 2023.    16+

---

* В выпусках журнала могут упоминаться организации (Meta, Facebook, Instagram) в отношении которых судом принято вступившее в законную силу решение о ликвидации или запрете деятельности по основаниям, предусмотренным Федеральным законом от 25 июля 2002 года № 114-ФЗ 'О противодействии экстремистской деятельности' (далее - Федеральный закон 'О противодействии экстремистской деятельности'), или об организации, включенной в опубликованный единый федеральный список организаций, в том числе иностранных и международных организаций, признанных в соответствии с законодательством Российской Федерации террористическими, без указания на то, что соответствующее общественное объединение или иная организация ликвидированы или их деятельность запрещена.