Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

4.2. Свойства алгоритмических отображений. Теорема сходимости

Пусть решение некоторой экстремальной задачи со скалярным аргументом есть x* = 0 (в качестве примера здесь можно назвать задачу об отыскании х≥0→min{z = 1+x} или х≥0→max{z = -2х2+3} и т. д.). Если дано исходное значение x = x1 ≠ 0, то в качестве допустимого можно принять алгоритм, основанный на отношениях xk+1=xk/r при r>1 или xk+1∈[xk/p, xk/r] при p>r>1. Как уже отмечалось (см. 4.1), порождаемые подобными алгоритмами последовательности {хk} обладают свойством


(т. е. сходятся к точке x* = 0).

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

(4.1)

то при начальном значении x1>1 возникает последовательность {хk}, сходящаяся к Х = 1. Тот факт, что алгоритм приводит к точке, не удовлетворяющей условию Х = х* = 0, равносилен нарушению требования его сходимости.

Чтобы найти причину неудовлетворительного поведения рассматриваемой последовательности, заметим следующее: функция W(xk) = xk/r является непрерывной, функция W(xk) в виде (4.1) имеет разрыв в точке х = 1. Как будет видно из дальнейшего, именно это обстоятельство оказывается решающим для оценок приемлемости того или иного алгоритма.

Пусть алгоритм поиска точки максимума функции z=f (X) на множестве U задан точечно-множественным отображением W(Хk); пусть далее множество искомых оптимальных X* не пусто. Обратимся к теореме (11): если

а) все Xk+1, порождаемые принятым отображением W(Xk), образуют компактное множество, включенное в U;

б) для любой точки Хk+1∈W(Хk) при Хk≠Х* выполнено f(Xk+1)≥f(Xk);

в) при Xk=X* алгоритм либо завершает поиск, либо для любого Xk+1∈W(Хk) имеет место равенство f (Xk+1) = f(Xk) = f (X*);

г) отображение W (Xk) замкнуто в точке Xk при Хk ≠ Х*, то рассматриваемый алгоритм либо останавливается в X*, либо предел любой сходящейся последовательности, формируемой в соответствии с требованием Хk+1∈W(Xk), есть X*.

Доказательство: заметим, что здесь достаточно исследовать случай, когда вырабатывается бесконечная последовательность {Хk} (иначе, в соответствии с условием в), очередная точка Хk, где завершается поиск,, должна быть принята за X*); для этого случая можно утверждать сходимость последовательности {Хk} к Х (см. условие а)), причем f(Хk+1)≥f(Xk) и


(см. условия б) ив)); рассмотрим подпоследовательность {ХK+1} с предельной точкой Х∞+1 в силу тех же замечаний


теперь остается лишь убедиться в том, что Х = Х*;. предположив противное (т. е. Х*), приходим к заключению: W(ХK) замкнуто в Х (см. условие г)) и f(X∞+1)≥f(X) при Х∈W(Х) (см. условие б)); но выше было подтверждено, что f(X∞+1) = f(Х); возникшее противоречие завершает доказательство теоремы. □

Чтобы сделать более конкретным содержание теоремы (11), заметим следующее: если нарушено условие а), то порождаемая алгоритмом последовательность {Хk} может иметь предельную точку вне U или вообще расходиться; условие б) требует улучшения значений z = f(X) на каждом шаге; условие в) относится к завершающей стадии поиска X*; условие г) необходимо для обеспечения сходимости алгоритма (в оптимальной точке замкнутость алгоритмического отображения уже не является обязательной, поскольку здесь доминирует требование в)). Таким образом, выбираемое отображение W(Xk) должно обладать целым рядом свойств, перечисленных выше; вследствие этого оно часто имеет весьма сложную структуру.

Непосредственное использование полученных результатов для подтверждения факта сходимости того или иного алгоритма бывает затруднено неудачным выбором W(Xk), который обычно неформален (хотя всегда есть стремление согласовать его с условиями теоремы (11)). Наиболее распространены осложнения, связанные с невозможностью убедиться в наличии свойства замкнутости у W (Xk). В таких случаях может оказаться полезным следующий прием: сложное алгоритмическое отображение разбивается на несколько составных частей,, замкнутость которых доказывается сравнительно легко; затем делается попытка установить желаемое свойство и у первоначального отображения. Реализация этой идеи требует уточнить понятие составного отображения.

Пусть X∈W1(V) и Y∈W2(X)-точечно-множественные отображения. Составное отображение W(V) = W2[W1(V)] представляет собой объединение множеств W2(Х), образуемых всеми X, содержащимися в W1. Например, если W1(V) и W2(Х) заданы как [v, 1] и [х-5; x+8], то


улучай скалярных v, х).

Обратимся теперь к теореме (12), приводимой здесь без доказательства: если W1(V) замкнуто в точке V, W2(X) замкнуто на множестве W1(V) и некоторая подпоследовательность последовательности {Хk} сходится к Х при условиях XkW(Vk), Vk→V, то составное отображение W(V) = W2[W1(V) ] замкнуто в W.

Рассмотренные положения позволяют обосновать приемлемость тех или иных численных методов для решения экстремальных задач.

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"