Глава 11. НЕОБХОДИМЫЕ И ДОСТАТОЧНЫЕ УСЛОВИЯ СХОДИМОСТИ

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

11.1. ВВЕДЕНИЕ

Чтобы вывести эти новые условия, подробно проанализируем предшествовавшие условия сходимости. Четыре трудности являются очевидными. Первая — это требование замкнутости алгоритмического отображения; многие отображения незамкнуты. Вторая трудность — это требование строгого улучшения функции в случае, если не является подходящей точкой (условие 2а теоремы сходимости А), Конечно, нет необходимости, чтобы

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

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

Последний вопрос касается конкретного определения алгоритмического отображения. Раньше мы полагали, что т. е. отображение определялось на всем пространстве V. В действительности же достаточно, если будет определено лишь на части V, скажем на тогда