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

На правах рукописи

Заика Ирина Викторовна

ии3055741

РАЗРАБОТКА И ИССЛЕДОВАНИЕ СХЕМ ОПТИМИЗАЦИИ НА ОСНОВЕ АЛГОРИТМОВ СОРТИРОВКИ С ПРИЛОЖЕНИЕМ К ИДЕНТИФИКАЦИИ ЭКСТРЕМУМОВ РЕШЕНИЙ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ

Специальности:

05.13.17 - Теоретические основы информатики

05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Таганрог 2007

003055741

Работа выполнена на кафедре информатики Таганрогского государственного педагогического института

Научный руководитель: доктор технических наук,

профессор Ромм Яков Евсеевич

Официальные оппоненты: доктор технических наук,

профессор Карелин Владимир Петрович

доктор технических наук,

профессор Божеток Александр Витальевич

Ведущая организация: ФГНУ НИИ "СПЕЦВУЗАВТОМАТИКА" г. Ростов-на - Дону

Защита состоится _2007 г. в_часов на заседании диссертационного

совета Д 212.259.02 Таганрогского государственного радиотехнического университета по адресу 347928, г. Таганрог, Ростовская область, ГСП-17А, пер. Некрасовский, 44, ауд. Д-406.

С диссертацией можно ознакомиться в библиотеке Таганрогского государственного радиотехнического университета.

Автореферат разослан «_»__ 2006 г.

Ученый секретарь диссертационного совета Д 212.259.02 доктор технических наук, профессор

Бабенко Л.К.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. Современное состояние теории оптимизации характеризуется фундаментальными направлениями исследования в области линейного, . выпуклого, стохастического программирования, оптимального управления и численных методов приближенного решения экстремальных задач. Методы оптимизации находят широкое применение в задачах проектирования электрических цепей, определения оптимального варианта конструкции летательных аппаратов с целью максимальной прочности, минимального веса и стоимости, в задачах об ударе и колебаниях, где требуется вычислить амплитуду резонанса при наличии многочисленных источников возбуждения колебаний. Задачи оптимизации ставятся в аэрокосмической технике, промышленной технологии, в области автоматического регулирования, в экономике, банковском деле. Существующие методы делятся на методы условной и безусловной оптимизации. Первые относятся к разделам теории игр и исследования операций, линейного и нелинейного программирования и примыкают к теории поддержки принятия решений. Сюда же относятся схемы оптимизации управления и контроля. Методы безусловной оптимизации исходят из классических схем нахождения экстремумов функций и решений уравнений, включая интегральные и дифференциальные, а также уравнения в частных производных. Многие трудности решения оптимизационных задач сводятся к корректному определению всех локальных и глобальных экстремумов целевых функций в области допустимых значений. Трудности представляют сложные типы топологического рельефа функций. Разрешению этих трудностей посвящены спеии&чьные теоретические и экспериментальные исследования. Как правило, в рамках существующих подходов не ставится задача автоматической локализации всех экстремумов функции в области допустимых значений, принята точка зрения, что не существует универсального алгоритма численного решения задач безусловной оптимизации. При решении сложных задач обычно пользуются несколькими методами, чтобы увеличить долю удачных решений. Сложности компьютерной реализации многих численных схем связаны с тем, что они основаны на поведении производных, представленных конечно-разностными приближениями. Поэтому актуальна разработка такого программного метода локализации экстремумов функций, который бы осуществлял автоматическую идентификацию области каждого экстремума и отличался существенным ограничением роста погрешности при его вычислении. В качестве основы метода целесообразно рассмотреть алгоритмы сортировки, поскольку они включают лишь операции сравнения и сами по себе не накапливают погрешность.

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

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

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

распараллеливаемой адресной сортировки (используются параллельные сортировки

подсчетом и слиянием).

Для достижения поставленной цели ставятся следующие задачи:

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

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

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

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

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

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

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

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

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

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

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

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

Конкретно, научная новизна характеризуется следующим образом:

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

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

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

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

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

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

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

Основные положения, выносимые на защиту:

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

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

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

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

Связь с плановыми исследованиями, проводимыми по месту выполнения диссертационной работы. Диссертационная работа выполнялась в рамках госбюджетной НИР

«Математические методы устойчивой параллельной обработки, поиска и

распознавания» (№ гос. регистрации 01.2.00 106436, коя ГРНТИ 28.23.15), проводимой на кафедре информатики ГОУВПО ТГПИ в рамках приоритетного направления развития науки и техники в РФ «Информационные и телекоммуникационные системы» в соответствии с перечнем критических технологий РФ «Технологии обработки, хранения, передачи и защиты информации» по направлению фундаментальных исследований «Информатика. Искусственный интеллект, системы распознавания образов, принятие решений при многих критериях».

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

Внедрение и использование результатов работы. Полученные в работе результаты использованы

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

2. В госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания» (№ гос. регистрации 01.2.00 106436, код ГРНТИ 28.23.15), проводимой на кафедре информатики ГОУВПО ТГПИ.

3. В учебном процессе кафедры информатики Таганрогского государственного педагогического института в рамках курсов «Информатика», «Информационные технологии в математике», «Численные методы», «Элементы абстрактной и компьютерной алгебры».

Апробация работы. Основные результаты работы докладывались на: X, XI международных конференциях «Математические модели физических процессов» (Таганрог, ТГПИ, 2004, 2005 гг.); V международной научно-практической конференции по программированию УкрПРОГ' 2006 (Украина, Киев, 2006 г.); VIII международной научно-практической конференции «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права» (Москва, МГАПИ, 2005 гг.); IV-й международной научно-практической конференции «Проблемы регионального управления, экономики, права и инновационных процессов в образовании» (Таганрог, ТИУиЭ, 2005 г.); на ряде других конференций и семинаров.

Публикации. По материалам диссертационной работы опубликовано 13 печатных работ с общим объёмом 14,3 печатных листов.

Структура и обьём работы. Диссертация состоит из введения, 3 глав, списка литературы и 5 приложений. Основное содержание работы изложено на 153 страницах, включая список литературы из 120 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

дискретизации функции на входе схемы. Используются сортировки слиянием и

подсчетом. Для краткости ниже с помощью матрицы сравнений (МС) (рис. 1) представлена вторая из них. Массив С, состоящий из Л' элементов, располагается горизонтально сверху и вертикально слева от МС. На пересечении i -й строки и j -го столбца находится результат сравнения элементов c[i] и c[j\, отмечаемый знаком « + », если c[i] < c[j], знаком « - », если

Число нулей и плюсов в j -м столбце над диагональю, включая диагональный элемент, складывается с числом минусов j -й строки справа от диагонали. Сумма накапливается в счетчик по к , значение к становится индексом элемента в отсортированном массиве: cl[/fc]:=c[y], с тем же индексом запоминается входной номер переставленного элемента: е[А:]:= j.

Данная модификация сортировки обладает максимальным параллелизмом ввиду возможности одновременно всех сравнений, достигая временной сложности 0(1). Здесь эта сортировка дана для наглядности, на практике используется сортировка слиянием с временной оценкой О (Mog 2 N). Для действительной функции одной действительной переменной

y = f(x) (1)

вводится текущий промежуток [ ], внутри которого строится равномерная сетка с

<т хт-хт

постоянным шагом по направлению оси ОХ: Х( = л1' + (h, I = 0,1 ,...,N , N --. На сетке

И

считываготся значения функции и принимаются за элементы сортируемого массива:

«М = /(*,-!>> ' = 1,2,...,*. (2)

Элементы (2) поступают на вход сортировки и сортируются. К выходу сортировки подсоединяется условный оператор, осуществляющий локализацию каждого минимума в окрестности произвольно заданного радиуса ео среди элементов (2), при условии, что радиус меньше половины расстояния между любыми двумя соседними минимумами. Такой оператор имеет вид :| e[k-I]-e[k]\<=eo/h, / = 1,2....Д-1. Его программная реализация:

k:=l; while k<=N do begin for L:=l to k-1 do if abs(e[k-L]-e[kJ) <= epsO/h then goto 22; xk:=xO+e[k]*h;

22: k:=k+l end;

Здесь N - число узлов, совпадающее с числом сортируемых элементов, h - шаг равномерной сетки, sq - радиус во -окрестности текущего узла, хк - разностное выражение искомой точки локального минимума. Оператор локализует минимумы по построению: если в со -окрестности узла с номером е[к\ не идентифицирован ни один номер , это означает отсутствие в ней

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

|е[А + /]-е[А]|<=е/мО/й, 1= I, 2,...,n-k . (3)

Реализация (3) аналогична реализации оператора локализации минимума.

с[/] > с[у], и знаком « 0 », если c[i] = c[j]. Матрица сравнений

7.2 4 2 2 5

7.2 0 - - - -

4 0 - - +

2 0 0 +

2 0 +

5 0

Рис. 1

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

строится следующим образом. На входе схемы задаются постоянные параметры: eg, априори меньшее половины расстояния между искомыми минимумами, шаг h =е0 / с, с = const, 20 <с (граница выбора с определена на основе эксперимента), число сортируемых элементов N (равное числу узлов сетки). Первоначально эти узлы определяются на текущем промежутке [ .t(,V) ] постоянной длины Nyh. Описание работы схемы на промежутке дано непосредственно выше. В результате достигается полная идентификация на этом промежутке всех локальных минимумов при заданной окрестности локализации. Затем производится смещение текущего промежутка на его длину до тех пор, пока не будет пройден весь априори заданный промежуток поиска минимумов. Локальные максимумы аналогично идентифицируются на основе (3). Во избежание ложных экстремумов (они могут появляться на концах текущего промежутка) из схемы исключаются обе границы текущего промежутка. При достижении точек границ полностью воспроизводится процесс сортировки и локализации экстремумов по ранее описанной схеме для элементов массива, образуемых значениями функции (1) слева от правой границы и справа от левой границы. Это влечет инвариантность схемы относительно размеров промежутка поиска экстремумов. Если расстояние между ближайшими экстремумами неизвестно, то ер надлежит априори выбрать с достаточным запасом малости. Описанная схема ниже трактуется как общая схема идентификации экстремумов числовой последовательности с использованием сортировки. Схема переносится на случай действительной функции двух действительных переменных

z = f(x,y). (4)

На промежутках [ х(0\ х^ ] и [ v(0), ] строится равномерная прямоугольная сетка по

направлениям осей ОХиОК: xe = x(0) + (h, £ = 0,1 ,..„JV , N= )~х<'\ хт = х(0) + Nh;

п

yt +th, ( = 0,1 ,...,M, M = —-——, = + Mk . Дм нахождения минимумов

h

функции (4) выполняется проход в направлении оси OY вдоль столбцов сетки, во время которого находится минимальное по строкам значение ф] = min /(х,,уЛ при фиксировании номера

i=const IS j<M

столбца, этот минимум заносится на вход процедуры сортировки как элемент с(/) одномерного массива. К выходу процедуры подсоединяется оператор локализации, который для текущего узла, определяемого индексом, записанным в el[i], находит каждый узел xO+el[i]*/i, в проекции ео-окрестности которого на ось ОХ нет узлов, доставляющих значения элементов входной последовательности, предшествующие с{е\[к]] в отсортированном массиве. Значение локализованной абсциссы точки минимума xk =x0+e\[k]*h дает привязку к локализуемой точке двумерного минимума. Индекс абсциссы фиксируется и аналогично локализуется ордината ук := y0 + e2[kl]*h, в которой достигается приближение к минимуму /(х,у). Остается выполнить спуск к наименьшему значению в со -окрестности локализованной точки. Он осуществляется выбором наименьшего значения в сужаемой окрестности с фиксированным числом элементов сетки, причем по обеим переменным, пока не достигается требуемая точность. Для локализации максимума используется оператор (3). Во всей области поиска экстремумов функции (4) производится смещение промежутков [ х<0К ] и [ у<0\ у1А,) ] до тех пор, пока не будет пройдена вся априори заданная область. При этом отсекаются все концы на текущих промежутках, дополнительная проверка границ на экстремум осуществляется при помощи сортировки и локализации экстремумов по схеме, описанной для элементов одномерного массива. Данная схема переносится на случай функции произвольного числа переменных

С =Д*Ь*2 .•■'•.*»)• (5)

Первоначально рассматривается одна переменная л, и для текущего ее значения на равномерной сетке находится минимум (максимум) функции (5), который берется по л-1 другим переменным. Все такие минимумы (максимумы) поступают на вход сортировки в виде одномерной последовательности, после чего оператор локализации идентифицирует среди ее элементов все локальные минимумы (максимумы) в ео -окрестности при априори заданном со • Каждая локализованная координата фиксируется, являясь привязкой к искомому локальному минимуму (максимуму) п -мерной функции. Затем при каждой зафиксированной локализованной координате для оставшихся л-1 других координат возобновляется процесс, полностью идентичный только что описанному для п первоначальных координат. Конкретно, минимумы (максимум) по л-2 переменным при фиксированной локализованной координате, взятые при каждом текущем значении новой переменной на равномерной сетке, образуют новую одномерную последовательность. Эта последовательность, в свою очередь, поступает на вход сортировки и с помощью оператора локализации идентифицируются все значения второй координаты искомых минимумов (максимумов). Далее, при фиксировании локализованных координат процесс возобновляется для оставшихся л-3 координат и так, пока в заданном порядке не будут перебраны все независимые переменные функции (5). Схема устойчиво идентифицирует экстремумы функции (5) с точностью до дискретизации входных значений. Нули идентифицируются как минимумы модулей функций. В частности, для локализации и вычисления всех нулей функции (1) достаточно на вход сортировки подать с[/] = | /(*,_!) |, / = 1,2,...,л, нули функций многих переменных локализуются как минимумы модуля Т*') = |/(*1.*2>™>д:п)| по приведенной схеме. Нули алгебраических функций идентифицируются

на основании принципа максимума, нули трансцендентных функций дополнительно идентифицируются по значению. Изложенная схема отличается от известных по построению на основе сортировки и фактическим отсутствием ограничений на вид целевой функции. Автоматичность (стандартность) программной идентификации нулей и экстремумов достигается за счет упорядочения на основе сортировки и взаимно однозначного соответствия индексов сортируемых элементов, что отличает схему от перебора. В главе проводится сравнение схемы с известными методами. В частности, в табл.1 представлен пример сравнения поиска всех минимумов модуля трансцендентной функции/(*) = 5т(емп'/>'_с<к(/'' -г*), где Р = хР2 *при ^=(х-1)(*-2.99)(х-3)(х-4)(х-5)(х-6.001)(х-6.002)(х-7), Р2 = (х-8.23)(х-9)(х-10.976)(х-11)(х-12)(х-13)(х-14)(х-15), Я3 = (х-16)(х-17)(х-18)(х-19)(20.098)(х-21)(х-22.12345)(х-23) ,х<=[0,5],

Таблица 1

Поиск всех минимумов модулей функции /(х) = -сх), хе[о,5].

Метод Точность приближения Абсциссы точек Минимумов Значения минимумов

Общего поиска - - -

Пакет Maple - - -

Схема на основе сортировки ю-5 -2.7105Е-0020 1.Q002E+0000 2.85506Е+0001 2.95506Е+0001 0 3.7675Е-0005 5.8840Е-0004 3.7675Е-0004

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

Аналогично идентифицируются все

.Л/1 _t. Г..« *

f(x,y,z) = (1 + sin2 x)(I + sin'2 >0(1 + sin¿ г), д: € [-4, 0], у е [-4, 0], 2 е[-4,0]. Поиск всех локальных минимумов фикции трех переменных в кубе

минимумы функции трех переменных

Таблица 2

Метод Точность Приближения Координаты точек минимумов Значения Минимумов

Л' Y г

Mathcad - - - - -

Maple - - - - -

Схема на ю-2 -0.002 -3.14 -0.002 1.0000189

основе -0.002 -3.14 -3.14 1.0000210

сортировки -3.14 -0.002 -3.14 1.0000179

-3.14 -3.14 -3.14 1.0000389

В главе дана оценка параллельного выполнения схемы на основе параллелизма сортировки и взаимной независимости рассматриваемого алгоритма по всем фрагментам в произвольно выбранном прямоугольном разбиении области. Временная сложность параллельной схемы оценивается на модели неветвящейся параллельной программы при использовании параллельной сортировки слиянием Т(Я)-о(1оё2^ х 1°ё2(е0/е) ) » число процессоров

Я = О ^ 5/Я т- число узлов сетки при спуске, со ~ радиус окрестности локализации,

е - априори заданная граница абсолютной погрешности, 5 - площадь прямоугольной области поиска, Н - длина текущего промежутка. Для сортировки подсчетом Г(Л)=0( 1о§2(ео'е) ) •

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

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

%-*°Ах,у\у(хо) = уо, (7)

ах

предполагаются выполненными все условия существования и единственности решения, а также все условия сходимости к решению всех рассматриваемых ниже разностных схем. С целью идентификации всех экстремумов разностного решения задачи (7) на промежутке (*о> и ] задается равномерная сетка, на которой строится решение, например, по методу Эйлера:

*>=*о+ '"*.< = и..-,* А = (8)

п

Индексированные значения (8) принимаются за входные элементы одномерного массива

сМ = ><*,•-0, ¿ = 1,2,...',«. (9)

Элементы (9) сортируются. Аналогично случаю (2), присоединение к сортировке оператора локализации минимумов (максимумов) влечет устойчивую локализацию (для разностного решения это означает окончательную идентификацию) всех локальных экстремумов разностного решения задачи (7) в произвольной ео -окрестности. Ограничение заключается в том, что ео должно быть априори выбранным не больше половины расстояния между ближайшими соседними минимумами (максимумами). Если расстояние измеряется числом узлов сетки между соответственными экстремумами, то ео/Л должно быть не больше половины числа промежуточных узлов между ближайшими экстремумами (одного вида). Существенна специфика текущего промежутка [х0 ,хп]. Промежуток разбивается узлами равномерной сетки на п шагов

длины /г, где Л выбирается из условий априори заданной границы абсолютной

погрешности решения, п априори задается как приемлемая для языка программирования граница стационарного массива (9). На текущем промежутке [х0,х„] производится полная

идентификация экстремумов разностного решения (8), если таковые входят в этот промежуток. Чтобы выполнить идентификацию экстремумов на произвольно заданном промежутке [Ход ,Х„„], выполняется перемещение по нему с шагом, равным длине промежутка [хо,,х„]. На

каждом шаге перемещения полностью повторяются операции, описанные для промежутка [,г0Для проверки границ на экстремум на каждом таком шаге отсекаются все концы

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

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

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

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

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

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

л.

Уг>—Уя

системы

ОДУ:

У2Щ2 +•••+ №(')Г

общем случае может быть использована любая каноническая норма вектора. После этого применяется схема идентификации экстремумов одномерного массива tf[i] ,1 = 1,2,..., и. Осуществима идентификация нулей: достаточно на вход сортировки подать абсолютные величины значений разностного решения на равномерной сетке и искать минимумы описанным способом. В случае одного уравнения о[/] = |>- (x,_i)|, в случае системы ОДУ из N уравнений

о1[0 = |л(*/-1)|. а2Ш = \У2 C*/-i)|> —> вЛ'М = |.улг(*/-1)|> 1 = 1,2,...,и. Далее без изменения

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

Изложенная схема с видоизменением распространяется на разностные решения уравнений в частных производных. Для этого формируется многомерный массив разностных значений приближенного решения, который интерпретируется как дискретная функция нескольких переменных х, у,..., t. Полученные приближения, определенные во всех узлах равномерной прямоугольной сетки, рассматриваются как дискретное представление функции iff = /(xi ,х2 ,...,*„) из (5). Для этой функции повторяются все шаги идентификации экстремумов и

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

i^L = -yl-o.\*y2,yi(0)=0.\,y2(0)=\ . На промежутке [о,5о] требуется найти все dt dt

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

Таблица 3

Метод Шаг Точки экстремумов Экстремумы решения yl точки экстремум ов Экстремумы решения y2

идентификация на основе сортировки ю-5 3.14505 6.29057 9.43467 Minyi=-o.oe5 maxyl=0.07301 minyl=-0.0623 1.52220 4.66773 7.81325 miny2=-0.0926 maxy2=0.07918 rainy2=-0.0676

40.85852 44.00090 47.14329 minyl=-0.0129 maxyl=0.01106 minyl=-0.0094 42.3796 45.5220 48.6644 maxy2-0.01199 miny2=-0.0102 maxy2=0.00876

Аналогично идентифицируются

нули разностного решения системы:

Таблица 4

Метод Шаг Точки Значения Точки Значения

Нулей компоненты нулей компоненты

решения yl решения у2

идентификация 1.62237 Miny1=0.00000 3.14505 Miny2=0.00000

на основе 4.76-789 miny1=0.00000 6.29057 miny2=0.00000

сортировки ю-5 7.91342 minyl=0.00000 9.43467 miny2=0.00000

42.47975 minyl=0.00000 40.85852 miny2=0.00000

45.62213 miny1=0.00000 44.00090 miny2=0.00000

48.76451 minyl=0.00000 47.14329 miny2=0.00000

Результаты работы пакетов Mathcad и Maple формируются путем перевода системы в уравнение высшего порядка и графическим отображением решения без числовой идентификации самих экстремумов. Графическое отображение решения уравнения высшего порядка корректно лишь для несложных решений уравнений малой степени, усложнение графика влечет потерю точности идентификации нулей и экстремумов. График исключает идентификацию экстремумов и нулей нормы решений системы ОДУ, кроме того, чтобы решение ОДУ отобразилось на графике в виде кривой в плоскости Oty, диапазон изменения переменной и масштаб координатных осей подбираются вручную. Графическое представление экстремумов недоступно для динамического программного использования их значений.

В третьей главе предлагается подход к применению схем многомерной оптимизации глав 1, 2 для идентификации экстремальных отклонений разностных решений системы ОДУ от невозмущенного решения при вариации параметрических коэффициентов системы. Рассматриваются математические модели поведения динамических систем вида

^- = F(Y,l,a), (11)

dt

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

ах ах

-Т-=/з ("I.й2.>Л.Л'ГЗ).

их

У1(Х0)=УЮ<У2(Х0)=У20 У}(*о)=УЗ О •

Для оценки отклонения от невозмущенного решения ищется максимальное и минимальное отклонение от нуля нормы разности между возмущенным и невозмущенным решениями системы (12) при вариации а^а^а^. Помимо конкретной оценки отклонения

ставится цель исследовать устойчивость решения в условиях данной вариации. Норма разности решений системы (12) при возмущенных и невозмущенных начальных данных формируется для взятых с постоянным шагом (варьируемых) значений коэффициентов «1,02 >яз и независимой переменной х. Диапазоны вариации и шаг дискретизации выбираются из условий задачи. С заданными шагами по четырем данным значениям переменных считываются значения, например, эвклидовой нормы разности возмущенного и невозмущенного решений

-Я| +\>'2-У2\ +\уз _Уз| • (13)

Дискретизированная функция (13) представляется в виде четырехмерного массива, далее задача решается по описанной ранее схеме оптимизации для функции четырех переменных. Например,

- - ¿У] <Л>2 <Ь>ъ

для линеинои системы —- = = у3 = -а0 у] -а\ у'1 -а2 уз вариация «1,^2,03

Л Л с/1

происходит в области -1 < ац < 1, 1 < щ < 5, 9 <а2 £10, соответственно, с шагами /¡о = 0.7 , Л) = 0.8, И2 = 0.9 ; промежуток изменения независимой переменной 0 < / й 15 , шаг выборки Л = 2 является шагом вариации, не совпадающим с шагом разностной схемы, которая обеспечит априори заданную точность разностного решения при каждом наборе значений в[,о2,Дз. Для оценки максимального отклонения системы от точки покоя взамен (13) целесообразно идентифицировать <+1

максимум нормы матрицы ]~[(Я+ЛЛ(»;)) , где А - матрица коэффициентов данной линейной 1-0

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

Значения варьируемых параметров Значение максимума

а0=-1.0000 а1=1.0000 а2=9.0000 t=14 тах= 1.098827328579Е+0002

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

/+1

устойчивости системы на основе пошагового вывода нормы матрицы £ЧЛЛ(/{)) . Способ

?=о

оценки устойчивости соответствует (Кибернетика и системный анализ, 2004, № 4, 2006, № 1) необходимым и достаточным условиям устойчивости линейной системы

со | (О I

|~|(£ + М(г£)) ¿с = сощ»<со, дополнительное к данному условие Нш + =0

г=о I * ~*00 К

необходимо и достаточно для асимптотической устойчивости. Для вариации коэффициентов а0, оь (¡2 в области 2 < сто < 3, 11 < «[ < 12 , 9 <о2 <11, соответственно, с шагом = 0.7 , Ь ¡= 0.8,

Л2 =0.9, в промежутке изменения независимой переменной 0</ < 15 с шагом й = 2 значение

коэффициентов ад, 0[, 02 и значение независимой переменной /, доставляющих

максимальное отклонение нормы матрицы от нуля примет вид

Значения варьируемых параметров Значение максимума

а0=2.0000 а1=11.0000 а2=10.80000^=2 Мах- 1.6607664311Б+0000

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

Таблица 5

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

Экстремальные значения параметров

а0 = -1, а, = 1, а2 ~ 9 О0 = 2, о, =11, «2=10.8

Оценка устойчивости по норме матрицы 1*1 JJW) 1-0 Оценка устойчивости по знаку корней характеристического многочлена /> = Я3 + а2Я2 + Я + а0 Оценка устойчивости по норме матрицы 1 = 0 Оценка устойчивости по знаку корней характеристического многочлена Р = Л3+а2А2+а,Л + а0

norma- 2.867Е+0012 norma- Э.642Е+0024 -7.51Е+0000 -1.56Е+0000 8.49Е-0002 norma- 2.103Е-0010 norma- 1.342Е-0020 norma- 1.078E-0234 norma- 6.883E-0245 -9.68Е+0000 -8.79Е-0001 -2.34Е-0001

norma- 4.513E+04 84 norma- 5.783E+0496

norma= 1.217E+0633 norma- 1.560E+0645 norma- 9.П5Е-0500 norma- 5.856E-0S10

Система не устойчива Система не устойчива Система устойчива Система устойчива

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

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

п п п

/(*)= ХСЛ + -шихтах), (14)

при системе ограничений

п

£Ь" ' = |>т- х] 2 У = (15)

М

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

(14) может достигаться либо на границе, либо внутри области. Идентификация экстремумов выполняется сначала внутри, затем на границе области. Вначале идентифицируются все точки х*, в которых достигаются локальные экстремумы функции (14), на выходе осуществляется проверка принадлежности полученного решения допустимой области (15), - при невыполнении для локализованного ** хоть одного из условий, экстремум /(**) отбрасывается. Для

п

нахождения экстремумов на границе области из каждого равенства системы =6,, 1 = 1 ,т,

М

X] == 0, j = \,n выражается одна неизвестная хк и подставляется в функцию (14), образуется

л-1 и-1л-1

новая функция от п-1 переменных, которая обозначается /(*)= + £ Я/**./'** • вход

/=1 у=М=!

рассматриваемой схемы подаются значения функции /(х), считываемые с постоянным шагом А . Как и для задачи безусловной оптимизации, задается интервал изменен™ независимых

переменных %,<*!<?<,[, х0Х<х2^х02..... *о<л-2)^*л-1 ^*о(„-1), где ?00>*0Ь-*0(л-2И0(п-1) -

координаты точек вершин многогранника допустимой области. Схема идентифицирует все точки х**, в которых достигаются экстремумы функции /(х), перед выводом результата проверяется принадлежность полученного решения области (15). При невыполнении для х** хотя бы одного из условий оптимум Д.* *) отбрасывается. Например, функция : = -х\х2 + 2лг| + Здг] + 2х^ +1 при ограничениях дг, + х2 + 5 2 О, < О, х2 < О вначале исследуется на экстремум внутри области, образованной осями координат Охх, Ох2 и прямой х2 =-5-^ . Значения функции г поступают на вход схемы оптимизации функции двух действительных переменных, где х2 изменяются с постоянным шагом Н в прямоугольнике х1 е [-5,0], х2е [-5, 0], включающем все значения допустимой области. Программа, представленная в приложении, идентифицирует точку минимального значения г, на выходе программы проверяется выполнение ограничений. Результат работы программы (внутри области допустимых значений):

Значение переменной Значение Проверка условий

минимума х1+х2+5>=0;х1<=0;х2<=0

Х1=-2 .00 Мп.п=-3.00 Х1+х2+5=2.00

Х2= -1.00

Далее функция г исследуется на экстремум на границе области. Первое ограничение преобразуется к виду ^+^2+5 = 0, откуда выражается х2 и подставляется в функцию г, при

этом образуется новая функция г = +26х[ +41. На вход схемы подаются значения функции I, считываемые с постоянным шагом А на промежутке х1 е [-5, 0]. Идентифицируются точки интервала, в которых достигается максимум г, осуществляется проверка принадлежности полученного решения допустимой области. Результат работы программы (на границе области допустимых значений):

Значение переменной Значение максимума Проверка условий

х 1 +х2+5>=0;х 1 <=0;х2<=0 Х1--4.99; х2= -0.01 Мах=10.9б Х1+х2+5=0.00

х1=0.00; х2= -5.00 Мах=41.00 Х1+х2+5=0.00

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

наибольшие и наименьшие значения

целевых функций. Ограничение

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

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

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

-1.19759005794147 961Е-0001 -7.509869252169Е-0001 7.1716316206Е-0011 -1.19759005794147961Е-0001 7 .5098692521693Е-0001 5.8660744662Е-0011 При (д <0,5 с все действительные части корней находятся в левой полуплоскости, система управления устойчива. Расчеты соответствуют результатам, полученным по диаграмме Боде. Приводится схема идентификации нулей функций на основе сортировки, позволяющая найти распределение корней характеристического многочлена передаточной функции на всей комплексной плоскости. Прилагаются акты о внедрении результатов диссертационной работы.

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

Работа включает следующие научные результаты.

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

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

3. Схема оптимизации на основе сортировки применяется для идентификации экстремумов норм решений систем ОДУ и проводится программная оценка возмущения решения системы ОДУ при вариации параметров.

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ РАБОТЫ 1. РоммЯ.Е., Заика И.В. Метод нахождения экстремумов решений дифференциальных уравнений на основе адресной сортировки. / ТГПИ. - Таганрог, 2003. - 29 с. Деп. в ВИНИТИ 12. 05. 2003, № 908-В2003. (лично автора - 0,75 п.л.)

или 53 + 2$2 + 5+е = 0. По схеме на основе сортировки получится:

мнимая часть корней

1.1754943508Е-0038

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

2. Ромм Я.Е., Катрич С.А, Буланов С.Г, Заика И.В. Моделирование критериев устойчивости и определение экстремальных значений решений дифференциальных уравнений на основе разностных схем при помощи сортировки. // В кн. Математические модели физических процессов: Материалы Х-й Международной научной конференции. - Таганрог, 2004. — С. 156 — 163. (лично автора-0,125 пл.).

3. Ромм Я.Е., Заика И.В. Схема поиска экстремумов и нулей решения системы дифференциальных уравнений на основе сортировки. / ТГТТИ. - Таганрог, 2004. - 49 с. Деп. в ВИНИТИ 28.05. 2004, № 897-В2004. (лично автора - 1,3 п.л.)

4. Ромм Я.Е., Заика И.В. Схема поиска экстремумов и нулей функций на основе адресной сортировки. / ТГПИ. - Таганрог, 2005. - 50 с. Деп. в ВИНИТИ 01. 03. 2005, № 289-В2005. (лично автора - 1,35 пл.)

5. Ромм Я.Е., Заика И.В. Схема программной локализации и вычисления экстремумов и нулей функций на основе сортировки. // В кн.: VI научно-практическая конференция преподавателей, студентов, аспирантов и молодых ученых. - Таганрог, 2005. -С. 234 -239. (лично автора - 0,23 пл.)

6. Заика И.В. Локализация экстремумов функций на основе сортировки. // В кн.: III Межрегиональная научно-практическая конференция студентов, аспирантов и молодых ученых «Молодежь XXI века - будущее Российской науки». - Ростов-на-Дону, 2005. - С. 27-29.

7. Заика И.В. Схема локализации экстремумов функций и разностных приближений решений дифференциальных уравнений на основе сортиров. // В кн.: Математические модели физических процессов: Материалы XI-й Международной научной конференции. - Таганрог, 2005. -С. 229-232.

8. Ромм Я.Е., Заика И.В., Соловьева И.А. Метод программной оптимизации в приложении к математическим моделям экономики. // В кн.: «Проблемы регионального управления, экономики, права и инновационных процессов в образовании». Т.2. - Таганрог. -2005. - С. 17 - 26. (лично автора - 0,27 п.л.)

9. Ромм Я.Е., Заика И.В., Соловьева И.А. Локализация нулей и экстремумов функций на основе сортировки в приложении к распознаванию изображений. // В кн.: Модернизация отечественного педагогического образования: проблемы, подходы, решения. Ч .II. «Технологические основы образовательного процесса в современной высшей школе». — Таганрог, 2005. - С. 38-49. (лично автора - 0,3 п.л.)

10. Ромм Я.Е., Заика И.В., Соловьева И.А. Схема локализации экстремумов функций на основе сортировки в приложении к распознаванию изображений. // В кн.: Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права: Научные труды VII Международной научно- практической конференции. - Москва, 2005. - С. 173 - 178. (лично автора-0,19 пл.)

11. Ромм Я.Е., Заика И.В. Программная локализация экстремумов функций и разностных приближений решений дифференциальных уравнений // Изв. вузов. Сев.-Кавк. регион. Техн. науки. - 2005. - спец.выпуск"Математическое моделирование и компьютерные технологии". -С. 55 - 61. (лично автора - 0,5 пл.)

12. Ромм Я. Е., Заика И.В., Тюшнякова И.А. Идентификация экстремумов функций на основе сортировки с приложением к вычислительным схемам алгебры, анализа и распознаванию изображений. // В кн.: Проблеми програмування: Матер]алы 5-й м1жнародно1 науково-практично1 конференцп з програмування УкрПРОГ'2006. 23-25 травня 2006 р. Украша, Кшв.-2006. № 2-3. -С. 708 - 717. (лично автора - 0,3 п.л.)

13. РоммЯ.Е., Заика И.В., Лабинцева A.A. Идентификация нулей и экстремумов разностных решений обыкновенных дифференциальных уравнений и уравнений в частных производных на основе сортировки / ТГПИ. - Таганрог, 2006. - 32 с. Деп. в ВИНИТИ 07.03.2006, № 230 -В 2006. (лично автора - 0,56 п.л.)

Соискатель

Заика И.В.

Подписано к печати Объем 1,0 уч.-изд.л.

Заказ Тираж 100 экз.

Издательство Таганрогского государственного радиотехнического университета ГСП 17А, Таганрог, 28, Некрасовский, 44 Типография Таганрогского государственного радиотехнического университета ГСП 17А, Таганрог, 28, Энгельса, 1

Введение

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

1.1. Параллельные алгоритмы сортировки слиянием и модифицированной сортировки подсчетом

1.1.1. Последовательное слияние по матрицам сравнений

1.1.2. Числовые параметры сортировки слиянием

1.1.3. Сортировка слиянием массива с произвольным числом элементов.

1.1.4. Модифицированная сортировка подсчетом

1.2. Алгоритм автоматической идентификации экстремальных значений одномерной последовательности на основе сортировки

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

1.4. Инвариантность схемы относительно вида функции и размеров промежутка поиска экстремумов

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

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

1.7. Автоматическая идентификация на основе сортировки нулей функций одной и многих переменных

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

1.9. Сравнение схемы идентификации экстремумов на основе сортировки с известными методами безусловной оптимизации

1.10. Выводы

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

2.1. Идентификация на основе сортировки экстремумов разностного решения обыкновенного дифференциального уравнения (ОДУ) первого порядка

2.1.1. Идентификация истинных и исключение ложных экстремумов на границах текущего промежутка при помощи сортировки.

2.2. Идентификация на основе сортировки экстремумов разностного решения системы дифференциальных уравнений второго порядка

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

2.4. Случаи систем ОДУ из трех и более уравнений с приложением к идентификации экстремумов нормы разностных решений

2.5. Автоматическая идентификация на основе сортировки нулей разностных решений дифференциальных уравнений

2.6. Алгоритм автоматической идентификации экстремальных значений и нулей разностных решений уравнений в частных производных

2.7. О сравнении с известными методами поиска на основе сортировки экстремумов и нулей решений дифференциальных уравнений

2.8. Выводы

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

3.1. Применение алгоритма многомерной оптимизации на основе сортировки к поиску экстремумов разностных решений систем линейных ОДУ при вариации параметров

3.1.1. Многомерная оптимизация на основе сортировки дискретно представленной функции четырех переменных.

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

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

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

Статическая задача вида / (*) -> min, хеХ, называется задачей условной оптимизации, если Х- собственное подмножество пространства R" (X с R", X ф R"). Задача условной оптимизации записывается в виде f(x) -> min, g (x) = 0, i = \,m, и решается методом множителей Лагранжа. Основная идея метода заключается в переходе от задачи на условный экстремум исходной функции к задаче на безусловный экстремум специально построенной функции Лага гранжа Цх, Л) = /(*) +где хеЛп, Л = (Л1,Л2,.,Лп)еЛт. Обычно оптиы мальные решения находят, проверяя "потенциальные" решения х*, Л*, удовлетворяющие необходимым условиям существования решения ^(х',Х) = 0, ¿'л(х',Л') = О (условиям первого порядка).

Классические решения динамических задач основывались на вариационном исчислении. К этим задачам относятся: изопериметрическая, задача Лагранжа, задача Майера, задача Больца. Например, для изопериметрической задачи среди всех кусочно-гладких вектор-функций у- {у,(*),.у2(*),.».Ул(*)}, принимающих заданные значения на концах интервала [х„х2], находят ту, которая доставляет экстрех, хг мум функционалу ^(у)= ¡/0(х,у,у')ск при связях Jl(y)= ¡/,(х,у,у')ск =

X, X, = 1,2 ,.,*).

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

Задача линейного программирования формулируется следующим образом. Среди неизвестных хх,хг,.хп, удовлетворяющих системе вида аихх+апх2+.+а^пхп>Ь, , апх,+апх2+.+а2пхп>Ь2,

1) ат^х+атгх2+.+атпхп>Ьт , х, >0, х2> 0,.> 0, требуется найти такие, при которых линейная функция = + с2х2 +. + с„х„, (2) достигает своего наименьшего (наибольшего) значения. Функцию (2) называют целевой функцией или функцией цели, а систему неравенств (1), которым должны удовлетворять переменные целевой функции, называют системами ограничений. Предположим, что заданная система ограничений преобразована так, что какие -либо г ее неизвестных выражены через остальные

1 = «1 +«•+<*!„*„+А • .(3) хг=агыХг+]+. + атхп + Рг , д>О, /?2>0,.Д>0, Неизвестные х{,х2,.,хг называются базисными неизвестными, остальные -свободными. Совокупность неизвестных £ = {аг,,;с2, ,,хг} называют базисом. Подставляя в (2) вместо базисных неизвестных их выражения из (3), можно целевую функцию/представить через свободные неизвестные: / = /0 + /г+]хг+] +. + у„хп. Значения свободных неизвестных х1(1 = г + 1,г + 2,.,п) приравнивают к нулю. Тогда из (3) следует х, = рх,хг = /З2.хг = /.Зг. Получим одно из решений системы (3) (/?,, /?2,0,0,.,0) - это решение называют допустимым. Для этого решения, соответствующего базису Б, значение целевой функции / = /0- Основная идея метода решения задачи линейного программирования состоит в переходе от базиса Б к новому базису Б' так, чтобы новое значение /уменьшилось (или, по крайней мере, не увеличивалось). Таким путем в конечном итоге можно прийти к базису, дающему минимум функции/ либо выяснить, что задача не имеет решения.

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

Задача условной оптимизации в нелинейном случае записывается в виде /(*)-»пил, &(х)<0, 1 = 1?, Я"(хеГ).

В качестве примера подхода к решению задач нелинейного программирования можно рассмотреть метод штрафных функций. Исходная задача условной оптимизации преобразуется в последовательность задач безусловной оптимизации путем введения штрафных функций Р(х,Д) = /(х) + СЗ(Л,£(х))-»тт, хеЯ", где - расширенная функция, СЗ(Д,£(х)) - штрафная функция, Л-штрафной параметр. Задача условной минимизации /(х) заменяется последовательностью задач безусловной минимизации Р(х,Лм) при / = 1,2,.При этом из начальной точки х<0) находится последовательность точек лг(1),л:<2),., сходящаяся при определенных условиях к решению х' исходной задачи. Методы штрафных функций разделяются на методы внутренней точки и методы внешней точки. Метод штрафных функций называется методом внутренней точки (внешней точки), если все точки последовательности х{1}, / = 0,1, 2,., являются допустимыми (недопустимыми).

В качестве внутренней штрафной функции часто используются логарифмиг ческая штрафная функция 0(/?,, £(*)) =-Л, ]Г1п(-£,(л:)), а также обратная штраф1 1 ная £(*)) =-Я, I

В качестве внешней штрафной функции часто используются штрафная г функция типа квадрата "срезки" Q(R,, g(x)) = -R, ]Г (g, (x))2, где i , ЧЛ fg,(x), если g,(x)Z0, [О, если g,{x)< 0.

Помимо этого метода для решения задач нелинейного программирования используются методы аппроксимирующего программирования, включая методы линеаризации /94, 100, 101, 115/, и применимые к ним методы линейного программирования /33/, а также метод неопределенных множителей Лагранжа.

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

II. Один из основных подходов к решению экономических задач дает теория игр /64, 120/. На начальных этапах развития теории игр ее рассматривали как обобщение теории оптимизации на случай двух и более участников экономического процесса. Однако подлинное отличие от традиционной теории заключалось в том, что в теории игр учитывается взаимодействие участников экономического процесса и возможность конфликта между ними. Это отличие нашло выражение в целевой функции, которая определяет размер выигрыша в зависимости от выбранного решения: выигрыш одного участника экономического процесса зависит не только от того, какие альтернативы выберет он сам, но и от того, какие альтернативы выберут другие. Благодаря этому в экономических исследованиях игровой подход применялся преимущественно для изучения таких экономических проблем, как двусторонняя монополия или олигополия. Кроме того, теория простых игр позволила уточнить понятие равновесия в экономике. В играх двух участников с нулевой суммой равновесной стратегией любого участника экономического процесса является такая, которая дает данному участнику наибольший минимальный выигрыш при любой возможной стратегии другого игрока. Такое равновесие консервативно, поскольку участник экономического процесса должен выбирать не ту стратегию, которая приносит ему наибольший выигрыш при неразумном выборе стратегии соперником, а ту стратегию, которая в наибольшей степени предохраняет от потерь в игре с умудренным соперником.

Теория оснований экономики и основных механизмов социальных организаций глубоко связана с теорией «стратегических игр». Для обозначения основных понятий в качестве простейшего примера стратегической игры можно рассмотреть игру двух лиц с нулевой суммой. Пусть ср будет функцией многих переменных х,у.Выделяя одну из них, например, х, и фиксируя значения других переменных у,., можно рассматривать (р{х,у.) как функцию одной переменной х. Поскольку то же можно проделать и для любой другой переменной у,., необходимо указать, что операции max, min относятся именно к переменной х, например, тъ.\(р(х,у), X тпф(х,у). Пусть max max^(;c,j>) есть максимум (р{х,у.), если рассматривать л: у и у как единую переменную. Это означает, что для некоторых надлежащим образом выбранных х0 и у0 выполняется (р (x0,-y0) = max max^(;c,j>) и для всех х' и у' У должно быть (р (х0,уй)>(р(х\у'), аналогично, для функции (р{х,у) минимум есть min min (p{x,y). У

Пара дг0, y0 называется седловой точкой функции (р, если (р{х,у0) принимает максимальное значение при х = х0, а (р{х0,у) принимает минимальное значение при У = У0• Д151 функции <Р(х,у) справедливо max min(р (х ,.y) = min тахф(х,у) тогда и только тогда, когда существует седло

X у у X вая точка х0, у0 функции (р.

При рассмотрении игры Г двух лиц с нулевой суммой игра состоит из двух ходов: игрок 1 выбирает число г, = \,.,ßx, а игрок 2 выбирает г2 = \,.,ß2 (каждый выбор производится при полном незнании выбора другого игрока), после чего игроки 1 и 2 получают соответственно выигрыши Кх(тх,т2), К2(тх,т2).

Так как рассматривается игра с нулевой суммой, то Кх(тх,т2) + К 2(тх,т2) = 0. Это можно выразить следующим образом:

К,(т1,т2) = К (г,,г2), К2(тх,т2) = -К (г,,г2).

Чтобы понять, как очевидные желания игроков 1 и 2 определяют их выборы г, и г2, удобно использовать графическое представление. Для этого К{тх,т2) представляется в виде прямоугольной матрицы. При этом образуется прямоугольник из Д строк и ß2 столбцов, где числа тх =],., Д и г2 = 1,.,/?2 задают нумерацию первых и вторых столбцов, соответственно, в клетку с номерами г, и т2 записываются элемент матрицы К(тх ,т2).

1 2 . ß2

1 КО,2) Щт2) К{ l,ß2)

2 К( 2,1) К( 2,2) Ц2,т2) К{ 2,ß2)

К( xi,2) Kdl,ß2) l K(ßl,0 AT(PI,t2) *(ßl,T2) ATCPI,P2>

Следует отметить, что на функцию К(тх,т2) не накладывается никаких ограничений.

Оба игрока заинтересованы только в значениях элемента матрицы К (г,, т2). Игрок 1 старается максимизировать его, но он контролирует только строку, т. е. число г,. Игрок 2 старается минимизировать его, но он контролирует только столбец, т. е. число г2. Трудность при анализе игры Г заключается в том, что игрок 1, выбирая г,, не знает, с каким выбором г2 игрока 2 он столкнется, и наоборот. Поэтому ниже производится сравнение игры Г с другими играми, для которых эта трудность не возникает. В случае, когда ход первого игрока предшествует ходу второго игрока, значение партии такой игры можно /64/ охарактеризовать величиной v, = тахттЛГ(г,,г2). Аналогично, для игры, когда ход второго игрока пред

П 'г шествует ходу первого, v2 = min шах К{тх, т2). Если значение партии v для игры Г

2 Г1 вообще может быть определено, то оно должно лежать между значениями v, и v2, то есть v, < v < v2. Длина этого интервала, в котором может находиться v, есть А = v2 - v, > 0. Игра может быть такой, что неважно, какой игрок «раскрыл» своего оппонента, т. е. что получаемое преимущество при этом равно нулю. В соответствии со сказанным выше, это может быть в том и только в том случае, когда А = О или, что то же самое, когда v, = v2 /64/. Или, если заменить vx и v2. выражениями, которые их определяют, maxminA!'(r1,r2)=minmaxA!'(rI,r2). Если игра Г обладает этими свойствами, то ее называют вполне определенной. Действительно, Г вполне определена, тогда и только тогда, когда существует седловая точка функции £(г„г2)/64/.

III. Теория игр признана классической наукой, играет значительную роль в ряде прикладных областей, включая военное дело и экономику /1, 112-114/. В качестве основного подхода к задачам теории игр используются средства классического анализа и дифференциальные уравнения. В этом контексте рассматривается теория дифференциальных игр, которая исследует игры, где противники принимают целый ряд последовательных решений, которые так логически связаны друг с другом, что эта связь может послужить основой наглядной и численно анализируемой модели.

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

Общая постановка задачи этой теории и подходы к ее решению характеризуются непосредственно ниже. IV. Уравнение

Ху =//(х1,.,хп,и1,.,иг), 7 = 1,.,п, (4) или х = / (х,и,/), описывающие движение некоторого управляемого объекта, где время, х = (х,,.,хп)- величины, характеризующие движение объекта в зависимости от времени и называемые фазовыми координатами, и = (и1,.,ип)~ параметры управления. Для того чтобы фазовые координаты объекта (4) были определены в виде функций времени х = *(/) на некотором отрезке /„</</,, необходимо в начальный момент времени задать начальное условие х(/0) = х0 и параметры управления и = {и1,.,ип) как функции времени и = и(1) при /е[/0,/,]. Тогда фазовые координаты л: = х(/) будут определяться как решение следующей задачи Коши: х = /(х({),и( (5) х(/0) = х0. (6)

Непрерывная функция х = х(/), удовлетворяющая равенству I |/(х(г),м(г),г)^г + х0, /0 <1<ц, (7) о называется решением или траекторией задачи (5), (6), соответствующей начальному условию х0 и управлению и. Задача оптимального управления заключается в том, чтобы минимизировать или максимизировать функцию (7) на множестве допустимых решений.

Эффективным средством исследования задач оптимального управления является принцип максимума Понтрягина /104/, представляющий собой необходимое условие оптимальности в таких задачах: если выбрано допустимое управление м(/) и получена фазовая траектория *(/) с начальным условием х(/0) = х0, то система

-¿'У'г. (/ = 0, ,,.,„.) а/ а=о ах: имеет единственное решение у/ при любых начальных условиях для

С помощью полученных функций у/, строится функция л

К(1//,х,и)=^1//а /а(х,и). Для оптимальности управления &(/) и траектории *(/) а=0 необходимо существование такой ненулевой непрерывной вектор-функции (//(/)= {ц/0(/),.,^п(/)), соответствующей функциям и(/) и *(/), что при любом

0 </</,, функция £(^(/),;с(/),и(/)) переменного и е и достигает в точке и = и(/) л максимума. В конечный момент Г,, ///„(/,) <0, ^]^а(/1)/а(л'(/1),м(/1)) = 0. а=0

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

Помимо принципа максимума Понтрягина в области динамического программирования широко известен принцип оптимальности Беллмана. Описание принципа в содержательном смысле заключается в следующем /20,104 /.

Принцип оптимальности. Оптимальная политика (или стратегия, понимаемая как последовательность допустимых решений) обладает тем свойством, что, каковы бы ни были начальное состояние и начальное решение, последующие решения должны составлять оптимальную политику относительно состояния, являющегося результатом применения первого решения. Принципа максимума Понтрягина и принцип оптимальности Беллмана находят разнообразное применение при решении задач вариационного исчисления и задач условной оптимизации /68, 104/

V. Для решения задач оптимизации широко используется современные средства вычислительной техники. В процессе использования последовательных компьютеров был накоплен и отработан огромный фонд численных методов и программ. Однако оказалось, что современные персональные компьютеры не в состоянии решить за приемлемое время многие задачи, имеющие большой объем вычислений. Использование параллельных компьютеров позволяет минимизировать время реализации алгоритмов. При этом существенно, чтобы параллельная реализация алгоритма имела такие же вычислительные свойства, как и любая другая. В частности, если исходный алгоритм (последовательный) был численно устойчив, то он должен оставаться таким же и в параллельной форме. Как отмечается в /27/, на практике подавляющее большинство алгоритмов оказалось несостоятельным. Огромное число требуемых процессоров, сложные информационные связи между операциями, численная неустойчивость, конфликты в памяти препятствуют применению быстрых параллельных алгоритмов. Перечисленные трудности относятся к существующим задачам оптимизации. Поэтому необходима разработка машинного метода приближенных вычислений, позволяющего экономить время и усилия, затрачиваемые на решение оптимизационной задачи.

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

Сортировка /24/ практически присутствует во всех приложениях операционных систем при обработке больших объемов данных. С помощью сортировки решаются задачи "группировки", когда нужно собрать элементы по некоторому признаку. Сортировка используется при поиске с целью его ускорения, с помощью сортировки можно сделать выдачи ЭВМ более удобным для человеческого восприятия. В контексте сортировки рассматриваются многие аспекты программирования.

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

Временная сложность алгоритмов будет измеряться количеством последовательных шагов их выполнения. В частности, временная сложность сортировки измеряется числом последовательно выполняемых сравнений. Временная сложность параллельных алгоритмов будет оцениваться на модели неветвящихся параллельных программ /2, 19, 77, 93/ без учета обмена. Временная сложность параллельной сортировки будет обозначаться Г(/?) = к г, где т - время бинарного сравнения, к количество последовательных сравнений, 7? - число используемых процессорных элементов (при описании параллельных сортировок иногда их называют компараторами).

Сортировка вставками /53/. Элементы просматриваются по одному, каждый новый элемент вставляется в подходящее место среди ранее упорядоченных элементов (временная сложность -Т{ 1) = 0(Ы2), где 0(/) - класс функций, растущих не быстрее /). Сортировка Шелла, временная сложность которой Г(1) = 0(М15), представляет собой усовершенствование сортировки вставками. Эта сортировка представляет собой многопроходную сортировку, при которой список разбивается на подсписки, каждый из них сортируется отдельно, причем на каждом проходе число подсписков уменьшается, а их длина растет.

Обменная сортировка /53, 83, 84/. Предусматривает систематический обмен местами между элементами пар, в которых нарушается упорядоченность, до тех пор, пока таких пар не останется. Существуют несколько типов сортировки, для которых обмены являются основной характеристикой. Выделяют обменную сортировку с выбором ("метод пузырька"), поразрядную сортировку, обменную сортировку с разделением ("быстрая сортировка" Хоара), обменная сортировка со слиянием (параллельная сортировка Бэтчера).

Пузырьковая сортировка (Т(\) = 0(Ыг)) сравнивает элементы попарно, переставляя между собой элементы тех пар, порядок в которых нарушен.

Пример обменной сортировки (метод «пузырька»)

100 728 50 259 16

1-шаг 100 728 50 (КЗ) 259

2-шаг юо 728 (1б) 50 259

3-шаг 100 (1б) 728 50 259

4-шаг @ 100 728 50 259

Рис. 1.

Поразрядная сортировка (7\1) = 0{Ы)) /59/, выполняется при условии, что длина ключа невелика по сравнению с числом ключей. Список разбивается на стопки и при каждом проходе используется отдельная часть ключа.

Быстрая сортировка (сортировка Хоара, в наихудшем случае Т(\) = 0(М2), в среднем случае Г(1) = 1о§2 И)) представляет собой рекурсивный алгоритм, который выбирает в списке осевой элемент, а затем разбивает список на две части, состоящие из элементов соответственно меньших или больших выбранного.

Пример быстрой сортировки

Исходный список ¡Т] [Тз] [Т] [7] [Т] [Т] [Т]

Ось в ячейке 4 | 1 | | 4 |

Ось в ячейке! || 1 |) |Т] \Т] НП ПП ПП ПЛ

Ось в ячейке 3 Ш Ш И Ш Ш Ш [Ш

Ось в ячейке 5 ш ш ш ш ш ш ив Рис. 2.

Сортировка Бэтчера /53/ производит параллельное слияние пар отсортированных подпоследовательностей (Т(Ы) = 0(1о§2 Ы)).

Сортировка слиянием (Г(1) = 0(//1о§2 УУ)) берет два уже отсортированных списка и создает, сливая их, новый отсортированный список.

Сортировка выбором /53/. Из последовательности выделяется наименьший (наибольший) элемент и каким- либо образом отделяется от остальных, затем выбирается наименьший (наибольший) из оставшихся, процесс повторяется до тех пор, пока все элементы последовательности не будут отсортированы. На идее выбора основан алгоритм пирамидальной сортировки

Пирамидальная сортировка (7\1) = 0(Ы 1о§2 Ы)) строит бинарное дерево, значение каждого узла в котором превышает значение потомков. В результате наибольший элемент списка помещается в корень, при его удалении и выборе очередной пирамиды в корне оказывается следующий по величине элемент. Процесс повторяется, пока все элементы не окажутся в отсортированном списке.

Сортировка подсчетом /53, 86/. При сортировке подсчетом (7X1) = (?(N2)), каждый элемент сравнивается со всеми остальными; окончательное положение элемента определяется подсчетом числа меньших ключей.

Современные методы последовательных сортировок обсуждаются в работах /116, 117, 119/.

Касаясь параллелизма сортировок, кроме схемы параллельной сортировки Бэтчера /53/ (T(N) = OOog* N)), необходимо отметить параллельные варианты сортировок подсчетом /77/ (T(N2 /2) = 0(\)) и слиянием /79-81/ (T(N2/4)=0(\og2N)). Помимо отмеченных, современное состояние параллельных сортировок освящено в /83,102, 103, 118 /, где, в частности, приводятся схемы с временной сложностью Т{п) = O(log2 п).

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

Для двух упорядоченных массивов из п элементов (в примере п = 4) aJXl.5,5,7), {^=(1,7,9,13) слияние производится по матрице сравнения (рис.3).

Пример матрицы сравнений для слияния двух массивов

-00 0 4 4 6 оо

-00 0 + + + + + 0

0 - 0 + + + + 1

6 - - - - 0 + 2

10 - - - - - + 3

12 + 4 оо 0 5

0 1 2 3 4 5

Рис. 3.

Номера элементов в массиве {с(}4еЦ на выходе слияния единственным образом определяются местоположением смены знака в матрице сравнений, - для Ь1 в /-й строке, для aj в у'-м столбце, - при этом с bt, если av =-\, a((;tl)>0, aJt если av > 0, au+l)J=-\,

1, bt <Oj, au = sign(aJ-bl) = \ 0, b, i

-1, a!<bi. где /, j - любые индексы из набора 4 > / > 0 < j <4.

Для параллельного слияния двух упорядоченных массивов из т и п элементов сравнение всех элементов между собой в матрице сравнений производится одновременно. Временная сложность параллельного слияния Т(т *п) = 0(1).

Замечание 1. Вся сортировка слиянием по матрице сравнений в параллельном варианте имеет временную сложность T(N2/4)=0(\og2N). При этом данная сортировка относится к числу наиболее быстрых и в последовательном варианте

Немаловажным качеством сортировок является их устойчивость. Сортировка называется устойчивой, если она обладает свойством сохранения порядка записей с одинаковыми ключами /53/. К числу устойчивых относятся, например, сортировка вставками, к числу неустойчивых - корневая, пирамидальная, быстрая. В /83, 84/ предложены такие параллельные модификации известных схем сортировок, при которых модифицированные сортировки приобретают устойчивость, включая параллельное видоизменение сортировок подсчетом и слиянием.

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

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

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

1. Методы нулевого порядка, или прямого поиска, стратегия которых основана на использовании информации только о свойствах функции.

2. Методы первого порядка, в которых при построении итерационной процедуры наряду с информацией о функции используется информация о первых производных этой функции.

T(l)=0(Nlog2N) /80,81/.

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

В литературе /3, 6, 14, 25, 29, 36/ не выделяется универсальный метод, применимость которого была бы оправдана и эффективна во всех случаях. Выбор того или иного метода, его программная реализация должны быть согласованы с конкретными условиями, вытекающими из специфики решаемой задачи безусловной минимизации.

Для функции одной переменной классический подход /6, 20, 40, 47, 50/ при поиске минимума (максимума) функции /(х) состоит в последовательном вычислении функции при возрастающих значениях х до тех пор, пока не будет достигнуто наименьшее (наибольшее) значение функции. Значения л: должны быть заключены в интервале а<х<Ь. В начале процесса оптимизации интервал имеет длину Ъ - а. Вычислив значения функции /(х,) и /(х2) при значениях дг, и х2 в указанном интервале, интервал сужают. В зависимости от способов сужения интервала различают следующие методы оптимизации: метод общего поиска, метод Фибоначчи, метод золотого сечения, метод парабол.

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

1. Метод общего поиска /106/. Наиболее естественным способом сужения интервала для одномерной унимодальной функции является деление его па несколько равных частей с последующим вычислением значений целевой функции в узлах полученной сетки (рис. 4). В результате интервал сужается до двух шагов сетки. Обычно говорят о дроблении интервала неопределенности, которое характе2 ризуется коэффициентом к. Разделив интервал на N частей, получим к = ——-.

Чтобы получить к =0.01, потребуется вычислить функцию в 199 точках, при к = 0.001 потребуется N = 1999. Эффективность метода при уменьшении интервала неопределенности быстро падает.

Метод общего поиска

Суженный интервал неопределенности <-►

-----1—р 1 *3 ^

Рис. 4.

2. Метод Фибоначчи /9, 100/ является наилучшим в смысле максимального уменьшения длины отрезка локализации. Согласно этому методу на первом шаге проводятся два вычисления значений /(х) в точках д:'" и д*", д^" < х™, расположенных симметрично относительно середины отрезка А0 =[а,Ь]. По результатам вычислений одна из частей отрезка ([а,х,(1)] либо [д^б]) отбрасывается, при этом одна из точек (соответственно, д^1' либо д^") уже проведенных вычислений остается внутри отрезка Д2 = А'". На каждом последующем шаге точка очередного вычисления выбирается симметрично относительно оставшейся точки. Таким образом, на первой итерации проводятся два вычисления значений /(х), на каждой последующей - одно вычисление. Поэтому при заданном количестве вычислений N будет выполнено N-I шагов. При вычислении х{,л и х^, ./ = 1,^-1 используются числа Фибоначчи: = = 1, = ^ = 2,3». Условием окончания вычислений является выполнение заданного количества вычислений N.

Недостатком метода Фибоначчи, является то, что должно быть задано количество вычислений N.

3. Метод золотого сечения /6, 100/ применяется к недифференцируемым функциям. Функция /(х) должна быть задана и кусочно-непрерывна [а,Ь], иметь на этом отрезке (включая его концы) только один локальный минимум. На первом шаге выбираются две точки, расположенные симметрично относительно середины исходного отрезка; на каждой последующей итерации выбирается одна точка, расположенная симметрично относительно оставшейся точки. Метод золотого сечения основан на таком делении отрезка локализации, при котором отношение большей

•ечасти отрезка ко всему отрезку равно отношению меньшей части к большей. При таком делении используется две дроби Фибоначчи 0,382, 0,618, удовлетворяющие условиям Ф, +Ф2 = 1, Ф, = (Ф2)2. Итерации прекращаются, когда длина этого отрезка станет меньше заданной погрешности.

Метод золотого сечения применим даже к недифференцируемым функциям и всегда сходится; сходимость его линейна. Если на отрезке [а,Ь] функция имеет несколько локальных минимумов, то процесс сойдется к одному из них (но не обязательно к наименьшему). Этот метод применяют в технических или экономических задачах оптимизации, когда минимизируемая (максимизируемая) функция не-дифференцируема, а каждое вычисление функции выполняется по сложному алгоритму.

4.Метод парабол /21, 49/. Если /(х) дифференцируема, то можно построить более быстрые методы, основанные на решении уравнения /'(х) = 0. На практике часто /(х) имеет первую и вторую производную. Поэтому для нахождения нулей первой производной применяют метод линеаризации, что приводит к итерацион

Г(х ) ному процессу =хк - п . Для успешной работы метода парабол необходи Ы мы дополнительные поправки к алгоритму. В ходе вычислений надо проверять, продвигаются ли вычисления к минимуму. Если функция имеет несколько локальных минимумов, то метод может сойтись к любому из них или не сойтись вовсе. Описанный способ не дает гарантии того, что будут найдены все минимумы (и тем самым, что будет найден абсолютный минимум).

Наилучшими критериями сравнения методов поиска являются их эффективность и универсальность. Под эффективностью алгоритма обычно понимают количество вычислений функции, необходимое для достижения требуемого сужения интервала неопределенности. Лучшим в этом отношении является метод Фибоначчи, худшим — метод общего поиска. Как правило, методы Фибоначчи и золотого сечения, обладающие высокой эффективностью, наиболее подходят для решения одномерных унимодальных задач оптимизации /31,35, 106/.

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

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

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

Функции многих переменных. Численное решение задач безусловной минимизации (максимизации) функций многих переменных, как правило, значительно сложнее, чем решение задач минимизации (максимизации) функций одного переменного. С ростом числа переменных возрастают объемы вычислений и усложняются конструкции вычислительных алгоритмов, более сложным становится анализ поведения функции Основные трудности многомерного случая удобно рассмотреть на примере функции двух переменных f(x,y). Она описывает некоторую поверхность в трехмерном пространстве с координатами х, у, /. Задача f{x,y) = min означает поиск низшей точки этой поверхности. Рельеф этой поверхности можно изобразить линиями уровня. Проведем равноотстоящие плоскости / = const и найдем линии их пересечения с поверхностью f(x,y); проекции этих линий на плоскость хОу называют линиями уровня. Направление убывания функции указывают штрихами, рисуемыми около линий уровня. Полученная картина напоминает топографическое изображение рельефа горизонталями. По виду линий уровня условно выделяют три типа рельефа: котловинный, овражный и неупорядоченный. При котловинном рельефе линии уровня похожи на эллипсы (рис. 5, а). В малой окрестности невырожденного минимума рельеф функции котловинный.

Овражный тип рельефа. Если линии уровня кусочно-гладкие, то выделим на каждой из них точку излома. Геометрическое место точек излома называют истинным оврагом, если угол направлен в сторону возрастания функции, и гребнем — если в сторону убывания (рис. 5, б). Чаще линии уровня всюду гладкие, но на них имеются участки с большой кривизной; геометрические места точек с наибольшей кривизной называют разрешимыми оврагами или гребнями (рис. 5, в)

Неупорядоченный тип рельефа (рис. 5, г) характеризуется наличием многих максимумов, минимумов и седловин.

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

5. Метод спуска по координатам /20, 90/. Рассмотрим функцию трех переменных /(х,у,г). Выберем нулевое приближение л;0, у0, г0. Фиксируем значения двух координат у = у0, 2 = 70. Тогда функция будет зависеть только от одной переменной х, обозначим ее через /¡(х) = /(х,у0,г0). Используя методы поиска экстремума для функции одной переменной, находим минимум функции /¡(х), обозначив его через д:,. Выполнение шага из точки (х0,у0,г0) в точку (х1,у0,г0), по направлению, параллельному оси дг, уменьшает значение функции.

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

Графическое изображение линий уровня г)

Рис. 5. шаг приведет в точку (хх,ух,г0). Из этой точки делают третий шаг - спуск параллельно оси г и находят минимум функции /3(х) = /(хх,ух,г ). Приход в точку (хх,ух,гх) завершает цикл спусков. Далее циклы повторяют. Если на каждом спуске функция не возрастает, и при этом значения функции ограничены снизу ее значением в минимуме, то итерации сойдутся к некоторому пределу. Сходимость покоординатного спуска к минимуму зависит от функции и выбора нулевого приближения. Существуют случаи сходимости спуска по координатам к искомому минимуму и случаи, когда этот спуск к минимуму не сходится.

Метод спуска по координатам несложен и легко программируется, но сходится медленно, а при наличии оврагов - очень плохо. Поэтому его используют в качестве «первой попытки» при нахождении минимума.

6. Наискорейший спуск. Спускаться можно не только параллельно осям координат. Вдоль любой прямой г = г0 + о/ функция зависит только от одной переменной, /(г0+о/) = и минимум на этой прямой находится методами поиска экстремума для функции одной переменной. Наиболее известным является метод наискорейшего спуска, когда выбирается а = -№ас1 /)ггц, т. е. направление, в котором функция быстрее всего убывает при бесконечно малом движении из данной точки. Спуск по этому направлению до минимума определяет новое приближение гх. В этой точке снова определяется градиент и делается следующий спуск. Этот метод сложнее спуска по координатам, требуется вычислять производные и градиент (иногда конечно-разностными методами) и переходить к другим переменным. По сходимости наискорейший спуск не лучше спуска по координатам. При попадании траектории в истинный овраг спуск прекращается, а в разрешимом овраге сильно замедляется /50/.

7. Сопряженные направления /6, 9/. Методы наискорейшего спуска или спуска по координатам требуют бесконечного числа итераций, но можно построить такие направления спуска, что для квадратичной функции /(г) = (г, Аг) + (Ь,г) + с, (г есть п-мерный вектор) с симметричной положительно определенной матрицей А процесс спуска сойдется к минимуму за конечное число шагов. Вводится норма вектора х(|2 = (х, Ах) > 0, х*0. (8)

Определение (8) подразумевает скалярное произведение векторов х и у вида дг, Ау). Векторы, ортогональные в смысле скалярного произведения, называют сопряженными (по отношению к матрице А). Поочередный спуск по сопряженным направлениям особенно выгоден при поиске минимума (максимума). На этом основана большая группа методов: сопряженных градиентов, сопряженных направлений, параллельных касательных и др. Для квадратичной функции они применяются с одинаковым успехом, на произвольные функции хорошо обобщается метод сопряженных направлений, у которого детали алгоритма тщательно отработаны. Метод сопряженных направлений относят к наиболее эффективным методам спуска. Он неплохо работает при вырожденном минимуме, при разрешимых оврагах, при наличии слабо наклонных участков рельефа - "плато". Методы спуска неполноценны на неупорядоченном рельефе. Если локальных экстремумов много, спуск из нулевого приближения может сойтись лишь к одному из них, не обязательно абсолютному, в этом случае применяют случайный поиск /50, 90/.

8. Случайный поиск. Предполагают, что минимум (или все минимумы) лежит в некоторой замкнутой области; линейным преобразованием координат помещают ее внутрь единичного «-мерного куба. Выбирают в этом кубе N случайных точек; если о расположении экстремумов заранее ничего не известно. Вероятность, что хотя бы одна точка попадет в небольшую окрестность локального минимума, мала. Поэтому берут небольшое число точек и каждую рассматривают как нулевое приближение. Из каждой точки совершают спуск, быстро попадая в ближайший овраг или котловину; когда шаги спуска сильно укорачиваются, его прекращают, не добиваясь высокой точности. Этого достаточно, чтобы судить о величине функции в ближайшем локальном минимуме. Сравнивая окончательные значения функции на всех спусках между собой, можно изучить расположение локальных минимумов функции и сопоставить их величины. Метод случайного поиска зачастую позволяет найти все локальные минимумы функции 10-20 переменных со сложным рельефом. Он полезен при исследовании функции с единственным минимумом; в этом случае можно обойтись заметно меньшим числом случайных точек. Недостаток метода в том, что надо заранее задать область, в которой выбираются случайные точки. Широкая область затрудняет детальное исследование, узкая область влечет потерю экстремумов.

9. Метод Ньютона /6, 100/ относится к методам спуска. В этом методе очередная точка лг^в последовательности дг(0),дг(1),дг(2),. приближений к точке минимума х* выбирается по правилу ¿»-п + ра)=ха-п 8Гас1 /(.г'4"1»), Л = 1,2., где = матрица, обратная матрице А, таким образом, метод Ньютона является методом второго порядка. Вычисления заканчиваются, если /'(х{к)) <е, где е> 0 - малое, наперед заданное число. Сходимость метода Ньютона зависит от выбора дг(0), метод отличается трудоемкостью, требуя обращения на каждом шаге матрицы вторых производных минимизируемой функции.

10. Метод Дэвидона - Флетчера - Пауэлла /6/. Среди алгоритмов многомерной минимизации следует выделить группу алгоритмов, которые объединяют достоинства наискорейшего спуска и метода Ньютона. Такие алгоритмы принято называть квазиньютоновскими. Особенность состоит в том, что при их применении нет необходимости вычислять и обращать матрицу Гессе целевой функции, в то же время удается сохранить высокую скорость сходимости алгоритмов. Элементы релаксационной последовательности {*} в алгоритмах квазиныотоновских методов минимизации непрерывно дифференцируемой функции /(х) строят в соответствии с рекуррентным соотношением х{к) = х{Ы) + р{к), направление спуска на к-й итерации задают в видер(к) =-А^гас1 /(ха'1}), где -grad/(х{к'1))~ антиградиент целевой функции в точке х{к'1), Ак~ положительно определенная матрица порядка п, обновляемая на к -й итерации.

Метод Дэвидона - Флетчера - Пауэлла /106/ представляет собой алгоритм отыскания безусловного минимума целевой функции от нескольких переменных. Необходимы частные производные целевой функции по независимым переменным. В основе метода лежит допущение об унимодальности целевой функции, при нарушении допущения следует брать несколько исходных точек. Метод Дэвидона -Флетчера - Пауэлла позволяет обходить трудности, связанные с разрывами производных в пространстве проектирования. Распространено мнение, что этот метод наиболее эффективен из всех градиентных методов, дает полную информацию о кривизне поверхности целевой функции в точке минимума, однако при этом требуется больший объем памяти и длительность счета. При исследовании унимодальной функции, откуда бы ни начинался поиск, вычисления приведут к нужной точке. На рис. 6 приведены линии уровня функции с двумя локальными минимумами в точках Ох и 02. Сравнивая между собой значения функции в точках 01 и 02, находят, что наименьшее значение функции достигается в точке 02.

Пример функции с двумя локальными минимумами в точках Ох и 02

Рис. 6.

Если начать поиск наименьшего значения с помощью градиентного спуска из точки Ах, поиск приведет в точку 0{, которую ошибочно можно принять за искомый минимум. С другой стороны, если поиск начинается с точки Л2, то вычисления приведут в точку 02.

Принято считать /11, 90, 95/, что универсального приема, который бы позволил эффективно справляться с многоэкстремальностью, не существует. Самый простой прием состоит в том, что проводят поиск несколько раз из разных начальных точек. Если при этом получаются разные значения целевой функции, то сравнивая их, выбирают наименьшее /90, 106/. Расчеты останавливают после того, как несколько новых поисков не меняют полученного ранее результата. Выбор начальных точек поиска, обоснованность прекращения расчетов в значительной степени зависят от опыта и интуиции специалистов, решающих задачу. Во многих случаях необходима различная дополнительная информация о характере задачи, которая существенно помогает при выборе метода, начальной точки поиска. Если нет никаких предположений о специальных свойствах целевой функции и о характере рассматриваемой области, это затрудняет анализ. Конкретизация задачи, выделение определенных классов функций и областей позволяет провести более глубокое исследование и разработать специальные методы, которые решают задачу исчерпывающим образом.

11. Исследование ландшафтов целевых функций на основе эволюционной оптимизации. В рамках подхода к решению задач оптимизации исследуется возможность применения эволюционных и генетических алгоритмов /10, 13/. При этом строятся новые целевые функции, обеспечивающие получение оптимальных решений для исходных функций /54/. Использование одних и тех же целевых функций в рамках схемы эволюционных алгоритмов часто приводит к достижению локального, но не глобального экстремума. По этой причине возникает идея замены одной целевой функции на другую при условии, что это приводит к эквивалентному результату. Актуальна задача выбора эффективной целевой функции на ранней стадии разработки нового алгоритма. Для выбора такой функции конструируются подходы на основе анализа ландшафтов целевой функции /32, 57/. Разработанные в данном аспекте методы ориентированы на получение интегральных параметров ландшафта целевой функции, которые определённым образом характеризуют её сложность для эволюционных алгоритмов. Чтобы оптимизировать функцию модифицируется алгоритм расчета интегральных параметров на основе барьерных деревьев. На этой основе выделяются компоненты, по которым можно судить об эффективности соответствующих им целевых функций для эволюционных алгоритмов. Метод барьерных деревьев /57/ позволяет оценить глубину каждого локального минимума и степень его влияния на процесс эволюционного проектирования. Основная идея метода заключается в том, что сложность поверхности отражает высота к, на которую необходимо подняться, чтобы попасть из одного локального минимума в другой.

Подход включает следующие затруднения. Сравнивать целые наборы величин затруднительно, поскольку количество локальных оптимумов обычно различно для различных целевых функций. Кроме того, для автоматического сравнения желательно иметь один интегральный параметр. Поэтому необходимо оценить вероятность не возникновения преждевременной сходимости. Для этого достаточно, чтобы генетический алгоритм мог выйти из текущего локального оптимума и найти другой с лучшим значением. В случае успеха он вероятнее найдёт локальный оптимум, который ближе всего находится к текущему локальному оптимуму. Производится /54/ переход от набора параметров локального минимума к единственному параметру оценки области локального минимума. /(х(,х;) - минимальный барьер, который необходимо преодолеть, чтобы попасть из локального оптимума / в локальный оптимум j. Барьер - это наивысшая точка некоторого пути. Чтобы получить только один интегральный параметр для всего ландшафта, достаточно выделить из всех локальных оптимумов тот, выход из которого наиболее сложен. Значение такого оптимума интерпретируется как глубина В ландшафта. Для сравнения ландшафтов берётся отношение глубины к общей высоте ландшафта, которое называется сложностью ц/. Для сравнения ландшафтов используются два параметра - глубина В и сложность ц/.

Основная идея определения всех локальных оптимумов состоит в предварительной дискретизации пространства неравномерной сеткой. После этого для определения является ли некоторая точка локальным или глобальным оптимумом достаточно просмотреть соседние для неё точки. В результате получается линейный алгоритм сложности 0(3 nN), где N -количество точек исходной выборки, а п размерность пространства. Положительные результаты достигаются в случае поверхности близкой к классу унимодальных и при достаточных размерах области локализации экстремума /54/. Количество найденных решений зависит от модальности функции.

VII. Предварительная характеристика проблем вычислительных схем оптимизации. Как отмечалось, принята точка зрения /6, 20, 50, 90/, что не существует универсального алгоритма численного решения задач оптимизации. Метод, приспособленный к одному типу рельефа функции, может оказаться непригодным на рельефе другого типа. При решении сложных задач оптимизации пользуются несколькими методами, чтобы увеличить долю удачных решений. Поиск экстремума выполняется несколько раз с различными начальными приближениями, сравнивая значения целевой функции и выбирая наименьшее (наибольшее). Итерации прекращаются, когда несколько повторений не меняют результата.

Можно отметить, что по причинам изложенных затруднений в рамках существующих вычислительных схем безусловной оптимизации не ставится задача автоматического определения всех локальных экстремумов функции в области допустимых значений. Существующие системы компьютерной математики /41/ реализуют разнообразные схемы вычисления экстремальных значений функций. В частности, в Mathcad для определения экстремумов функций реализованы градиентные методы, включая метод сопряженных градиентов, метод Левенберга /41, 106/. В пакете Maple исследование на экстремум функции заключается в нахождении точек, в которых производная исследуемой функции равна нулю /41/. Устойчивая работа математических пакетов зависит от сложности исследуемой функции. Иногда пакеты не могут указать точку экстремума, лишь представляя исследуемую функцию графически. В этом случае не идентифицированы числовые значения, а графически они отображены с малой точностью разрешающей способности графического редактора. Сложности использования пакетов усугубляются для функций многих переменных.

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

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

Зачастую трудности решения актуальных задач оптимизации /42, 46/, включая задачи современной теории управления /34, 56/ сводятся к отмеченным трудностям известных методов безусловной оптимизации.

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

В качестве основы разработки целесообразно рассмотреть алгоритмы сортировки, поскольку они включают лишь операции сравнения и сами по себе не накапливают погрешности.

Сортировки традиционно применяются для поиска и моделирования методов теоретической информатики /102/. Положительный опыт применения сортировки именно для схем оптимизации описан в /77-79, 71, 75/.

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

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

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

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

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

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

Для достижения поставленной цели в диссертационной работе ставятся следующие задачи:

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

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

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

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

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

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

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

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

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

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

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

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

Конкретно, научная новизна характеризуется следующим образом:

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

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

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

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

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

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

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

Основные положения, выносимые на защиту:

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

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

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

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

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

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

Внедрение и использование результатов работы. Полученные в работе результаты использованы

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

2. В госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания» (№ гос. регистрации 01.2.00 106436, код ГРНТИ 28.23.15), проводимой на кафедре информатики ГОУВПО ТГПИ.

3. В учебном процессе кафедры информатики Таганрогского государственного педагогического института в рамках курсов «Информатика», «Информационные технологии в математике», «Численные методы», «Элементы абстрактной и компьютерной алгебры».

Апробация работы. Основные результаты работы докладывались на:

X, XI международных конференциях «Математические модели физических процессов» (Таганрог, ТГПИ, 2004,2005 гг.);

V международной научно-практической конференции по программированию УкрПРОГ' 2006 (Украина, Киев, 2006 г.)

VIII международных научно-практических конференциях «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права» (Москва, МГАПИ, 2005 гг.);

VI научно-практической конференции преподавателей, студентов, аспирантов и молодых ученых (Таганрог, ТИУиЭ, 2005 г.);

IV-й международной научно-практической конференции «Проблемы регионального управления, экономики, права и инновационных процессов в образовании» (Таганрог, ТИУиЭ, 2005 г.);

Ill межрегиональной научно-практической конференции студентов, аспирантов и молодых ученых «Молодежь XXI века - будущее российской науки» (Ростов, РГУ, 2005г.); международной научно-практической конференции «Модернизация отечественного педагогического образования: проблемы, подходы, решения» (Таганрог, ТГПИ, 2005 г.)

Публикации. По материалам диссертационной работы опубликовано 13 печатных работ с общим объёмом 14,3 печатных листов.

Структура и объём работы. Диссертационная работа состоит из введения, 3 глав основного раздела, списка литературы и 5 приложений. Основное содержание работы изложено на 153 страницах, включая список литературы из 120 наименований.

3.7. Выводы.

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

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

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

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

Заключение

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

Диссертационная работа включает следующие научные результаты.

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

2. Исследованы границы применимости единой конструкции схем безусловной оптимизации для функций с топологически сложным рельефом; даны оценки временной сложности максимально параллельной формы предложенных схем.

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

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

5. На основе сортировки синтезирована схема автоматической программной идентификации глобальных и локальных экстремумов норм разностных решений систем ОДУ при дискретной вариации параметров и указана связь с оценкой устойчивости решения; схема перенесена на случаи вариации параметров трансцендентных, алгебраических и других уравнений.

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

Научная новизна результатов диссертационной работы заключается в следующем.

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

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

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

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

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

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

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

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

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

Практическое использование результатов работы.

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

2. В госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания» (№ гос. регистрации 01.2.00 106436, код ГРНТИ 28.23.15), проводимой на кафедре информатики ГОУВПО ТГПИ.

3. В учебном процессе кафедры информатики Таганрогского государственного педагогического института в рамках курсов «Информатика», «Информационные технологии в математике», «Численные методы», «Элементы абстрактной и компьютерной алгебры».

1. Айзеке. Р. Дифференциальные игры. Пер. с англ. - М.: Мир, 1967 - 480 с.

2. Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем / Отв. ред. А.П.Ершов. — М.: Наука, 1982.

3. Амосов A.A., Дубинский Ю.А., Копнёнова Н.В, Вычислительные методы для инженеров. — М.: Высшая школа, 1994.

4. Арнольд В.И. Обыкновенные дифференциальные уравнения. М.: Наука. -1971.-240 с.

5. Арушанян О.Б., Залеткин C.B. Численное решение обыкновенных дифференциальных уравнений на Фортране. — М.: Изд-во МГУ, 1990.

6. Атгетков А.В . Методы оптимизации Учебн. для студ. втузов / М. изд. МГТУ им. Н.Э. Баумана, 2003 г. -439с.

7. Бабушка И., Витасек Э., Прагер М. Численные процессы решения дифференциальных уравнений. М.: Мир, 1969. - 368 с.

8. Базара М., Шести К. Нелинейное программирование. Теория и алгоритмы: Пер. с англ. М.: Мир, 1982. - 583 с.

9. Банди. Б. Методы оптимизации. Вводный курс: Пер.с англ. М.: Радио и связь, 1988.- 128 с.

10. Батищев Д.И. Генетические алгоритмы решения экстремальных задач: Учебное пособие. Воронеж : ВГТУ, 1995.

11. Бахвалов С., Жидков Н.П., Кобельков Г.М. Численные методы.— М.: Лаборатория Базовых Знаний, 2001.

12. Бахвалов И.С., Лапин A.B., Чижонков Е.В. Численные методы в задачах и упражнениях. — М.: Высшая школа, 2000.

13. Букатова И.Л. Эволюционные технологии- средства интенсивной информации. М.: РАН, ИРЭ, ПРЕПРИНТ №5(593), 1994.

14. Березин И.С., Жидков Н.П. Методы вычислений. Т. 2. - М.: Государственное издательство физико-математической литературы, 1962. - 640 с.

15. Боглаев Ю.П. Вычислительная математика и программирование.— М.: Высшая школа, 1990.

16. Буланов С.Г., Заика И.В., Катрич С.А., Ромм Я.Е. Моделирование критериев устойчивости и определение экстремальных значений решений дифференциальных уравнений на основе разностных схем при помощи сортировки / ТГПИ Таганрог. - 2004.

17. Бэр К., Гольштейн Е.Г., Соколов H.A. Об использовании метода уровней для минимизации выпуклых функций, не все значения которых конечны // Экономика и матем. методы, 2000, т.36, вып.4.

18. Вазов В., Форсайт Дж. Разностные методы решения дифференциальных уравнений в частных производных. — М.: ИЛ, 1963.

19. Валях Е. Последовательно-параллельные вычисления. — М.: Мир, 1985

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

21. Вержбицкий В.М. Основы численных методов. М.: Высшая школа, 2002. -848 с.

22. Вержбицкий В.М. Численные методы (линейная алгебра и нелинейные уравнения). — М.: Высшая школа, 2000.

23. Верлань А.Ф., Сизакое B.C. Интегральные уравнения: методы, алгоритмы, программы. — Киев: Наукова думка, 1986.

24. Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989. -360с.

25. Влах И., Сингхал К. Машинные методы анализа и проектирования электрических схем: Пер.с англ. М.: Радио и связь, 1988 - 559 с.

26. Воеводин В,В. Вычислительные основы линейной алгебры. — М.: Наука, 1977.

27. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2004-608 с.

28. Вотяков A.A. Линейная оценка сложности двумерной задачи ЛП // Экономика и матем. методы, 1998, т.34, вып.З.

29. Галеев Э.М., Тихомиров В.Н. Оптимизация: теория, примеры, задачи. — М.; Эдиториал УРСС, 2000.

30. Гантмахер Ф.Р. Теория матриц. М.: Наука, 1988. - 552 с.

31. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. — М.: Мир, 1985.

32. Гладков Л.А., Зинченко Л.А., Курейчик В.В., Курейчик В.М., Лебедев Б. К, Нужнов Е.В, Сорокин С.Н. "Методы генетического поиска" . Под ред. В.М. Курейчика. Таганрог, изд-во ТРТУ, 2002. 147с.33