Глава 9. Релаксационные методы решения экстремальных задач. Методы безусловной минимизации

9.1. Вопросы сходимости

Прежде чем приступить к решению конкретной экстремальной задачи, следует выяснить вопрос, какому из методов минимизаций отдать предпочтение в данном случае. Для этого необходимо уметь сравнивать методы. Один путь-сравнивать на основании опыта и достаточного числа экспериментов - путь, без которого не обходится ни один специалист, использующий современную вычислительную технику для решения прикладных задач. Другой путь, никак не исключающий первый, - сравнивать качество методов на определенных классах задач. И здесь сразу же обнаруживается важная роль априорных характеристик методов. Эти характеристики должны учитывать многие факторы, в том числе трудоемкость вычислений, скорость сходимости, устойчивость метода к ошибкам в вычислениях, время (продолжительность) счета и ряд других. Пока еще не поставлена задача об исчерпывающей характеристике метода, но ясно, что одним из важных ее компонентов явится вопрос о сходимости. Отметим, что термин "скорость сходимости" всюду в этой книге понимается в классическом смысле, то есть как сравнение отклонения m-го приближения от точного решения с некоторой функцией числа m. Предположим, что для определенного класса задач некоторый метод А обеспечивает более быструю сходимость последовательных приближений, чем метод В. Тогда для того чтобы убедиться, что этот факт имеет место и для нашей экстремальной задачи, необходимо установить ее принадлежность соответствующему классу. Но и это в реальных ситуациях дело весьма непростое. Суть в том, что экстремальные задачи имеют своей целью дать возможность проникнуть в сущность того или иного явления и принять в определенном смысле наилучшее решение для управления самим явлением. Однако, как правило, информация об изучаемом явлении неполна и, следовательно, неполна информация об исходных величинах, входящих в экстремальную задачу. И все-таки, во-первых, определенная информация о задаче содержится в самой ее постановке в силу наших знаний о "физической" стороне изучаемого явления и благодаря имеющимся сведениям об оценках точности входных данных. С другой стороны, в процессе решения экстремальной задачи наши сведения о ней все более пополняются, таким образом, все более проясняется ее принадлежность определенному классу. Стало быть, накапливаемая информация и априорные характеристики позволяют своевременно оценить достоинства и недостатки определенного метода в применении к конкретной задаче и, следовательно, внести элементы управления в процедуру поиска решения.

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

Ниже рассматриваются различные релаксационные методы решения экстремальных задач и исследуются их скорость сходимости и устойчивость для выпуклых и достаточно гладких функций, как правило, принадлежащих классу С^1,1(Х), то есть градиенты которых удовлетворяют условию Липшица.

Поясним, в каком смысле здесь понимается устойчивость методов минимизации. Будем называть ошибки в вычислениях допустимыми, если они не превосходят некоторого числа ε. Если для некоторого метода существуют оценки, устанавливающие порядок сходимости, например, оценки, сравнивающие величину отклонения m-го приближения от точного решения с величиной О (1/m^α) (здесь число α определяет порядок сходимости),

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