Сравнительный анализ вычислительной сложности алгоритмов релаксационно-итерационного типа
Несмотря на то, что обобщенный релаксационный итерационный алгоритм (ОРИА) на сегодня самый быстрый и точный итерационный алгоритм МГУА, для которого доказана сходимость, его аналоги: многорядный упрощенный алгоритм (МУА) и многорядный алгоритм с комбинаторикой и селекцией обобщенных переменных (МАК...
Збережено в:
| Опубліковано в: : | Індуктивне моделювання складних систем |
|---|---|
| Дата: | 2013 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2013
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/83671 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Сравнительный анализ вычислительной сложности алгоритмов релаксационно-итерационного типа / Н.В. Кондаршова // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2013. — Вип. 5. — С. 184-200. — Бібліогр.: 9 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859981972200226816 |
|---|---|
| author | Кондаршова, Н.В. |
| author_facet | Кондаршова, Н.В. |
| citation_txt | Сравнительный анализ вычислительной сложности алгоритмов релаксационно-итерационного типа / Н.В. Кондаршова // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2013. — Вип. 5. — С. 184-200. — Бібліогр.: 9 назв. — рос. |
| collection | DSpace DC |
| container_title | Індуктивне моделювання складних систем |
| description | Несмотря на то, что обобщенный релаксационный итерационный алгоритм (ОРИА) на сегодня самый быстрый и точный итерационный алгоритм МГУА, для которого доказана сходимость, его аналоги: многорядный упрощенный алгоритм (МУА) и многорядный алгоритм с комбинаторикой и селекцией обобщенных переменных (МАКСО) также имеют свою «нишу» применимости. В плоскости двух параметров: размера выборки (числа наблюдений) и сложности модели (числа аргументов) показаны области превышения вычислительной сложности (быстродействия) одного алгоритма по отношению к другому. Проведен сравнительный анализ быстродействия нерекуррентного и рекуррентных вариантов ОРИА между собой и каждого из них в сравнении с МУА.
Незважаючи на те, що узагальнений релаксаційний ітераційний алгоритм (УРІА) на сьогодні найшвидший і точний ітераційний алгоритм МГУА, для якого доведена збіжність, його аналоги: багаторядний спрощений алгоритм (БСА) і багаторядний алгоритм з комбінаторикою і селекцією узагальнених змінних (БАКСУ) також мають свою «нішу» застосовності. У площині двох параметрів: розміру вибірки (числа спостережень) і складності моделі (числа аргументів) показані області перевищення обчислювальної складності (швидкодії) одного алгоритму по відношенню до іншого. Проведено порівняльний аналіз швидкодії нерекуррентного та рекурентних варіантів УРІА між собою і кожного з них у порівнянні з БСА.
Despite the fact that the generalized relaxation iterative algorithm (GRIA) for today is most fast and precise iterative algorithm GMDH for which the convergence is proved, its analogues: a multi-layered simplified algorithm (MSA) and multi-layered algorithm with combinatorics and selection of generalized variables (MACSG) also have their "niche" applicability. Areas of exceedance computational complexity (running speed) of an algorithm with respect to another in the plane of two parameters such as sample size (number of observations) and model complexity (number of arguments) are shown. A comparative analysis of the running speed of nonrecurrent and recurrent variants GRIA between themselves and each of them compared to the MSA is provided.
|
| first_indexed | 2025-12-07T16:26:12Z |
| format | Article |
| fulltext |
Кондрашова Н.В.
УДК 681.513.8
СРАВНИТЕЛЬНЫЙ АНАЛИЗ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ
АЛГОРИТМОВ РЕЛАКСАЦИОННО-ИТЕРАЦИОННОГО ТИПА
Н.В. Кондрашова
Международный научно-учебный центр информационных технологий и систем
НАНУ и МОН Украины,
NKondrashova@ukr.net
Незважаючи на те, що узагальнений релаксаційний ітераційний алгоритм (УРІА) на сьогодні
найшвидший і точний ітераційний алгоритм МГУА, для якого доведена збіжність, його
аналоги: багаторядний спрощений алгоритм (БСА) і багаторядний алгоритм з
комбінаторикою і селекцією узагальнених змінних (БАКСУ) також мають свою «нішу»
застосовності. У площині двох параметрів: розміру вибірки (числа спостережень) і
складності моделі (числа аргументів) показані області перевищення обчислювальної
складності (швидкодії) одного алгоритму по відношенню до іншого. Проведено
порівняльний аналіз швидкодії нерекуррентного та рекурентних варіантів УРІА між собою і
кожного з них у порівнянні з БСА.
Ключові слова: метод групового урахування аргументів (МГУА), узагальнений релаксаційний
ітераційний алгоритм (УРІА), багаторядний спрощений алгоритм (БСА), багаторядний
алгоритм з комбінаторикою і селекцією узагальнених змінних (БАКСУ), рекурентні
обчислення.
Despite the fact that the generalized relaxation iterative algorithm (GRIA) for today is most fast and
precise iterative algorithm GMDH for which the convergence is proved, its analogues: a multi-
layered simplified algorithm (MSA) and multi-layered algorithm with combinatorics and selection
of generalized variables (MACSG) also have their "niche" applicability. Areas of exceedance
computational complexity (running speed) of an algorithm with respect to another in the plane of
two parameters such as sample size (number of observations) and model complexity (number of
arguments) are shown. A comparative analysis of the running speed of nonrecurrent and recurrent
variants GRIA between themselves and each of them compared to the MSA is provided.
Keywords: Group Method of Data Handling (GMDH), Generalized Relaxation Iterative Algorithm
(GRIA), Multilayered Simplified Algorithm (MSA), Multilayered Algorithm with Combinatorics and
Selection of Generalized variables (MACSG), recurrent calculation.
Несмотря на то, что обобщенный релаксационный итерационный алгоритм (ОРИА) на
сегодня самый быстрый и точный итерационный алгоритм МГУА, для которого доказана
сходимость, его аналоги: многорядный упрощенный алгоритм (МУА) и многорядный
алгоритм с комбинаторикой и селекцией обобщенных переменных (МАКСО) также имеют
свою «нишу» применимости. В плоскости двух параметров: размера выборки (числа
наблюдений) и сложности модели (числа аргументов) показаны области превышения
вычислительной сложности (быстродействия) одного алгоритма по отношению к другому.
Проведен сравнительный анализ быстродействия нерекуррентного и рекуррентных
вариантов ОРИА между собой и каждого из них в сравнении с МУА.
Ключевые слова: метод группового учета аргументов (МГУА), обобщенный релаксационный
итерационный алгоритм (ОРИА), многорядный упрощенный алгоритм (МУА), многорядный
алгоритм с комбинаторикой и селекцией обобщенных переменных (МАКСО), рекуррентные
вычисления.
Індуктивне моделювання складних систем, №5, 2013 184
Сравнительный анализ вычислительной сложности алгоритмов
Вступление
Данная работа выполнена в рамках темы «Разработка и исследование
интеллектуальных технологий индуктивного моделирования для задач
поддержки решений в сложных системах». Созданная технология построения
регрессионных моделей на основе ОРИА МГУА [1] с рекуррентными
вычислениями является ее важным результатом. Прообразом этого алгоритма
является МУА [2], а предшественником – модификация МУА – МАКСО [3].
Если первый алгоритм – МУА – имеет исторический интерес и теоретическое
значение, то МАКСО, имеющий современный интерфейс и расширенные
возможности, является широко используемым программным продуктом.
Решение практических задач моделирования по выборкам данных даже средней
размерности для этого алгоритма является трудной задачей. Например, на
получение одной МАКСО-модели по выборке, имеющей около десятка
переменных и несколько десятков точек наблюдения, было затрачено
несколько суток расчетного времени компьютера с процессором Intel Core i3
M350 2.27 GHz. При этом использовался «веерный» вариант алгоритма,
описанный в [4]. МУА и МАКСО по вычислительной сложности являются
тождественными, поэтому для сравнения рассмотрим первый многорядный
упрощенный алгоритм.
Для решения задач большой размерности с сотнями тысячами наблюдений
и тысячами переменных был создан ОРИА. Время решения задач этим
алгоритмом по сравнению с аналогом снижается в десятки, сотни, тысячи и т.д.
раз в зависимости от числа аргументов и наблюдений. В данной статье
исследуется вопрос, насколько по быстродействию отличаются релаксационно-
итерационные алгоритмы при небольшом объеме выборки. Целью данной
статьи является исследование быстродействия указанных алгоритмов для
граничных соотношений объемов обучающей и проверочной выборок, в
зависимости от двух параметров: сложности модели и размера выборки.
1. Постановка задачи
Алгоритмы, о которых речь пойдет ниже, предназначены для решения за-
дачи моделирования по таблицам или выборкам числовых данных. В задаче
идентификации методом группового учёта аргументов известна матрица изме-
рений исходных данных , dim W = nW W×(m+1), т – число входных перемен-
ных (число столбцов). Размерность выходного вектора dim y = nW×1, nW – коли-
чество наблюдений. Неизвестны характеристики шума ξ в объекте. Предпола-
гается, что он аддитивен, некоррелирован с полезными сигналами, имеет нуле-
вое математическое ожидание ( 0][ =Μ ξ ), диагональную матрицу ковариаций
( ) и конечную дисперсию (
Wn
T E2σξξ = ∞<2σ ). Где – единичная матри-
ца n
WnE
W×nW. Необходимо найти структуру и параметры θi, mi ,0= модели
Індуктивне моделювання складних систем, № 5, 2013 185
Кондрашова Н.В.
∑
=
=
m
i
ii zy
0
θ , (1)
удовлетворяющие максимальной точности заданного критерия. Выражение (1)
является скалярным видом линейной модели. Под структурой линейной модели
объекта понимается информативный набор (множество) аргументов zi, который
его описывает с максимальной точностью заданного критерия. Пусть матрица
входов Х имеет размерность nW×m. Векторный, нелинейный вид модели:
),( Xy Θ= f . (2)
ОРИА МГУА строит линейные по параметрам модели. Выражение (2) путем
различных преобразований (линеаризацией, разложением в ряд, логарифмиро-
ванием и прочее) и последующим переобозначением преобразованных пере-
менных приводится к виду (1). Преобразованные и переобозначенные перемен-
ные называются аргументами. Структурой модели в этом случае на-
зывается нелинейная функция входных переменных, заданная с точностью до
значений, линейно входящих в неё параметров
)(Xii fz =
),...,( 1 Mθθ
)))
=Θ . Как правило,
М≥т. В дальнейшем будем считать, что М=т.
Под информативным понимается при отсутствии шума набор «истинных»
аргументов, при наличии шума – набор «адекватных» шуму аргументов. «Аде-
кватное» упрощение модели происходит при превышении дисперсии реального
шума в объекте значений, так называемых, критических дисперсий [5]. Сле-
дующее определение «истинной» структуры является обобщением определе-
ния, данного в [6].
Определение 1. Назовем «истинной» структуру , которая является не-
смещенной оценкой функции f, зависящей от вектора параметров Θ и матрицы
входов Х, если
0f
)(])[M,(0 XX ff =Θ
)
. При этом структура имеет сложность:
, где
0f
)0,][M(
1
0 ∑
=
−=
m
i
iEqualms θ
)
][⋅Μ – оператор математического ожидания, ко-
торое осуществляется по всевозможным реализациям шума ,...2,1, =iiξ . Функ-
ция сравнения )0],[M( iEqual θ
)
равна 1, если математическое ожидание какого-
либо параметра ][ iθ
)
Μ равно 0. Истинная модель при этом имеет вид:
Wjmjjj njxxfy ,1,),...,( ,1, =+= ξ ,
где измерены точно. Неважно, какие значения имеют линейные параметры.
Полагается, что они не равны нулю и сложность истинной модели равна s
jix
0.
Індуктивне моделювання складних систем, №5, 2013 186
Сравнительный анализ вычислительной сложности алгоритмов
Определение 2. Назовем «адекватной» идентифицируемую модель, кото-
рая упрощается, становится соответствующей неизвестному уровню шума при
его увеличении на выходе объекта.
2. Краткие сведения об ОРИА МГУА
ОРИА известен в двух своих модификациях с нерекуррентными и рекур-
рентными вычислениями оценок параметров модели и значений критериев. При
каких условиях их скорость различается на порядки, было доказано и показано
в [7]. Резонный вопрос: зачем говорить о двух модификациях, если и так ясно,
что модификация с рекуррентными вычислениями должна быть лучше. Пока-
жем, что при малом числе аргументов это не выполняется. Проведем также ана-
литическое сравнение двух указанных модификаций ОРИА с его аналогом
МУА для того, чтобы стал очевидным тот факт, что для безусловной независи-
мости от числа наблюдений переборной стадии недостаточно выделить отдель-
ный блок формирования ковариационных матриц, как это сделано в РИА с не-
рекуррентным методом (РИАНМ) вычислений параметров и критерия. Ограни-
чимся рассмотрением случая, когда исходная выборка W разбита на две подвы-
борки: обучающую А и проверочную В, =∩∪= BABAW , ∅.
В работе речь пойдет об одном и том же алгоритме – ОРИА, нерекуррент-
ная и рекуррентная модификации которого совпадают в двух своих следующих
стадиях:
1) преобразование матрицы входных переменных в аргументы, для полу-
чения моделей заданного класса (например, полиномиальных, линейных или
нелинейных разностных моделей);
2) подготовительных вычислений, где осуществляется: преобразование
вектор-столбцов матриц аргументов выборок А и В путем вычитания средних
значений элементов А выборки, а также расчет «ковариационных» матриц для
указанных выборок BA ΣΣ , .
Модификации ОРИА отличаются своей самой вычислительно затратной
третьей стадией, на которой модели строятся итеративно, с использованием
элементов ковариационных матриц указанных выборок. Рассмотрим кратко от-
личительную третью стадию этих модификаций: одну с нерекуррентными вы-
числениями и две – с рекуррентными.
3. Релаксационный итерационный алгоритм с использованием нере-
куррентного метода
Этот алгоритм является вариантом ОРИА с нерекуррентным методом вы-
числения параметров и критерия селекции. Алгоритм начинает работу полным
перебором из т аргументов по два:
jAlAilAl xxy ωϖ ))) += , 2,1 mCl = . (3)
Індуктивне моделювання складних систем, № 5, 2013 187
Кондрашова Н.В.
Оценки параметров находятся методом наименьших квадратов (МНК):
( ) yXXX T
ll
T
l
1−
=Ωl , (4)
из условия минимизации остаточной суммы квадратов RSSl. При оценке пара-
метров модели (3) ( )Tll ωϖ ))
l ,=Ω , , 22)dim( ×=l
T
l XX 2,1 mCl = , ( )jil xxX ,= ,
ijmji >= ,,1, . На самом деле оценки параметров модели (3) получаются
МНК для вложенных структур, сначала для моделей одного аргумента,
lA
T
lA
lA
T
lA
l xx
yx
=1ϖ) , mlAllAl ,1,11 == xy ϖ)) ,
потом для двух аргументов
mljmljAjAllAl ),1(,,1,2122 +==+= xyy ωϖ )))) ,
как результат минимизации min)()( →−−= r
lAA
Tr
lAA
r
lRSS yyyy ))
при 2,1=r .
Число перебранных моделей, для которых они вычисляются равно 2/)1( −mm .
Параметры модели определяются только по данным выборки А, поэтому индекс
А для параметров опускаем.
Опишем кратко алгоритм при свободе выбора моделей F=1 на каждой ите-
рации, для номера итерации r ≥ 2. Свобода выбора F > 1 на факт сходимости
алгоритма к «истинной» модели не влияет, а влияет только на скорость сходи-
мости, при условии что в переборе участвуют все «истинные» аргументы и п ≥
т [7].
Пусть необходимо найти лучшую линейную модель (r+1)-й итерации:
1111 ++++ += r
A
rr
A
rr
A xyy ωϖ )))) , 2≥r . (5)
Для этого строятся все возможные модели (r+1)-й итерации вида (5)
1
,
111
,
++++ += r
Al
r
l
r
A
r
l
r
Al xyy ωϖ )))) , 2≥r , ml ,1= . (6)
где 1+r
lϖ) , 1+r
lω
) – МНК-оценки, получаемые из условия равенства правой части
(6) исходному выходному вектору уА. Можно показать, что оценки вложенных
структур являются точно соответствующими МНК-оценкам (4) lll ϖϖϖ ))) =21 ,
lj ωω )) =2 только при r ≤2. Если в матрице больше, чем два столбца, то оценки lX
Індуктивне моделювання складних систем, №5, 2013 188
Сравнительный анализ вычислительной сложности алгоритмов
параметров при , j=1,2,..,r, получаемые по формуле (4), а также итерационно
по формулам (6) не равны между собой для одного и того же r.
jAx
Для всех моделей (6) по данным проверочной выборки В вычисляется кри-
терий селекции )()( 1
,
1
,
1 +++ −−= r
BlB
Tr
BlB
r
lAR yyyy )) . По его минимуму находится
лучший аргумент и параметры модели (6 ) на (r+1)-й итерации, т.е. тройка:
( 1+rϖ) , 1+rω) , ),,,(minarg) 111
,,,1,),(
1
211
yxx
xy
l
r
l
r
l
r
l
ml
r AR
Wn
l
Wnr
l
r
l
+++
ℜ∈ℜ∈=ℜ∈
+
++
= ωϖ
ωϖ
))
))
.
После этого получается модель в исходных переменных («развернутая» мо-
дель): irrrr −++++ Ω= 1|111 )) Gy , где число 0),...,1(, −= rri показывает сколько раз
корректировался коэффициент при переменной c индексом (r+1-i). Матрица
составляется из вектор-столбцов аргументов ( ) матрицы Х, в
порядке их включения в модель. Вектор оценок коэффициентов (r+1)-й итера-
ции «развернутой» модели
1+rG 11 ,,..., +rr xxx
( )Trrrrrirr 1|12|11|11|1 ,,...,, ++++−++ =Ω ωωωω )))))
– при усло-
вии, что на предыдущих итерациях были выбраны аргументы , а на
(r+1)-й – аргумент с параметром
rxx ,...,1
11 ++ = rr
A xx 1|11 ++
Δ
+ = rrr ωω )) . Первая часть верх-
него индекса r+1 определяет номер итерации. Во второй части – символ | озна-
чает: при условии выбора на предыдущих итерациях аргументов, верхний ин-
декс которых равен (r+1-i), 0),...,1(, −= rri и совпадает с порядковым номером
их включения в модель.
Для того чтобы оценить количество операций, необходимое для вычисле-
ния модели данным алгоритмом, выпишем формулы, по которым вычисляются
параметры:
( ) ( )
( ) 2
1
1
,
1
,
1
,1
1
,
1
,1
)(
)()(
+
++
+
+
++
+
−
−
=
r
r
Al
Tr
Alr
A
Tr
Alr
r
Al
Tr
Alrr
l
ba
bc
xx
yxxx
ϖ) ,
( )
( ) 2
1
1
,
1
,
1
1
,1
)(
)(
+
++
+
+
+
−
−
=
r
r
Al
Tr
Alr
rrA
Tr
Alrr
l
ba
cba
xx
yx
ω) (7)
где коэффициенты ar, br+1, cr равны соответственно:
irrrTrTirr
ra −− ΩΩ= || )()(
))
GG , Tr
Arb )(1 y)=+
1
,
+r
Alx =( )1
,
+r
Alx T irrr −Ω |)
G ,
A
Tr
Arc yy )()= =(yA)T irrr −Ω |)
G .
Критерий селекции 1+r
lAR и критерий RSSr+1 вычисляются для ml ,1= по
формулам
irr
l
r
Bl
Tr
Bl
Tr
l
r
l
r
Bl
T
BB
T
B
r
l
irirAR −++++++++ ΩΩ+Ω−= −+−+ 1|11
,
1
,
111
,
1 )()|(|2 11 )))
GGGyyy , (8)
irrrTrTirrirrrT
AA
T
A
rRSS −++++−++−++++ ΩΩ+Ω−= 1|111(1|11|111 ))(2
)))
GGGyyy . (9)
Індуктивне моделювання складних систем, № 5, 2013 189
Кондрашова Н.В.
При вычислении вектора irr −++Ω 1|1)
первые r оценок параметров лучшей
модели (r+1)-й итерации определяются как: irrr
l
−+ Ω |1 ))ϖ , 0),...,2(),1( −−= rri , а
оценка 1+rω) – получена по формуле (7).
Из работы [7] известно, что вычислительная сложность построения одной
модели РИАНМ на r-й итерации, имеющей r аргументов, равна:
. (10) 94)(Q 2 ++= rrr
нерек
4. Релаксационный итерационный алгоритм с использованием
рекуррентного метода (РИАРМ)
Отличие РИАРМ от РИАНМ состоит в том, что коэффициенты ar, cr на r-й
итерации для модели (6) вычисляются по рекуррентным формулам общего вида
),,,( 1 rArrr xbafa ω)−= , ),,( 1 rrrr bcc ωϕ )
−= .
В первом варианте алгоритма (РИАРМ1) критерий селекции и кри-
терий RSS
1+r
lAR
r+1 для ml ,1= вместо формул (8) и (9) вычисляются по формулам,
имеющим общий вид: ),,,,(1
BBB
rr
l ARAR yxGΩ=+ φ ,
. Из [7] известно, что число операций рекур-
рентных алгоритмов линейно зависит от числа аргументов r. В РИАРМ
),,,,(1
AAA
rr RSSRSS yxGΩ=+ ψ
1 число
операций одной итерации
294Q
1
+= rрек . (11)
Второй вариант рекуррентного алгоритма (РИАРМ2) является более эконом-
ным при вычислении критериев по формулам вида: ,
и его сложность равна:
),,( ,,1 BBrBr
r
l baAR yφ=
),,( ,,1 AArAr
r baRSS yψ=
263Q
2
+= rрек . (12)
5. Сравнение нерекуррентного и рекуррентных методов вычислений в
ОРИА
Рассмотрение предпочтительности применения нерекуррентных по
сравнению с рекуррентными вычислениями с позиции здравого смысла –
нонсенс. На примере сравнения двух методов вычисления в ОРИА покажем,
что нерекуррентные методы «выигрывают» у рекуррентных, если число
аргументов в моделях, которые они строят, меньше некоторого количества, и
«проигрывают» – в противном случае.
Індуктивне моделювання складних систем, №5, 2013 190
Сравнительный анализ вычислительной сложности алгоритмов
Результаты расчета числа операций при построении одной модели в
зависимости от числа итераций r, количество которых равно числу аргументов
в «развернутой» модели, для трех вариантов алгоритмов (одного с
нерекуррентными и два с рекуррентными вычислениями) представлены
графически на рис. 1. Из сравнения графиков видно, что при т меньше
четырех, алгоритмы, не имеющие рекуррентных вычислений оценок
параметров модели и значений критериев, имеют меньшее число операций, а
при т≥ 5, наоборот, оба рекуррентных алгоритма являются более «быстрыми».
Рис. 1 – Зависимость числа вычислений от числа аргументов (итераций) r.
В целом, результаты, представленные на рис. 1, показывают преимущество
второго рекуррентного варианта алгоритма, поскольку число аргументов
модели т, при котором нерекуррентный метод является более
быстродействующим по сравнению с обоими рекуррентными, пренебрежимо
мало, а малые отличия Qнерек от Qрек не могут при решении реальных задач
сделать нерекуррентный метод более предпочтительным.
При т ≥ 5 в зависимости от значений числа аргументов рекуррентные
методы быстрее нерекуррентных в 10 раз при т =10, в 100 раз при т =100 и т.д.
6. Сравнительный анализ ОРИА и МУА
Сравним два алгоритма, принадлежащих одному виду релаксационно-
итерационных: ОРИА с его прообразом – МУА. Поскольку алгоритм МУА
имеет некоторые преимущества (он экономно расходует оперативную память,
не хранит ковариационные матрицы BA ΣΣ , ), важно убедиться, в каких
случаях этот алгоритм не хуже в вычислительном плане своего
усовершенствованного аналога ОРИА. Для этого сравним число операций,
Індуктивне моделювання складних систем, № 5, 2013 191
Кондрашова Н.В.
приходящееся на одну итерацию, этих двух алгоритмов. Известно [7], что число
операций при построении МУА одной модели равно
327),,(МУА +++= BABBA nnrnnnrQ . (13)
Для возможности проведения дальнейшего анализа заданных зависимостей
(10)-(13) удобно перейти к переменным в области действительных значений,
обозначив их ℜ∈ρη, . Построив известную зависимость в непрерывной облас-
ти, нужно проверить решение неравенств на корректность в области целочис-
ленных значений. Натуральные числа nB, r ∈ N будем получать в результате ок-
ругления действительных
B
ℜ∈ρη, , как ⎣ ⎦η=Bn и ⎣ ⎦ρ=r .
Рассмотрим три основных варианта соотношений при разбиении выборки.
Если используется критерий регулярности, то традиционное разбиение равно nA
: nB =2:1, если усредненный критерий регулярности (УКР) (англ. «leave one
out»), то – nA : nB =(nW-1):1; если применяется какой либо из критериев несме-
щенности (согласованности), то выборка разбивается в отношении nA : nB =1:1.
В задаче прогнозирования с квазиоптимальным разбиением значение отноше-
ния nA : nB, на практике изменяется от 1:1 до 2:1 [8]. Разбиения nA : nB =(nW-1):1 и
nA : nB =1:1 это – два варианта соотношений размеров подвыборок, которые яв-
ляются наименьшим и наибольшим по трудоемкости перебора. При поиске луч-
шего разбиения по УКР осуществляется полный перебор (ПП), имеющий ли-
нейную вычислительную сложность по пW. При nA : nB =1:1 ПП, имеющий экс-
поненциальную сложность L= 12 1 −−Wn , часто заменяется разбиением «по дис-
персии» [9]. Традиционно применяемое разбиение nA : nB =2:1 является соотно-
шением объемов обучающей и проверочной выборок, полученным опытным
путем. Вычислительная сложность поиска лучшего разбиения в данной работе
вынесена за рамки исследования. Лучшее разбиение считается полученным,
при этом отношение nA : nB может быть разным. Рассмотрим случаи А), Б) и В).
Формулы (10)-(12) не изменят своего вида при подстановке . ρ
Δ
=r
А) Если nA : nB =2:1, то в соответствии с новыми обозначениями выражение
(13) примет вид:
QМУА(ρ,η) = ρη + 16η + 3. (14)
Б) Если nA :nB =(nW-1):1, то (13) имеет вид:
QМУА(ρ,η) = ρ +7(nW - 1) + 5. (15)
В) Если nA : nB =1:1, то формула (13) выглядит следующим образом
QМУА(ρ,η) = ρη + 9η + 3. (16)
Рассмотрим, при каких условиях число вычислений МУА, больше или
равно числу вычислений ОРИА
QМУА ≥ QОРИА. (17)
Індуктивне моделювання складних систем, №5, 2013 192
Сравнительный анализ вычислительной сложности алгоритмов
7. Сравнительный анализ вычислительной сложности РИАНМ и МУА
Сравним МУА сначала с модификацией ОРИА с нерекуррентным
методом вычислений (РИАНМ) сложности (10).
Рассмотрим случай А), когда отношение nA : nB =2:1. Подставив в (17)
выражения (14) и (10) получим нестрогое неравенство для анализа в области
действительных переменных
ρ2 + (4 – η)ρ – 16η + 6≤ 0. (18)
Найдем корни уравнения (18) ρ1, ρ2.
8565.02/)4(6164/)816(2/)4( 22
2,1 −+±−−=−++−±−−= ηηηηηηηρ . (19)
В результате имеем соотношение, связывающее непрерывные параметры, когда
ℜ∈ρη , :
8)56(5.02/)4(1 −+−−−= ηηηρ ,
8)56(5.02/)4(2 −++−−= ηηηρ (20)
При любых ℜ∈η , ⎣ ⎦η=Bn значения ρ1 < 0, поэтому это решение исключается
из рассмотрения. Исследуем при каких значениях nВ, (nW) и ⎣ ⎦ρ=r выполняет-
ся неравенство (18), и в какой из частей области изменения значений, которую
пересекает решение (20), это неравенство не выполняется. Последовательно
подставляя значения η = nВ = 1, 2, 3,… в (20), получим ряд значений ρ2
, округ-
ляя которые с недостатком (ниже кривой), получим выполнение неравенства
(17), а с избытком (выше кривой) – выполнение противоположного неравенства
QМУА ≤ QОРИА. (21)
Если η = nВ = 1, (nW = 3), то 27.285615.02/)14(2 =−++−−=ρ , то в
точках 0 < r ≤ ⎣2.77⎦ – =2 выполняется неравенство (17), а в точках r ≤ ⎣ ⎦2.77 +=3
выполняется (21).
Квадратные скобки ⎣ ⎦⋅ – обозначают операцию отбрасывания дробной час-
ти числа (округление с недостатком), ⎣ ⎦⋅ + – округление до ближайшего целого с
избытком. Подстановкой nB =1, r=2 в неравенство
r2 + (4 – nB)r – 16nB + 6≤ 0 (22)
можно убедится, что оно удовлетворяется и, значит, r=2 наибольшее значение
r, при котором еще выполняется QМУА ≥ QРИАНМ.
Аналогично, если η = nВ = 2, nW = 6, то
39.482)562(5.02/)24(2 =−++−−=ρ , то ⎣ ⎦ 439.40 =≤≤ −r и т.д.
Індуктивне моделювання складних систем, № 5, 2013 193
Кондрашова Н.В.
Построив график и линейную регрессию, можно получить при малых значени-
ях r и nW зависимость
r(nW) ≈
3
2 nW. (23)
Рассмотрим подкоренное выражение (20)
08562 =−+ ηη , 1533.28288676282,1 ±−=+±−=η , η1 ≅ -56, η2 = 0.1533 ≅ 0.
Поскольку величина nB η является целочисленной переменной, подкоренное
выражение аппроксимируем, как (η + 56)η. Легко заметить, что тангенс угла на-
клона пограничной кривой (19) асимптотически при
Δ
=
∞→Bn стремится к 1, т.е.
. Тогда в области значений этих параметров выше указанной границы
( , ), алгоритм МУА имеет бόльшее быстродействие, чем
РИАНМ и, наоборот, при моделировании сложных объектов чаще бывает, что
– в таком случае быстродействие РИАНМ выше, чем МУА.
Bn
nr
B ∞→
≈
Bn
nr
B ∞→
> Wn
nr
W
3/1
∞→
≈
Bn
nr
B ∞→
<
В области малых значений nB ≤ 3, если зависимость r = аnB B аппроксими-
ровать линейной функцией, где коэффициент а=2, то если 0< r ≤ 2nBB (r ≤ 2/3nW)
РИАНМ по скорости предпочтительнее, чем МУА и, наоборот, МУА имеет
большее быстродействие, чем РИАНМ при r > 2nB (r > 2/3nW).
При использовании УКР, когда имеется одна точка в проверочной последова-
тельности (nB =1) неравенство (18) имеет вид 0 , решая которое
совместно с неравенством (17), получим что при 3
B 1622 ≤−+ ρρ
0 << r QМУА ≥ QРИАНМ, а
при 3≥r QМУА < QРИАНМ. Заметим, что если nBB=1, то вышеприведенные усло-
вия выполнятся для единственного значения 3=Wn , в силу nA : nB =2:1.
Рассмотрим более общий случай Б) для любого nW ≥ 2, при соотношении
nA :nB =(nW-1):1.
Подстановкой (15) и (10) в (17) получаем неравенство, которое имеет вид
07732 ≤+−+ Wnrr . (24)
Построив параболу (24) (сплошная линия, см. рис. 3), подстановкой
определим соответствующие области. В заштрихованной области,
ограниченной штрихпунктирной кривой, построенной при целочисленных зна-
чениях , выполняется условие большего быстродействия МУА. В области
ниже светлой штрихпунктирной кривой, наоборот, РИАНМ делает меньше опе-
раций.
N, ∈Wnr
Wnr,
Осталось рассмотреть еще один важный для практики случай В) деления
выборки пополам nA : nB=1:1. B
Індуктивне моделювання складних систем, №5, 2013 194
Сравнительный анализ вычислительной сложности алгоритмов
Рис. 2 – Результаты сравнения быстродействия РИАНМ и МУА в плоскости
числа аргументов r «развернутой» модели и количества наблюдений nW при
условии nB =1 и отношении объемов выборок nA : nB=(nB W – 1):1.
Подстановкой (16) и(10) в (17) получаем следующее неравенство:
ρ2 + (4 – η)ρ – 9η + 6≤ 0. (25)
Выбираем одно из решений равенства (25),
8)28(5.02/)4(2 −++−−= ηηηρ (26)
Рис. 3 – Результаты сравнения быстродействия РИАНМ и МУА в плоскости
числа аргументов r «развернутой» модели и количества наблюдений nW в за-
висимости от трех рассмотренных соотношений nA : nB .
Індуктивне моделювання складних систем, № 5, 2013 195
Кондрашова Н.В.
Используя (26), для положительных значений η>0, ρ>0 можно указать об-
ласти выполнения неравенств (17) и (21). Подстановкой целочисленных значе-
ний (nВ, nW , r) ∈ N находятся соответствующие области выполнения нера-
венств, как и в случае А), округлением с недостатком r = ⎣ ⎦ρ – (выполняется
(17)) и округлением с избытком r = ⎣ ⎦ρ +, где выполняется (21).
В асимптотике при , как и в случае А), тангенс угла стремится к 1,
т.е. , но .
∞→Bn
Bn
nr
B ∞→
≈ Wn
nr
W
2/1
∞→
≈
На рисунке 3 приведены три кривые, отвечающие трем вышерассмотрен-
ным соотношениям объемов обучающей и проверочной выборок. Неравенства
(выписанные в рамочках) в заштрихованных областях выполняются независимо
от отношения nA : nB , в незаштрихованной – выполнение неравенств зависит от
отношения объемов подвыборок. В наибольшей степени преимущество по бы-
стродействию РИАНМ по сравнению с МУА проявляется в случае деления вы-
борки пополам, в наименьшей – когда в проверочной выборке всего одна точка.
7. Сравнительный анализ вычислительной сложности РИАРМ и
МУА
Известны два метода и две формулы (9) и (10) оценки сложности
вычислений релаксационных итерационных алгоритмов с рекуррентными
вычислениями (РИАРМ), отличающиеся на ρ+3. Сравним количество операций
МУА и алгоритм с меньшим числом операций (РИАРМ2), формулы (10) и (12).
Также как и в случае с РИАНМ проверяем условие (17).
Рассмотрим случай А), когда отношение nA : nB =2:1. С учетом перехода к
непрерывным переменным, подставив в (17) выражения (14) и (12), получим:
0263316 ≥−−++ ρηρη . (27)
Преобразуем (27) к виду 025)16)(3( ≥++− ρη . Откуда в соответствии с
условием (17), если η >3 должно выполняться неравенство
16
)3(
25
−
−
−≥
η
ρ , (28)
или по отношении к другой переменной – неравенство 3
)16(
25
+
+
−≥
ρ
η .
Построив гиперболу, соответствующую равенству (28), покажем на
рисунке 4 область на плоскости двух координат, в которой выполняется
условие (17). При подстановке N∈= Wnη в равенство (28) и округлением
r= ⎣ ⎦ρ + с избытком найдем область выполнения строгого неравенства (21), а
округлением r = ⎣ ⎦ρ _ с недостатком – область строгого неравенства (17).
Індуктивне моделювання складних систем, №5, 2013 196
Сравнительный анализ вычислительной сложности алгоритмов
Почти везде (т.к. если пВ ≥ 3 при любом количестве итераций (17)
выполняется) РИАРМ2 превосходит по быстродействию МУА, и только при пВ
=2 число итераций ограничено сверху, т.е. 0 < r ≤ 9. МУА имеет преимущество
в небольшой области значений пВ ∈ [1; 2], при пВ =2, есть ограничение r > 9, а
при пВ =1 нет ограничений по r. Тот же характер имеет граница для РИАРМ1
13
)3(
5.12
−
−
−≥
η
ρ , (29)
но график сдвинут правее при пересечении оси абсцисс (ρ=0) из точки η= 1.44 в
точку η=2.03. С учетом целочисленности значений пВ эти две гиперболы (28) и
(29) при анализе существенно не отличаются (сливаются в одну на участке
3>η> 2), только в точке при пВ =2 отсутствует ограничение на число итераций
(МУА имеет преимущество при любом числе итераций). В области параметров
(nW , r) ∈ N поскольку nB=1/3 nB W, то при nW=9 число итераций ∞→r , а значит
РИАРМ без ограничений быстрее, чем МУА, nW ≥ 9.
При использовании УКР при nB =1 и nB A : nB =2:1 условия (22) и (23)
всегда выполняются, а значит, оба варианта РИАРМ при любых ρ имеют
большее быстродействие, чем МУА.
Рис. 4 – Результаты сравнения скорости РИАРМ2 и МУА в плоскости значений
аргументов r и объема проверочной выборки nВ при условии nA : nB =2:1.
Рассмотрим случай Б) для любого nW ≥ 2 и соотношения nA:nB=(nB W – 1):1.
При подстановке (15) и (11) в (17) получим, что для выполнения неравенства
(17) следует провести для РИАРМ1 анализ неравенства
5)1(7294 +−+≤+ Wnrr . При подстановке (15) и (12) в (17) получим
5)1(7263 +−+≤+ Wnrr для РИАРМ2. После преобразований имеем две ли-
нейные зависимости и убеждаемся, что в области значений N∈r выше пря-
Індуктивне моделювання складних систем, № 5, 2013 197
Кондрашова Н.В.
мых
3
31
3
7
−= Wnr для РИАРМ1 и 145,3 −= Wnr для РИАРМ2 МУА имеет боль-
шее быстродействие, и наоборот, под прямыми находится область N∈r боль-
шего быстродействия РИАРМ, причем под прямой РИАРМ2 область больше.
Рис. 5 – Результаты сравнения быстродействия РИАРМ и МУА в плоскости
числа аргументов r «развернутой» модели и количества наблюдений nW при
условии nB =1, nA : nB=(nB W – 1):1.
Заштрихованные области соответствуют случаям безусловного
выполнения неравенств (17) и (21), незаштрихованная – зависит от
нерекуррентного метода вычисления параметров и критериев (варианта
РИАРМ).
Рассмотрим случай В) деления исходной выборки пополам, nA : nB = 1 : 1.
Подстановкой (16) и (11) в (17) получаем следующее неравенство для РИАРМ1:
02649 ≥−−+ ρηρη . (30)
Подстановкой (16) и (12) в (17) получаем неравенство для РИАРМ2:
02339 ≥−−+ ρηρη . (31)
Преобразуем (31) к виду (η - 3)(ρ + 9) ≥ -4. Откуда для РИАРМ2 получим
отношение 9
3
4
−
−
−≥
η
ρ , а для РИАРМ1 6
3
2
−
−
−≥
η
ρ . Две полученные
гиперболы, соответствующие равенствам (30) и (31), в области параметров (nВ,
r) ∈ N ничем не отличаются от гиперболы, полученной решением равенства
(29), только ось абсцисс они пересекают в разных точках: η =2,56 и η =2,67. В
области целочисленных значений (nВ, r) ∈ N эти 2 гиперболы сливаются в
одну. Их отличия можно пронаблюдать, построив их в области (nW , r) ∈ N.
Поскольку nB=0,5 nB W при nA : nB = 1:1, то ∞→r при nW=6 .
Індуктивне моделювання складних систем, №5, 2013 198
Сравнительный анализ вычислительной сложности алгоритмов
Рис. 6 – Результаты сравнения быстродействия РИАРМ и МУА в плоскости
числа аргументов r «развернутой» модели и количества наблюдений nW в за-
висимости от трех рассмотренных соотношений nA : nB
На рис. 6 приведены графики четырех функций )( Wnfr = , отвечающие
трем рассмотренным соотношениям nA : nB (четвертая функция для того, чтобы
показать отличие РИАРМ1 и РИАРМ2). В заштрихованных областях указанные
на рисунках неравенства выполняются независимо от отношения nA : nB, в
незаштрихованной – выполнение неравенств зависит от отношения точек в
подвыборках. В наибольшей степени преимущество по быстродействию
РИАРМ по сравнению с МУА, как и при сравнении пары РИАНМ и МУА,
проявляется в случае деления выборки пополам, а в наименьшей – когда в
проверке имеется одна точка.
B
8. Выводы
Сравнение вычислительной сложности рекуррентных и нерекуррентного
методов вычислений в ОРИА показало, что область значений числа аргументов
т, при которых проявляются преимущества нерекуррентных алгоритмов,
невелика и поэтому этот факт не может изменить общепринятого мнения о
предпочтительности рекуррентных вычислений.
Сравнительный анализ вычислительной сложности МУА с РИАНМ и
РИАРМ показал, что если в алгоритме МУА сделано одно усовершенствование
– отделена стадия вычисления ковариационный матрицы от переборной стадии,
то быстродействие ОРИА с нерекуррентными вычислениями зависит от числа
точек nB при любых возможных отношениях nA : nB. B
Сравнение РИАРМ и МУА выявило обширную область изменения числа
наблюдений nB 3≥ (nW 9 ) при отсутствии ограничений на число аргументов
(итераций), когда РИАРМ превосходит МУА по быстродействию в двух тради-
ционно применяемых вариантах разбиений: n
≥
A : nB = 1:1 и nA : nB = 2:1. Результа-
Індуктивне моделювання складних систем, № 5, 2013 199
Кондрашова Н.В.
ты сравнения вычислительной сложности РИАРМ и МУА в случае nA : nB = (nW -
1):1 показали, что между параметрами r и nW имеется линейная зависимость.
Выше этой линии МУА является более быстрым, по сравнению с РИАРМ, ниже
РИАРМ имеет большее быстродействие. Поэтому использование УКР (nB =1),
несколько ограничивает применение РИАРМ
B
2 в сравнении с МУА, при этом
важным является то, что , Wnr > 145,3 −= Wnr , а при некоррелированных ар-
гументах для внутренней сходимости «по структуре» достаточно [7]. Wnr 3≈
Литература
1. Павлов А. В. Обобщённый релаксационный итерационный алгоритм
МГУА. Індуктивне моделювання складних систем. Збірник наук. праць. –
К.: МННЦІТС, 2011. вип.3. – С. 95-108.
2. Шелудько О.И., Патереу С.Г. Упрощенный алгоритм идентификации
характеристик сложных объектов по МГУА. В кн.: программы прямого
синтеза моделей (по принципу самоорганизации). Киев: РФАП, 1975,
вып.1.
3. Павлов А. В. Модифицированный алгоритм с комбинаторной селекцией и
ортогонализацией переменных и его анализ. Індуктивне моделювання
складних систем. Збірник наук. праць. К.:МННЦІТС, 2010, вип.2. –
С.130-139.
4. Кондрашова Н.В., Павлов В. А., Павлов А.В. Многорядный алгоритм
веерных решений // Вісник Національного технічного університету
України „КПІ”. Інформатика, управління та обчислювальна техніка. К.,
«Век+», 2006. – 45. – С. 218-227.
5. Степашко В. С. Метод критических дисперсий как аналитический аппа-
рат теории индуктивного моделирования / Степашко В. С. // Проблемы
управления и информатики. – № 2. – 2008. – С. 8-26.
6. Ивахненко А.Г. Моделирование сложных систем по экспериментальным
данным / Ивахненко А.Г., Юрачковский Ю.П. – М.: Радио и связь, 1987.–
120 с.
7. Павлов А. В. Технологія побудови регресійних моделей на основі
релаксаційного ітераційного алгоритму з рекурентними обчисленнями
об’єктів [Текст] : Дис. ... канд. техн. наук : 05.13.06 / Павлов Андрій
Володимирович; Міжнародний науково-навчальний центр
інформаційних технологій то систем МОН молоді та спорту України. –
К., 2012. – 251 с.
8. Kondrashova N.V., Pavlov A.V., Pavlov Ya.V. Sample division with sliding
interval as a method of increase of accuracy for time series forecasting – //
Proc. of ICIM 2008. 2nd International conference on inductive modeling,
Sept.15-19, 2008. Kyiv. - P. 250-254, ISBN 978-966-02-4889.
9. Ивахненко А.Г. Системы эвристической самоорганизации в технической
кибернетике. – Киев: «Техніка», 1971. – 372 с.
Індуктивне моделювання складних систем, №5, 2013 200
|
| id | nasplib_isofts_kiev_ua-123456789-83671 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0044 |
| language | Russian |
| last_indexed | 2025-12-07T16:26:12Z |
| publishDate | 2013 |
| publisher | Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| record_format | dspace |
| spelling | Кондаршова, Н.В. 2015-06-21T17:45:21Z 2015-06-21T17:45:21Z 2013 Сравнительный анализ вычислительной сложности алгоритмов релаксационно-итерационного типа / Н.В. Кондаршова // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2013. — Вип. 5. — С. 184-200. — Бібліогр.: 9 назв. — рос. XXXX-0044 https://nasplib.isofts.kiev.ua/handle/123456789/83671 681.513.8 Несмотря на то, что обобщенный релаксационный итерационный алгоритм (ОРИА) на сегодня самый быстрый и точный итерационный алгоритм МГУА, для которого доказана сходимость, его аналоги: многорядный упрощенный алгоритм (МУА) и многорядный алгоритм с комбинаторикой и селекцией обобщенных переменных (МАКСО) также имеют свою «нишу» применимости. В плоскости двух параметров: размера выборки (числа наблюдений) и сложности модели (числа аргументов) показаны области превышения вычислительной сложности (быстродействия) одного алгоритма по отношению к другому. Проведен сравнительный анализ быстродействия нерекуррентного и рекуррентных вариантов ОРИА между собой и каждого из них в сравнении с МУА. Незважаючи на те, що узагальнений релаксаційний ітераційний алгоритм (УРІА) на сьогодні найшвидший і точний ітераційний алгоритм МГУА, для якого доведена збіжність, його аналоги: багаторядний спрощений алгоритм (БСА) і багаторядний алгоритм з комбінаторикою і селекцією узагальнених змінних (БАКСУ) також мають свою «нішу» застосовності. У площині двох параметрів: розміру вибірки (числа спостережень) і складності моделі (числа аргументів) показані області перевищення обчислювальної складності (швидкодії) одного алгоритму по відношенню до іншого. Проведено порівняльний аналіз швидкодії нерекуррентного та рекурентних варіантів УРІА між собою і кожного з них у порівнянні з БСА. Despite the fact that the generalized relaxation iterative algorithm (GRIA) for today is most fast and precise iterative algorithm GMDH for which the convergence is proved, its analogues: a multi-layered simplified algorithm (MSA) and multi-layered algorithm with combinatorics and selection of generalized variables (MACSG) also have their "niche" applicability. Areas of exceedance computational complexity (running speed) of an algorithm with respect to another in the plane of two parameters such as sample size (number of observations) and model complexity (number of arguments) are shown. A comparative analysis of the running speed of nonrecurrent and recurrent variants GRIA between themselves and each of them compared to the MSA is provided. ru Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Індуктивне моделювання складних систем Наукові статті Сравнительный анализ вычислительной сложности алгоритмов релаксационно-итерационного типа Article published earlier |
| spellingShingle | Сравнительный анализ вычислительной сложности алгоритмов релаксационно-итерационного типа Кондаршова, Н.В. Наукові статті |
| title | Сравнительный анализ вычислительной сложности алгоритмов релаксационно-итерационного типа |
| title_full | Сравнительный анализ вычислительной сложности алгоритмов релаксационно-итерационного типа |
| title_fullStr | Сравнительный анализ вычислительной сложности алгоритмов релаксационно-итерационного типа |
| title_full_unstemmed | Сравнительный анализ вычислительной сложности алгоритмов релаксационно-итерационного типа |
| title_short | Сравнительный анализ вычислительной сложности алгоритмов релаксационно-итерационного типа |
| title_sort | сравнительный анализ вычислительной сложности алгоритмов релаксационно-итерационного типа |
| topic | Наукові статті |
| topic_facet | Наукові статті |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/83671 |
| work_keys_str_mv | AT kondaršovanv sravnitelʹnyianalizvyčislitelʹnoisložnostialgoritmovrelaksacionnoiteracionnogotipa |