автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Задача оптимального управления внешним долгом

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

ГГБ ОД

СИНЯГИН Станислав Юрьевич ~ 5 ИЮ/Т 2000

ЗАДАЧА ОПТИМАЛЬНОГО УПРАВЛЕНИЯ ВНЕШНИМ ДОЛГОМ

Специальность: 05.13.18. Теоретические основы математического моделирования, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Долгопрудный 2000

Работа выполнена на кафедре управления и вычислительных систем Московского Физико-Технического института (государственного университета).

Научные руководители: доктор физ.-мат. наук, профессор кандидат физ.-мат. наук, доцент

Дикусар В. В. Шахнов И. Ф.

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

доктор физ.-мат. наук, профессор Афанасьев А. П.

кандидат физ.-мат. наук, доцент Волков Ю. Н.

Ведущая организация:

Центральный Экономико-Математический Институт РАН

Защита состоится "£3_" ЬлЮ^ 2000г. в на заседании

диссертационного совета К 063.91.03 при МФТИ в Московском

физико-техническом институте (государственном университете)

по адресу: 141700, г. Долгопрудный, Моск. обл., Институтский пер., д. 9.

С диссертацией можно ознакомиться в библиотеке МФТИ.

Автореферат разослан " ^ " ^-'М 2000г.

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

кандидат физ.-мат. наук ¿ГГ-^г—2—^Т7 Федько О. С.

ЦЛш,0

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

Актуальность темы. Государственный долг России составляет порядка 1000 долларов США на душу населения [1]. Величина долга Москвы равна примерно 380 долларов США на душу населения, если не считать унаследованный Россией советский долг. С другой стороны, западные страны должны России порядка 300 миллиардов долларов США, на считая вывоза капитала за рубеж. Кроме того, России должны бывшие социалистические страны, развивающиеся страны и страны СНГ. Общая сумма их долга России составляет 2172205 миллионов рублей (76 миллиардов долларов США). Отсюда видна сложность рассматриваемой проблемы. Дикусар В.В. и Абрамов А.П. предложили модель динамики выплаты внешнего долга на базе двусекторной модели (сырьевой и производственный секторы). Рассматриваемая модель сводится к задаче оптимального управления при наличии фазовых и смешанных ограничений типа равенств и неравенств. Единственным инструментом для качественного анализа таких задач являются принцип максимума Л.С. Понтря-гина и схема Дубовицкого-Милютина. Однако при применении указанного математического аппарата возникают принципиальные трудности. Они связаны с неединственностью множителей Лагранжа и определением геометрии оптимальной траектории (множества активных индексов). Известно, что необходимые условия экстремума приводят к краевой задаче. Здесь также возникают определенные трудности при численном решении упомянутой задачи. Отсюда следует важность рассмотрения задач с фазовыми и смешанными ограничениями в практическом и методическом аспектах.

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

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

Методы исследования. Используются методы решения линейных алгебраических систем, методы продолжения решений по параметру, метод Ньютона, методы Рунге-Кутта, полиномы Лагранжа и Чебышева, программный комплекс "Баланс-2" (Умнов А.Е., Шомполов И.Г.).

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

1. Сформулированы и доказаны теоремы о продолжении решений по параметру.

2. Предложена система моделей, зависящая от параметров. Это позволяет получить точное решение задачи Понтрягина Л.С. для случая свободного правого конца. Указанное решение является первым приближением при решении краевой задачи.

3. Получена алгоритмическая оценка решения плохо обусловленной линейной системы.

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

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

Апробация результатов работы. Основные результаты диссертационной работы докладывались и обсуждались на научной конференции Московского физико-технического института (Долгопрудный, 1998), на семинарах Института Системного Анализа РАН, ВЦ РАН, ЦЭМИ РАН, Института Проблем Управления РАН.

Публикации. По теме диссертации опубликовано три печатные работы.

Структура и объем работы. Диссертация состоит из введения и четырех глав, изложенных на 132 страницах, содержит 4 таблицы, 15 рисунков, список литературы, приложения.

Краткий обзор работы.

В Главе I диссертации на основе двусекторной модели внешнего долга [2] рассматривается задача минимизации внешнего долга на одного работника. Необходимо заметить, что исследование задачи проводится в условиях отсутствия достаточно полной информации о качественных свойствах и количественных характеристиках объекта моделирования. Известен только внешний долг на одного работающего и условия обслуживания внешнего долга.

Классическая методология математического моделирования основные усилия направляла на повышение уровня адекватности моделей, т.е. степень их соответствия объекту моделирования [3].

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

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

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

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

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

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

При выполнении необходимых условий в неполной модели ищется допустимое решение.

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

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

Процесс пополнения фактически является процедурой выделения конуса достижимых состояний (Умнов) [3], (Моисеев) [4], (Разумихин) [5].

В схемах неполного моделирования [3] используются кусочно-линейные аппроксимации для всей совокупности состояний математической модели.

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

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

Умнов А. Е. в своей работе [6] ввел понятие специального математического объекта, именуемого компактным образом неполной модели. Схема, использующая этот объект, позволяет преодолевать все упомянутые трудности. Компактный образ по определению [6] включает результат некоторого отображения множества условно допустимых состояний неполной модели и систему вычислительных процедур для построения этого отображения.

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

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

р(Г,Е0) = тах{шахттр(х,у),тахттр(а;,?/)},

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

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

измерения расстояния между множествами равноправны.

В диссертации динамика внешнего долга описывается системой уравнений [2]

¿1 = ~(1хХ1 + Щ + 42, хх(0) = х10, хх(т) = Х\\,

¿2 = ~(12Х2 + из + "4, £2(0) = х20, Х2{Т) = х12, (1)

¿3 = А13х3 + щ + и3 + и5 - х3(0) = х30, Ь £ [0, Т],

X = (хх, х2, х3), и = (их, и2, и3, и4, иь).

Здесь х - фазовый вектор, и - управляющая вектор функция, цх, (12, /¿з, V - константы, е(£) - заданная функция.

Кроме уравнения (1), заданы уравнения баланса для двух секторов (сырьевой и производственный секторы)

/1(2:1) = е(<) + «1/1 (хх) + а2/2{х2), .у.

/2(х2) = и2 + щ +с2(£),

гДе /1(2:1), /2(2:2) _ заданные функции (производительности) в соответствующих секторах, е(£) - поток экспорта первого сектора, с2(£) - заданное неинвестиционное потребление.

На управляющие функции и;(£), г = 1,5 положены ограничения

0 < и,-(<) < ил, г = 1,5 (3)

и5(*)+<*(«) >стш, ¿е[0,Т]. (4)

Ограничение (4) означает, что поток потребления не может быть меньше некоторого минимального значения. Фазовые ограничения имеют вид

0 < хх(£), х2тш < х2(£), 0 < х3(*) < х3тах. (5)

Смысл второго ограничения (5) означает, что фондовооруженность производственного сектора не должна падать ниже некоторого критического уровня. Третье ограничение (5) задает уровень внешнего долга, превышение которого может привести к финансовому банкротству.

Поясним смысл управляющих функций: щ(<) - поток внешних инвестиций в 1-й сектор; и^Ь) - поток фондообразующей продукции из второго сектора в первый; - поток внешних инвестиций во второй сектор;

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

Рассматривается задача А2 о минимизации внешнего долга

при наличии ограничений (1) - (5).

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

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

Задача Ах. Найти ттжз(Т) при условиях (1) - (5), если

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

Наиболее просто это можно сделать в задаче А0.

Задача Ао- Требуется определить тта^Т) при условиях (1) - (8), если цг — Ц2 = ^з = 0.

В задаче Ао сначала решается задача Понтрягина Л.С. [7]. Для этой цели предполагается выполнение условий (3), (4) и первое равенство (2) с учетом (7) подставляется в дифференциальное уравнение (1), т.е.

х3 (Т) -»• гшп

(6)

ЛЫ = АяхЮ, о < ¡п(4) < 01, ах е я1,

/2(^2) = /32*2(*)> ®2тт < Ы*) ^ а2> а2 € В1.

(7)

(8)

е(г) = (1 - «0/1(2:1) - »2/2(2:2), 7

а второе равенство (2) заменяется неравенством

и2+Щ < - <*(*). (9)

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

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

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

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

тивных индексов для ограничений типа неравенств.

В работе для предварительной оценки геометрии использовалась дискретная схема явного метода Эйлера для системы (1). В результате получается задача линейного программирования (ЛП) большой размерности. Для решения задачи ЛП был использован пакет оптимизационных программ "Баланс-2". Он включает прямой симплекс-метод. Блок-схема алгоритма предложена Кимом К.В. (ЦЭМИ РАН - НАБА, 1985 г.). Программная реализация пакета выполнена в НПО "Научный центр" (МЭП СССР) совместно с кафедрой высшей математики МФТИ в 1990 г. (Ум-нов А.Е., Шомполов И.Г.) [10].

Входной файл данных пакета "Баланс-2" формировался на "Языке генерации линейных моделей Ь". Язык разработан Коротких М.П. (ЗАО "Информационные технологии", 1992 г.). Он представляет собой модифицированное подмножество языка "Си++".

Обработка выходных файлов системы "Баланс-2" проводилась средствами системы программ "МБ Ехе1 95".

Пакет "Баланс-2" использовался также для оценки геометрии смешанных ограничений типа (9), а также в задаче Понтрягина с фиксированным правым концом (задача Ао).

Для решения задачи А1 использовались результаты задачи Ао в качестве первого приближения. Указанное решение получалось методом продолжения решений по параметру а 6 [0,1]:

¿1 = —ац\Х1 + щ+и2

¿2 = —а(12Х2 + из + Щ (10)

¿з = + их + и3 + и5 - уе{£)

При а = 0 задача А1 эквивалентна задаче Ао- Далее выполняется продолжение решений по параметру а вплоть до а = 1.

Решение задачи А1 используется для решения задачи А2 методом

введения параметра ¡3 € [0,1] в систему (2):

е(4) = /3(1 - «ОД(ц) + /?а2/2(х2)+

+(1 - £)(1 - аОА®^) + (1 - /3)а2/32х2(г)>

/3/2(х2) + (1 - /3)/32Х2 = и2 + и2 + <*(<)■

Затем решение продолжается по параметру /3.

Теорема. Продолжение решений по параметрам в задачах А\ и А2 существует и единственно и не зависит от выбора очередности продолжения по параметру.

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

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

Рассмотрим произвольную систему линейных алгебраических уравнений:

а\\х\ а2\Х1

Она может быть переписана в матрично-векторном виде:

+ ах2х2 + ... а\пхп — Ь\

+ <12222 + ... 0.2„хп = Ъ2 + ат2Х2 + • • • атпхп = Ът.

(П)

Ах = Ь, А бЛтХп, х е Я", Ь еГ, (12)

где А - прямоугольная матрица, х и Ь векторы, а Я" - действительное евклидово пространство размерности п.

Матрицу А мы будем иногда называть линейным оператором, действующим в линейном пространстве К" с областью значений в линейном пространстве Ет. Такое определение удобно для описания процедур, свойственных произвольным линейным пространствам. В силу общности линейных пространств, систему типа (12) будем иногда называть просто уравнением.

Система (12) называется совместной, если она имеет не менее одного решения, иначе она называется несовместной. Для произвольной системы (12) возможны три случая:

1. система несовместна;

2. система имеет единственное решение;

3. система имеет бесконечно много решений.

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

• Плохая обусловленность задачи [11] - [17]. Матрицу с большим числом обусловленности как правило не удается привести к хорошо обусловленному виду путем линейных преобразований. Поэтому актуальна проблема выбора и разработки методов, нечувствительных к числу обусловленности системы.

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

компьютере с тактовой частотой 100 MHz займет время порядка 103 секунд. Решение системы большой размерности значительно упрощается в случае, когда заранее известна структура матрицы. Так, задачу с блочно-диагональной матрицей можно разбить на несколько независимых задач меньшей размерности. Трехдиагональные системы решаются методом прогонки с линейной вычислительной сложностью [11], [14].

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

В 40-х годах XX века с появлением компьютеров сильно возрос интерес к численным методам. Началось активное исследование применимости существующих методов к машинным вычислениям, попытки увеличить их точность. Вплоть до 80-х годов решение вычислительных задач было сильно ограничено ресурсами ЭВМ, поэтому особое значение придавалось экономичности алгоритмов. Именно тогда был разработан очень экономичный метод прогонки для решения трехдиагональных систем [14].

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

ния приблизительной оценки решения.

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

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

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

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

Глава III диссертации посвящена методам продолжения решений по параметру. Рассматривается система п нелинейных алгебраических или

трансцендентных уравнений, зависящая от параметра д:

/(я,д) = 0, хеНп, д 6 Я1, /ей" (13)

Пусть известно решение (хо,до) системы (13), т.е. /(хо,до) — 0. Рассмотрим окрестность В(хо, до) € Я"+1 точки (хо,до) в виде прямоугольного параллелепипеда в Я"+1 с центром в точке (хо, до)- Теорема о неявных функциях [18] дает ответ на вопрос о свойствах решения системы (13).

Теорема 3.1. [18]. Предположим, что

1. все функции /ь ..., /п определены и непрерывны в В(хо, до);

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

3. /(х0, до) = 0;

4. в точке (хо,до) отличен от нуля якобиан с1е17, матрица которого имеет вид

•7= 1хЫ,до)- (14)

Тогда в некоторой окрестности точки (хо, до) система уравнений (13) определяет х как однозначную функцию д:

х = х(д), х(д0) =х0, х <= Я". (15)

Указанные функции непрерывны и имеют непрерывные первые производные.

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

Для получения решения х\ при дх близкому к до, необходимо продвинуться вдоль этой кривой, оставаясь, однако, внутри В(хо,до)- Если условия Теоремы 3.1 выполнены в окрестности точки (11,91), то решение снова можно продолжить, и так далее. Это свойство и составляет основу метода продолжения по параметру.

Точки, п которых с1е1называются регулярными, а точки, в которых ¿еЬ J = 0 - особыми.

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

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

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

Первая группа связана с выбором наилучшего параметра продолжения из условия наилучшей обусловленности матрицы Якоби [19] (Шала-шилин В.И., Кузнецов Е.Б.).

Вторая группа методов связана с непрерывным аналогом метода Ньютона [20] (Давиденко Д.Ф.). Из (13) следует

'-Ъ <16>

Указанный подход позволяет использовать для построения решения х — х(д{) задачи Коши (16) различные численные методы интегрирования обыкновенных дифференциальных уравнений.

Продолжение решений при помощи интегрирования задачи Коши (16) обычно называют непрерывным аналогом Ньютона. Некоторые аспекты его применения изложены в работах Дикусара В.В. [7] и Федорен-ко Р.П. [21].

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

Опыт численного решения задач Коши показывает, что среди них следует выделять так называемые жесткие системы, которые требуют специальных численных методов. Несмотря на большое число публикаций по данной проблеме, до сих пор не существует общепринятой концепции жестких систем. Более того, нет даже общепринятого определения жесткости [19]. С содержательной точки зрения под жесткими системами понимают разнотемповые процессы. Здесь под жесткостью понимается спектральная норма матрицы Якоби.

Обычно для интегрирования жестких систем применяют неявные схемы. Однако их применение наталкивается на трудности, связанные с плохой обусловленностью матрицы Якоби. Дикусар В.В. предложил метод введения управляющих параметров для интегрирования жестких систем [22]. Лебедев В.И. предложил и реализовал программно явный метод Эйлера на основе итерационных процессов чебышевского типа [23].

Левенберг (1944) и Маркардт (1963) предложили модифицированный метод Гаусса-Ньютона, зависящий от двух параметров шк и А к [24]:

хк+1 = хк- ык[/'{хк)*/'{хк) + А^^/'Ы/Ы,

Л* > 0, шк > 0 ^ '

Дикусар В.В. [7] предложил другой вариант метода Ньютона с максимальной скоростью сходимости.

Основное время во всех предложенных методах тратится на вычисление матрицы Якоби. В диссертации предложены методы прогнозирования элементов матрицы Якоби и последующих приближений на базе полиномов Лагранжа и ортогональных полиномов Чебышева [23].

Полиномы Лагранжа первой и второй степени применяются при хорошо обусловленной матрице Якоби.

В случае плохо обусловленной матрицы 3 (14) для повышения эффективности метода Ньютона применяются полиномы Чебышева. Построение полиномов по параметру продолжения также дает возможность вычислять элементы матрицы Якоби непосредственно. Это на порядок увели-

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

Четвертая глава диссертации посвящена конкретным примерам решения задачи о внешнем долге.

В процессе вычислительных экспериментов выяснилось, что система (1) является неустойчивой по отношению к варьированию начальных условий и параметров задачи. Аналогичным свойством обладает и сопряженная система. Указанное свойство прослеживается на характере аналитических решений в Главе I. Наличие малых параметров /х,-, ¿ = 1,3 усложняют получение решений численными методами.

Использование системы "Баланс-2" [10] также не дает приемлемых результатов в плане построения устойчивых решений по начальным данным и параметрам задачи.

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

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

а затем с шагом Д£/2. Такой подход дал хорошее совпадение анали-

тического и численного решения.

При дискретизации задачи методом Эйлера она сводилась к задаче линейного программирования большой размерности. При Т = 100 выбирали = 1. Для решения указанной задачи использовался пакет "Баланс-2". Решение оказалось близким к аналитическому, однако появились краевые эффекты для управляющих функций. В начале и конце периода управления меняли знак, что не согласовывалось с принципом максимума (Приложение II).

В дальнейшем система "Баланс-2" использовалась для оценки геометрии оптимальной траектории в случае фазовых и смешанных ограничений. Полученное решение ислледовалось на предмет выполнения необходимых условий экстремума.

Полученные решения использовались в качестве первого приближения для решения задачи Аг. Для интегрирования системы (10) производилась замена переменных

2/1 = Ьяь г/г = 1пх2, ?/з=Ьжз.

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

Решение задачи А2, т.е. решение с различными производственными функциями /1(2:1) и /2(2:2) не меняет качественную картину решений. На самом деле, например, любое представление вида

ЬЫ = М1 - '*•), /2(^2) = 62(1 - е-*212)

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

Результаты расчетов приведены в Приложении II. Кроме того, представлены графики соответствующих переменных.

Основные выводы и результаты работы.

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

1. Предложены различные методы параметризации исходной модели с целью продолжения решений по параметру.

2. Получена алгоритмическая оценка решения плохо обусловленной алгебраической линейной системы (система Годунова С.К.).

3. Предложен метод предварительной оценки геометрии оптимальной траектории с помощью системы "Баланс-2".

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

5. Показано, что логарифмическая замена переменных улучшает устойчивость явных численных методов интегрирования типа Рунге-Кутта.

Приведенные примеры расчета показали эффективность разработанной методики.

Литература к автореферату.

1. Арсеньев В. Россия потеряла чувство долга. Журнал "Деньги". Экономический еженедельник издательского дома "Коммерсантъ". №31 [234] 11 августа 1999 г., стр. 9-11.

2. Абрамов А.П., Дикусар В.В. Нерегулярные точки в двусекторной экономической модели внешнего долга. Журнал "Дифференциальные уравнения", том 33, №12, Минск, 1997, стр. 1203-1209.

3. Умнов А.Е. Проблемы математического моделировании в условиях неполной информации. Автореферат докторской диссертации. ИПУ РАН, 1994.

4. Моисеев H.H. Математические задачи системного анализа. М.: Наука, 1981.

5. Разумихин B.C. Физические модели и методы теории равновесия и программирования в экономике. М.: Наука, 1975.

6. Умнов А.Е. Компактные образы неполных математических моделей сглаженного типа. Сб. "Проблемы математики в физико-технических и экономических задачах". М.: МФТИ, 1993.

7. Афанасьев А.П., Дикусар В.В., Милютин A.A., Чуканов C.B. Необходимое условие в принципе максимума. М.: Наука, 1990.

8. Дикусар В.В., Синягин С.Ю. Качественные и численные методы в задаче оптимального управления внешним долгом. Вычислительный центр РАН. Сообщения по прикладной математике. М.: ВЦ РАН, 2000.

9. Осмоловский Н.П. Теория условий высших порядков в оптимальном управлении. Автореферат докторской диссертации. Ленинградский университет, 1988.

10. Умнов А.Е. Система содействию принятия решений "Баланс". Методология, модели и алгоритмы. Издание СП "Комтех", Москва, 1991.

11. Калиткин H.H. Численные методы. М.: Наука, 1978.

12. Тихонов А.Н., Леонов A.C., Ягола А.Г. Нелинейные некорректные задачи. М.: Наука, 1995.

13. Морозов В.А. Регулярные методы решения некорректно поставленных задач. М.: Наука, 1987.

14. Волков Е.А. Численные методы. М.: Наука, 1987.

15. Ихрамов Х.Д. Численные методы для симметричных линейных систем. М.: Наука, 1988.

16. Райе Дж. Матричные вычисления и математическое обеспечение. М.: Мир, 1984.

17. Годунов С.К. Решение систем линейных уравнений. Новосибирск: Наука, 1980.

18. Кудрявцев Л.Д. Математический анализ. Т. 2. М.: Высшая школа, 1973.

19. Шалашилин В.И., Кузнецов Е.Б. Метод продолжения решений по параметру и наилучшая параметризация. Эдиториал УРСС, Москва, 1999.

20. Давиденко Д.Ф. Об одном новом методе численного решения систем нелинейных уравнений //ДАН СССР, 1953, Т. 88, №4, С. 601-602.

21. Федоренко Р.П. Жесткие системы ОДУ и их численное интегрирование. // Вычислительные процессы и системы. 1991, вып. 8, С. 328380.

22. Дикусар В.В. Методы теории управления при численном интегрировании ОДУ. Ж.ДУ. том 30, №12. Минск. С. 2116-2121.

23. Лебедев В.И. Как решать явными методами жесткие системы дифференциальных уравнений //Вычислительные процессы и системы. 1991. Вып. 8. С. 237-291.

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

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

1. Dikoussar V., Sinyagin S. Solving of Linear Systems. In Proceeding of ISA RAS "Dynamics of Non-Homogeneous Systems" M.: URSS, 1997, p. 179-192.

2. Синягин С.Ю. Метод вычисления первого приближения в задаче оптимального управления о внешнем долге //Проблемы нелинейной динамики и управления. Сборник трудов ИСА РАН. М.: УРСС, 1999. С. 209-216.

3. Дикусар В.В., Синягин С.Ю. Качественные и численные методы в задаче оптимального управления внешним долгом. Вычислительный центр РАН. Сообщения по прикладной математике. М.: ВЦ РАН, 2000, 50 стр.

Введение

I. Задача оптимального управления внешним долгом

1.1. Постановка задачи.

1.2. Первое приближение.

1.3. Принцип максимума без учета фазовых ограничений

1.4. Задача со свободным правым концом

1.5. Решение основной системы в задаче со свободным правым концом.

1.6. Нулевое приближение.

1.7. Продолжение решений по параметру 2.

1.8. Краевая задача с концевыми условиями для фазовых переменных

1.9. Метод введения параметра в дифференциальные уравнения

1.10. Замена переменных.

II. Численные методы решения систем линейных уравнений 44 2.1. Обзор численных методов решения систем линейных уравнений

2.1.1. Принятые обозначения.

2.1.2. Прямые и итерационные методы.

2.1.3. Нормы векторов и матриц.

2.1.4. Обусловленность матриц. Ошибки округления

2.1.5. Метод нормальных уравнений.

2.1.6. Принцип регуляризации

2.1.7. Применение методов факторного анализа в решении плохо обусловленных линейных систем

2.1.8. Метод введения параметра.

2.2. Метод продолжения по параметру для решения систем линейных уравнений.

2.2.1. Принцип продолжения.

2.2.2. Метод продолжения для решения линейных систем

2.2.3. О выборе числа итераций.

2.2.4. Расширения метода продолжения.

2.2.5. Процедура проверки метода

2.2.6. Результаты тестирования метода.

2.2.7. Интегральный метод проверки вычислительного метода

2.2.8. Выводы по результатам вычислений.

III. Методы продолжения решений по параметру

3.1. Постановка задачи

3.2. Наилучший параметр продолжения решения.

3.3. Непрерывный аналог метода Ньютона.

3.4. Жесткие системы обыкновенных дифференциальных уравнении

3.5. Обобщенный метод Ньютона. •

3.6. Полиномы Чебышева и Лагранжа.

3.6.1. Метод ортогональных функций

3.6.2. Полиномы П.Л. Чебышева

Ш. Результаты численных расчетов

4.1. Задача Понтрягина.

4.2. Пример аналитического исследования необходимых условий в задаче с фазовыми ограничениями.

Государственный долг России состоит не только из федеральной части, но и региональной. Большая часть задолженности субъектов Федерации падает на Москву. В общей сложности это составляет около 3,2 миллиарда долларов США по курсовым соотношениям, сложившимся на конец августа 1999 года. Величина долга Москвы равна примерно 380 долларов США на душу населения - что сравнимо с долгом Российской Федерации на душу населения, если не считать унаследованный Россией советский долг [1]. С другой стороны, долги различных стран России составляют порядка 300 миллиардов долларов США, не считая вывоза капитала за рубеж. Таким образом, указанная проблема представляет значительный интерес.

В Главе I диссертации на основе двусекторной модели внешнего долга [2] рассматривается задача минимизации внешнего долга на одного работника. Необходимо заметить, что исследование задачи проводится в условиях отсутствия достаточно полной информации о качественных свойствах и количественных характеристик объекта моделирования. Известен только внешний долг на одного работающего и величина обслуживания внешнего долга.

Классическая методология математического моделирования основные усилия направляла на повышение уровня адекватности моделей, т.е. степень их соответствия объекту моделирования [3].

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

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

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

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

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

При выполнении необходимых условий в неполной модели ищется допустимое решение.

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

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

Процесс пополнения фактически является процедурой выделения конуса достижимых состояний (Умнов) [3], (Моисеев) [4], (Разумихин) [5].

В схемах неполного моделирования [3] используются кусочно-линейные аппроксимации для всей совокупности состояний математической модели.

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

Умнов А.Е. в своей работе [6] ввел понятие специального математического объекта, именуемого компактным образом неполной модели. Схема, использующая этот объект, позволяет преодолевать все упомянутые трудности. Компактный образ по определению [6] включает результат некоторого отображения множества условно допустимых состояний неполной модели и систему вычислительных процедур для построения этого отображения.

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

Пусть ^ - множество условно допустимых состояний неполной модели, а ^о - множество ее целевых состояний. В качестве меры оценки расстояния между множествами .Р и ^о используется метрика Хаусдорфа.

Она определяется решением следующей задачи оптимизации: p{F, Fq) = max{maxminp(:r, у), тахютр(ж, ?/)}, x€F yeFo y€F0 xGF где p(x, у) - некоторая неотрицательная функция, характеризующая близость двух состояний модели и обладающая стандартными свойствами точечной метрики.

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

В диссертации динамика внешнего долга описывается системой уравнений [2]

1 = -jniXt + щ + и2, Xi(0) — ¡Ею, хг(Т) = ХЦ,

2 = ~ß2X2 + Щ + Щ, Х2(0) = X2Q, Х2(Т) = Х12, (1)

Xз = мз^з + Щ + US + щ - ue(t), ж3(0) = ж30, t £ [О, Т],

X = (х\, Х2, Жз), U — (иЪ U2, щ).

Здесь х - фазовый вектор, и - управляющая вектор функция, /¿i, ц2: /¿3, v - константы, e(t) - заданная функция.

Кроме уравнения (1), заданы уравнения баланса для двух секторов (сырьевой и производственный сектора) fi(xi) = e(t) + aifi(x{) + a2f2(x2), ^ f2(x2) = Щ + Щ + c2(t), где fi(xi), f2{x2) - заданные функции (производительности) в соответствующих секторах, e(t) - поток экспорта первого сектора, c2(t) - заданное неинвестиционное потребление.

На управляющие функции U{(t), г = 1,5 положены ограничения

О < Ui(t) < иц, 2 — 1,5 (3) u5(t) + c2(t) > cmin, te[0,T]. (4)

Ограничение (4) означает, что поток потребления не может быть меньше некоторого минимального значения.

Фазовые ограничения имеют вид

0<Zi(i), Х2тЫ < X2(t), 0 < Xs(t) < XZmax- (5) ■

Смысл второго ограничения (5) означает, что фондовооруженность производственного сектора не должна падать ниже некоторого критического уровня. Третье ограничение (5) задает уровень внешнего долга, превышение которого может привести к финансовому банкротству.

Поясним смысл управляющих функций: ui(t) - поток внешних инвестиций в 1-й сектор; u2(t) ~ поток фондообразующей продукции из второго сектора в первый; us(t) - поток внешних инвестиций во второй сектор;

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

Рассматривается Задача А2 о минимизации внешнего долга ж3(Т) -> min (6) при наличии ограничений (1) - (5).

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

В качестве первого приближения вместо задачи А2 рассмотрим задачу Аь

Задача Ai. Найти minхз(Т) при условиях (1) - (5). если /i(®i)=/3i®i(i), 0<aji(<)<ai, ai S R\ (7) f2(x2) = ß2x2{t), min < x2(t) < a2, a2e R1. (8)

Линейные неравенства (7), (8) для соотношений (2) позволяют провести качественное исследование оптимального управления для задачи Ai.

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

Наиболее просто это можно сделать в задаче Ао

Задача Ао- Требуется определить ютжз(Т) при условиях (1) - (8), если цх = ¡12 = /¿з = 0.

В задаче Ао сначала решается задача Понтрягина Л.С. [7]. Для этой цели предполагается выполнение условий (3), (4) и первое равенство (2) с учетом (7) подставляется в дифференциальное уравнение (1), т.е. е(£) = (1 - ахЩж!) - а^Ог), а второе равенство (2) заменяется неравенством и2+и4<р2Х2&)-С2{г), (9) которое предполагается автоматически выполненным. В этом случае легко определяется структура оптимального управления, что дает возможность найти оптимальную траекторию. Отметим, что сначала решается задача свободным правым концом, т.е. х\(Т) и х2(Т) не фиксированны.

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

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

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

В работе для предварительной оценки геометрии использовалась дискретная схема явного метода Эйлера для системы (1). В результате получается задача линейного программирования (ЛП) большой размерности. Для решения задачи ЛП был использован пакет оптимизационных программ "Баланс-2". Он включает прямой симплекс-метод. Блок-схема алгоритма предложена Кимом К.В. (ЦЭМИ РАН - ИАБА, 1985 г.). Программная реализация пакета выполнена в НПО "Научный центр" (МЭП СССР) совместно с кафедрой высшей математики МФТИ в 1990 г. (Ум-нов А.Е., Шомполов И.Г.) [10].

Входной файл данных пакета "Баланс-2" формировался на "Языке генерации линейных моделей Ь". Язык разработан Коротких М.П. (ЗАО "Информационные технологии", 1992 г.). Он представляет собой модифицированное "подмножество языка "Си+-Н".

Обработка выходных файлов системы "Баланс-2" проводилась средствами системы программ "МБ Ехе1 95".

Пакет "Баланс-2" использовался также для оценки геометрии смешанных ограничений типа (9), а также в задаче Понтрягина с фиксированным правым концом (задача Ао).

Для решения задачи А1 использовались результаты задачи Ао в качестве первого приближения. Указанное решение получалось методом продолжения решений по параметру а € [0,1]:

1 ~ —а11\Х\ + щ + и2

X2 = -0*112X2 + «3 + ^4 (10)

3 = а^х2 + щ + щ + и5 - ие{Ь)

При а = 0 задача А1 эквивалентна задаче А0. Далее выполняется продолжение решений по параметру а вплоть до а = 1.

Решение задачи Ах используется для решения задачи А2 методом введения параметра /3 (Е [0,1] в систему (2): е{1) = /3(1 - «0/1 (ая) + (За2Ых2)+

1 - /3)(1 - аО/Зтй + (1 - Р)а202Х2(г), /3/2(2:2) + (1 - Р)(32Х2 = и2 + и2 + ф).

Затем решение продолжается по параметру /3.

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

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

Рассмотрим произвольную систему линейных алгебраических уравнений: ацх 1 + Й12Ж2 + • • • а>1пхп = 021^1 + а22%2 + . а2пхп = 1 т!^! + ат2Х2 + . атпХп — Она может быть переписана в матрично-векторном виде:

Ах — Ь, А е Ятхп, х€ Л", Ь е (12) где А - прямоугольная матрица, х и Ь - векторы, а Кп - действительное евклидово пространство размерности п.

Матрицу А мы будем иногда называть линейным оператором, действующим в линейном пространстве Л™ с областью значений в линейном пространстве Лт. Такое определение удобно для описания процедур, свойственных произвольным линейным пространствам. В силу общности линейных пространств, систему типа (12) будем иногда называть просто уравнением.

Система (12) называется совместной, если она имеет не менее одного решения, иначе она называется несовместной. Для произвольной системы (12) возможны три случая:

1. система несовместна;

2. система имеет единственное решение;

3. система имеет бесконечно много решений.

Особый интерес представляют системы с квадратными (т = п) невырожденными (с!^ А ф 0) матрицами. Системы такого вида совместны и имеют единственное решение при любых правых частях. Именно такие задачи возникают в большинстве практических случаев. Численное решение этих систем связано, как правило, со следующими трудностями:

• Плохая обусловленность задачи [11] - [17]. Матрицу с большим числом обусловленности как правило не удается привести к хорошо обук Ъ2 ът.

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

• Большая размерность задачи. Здесь размерностью задачи является размерность матрицы А, т.е. число п. Многие численные методы имеют вычислительную сложность порядка п3. Так, решение задачи размерности 103 требует порядка 109 арифметических операций, что на компьютере с тактовой частотой 100 MHz займет время порядка 103 секунд. Решение системы большой размерности значительно упрощается в случае, когда заранее известна структура матрицы. Так, задачу с блочно-диагональной матрицей можно разбить на несколько независимых задач меньшей размерности. Трехдиагональные системы решаются методом прогонки с линейной вычислительной сложностью [11], [14].

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

В 40-х годах XX века с появлением компьютеров сильно возрос интерес к численным методам. Началось активное исследование применимости существующих методов к машинным вычислениям, попытки увеличить их точность. Вплоть до 80-х годов решение вычислительных задач было сильно ограничено ресурсами ЭВМ, поэтому особое значение придавалось экономичности алгоритмов. Именно тогда был разработан очень экономичный метод прогонки для решения трехдиагональных систем [14].

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

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

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

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

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

III глава диссертации посвящена методам продолжения решений по параметру. Рассматривается система п нелинейных алгебраических или трансцендентных уравнений, зависящая от параметра q f{x, q) = 0, хе Rn, qeR\ / G Rn (13)

Пусть известно решение xq, до системы (13), т.е. f(xо, до) — 0- Рассмотрим окрестность В{хо, до) £ Rn+1 точки (жо, до) в виде прямоугольного параллелепипеда в Rn+l с центром в точке (#o,go)- Теорема о неявных функциях [18] дает ответ на вопрос о свойствах решения системы [13].

Теорема 3.1. [18]. Предположим, что

1. все функции /i,., fn определены и непрерывны в В(хо, до);

2. существуют и непрерывны в Б(жо,до) частные производные от этих функций по всем аргументам;

3. f(xo, до) = 0;

4. в точке (гс0, до) отличен от нуля Якобиан det J, матрица которого имеет вид

J = fx(xo,qo)- (14)

Тогда в некоторой окрестности точки (жо, до) система уравнений (13) определяет х как однозначную функцию д: х = ж(д), x(q0) =х0, х е Rn. (15)

Указанные функции непрерывны и имеют непрерывные первые производные.

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

Для получения решения х\ при д\ близкому к до, необходимо продвинуться вдоль этой кривой, оставаясь, однако, внутри В{хо, до)- Если условия теоремы (3.1) выполнены в окрестности точки (х^, д1), то решение снова можно продолжить и так далее. Это свойство и составляет основу метода продолжения по параметру.

Точки, в которых 3 ф 0 называются регулярными, а точки, в которых йеЬ «7 = 0- особыми.

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

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

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

Первая группа связана с выбором наилучшего параметра продолжения из условия наилучшей обусловленности матрицы Якоби [19] (Шала-шилин В.И., Кузнецов Е.Б.).

Вторая группа методов связана с непрерывным аналогом метода Ньютона [20] (Давиденко Д.Ф.). Из (13) следует с1х дf д/

- 3Тч + Тч=й> *(«) = *<>• (16)

Указанный подход позволяет использовать для построения решения х = х(д{) задачи Коши (16) различные численные методы интегрирования обыкновенных дифференциальных уравнений.

Продолжение решений при помощи интегрирования задачи Коши (16) обычно называют непрерывным аналогом Ньютона. Некоторые аспекты его применения изложены в работах Дикусара В.В. [7] и Федорен-ко Р.П. [21].

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

Опыт численного решения задач Коши показывает, что среди них следует выделять так называемые жесткие системы, которые требуют специальных численных методов. Несмотря на большое число публикаций по данной проблеме, до сих пор не существует общепринятой концепции жестких систем. Более того, нет даже общепринятого определения жесткости [19]. С содержательной точки зрения под жесткими системами понимают разнотемповые процессы. Здесь под жесткостью понимается спектральная норма матрицы Якоби.

Обычно для интегрирования жестких систем применяют неявные схемы. Однако их применение наталкивается на трудности, связанные с плохой обусловленностью матрицы Якоби. Дикусар В.В. предложил метод введения управляющих параметров для интегрирования жестких систем [22]. Лебедев В.И. предложил и реализовал программно явный метод Эйлера на основе итерационных процессов чебышевского типа [23].

Левенберг (1944) и Маркардт (1963) предложили модифицированный метод Гаусса-Ньютона, зависящий от двух параметров сок и Хк [24]:

Хк+1 = хк- ик[/'{хк)*/'(хк) + АкЕ]~1/'(хк)/(хк) ^

А*>0, щ > О

Дикусар В.В. [7] предложил другой вариант метода Ньютона с максимальной скоростью сходимости.

Основное время во всех предложенных методах тратится на вычисление матрицы Якоби. В диссертации предложены методы прогнозирования элементов матрицы Якоби и последующих приближений на базе полиномов Лагранжа и ортогональных полиномов Чебышева [23].

Полиномы Лагранжа первой и второй степени применяются при хорошо обусловленной матрице Якоби.

В случае плохо обусловленной матрицы J (14) для повышения эффективности метода Ньютона применяются полиномы Чебышева. Построение полиномов по параметру продолжения также дает возможность вычислять элементы матрицы Якоби непосредственно. Это на порядок увеличивает эффективность методов Ньютона в случае плохо обусловленной матрицы Якоби.

Четвертая глава диссертации посвящена конкретным примерам решения задачи о внешнем долге.

В процессе вычислительных экспериментов выяснилось, что система (1) является неустойчивой по отношению к варьированию начальных условий и параметров задачи. Аналогичным свойством обладает и сопряженная система. Указанное свойство прослеживается на характере аналитических решений в главе I. Наличие малых параметров /¿¿, г = 1,3 усложняют получение решений численными методами.

Использование системы "Баланс-2" [10] также не дает приемлемых результатов в плане построения устойчивых решений по начальным данным и параметрам задачи.

Процесс поиска необходимых параметров задачи проводился путем аналитического решения задачи Ао- Основной целью был такой подбор таких начальных данных и параметров задачи, чтобы в конце планируемого периода получить снижение задолженности по сравнению с первоначальным, т.е. ж3(Т) < £з(0). Тем самым была определена область устойчивости решений в плане снижения долга в зависимости от начальных данных и параметров задачи в случае свободного правого конца. После этого исследовалось влияние изменения граничных условий х\(Т) и х2{Т) на функционал задачи.

Краевая задача со свободным правым концом решалась также численными методами путем продолжения решений по параметру. Сначала была решена задача Понтрягина. Система дифференциальных уравнений интегрировалась стандартным методом Рунге-Кутта с постоянным шагом. Шаг интегрирования выбирался на основе интегральной оценки концевых значений фазовых координат. Интегральная оценка основывалась на принципе Рунге-Кутта локального выбора шага интегрирования. Для этой цели основная и сопряженная система интегрировались с шагом At, а затем с шагом Д£/2. Такой подход дал хорошее совпадение аналитического и численного решения.

При дискретизации задачи методом Эйлера она сводилась к задаче линейного программирования большой размерности. При Т = 100 выбирали At — 1. Для решения указанной задачи использовался пакет "Баланс-2". Решение оказалось близким к аналитическому, однако появились краевые эффекты для управляющих функций. В начале и конце периода управления меняли знак, что не согласовывалось с принципом максимума (Приложение II).

В дальнейшем система "Баланс-2" использовалась для оценки геометрии оптимальной траектории в случае фазовых и смешанных ограничений. Полученное решение ислледовалось на предмет выполнения необходимых условий экстремума.

Полученные решения использовались в качестве первого приближения для решения задачи А1. Для интегрирования системы (10) производилась замена переменных

У1 = 1п ХЪ у-2 = 1п х2, Уъ = Ь ж3.

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

Решение задачи А2, т.е. решение с различными производственными функциями /1(3:1) и /2(^2) не меняет качественную картину решений. На самом деле, например, любое представление вида = &!< 1 - е~а1Х1), /2(а>2) = 62(1 - е~а2Х'2) допускает такое кусочно-линейное описание, что за счет выбора его параметров задачи с различным представлением будут эквивалентны в смысле концевых значений фазовых переменных.

Результаты расчетов приведены в Приложении II. Кроме того, представлены графики соответствующих переменных.

Литература к Введению.

1. Арсеньев В. Россия потеряла чувство долга. Журнал "Деньги". Эо-номический еженедельник издательского дома "Коммерсантъ". №31 [234] 11 августа 1999 г., стр. 9-11.

2. Абрамов А.П., Дикусар В.В. Нерегулярные точки в двусекторной экономической модели внешнего долга. Журнал "Дифференциальные уравнения", том 33, №12, Минск, 1997, стр. 1203-1209.

3. Умнов А.Е. Проблемы математического моделированим в условиях неполной информации. Автореферат докторской диссертации. ИПУ РАН, 1994.

4. Моисеев H.H. Математические задачи системного анализа. М.: Наука, 1981.

5. Разумихин B.C. Физические модели и методы теории равновесия и программирования в экономике. М.: Наука, 1975.

6. Умнов А.Е. Компактные образы неполных математических моделей сглаженного типа. Сб. "Проблемы математики в физико-технических и экономических задачах". М.: МФТИ, 1993.

7. Афанасьев А.П., Дикусар В.В., Милютин A.A., Чуканов С.В. Необходимое условие в принципе максимума. М.: Наука, 1990.

8. Дикусар В.В., Синягин С.Ю. Качественные и численные методы в задаче оптимального управления внешним долгом. Вычислительный центр РАН. Сообщения по прикладной математике. М.: ВЦ РАН, 2000.

9. Осмоловский Н.П. Теория условий высших порядков в оптимальном управлении. Автореферат докторской диссертации. Ленинградский университет, 1988.

10. Умнов А.Е. Система содействию принятия решений "Баланс". Методология, модели и алгоритмы. Издание СП "Комтех", Москва, 1991.

11. Калиткин H.H. Численные методы. М.: Наука. 1978.

12. Тихонов А.Н., Леонов A.C., Ягола А.Г. Нелинейные некорректные задачи. М.: Наука, 1995.

13. Морозов В.А. Регулярные методы решения некорректно поставленных задач. М.: Наука, 1987.

14. Волков Е.А. Численные методы. М.: Наука, 1987.

15. Ихрамов Х.Д. Численные методы для симметричных линейных систем. М.: Наука, 1988.

16. Райе Дж. Матричные вычисления и математическое обеспечение. М.: Мир, 1984.

17. Годунов С.К. Решение систем линейных уравнений. Новосибирск: Наука, 1980.

18. Кудрявцев Л.Д. Математический анализ. Т. 2. М.: Высшая школа, 1973.

19. Шалашилин В.И., Кузнецов Е.В. Метод продолжения решений по параметру и наилучшая параметризация. Эдиториал УРСС. Москва, 1999.

20. Давиденко Д.Ф. Об одном новом методе численного решения систем нелинейных уравнений //ДАН СССР, 1953, Т. 88, т., С. 601-602.

21. Федорснко Р.П. Жесткие системы ОДУ и их численное интегрирование. // Вычислительные процессы и системы. 1991. вып. 8, С. 328380.

22. Дикусар В.В. Методы теории управления при численном интегрировании ОДУ. ЖДУ. том 30, №12. Минск. С. 2116-2121.

23. Лебедев В.И. Как решать явными методами жесткие системы дифференциальных уравнений //Вычислительные процессы и системы. 1991. Вып. 8. С. 237-291.

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

I. Задача оптимального управления внешним долгом

1.1. Постановка задачи.

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

Предполагается, что производственная функция каждого из секторов имеет постоянную отдачу от масштаба производства и что связь между фондовооруженностью труда = х^), г -— 1,2 и его производительностью уг = ?/г(£) определяется в секторе г функцией вида где /г(жг-), г = 1,2 удовлетворяют неоклассическим условиям [1-2]

Уг^/г(Жг), ¿ = 1,2

1.1.1)

1.1.2) где { — 1,2- коэффициенты амортизации; щ - поток внешних инвестиций в 1-й срктор; и2 ~ поток фондообразующей продукции из второго сектора в первый; щ - поток внешних инвестиций во 2-й сектор:

4 - поток фондообразующей продукции второго сектора, направленный на собственное развитие.

Уравнение баланса продукции для первого сектора имеет вид

ЛЫ - е(*) + 01/1(0:1) + СК2/2Ы (1.1.3)

Здесь е(£) - поток экспорта первого сектора, а «¿/¿(а^), г — 1, 2 - потребление продукции первого сектора в соответствующих отраслях.

Балансовое уравнение для второго сектора задается равенством

2(х2)=и 2 + гг4 + с2й, (1-1.4) где с2(¿) - поток продукции, направленный на неинвестиционное потребление.

В рассматриваемой модели предполагается, что потоки экспорта и импорта определяют динамику внешнего долга. Пусть Ж3 = жз(^) означает внешний долг в момент времени Тогда

3 = + щ щ + «5 ~ уе\{1). (1.1.5)

Принятые обозначения: член учитывает необходимость обслуживания внешнего долга; щ — - поток импорта потребительских товаров; коэффициент V служит для сопоставления внутренних и внешних цен.

Предполагается, что поток потребления не может быть меньше некоторого минимального значения

Щ^) + С2(г) >сшш, te[Q,T\. (1.1.6)

Кроме того, уровень фондовооруженности во втором секторе не должен падать ниже некоторого критического уровня

2Й>®2шш, *е[0,Т]. (1.1.7)

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

Значение внешнего долга не может превышать некоторого порогового уровня, за которым следует финансовое банкротство страны max 5 ь £[0,Т]. (1-1.8)

Начальное состояние системы известно l(0) = Жю, Х2(0) = Х20, x3(0)=X3Q. (1.1.9)

Задача Ai. Рассматривается задача о минимизации внешнего долга при наличии ограничений (1.1.1)—(1.1.9), т.е. х3(Т)-+тт . (1.1.10) и заданных краевых условиях

Х1{Т) = х1Ь х2(Т) - х21 (1.1.11)

1. Иванилов Ю.П., Лотов A.B. Математические модели в экономике. М.: Наука, 1979.

2. Абрамов А.П., Дикусар В.В. Нерегулярные точки в двусекторной экономической модели внешнего долга. Журнал "Дифференциальные уравнения", том 33, №12, Минск, 1997, стр. 1203-1209.

3. Синягин С.Ю. Методы вычисления первого приближения в задаче оптимального управления о внешнем долге //Проблемы нелинейной динамики и управления. Сборник трудов. М.: ИСА РАН, 1999, стр". 209-216. Изд. Эдиториал УРСС, Москва.

4. Афанасьев А.П., Дикусар В.В., Милютин A.A., Чуканов C.B. Необходимое условие в принципе максимума. М.: Наука, 1990.

5. Шалашилин В.И., Кузнецов Е.Б. Метод продолжения решений по параметру и наилучшая параметризация. Эдиториал УРСС, Москва, 1999.

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

7. Венецкий И.Г., Венецкая В.И. Основные математико-стохастические понятия и формулы в экономическом анализе. М.: Статистика, 1979.

8. Тихонов А.Н., Васильева A.B., Свешников А.Г. Дифференциальные уравнения. М.: Наука, 1985.

9. Федоренко Р.П. Приближенное решение задач оптимального управления. М.: Наука, 1978.

10. Dikoussar V., Sinyagin S. Solving of Linear Systems in Proceedings of ISA "Dynamics of Non-Homogeneous Systems". M.: URSS, 1997, p. 179192.1.. Численные методы решения систем линейных уравнений