К.т.н. Заика И.В.

Таганрогский государственный педагогический институт им. А.П. Чехова, Россия

Метод автоматической идентификации решений систем уравнений на основе сортировки

Для идентификации нулей линейных и нелинейных алгебраических систем уравнений, а так же трансцендентных систем уравнений применяется схема сортировки с взаимно однозначным соответствием входных и выходных индексов сортируемых элементов. К программе сортировки [1] подсоединяется условный оператор, локализующий все минимумы среди элементов входной последовательности. Фиксируется любое меньшее половины минимального расстояния между минимумами. Условие локализации всех минимальных в -окрестности значений дискретизированной функции одной переменной на равномерной сетке с шагом примет вид [1]: . Здесь – элемент массива входных индексов, располагаемого в порядке отсортированных по неубыванию значений функции, образующих одномерный массив. Условие означает, что в -окрестности узла с индексом нет индекса входного элемента, который бы превосходил элемент с индексом . Максимумы локализуются аналогично [1]. Нули функции идентифицируются как достаточно малые минимумы модулей значений на равномерной сетке. С использованием плоской равномерной прямоугольной сетки схема распространяется на идентификацию экстремумов и нулей функций двух переменных [2]. Дискретизированные значения функции интерпретируются как двумерные массивы. Данная схема следующим образом применяется к безусловной численной локализации нулей систем однородных уравнений. Пусть исходная система нелинейных уравнений преобразована к виду однородной системы

(1)

с действительными левыми частями (как последует из построения, метод распространяется на случай комплексной левой части). Совокупность аргументов можно рассматривать как n-мерный вектор с действительными компонентами. Аналогично совокупность функций представляет собой также n-мерный вектор с действительными компонентами. Пусть требуется найти все решения системы (1) в многомерном параллелепипеде, входящем в область ее определения. Строится равномерная сетка, в узлах которой значения канонической нормы вектор-функции из левой части (1) (для определенности норма – сумма модулей компонент) принимаются за элементы массива:

, . (2)

На вход алгоритма идентификации минимумов функции n переменных подается массив (2), после чего идентифицируются все нули системы (1) как минимумы нормы левой части. При этом первоначально идентифицируются все минимумы, затем среди них выбираются те, которые близки к нулю с априори заданной точностью : .

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

Схема без изменения применима для приближенных решений систем линейных и нелинейных алгебраических, а также трансцендентных уравнений [2], по способу компьютеризации отличаясь от аналогов [4, 5]. На вход метода поступают значения функции, которые с учетом общности ограничений могут вырабатываться в результате решения некоторой другой задачи в реальном времени. Существенным ограничением при этом является требование достаточной малости шага дискретизации. Отличительным качеством, как и в двумерном случае, остается отсутствие начальных приближений, а также области локализации экстремумов, используемых в математических методах [5,6]. Численный эксперимент показывает применимость схемы в случае вектор-функций из левой части (1) со сложным рельефом [2], включая разрывы первого рода.

Литература:

1. Ромм Я.Е. Локализация и устойчивое вычисление нулей многочлена на основе сортировки. I // Кибернетика и системный анализ. – 2007. – № 1. – С. 165 – 182.

2. Заика И.В. Разработка и исследование схем оптимизации на основе алгоритмов сортировки с приложением к идентификации экстремумов решений дифференциальных уравнений. – Таганрог: ТРТУ, 2007, автореферат диссертации на соискание ученой степени канд. техн. наук.

3. Ромм Я.Е. Параллельная сортировка слиянием по матрицам сравнений. II // Кибернетика и системный анализ. – 1995. – № 4. – С. 13 – 37.

4. Березин И.С., Жидков Н.П. Методы вычислений. Т.2. – М.: Физматгиз, 1962. – 640 с.

5. Демидович Б.П., Марон И.А. Основы вычислительной математики. – М.: Физматгиз, 1963. – 660 с.

6. Васильев Ф.П. Численные методы решения экстремальных задач. – М.: Наука, 1988. – 552с.