Оптимизация численных алгоритмов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ



- „«ЯП

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

МИХЕЕВ Сергей Евгеньевич

ОПТИМИЗАЦИЯ ЧИСЛЕННЫХ АЛГОРИТМОВ

010109 - Дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени доктора физико-матемагических наук

Санкт-Петербург - 2006

003065582

Работа выполнена в Санкт-Петербургском государственном университете

Официальные оппоненты

доктор физ -мат наук, профессор Демьянов В Ф

доктор физ.-мат наук, Жадан В Г доктор физ.-мат. наук, профессор Нестеров М М

Ведущая организация - институт математики и механики Уральского отделения Российской академии наук

Защита состоится 22 февраля 2007 г в 14 часов на заседании диссертационного совета Д 002 017 02 при Вычислительном центре имени А А Дородницина Российской академии наук по адресу. 119991, Москва, ГСП-1, ул. Вавилова, 40.

С диссертацией можно ознакомится в библиотеке ВЦ РАН по адресу Москва, ул Вавилова, 40.

Автореферат разослан января 2007 г.

Ученый секретарь диссертационного совета

(В В Рязанов)

Общая характеристика работы

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

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

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

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

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

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

||Л(®)-а||<с||»-а|Р, р> 1, О 0, (1)

(а — искомое решение). Она и исследовалась для самых распространенные значений параметра р: 1 — линейная сходимость и 2 — квадратичная сходимость

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

тем самым, усилить результат Так, ограниченность производной, по возможности, заменяется на ее липшицевость Например, в теореме Канторовича о сходимости метода Ньютона для уравнения д(х) = О сам Л.В.Канторович использует условие вида ||g"(a;)|| < L V х €Е S. А в теореме Канторовича в версии М.А Красносельского это условие заменяется на липшицевость д' в S.

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

Получение оценки (1) часто является существенной частью обоснования одноточечного итеративного метода вида хк+1 := Л(хк), к = 0,1,... Удобным инструментом для этого оказался метод дифференцирования по итерации, куда органично вкладывается полупроизводная Его можно применить для обоснования сходимости метода Ньютона в классах функция, отличных от тех, которые рассматривали Л.В. Канторович, М.К. Гавурин, И.П. Мысовских в соответствующих теоремах о методе Ньютона.

Он же использовался и для обоснования метода квадратичной оптимизации (МКО), предназначенного для решения нелинейных программ вида f(x) —> min . Суть МКО — в последовательном состав-

д(х)< о

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

Под названием метод параболоидов это можно встретить у Дж Ортеги и В Рейнболдта для поиска безусловного экстремума. Модификации метода параболоидов рассматривались К. Левенбергом и С Гольдфельдом, Р. Курантом, Т. Троттером

Наиболее близка к МКО одна из модификаций метода линеаризации Б.Н Пшеничного и Ю.Н.Данилина. В ней для ускорения сходимости предлагалось ввести в линейную аппроксимацию целевой функции на шаге квадратичную добавку (х — xk)rLxx(x — хк)/2, где Lxx - гессиан соответствующей функции Лагранжа. В случае линейности функций-ограничений он совпадает с гессианом функции /, а сам метод линеаризации — с МКО.

МКО, как часть метода последовательной оптимизации управле-

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

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

В одномерном пространстве итеративное решение скалярного уравнения д(х) = 0 и минимизация скалярной функции f{x) при помощи экстраполяционных полиномов порядка большего единицы восходит к П Л. Чебышеву. Интерполяционные полиномы можно встретить в методе Мюллера и интерполяционном методе высокого порядка поиска одномерного минимума Н.Е. Кирина (1968 г.). Однако разнообразие методов на основе интерполяции, перспективных для исследования, этим далеко не исчерпывается.

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

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

Несколько снижаются вычислительные затраты на определение значений целевой функции, если в упомянутой последовательности от комбинации к комбинации происходит минимальное изменение состава элементов Коды Грея позволяют создавать алгоритмы минимального изменения, но даже в простейших случаях целевой функции вида /(ж) = | ~ Щ минуют вопрос об отсечениях. Для решения задач минимизации на пространствах с большим числом элементов за разумное время необходимо изыскивать новые алгоритмы, допускающие включение отсечений

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

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

Научная новизна состоит в следующем.

1. Установлены предельно широкие условия, когда решение нелинейной программы /(ж) —> min есть часть решения системы

д(х)<0

V/(х) + №д(х) = О Л А > 0 Л Хд(х) = 0 Л д{х) < 0 и обратно

2. На основе оценки (1) и принципа минимальности получены формулы релаксации для произвольного одноточечного итеративного метода ж,+1 = А{хг), которые позволяют генерировать итерации с лучшей сходимостью, чем {ж*}.

3. Описано исчисление полупроизводных.

4. Обоснован метод дифференцирования по итерации, использующий полупроизводную и разностную производную.

5 Уточнены некоторые оценки удаленности решения нелинейного уравнения в банаховом пространстве

6 Посредством метода дифференцирования по итерации обоснован метод Ньютона решения нелинейного уравнения со специальной левой частью

7. Установлены область сходимости и произведена оценка скорости сходимости метода квадратичной оптимизации (МКО), строящего последующую итерацию хк+1 по итерации хк как решение квадратичной программы

У/(х*)(в - хк) + (х- хк)тН*(хк)(х - хк)/2 тш

Установлены критерии выбора начальной точки для МКО. Установлены оценки вида Ца;**1 — ж|| < а||ж*+1 — ж^Ц для МКО.

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

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

10 Модифицирован метод Била решения квадратичных программ: приведена табличная схема, позволяющая применять его для смешанного состава переменных (ограниченных и неограниченных по знаку), дан алгоритм поиска начальной допустимой таблицы, вкладывающийся в основной алгоритм; указан алгоритм предотвращения зацикливания

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

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

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

14. Приведен и обоснован алгоритм решения задач вида гт_

| —тщ

¿о

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

Апробация материалов исследования проходила на семинаре кафедры информационных систем, на семинаре по теории управления под руководством В.И.Зубова в Санкт-Петербургском университете, на семинаре по дифференциальным уравнениям под руководством Н.М Матвеева в Педагогическом университете им. А Герцена, на семинаре в ВЦ РАН, на семинаре в UMIST (University of Manchester Institute of Science and Technology), на семинаре в институте математики и механики УрО РАН, на семинаре в Санкт-Петербургском Университете Экономики и Финансов; на международных конференциях: CDE'IV (Руссе, Болгария, 1987), SICDE (Болгария, 1991), CSAM'93 (С.-Пб.), Interval 94 (С.-Пб.), ICI&C97 (С -Пб ), MMSED-2004 (Москва), Устойчивость и процессы управления 2005 (С -Пб). По теме диссертации опубликована 31 работа общим объемом 780 стр., из них два учебных пособия (8 печатных листов) и две монографии (27.4 печ. листов).

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

По своему характеру первая глава является вводной для глав 3,4,6 и ее можно отнести к основам нелинейного программирования. Основной объект исследования там — нелинейные программы общего вида

/(«)-»■ (2)

д(х)<0

где / — скалярная функция, именуемая целевой, х — n-мерный вектор, д — га-мерная вектор-функция (ж, д - столбцы). Нелинейная программа (2) здесь именуется для краткости задачей А.

Поиск у функции Лагранжа F(x, Л) = f(x) + Xg(x) (Л - т-мерная строка), седловой точки (ж, А), определяемой неравенствами

F(x Д) > F(x, Ä) > F(x, A) VA >0, Vx е Rn, именуется задачей В. Связь между решением задачи А и ж-составля-ющей решения задачи В описана в теоремах Куна-Таккера. В случае дифференцируемости функций fug, как известно, седловая точка необходимо удовлетворяет системе Куна-Таккера

VxF(x, А) = 0 А А > 0 Л tV\F(x, А) < 0 Л №\F(x,X) — 0 (3)

Поиск решения системы (3) в свою очередь можно рассматривать как самостоятельную задачу, которая далее именуется задачей С Выпуклость / и д гарантирует совпадение множества решений задач В и С. Здесь доказаны вложение множества решений задачи А в ж-проекцию множества решений задачи С без выпуклости и обратное вложение для слабо унимодальных функций Слабая унимодальность функции / определяется как выпуклость множества {ж|/(ж) < с} для всех с.

Теорема 1.5. Пусть у задачи С существует решение (£, Л) и выполнены условия- 1) функции fug слабо унимодальны; 2) / — непрерывна, 3) V/(ж) ф 0 Тогда а есть решение ЗА.

Контрпримерами показано, что эту теорему нельзя усилить снятием какого-либо условия.

Комбинация теорем Куна-Таккера, связывающих ЗА и ЗВ, ЗВ и ЗС, порождает следующее утверждение: если целевая функция и функции ограничения выпуклы и дифференцируемы, то при выполнении условия Слейтера существует решение ЗС и решение ЗА есть его ж-составляющая Напрямую, без использования ЗВ — задачи посредника, доказан более сильный результат. Теорема 1.7. Пусть 1) у задачи А существует решение ж;

2) Уг 6 I = {г|<л(ж) = 0} 3 Vflr,(ж) ф 0;

3) функция g слабо унимодальна и непрерывна,

4) существует х* такая, что д(ж*) < 0 (условие Слейтера);

5) существует Vf(x)

Тогда у задачи С существует хотя бы одно решение, которое имеет х-составляющую, совпадающую с решением ЗА.

Многие итеративные методы могут быть модифицированны с помощью принципа минимальности (ПМ) с целью улучшения сходимости Изложим ПМ для одноточечных итеративных методов вида х* = Л(х), Л В —> В, где В — банахово пространство, ж — приближение на текущем шаге, индекс * отмечает величины, относящиеся к последующему шагу. Пусть помимо приближения ж на шаге известна дополнительно информация I Такой информацией может быть, например, оценка (1). Пополним I, если в ней нет оценки погрешности d текущего приближения, величиной d Выберем некоторое строение 2 итеративной информации I, которое будет постоянным на всех шагах Информации I совместно ежи Л(х) соответствует допустимое на текущем шаге множество 1{х, А{х), I)

В общем случае I зависит от предыстории итеративного процесса. от начального приближения до текущего Поэтому, если вместо Л

используется какая либо его модификация М.А, то итеративная информация иная- /м. Предлагается для построения очередной итеративной пары {■^'л!- -^м} так использовать Хм Х{х-М1 «Д(жм), 1м)

Последующую итерацию х*м следует выбрать так, чтобы при наличии величин А(хм), хм и информации 1Ы оценка погрешности <1М итерации х^ была бы минимальной Иными словами, если А(г>) = тахг6гм г\\> тох*м = а^тшоея А(щ) Очередная итеративная информация должна обладать строением Н, входящая в нее оценка погрешности есть (Iм = Д(ж^). Если не вся итеративная информация следующего шага найдена, то для определения оставшейся части рассматривается для неполного количества входной информации допустимое множество Х'(и, </), V £ В, / £ Н. ИI* назначается таким, что £'(ж*,/*) С если только 3 б 5

и X' (х*м, 7) э Хм. Если минимайзер функции Д(-у) или очередная итеративная информация не определяются единственным образом согласно вышеизложенному, то это следует сделать с привлечением каких-нибудь дополнительных соображений об их выборе.

Модификация алгоритма, полученная с помощью ПМ именуется его точной релаксацией (ТР), а итерации с ТР — методом точных релаксаций. В алгоритмах с линейной сходимостью (р— 1) в евклидовых и гильбертовых пространствах, когда (\/х) ||ж|| = \/х х, применение ПМ приводит к следующему методу ТР. (Чтобы не загромождать формулы, верхний и нижний индексы "м" опущены.)

Инициализация. Если известна оценка ||х° — а\] < с?о, то д, :=

(1о, иначе с? •= +оо. Полагаем х := ж0 Пошаговые расчеты:

г := А(х) — х, г := ||г ||, г = <¿(1 - с2)/лЛ + с2, (4)

если г < г, то

х* .= х + г(1/2 + ^(1-с2)/2г2), ^ = \/<Р — (г + ¡Р{1 — с2)/г)2/4, если г > г, то

* г . ст

ж "с2" (5)

В скалярном пространстве в случае <¿(1 — с) > г расчетные формулы совпадают с (5), а в противном случае имеют вид

.= ж + (йщъ г + ^)/2 ^ := (<I -

В скалярных пространствах й* < ёс/(1 — с), что всегда лучше, чем применение (1) для оценки погрешности последующего приближения согласно исходному алгоритму (тогда всего лишь < (¿с) В многомерном пространстве оценка по ТР в большинстве случаев, когда ||Л(ж) — ж|| ф ¿у/1 — с2, лучше оценки приближения по исходному алгоритму Л(ж), и в очень редких случаях, когда ||*4.(ж) —ж|| = й-^/Х — с2, оценки погрешностей и сами приближения совпадают.

Несколько более сложные расчетные формулы, но также с априори легко вычисляемой трудоемкостью, получены на основе ГШ для итеративных процессов с квадратичной сходимостью (р = 2)

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

Пусть II, Ш - банаховы пространства (В-пространства), М С и и имеется отображение А . М М-.

Определение 3 1. Пусть х — не изолированная точка множества М и величина

1А(х) =Тт||А(а + Д)-А(®)||иг/||Д||сг (6)

конечна. Назовем тогда ее полупроизводной отображения А в точке х Здесь предел берется по таким А, что х + А £ М

Если М не имеет изолированных точек и полупроизводная Ьх{х) существует для всех х Е М, то формула (6) определяет на М функцию, которую будем именовать полупроизводной отображения А на множестве М

Если отображение А имеет в М - множестве без изолированных точек - константу Липшица Ь, то оно имеет в М полу производную, ограниченную сверху числом Ь Для выпуклого множества верно и обратное.

Лемма 3.1. Пусть полупроизводная отображения А ограничена константой Ь в выпуклой области задания М: Ьх{х) < Ь Ух Е М. Тогда отображение А Липшицев о в М с константой Ь Когда значения отображения суть линейные ограниченные операторы из одного банахового пространства в другое, будем именовать его семейством операторов Таким образом, для семейства операторов имеет смысл понятие полупроизводной Для краткости записи оператора, обратного к оператору А(у) из семейства {А(г/)} будет использоваться А~1(у) вместо более корректного (А(у))-1. Лемма 3.2. Пусть Z,U,W - В-пространства и множество М лежит в Z. Если определенное на М семейство линейных ограниченных операторов А(у) : V —» У/, у 6 М, имеет полупроизводную

ЬА{х) в точке ж £ М и оператор А(х) имеет ограниченный обратный А-1 (ж) • Ш —^ Л, то существует 6 > 0, такое, что для всех у из окрестности V := 5(ж, 6) М операторы А{у) имеют обратные, а семейство обратных операторов А~г(у) -^-11, у £ V, равномерно ограничено, в ж тоже имеет полупроизводную ЬА-1 (х) и

ЬА-г{х)<\\А-\х)\\ЧА{х) Демма 3.3. Пусть для каждой точки в интервала [О, в] имеет место оценка полупроизводной вещественной функции / вещественного аргумента. Lf{s) < г (в) и г (в) - конечна, неотрицательна и суммируема по Лебегу Тогда |/(в) — /(0)| < I Уз £ [о, в].

Jo

Лемма 3.4. Пусть отображение А имеет в точке х полупроизводную ¿А(ж), а скалярная функция / определена в некоторой окрестности точки у := ||А(ж)|| и существует полупроизводная Lf(y). Тогда суперпозиция С?(ж) := /(\\А(х)\\) имеет в х полупроизводную, которая удовлетворяет оценке Ьа(х) < Lf(y)LA(ж). Лемма 3.5. Пусть Z,U,W - В-пространства и ограниченное выпуклое множество М лежит в Z Если определенное на М семейство линейных ограниченных операторов А(ж) • 17 —» ТУ, ж £ М, на М имеет полупроизводную ЬА(ж) и ограниченные обратные А~г(х), такие, что ||л-1(ж)||£А(ж) <о- Ух ем, то семейство обратных операторов {А~1(х)}хем ограничено снизу по норме положительной величиной, а семейства операторов {А(х)}х^м и {А~1(х)}х^м липшицевы на М.

Суждения о сходимости итераций ж0, ж1,... к а можно выводить из оценки Цж*^1 — а|| < ||ж* — а||р. Ее, в свою очередь, часто удобно получать с помощью следующего приема, именуемого далее дифференцированием по итерации. Пусть поиск решения а € Е7 некоторой исходной задачи сведен к поиску решения уравнения (3(0, а) = 0 итерациями {ж*} С и, определяемыми рекуррентно из

в{хк+1 - хк, ж*) = 0, (7)

где (7 х11 IV, II, IV — ^-пространства. Предполагается, естественно, что существует достаточно простой (сравнительно с исходной задачей) алгоритм разрешения уравнения (?(ж, у) = 0 относительно первого аргумента Соединим отрезком текущую итерацию хк с решением а исходной задачи и параметризуем его-

хк{г) := а + М, <? = ж* -а, ¿£[0,1].

После подстановки в (7) переменной хк(€) вместо постоянной хк получится семейство уравнений с параметром t Обозначим решение такого уравнения относительно хк+1 через ж(£) и введем у = х(6)—а. Поскольку бг(0,а) = 0, справедливо у(0) = 0. Если (? имеет производные по первому и второму аргументам (С?!, С2), то тождество С(у — сИ, Хк^)) = 0 можно продифференцировать по I

вЦу - <?<, хк{ЩУ - + С2(у - хк{Ь))й = 0 (8)

Если С^у — (И,хь(Ь)) не вырождена, (8) можно разрешить относительно у у={1 - {С-^у - сГг, Жй(<)))-1С2(г/ - <И, хк^)))с1 Отсюда получаем дифференциальное неравенство

1Ы1 < Р - (0'г(у - ХкШ^Щу - ¿1, ж*ф)|||И II (9)

Если получить оценку

||1 - (Щу - «И, ХкШ-Щу - ж*(*))|| < /(||у||,<), то (9) совместно с очевидным ЦуЦ^ < ||у|| и с у(0) = 0 даст систему

(№ </ШИ)Й1> 111/(0)11 = 0. (ю)

Если f непрерывна в некотором открытом множестве М, то, как известно, максимальное решение задачи Коши

г = /(м)Й I, *(о) = 11у(0)|| = о, (и)

мажорирует любое решение системы (10) относительно скалярной функции ||з/|| на общем интервале существования [0, а]

Каким должно быть это а, чтобы извлечь из решения задачи Коши (11) оценку сверху на ||ж*+1 — а||?

Согласно построению ||ж*+1 — а|| — ||у(1)||. Следовательно нужно использовать оценку ||у(1)|| < г(1). Поэтому общий интервал существования должен содержать [0,1], те должно быть обеспечено а > 1. Путь к этому указывает следствие из теоремы Пеано: Лемма 3.6. Определим для положительных Ь прямоугольник Нъ = [—Ь, Ь] х [0,1] Пусть существует Ь, такое, что вир |/(2,<)| < Ь.

Пусть f непрерывна в Щ Тогда задача Коши (11) имеет на сегменте [0,1] хотя бы одно решение, мажорируещее любое решение системы (10) на общем интервале существования.

Согласно построению и допущениям относительно (? функция у определена на [0,1] и удовлетворяет (10) Поэтому, когда решение

задачи Коши (11) существует на сегменте [0, а') и а' > 1 (что будет, например, если выполнены условия последней леммы), тогда \\xkJrí — а\\ < z( 1) Vdl^ll) = V'GI®* — <*||)> чего часто бывает достаточно для анализа сходимости и скорости сходимости.

В тех случаях, когда функция G всего лишь липшицева и не дифференцируема, существенное удобство в выкладках предоставля-

h{t + r)-h(t)

ет инои взгляд на разностное отношение п(т. ъ) := —---—

г

функции h{r¡) скалярного аргумента r¡ из сегмента D Обычно второй аргумент разностного отношения считается фиксированным, а в оценках, которые предстоит сделать, он будет переменным. В описании такой смысловой нагрузки на параметр удобно следующее.

Определение 3.2. Разностной производной в точке t £ D заданной на сегменте D С R1 вектор-функции h : D —У U (U — В-пространство) будем называть зависящую от параметра t вектор-функцию /iv (t, •), заданную в D(t, D) (D —1)\{0} формулой

b?{t,e)=h{t + e)-H{t) Ve € D(t, D) (12)

Величину e назовем отклонением (разностным), а операцию нахождения разностной производной —разностным дифференцированием

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

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

1. (/ ± 9)v = fV ± gv- 2. (r/)v = r/v, г — число.

3. Если вектор-функция / дифференцируема в точке t, то fv(t, е) = f(t) + ш(е) = f'(t), где lim^o <*(е) = 0.

Здесь и далее под знаками = и < понимается, соответственно, равенство и неравенство, приближённые с точностью до величин, стремящихся к 0 6 U, когда е —¥ 0.

4. Пусть g либо / имеет полупроизводную в t. Тогда

(f9)V(t) = fV(i)g(t)+mg*(t).

5. Пусть на сегменте Dg с R1 заданы вектор-функция g • Dg Df С U и отображение / : Df —> V Тогда определена суперпозиция

f(g) Dg ->V И если f дифференцируемо в точке g(t) (t 6 Dg), то {f{g))v{t,e)~f{g{t))gv{t)

6. Пусть вектор-функция g Dg Df с U и отображение f : Df V имеют полупроизводные Lg и Lf в точках t и git), соответственно Тогда || (/(ff))v (i)|| < Lf\\gv{t)\\ < LfLg.

7. Пусть имеются вектор-функции g • D U, h : D —V, и Df := {(ж, у) | (3i G D) x = g(t) А у = h(t)} Пусть

1) g и h имеют полупроизводные Lg и L^ в точке t £ D,

2) z-=(g(t),h(t))eDf\dDf;

3) в точке z отображение / обладает производными Фреше по первому и второму аргументам: f'g и f'h.

Тогда (f(g, h))? (t) S fg{g{t),h{t))gv [t) + fUg(t),h(t))h? (t).

8. Пусть теперь из предположений п.7 изъято 2) и ослаблено 3) 3') в точке z = (g(t), h(t)) отображение / имеет полупроизводные по первому и второму аргументам Lfg и Lfh-

Тогда \\{f{g,h))Y{t,e)\\ < LfgLg + LfhLh. Основываясь на известных теоремах о дифференциальных неравенствах, метод дифференцирования по итерации можно применять и при отсутствии £?з — производной функции G по второму аргументу, уходя, тем самым, от вопроса о существовании производной у x(t) Для этого следует произвести разностное дифференцирование по t тождества G(y — dt, ж= 0 и начать исследовать вместо (9) приближенное дифференциальное неравенство

||yv|| < ||/ — (Gi(y — dt, Xk{t)))~1G2 (у — dt, ж*(£))||||й|| (13)

с использованием вышеприведенных свойств разностной производной.

Если удается получить оценку сверху правой части (13) величиной /(||i/||,i)||d ||, то вектор-функция у = x(t) — а должна удовлетворять системе

Ы\7 < /(Il2/IM)IHI, ||у(0)|| = 0, (14)

решения которой также мажорируется решением задачи Коши (11).

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

д(х) = 0, xeDcU, (15)

для нелинейного отображения д £> —> Ш в паре банаховых пространств II, W (В-пространств).

Теорема 4.1. Пусть II, IV — В-пространства, область О принадлежит I/, д . О —Ш, и выполняются следующие условия.

1) Н$(зо)|| < Яо; < Г0;

2) 1 липшицево в I) с константой Ь\

3) ||^_1(я;)|1 < гм Ух £ И, 4) шар принадлежит Б, где

ак .= 1~л/г1~2Р1, Рь < 1/2 Л Тм >

¿х :— <

Ьг0

- (т-м/гр -1)2 /ГИ<001 (Рь<1/2\ Г"90 ~ 2гмЬ ' {Р, > 1/2) 7 1 Тм < ак)'

1 — то/гм 1

Р, := Ьтхд0, если гм < оо, то Тм •=-—-1—, иначе Тм •.= -—.

Ьг0 Ьг0

Тогда

а) в шаре £(хо,^) существует решение а уравнения (15),

б) которое является предельной точкой фазовой траектории решения задачи Коши

х = -1~1{х)д{х)/ ||/-1(®)»(®)|| =: *■(*), ®(0) = х0, (16)

а именно, существует Т & [О, «У, такое, что решение этой задачи определено на [О, Т), непродолжимо вправо и 11т*_>.т_о ж(2) — а. Причем ||<7(жОО)|| монотонно убывает до 0 на [О,Т).

Кроме того, если гы < оо, а оценка то огрубляется до т^, то условие 2) можно ослабить до локальной липшицевости I в £>'

Теорема 4.1 в части существования и оценки удаленности решения перекликается с теоремами Канторовича, Мысовских, Гавурина (ЧТК, ЧТМ, ЧТГ). Сравнительный анализ приводит к следующему.

1. Условий в ЧТМ больше, чем в Т.4.1, на условие гмго£9о < 2. А оценка удаленности корня отображения д от заданной точки ж0 по ЧТМ всегда хуже, чем по Т.4.1 («¿м > ¿х).

2. Сравнительно с ЧТК в Т 4.1 добавлено условие ||^'(ж)|| < гм. Однако, допускается возможность гм — оо, что соответствует условиям ЧТК. Утверждения ЧТК и Т.4 1 в этом случае совпадают. Т.е Т 4 1 является расширением ЧТК на случай владения информацией о гм.

3. В ЧТГ имеется требование локальной ограниченности производной Гато от д'. В Т.4 1 требуется лишь локальная липшицевость д'. Таким

образом, когда го огрублено до гм, Т 4 1 является усилением ЧТГ в части оценки удаленности корня отображения д от заданной точки хо Когда го < гм, Т 4 1 является расширением ЧТГ и дает лучшую оценку удаленности

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

Определение 4 2 Назовем классом П(£>, <х, хо,до, Го), где а, до, Го > 0, а хо принадлежит открытой области 2?, класс отображений д, удовлетворяющих таким условиям 1 д непрерывно в £)

2 Линейный оператор 3 - производная (Фреше) отображения д - в области О невырожден и имеет полупроизводную LJ

3 (Уж € В) Мж)г(ж) < а, где г(ж) = ||/_1(®)11

4 9о > ||<7(жо)||, го > г(ж0)

Теорема 4.2. Пусть £/, IV - В-пространства, Оси, д : О Ш, д принадлежит П(£), а, хо, до, ^о) и верны условия:

1) Ра := го<тдо < 1,

2) шар 5(жо, сЫ принадлежит области Б, где с?2 := — ^^——

сг

Тогда в шаре Б{жо,с?г) существует корень а уравнения (15), который является правой предельной точкой фазовой траектории решения задачи Коши с автономным уравнением

х = -7-1(ж)д(ж)/ ||7-1(ж)д(ж)|| = F(ж), ж(0) = ж0, (17)

а именно, существует Т £ (0,сУ, такое, что решение этой задачи определено на [О, Т), непродолжимо вправо и Ьггь^т-о ж(£) = а. Причем ||<7(ж(£))|| монотонно убывает до 0 на [О, Т).

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

Теорема 4.3. (Локальная сходимость метода Ньютона) Пусть область X) принадлежит В-пространству, пусть отображение д принадлежит П(15, <т, Жо) и некоторая оценка (1 удаленности решения а. уравнения (15) от начальной точки жо удовлетворяет следующим условиям

1) <тй —. со < с, где с есть решение уравнения

С (с) (ес — 1 — с)/с = 1 (18)

(расчеты показывают, что с принадлежит (1.25,1.26)),

2) S(x0,pd) CD, где р = 1 + C(<rd) Тогда

а) метод Ньютона, начатый в точке хо, корректно определен и сходится к решению а., все итерации лежат в шаре S(xo,pd);

б) скорость сходимости оценивается неравенством

||®fe+i - а|| < С (a\\xk - а||) - а||,

причем s < 1 С (<rs) < C(cr)s, что соответствует квадра-

тичной скорости сходимости ||®fc+i — а(| < С (а) — а||2,

в) решение а системы д(х) = 0 единственно в шаре S(xo,d) Теорема 4.4. Условия 1, 2 теоремы 4 3 являются также и необходимыми в том смысле, что при их нарушении можно найти функцию и начальную точку, для которых метод Ньютона не сходится, а для начальных точек, обеспечивающих сходимость, оценка скорости сходимости точна.

Теорема 4.5. Пусть U, W — В-пространства, D С U, g : D —» W, g принадлежит TL(D,cr,xo,9o,ro) и выполнены также условия:.

— 2с _

1) Р„ = г (¡а9 о < --—, где с — решение уравнения (18);

J. "j" 2с

2) S(xo,pdo) С D, где р ■= 1 + C(<rd0), d0 •= -———.

<т

Тогда

а) существует решение а уравнения д(х) = 0, единственное в шаре S(x0,do);

б) метод Ньютона, начатый в точке xq, корректно определен и сходится к конечному решению а,

в) скорость сходимости оценивается неравенством

||»fc+i - а|| < С (<г||х* - а||) \\хк - а\\.

Метод квадратичной оптимизации (МКО) — основное содержание главы 5 Его назначение - итеративное решение задачи А. Пусть хк есть текущее приближение. Тогда по МКО следующее приближение к решению задачи А есть решение квадратичной программы

Г f(x) := Vf(xk)(х - хк) + (х - хк)ТН(хк)(х - хк)/2 _ min ,

< ~g{x,xk)<0

[ g(x,xk):=g(xk) + J(xk)(x-xk)

относительно х Здесь Н - гессиан функции /, J - матрица, строки которой есть Vgt, г — 1,т

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

Получены результаты о сходимости МКО "классического типа". Теорема 5 1 о локальной сходимости- при достаточной близости начальной точки к решению, липшицевости якобиана функций-ограничений, их достаточной "не сплющенности", липшицевости гессиана целевой функции метод сходится и для скорости сходимости имеет место оценка (1), где константа с вычисляется на основе вышеперечисленных характеристик нелинейной программы.

Исходя из тех же характеристик и дополнительной информации о последующей итерации х1, получены теоремы о сходимости МКО без привлечения сведений об удаленности решения от итерации ж0, напротив, вычислена константа d в оценке Цж1 — а|| < ¿Цж1 — ж°|| как функция от характеристик нелинейной программы в случае ограничений-равенств (теорема 5.5), так и в случае ограничений-неравенств. Такая оценка может использоваться как критерий остановки итеративного процесса. Положим v := ж1 — ж0, v := ЦгГЦг-Обозначим через eig функцию, значение которой есть наименьшее собственное число ее матричного аргумента

Лемма 5.17. Пусть функции fug задачи А имеют в выпуклой области задания V гессиан Н и матрицу Якоби J, соответственно, и пусть для всех ж, ж + Д Е V выполнены условия: 1) ||Я(ж + Д) - Я(ж)||2 < г||Д||2; 2) eigtf (ж) > ß > 0;

3) ||V/(®)||a < p-, 4) Sp Н(г) < s„; 5) ||J(x + Д) - J(x)||2 < X||AÜ2,-

6) для всех G, баз J, верно. 8р((С(ж)Сг(ж))-1) < г; введем обозначения :— \fr + (1 + sHy/r)2ß~2, С(и) = V* (ju + + Zu2/2)) , и пусть

7) C(v) - с < 1; 8) (L - l)v < Lp^f, 9) Si:= {y|||y-®l|la <cv}cV;

Тогда ||ж2 — ж1 j< vC(v), где ж2 — итерация, полученная посредством МКО из х1

Теорема 5.6. Пусть выполнены условия 1 — 8 предыдущей леммы и 5:=|ж|||ж-ж1||<т^]сУ

Тогда МКО, начатый еж0« имеющий следующую итерацию ж1, сходится к некоторой точке а, причем все порождаемые им итерации лежат в шаре S и а £ S

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

Лемма 5.19. Пусть U,W — В-пространства, q — отображение íiy С U в íls С W, обладающее в V — некоторой окрестности внутренней точки уо множества С1у — следующим свойством• с точностью до малых второго порядка по отношению к Цуг — Vi\\

«Ы - q(yi) & <ЭЫ(У2 - Vi) + 0(j/2,2/i)i

здесь Q — линейный оператор, непрерывный в точке уо и имеющий в ней ограниченный обратный HQö1!! S с и Qo — Q(y0); отображение О удовлетворяет неравенству ¡|О(3/25 3/х)11 < и\\У2 — 3/11|, а ис < 1. Обозначим sq = 5(1/0) Тогда в некоторой окрестности точки s0 £ определено единственное непрерывное обратное отображение у = p(s) со свойствами.

1) q(p(s)) = s, 2) p(s0) = Уо, 3) \\у - у0|| < - «о||

где е > 0 и может быть сделана сколь угодно малой выбором размеров окрестности точки so

С помощью теоремы 5 7 вычислив значение целевой функции /(ж0) и значения функций-ограничений g(ж0), можно определить удаленность решения от некоторого приближения ж0, если g - слабо унимодальна.

В §5 5 исследуются возможности модификации МКО. Оказалось, что V f{xk), J(xk), g(xk) должны вычисляться с возрастающей точностью, иначе сходимость не гарантирована. Гессиан согласно теореме 5 9 может быть вычислен лишь в начальной точке, но это будет стоить сужения множества, на котором гарантирована сходимость В конкретных применениях погрешности в вычислениях гессиана мало сказывались на скорости сходимости, и, поскольку вычислительные затраты на итерацию существенно снижались в сравнении с немоди-фицированным МКО, общие вычислительные расходы на достижение желаемой точности были заметно ниже.

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

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

Вопросы построения квадратичных аппроксимаций рассмотрены в §6.1 -§6 8 Пусть интерполяционный агрегат является квадратичной вещественной функцией.

/(ж):=ж*Яж, я°)' <19)

где * в верхнем индексе обозначает операцию транспонирования и комплексного сопряжения, hoo — вещественное число, ho — n-мерная строка, Я— эрмитова матрица размером [п х п]. Н* = Н. Когда все узлы принадлежат вещественному пространству, все параметры интерполяционного агрегата тоже полагаются вещественными, в этом случае в (19) операция * сводится к транспонированию, а эрмитовости соответствует симметричность

Когда исходный материал для построения есть значения целевой функции уо, , у$ в узлах ж0,..., х', при s = N, где N — число параметров агрегата (19), требуется решать задачу линейной (по параметрам) интерполяции: /(ж*) = уъ, к = 0,. , s, а когда s > N — задачу аппроксимации с некоторым критерием качества, например,

s 2

а(Я).= £к-/(Я,ж')| —>min (20)

1 н

Доказано (§6.1-§6.4), что для существования и единственности конечного решения в указанных задачах в вещественном случае достаточно, чтобы для задачи интерполяции узлы представляли собой набор из начального узла ж0, получаемого из внешней задачи, и серий (21), (22), а для задачи аппроксимации узлы содержали этот набор, в комплексном случае для обеих задач существование и единственность конечного решения обеспечиваются добавлением к вышеуказанному набору еще узлов серий (23), (24).

xh = x° + eek, хп+к=х°-еек, к =7~ri. (21)

Здесь е*, к — 1, п — единичные столбцы

х2п+(2п-к)(к-1)/2+3-к _ хо + еек + еез > к= 1>п_ 1) ^ _ Й + (22)

Пусть I — мнимая единица

х"^-1 = х° + хеек, к = Т^ь. (23)

хк+{гп-к+г)к12+]-к-1 = хо+еек+Х£е1^ к — — 1, 3 = к + 1,п. (24)

Требование выпуклости принципиально, когда известно, что исходная функция выпукла. Невыпуклость аппроксимации тогда однозначно свидетельствует о ее низком качестве. Бывают и иные причины добиваться выпуклости аппроксимации Предложены три алгоритма, обеспечивающие выпуклость / из (19). Первые два итеративны и дают приближение к условному минимуму суммы квадратов отклонений значений агрегата от значений целевой функции на узлах при условии выпуклости. Качество приближения оценивается по величине этой суммы Эти два алгоритма базируются на простых условиях положительной определенности матрицы, отличных от критерия Сильвестра и удобных в аналитических исследованиях

Теорема 6.16. Пусть ||А||Е •= положительной полу-

определенности матрицы А необходимо, чтобы

Эр А> \\А\\Е, (25)

и достаточно, чтобы

Бр Л > Ц-^Цб- (26)

Условие вида (25) не улучшаемо в том смысле, что существует положительно полуопределенная матрица А, удовлетворяющая

Эр Л =

Константа ■\/п — 1 в условии (26) не улучшаема• для всякого 8 > О найдется знаконеопределенная матрица В, такая, что

Эр В > (л/га—Т — 6) 11-ВЦв. ■

Необходимый и достаточный критерии положительной определенности получаются из соответствующих вышеприведенных заменой нестрогих неравенств на строгие (теорема 6 17).

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

Шаг 1 Найти любым способом без условия выпуклости лучшую, согласно какому-либо критерию, матрицу Нвз по данным узлам.

Шаг 2 Преобразовать унитарным преобразованием U к диагональному виду D - U*H*3U подматрицу Нвз (см (19)) матрицы Нвз.

Шаг 3. Обнулить все отрицательные элементы в D, т е. получить матрицу D+. Шаг 4. Найти Н+ = UD+U*.

Шаг 5. Заменить в Нвз подматрицу Нвз на Н+ То, что получится, и есть ближайшая по шуровской норме || • ||Е к наилучшей безусловной аппроксимации выпуклая аппроксимация.

Если все узлы вещественны, то подматрица Нвз — вещественна, симметрична и к диагональному виду она приводится ортогональным преобразованием: D = СТНС (шаг 2), и на шаге 3. Н+ = CD+C'T.

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

В §7 1 рассмотрен дискретный аналог метода Чебыщева (ДМЧ) решения скалярного уравнения f(x) = 0. В нем для получения каждой следующей итерации предлагается использовать обратную интерполяционную задачу с п последними узлами. Вычисляются в узлах ж!,...,ж„ величины у, — f{x,), г=1,п Находится свободный член а интерполяционного полинома Р такого, что ж, = Р{у,), г = 1, п. Далее ж, •= ж.+i, г = 1, п — 1, хп-.~ а.

Пусть М = sup |р(")(г)| sup |/'(ж)|/га!, где F - обратная к f

г

функция. Тогда ключевым для сходимости ДМЧ является поведение

решения разностного уравнения

tk ~ tk-i -tk-2 ~ ■ -tk-n=lnM, к > п. (27)

связанного с итерациями по ДМЧ соотношением tг > In \уг j Пусть наибольший корень уравнения V(v) = vn — vn~x — . — 1 = 0 -характеристического для (27) - обозначен через Ai Теорема 7.2. Наибольший положительный корень характеристического уравнения удовлетворяет соотношению

2 > Ai > ц(п) .= 2п/(п + 1) (28)

Непосредственное приближенное вычисление корней характеристического уравнения дает следующие оценки А*(п) снизу для Ai(n):

А П 2 3 4 5 6 7

А* 1.61803 1 83928 1.92756 1.96594 1.98358 1.99196

ß 1 33333 1.50000 1 60000 1.66666 1.71428 1 75000

Все цифры в таблице для А*(п) верны в том смысле, что А*(га)+0 00001 > А^га).

Теорема 7.3. Справедливы неравенства Лх(п+1) > Аз.(га), п = 2,3,...

Таким образом, когда п — 2,1 можно использовать табличные оценки А* (га) с погрешностью не превосходящей 0 00001, когда п = 8,200-оценку Ах(га) > А(7) с погрешностью не большей 0 0001. Для теоретических исследований можно использовать оценку (28) при всех п с погрешностью не более 2/(га+ 1)

Теорема 7.4. Сходимость ДМЧ можно гарантировать, когда начальные приближения удовлетворяют условиям 1 > п~у/М \ук\, к = 1, га Скорость сходимости по значениям функции можно при к > га оценить неравенством

1пЫ<сА?(га) + (1пМ)/(1-га), (29)

где с =тахь=11 п(2~к 1п( п~УИ Ы)),

или, более точно, с:=тахк-1, ,»(А^"ь(га) 1п( п~л/М \уь|)) ■

Потенцирование оценки логарифма (29) приводит к традиционному виду оценки. \ук\ < 1}А1, где к > п, Б = ес.

Для погрешности по аргументу имеет место оценка \хк -x\<L п~УМ Das к > п, где L = mf"1/'^) = supF'(y).

X у

Те же идеи лежат в исследовании поиска одномерного минимума на основе n-точечной интерполяции (§7.3). Рассматривается задача поиска безусловного локального минимума скалярной функции / £ С(поЬ) на множестве (а, Ь). Предлагаемый итерационный метод решения этой задачи состоит в том, что на каждом шаге очередное приближение к точке минимума находится как точка минимума интерполяционного многочлена, построенного по ранее найденным приближениям Пусть имеются узлы хь, Xk+i,..., ®fc+n-i достаточно близкие к решению х. Вычислим в этих узлах значения функции и построим интерполяционный полином р степени п — 1: р(ж») = /(®>)> i = k,k + n— 1

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

После выбора начальных узлов Хк, к = 1 , п, этот алгоритм определяет все последующие Хк, к = n + 1, п + 2,.... Положим

М - sup |/i">fo)|/(/(n-l)i), где г = 2|/2|-£|/,г(г-1)(6-а)-2|, чб(«,ь) ,=3

ft — разделенные разности г-ro порядка f(xk, ■ , £fc-fi)- Ключевым для метода является разностное уравнение tk — tk-2 ~ •••— Н-п — М с характеристическим уравнением V(v) :— vn — vn~2 — . — v — 1 = 0. Его наибольший корень, как и ранее обозначаемый через Ai(n), участвует в оценке скорости сходимости вида (29)

Лемма 7.1+7.2. Все корни многочлена V простые Его наибольший вещественный корень Ai(n) лежит в интервале

(м(п) := (п + л/5га2 - 4)/(2п + 2), Д •= (l + Vb/2).

Непосредственные приближенные вычисления корней характеристического уравнения дают такие оценки А*(п) снизу для Ai(n) :

Ai п 3 4 5 6 7 8

А* 1.32471 1 46557 1.53415 1.57014 1 59000 1.60134

1 17539 1 27177 4/3 1.37617 1.40776 1.43202

Все цифры в таблице для А*(п) верные в том смысле, что А*(п)+0 00001 > Ai(n) > А*(п) Конечное число цифр у иррациональных /х(п) получено посредством простого усечения. С точностью до Ю-5 с округлением в большую сторону ß = /х(оо) = 1.61804. В силу леммы 7 1 верно Ai(oo) = ß

Теорема 7.7. Справедливо Ai(n+ 1) > Ai(n), п = 3,4,

Следовательно, для п = 3,8 можно использовать табличные оценки А*(п) с погрешностью, не превосходяшей 0 00001, для п = 9,97 оценку Ai(n) > А*(8) с погрешностью не более ß—\*(8) < 0.017 Для теоретических исследований можно использовать вместо Ai(n) его оценку /¿(п) при всех п с погрешностью не более

ß-/i(n) = 0 5 (l + л/5 - (п + л/5п2-4)/(п+1)).

Имеет место 98) > А* (8) и /i(n) ß

Теорема 7.8. Итеративный метод на основе п-точечной интерполяции корректно определен и сходится к решению уравнения f{x) = 0, если. 1) / е CfaM;

2) сужен интервал (а, Ь) так, что

V .= infJ/>)|-E sup №Л(Ь-аГ-2>0,

«е(а.Ь) f^ «6(а,Ь) 1г - ¿У

3) в определении М использовано V вместо I;

4) хь £ (а, Ь), k = I,п — 1, Sgan С (а,Ь) при pz = 2f'(x„)/s,

либо при рз = + Dxг+1 ) / ""v/M, I> = ес;

5) с maxfe=1, ,„ (in | ""^М /'Ы/«|) А^ * < 0 Скорость сходимости тогда оценивается формулой

\<х-хк\к> 1.

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

Дискретное программирование тесно связано с вопросами порождения пространств при реализации алгоритмов на ЭВМ В §8 2 предложен названный здесь пачечным алгоритм порождения комбинаторного пространства (сочетаний), обладающий порядком минимального

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

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

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

Сопоставим комбинации кодовое слово IV, состоящее из нулей (весы с номером равным позиции данного нуля не вошли в комбинацию) и единиц (соответствующие весы вошли)

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

Пачечный алгоритм основан на генераторе сочетаний, который состоит из двух рекурсивных подалгоритмов- прямого, отмечаемого параметром 8 = 1 и обратного, отмечаемого параметром 8 = — 1, одинаковых за исключением понятий "лево, начало" и "право, конец".

Пачечный генератор

Шаг П1(£). Сдвигается, если возможно, пачка влево, когда <5 = 1, и вправо, когда 8 = — 1; если сдвинуть пачку нельзя — впереди ((5 = 1), или сзади (8 = — 1), от нее стоит код-единица или же пачка подошла к левому концу (8 = 1), или к правому (8 ~ —1), кодового слова, то из стека возвращаются кодовое слово и положение пачки, управление возвращается на шаг П1 тому алгоритму, который вызвал активный в данный момент.

Шаг П2. В стек засылается кодовое слово и положение пачки. Шаг П3(<£). Если размер пачки был больше 1, то происходит сокращение его на 1, оставляя вне пачки первую (£ = — 1), или последнюю (5 = —1), код-единицу. Если размер пачки был равен 1, то вместо выполнения следующего шага П4 происходит переход к шагу П1(<5).

Шаг П4(<5). 8.= -8 я

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

ную пачку, занимающую крайне правое (S = 1) или левое (S = — 1) положение. Назовем два варианта такой инициализации прямой и обратной, соответственно

Теорема 8.5. При отсутствии отсечения пачечный генератор порождает все С* комбинаций размером к в любой инициализации (Два варианта начального слова соответствуют взаимно-обратным, т е. симметричным, последовательностям сочетаний.)

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

1) \T(W) - PI —> min, 2) T(W) -L —> min ,

' 1 V ' 1 w / V / t[w)>l

3) H - T(W) T(minH; 4) T(W) E [L, H],

где P,L,H — заданные числа, T(W) — вес комбинации со словом W.

Численные эксперименты с пачечным генераторм показали сокращение числа обсчитываемых комбинаций в этих задачах в сравнении с иными способами порождения комбинаторного пространства примерно на два порядка при п = 14.

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

Введем обозначения- х, (t) — количественное состояние г-й отрасли (переменной) в момент времени t, г = 1, п, it{y) — количественное состояние г-й отрасли после вложения в нее у средств, полагаем, что (у) — неубывающая с непрерывной производной с, (у) > 0 функция, х,е — норматив г-й отрасли, то есть состояние, в которое желательно привести г-ю отрасль, х,о "= ж, (0) — количественное состояние г-й отрасли в начальный момент t = 0, ; общее финансирование u(t) — неубывающая непрерывная справа и в момент окончания Т непрерывная слева функция времени; объем общего финансирования за все рассматриваемое время U := и(Т), реальный план — набор п неубывающих функций времени ü(t) ■— (ui(t), ..,un(t)),

подчиненных условию u(t) = функции из набора — ре-

альные отраслевые планы, они могут быть рассматриваемы также как функции от общего финансирования с областью задания G При наличии у функции u(t) скачков G ф [0, £7]. Тогда рассматривается виртуальный план й(у) .= (ui(y),. .,ИпЫ) (у € [О, С/]), являющийся расширением реального u(t) := U(u(t)). Потребуем также, чтобы функции и, (у) были неубывающими функциями и чтобы выполнялось условие у = для всех у £ [О, U], Производные ■и, (и, у) := du,(y)/dy — интенсивность финансирования г-й отрасли после вложения у средств (во все отрасли); Н,(у) •= {х,е—тс.г(у))/х,е — относительная нехватка в г-й отрасли, после вложения в нее у средств.

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

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

Теорема 9.2. Условие = ^Т Vi>J> € М

является необходимым и достаточным, чтобы план и был опорным.

Теорема 9.3. Пусть минимизируемый функционал имеет вид

F = I Е М*)) di> где Ш = (i - ; т > о;

и,(0) = и(0) < h(у) = ж»0 + с«у, С, = const;

х, = (хге — х,о)/с, ^в,—решение уравнения //(ж,) = 0, г = l,nj.

Тогда для того, чтобы минимизирующий набор ui(t), .,un(t) был опорным планом, необходимо и достаточно коэффициентам Ai, ., Хп придать значения

>о_ кхге _-—

t — ТТ /п\ ' г — п1

с,н,[ 0)

к — произвольное положительное число.

Назначение теоремы 9.3 не в том, чтобы для одного частного набора весов {А,}, не прибегая к сложным алгоритмам, сразу получить минимайзер для F, а в указании того, какими должны быть веса, чтобы получить минимизацией приемлемый с некоторых других

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

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

где Л,..,/« — выпуклые функции, заданные на сегменте [О,II] с кусочно-непрерывной второй производной и конечным количеством участков линейности Тогда оптимальные, в смысле минимизации функционала Р реальный план (их., - й{1) и реальное управление («х), ..,«„(<)) =. г{Ь) существуют и могут быт вычислены с помощью описанных в приведенном далее алгоритме ПВП виртуальных планов (их(2), ...,ип(£)) = и(£) и управлений (ЗгС'О) •••! ЗпМ) Ш) следующим образом.

Назначается 2, (£)=з,(м(<)) для всех моментов непрерывности функции и

для моментов разрыва. Здесь (г/,(£ — 0),«(£)), Д := —

скачок м(£) в момент I Реальный план й{1) может быть вычислен либо через реальное управление и производную и по формулам

либо непосредственно через виртуальный план й{1) = и(и(^)).

Алгоритм построения виртуальных планов (ПВП). Положить зг(у) = 0, если существует индекс в, такой, что правосторонние производные удовлетворяют неравенству /г' (уг) > (у3) И пусть соотношение /¡{уг) = ттт Гт(ут) определяет множество индексов I, а ,7 — его подмножество, выделяемое соотношением Д'(у) = 0 Если

г = 1, п,

J пусто, положим

Если 7 непусто для какого то у0, то управление % задается постоянным на некотором сегменте таким образом.

а. Для г <$. «7 функции зг(у) = 0.

б. Для з Е 1 находятся Д,, такие, что + г/) = 0 Уг) Е (О, Д>) и либо f"(y(33 + Д, + 0) > О, либо у° + Д, = и.

в. ъ3{у) -=&3/<г 1е/

г Решается задача Коши для системы обыкновенных дифференциальных уравнений <Ш/ <1т = з(й), и(0) = 0, на сегменте [0, XX]

Выводы. Прямые теоремы о связи решений нелинейных программ и систем Куна-Таккера могут эффективно применяться в исследованиях по нелинейному программированию.

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

Математический аппарат, основанный на полупроизводных и разностных производных, хорошо проявил себя в различных оценках В частности, в оценивании удаленности решения нелинейного уравнения в банаховом пространстве, что позволило получить некоторое продвижение сравнительно с оценками в известных теоремах о сходимости метода Ньютона. Этот аппарат органично соответствует методу дифференцирования по итерации — эффективному инструменту в исследованиях по сходимости итерационных процессов Его применение позволило полностью обосновать метод квадратичной оптимизации и обосновать метод Ньютона решения систем нелинейных уравнений для особого класса функций, не охватываемого результатами Л. В. Канторовича, И. П. Мысовских, М. К. Гавурина.

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

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

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

Результаты выносимые на защиту Теоремы о связи решений нелинейной программы и системы Куна-Таккера.

Принцип минимальности для релаксации произвольных алгоритмов на основе оценки (1)

Аппарат полупроизводных и разностных производных с методом дифференцирования по итерации

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

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

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

Оценки скорости сходимости и областей сходимости дискретных методов высокого порядка решения скалярных уравнений и поиска скалярного экстремума

Алгоритмы обслуживания оптимизации в комбинаторных пространствах

Оптимизация экономических состояний, в частности алгоритм решения задач вида

где 41,. .ип,и- неубывающие функции, возможно разрывные

По теме диссертации опубликованы следующие работы :

1 Мейлахс А М , Михеев С.Б. Алгоритм решения // Задача оптимального распределения капиталовложений Л.: изд. Ленингр ун-та, 1971 С 14-17.

2. Михеев СЕ О сходимости метода последовательной оптимизации // Математическая физика Киев Наукова Думка, 1976. Вып. 20

С 52-58.

3 Михеев С Е Расширение теоремы Куна-Таккера на унимодальные функции // Математическая физика Киев Наукова Думка, 1977. Вып. 21. С 43-44.

4 Михеев С.Е Моделирование экономико-производственных систем 1, ВИНИТИ н 80070823, 1980, 6 с.

5 Михеев С.Е Моделирование экономико-производственных систем 2, ВИНИТИ н 7013087, 1982, 7 с

6 Михеев С Е Вычислительные аспекты метода последовательной оптимизации // Вопросы механики и процессов управления. JL. изд. Ленингр ун-та, 1980. Вып. 4 С 223-242.

7 Михеев С.Е. Одна задача распределения ресурсов и оптимизация сепарабельных целевых функций / / Методы математического анализа управляемых процессов Л., изд. Ленингр ун-та, 1980 С 169-179.

8. Камачкин А.М , Михеев С.Е. Планирование распределения ресурсов с дискретным временем // Труды ЛКИ: Математические модели и САПР в судостроении. Л.: изд. ЛКИ, 1982. С. 45-48.

9. Камачкин А М., Михеев С.Е Задача распределения и смешанная целочисленная программа // Труды ЛКИ. Математические модели и САПР в судостроении Л.: изд. ЛКИ, 1985. С 50-57.

10 Михеев С Е Области достижимости для одной дифференциальной игры. // Математические методы анализа управляемых процессов. Л.: изд. Ленингр ун-та, 1986. С. 133-146.

11. Михеев С.Е. Сходимость дискретного метода Чебышева и метода Мюллера // Вопросы механики и процессов управления. Л.: изд. Ленингр. ун-та, 1991. Вып 15. С. 89-99.

12. Михеев С.Е. Методы высоких порядков в задачах нелинейного программирования и решения уравнений. СПб : изд СПб ун-та, 1992. 95 с.

13. Михеев С.Е., Томина О.Н. Алгоритмы решения одного семейства задач обслуживания // Дифференциальные уравнения с частными производными (Общая теория и приложения). СПб.: изд. СПб пед. ун-та, 1992. С 93-100.

14. Михеев С Е., Силина Е К. Одна модель колебательного движения. // Вестник С.-Петербург, ун-та, 1994. Сер. 1, вып. 1. С 72-76

15 MiheevS.E А поп Linear Differential Model ofSheduling. Proceedings of ICI&C97 (International conference on mformatics and control). St Petersburg, Russia, 1997, p. 835-840.

16 Miheev S.E Contraction of Attainability Domains in a Game of Pursuit Nova Journal of Mathematics, Game Theory and Algebra vol 6, no 2/3, Nova Science Publ., New York, US, 1997, p. 147-161

17 Михеев С E Релаксационное ускорение на основе областей достижимости. // Вестник С.-Петербург ун-та. 1999 Сер 1, вып 3 (№ 15). С. 29-35

18 Михеев С Е Выпуклая квадратичная интерполяция // Вестник С.-Петербург, ун-та 1999 Сер. 1, вып 2 (№ 8) С. 42-48

19 Михеев С Е Управление конкурентоспособностью. СПб.- изд СПб. ун-та, 2001. 36 с

20. Михеев С.Е. Нелинейные методы в оптимизации СПб . изд СПб. ун-та, 2001. 276 с.

21 Михеев С.Е Комбиниационное дозирование. // Вопросы механики и процессов управления СПб : изд СПб ун-та, 2003 Вып 19 С 271277.

22 Михеев С Е. Эффективность релаксационного ускорения // Николай Ефимович Кирин (сборник статей). СПб • изд. СПб ун-та, 2003 С 183-197

23. Михеев С.Е Зоны безопасности в играх с линией жизни // Вестник С -Петербург, ун-та. 2003. Сер. 1, вып 3 (№ 15). С 69-78.

24. Михеев С Е Метод трехкоординатного спуска // Вопросы механики и процессов управления. СПб.: изд. СПб. ун-та, 2004 Вып. 21 С 128-136

25 Miheev S.E. Tax system & and interest to new industrial capacities. // Труды Международной конференции "Математическое моделирование социальной и экономической динамики" (MMSED-2004). М., 2004. С 212-216.

26. Михеев С Е. Выпуклая квадратичная аппроксимация // Вычислительные технологии. Новосибирск, 2004. Т 9, №4 С 66-76 27 Михеев С.Е Конкурентоспособность и трудоемкость // Вопросы механики и процессов управления СПб.. изд СПб. ун-та, 2004 Вып

23 С 118-141

28. Камачкин А. М., Михеев С. Е., Евстафьева В В Модели колебаний в нелинейных системах СПб.. изд СПб ун-та, 2004. 194 с.

29 Михеев С. Е Сходимость метода Ньютона на различных классах функций // Вычислительные технологии. Новосибирск, 2005 Т 10, №3 С 72-86.

30. Михеев С.Е , Позняк Л Т Улучшение оценок в одной теореме Мысовских о методе Ньютона // Труды международной конференции "Устойчивость и процессы управления". СПб , 2005 Т 2 С 876-885.

31 Михеев СЕ Существование и оценка решения нелинейного уравнения в банаховом пространстве // Вестник С -Петербург, унта 2005 Сер. 10, вып 3. С. 13-27.

32 Михеев В С., Михеев С Е Точная релаксация модифицированного метода Ньютона // Процессы управления и устойчивость Труды XXXVII международной научной конф - СПб., 2006 С 119-125

33 Михеев С.Е , Позняк JI.T Одна новая теорема существования решения нелинейного уравнения в банаховых пространствах // Вестник С.-Петербург, ун-та. 2006 Сер 10, вып 3 С. 35-43

Подписано в печать 14 11 2006 Формат бумаги 60 х 84 1/16 Бумага офсетная Печать ризографическая Уел печ л 2,0 Тираж 100 экз Заказ 3901

Отпечатано в отделе оперативной полиграфии НИИХ СПбГУ 198504, Санкт-Петербург, Старый Петергоф, Университетский пр 26

ВВЕДЕНИЕ

Глава 1.

ОБЩИЕ ВОПРОСЫ

НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Глава 2.

РЕЛАКСАЦИОННОЕ УСКОРЕНИЕ ИТЕРАТИВНЫХ ПРОЦЕССОВ

§2.1. ОПИСАНИЕ ПРИНЦИПА МИНИМАЛЬНОСТИ.

§2.2. ТОЧНЫЕ РЕЛАКСАЦИИ

ДЛЯ МЕТОДА ПРОСТЫХ ИТЕРАЦИЙ

§2.3. ТОЧНЫЕ РЕЛАКСАЦИИ

В СКАЛЯРНОМ ПРОСТРАНСТВЕ

§2.4. МНОГОМЕРНЫЙ СЛУЧАЙ (р= 1).

§2.5. ОБОБЩАЮЩАЯ СХЕМА.

§2.6. СТАТИСТИЧЕСКИЕ СВОЙСТВА ТОЧНОЙ

РЕЛАКСАЦИИ МЕТОДА ПРОСТОЙ ИТЕРАЦИИ (р=1)

§2.7. АСИМПТОТИКА ТОЧНОЙ РЕЛАКСАЦИИ.

§2.8. НЕЛИНЕЙНАЯ СХОДИМОСТЬ (р > 1)

§2.9. ЧИСЛЕННЫЕ ЭКСПЕРИМЕНТЫ.

Глава 3.

ДИФФЕРЕНЦИРОВАНИЕ ПО ИТЕРАЦИИ

§3.1. ПОЛУПРОИЗВОДНАЯ И ЕЕ СВОЙСТВА.

§3.2. АНАЛИЗ СХОДИМОСТИ

С ПОМОЩЬЮ ДИФФЕРЕНЦИРОВАНИЯ ПО ИТЕРАЦИИ

Глава 4.

НЕЛИНЕЙНЫЕ УРАВНЕНИЯ

§4.1. СУЩЕСТВОВАНИЕ И ОЦЕНКА РЕШЕНИЯ

НЕЛИНЕЙНОГО УРАВНЕНИЯ.

§4.2. СРАВНЕНИЕ С ИЗВЕСТНЫМИ РЕЗУЛЬТАТАМИ.

§4.3. СХОДИМОСТЬ МЕТОДА НЬЮТОНА.

§4.4. РАСХОДИМОСТЬ МЕТОДА НЬЮТОНА.

Глава 5.

МЕТОД КВАДРАТИЧНОЙ ОПТИМИЗАЦИИ

§5.1. ОПИСАНИЕ МЕТОДА.

§5.2. ЛОКАЛЬНАЯ СХОДИМОСТЬ.

§5.3. ПОЛУГЛОБАЛЬНАЯ СХОДИМОСТЬ.

§5.4. ВЫБОР НАЧАЛЬНОЙ ТОЧКИ.

§5.5. МОДИФИКАЦИИ МЕТОДА

КВАДРАТИЧНОЙ ОПТИМИЗАЦИИ.

Глава 6.

КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ

§6.1. РАЗЛИЧНЫЕ ПОДХОДЫ К ПОСТРОЕНИЮ

КВАДРАТИЧНЫХ ПРОГРАММ-АППРОКСИМАЦИЙ

§6.2. ЛИНЕЙНАЯ ИНТЕРПОЛЯЦИЯ И АППРОКСИМАЦИЯ

§6.3. КВАДРАТИЧНЫЕ АГРЕГАТЫ.

§6.4. ВЫБОР УЗЛОВ ИНТЕРПОЛЯЦИИ.

§6.5. ВЫПУКЛОСТЬ ЛИНЕЙНО-КВАДРАТИЧНОГО АГРЕГАТА

§6.6. АЛГОРИТМ ТРЕХКООРДИНАТНОГО СПУСКА.

§6.7. АЛГОРИТМ ЧАСТИЧНОГО ПРОЕКТИРОВАНИЯ.

§6.8. АЛЬТЕРНАТИВНЫЙ ПОДХОД.

§6.9. МОДИФИКАЦИЯ МЕТОДА БИЛА.

Глава 7.

ДИСКРЕТНЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ

И ПОИСКА ЭКСТРЕМУМА

§7.1. ДИСКРЕТНЫЙ МЕТОД ЧЕБЫШЕВА.

§7.2. МЕТОД МЮЛЛЕРА.

§7.3. ПОИСК ОДНОМЕРНОГО МИНИМУМА

НА ОСНОВЕ n-ТОЧЕЧНОЙ ИНТЕРПОЛЯЦИИ.

§7.4. УЧЕТ ПОГРЕШНОСТЕЙ ИЗМЕРЕНИЙ ПРИ МИНИМИЗАЦИИ

МЕТОДОМ ТРЕХТОЧЕЧНОЙ ИНТЕРПОЛЯЦИИ.

Глава 8.

МИНИМИЗАЦИЯ

НА КОМБИНАТОРНЫХ ПРОСТРАНСТВАХ

§8.1. АЛГОРИТМ СОСТАВЛЕНИЯ РАСПИСАНИЯ

ДЛЯ ОДНОГО СЕМЕЙСТВА ЗАДАЧ ОБСЛУЖИВАНИЯ

§8.2. КОМБИНАЦИОННОЕ ДОЗИРОВАНИЕ.

Глава 9.

МИНИМИЗАЦИЯ СЕПАРАБЕЛЬНЫХ ЦЕЛЕВЫХ ФУНКЦИЙ

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

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

Вводной для глав 5-7 является гл. 1. Основной ее объект — нелинейная программа общего вида: z)—> mm, (0.1) где / — скалярная функция, именуемая целевой, D — именуемое допустимым некоторое множество; во многих важных приложениях оно задается формулой

D := {х\д(х) < 0}; (0.2) здесь х — n-мерный вектор; д — m-мерная вектор-функция. Программа (0.1) является ключевым элементом большинства задач на оптимизацию.

Исходной задачей в гл. 1, 5-7 является нелинейная программа (0.1) с допустимым множеством (0.2), именуемая здесь для краткости задачей А. В основе многих исследований методов нелинейного программирования лежит функция Лагранжа. Для задачи А она задается формулой

F(x,X) := f(x) + Xg(x), где А — m-мерная строка. Поиск у функции Лагранжа седловой точки (х, Д), определяемой неравенствами

F(x,\)>F(X,\)>F(X,\) VA>0, Ухе BP, двойственная задача) здесь — задача В. Связь между решением задачи А и х-составляющей решения задачи В описана в теоремах Куна-Таккера [84]. В случае дифференцируемости функций / и д, как известно, седловая точка необходимо удовлетворяет системе

VxF(x, А) = 0 A V\F(x, А) < 0 A А>0 A №\F(x,\) = 0, (0.3) часто называемой системой Куна-Таккера. Поиск решения системы (0.3) можно рассматривать как самостоятельную задачу, которую далее будем именовать задачей С. Выпуклость функций / и g гарантирует совпадение множества решений задач В и С [79]. Связь между решением задачи А и х-составляющей решения задачи С традиционно устанавливается при помощи посредника — задачи

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

Здесь будет исследована прямая взаимосвязь задач А и С.

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

Пусть существует итеративный процесс вида хк+1 = Л(хк), к = 0,1,., начатый из я0. Может оказаться, что базовый алгоритм Л использует не всю доступную на /г-шаге информацию. Ею может быть, например, оценка текущей погрешности dk, оценка невязки, или часто используемая оценка погрешности последующей итерации через оценку погрешности текущей

4(:rfc) - а|| < с\\хк - а||р, р > 1, Дс = 0,1,2,. (0.4)

Здесь {х1}о° — элементы некоторого банахового пространства, порождаемые базовым алгоритмом Л, а — искомая неподвижная точка этого алгоритма: а = Л{а).

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

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

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

Проведены численные эксперименты с точной релаксацией модифицированного метода Ньютона для скалярного уравнения (§2.9).

При обосновании численных методов (да и, вообще, при формулировании теорем) естественно желание предельно ослабить условия и, тем самым, усилить результат. Так, ограниченность производной, по возможности, заменяется на ее липшицевость. Например, в теореме Канторовича (ТК) о сходимости метода Ньютона ([18], гл.ХУШ, § 1, т. 6) решения уравнения д(х) = 0 присутствует условие вида ||<7"(я)|| < L V х 6 S. Ав теореме Канторовича, приведенной в книге [23] это условие заменяется на липшицевость д' в S.

Одним из ослаблений подобного рода (или иначе расширением класса рассматриваемых функций) является понятие полупроизводной, введенной в §3.1. Оно активно используется в методе дифференцирования по итерации (§3.2). Суть его состоит в параметризации отрезка, соединяющего решение а с текущей итерацией: xk(t) := а + t(xk — а), и исследовании задачи Коши для y{t) :=xk+l{t)-a = A{xk(t))-cr. y = F(y,xk,xk-a), 2/(0) = 0 с переходом к дифференциальному неравенству относительно ||у||. Так как y(l) = xk+1, оценка для ||j/(l)|| позволяет оценить погрешность последующего приближения.

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

6 гл. 4 понятие полупроизводной использовано в выяснении существования и оценивании удаленности решения нелинейного уравнения в банаховом пространстве д{х) = 0. (0.5)

Для отображений д, обладающих липшицевой производной (класс С1'1) был получен результат - теорема 4.1, пересекающийся с известными теоремами Канторовича (ТК), Мысовских [58] (т. 1), Гавурина [7] (т. 1) в тех их частях (соответственно, ЧТК, ЧТМ, ЧТГ), где они касаются существования решения и оценки его удаленности от начального приближения.

Теорема 4.1 является расширением ЧТК на случай, когда известна оценка гм > ||(<7'(я))1||, является усилением ЧТМ в виде ослабления условий и усиления заключения, является усилением ЧТГ в виде ослабления условия.

Для отображения, обладающего полупроизводной (класс П) вначале в теореме 4.2 была получена оценка удаленности, затем найдены достаточные условия сходимости метода Ньютона и оценка скорости сходимости. Эти результаты не вложимы в упомянутые теоремы Канторовича, Мысовских, Гавурина, нет и обратного вложения. Конкретное отображение д, рассматриваемое как элемент из С1'1, может получить согласно этим теоремам гарантии по сходимости метода Ньютона и не получить как элемент из П согласно теоремам, приведенным в гл. 4. Возможно и наоборот. А также возможно получить гарантии при обеих трактовках и не получить ни в одной трактовке.

Большая часть итеративных методов поиска экстремума и решения систем нелинейных уравнений базируется на построении некоторой упрощенной здачи в окрестности итеративной точки. Последующее приближение есть решение этой упрощенной задачи. Наиболее распространенный способ упрощения — линейная экстраполяция (интерполяция) функций исходной задачи. Аппроксимирующая задача имеет тогда вид соответственно линейной программы или линейной системы, решение которых, как правило, несложно в вычислительном аспекте. Однако на шаге итеративного метода требуется рассчитать еще параметры аппроксимации, такие, например, как значения функций и их производных из исходной задачи. И может случиться, что вычислительная стоимость решения аппроксимирующей задачи многократно меньше, чем рассчет параметров. Тогда даже существенное усложнение аппроксимации будет оправдано: лишь бы оно увеличило скорость сходимости, поскольку последнее приводит к уменьшению общего числа шагов, потребных для получения решения заданной точности. Предпосылкой такого усовершенствования служит обладание некоторой информацией о нелинейностях параметров (см. гл. 5,7,9).

Следующей по сложности за линейной, по-видимому, надо признать квадратичную аппроксимацию. Именно она, т.е. квадратичная программа, составляет центральную часть метода квадратичной оптимизации (МКО) для решения задач нелинейного программирования общего вида. На практике этод метод хорошо зарекомендовал себя как составная часть метода последовательной оптимизации движения летательных объектов В.М.Пономарева [64]. Последнее служило, в частности, яркой иллюстрацией того что есть трудоемкость собственно метода на шаге и что есть затраты на вычисление параметров. Решение квадратичной программы образовывало первое, параметры же представляли собой математические ожидания функционалов от решений систем дифференциальных уравнений, описывающих движение летательного аппарата. Отношение первого к второму было ничтожно.

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

Методу квадратичной оптимизации посвящена глава 5. Его назначение — итеративное решение задачи (0.1) + (0.2), т.е. задачи А.

Пусть х есть текущее приближение. Тогда в соответствии с МКО следующее приближение к решению задачи А получается как решение квадратичной программы относительно параметров х: f(x,xk) := Vf(xk)(x - хк) + (х- хкуН(хк){х - хк)/2, д(х,хк) := J(xk){x - хк) + д(хк). f(x,xk)—у min (0.6) д(х,хк)< 0

Здесь Н — гессиан функции /, т.е. матрица из вторых производных J матрица из строк-градиентов Vgi: г = 1, га, т.е. - Ш"

Частные случаи метода квадратичной оптимизации предлагались и исследовались с 60-х годов. Так, для задачи А без ограничений, т.е. при D = i?n были предложены программы, реализующие фактически метод квадратичной оптимизации в чистом виде [96] и его модификацию, когда в качестве функции f(x,xk) берется квадратичный интерполяционный полином, совпадающий в некоторых 1 + n + п(п + 1)/2 точках с исходной целевой функцией / [94]. Дж. Ортега и В. Рейнболд этот частный случай называют методом параболоидов. Как составная часть метода последовательной оптимизации В.М. Пономарева, метод квадратичной оптимизации активно использовался при решении большого числа задач управления летательными объектами и другими системами [65], [66]. В [64] был доказан частный случай сходимости, когда система Куна-Таккера (0.3) эквивалентна своей подсистеме

Vf(x) + \J(x)=0 А Л^(гс) = 0. (0.7)

Тогда метод кваратичной оптимизации для задачи А можно сопоставить решению методом Ньютона некоторой системы нелинейных уравнений, являющихся подмножеством системы (0.3), и воспользоваться известными результатами для метода Ньютона. Однако большое количество конкретных задач (0.1) + (0.2) не обладает эквивалентностью систем (0.7) и (0.3), что делает актуальным теоретическое обоснование сходимости метода квадратичной оптимизации в применении к ним (§5.2), а также исследование критериев остановки итератиного процесса (§5.3) и исследование по выбору начальной точки (§5.4).

В §5.5 исследуются возможности модификации МКО по аналогии с модифицированным методом Ньютона. То есть, как сказываются на сходимости погрешности в вычислениях параметров для квадратичной программы на шаге. А именно, параметров Vf(xk), J(xk), д(хк), Н(хк). Нельзя ли какие-нибудь из них вычислить только в начальной точке и использовать затем вместо текущих значений, например, Н(х°) вместо Н(хк)1 Это дало бы существенное снижение общих вычислительных затрат.

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

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

В гл. 5 использование информации о нелинейном поведении целевой функции ограничилось аппроксимацией ее полиномом второго порядка. Тому было два основания: во-первых, построение многомерной аппроксимации более высокого порядка представляется весьма трудоемкой задачей, и, во-вторых, решать нелинейную программу с целевой функцией в виде полинома, порядка большего двух, значительно труднее в многомерном пространстве, чем квадратичную программу. В одномерном пространстве эти два затруднения существенно слабее, и в гл. 7 исследован ряд способов решения нелинейного уравнения и поиска одномерного экстремума. В §7.1 рассмотрен дискретный аналог метода Чебы-шева [3], [34] решения скалярного уравнения

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

М — величина, связанная с оценками сверху на \f'{x)\ и производную порядка п обратной к / функции), в общем виде достаточно подробно изученное еще = о.

0.8) tk - tk-i ~ - - tk-n - In M

0.9)

A.M. Островским [61] . Здесь не рассматривается общий случай, это позволило привести иные доказательства сходных утверждений, вполне достаточные для обслуживания дискретного метода Чебышева. Исследуется условие на начальные данные, гарантирующие сходимость и высокую скорость сходимости.

На базе §7.1 получены аналогичные результаты для решения (0.8) методом Мюллера (§7.2).

Те же идеи заложены в исследовании поиска одномерного минимума на основе n-точечной интерполяции (§7.3). Близкий метод был предложен Н.Е. Кири-ным и С.И. Веденяпиной [4], однако иной способ замещения узлов интерполяции имел последствием иные оценки скорости сходимости.

После получения обоснований итеративного метода, устойчивость его к ошибкам в исходных данных и к ошибкам округления — главное беспокойство для пользователя. В §7.4 исследуется сходимость метода трехточечной интерполяции (частный случай метода §7.3) при наличии погрешности в измерениях целевой функции [87]. Выясняется, нельзя ли повышением точности вычислений от шага к шагу сохранить тип сходимости.

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

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

В §8.1 исследуются алгоритмы поиска оптимального решения задач на обслуживание сеансов связи следующего вида:

Имеется га заявок на обслуживание. В каждой г-й заявке указывается отрезок времени Т; = [if,if], г = 1,ш, когда она может быть выполнена. Заявки выполняются на фиксированных непересекающихся участках обслуживания hi = \h\, hf\ во время сеанса связи [В, Е] D U"=i hj. На каждом участке hj может быть выполнена только одна заявка из числа тех, для которых hj содержится в некотором Ti . Требуется составить расписание, по которому обслуживается наибольшее число заявок.

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

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

Поскольку процесс идет в реальном времени, быстродействие алгоритма выбора имеет существенное значение. Предложен (см. §8.2) названный здесь пачечным алгоритм порождения комбинаторного пространства, обладающий порядком минимального изменения, как и двоично-отраженный я-разрядный код Грея [70], но, в отличие от последнего, позволяющий вводить отсечения.

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

На первом принципиальном шаге выбирается целевой функционал вида где t — время; Т — длительность срока планирования; Х{ — количественное состояние г-й отрасли; /; — функции вредности, убывающие с ростом ж»; Aj — веса. Фактически xi зависят не от времени, а от объема финансирования щ i-й отрасли: Xi = Х{(щ). Таким образом, задача приобретает вид где щ — возрастающие функции, ^Uj(i) = u(t) V £ € [0, Г], u(t) — заданная функция общего финансирования.

Сама такая постановка задачи является проблемой: каким должны быть fi и Aj, чтобы минимайзер для (0.11) воспринимался как оптимальное финансирование? То есть по сути: как добиться адекватности математической модели реалиям жизни? Даже при самом тщательном выборе /i,.,/n, но при Aj = . = А„ = 1 может случиться, что минимайзер для (0.11) вызовет недоумение заказчика. Здесь на помощь приходят веса. Закзчику предлагается количественно их оценить пропорционально важности отраслей. После чего находится новый минимайзер для новых весов. Эту процедуру можно повторять до получения приемлемого результата. Проблема адекватности кажется исчезнувшей, на самом деле всего лишь переместившись в адекватность выражения важности в виде некоторого числа.

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

Эта обратная экономическая задача исследована для частного случая. Как приемлемый был взят опорный план — равномерное сокращение дефицита по отраслям, а в качестве целевой функции — функционал вида (0.10) с Д,., /п, равными квадратам текущих относительных дефицитов, и линейной зависимостью Xi(y) = Xio + СгЩ. Оказалось (т. 9.3), что вектор параметров А, обеспечивающий совпадение опорного плана и минимайзера для (0.10) существует и единствен.

Наряду с обратной экономической задачей исследуется и прямая. Т.е. веса Ai,.,An фиксируются и, соответственно, вводятся в (сливаются с) Д,.,/п

0.10)

0.11)

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

Об обозначениях. Буква Т в верхнем индексе будет означать операцию транспонирования. Знак V — операция нахождения градиента, сам градиент будет пониматься как строка. Слева от знака ":=" находится обозначение того, что стоит справа от него. Справа от знака "=:" находится обозначение того, что стоит слева от него. В конце некоторых логических частей стоит знак ■ . Индекс итерации для векторных величин — верхний.

ЗАКЛЮЧЕНИЕ

Взаимосвязь между решениями трех задач: нелинейной программой (А), поиском седловой точки функции Лагранжа (В), решением системы Куна-Таккера (С) традиционно формулируется в виде четырех теорем Куна-Таккера А—>В, В-*А, А-+С, С-*А. Кроме безусловной теоремы из В в А, (^-составляющая решения задачи В всегда есть решение задачи А) каждая из трех остальных имеет необходимый характер условий в том смысле, что для любого изъятия или ослабления какого либо условия можно привести контрпример, для которого утверждение соответствующей теоремы неверно, т.е. теоремы не могут быть усилены. Посредством суперпозиций двух пар этих теорем можно установить связи А—>С и С->А, причем каждая будет содержать требование выпуклости целевой функции f(x) и функций-ограничений д(х).

В гл. 1 получено более сильное утверждение: ^-составляющая решения системы Куна-Таккера является решением задачи А всего лишь при требовании слабой унимодальности fag, непрерывности / и отличия от нуля градиента / в х-составляющей решения задачи С. Показана невозможность ослабления этих требований (теорема 1.5 и контрпримеры к ней). Введенное здесь понятие слабой унимодальности трактуется как не убывание функции при удалении от ее множества минимальных значений вдоль любого луча. Получены альтернативные формулировки без требования непрерывности (теоремы 1.5' и 1.5").

Для обратной связи от решения задачи А к решению задачи С получены результаты также без требования выпуклости. В теореме 1.7 требуется всего лишь слабая унимодальность и непрерывность д вместо выпуклости fug. Теорема 1.6 вместо условия Слейтера и выпуклости / и д имеет лишь требование существования х* такого, что Vgi(x)(x* — х) < 0 для всех г, соответствующих существенным ограничениям: gi(x) = 0.

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

ПМ был применен к итеративным одноточечным методам, в которых последующие приближения порождаются алгоритмом Л: хк+1 = Л(хк), а в качестве дополнительной информации имелась оценка погрешности последующего приближения вида

4(z*+1)-a|| <ф*-а||р, р > 1, fc = 0,1,2,., где {я*}о° — элементы некоторого вещественного евклидова или гильбертова пространства, х° — начальное приближение, а — неподвижная точка исходного алгоритма: а = Л(а), с — положительная константа (если р = 1, то с € (0,1).

На основе ПМ получена модификация алгоритма а, названная точной релаксацией. В ней вместо итеративной последовательности {я*}о° предлагается строить последовательность элементов и последовательность чисел — оценок погрешностей — таких, что у0 = х°, do — каким то образом полученная оценка погрешности начального приближения, а остальные приближения и оценки погрешностей порождаются расчетными формулами вида ук + р (dk, Л(у*), с) - у"), dk+1 = A(dk, у\ с), где коэффициент релаксации р(-, •, •) определен из ПМ т.е так, чтобы погрешность <4+i для итерации ук+1 была минимальной при знании только значений 4-х его аргументов. Вычислительная стоимость расчетных формул коэффициента точной релаксации и оценки погрешности невелика: скалярное произведение элементов исходного пространства, два сложения в нем и от 3 до 8 арифметических операций. Выгода модификации проявляется в повышении скорости сходимости к нулю оценок погрешности {dk} в сравнении со скоростью убывания оценок погрешности {dk} итераций базового алгоритма. (При р = 1 справедливо dk = c^cfo, где d0 - априори известная оценка начального приближения.) Для модификации всегда dk+i < cdk. На некоторых шагах, вообще говоря, возможно dk+1 = cdk, но вероятность этого, в предположении равномерного распределения решения в шаре радиуса dk, соответствует приблизительно отношению меры машинного представления сферы радиуса d^V 1 — с2 к мере машинного представления шара радиуса dk, что даже для двумерного пространства и используемых в настоящее время ЭВМ есть ничтожная величина. В большинстве остальных случаев модификация обеспечивает меньшую оценку погрешности последующей итерации. В одномерном случае всегда справедлива с более сильная оценка dk+i < --dk.

1 + с

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

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

С помощью понятия полупроизводной получена теорема 4.1, которая в части оценки удаленности решения от заданной точки является расширением теоремы Канторовича ([18], гл.XVIII, § 1, т. 6) о сходимости метода Ньютона для уравнения д(х) = 0 на случай, когда известна оценка гм> ||(р'(ж))-1||. В сравнении с теоремой Мысовских ([58], т. 1) условия теоремы 4.1 слабее, а оценка удаленности всегда меньше. Используемая в теореме 4.1 оценка r0 > ИО/'Ос))-1!! допускает огрубление до гм, и тогда условия теоремы 4.1 содержатся в условиях теоремы Гавурина ([7], т. 1), а оценки удаленности совпадают. Т.е. теорема 4.1 является усилением теоремы Гавурина в части оценки удаленности корня, ибо в ней требуется лишь локальная липшицевость д' вместо более сильного условия локальной ограниченности производной Гато от д' в теореме Гавурина. Когда го < ги, Т. 4.1 является расширением теоремы Гавурина и дает лучшую оценку удаленности.

При существенно иных предположениях, чем в теоремах Канторовича, Мы-совских, Гавурина и 4.1, об отображении д получена теорема 4.2 об оценке удаленности решения от заданной точки. Для одних значений характерных параметров лучшую оценку предоставит теорема 4.2, для других — 4.1 (оценка из последней не хуже, чем в теоремах Канторовича, Мысовских, Гавурина). Суждения теорем 4.1 и 4.2 относятся к разным классам отображений: П и С1,1 (см. опред. 4.1, 4.2). В классе П с помощью дифференцирования по итерации получены результаты о сходимости метода Ньютона, не содержимые в полученных для класса С1'1 теоремах Канторовича, Мысовских, Гавурина и не объемлющие их.

Дифференцирование по итерации также было основным инструментом обоснования метода квадратичной оптимизации (МКО). МКО, т.е. итеративное решение нелинейной программы f{x) —> min при ограничениях д(х) < О посредством решения аппроксимирующих квадратичных программ на итерациях, описан довольно давно. Однако в общем случае, несмотря на великолепные практические результаты для некоторых классов задач, теоретического обоснования метода не было. В гл. 5 выяснено при каких условиях можно гарантировать сходимость, оценена скорость сходимости, погрешность по двум последовательным итерациям и удаленность решения от начальной точки.

Усиление результата автора в [28] было достигнуто в §5.2 в виде утверждения о сходимости метода к а — решению задачи А — из любой точки в окрестности а. Размеры окрестности являются некоторой функцией "естественных" ограничений: на скорость изменения производных функций-ограничений и элементов гессиана, а также на "сплющенность" системы градиентов функций-ограничений.

В §5.3 приведен критерий остановки итеративного процесса. Он позволяет оценить удаленность решения от текущей итерации по известному расстоянию до предыдущей итерации и тем же "естественным" [30] ограничениям. В §5.4 по константам задачи и значениям параметров задачи А в точке определяется корректность выбора этой точки в качестве начальной для МКО.

В §5.5 показано, что сходимость МКО можно сохранить и при приближенных вычислениях итерационных параметров. При этом функции V/(xk), J(xk), д(хк) должны вычисляться с возрастающей точностью, иначе сходимость не гарантирована. Гессиан же целевой функции может быть вычислен лишь в начальной точке, но это будет стоить сужения множества, на котором гарантирована сходимость. В конкретных приложениях [67], [30]. погрешности в вычислениях гессиана практически не сказывались на скорости сходимости, и, поскольку вычислительные затраты на итерацию существенно снижались в сравнении с немодифицированным МКО, общие вычислительные расходы на достижение желаемой точности были заметно ниже.

Очень тесно к МКО примыкают способы построения аппроксимаций нелинейных программ на итерации. Этот вопрос рассмотрен в гл. б. В §6.1 исследована проблема выбора узлов для построения линейной по параметрам аппроксимации. Как выяснилось (т. 6.5), для успешного построения этой аппроксимации достаточно включить в состав узлов такой набор, что задача линейной интерполяции на нем всегда имеет единственное решение. Бели аппроксимирующий агрегат линеен по аргументам, то таким набором, как известно, является набор узлов в общем положении. Если аппроксимирующий агрегат квадратичен по аргументам, то как для вещественного случая, так и для комплексного найдены алгоритмы порождения узлов, обеспечивающие существование и единственность решения задачи аппроксимации, и попутного отыскания параметров аппроксимирующего агрегата.

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

Важное место в МКО занимает процедура решения квадратичной программы. Исследована модификация метода Била (§6.9), позволяющая за конечное число шагов найти решение. Собственно метод Била преобразован в матричную форму, удобную для программирования на ЭВМ. Поиск допустимой начальной точки реализован в виде алгоритма с большим количеством общих с методом Била операторов, что позволяет создавать компактные программы. Модификация позволяет решать квадратичные программы с вырожденной матрицей квадратичной формы, а также воспринимать часть переменных ограниченными по знаку, а часть - нет. Создан простой алгоритм предотвращения зацикливания, при его использовании доказана конечность числа итераций, необходимых для достижения конечного или бесконечного решения или установления факта отсутствия решения.

Идее повышения эффективности вычислительного итеративного процесса служат и другие методы высоких порядков. К ним можно отности, как метод Чебышева решения скалярного уравнения f(x) = 0, так и его дискретный аналог, использующий обратную интерполяцию. В гл. 7 получена оценка скорости сходимости дискретного метода Чебышева неравенством вида хк-х\ < tie"cA*<n> , (*) где положительные и, с - константы, зависящие от начальных данных, a Ai (п) - наибольший корень характеристического полинома tn — tn~l -. — 1 = 0. Доказано

2 > Ai(n) > 2п/(п + 1)

Аналогичные оценки получены для метода Мюллера решения уравнения f(x) = 0 (прямая интерполяция по трем узлам на каждой итерации).

Поиск одномерного безусловного минимума при помощи п-точечной прямой интерполяции на каждой итерации имеет, как оказалось (гл. 7), аналогичную (*) оценку скорости сходимости, только вместо Ai(n) там следует поставить i/i (п) - наибольший положительный корень полинома tn — tn~2 — . — 1 = 0. Доказано п + V5n2 - 4)/(2п + 2) < i/i (n) < (1 + л/5)/2.

Поскольку 0 < 2 - Ai(n) < 0.01 при п > 7 и при п > 8 справедливо 0 < (1 + л/5)/2 — i/i (п) < 0.017, использование большого количества узлов в дискретном методе Чебышева и методе минимизации при помощи п-точечной интерполяции нецелесообразно.

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

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

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

Для задач составления расписания сеансов связи был предложен алгоритм, жадный по концу заявок. Он показал высокую эффективность решения этих задач при численной реализации. Причем для задачи 1 из §8.1, он был не хуже по быстродействию алгоритма решения транспортной задачи, к которой она может быть приведена [73], а для задачи 2 поиск конкурентов алгоритму, жадному по концу заявок, пока остался безуспешен.

Оптимизацию распределения капиталовложений часто сводят к минимизации функционала вида = jf Е ШФ))*г с ограничениями вида Yl£i(t) = u(t), щ > 0, неизвестными здесь являются функции Xi(-), .,£„(•); Ах,., Ап — веса; функция и возрастает.

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

В гл. 9 при конкретных {fi} получены формулы для весов {Ai}, обеспечивающие совпадение опорного плана и минимайзера функционала Ф. Подобный подход помогает выяснять связь между приоритетностью отрасли и численными значениями весов.

В гл. 9 предложен алгоритм генерации минимайзера функционала весьма общего вида: с ограничениями вида £ «»(£)= u(t) и щ Неизвестными здесь являются отраслевые планы ui(-),.,un(-). Функции {/,•} предполагаются имеющими кусочно непрерывную вторую производную.

Вначале доказана оптимальность результата, выдаваемого этим алгоритмом, для случая u(t) = t (т. 9.6). Затем — оптимальность планов, когда и — произвольная возрастающая функция с разрывами.

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

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

3. Бахвалов Н. С., Жидков Н. П., Кобельков Г. Н. Численные методы. М., 1987. 598 с.

4. Веденялина С. И., Кирин Н.Е. Интерполяционный метод высокого порядка одномерного поиска минимума // Динамика систем и управление. Саранск, 1986. С. 69-75.

5. Васильев Ф. П., Иваницкий А. Ю. Линейное программирование. М., 1998. 176 с.

6. Воеводин В. В. Вычислительные основы линейной алгебры. М., 1977. 552 с.

7. Гавурин М. К. Нелинейные функциональные уравнения и непрерывные аналоги итерационных методов // Изв. ВУЗов, 1956. № 5 (6). С. 18-31.

8. Гантмахер Ф. Р. Теория матриц. М., 1988. 552 с.

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

10. Гельфанд И.М. Лекции по линейной алгебре. М., 1971. 272 с.

11. Гилл Ф., Мюррей У. Численные методы условной оптимизации. М., 1977. 290 с.

12. Далецкий Ю.Г., Крейн М.Г. Устойчивость решений дифференциальных уравнений в банаховом пространстве. М., 1970, 534 с.

13. Даугавет В.А. Метод дополнительного базиса в квадратичном программировании // Вестн. Ленингр. ун-та. 1992. Сер. 1, вып. 3. С. 31-38.

14. Дуткевич Ю.Г., Петросян JI. А. Игра с "линией жизни". Случай 1г захвата // Вестн. Ленингр. ун-та, 1969.№ 13. С. 31-38.

15. Дэннис Дж., Шнабель Р. Численные методы безусловной оптимизации и решения нелинейных уравнений. М., 1988. 440 с.

16. Зубов В. И., Петросян JI. А., Мейлахс А. М., Михеев С. Е. Отчет по теме: "Задача оптимального распределения капиталовложений". JL, 1971. 21 с.

17. Камачкин A.M., Михеев С.Б., Евстафьева В.В. Модели колебаний в нелинейных системах. СПб.: изд. СПбГУ, 2004. 194 с.

18. Канторович JI. В., Акилов Г. П. Функционльный анализ. М., 1977. 744 с.

19. Карлин С., Стадден В. Чебышевские системы и их применение в анализе и статистике. М., 1976. 568 с.

20. Картан А. Дифференциальное исчисление, дифференциальные формы. -М., 1971. 392 с.

21. Кирин Н. Е., Сеисов Ю.Б. Оптимизация процессов в управляемых системах. Ашхабад, 1991. 264 с.

22. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. М., 1972. 496 с.

23. Красносельский М.А. и др. Приближенное решение операторных уравнений. М., 1969. 455 с.

24. Красовский Н. Н. Игровые задачи о встрече. М., 1970. 420 с.

25. Кюнци Г., Крелле В. Нелинейное программирование. М., 1965. 304 с.

26. Липский В. Комбинаторика для программистов. М., 1988. 213 с.

27. Лорин Г. Сортировка и системы сортировки. М., 1983. 384 с.

28. Михеев С. Е. О сходимости метода последовательной оптимизации // Математическая физика. 1976. № 20. С. 52-58.

29. Михеев С. Е. Расширение теоремы Куна-Таккера на унимодальные функции // Математическая физика. 1977. № 21. С. 43-44.

30. Михеев С. Е. Вычислительные аспекты метода последовательной оптимизации // Вопросы механики и процессов управления. JL: изд. Ленингр.-унт., 1980. Вып. 4. С. 223-242.

31. Михеев С. Е. Одна задача распределения ресурсов и минимизация сепа-рабельных целевых функций // Вопросы механики и процессов управления. Л.: изд. Ленингр.-унт., 1980. Вып. 4. С. 169-179.

32. Михеев С. Е., Каменев В. В. О формировании пространственной волны в популяции амброзиевого листоеда // Вопросы механики и процессов управления. СПб.: изд. СПбГУ, 1989. Вып. 12. С. 52-63.

33. Михеев С. Е. Сходимость дискретного метода Чебышева и метода Мюллера // Вопросы механики и процессов управления. СПб.: изд. СПбГУ, 1992. Вып. 15. С. 89-99.

34. Михеев С. Е. Методы высоких порядков в задачах нелинейного программирования и решения уравнений. СПб.: изд. СПбГУ, 1992. 95 с.

35. Михеев С. Е., Томина О. Н. Алгоритмы решения одного семейства задач обслуживания // Дифференциальные уравнения с частными производными (общая теория и приложения). СПб, 1992. С. 93-100.

36. Михеев С.Е., Силина Е.К. Одна модель колебательного движения // Вестник С.-Петербург, ун-та. 1994. Сер. 1, вып. 1 (№ 1). С. 72-76.

37. Михеев С. Е., Никольский А. М. Метод спуска в задачах аппроксимации // Процессы управления и устойчивость: Труды XXX научн. конф. -СПб., 1999. С. 119-125.

38. Михеев С. Е. Релаксационное ускорение. ВИНИТИ № 2089-В98,3.6.1998. 11 с.

39. Михеев С. Е. Зависимость конкурентоспособности труда от уровня акцизных налогов. ВИНИТИ №3012-В98,16.10.1998. 19 с.

40. Михеев С.Е. Выпуклая квадратичная интерполяция // Вестник С.Петербург. ун-та. 1999. Сер. 1, вып. 2 (№ 8). С. 42-48.

41. Михеев С. Е. Релаксационное ускорение на основе областей достижимости // Вестник С.-Петербург, ун-та. 1999. Сер. 1, вып. 3 (№ 15). С. 29-35.

42. Михеев С. Е. Управление конкурентоспособностью. СПб.: изд. СПбГУ, 2001. 36 с.

43. Михеев С.Е. Нелинейные методы в оптимизации. СПб.: изд. СПбГУ, 2001. 276 с.

44. Михеев С.Е. Эффективность релаксационного ускорения // Николай Ефимович Кирин (сборник статей). СПб., 2003. С. 183-197.

45. Михеев С.Е. Зоны безопасности в играх с линией жизни // Вестник С.-Петербург, ун-та. 2003. Сер. 1, вып. 3 (№ 17). С. 69-78.

46. Михеев С. Е. Комбиниационное дозирование // Вопросы механики и процессов управления. СПб.: изд. СПбГУ, 2003. № 19. С. 271-277.

47. Михеев С. Е. Метод трехкоординатного спуска // Вопросы механики и процессов управления. СПб.: изд. СПбГУ, 2004. № 21. С. 128-136.

48. Михеев С. Е. Выпуклая квадратичная аппроксимация // Вычислительные технологии. Новосибирск, 2004. Т.9, №4. С. 66-76.

49. Михеев С. Е. Спуск по базисным направлениям с ограничением // Вопросы механики и процессов управления. СПб.: изд. СПбГУ, 2004. № 22. С. 116-126.

50. Михеев С. Е. Конкурентоспособность и трудоемкость // Вопросы механики и процессов управления. СПб.: изд. СПбГУ, 2004. № 23. С. 118-141.

51. Михеев С. Е. Сходимость метода Ньютона на различных классах функций // Вычислительные технологии. Новосибирск, 2005. Т.10, №3. С. 72-86.

52. Михеев С. Е., Позняк JI.E. Улучшение оценок в одной теореме Мысовских о методе Ньютона // Труды международной конференции "Устойчивость и процессы управления". СПб, 2005. Т. 2. С. 876-885.

53. Михеев С. Е. Существование и опенка решения нелинейного уравнения в банаховом пространстве // Вестник С.-Петербург, ун-та. 2005. Сер. 10, вып. 3. С. 13-27.

54. Михеев В. С., Михеев С. Е. Точная релаксация модифицированного метода Ньютона // Процессы управления и устойчивость: Труды XXXVII международной научн. конф. СПб., 2006. С. 119-125.

55. Михеев С. Е., Позняк JI.T. Одна новая теорема существования решения нелинейного уравнения в банаховых пространствах // Вестник С.Петербург. ун-та. 2006. Сер. 10, вып. 3. С. 35-43.

56. Мухачева Э. А., Рубинштейн Г. Ш. Математическое программирование. Новосибирск, 1987. 274 с.

57. Мысовских И.П. К вопросу о сходимости метода Ньютона. // Труды Матем. ин-та им. Стеклова. 1949. №28. С. 145-147.

58. Мысовских И.П. О сходимости метода JI.B. Канторовича решения функциональных уравнений и его применениях // Докл. АН СССР 70. 1950. №4. С. 565-568.

59. Никольский С. М. Курс математического анализа. М., 1973. Т. 1. 432с.

60. Ортега Дж., Рейнболдт В. Итерационные методы решения нелинейных систем уравнений со многими неизвестными. М., 1975. 558 с.

61. Островский А. М. Решение уравнений и систем уравнений. М., 1963. 220 с.

62. Панин В. М. Нормализованный метод конечных штрафов в задаче нелинейного программирования // Докл. АН СССР. Сер. мат. 1989. Т.304, №3. С. 549-552.

63. Петросян JI. А. Игры преследования с "линией жизни" // Вестн. Ленингр. ун-та. 1967. №13. С. 76-86.

64. Пономарев В.М., Горичев Ю.В., Городецкий В. И. Последовательная оптимизация нелинейного закона управления // Нелинейная оптимизация систем автоматического управления / Под ред. В. М. Пономарева. -М., 1970. С. 15-19.

65. Пономарев В. М., Литвинов Л. П. Основы автоматического регулирования и управления. М., 1974. 439 с.

66. Поцелуев А. В., Майборода JI. А., Пономарев В. М. и др. Статистический анализ и оптимизация следящих систем. М., 1977. 360 с.

67. Пшеничный Б. Н., Данилин Ю. М. Численные методы в экстремальных задачах. М., 1975. 319 с.

68. Пшеничный Б. Н. Метод линеаризации. М., 1983.

69. Пшеничный Б. Н., Панин В. М. Линейная сходимость методов линеаризации. // Докл. АН СССР. Сер. А. 1987. №4. С. 16-18.

70. Рейнгольд Э., Нивергельд Ю., Део Н. Комбинаторные алгоритмы. М., 1971. 476 с.

71. Розенвассер Е. Н., Юсупов Р. М. Чувствительность систем автоматического управления. М., 1981. 464 с.

72. Рокафеллар Р. Т. Выпуклый анализ. М., 1973. 469 с.

73. Танаев В. С., Шкурба В. В. Введение в теорию расписаний. М., 1975. 256 с.

74. Титчмарш Е. Теория функций. М., 1982. 463 с.

75. Уилкинсон Дж. X. Алгебраическая проблема собственных значений. -М., 1970. 564 с.

76. Ульман Дж. Основы систем баз данных. М., 1983. 334 с.

77. Фаддеев Д. К., Фаддеева В. Н. Вычислительные методы линейной алгебры. М., 1960. 656 с.

78. Хартман Ф. Обыкновенные дифференциальные уравнения. М.: Мир, 1970, 720 с.

79. Хедли Дж. Нелинейное и динамическое программирование. М., 1967. 506 с.

80. Хейгеман JL, Янг Д. Прикладные итерационные методы. М., 1986. 446 с.

81. Химмельблау Д. Прикладное нелинейное программирование. М., 1975. 534 с.

82. Хлямков А. В. Замечание о сходимости метода парабол // Матем. заметки. 1998. Т. 63, вып. 2. С. 309.

83. Шилов Г.Е. Математический анализ: Специальный курс. М., 1961. 436 с.

84. Эрроу К.Дж., Гурвиц JL, Удзава X. Исследования по линейному и нелинейному программированию. М., 1962. 334 с.

85. Юдин Д. В., Голынтейн Е. Г. Линейное программирование. М., 1963. 424 с.

86. Miheev S. E. Stability zones in rhesus-systems // Abstracts of Invited Lectures к Short Comm. Delivered at the Second International Colloquium on Differential Equations, Bulgaria, 1991. P. 191.

87. Miheev S.E., Kokina V. G. Measurement errors control in the 3-points interpolation method // Intern. Congr. on Computer Systems and Applied Math. St.Petersburg, 1993. P. 272.

88. Miheev S.E. A non Linear Differential Model of Sheduling // Proc. ICI&C97 (Intern. Conf. Inform. Control). St .Petersburg, Russia, 1997. P. 835840.

89. Miheev S.E. Contraction of attainability domains in a game of pursuit // Game Theory and Applications / Eds. L. Petrosjan, V. Mazalov. Nova Science Pbl., N.Y. 1996. Vol. 2, P. 193-207.

90. Miheev S. E. Contraction of Attainability Domains in a Game of Pursuit. Nova J. Mathematics: Game Theory and Algebra. Nova Science Publ., N.Y. 1997. Vol.6, № 2/3. P. 147-161.

91. Miheev S.E. Relaxation Acceleration in Iterative Methods // Proceedings volume from the 11th IFAC Workshop "Control Applications of Optimization 2000". 2000. Vol. 1. P. 243-248.

92. Miheev S. E. Tax system & and interest to new industrial capacities // Труды Международной конференции "Математическое моделирование социальной и экономической динамики" (MMSED-2004). М., 2004. стр. 212216.

93. Rothnie J.B., Lozano Т. Attribute based life organization in a paged memory environment // Comm. ACM. 1974. Vol. 17:2. P. 63-69.

94. Schmidt J., Trinkaus H. Extremwetermittlung mit Funktionswerten von mehreren Veranderlichen // Computing. 1966. Bd. 1. S. 224-232.

95. Schwetlick H. Numerische Loesung nichtlinearer Gleichungen. Berlin, 1979, 346 S.

96. Spath H. The damped Taylor's series method for minimizing a sum of squares and for solving systems of nonlinear equations // Comm. ACM. 1967. Vol. 10. P. 726-728.