4.4. СВОЙСТВА СХОДИМОСТИ

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

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

При начальной точке 5 алгоритм в (4.5) привел бы к следующей последовательности

Ясно, что

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

Непрерывность и сходимость. Для выяснения существа алгоритмической сходимости рассмотрим подробно алгоритмы (4.3) и (4.4), которые сходятся, а также алгоритм (4.5), который не сходится. Сначала рассмотрим свойства, общие для всех трех алгоритмов. Предположим, что для каждого из них дана допустимая начальная точка Тогда все три алгоритма вырабатывают последовательность такую, что а) все допустимы и б) если не является оптимальной точкой. Значит, все алгоритмы при допустимой

Рис. 4.1. Алгоритмы.

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

Какое же тогда различие между сходящимися и несходящимися алгоритмами? Обратите внимание, что в (4.3) функция непрерывна. А функция для алгоритма (4.5)

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

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

Обычное определение непрерывности функции А в точке заключается в том, что из следует, что

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

Теперь можно дать определение замкнутого отображения. Точечно-множественное отображение замкнуто в точке если из следует г)

Рис. 4.2. Замкнутые отображения. Множество изображено в виде отрезка.

Отображение называется замкнутым на если оно замкнуто в каждой точке и мы будем говорить, что отображение замкнуто; если оно замкнуто во всех точках своего определения. Эквивалентное определение замкнутого отображения рассматривается в упр. 2.

Рис. 4.2 представляет собой графическое изображение замкнутого отображения. Используя этот рисунок, мы можем интерпретировать существо понятия замкнутости. Допустим, что Выберем так, чтобы иметь

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

Отображение, которое не является замкнутым, приведено на рис. 4.3. Пусть Выберем для всех тогда не входит в Следовательно, отображение А, представленное на рис. 4.3, не замкнуто в точке

Рис. 4.3. Незамкнутое отображение.