10.4. УСТОЙЧИВОСТЬ СИСТЕМ КОНЕЧНО-РАЗНОСТНЫХ УРАВНЕНИЙ — ТЕОРИЯ ЛЯПУНОВА

Алгоритмическое отображение в алгоритме Лагранжа было в сущности разностным уравнением. В этом

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

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

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

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

Тогда точка 0 будет точкой равновесия, и мы назовем ее решением.

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

где

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

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

Лемма 10.3. Пусть — непрерывная функция -Предположим, что при . Тогда для любого положительного числа Р множество где является компактным.

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

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

Теперь будет доказана основная теорема устойчивости.

Теорема 10.4. Рассмотрим систему конечно-разностных уравнений, представленную непрерывной функцией А где при заданном

и

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

Тогда т. е. система асимптотически устойчива в целом.

Доказательство. Сначала установим, что выполняются условия теоремы сходимости А.

Воспользовавшись выражениями (10.36) — (10.38), получим

Согласно лемме 10.3 множество компактно. Тогда условие 1 теоремы сходимости А имеет место, так как из (10.39) следует, что все принадлежат компактному множеству.

Определим точку 0 как подходящую точку. Если 2 не является подходящей точкой, то из (10.38) видно, что выполняется условие 2а теоремы сходимости А. Если — подходящая точка, то вследствие имеем что подтверждает выполнение условия 2б теоремы сходимости А.

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

Но так как все входят в компактное множество и все сходящиеся подпоследовательности имеют пределом точку 0, то

Этим завершается доказательство теоремы.

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

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

Некоторые применения теоремы даны в упр. 9, а особенности функции Ляпунова рассмотрены в упр. 11.

Упражнения

(см. скан)

(кликните для просмотра скана)

(см. скан)

Примечания и ссылки

§ 10.1. Алгоритм был разработай Хьюардом. Доказательство, естественно, будучи основано на теореме сходимости А, является новым. Метод центров в более абстрактных пространствах см. Буи — Тронг — Ли и Хьюард.

§ 10.2. Алгоритм Лагранжа представляет собой видоизменение метода разностных уравнений Удзавы применительно к методу дифференциальных уравнений Эрроу и Гурвица. Однако этот алгоритм несколько отличается от метода Удзавы из-за ошибки, допущенной в доказательстве автором оригинала. См. работу Эрроу, Гурвица, Удзавы (1958); Эрроу (1951); и Эрроу и Гурвица (1950). Распространение этой процедуры на игры лиц можно найти у Розена (1965).

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

§ 10.3. Другие экономические интерпретации см. в работах Гурвица; Эрроу и Гурвица (1960).

§ 10.4. Теория Ляпунова исключительно ценна и интересна. Можно посмотреть, например, работы Ляпунова; Л а Салле и Лефшетца; и Кальмана и Бертрама.

Дополнительные замечания

Для задачи НЛП было предложено множество других процедур. В работе Брегмана обсуждается вопрос о том, как находить допустимые точки выпуклых множеств, и этот вопрос связывается с линейным и квадратичным программированием. Другие процедуры построены в работах Еремина; Розена (1961); Варга (1963а), (1963b); Вегнера; Зуховишкого, Поляка и Примака (1963).

Хотя вопрос декомпозиции задач НЛП является весьма трудным, некоторые имеющиеся результаты, носящие предварительный характер, могут представить интерес. Например, можно посмотреть работы Розена (1963); Розена и Ориеа; Сандерса; Зангвилла (1967h). Декомпозицией пытаются свести решение задач большой размерности к решению нескольких задач меньшей размерности.

Следующим вопросом, который выходит за рамки темы настоящей книги, является параметрическое НЛП, в котором исследуется вопрос о том, как меняется решение при изменении некоторых параметров. Этому вопросу посвящены две работы Джоффриона (1966), (1967).