Численные эксперименты по исследованию скорости сходимости релаксационного итерационного алгоритма при построении нелинейных моделей

В работе c помощью численных экспериментов исследована скорость сходимости к точному решению при построении нелинейных моделей обобщённым релаксационным итерационным алгоритмом (ОРИА) МГУА и показано, что она на порядок ниже, чем аналогичная скорость при построении линейных моделей....

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2012
Hauptverfasser:	Павлов, А.В., Павлов, В.А.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2012
Schriftenreihe:	Індуктивне моделювання складних систем
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/45967
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Численные эксперименты по исследованию скорости сходимости релаксационного итерационного алгоритма при построении нелинейных моделей / А.В. Павлов, В.А. Павлов // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2012. — Вип. 4. — С. 145-157. — Бібліогр.: 8 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-45967
record_format	dspace
spelling	irk-123456789-459672013-06-22T03:20:33Z Численные эксперименты по исследованию скорости сходимости релаксационного итерационного алгоритма при построении нелинейных моделей Павлов, А.В. Павлов, В.А. В работе c помощью численных экспериментов исследована скорость сходимости к точному решению при построении нелинейных моделей обобщённым релаксационным итерационным алгоритмом (ОРИА) МГУА и показано, что она на порядок ниже, чем аналогичная скорость при построении линейных моделей. У роботі за допомогою чисельних експериментів досліджена швидкість збіжності до точного розв'язку при побудові нелінійних моделей узагальненим релаксаційним ітераційним алгоритмом (УРIА) МГУА і показано, що вона на порядок нижче, ніж аналогічна швидкість при побудові лінійних моделей. The paper investigates convergence rate of generalized relaxational iterative algorithm (GRIA) of GMDH in case with convergence to solution (nonlinear model) via numerical experiments. Convergence rate of GRIA in this case is one degree lower then in case with convergence to linear models. 2012 Article Численные эксперименты по исследованию скорости сходимости релаксационного итерационного алгоритма при построении нелинейных моделей / А.В. Павлов, В.А. Павлов // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2012. — Вип. 4. — С. 145-157. — Бібліогр.: 8 назв. — рос. XXXX-0044 http://dspace.nbuv.gov.ua/handle/123456789/45967 681.513.8 ru Індуктивне моделювання складних систем Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	В работе c помощью численных экспериментов исследована скорость сходимости к точному решению при построении нелинейных моделей обобщённым релаксационным итерационным алгоритмом (ОРИА) МГУА и показано, что она на порядок ниже, чем аналогичная скорость при построении линейных моделей.
format	Article
author	Павлов, А.В. Павлов, В.А.
spellingShingle	Павлов, А.В. Павлов, В.А. Численные эксперименты по исследованию скорости сходимости релаксационного итерационного алгоритма при построении нелинейных моделей Індуктивне моделювання складних систем
author_facet	Павлов, А.В. Павлов, В.А.
author_sort	Павлов, А.В.
title	Численные эксперименты по исследованию скорости сходимости релаксационного итерационного алгоритма при построении нелинейных моделей
title_short	Численные эксперименты по исследованию скорости сходимости релаксационного итерационного алгоритма при построении нелинейных моделей
title_full	Численные эксперименты по исследованию скорости сходимости релаксационного итерационного алгоритма при построении нелинейных моделей
title_fullStr	Численные эксперименты по исследованию скорости сходимости релаксационного итерационного алгоритма при построении нелинейных моделей
title_full_unstemmed	Численные эксперименты по исследованию скорости сходимости релаксационного итерационного алгоритма при построении нелинейных моделей
title_sort	численные эксперименты по исследованию скорости сходимости релаксационного итерационного алгоритма при построении нелинейных моделей
publisher	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
publishDate	2012
url	http://dspace.nbuv.gov.ua/handle/123456789/45967
citation_txt	Численные эксперименты по исследованию скорости сходимости релаксационного итерационного алгоритма при построении нелинейных моделей / А.В. Павлов, В.А. Павлов // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2012. — Вип. 4. — С. 145-157. — Бібліогр.: 8 назв. — рос.
series	Індуктивне моделювання складних систем
work_keys_str_mv	AT pavlovav čislennyeéksperimentypoissledovaniûskorostishodimostirelaksacionnogoiteracionnogoalgoritmapripostroeniinelinejnyhmodelej AT pavlovva čislennyeéksperimentypoissledovaniûskorostishodimostirelaksacionnogoiteracionnogoalgoritmapripostroeniinelinejnyhmodelej
first_indexed	2025-07-04T05:01:17Z
last_indexed	2025-07-04T05:01:17Z
_version_	1836691256815648768
fulltext	Павлов А.В., Павлов В.А Індуктивне моделювання складних систем, випуск 4, 2012 145 УДК 681.513.8 ЧИСЛЕННЫЕ ЭКСПЕРИМЕНТЫ ПО ИССЛЕДОВАНИЮ СКОРОСТИ СХОДИМОСТИ РЕЛАКСАЦИОННОГО ИТЕРАЦИОННОГО АЛГОРИТМА ПРИ ПОСТРОЕНИИ НЕЛИНЕЙНЫХ МОДЕЛЕЙ А.В. Павлов1, В.А. Павлов2 1Международный научно-учебный центр информационных технологий и систем НАНУ и МОНУ 2Открытый международный университет развития человека "Украина",г. Киев Me_ovechka@bigmir.net, vapavlo@bk.ru У роботі за допомогою чисельних експериментів досліджена швидкість збіжності до точного розв'язку при побудові нелінійних моделей узагальненим релаксаційним ітераційним алгори- тмом (УРIА) МГУА і показано, що вона на порядок нижче, ніж аналогічна швидкість при побудові лінійних моделей. Ключові слова: метод групового урахування аргументів, узагальнений релаксаційний ітера- ційний алгоритм, швидкість збіжності, нелінійні моделі. The paper investigates convergence rate of generalized relaxational iterative algorithm (GRIA) of GMDH in case with convergence to solution (nonlinear model) via numerical experiments. Conver- gence rate of GRIA in this case is one degree lower then in case with convergence to linear models. Key words: group method of data handling, generalized relaxational iterative algorithm, conver- gence rate, nonlinear models. В работе c помощью численных экспериментов исследована скорость сходимости к точному решению при построении нелинейных моделей обобщённым релаксационным итерацион- ным алгоритмом (ОРИА) МГУА и показано, что она на порядок ниже, чем аналогичная ско- рость при построении линейных моделей. Ключевые слова: метод группового учёта аугментов, обобщённый релаксационный итераци- онный алгоритм МГУА, скорость сходимости, нелинейные модели. Вступление В настоящее время мы часто сталкиваемся с задачами моделирования объектов (процессов), которые описываются большим количеством (больше 300) признаков (аргументов). Напомним постановку задачи. Задана матрица данных Х, dim X = nW × m, где т – количество входных переменных, nW – количество наблюдений (точек), и вектор у выходной пере- менной y, dim y = nW × 1. Выходная переменная y измеряется с помехой ξ. Предполагается ее аддитивность, некоррелированность, математическое ожи- дание М(ξ ) = 0, неизвестная дисперсия σ2 постоянна и неизвестен закон рас- пределения. Пусть задан класс структур моделей Ψ. Необходимо найти опти- мальную по минимуму заданного критерия CR модель ),(** ff Xfy Θ=   , (1) определяемую как )),(,(minarg* f f Xfyf Θ= Ψ∈  CR , (2) mailto:Me_ovechka@bigmir.net mailto:vapavlo@bk.ru Численные эксперименты по исследованию скорости сходимости Індуктивне моделювання складних систем,випуск 4, 2012 146 где оценки параметров fΘ  , 1dim ×=Θ ff s  , для каждой f(Х, Θf) ∈ Ψ – это решение задачи: )),(,(minarg ff Xfy ff Θ=Θ ℜ∈Θ QR s  . (3) Здесь QR(⋅) – критерий качества решения задачи оценивания параметров, CR(⋅) – критерий качества решения задачи выбора оптимальной модели. Именно в такой постановке задачи формулируется метод группового учё- та аргументов (МГУА), предложенный А.Г. Ивахненко, для ее решения. Алго- ритмы МГУА строят модели (1), линейные по вектору параметров Θf. Все алго- ритмы МГУА можно разделить на переборные и итерационные. Последние бы- ли разработаны для решения задачи (2), (3) при большом количестве аргумен- тов. Итерационные алгоритмы, в свою очередь, делятся на релаксационные и многорядные алгоритмы. Для итерационных алгоритмов (далее алгоритмов) важным является их сходимость к точному решению (истинной модели). С момента публикации статьи о первом алгоритме [1] исследованию их сходимости уделялось крайне мало внимания. Из ранних работ следует отметить работу [2], где теоретически доказывается сходимость алгоритма CML (алгоритм релаксационного типа) к точному решению. Этот алгоритм строит модели линейные, как по параметрам Θf, так и по переменным xi, mi ,1= . В работе [3] на нескольких примерах по- строения линейных и нелинейных по входным переменным моделей показана сходимость обобщённого итерационного алгоритма к точному решению; в [4] разработана принципиально новая методика проведения численных (компью- терных) экспериментов, в соответствии с которой устанавливается не только факт сходимости алгоритма, но и исследуется скорость сходимости, а также условия, от которых она зависит. 1. Постановка задачи Целью данной работы является исследование скорости сходимости с по- мощью методики, изложенной в [4], обобщённого релаксационного итерацион- ного алгоритма (ОРИА) МГУА, описанного в работе [5]. Если в [4] скорость сходимости ОРИА исследовалась при построении линейных моделей, то в дан- ной работе исследуются нелинейные модели. Кратко опишем методику иссле- дования скорости сходимости итерационных алгоритмов. 2. Методика проведения численных экспериментов для исследования скорости сходимости итерационных алгоритмов Определим скорость сходимости итерационного алгоритма как количе- ство итераций r, необходимых для получения решения с заданной точностью ε. Как правило, при проведении численных экспериментов r существенно зави- сит от свойств матрицы, подаваемой на вход алгоритма, например: от коррели- рованности её строк/столбцов, числа её обусловленности и др. Поэтому к ряду Павлов А.В., Павлов В.А Індуктивне моделювання складних систем, випуск 4, 2012 147 исследуемых в эксперименте параметров (свобода выбора F на каждой итера- ции, количество st одночленов модели и др.) следует добавить характеристику данных, влияющую на скорость сходимости. Не ограничивая общности, пусть это будет одна характеристика Pr. При проведении численных экспериментов используют Процедуру Гене- рации Матрицы (ПГМ), в основе которой лежит Генератор Псевдослучайных Чисел (ГПЧ). В экспериментах необходимо генерировать матрицы со свойства- ми, не влияющими на скорость сходимости алгоритма. Однако с учетом осо- бенности получения матриц параметр Pr является случайной величиной. По- этому необходимо настроить ПГМ так, чтобы математическое ожидание пара- метра Pr генерируемых матриц было близко к заданному значению. Методика исследования скорости сходимости итерационных алгоритмов состоит из следующих этапов: Этап 1. Определить параметры ПГМ и их значения, позволяющие гене- рировать матрицы с оценкой математического ожидания характеристики дан- ных Pr, близкой к заданному значению. Этап 2. Исследовать скорость сходимости алгоритма при изменении зна- чения параметра Pr и неизменных значениях его управляющих параметров. Этап 3. Для каждого из управляющих параметров алгоритма исследовать скорость сходимости при изменении его значения и неизменных значениях остальных параметров (включая параметр Pr). Каждый из этапов метода состоит из двух шагов: Шаг 1. Определить количество реализаций RN, удовлетворяющее задан- ному значению δ для гистограмм распределения параметра r при заданном значении исследуемого параметра par, par ∈ {Pr, F, st}. 1.1 Сгенерировать исходную матрицу с помощью ПГМ. 1.2 Построить модель с помощью исследуемого алгоритма, подав на его вход сгенерированную матрицу. 1.3 Добавить полученное значение r* в гистограмму. 1.4 Выполнить пункты 1.1-1.3 заданное количество реализаций RN. 1.5 Выполнить пункт 1.4 для разных значений RN, увеличивая его с не- которым интервалом до тех пор, пока мера отличия гистограмм для двух по- следовательных значений RN не станет удовлетворять заданному значению δ. Шаг 2. Построить гистограммы распределения параметра r* для разных значений параметра par, используя найденное количество реализаций RN. На первом этапе метода par = Pr. При этом на шаге 2 необходимо найти значения параметров ПГМ, при которых оценка математического ожидания па- раметра Pr генерируемой матрицы близка к заданному значению. Согласно [5] ОРИА содержит два метода оценивания параметров, три ме- тода расчёта критериев селекции и два генератора структур при построении не- линейных моделей: с направленным и полным перебором на каждой итерации. Если сходимость ОРИА к точному решению по внутреннему критерию RSSA не зависит от методов оценивания параметров и расчёта критериев селекции, то от генератора структур она зависит. В частности, алгоритм сходится при исполь- зовании генератора с полным перебором (в [6] теоретически доказаны различ- Численные эксперименты по исследованию скорости сходимости Індуктивне моделювання складних систем,випуск 4, 2012 148 ные виды сходимости), однако не существует такого доказательства для алго- ритма с генератором направленного перебора. Поэтому в данной работе иссле- дуется: насколько быстро сходится и от чего зависит скорость сходимости РИА, использующего генератор с полным перебором (ПП) структур на каждой итерации, при построении нелинейных моделей. Обозначим этот алгоритм РИА ПП. 3. Применение методики для исследования скорости сходимости РИА ПП В экспериментах ХA – исходная матрица данных, где её столбцы xi, mi ,1= соответствуют входным переменным хі. Для построения нелинейных моделей предварительно формируется матрица ZA, содержащая вектор- столбцы, отвечающие всем возможным произведениям исходных переменных xi, mi ,1= без повторов, ограниченным заданной максимальной степенью pow > 1, dim ZA = nW × l, mCl pow powm −−= + 1 . Для описания ПГМ введём обозначения: slin – количество линейных ис- тинных аргументов; smult – количество мультипликативных истинных аргумен- тов; WA – выходная матрица ПГМ, WA = (HAyA), dim WA = nA × (M + 1); nA – число наблюдений; M – количество аргументов; )( AAA ZXH = . Входными па- раметрами ПГМ являются: M, nA, slin, smult. Блок схема алгоритма представлена на рис. 1. В ПГМ используется один из широко известных генераторов псевдо- случайных чисел – Mersenne Twister MT19937 из открытой библиотеки C++ Boost [7], период, повторения случайной последовательности которого, состав- ляет 219937 [8]. Псевдослучайные числа генерируются по равномерному закону распределения в интервале [0; 1]. Можно показать, что скорость сходимости РИА ПП зависит от такой ха- рактеристики матрицы ХA, как мера ортогональности системы её вектор- столбцов. Обозначим центрированные по отношению к среднему и нормиро- ванные по величине среднеквадратичного отклонения σ вектор-столбцы матри- цы ХА в виде матрицы AX ~~ . Очевидно, что если вектор-столбцы матрицы AX ~~ образуют ортогональную систему, то корреляционная матрица ΣХ = A T AXX ~~~~ яв- ляется единичной с детерминантом, равным 1. Поэтому в качестве меры орто- гональности системы вектор-столбцов матрицы AX ~~ выбран детерминант d корреляционной матрицы ΣХ. Поскольку для меры ортогональности не важен знак парной корреляции между вектор-столбцами матрицы AX ~~ , пусть матрица ΣХ содержит модули значений. Следовательно, ]1;0[∈d , причём, если d = 0, то матрица ΣХ вырожденная, а при d = 1 она единичная. Павлов А.В., Павлов В.А Індуктивне моделювання складних систем, випуск 4, 2012 149 Рис. 1. Блок схема процедуры генерации матрицы Скорость сходимости алгоритма исследуется при условии, что матрица ХA содержит только истинные аргументы. Сходимость РИА ПП отслеживается по разности критерия NRSSА лучших моделей на двух соседних итерациях: 1 1, * , ++ ∆=− rrArA NRSSNRSS . Останов алгоритма осуществляется по условию ε<∆ +1r , где ε – заданная точность моделирования. Формула для расчёта * ,rANRSS имеет вид: ∑∑ == −= AA n i iA n i irAiArA yyyNRSS 1 2 , 1 2* ,,, * , ~)~~(  , где iAy , ~ – центрированное на выборке обучения А значение yA,i вектора yA; * ,, ~ irAy  – соответствующее центрированное значение выхода лучшей модели r-й итера- ции. Численные эксперименты по исследованию скорости сходимости Індуктивне моделювання складних систем,випуск 4, 2012 150 Применим методику исследования скорости сходимости итерационных ал- горитмов для анализа свойств РИА ПП при построении нелинейных моделей. Этап 1. На первом этапе методики следует определить параметры ПГМ и их значения, позволяющие генерировать матрицы с оценкой математического ожидания детерминанта d, близкого к заданному значению. Однако, прежде всего, необходимо определить количество реализаций RN, при котором ре- зультаты могут быть признаны достоверными. Процедура определения RN основывается на сравнении гистограмм рас- пределения параметра r* при двух разных значениях RN, где большее из них взято за эталон. Если погрешность гистограммы при меньшем значении RN по отношению к эталону не больше 5%, это значение берётся за RN. Подробное описание процедуры дано в [4], где найденное значение RN = 105. Как показали проведенные эксперименты это значение RN* можно использовать и при иссле- довании нелинейных моделей. Процесс генерации двух независимых случайных вектор-столбцов в ПГМ обладает следующим свойством: чем больше количество элементов nA в векто- рах, тем меньше значение их парной корреляции. Это объясняется тем, что чем больше размерность векторов, тем большая степень свободы для их представ- ления, и тем больше возможности для взаимной ортогонализации векторов. По- этому число наблюдений nA можно использовать для генерации матрицы ХA с заданным детерминантом матрицы ΣХ, где по диагонали при увеличении значе- ния nA будут стоять значения, близкие по модулю к 1, а вне диагонали – близ- кие к нулю. Подтвердим это утверждение численно. В случае построения нелинейной модели вектор-столбцы xi и zj матрицы )( AAA ZXH = имеют между собой парную корреляцию, лежащую в интервале [0.6; 0.99], что указывает на большую степень их линейной зависимости. По- этому в случае использования в качестве меры ортогональности детерминанта dH матрицы корреляций ΣH = A T AHH ~~~~ , он будет близким к нулю, и, что самое главное, даже сколь угодно большое значение параметра nA не сможет увели- чить значение dH хотя бы на 0.1. Ввиду этого при исследовании нелинейных моделей в качестве меры ортогональности подсчитывается детерминант d толь- ко для подматрицы ΣХ = A T AXX ~~~~ матрицы корреляций ΣH. Следует отметить, что для сходимости алгоритма важно, насколько попар- но линейно независимыми являются комбинации вектор-столбцов матрицы HA. Например, если взять модель: 3 31 2 22 3 11 xxxy θθθ ++= , (4) которая является нелинейной по переменным, а векторы x1, x2, x3 генерируются случайным образом (их парная корреляция близка к нулю), то скорость сходи- мости модели (4) будет сравнима со скоростью сходимости для линейной моде- ли: 312211 xxxy θθθ ++= . Для исследования скорости сходимости алгоритма при построении нели- нейных моделей была выбрана модель, содержащая как «линейно независи- Павлов А.В., Павлов В.А Індуктивне моделювання складних систем, випуск 4, 2012 151 мые» между собой x1, x2, x3, x4, x5, так и имеющие ненулевую корреляцию («ли- нейно зависимые») с xi, 5,1=i , переменные 2 1x , 3 1x , 2 2 1 xx : .64719.257932.526752.837736.9 46026.770017.611584.829046.729447.6 2 2 1 3 1 2 15 4321 xxxxx xxxxy +−++ +−++−= (5) Результаты этого эксперимента представлены на рисунках 2 и 3. Парамет- ры алгоритма: свобода выбора F = 5, точность моделирования ε = 10–6. Послед- нее значение выбрано таким, т.к. при ε < 10–6 в процессе построения гисто- грамм попадаются варианты, когда параметр r* превышает число итераций R(F), при котором алгоритм исчерпывает имеющийся объём оперативной памя- ти (1.5Гб), поскольку, например, при F = 5 получено R(F) = 4000. Рис. 2. Гистограммы распределения r* при изменении количества наблю- дений nA Над столбиками гистограмм рис. 3 представлены тысячные доли значений усреднённого детерминанта daver. Усредненное значение детерминанта рассчи- тывается следующим образом. Вычисляются значения детерминантов d всех матриц, для которых алгоритм сошёлся к решению за r* итераций, попадающих в соответствующий интервал для r. Значение daver есть среднее рассчитанных значений d. Анализ рисунков 2 и 3 позволяет заключить, что параметр nА прямо про- порционально влияет на: 1) значение детерминанта d, а, следовательно, и на меру ортогональности вектор-столбцов матрицы ХА, поэтому количество наблюдений можно использовать для получения матрицы корреляций с задан- ным значением детерминанта; 2) скорость сходимости алгоритма. Численные эксперименты по исследованию скорости сходимости Індуктивне моделювання складних систем,випуск 4, 2012 152 Ри с. 3 . Г ис то гр ам мы и с оо тв ет ст ву ю щ ие зн ач ен ия d av er д ля р яд а зн ач ен ий n A Павлов А.В., Павлов В.А Індуктивне моделювання складних систем, випуск 4, 2012 153 Шаг 1.2. Выполним поиск значений параметров ПГМ, при которых мате- матическое ожидание параметра d генерируемой матрицы близко к заданному значению. Ввиду того, что функция d является монотонно возрастающей от па- раметра nA, в качестве алгоритма поиска использовался бинарный поиск. Для модели (5) были определены значения nA, позволяющие генерировать матрицы ХА c заданным значением детерминанта d ∈ D, D = {0.5, 0.6, 0.7, 0.8, 0.9, 0.99}, см. табл. 1. Таблица 1. Количество точек и соответствующее значение детерминанта d 0.5 0.6 0.7 0.8 0.9 0.99 nА 10 12 16 26 57 500 Этап 2. Исследуем скорости сходимости РИА ПП при изменении детер- минанта d и неизменных остальных его параметрах для нелинейной модели (5), d ∈ D. Свобода выбора F = 5, точность моделирования ε = 10–6. Результаты представлены на рис. 4. Рис. 4. Гистограммы распределе- ния r, модель (5) Рис. 5. Гистограммы распределения r, мо- дель (6) Как видно из рис. 4, детерминант d влияет на скорость сходимости r, как количественно, так и качественно: при увеличении d математическое ожидание величины r* смещается влево (увеличивается скорость сходимости алгоритма), и уменьшается её дисперсия – гистограммы приобретают более выраженный пик (увеличивает вероятность сходимости алгоритма за rprob – количество ите- раций, соответствующее пику гистограммы). Следует подчеркнуть, что скорость сходимости к нелинейным моделям существенно зависит от ее структуры. Например, скорость сходимости к моде- ли y = –4.82186 + 9.10802·x1 – 7.82742x2 – 5.4407·x3 – 2.3515·x4 + 3.55896·x5 – – 1.37364· 3 1x + 7.78903· 421 xxx + 8.92675· 3 2x (6) Численные эксперименты по исследованию скорости сходимости Індуктивне моделювання складних систем,випуск 4, 2012 154 существенно ниже (рис. 5), чем к модели (5). Это объясняется тем, что модель (5) является более простой по количеству взаимосвязей между нелинейными членами, чем модель (6). Если для сходимости к линейной модели, зависящей от пяти аргументов, при d = 0.7 РИА ПП необходимо 21 итерация (ε = 10-12) [4], то для сходимости к модели (5), содержащей также 5 аргументов, – 53 итера- ций, а к модели (6) – 133 итерации. Причём характер гистограмм у нелинейных моделей является значительно более «размытым», нежели у линейных. Поэто- му можно заключить, что скорость сходимости РИА ПП при построении нели- нейных моделей на порядок ниже, чем линейных. Исследуем скорость сходимости РИА ПП при изменении параметров d и slin и постоянном количестве мультипликативных аргументов smult. Исследова- лась модель (5), d ∈ D, slin ∈ Slin, Slin = {5, 6, 7, 8, 9, 10}, smult = 3. Модули округ- лённых коэффициентов моделей для slin ∈ Slin представлены в таблице 2. Таблица 2. Коэффициенты нелинейных моделей slin \|θ0\| \|θ1\| \|θ2\| \|θ3\| \|θ4\| \|θ5\| \|θ6\| \|θ7\| \|θ8\| \|θ9\| \|θ10\| 5 6.294 7.29 8.12 6.70 7.46 9.38 6 5.30 7 4.00 8 7.78 9 1.04 10 3.15 Рис. 6. Значения числа рядов rprob для каждой пары (slin, d) Павлов А.В., Павлов В.А Індуктивне моделювання складних систем, випуск 4, 2012 155 Гистограммы строились для каждой пары (slin, d), и определялось значе- ние rprob. Свобода выбора F = 5, точность моделирования ε = 10-6. Результаты показаны на рис. 6, а их анализ приводит к следующим выводам: 1) значение детерминанта d прямо пропорционально влияет на скорость сходимости алго- ритма; 2) значения параметра slin обратно пропорционально влияют на скорость сходимости алгоритма. Этап 3. Исследуем скорость сходимости РИА ПП к модели (5) при варьи- ровании свободы выбора F и неизменном параметре d. Пусть d = 0.7, тогда nA = 17 (см. таблицу 1). Свобода выбора F ∈ nonlinℑ , nonlinℑ = {5, 10, 25, 50, 100, 250}. Гистограммы для F = 5 и F = 10 были получены при RN = 106 с целью удовлетворения заданной точности. Как видим из результатов, представленных на рис. 7, свобода выбора прямо пропорционально влияет на скорость сходимости алгоритма. Однако ха- рактер гистограмм для нелинейной модели значительно отличается от гисто- грамм для линейной [4]: при изменении F в пределах [25-100] гистограммы имеют не один, а два экстремума. Следует отметить, что при построении гисто- грамм, изменяя F в пределах [1-250], для любой нелинейной модели с увеличе- нием F левый из экстремумов становится глобальным, а при уменьшении F – правый. Поэтому при увеличении F от 50 до 100 скорость сходимости r* увели- чивается скачкообразно приблизительно в 3 раза (с r* = 48 до r* = 17 итераций). Рис. 7. Гистограммы распределения r* с изменением параметра F В таблице 3 проиллюстрирована скорость сходимости лучшей усреднённой нелинейной модели для F = 50. Модель усреднена по значениям коэффициен- тов и критерию. Как видим из таблицы 3, ввиду того, что в эксперименте была задана точность ε = 10-6, алгоритм не смог сойтись к модели (5) достаточно точно. Однако при построении модели y = 6.29447–7.29046·x1 + 8.11584·x2 +6.70017 2 1x – 7.46026·x1x2 +9.37736 2 2x (7) Численные эксперименты по исследованию скорости сходимости Індуктивне моделювання складних систем,випуск 4, 2012 156 с параметрами алгоритма nA = 50, RN = 104, F = 50 оперативной памяти было достаточно для сходимости алгоритма с точностью ε = 10-12 (см. таблицу 4). Таблица 3. Результаты сходимости РИА ПП для модели (5) № итерации NRSSA θ0 θ1 θ2 θ3 θ4 θ5 θ6 θ7 θ8 8 1.4·10-3 5.55 -3.06 8.65 6.66 -7.42 9.37 0 0 1.01 12 6.4·10-4 5.70 -3.36 8.47 6.68 -7.44 9.37 -0.04 0 1.62 15 4.7·10-4 5.75 -3.47 8.40 6.69 -7.44 9.37 -0.05 0 1.84 25 2.9·10-4 5.84 -3.65 8.27 6.69 -7.45 9.37 0.003 -0.088 2.21 35 2.4·10-4 5.89 -3.73 8.21 6.69 -7.45 9.37 0.017 -0.11 2.39 44 2.3·10-4 5.91 -3.77 8.18 6.69 -7.45 9.37 0.033 -0.13 2.48 Истинная модель: 6.22 -7.29 8.11 6.7 -7.46 9.37 8.26 -5.57 2.64 Таблица 4. Результаты сходимости РИА ПП для модели (7) № итерации NRSSA θ0 θ1 θ2 θ3 θ4 θ5 5 1.34·10-2 5.44639 0 7.55181 0 -7.11667 9.67987 10 5.11·10-3 6.62952 -6.59114 6.74778 4.97901 -5.74463 9.79954 20 1.67·10-3 6.35726 -6.76131 7.61762 5.85519 -6.91197 9.56507 43 3.2·10-4 6.26284 -6.93145 7.98576 6.32843 -7.42516 9.47388 100 7.78·10-6 6.28432 -7.22814 8.1131 6.64537 -7.47706 9.38612 200 5.55·10-9 6.29436 -7.28942 8.11563 6.69918 -7.46045 9.37758 289 1.6·10-11 6.29448 -7.29046 8.11582 6.70016 -7.46025 9.37736 Истинная модель: 6.29447 -7.29046 8.11584 6.70017 -7.46026 9.37736 3. Выводы В работе осуществлёна проверка эффективности работы обобщённого ре- лаксационного итерационного алгоритма (ОРИА) при построении нелинейных моделей. С помощью численных экспериментов исследованы скорость и усло- вия его сходимости к точным моделям. Исходя из анализа полученных резуль- татов можно заключить: Павлов А.В., Павлов В.А Індуктивне моделювання складних систем, випуск 4, 2012 157 1. Скорость сходимости ОРИА зависит не от того, является модель нели- нейной или линейной, а от значения парной корреляции аргументов, входящих в модель: чем она больше, тем ниже скорость сходимости. 2. Установлено, что по величине детерминанта d корреляционной матри- цы входных переменных можно судить о скорости сходимости; эта зависимость проявляется как количественно, так и качественно: чем больше детерминант, тем выше скорость сходимости, и тем больше вероятность того, что алгоритм сойдётся за наиболее вероятное количество итераций. 3. Скорость сходимости при построении моделей, имеющих большую парную корреляцию между аргументами (нелинейные модели) на порядок меньше тех моделей, у которых корреляция мала (линейные модели), при од- ном и том же количестве аргументов. Для сходимости РИА ПП к нелинейной модели, зависящей от пяти аргументов, с точностью ε = 10-12 необходимо около 300 итераций алгоритма, в отличие от линейной (с тем же количеством пере- менных), где требуется всего 15 итераций. Также следует отметить, что характеры гистограмм, описывающие веро- ятность сходимости ОРИА в случае с нелинейными моделями, существенно от- личаются от варианта с линейными: они являются более «размытыми», а также при некоторых значениях d имеют два экстремума. Литература 1. Ивахненко А.Г. Метод группового учета аргументов – конкурент метода стохастической аппроксимации // Автоматика. – 1968.– №3.– С. 58–72. 2. Ивахненко А.Г., Юрачковский Ю.П. Моделирование сложных систем по экспериментальным данным // Москва: Радио и связь, 1987.– 120 с. 3. Булгакова О. С. Узагальнений ітераційний алгоритм індуктивного мо- делювання з застосуванням мережевих технологій : дис. канд. техн. наук: 05.13.06 / Булгакова Олександра Сергіївна. – К., 2011. – 171 с. 4. Павлов А. В., В. А.Павлов. Методика экспериментальных исследований сходимости итерационных алгоритмов метода группового учёта аргументов // Вісник НТУУ „КПІ”. Інформатика, управління та обчислювальна техніка: Зб. наук. пр. – К.: «Век+», – 2011. – № 54. – С. 3-8. 5. Павлов А. В. Обобщённый релаксационный итерационный алгоритм МГУА // Індуктивне моделювання складних систем. Зб. наук. праць, вип. 2. – К.: МННЦІТС НАНУ, 2011. – С. 95-108. 6. Павлов А.В., Кондрашова Н.В. О сходимости обобщённого релаксаци- онного итерационного алгоритма метода группового учёта аргументов // Управляющие системы и машины, №3, 2012. – С. 24-29, 38. 7. Boost C++ library [Електронний ресурс] — 2011. — Режим доступа: http://www.boost.org/. 8. Mersenne twister [Електронний ресурс] – 2011. — Режим доступа: http://en.wikipedia.org/wiki/Mersenne_twister. http://www.boost.org/ http://en.wikipedia.org/wiki/Mersenne_twister УДК 681.513.8 В случае построения нелинейной модели вектор-столбцы xi и zj матрицы имеют между собой парную корреляцию, лежащую в интервале [0.6; 0.99], что указывает на большую степень их линейной зависимости. Поэтому в случае использования в качестве меры ортого... Следует отметить, что для сходимости алгоритма важно, насколько попарно линейно независимыми являются комбинации вектор-столбцов матрицы HA. Например, если взять модель: , (4) которая является нелинейной по переменным, а векторы x1, x2, x3 генерируются случайным образом (их парная корреляция близка к нулю), то скорость сходимости модели (4) будет сравнима со скоростью сходимости для линейной модели: . для исследования скорости сходимости алгоритма при построении нелинейных моделей была выбрана модель, содержащая как «линейно независимые» между собой x1, x2, x3, x4, x5, так и имеющие ненулевую корреляцию («линейно зависимые») с xi, , переменные , , : (5) Над столбиками гистограмм рис. 3 представлены тысячные доли значений усреднённого детерминанта daver. Усредненное значение детерминанта рассчитывается следующим образом. Вычисляются значения детерминантов d всех матриц, для которых алгоритм сошёлся к ... Анализ рисунков 2 и 3 позволяет заключить, что параметр nА прямо пропорционально влияет на: 1) значение детерминанта d, а, следовательно, и на меру ортогональности вектор-столбцов матрицы ХА, поэтому количество наблюдений можно использовать для получе... Шаг 1.2. Выполним поиск значений параметров ПГМ, при которых математическое ожидание параметра d генерируемой матрицы близко к заданному значению. Ввиду того, что функция d является монотонно возрастающей от параметра nA, в качестве алгоритма поиска и... Этап 2. Исследуем скорости сходимости РИА ПП при изменении детерминанта d и неизменных остальных его параметрах для нелинейной модели (5), d ( D. Свобода выбора F = 5, точность моделирования ( = 10–6. Результаты представлены на рис. 4. Как видно из рис. 4, детерминант d влияет на скорость сходимости r, как количественно, так и качественно: при увеличении d математическое ожидание величины r смещается влево (увеличивается скорость сходимости алгоритма), и уменьшается её дисперсия –... Следует подчеркнуть, что скорость сходимости к нелинейным моделям существенно зависит от ее структуры. Например, скорость сходимости к модели y = –4.82186 + 9.10802·x1 – 7.82742x2 – 5.4407·x3 – 2.3515·x4 + 3.55896·x5 – – 1.37364·+ 7.78903· + 8.92675· (6) существенно ниже (рис. 5), чем к модели (5). Это объясняется тем, что модель (5) является более простой по количеству взаимосвязей между нелинейными членами, чем модель (6). Если для сходимости к линейной модели, зависящей от пяти аргументов, при d = ... исследуем скорость сходимости РИА ПП при изменении параметров d и slin и постоянном количестве мультипликативных аргументов smult. Исследовалась модель (5), d ( D, slin ( Slin, Slin = {5, 6, 7, 8, 9, 10}, smult = 3. Модули округлённых коэффициентов мо... Таблица 2. Коэффициенты нелинейных моделей Рис. 6. Значения числа рядов rprob для каждой пары (slin, d) Гистограммы строились для каждой пары (slin, d), и определялось значение rprob. Свобода выбора F = 5, точность моделирования ( = 10-6. Результаты показаны на рис. 6, а их анализ приводит к следующим выводам: 1) значение детерминанта d прямо пропорцион... Этап 3. Исследуем скорость сходимости РИА ПП к модели (5) при варьировании свободы выбора F и неизменном параметре d. Пусть d = 0.7, тогда nA = 17 (см. таблицу 1). Свобода выбора F ( , = {5, 10, 25, 50, 100, 250}. Гистограммы для F = 5 и F = 10 ... Как видим из результатов, представленных на рис. 7, свобода выбора прямо пропорционально влияет на скорость сходимости алгоритма. Однако характер гистограмм для нелинейной модели значительно отличается от гистограмм для линейной [4]: при изменении F в... Рис. 7. Гистограммы распределения r* с изменением параметра F В таблице 3 проиллюстрирована скорость сходимости лучшей усреднённой нелинейной модели для F = 50. Модель усреднена по значениям коэффициентов и критерию. Как видим из таблицы 3, ввиду того, что в эксперименте была задана точность ( = 10-6, алгоритм н... y = 6.29447–7.29046·x1 + 8.11584·x2 +6.70017 – 7.46026·x1x2 +9.37736 (7) с параметрами алгоритма nA = 50, RN = 104, F = 50 оперативной памяти было достаточно для сходимости алгоритма с точностью ( = 10-12 (см. таблицу 4). Таблица 3. Результаты сходимости РИА ПП для модели (5) Таблица 4. Результаты сходимости РИА ПП для модели (7) 3. Выводы В работе осуществлёна проверка эффективности работы обобщённого релаксационного итерационного алгоритма (ОРИА) при построении нелинейных моделей. С помощью численных экспериментов исследованы скорость и условия его сходимости к точным моделям. Исходя ... 1. Скорость сходимости ОРИА зависит не от того, является модель нелинейной или линейной, а от значения парной корреляции аргументов, входящих в модель: чем она больше, тем ниже скорость сходимости. 2. Установлено, что по величине детерминанта d корреляционной матрицы входных переменных можно судить о скорости сходимости; эта зависимость проявляется как количественно, так и качественно: чем больше детерминант, тем выше скорость сходимости, и тем ... 3. скорость сходимости при построении моделей, имеющих большую парную корреляцию между аргументами (нелинейные модели) на порядок меньше тех моделей, у которых корреляция мала (линейные модели), при одном и том же количестве аргументов. для сходимости... Также следует отметить, что характеры гистограмм, описывающие вероятность сходимости ОРИА в случае с нелинейными моделями, существенно отличаются от варианта с линейными: они являются более «размытыми», а также при некоторых значениях d имеют два экст...

Численные эксперименты по исследованию скорости сходимости релаксационного итерационного алгоритма при построении нелинейных моделей

Institution

Ähnliche Einträge