Разработка и исследование схем оптимизации на основе алгоритмов сортировки с приложением к идентификации экстремумов решений дифференциальных уравнений тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Заика, Ирина Викторовна

• Заика, Ирина Викторовна
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Заика, Ирина Викторовна

Введение

Глава 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. В учебном процессе кафедры информатики Таганрогского государственного педагогического института в рамках курсов «Информатика», «Информационные технологии в математике», «Численные методы», «Элементы абстрактной и компьютерной алгебры».

Список литературы диссертационного исследования кандидат технических наук Заика, Ирина Викторовна, 2007 год

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