Сравнительный анализ вычислительной сложности алгоритмов релаксационно-итерационного типа

Abstract

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

Незважаючи на те, що узагальнений релаксаційний ітераційний алгоритм (УРІА) на сьогодні найшвидший і точний ітераційний алгоритм МГУА, для якого доведена збіжність, його аналоги: багаторядний спрощений алгоритм (БСА) і багаторядний алгоритм з комбінаторикою і селекцією узагальнених змінних (БАКСУ) також мають свою «нішу» застосовності. У площині двох параметрів: розміру вибірки (числа спостережень) і складності моделі (числа аргументів) показані області перевищення обчислювальної складності (швидкодії) одного алгоритму по відношенню до іншого. Проведено порівняльний аналіз швидкодії нерекуррентного та рекурентних варіантів УРІА між собою і кожного з них у порівнянні з БСА.

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.