Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,074

ЛОКАЛИЗАЦИЯ ЭКСТРЕМУМОВ И НУЛЕЙ ФУНКЦИЙ НА ОСНОВЕ СОРТИРОВКИ В ПРИЛОЖЕНИИ К АНАЛИЗУ УСТОЙЧИВОСТИ

Ромм Я.Е. 1 Заика И.В. 1 Тюшнякова И.А. 1
1 Таганрогский институт имени А.П. Чехова (филиал), ФГБОУ ВО «Ростовский государственный экономический университет (РИНХ)»
Предлагается распараллеливаемый компьютерный метод численной оптимизации на основе сортировки, позволяющий идентифицировать с априори заданной границей погрешности экстремумы и нули функций многих переменных по значениям и индексам местоположения. Метод существенно отличается от известных построением на основе сортировки, возможностью распараллеливания и произвольностью задания границ области всех экстремумов и нулей. Метод применяется для поиска экстремумов и нулей разностных решений систем обыкновенных дифференциальных уравнений, собственных значений матриц. Строится метод анализа устойчивости решений систем обыкновенных дифференциальных уравнений на основе нахождения при помощи сортировки собственных значений матрицы постоянных коэффициентов системы линейных обыкновенных дифференциальных уравнений произвольного порядка. Метод используется для компьютерного анализа устойчивости по Ляпунову системы как в случае асимптотической, так и неасимптотической устойчивости. Отмечаются приложения к анализу экстремальных особенностей сигналов и изображений.
параллельная численная оптимизация
сортировка
обыкновенные дифференциальные уравнения
устойчивость
анализ экстремальных особенностей сигналов
1. Веселая А.А. Вычисление нулей и экстремумов функций при вариации параметров на основе сортировки с приложением к моделированию устойчивости систем линейных дифференциальных уравнений: автореф. дис. ... канд. техн. наук. – Таганрог: ТТИ ЮФУ, 2009. – 18 с.
2. Заика И.В., Ромм Я.Е. Метод нахождения экстремумов решений дифференциальных уравнений на основе адресной сортировки / Депонированная рукопись № 908-В2003 12.05.2003.
3. Ромм Я.Е. Компьютерно-ориентированный анализ устойчивости на основе рекуррентных преобразований разностных решений обыкновенных дифференциальных уравнений // Кибернетика и системный анализ. – 2015. – Т. 51, № 3. – С. 107–124.
4. Ромм Я.Е. Локализация и устойчивое вычисление нулей многочлена на основе сортировки. I // Кибернетика и системный анализ. – 2007. – № 1. – С. 165–183.
5. Ромм Я.Е. Параллельная сортировка слиянием по матрицам сравнений. I // Кибернетика и системный анализ. – 1994. – № 5. – С. 3–23.
6. Ромм Я.Е. Применение сортировки для поиска нулей и особенностей функций с приложением к идентификации плоских изображений / Я.Е. Ромм, И.А. Тюшнякова; Федеральное агентство по образованию, Гос. образовательное учреждение высш. проф. образования «Таганрогский гос. пед. ин-т». – Таганрог, 2009.
7. Ромм Я.Е. Схемы численной оптимизации на основе алгоритмов сортировки с приложением к идентификации экстремумов решений дифференциальных уравнений: учебное пособие для студентов вузов, обучающихся по специальности 050202.65 «Информатика» / Я.Е. Ромм, И.В. Заика; М-во образования и науки Российской Федерации, Гос. образовательное учреждение высшего проф. образования «Таганрогский гос. педагогический ин-т». – Таганрог, 2010.
8. Ромм Я.Е., Заика И.В. Программная локализация экстремумов функций и разностных приближений решений дифференциальных уравнений // Известия высших учебных заведений. Северо-Кавказский регион. Серия: Технические науки. – 2005. – № M. – С. 55.
9. Ромм Я.Е., Корякин А.Б. Построение признаков распознавания с применением сортировки для обработки гидроакустических сигналов // Известия ЮФУ. Технические науки. – 2010. – № 5. – С. 95–102.
10. Ромм Я.Е., Соколов И.Н. Компьютерное диагностирование аритмии, тахикардии и брадикардии с применением схем сортировки // Известия ЮФУ. Технические науки. – № 7. – 2013. – С. 131–136.
11. Ромм Я.Е., Тренкеншу А.И. Идентификация тренда и конфигураций разворота валютного рынка FOREX на основе алгоритмов сортировки с применением корреляционного анализа // Современные проблемы науки и образования. – 2013. – № 2.
12. Ромм Я.Е., Тюшнякова И.А. Метод вычисления собственных значений матриц на основе сортировки в приложении к распознаванию изображений // Известия высших учебных заведений. Северо-Кавказский регион. Серия: Технические науки. – 2006. – № 1. – С. 11–20.
13. Ромм Я.Е., Тюшнякова И.А. Программная идентификация нулей и особенностей функций на основе сортировки с приложением к цифровой фильтрации // Проблемы программирования. – Киев, 2010. – № 2–3. – С. 593–603.
14. Рюмин О.Г. Разработка и исследование алгоритмов распознавания изображений на основе определения экстремальных признаков замкнутых контуров с помощью
сортировки: автореф. дис. ... канд. техн. наук. – Таганрог: Изд-во ТТИ ЮФУ, 2008. – 16 с.
15. Romm Y.E., Zaika I.V. Numerical sorting-based optimization as applied to general differential and nonlinear equations / Cybernetics and Systems Analysis. – 2011. – Т. 47. – № 2. – С. 316–329.

Постановка вопроса. Ставится задача построить схему программной локализации (и приближенного вычисления) нулей и экстремумов функций одной и более переменных в произвольной области на плоскости. Аналогичная задача ставится для разностных приближений решений систем обыкновенных дифференциальных уравнений (ОДУ), при этом число уравнений и длина промежутка изменения независимой переменной могут быть произвольными. Помимо того, рассматриваемую схему требуется перенести на вычисление нулей многочленов с учетом их кратности, включая нули характеристического многочлена матрицы. Схему предполагается применить для компьютерного анализа устойчивости по Ляпунову системы ОДУ как в случае асимптотической, так и неасимптотической устойчивости на основе параллельного метода нахождения собственных значений матрицы постоянных коэффициентов системы линейных ОДУ произвольного порядка.

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

y = f(x) (1)

на промежутке [x(0), x(N)] в области ее определения. Строится равномерная сетка:

pomm01.wmf x? = x(0) + ?h, ? = 0, 1, ..., N.

На сетке считываются значения функции (1)

c[i] = f(xi–1), i = 1, 2, ..., N. (2)

Элементы массива (2) сортируются. Используется быстрая сортировка, основанная на адресном слиянии двух упорядоченных массивов по матрице сравнений, детально описанная в [3–5]. К выходу сортировки подсоединяется условный оператор, осуществляющий локализацию каждого минимума в окрестности произвольно заданного радиуса ? среди элементов (2), при условии, что ? меньше половины расстояния между любыми двумя соседними минимумами. Такой оператор можно представить соотношением pomm02.wmf l = 1, 2, ..., k – 1. Индексы E[k] входных элементов располагаются на выходе в порядке элементов отсортированного массива. Смысл оператора в том, что в ?-окрестности входного элемента с индексом E[k] нет элемента в отсортированном массиве, превосходящего по значению элемент с этим индексом. Данный оператор ниже называется оператором локализации минимума. После локализации минимума выполняется спуск к наименьшему значению в окрестности локализованной точки. Он осуществляется выбором наименьшего значения в сужаемой окрестности c фиксированным числом элементов равномерной сетки, пока не достигается требуемая точность.

Например, все минимумы функции y = sin(x) на [–30, 30] в результате работы программы, листинг которой представлен в [7, 15], примут значения

Достигнутая точность приближения характерна для излагаемого метода.

Инвариантность метода относительно длины промежутка достигается путем смещения базового промежутка с числом узлов N на расстояние, равное его длине. Во избежание ложных экстремумов отсекаются обе границы текущего промежутка, проверка его границ на экстремумы производится с помощью сортировки. Эта сортировка локализует экстремумы по ранее описанной схеме для элементов массива, образуемых значениями функции (1) слева от правой границы и справа от левой границы. В результате достигается инвариантность схемы относительно размеров области поиска экстремумов. По построению схема инвариантна относительно вида функции (2), на которую не накладывается математических ограничений. Функция, в частности, может быть задана таблично, при этом спуск окажется излишним.

Вычисление всех локальных максимумов в области с произвольно заданными границами можно произвести, если условие локализации минимума заменить на условие локализации максимума путем обратного направления просмотра элементов отсортированного массива: pomm03.wmf l = 1, 2, ..., n – k.

Вычисление нулей функции одной действительной переменной. Для локализации и вычисления нулей функции (1) достаточно на вход сортировки подать абсолютные величины ее значений на равномерной сетке pomm04.wmf i = 1, 2, ..., n, и искать минимумы описанным выше способом. Например, та же программа локализует и вычислит все нули многочлена

P = P1?P2?P3,

где pomm05.wmf

pomm06.wmf

pomm07.wmf

в виде

1.00000000000000000E+0000 0.00000000000000E+0000

3.00000000000000000E+0000 0.00000000000000E+0000

…………………………………………………

2.21234500000000000E+0001 0.00000000000000E+0000

2.30000000000000000E+0001 0.00000000000000E+0000

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

z = f(x, y) (3)

в области ее определения первоначально задаются текущие промежутки с границами [x(0), x(N)] и [y(0), y(M)]. Внутри ограниченных ими прямоугольников строится равномерная прямоугольная сетка:

pomm08.wmf x? = x(0) + ?h,

? = 0, 1, ..., N; y? = y(0) + ?h, ? = 0, 1, ..., M.

Для нахождения минимумов функции (3) выполняется проход в направлении оси OY вдоль j-го столбца прямоугольной сетки, во время которого находится минимальное по строкам значение c[j] = min f(xj, yi) (1 ? i ? M), этот минимум заносится на вход сортировки как j-й элемент сортируемого одномерного массива. К выходу процедуры подсоединяется оператор локализации минимума. Спуск к наименьшему значению в окрестности локализованной точки осуществляется с помощью выбора наименьшего значения в сужаемой окрестности c фиксированным числом элементов в сетке, причем по обеим переменным, пока не будет достигнута требуемая точность. Такой спуск повторяется дважды [4] с целью повышения точности приближения. Локализация максимума производится аналогично одномерному случаю.

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

Вычисление нулей функции двух переменных. Нули функции (3) вычисляются по описанной для минимумов схеме, если на вход метода подать

pomm09.wmf (4)

Все локализованные минимумы модуля исследуемой функции будут включать ее нули. Их можно идентифицировать по значению функции. Если других минимумов нет, то будут локализованы и вычислены именно нули в произвольно заданной и зафиксированной области на плоскости. В частности, так вычисляются все нули многочленов с комплексными коэффициентами [1, 13]. Изложенная выше схема отличается от известных построением на основе сортировки, «автоматизмом» и отмеченной инвариантностью программной локализации нулей и экстремумов. В отличие от схем, ориентированных только на вычисление нулей, по изложенной схеме вычисляются как нули, так и произвольные экстремумы в произвольной области на плоскости.

Программной особенностью схемы является ее инвариантность относительно размеров области, не требующая объявления динамических массивов. Схема обладает параллелизмом на основе разбиения области на взаимно независимые фрагменты, а также на основе параллелизма использованных сортировок.

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

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

Схема локализации и вычисления экстремальных значений и нулей решений систем обыкновенных дифференциальных уравнений. Пусть рассматривается задача Коши для уравнения

pomm10.wmf y(x0) = y0. (5)

На промежутке [x0, xn] строится равномерная сетка, приближенное решение задачи (5) вычисляется по разностной схеме. Пусть для определенности выбран метод Эйлера:

pomm11.wmf xi = x0 + ih,

i = 1, 2, ..., n, pomm12.wmf (6)

Значения (6) принимаются за элементы сортируемого массива

c[i] = yi–1, i = 1, 2, ..., n. (7)

Элементы (7) сортируются. Присоединение условия локализации минимумов (максимумов) к программе сортировки элементов (7) влечет устойчивую локализацию и вычисление экстремумов приближенного решения задачи (5) [3, 15]. На промежутке с произвольно заданными границами [X00, Xnn] для исключения ложных экстремумов, как и выше, на концах текущих промежутков используется процедура сортировки с соответственным условием локализации экстремумов. Для случая системы дифференциальных уравнений схема применяется к каждому уравнению в отдельности. Детальное описание и другие примеры на случай системы приводятся в [7]. Для локализации нулей достаточно на вход сортировки подать абсолютные величины значений приближенного решения на равномерной сетке.

Локализация и вычисление собственных значений матриц. Собственные значения матрицы

pomm13.wmf

вычисляются по описанной схеме как нули характеристического многочлена

pomm14.wmf

Его коэффициенты предварительно определяются по методу Леверье: решается система уравнений Ньютона:

pomm15.wmf

где pomm16.wmf, Sk = Sp(Ak) – след матрицы Ak. Многочлен pomm17.wmf (? = x + Iy) задан своими коэффициентами, для формирования соответственной многочлену функции f(x, y), которая подается на вход метода, используется биномиальное разложение [13] или значение многочлена умножается на комплексно-сопряженное значение. В результате

pomm18.wmf

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

Приложение метода к анализу устойчивости. Метод анализа устойчивости линейной системы ОДУ с матрицей постоянных коэффициентов базируется на известных утверждениях: система устойчива тогда и только тогда, когда все характеристические нули матрицы правой части обладают неположительными вещественными частями, причем характеристические нули, имеющие нулевые вещественные части, допускают лишь простые элементарные делители. Система асимптотически устойчива тогда и только тогда, когда все характеристические нули матрицы правой части имеют отрицательные вещественные части. Алгоритм анализа устойчивости строится путем соединения этих утверждений с компьютерным методом идентификации нулей характеристического многочлена с учетом кратности на основе сортировки, инвариантным относительно области поиска нулей:

1. Вычисляются (локализуются с наперед заданной точностью) все нули характеристического многочлена без учета кратности.

2. Если среди них хоть один имеет положительную вещественную часть, то система неустойчива и анализ закончен. Иначе выполняется переход к п. 3.

3. Если число нулей с неположительной вещественной частью равно n, то они все различны и система устойчива. Анализ закончен. Иначе выполняется переход к п. 4.

4. Выполняется проверка кратности нулей с отрицательной вещественной частью. Если общее число нулей есть n, то характеристические нули с нулевой вещественной частью все различны, система устойчива, анализ закончен. Если общее число нулей меньше n, то среди нулей с нулевой вещественной частью имеются кратные, система неустойчива.

5. Конец алгоритма.

Вопрос об асимптотической устойчивости решается в один этап: если все нули имеют отрицательную вещественную часть, то система асимптотически устойчива, иначе система не является асимптотически устойчивой [1, 13].

Компьютерный анализ устойчивости можно дополнить методами из [3], распространяемыми на случай нелинейных систем.

Приложения к анализу экстремальных особенностей сигналов и изображений. Массив оцифрованных сигналов подается на вход сортировки в виде числовой последовательности. С некоторым радиусом локализации (радиус зависит от предметной области и природы сигналов) в этой последовательности идентифицируются все локальные экстремумы. Идентифицированные по значению и местоположению экстремумы интерпретируются как первичные экстремальные признаки объекта, который требуется выделить. Далее, выделяются все экстремумы в окрестности индекса каждого первичного экстремального признака. Полученное сочетание экстремумов интерпретируется в содержательном смысле исследуемой предметной области и выделяемого объекта. На этой основе удается частично автоматизировать диагностику электрокардиограмм [10], выделить объект по данным гидроакустической локации [9]. Наиболее существенные экстремумы (экстремальные признаки) можно найти автоматически, задав в программе итерации с возрастающим радиусом локализации до фиксированного числа повторений идентифицированных экстремумов. Так удается найти существенные признаки распознаваемого изображения [14], выделить тренд графического анализа, определить его тенденцию и точку разворота [11]. При этом целесообразно использовать преобразование последовательности первичных экстремумов как новой последовательности на вход метода, на этой основе удается выделить целочисленные идентификаторы для распознавания достаточно сложных изображений.

Заключение

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

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


Библиографическая ссылка

Ромм Я.Е., Заика И.В., Тюшнякова И.А. ЛОКАЛИЗАЦИЯ ЭКСТРЕМУМОВ И НУЛЕЙ ФУНКЦИЙ НА ОСНОВЕ СОРТИРОВКИ В ПРИЛОЖЕНИИ К АНАЛИЗУ УСТОЙЧИВОСТИ // Фундаментальные исследования. – 2015. – № 12-4. – С. 718-723;
URL: http://www.fundamental-research.ru/ru/article/view?id=39611 (дата обращения: 19.10.2019).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074