Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,441

LOCALIZATION OF ZEROS OF FUNCTIONS OF SEVERAL VARIABLES, BASED ON THE SORTING IN THE APPLICATION TO THE STABILITY ANALYSIS OF ORDINARY DIFFERENTIAL EQUATIONS

Veselaya А.А. 1 Zaika I.V. 1 Tyushnyakova I.A. 1
1 Taganrog Institute named after A.P. Chekhov (branch) Rostov State University of Economics
Описан распараллеливаемый компьютерный метод численной оптимизации на основе устойчивой сортировки, который позволяет определить с априори заданной границей погрешности нули функций многих переменных по значениям и индексам местоположения. Метод отличается от известных построением на основе сортировки, возможностью распараллеливания и произвольностью задания границ области всех нулей функции. Строится программный метод анализа устойчивости решений систем обыкновенных дифференциальных уравнений на основе нахождения собственных значений матрицы постоянных коэффициентов системы линейных обыкновенных дифференциальных уравнений произвольного порядка при помощи сортировки. Метод применяется для компьютерного анализа устойчивости по Ляпунову системы обыкновенных дифференциальных уравнений в случаях асимптотической и неасимптотической устойчивости. Изложенная методика применяется к анализу устойчивости реальной физической системы.
Proposed parallelized computer numerical optimization method on a sustainable basis the sort that allows to identify a priori a given boundary error zeros of functions of several variables on the value and index position. The method differs from the known building on the basis of the sort, the possibility of parallelization and arbitrary boundaries of the field all zeros job. Construct a software method for analyzing the stability of solutions of systems of ordinary differential equations on the basis of a finding by means of sorting the eigenvalues of the constant coefficients of linear ordinary differential equations of arbitrary order. The method is used for computer analysis of Lyapunov stability of a system of ordinary differential equations in the case of asymptotic and non-asymptotic stability. The stated procedure is used to analyze the stability of the real physical system.
numerical optimization
sorting
ordinary differential equations
stability
1. Andreeva E.A. Variacionnoe ischislenie i metody optimizacii. M.: Vysshaja shkola, 2010. 586 p.
2. Antonov V.I. Linejnaja algebra i analiticheskaja geometrija / Prospekt. 2011. 139 p.
3. Bugrov Ja.S. Vysshaja matematika. M: Drofa, 2004. 284 p.
4. Vasil’ev F.P. Metody optimizacii. M.: MCNMO, 2011. 433 p.
5. Vasil’eva A.B., Tihonov N.A. Integralnye uravnenija. M.: Fizmatlit, 2004.
6. Veselaja A.A. Vychislenie nulej i jekstremumov funkcij pri variacii parametrov na osnove sortirovki s prilozheniem k modelirovaniju ustojchivosti sistem linejnyh differencialnyh uravnenij. Avtoreferat dissertacii na soiskanie uchenoj stepeni kand. tehn. nauk. Taganrog, 2009. 19 p.
7. Galiseev G.V. Programmirovanie v Delphi. M.: Dialektika, 2003.
8. Zaika I.V., Tjushnjakova I.A. Programmnoe opredelenie nulej funkcij i raznostnyh reshenij sistem obyknovennyh differencialnyh uravnenij na osnove sortirovki // Nauchnyj vestnik. 2015. no. 4 (6). pp. 39–52.
9. Ilin V.A. Vysshaja matematika / «TK Velbi». 2002.
10. Makkonnell D. Analiz algoritmov. M.: Tehnosfera, 2002. 304 p.
11. Romanko V.K. Kurs differencialnyh uravnenij i variacionnogo ischislenija. M.: LBZ. 2001.
12. Romm Ja.E., Zaika I.V., Labinceva A.A. Bezuslovnaja chislennaja optimizacija pri variacii parametrov. I / Deponirovannaja rukopis no. 193-V2008 04.03.2008.
13. Romm Ja.E., Zaika I.V. Programmnaja lokalizacija jekstremumov funkcij i raznostnyh priblizhenij reshenij differencialnyh uravnenij. Izvestija vysshih uchebnyh zavedenij // Izvestija vysshih uchebnyh zavedenij. Severo-Kavkazskij region. Serija: Tehnicheskie nauki. 2005. no. M. pp. 55.
14. Romm Ja.E., Gurevich M.Ju., Belokonova S.S., Soloveva I.A. Vychislenie nulej i poljusov funkcij na osnove ustojchivoj adresnoj sortirovki s prilozheniem k poisku i raspoznavaniju // Problemi programuvannja. 2004. no. 2–3. pp. 462.
15. Romm Ja.E., Tjushnjakova I.A. Primenenie sortirovki dlja poiska nulej i osobennostej funkcij s prilozheniem k identifikacii ploskih izobrazhenij // Uchebnoe posobie. Taganrog, 2009.
16. Trenogin V.A. Funkcionalnyj analiz. M.: Fizmatlit, 2002.
17. Tjushnjakova I.A. Razrabotka i issledovanie shem primenenija sortirovki dlja poiska nulej i osobennostej funkcij s prilozheniem k identifikacii ploskih izobrazhenij // Dissertacija na soiskanie uchenoj stepeni kandidata tehnicheskih nauk. Taganrog, 2006.
18. Fljonov M.E. Delphi. Sekrety programmirovanija. SPb.: Piter, 2006.
19. Harbor R. Sistemy upravlenija s obratnoj svjazju. M.: LBZ, 2001.
20. Jelsgolc L.Je. Differencialnye uravnenija i variacionnoe ischislenie. M.: Nauka, 1969.
21. Chirtik A.A. Programmirovanie v Delphi. SPb: Piter, 2011.
22. Romm Y.E., Zaika I.V. Numerical sorting-based optimization as applied to general differential and nonlinear equations // Cybernetics and Systems Analysis. 2011. T. 47. no. 2. pp. 316–329.

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

Схема сортировки и вычисление нулей функций нескольких переменных по индексам данных

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

ves01.wmf (1)

В области определения функции задается промежуток ves02.wmf. На промежутке ves03.wmf, ves04.wmf, ves05.wmf считываются значения функции (1)

ves06.wmf, ves07.wmf. (2)

Значения c[i] функции f(x) сортируются. После осуществляется локализация минимумов функции в наперед заданной окрестности ε среди элементов (2), с помощью условного оператора ves09.wmf, ves10.wmf. Где e[k] – индексы сортируемых элементов, располагающиеся на выходе по порядку отсортированного массива. Чтобы вычислить нули функции, необходимо на вход сортировки подать величины (2) взятые по модулю ves11.wmf, ves12.wmf, и искать нули как минимумы модуля.

Для нахождения минимумов для функции двух переменных ves13.wmf внутри области определения ves14.wmf и ves15.wmf задается прямоугольная сетка: ves16.wmf, ves17.wmf, ves18.wmf, ves19.wmf, ves20.wmf. Далее осуществляется проход вдоль оси OY, j столбца прямоугольной сетки, в результате которого находится наименьшее значение ves22.wmf, ves23.wmf, полученный минимум поступает на вход сортировки как j элемент одномерного массива. После чего оператор локализации минимума вычисляет все индексы минимумов функции двух переменных.

Описанная схема переносится для вычисления всех нулей функции z. На вход программы достаточно подать значения: ves24.wmf. Нули функции локализуются как минимумы модуля [1–7, 17]. Таким образом, вычисляются все корни полиномов с комплексными коэффициентами [9, 10, 12, 13].

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

Собственные значения квадратной матрицы А размерности n×n определяются по описанной выше схеме как нули характеристического полинома:

ves25.wmf.

Коэффициенты данного полинома вычисляются с помощью метода Леверье. Для этого необходимо решить систему уравнений Ньютона: ves26.wmf. Здесь ves27.wmf, ves28.wmf – след матрицы Аk. Полином ves29.wmf (ves30.wmf) задается своими коэффициентами. Для того чтобы на вход метода подать соответственную полиному функцию f(x, y), применяется биномиальное разложение [3, 6, 8]; иначе значение полинома умножается на комплексно-сопряженное. В результате получим функцию ves31.wmf. В случае если коэффициенты характеристического полинома вычислены с достаточной точностью, изложенный метод определения собственных значений матриц является устойчивым ввиду фактически верного вычисления нулей полиномов с учетом кратности [14–16].

Программное определение нулей характеристического полинома матрицы постоянных коэффициентов системы линейных ОДУ произвольного порядка

Пусть дана система линейных ОДУ в матричной форме с постоянными коэффициентами [8, 11, 22]

ves32.wmf, (3)

где Y и A – квадратные матрицы постоянных коэффициентов размерности n×n. Общее решение системы ОДУ (3) с постоянной матрицей A:

ves34.wmf. (4)

Начальные условия для (4):

ves35.wmf, (5)

тогда решение ves36.wmf удовлетворяет задаче Коши ves37.wmf. Ставится цель: провести исследование решения (4) системы ОДУ (3) на устойчивость в смысле Ляпунова [11, 12].

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

Из I теоремы Ляпунова об устойчивости известно, что нули характеристического полинома матрицы A из (3) имеют связь с характером устойчивости (3): в случае если все собственные значения имеют отрицательные действительные части, то система асимптотически устойчива; в противном случае система неустойчива [19, 20].

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

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

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

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

Пример 1. Пусть система (4) имеет матрицу коэффициентов:

ves38.wmf

Необходимо определить знаки действительной части собственных значений матрицы. Ниже представлен алгоритм, который вычисляет действительные части собственных значений с точностью ves39.wmf.

vesel1.wmf

Результаты вычислений: – 3.000; 2.510; – 0.430; 4.725; 9.985.

С помощью изложенной программы удается вычислить действительные части нулей с учетом знака за относительно малый период времен. Точность вычислений проигрывает по сравнению с результатами полной программы, однако это оказывается достаточным для того, чтобы сделать вывод о неустойчивости точки покоя системы. Предложенный метод используется для быстрого анализа устойчивости. В случае если действительные части положительны, то система неустойчива. Для достоверности оценки устойчивости можно осуществить локализацию действительных и мнимых частей нулей характеристического многочлена. Результат вычисления действительных и мнимых частей (полный код программы приводится в [6]):

Действительная часть нулей

Мнимая часть нулей

Значение функции

– 3.00000000000000000E + 0000

2.51052877410466521E + 0000

– 4.28061588346591394E-0001

– 4.72255545982224341E + 0000

1.06400882740641695E + 0001

0.00000000000000000E + 0000

– 2.71473540786538243E-0029

– 6.52520446799852453E-0056

– 4.44724119213053305E-0029

– 4.38707603928584072E-0034

0.00000000000000E + 0000

1.23259516440783E-0032

5.49509021016461E-0106

3.25482160601443E-0032

2.30564629222262E-0029

 

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

Пример 2. Оценить устойчивость системы. Система имеет следующий вид:

ves40.wmf

Листинг программы полностью приводится в [6]. Результат работы программы:

Действительная часть нулей

Мнимая часть нулей

Значение функции

– 4.573

– 2.805

– 103.668

– 1.66.591

0.000

– 5.272

– 5.272

– 24.590

– 24.593

0.000

0.000

0.000

0.000

0.000

229.567

– 229.837

346.355

– 346.355

3.76070674693958763E + 0035

2.67668758647364437E + 0033

5.88014178051377293E + 0037

1.54394867607685689E + 0033

3.68630606796407673E + 0032

4.35465580557896453E + 0036

3.67676705867643764E + 0038

4.14596930357129645E + 0039

2.94264390362970963E + 0034

 

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

Заключение

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