Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 4.5. ТЕОРЕМА СХОДИМОСТИНекоторые из основных условий, обеспечивающих сходимость, отмечены выше, теперь они будут сформулированы в виде теоремы. Прежде чем сформулировать теорему, докажем одну лемму. Лемма 4.1. Пусть
Тогда
Доказательство. Благодаря непрерывности
Согласно (а) последовательность
Используя выражение (4.6) и определение предела, видим, что для данного
Для
Тогда из выражений (4.7) — (4.9) следует, что
Лемма образно может быть интерпретирована в следующем виде. Если последовательность монотонно возрастающая, т. е. Компактность. Нам необходимо ввести еще одно понятие — компактность. Множество X называется компактным, если любая последовательность (или подпоследовательность) в X содержит сходящуюся подпоследовательность. В более явной форме, если дана подпоследовательность Можно показать, что в эвклидовом пространстве компактные множества соответствуют замкнутым и ограниченным множествам. Компактное множество должно содержать всю свою границу и не может простираться в бесконечность ни в одном направлении. Точки, вырабатываемые большинством алгоритмов, должны находиться в таких множествах. Теорема сходимости. Теорему сходимости мы сформулируем в весьма общих терминах. Вместо целевой функции будем пользоваться более общей функцией Множество подходящих точек
Другие примеры включают случаи, когда В теореме по заданной точке Теорема сходимости А. Пусть точечно-множественное отображение А Предположим, что 1) все точки 2) существует непрерывная функция а) если б) если 3) отображение А замкнуто в точке Тогда либо алгоритм останавливается в подходящей точке, либо предел любой сходящейся последовательности является подходящей точкой. Доказательство. Если алгоритм завершает поиск, то согласно Прежде всего следует обратить внимание на то, что согласно Используя
Рассмотрим теперь подпоследовательность
Условия (4.10) и (4.11) дают
Чтобы завершить доказательство, допустим, что
Тогда согласно п. 3
По предположению
Так как (4.12) и (4.14) противоречат друг другу, то точка Обсуждение теоремы сходимости А. Выше была сформулирована первая теорема сходимости. Несмотря на то, что далее будут доказаны более сильные теоремы сходимости, теорема сходимости А охватывает довольно широкую область и в последующих главах мы используем ее для доказательства сходимости многочисленных алгоритмов. Проанализируем теперь более подробно предположения теоремы сходимости А. В первую очередь, следует обратить внимание на то, что вместо переменной х мы пользовались переменной Условие 1 гарантирует достаточно хорошее поведение всех последовательностей. Без этого условия подпоследовательность может иметь предельную точку вне множества V или может расходиться. Условие 1 запрещает эти аномалии. Следует обратить, однако, внимание на то, что нет необходимости в компактности допустимого множества Как было отмечено ранее, использование Как было отмечено при рассмотрении примеров, для устранения разрывов, которые могут препятствовать сходимости, требуется нечто подобное условию 3. Следует обратить внимание, однако, на то, то мы не требуем замкнутости отображения в подходящей точке. В подходящей точке доминирует условие 26 и поведение самого отображения А несущественно. При установлении сходимости доказательство условия 3 обычно является наиболее сложным. Часто при математическом подтверждении условия 3 помогает следующая эвристика. Пусть Таким образом, теорема сходимости А устанавливает точную процедуру проверки сходимости. В первую очередь, должны быть определены отображение А и точки
|
1 |
Оглавление
|