4.6. РАЗЛОЖЕНИЕ АЛГОРИТМИЧЕСКОГО ОТОБРАЖЕНИЯ

Прямое доказательство замкнутости алгоритмического отображения А проводится обычно с трудом, так как А может быть составлено из нескольких частей. В этом параграфе мы покажем, как упростить это доказательство; вместо замкнутости А докажем замкнутость каждой из составных частей А. Например, в гл. 5 отображение А будет разложено на два отображения: D и М. Отображение при данном будет определять направление, а отображение М — вычислять используя данное направление. Поэтому отображение А может быть записано в виде чтобы показать, что А составлено из двух отображений. Доказательство замкнутости А потребует лишь доказательства замкнутости каждого из и М. Вообще говоря, эта последняя задача является проще и решается значительно легче, чем задача непосредственного доказательства замкнутости А.

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

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

Композиция представляет собой объединения множеств полученных из всех содержащихся в

Более строго составное отображение определяется как

В качестве примера определим соотношениями Тогда имеет вид

Здесь — пустое множество. Следует обратить внимание на то, что если так как в этом случае

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

Лемма 4.2. Пусть — точечно-множественные отображения. Предположим, что С замкнуто в точке , а В замкнуто на Предположим также, что если , то для некоторого а К

Тогда композиция замкнута в точке

Доказательство. Пусть Необходимо доказать, что

Выберем так, чтобы иметь

По предположению Вследствие замкнутости

Аналогично Следовательно,

К сожалению, лемма 4.2 не просто утверждает, что композиция двух замкнутых отображений замкнута. Требуется дополнительное предположение, благодаря которому сходится некоторая подпоследовательность последовательности Читатель легко может убедиться из упр. 8, что это предположение является обязательным. Другие формы этого предположения основаны на следующих следствиях 4.2.1 и 4.2.2. Следствие 4.2.1 особенно полезно. Доказательство этих следствий дается в качестве упр. 10.

Следствие 4.2.1. Пусть — точечно-множественные отображения. Допустим, что С замкнуто в точке а В замкнуто на Если множество X компактно, то -замкнуто в

Следствие 4.2.2. Пусть С: — функция, а точечно-множественное отображение.

Предположим, что С непрерывна в , а В замкнуто на Тогда точечно-множественное отображение замкнуто в точке

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

Сумма отображений определяется соотношением

Например, то

Скалярное произведение отображений определяется соотношением

Множество А представляет собой множество скалярных произведений для всех и для всех

Если то следующей разновидностью составного отображения является отображение типа произведения скаляра на вектор: где — скаляр; с — вектор; — вектор.

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

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

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

При этом отображение-сумма выражается композицией

Следующая лемма непосредственно следует из следствия 4.2.1.

Лемма 4.3. Пусть отображения замкнуты в точке Если компактно, то сумма этих отображений замкнута в точке

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

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

а. либо В, либо С — непрерывная функция в точке если то существует такое, что компактно.

Лемма 4.5. Пусть отображения В: замкнуты в точке Тогда скалярное произведение отображений замкнуто в точке если выполняется любое из следующих трех условий:

а. в точке как В, так и С — непрерывные функции;

б. если то существует такое, что

в. компактно.

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

а. в точке как В, так и С — непрерывные функции;

б. если то существует такое, что где по крайней мере одна из компонент вектора отлична от нуля;

в. если то существует такое, что где

г. множества V и компактны;

д. либо В — непрерывная функция и компактно, либо V компактно и С — непрерывная функция.

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

Упражнения

(см. скан)

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

(см. скан)

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

Приведенные здесь понятия алгоритма и сходимости основаны на работе Зангвилла Абади указал автору на то, что работа по теории сходимости, в какой-то степени подобная теореме сходимости А, выполнена Чевасом. На значение декомпозиции замкнутых отображений для НЛП указал Зангвилл (1967d).

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

Рис. 4.3 предложен доктором Вильямсом.