§ 5. Решение стационарных задач путем установления

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

Вектор пропорционален градиенту функции , т.е. ортогонален ее линиям уровня и направлен в сторону убывания значений функции . Таким образом, при перемещении вдоль траектории системы (1) значение не возрастает. Формально справедливость этого утверждения следует из неравенства

означающего, что всюду, за исключением стационарных точек функции .

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

Для решений этой системы имеем

если только . Функцию в первом случае и — во втором можно рассматривать как энергию материальной системы, движение которой описывается системами уравнений (1) и (3). Соотношения (2) и (4) показывают, что рассматриваемые нестационарные процессы характеризуются оттоком или, как говорят, диссипацией энергии.

Чтобы прояснить вопрос о разумном выборе , рассмотрим простейшую модель: — скаляр, ; тогда (3) приобретает вид

Соответствующее характеристическое уравнение

его корни м при , т.е. общее решение есть .

Скорость убывания решений рассматриваемого уравнения определяется величиной

При имеем и поэтому

При величины вещественны и

Тогда

Таким образом, график имеет вид, изображенный на рис. 7.5.1, и . Из результатов рассмотрений этой модельной задачи можно сделать следующие качественные выводы.

1. Если коэффициент трения очень мал (в нашем случае ), то решение системы (3) медленно устанавливается к положению равновесия; при этом (вследствие условия происходят колебания около положения равновесия.

2. Если велико (), то решение также медленно устанавливается; причина состоит в том, что при большом коэффициенте трения движение не может приобрести большой скорости.

Рис. 7.5.1

3. Оптимальное значение лежит где-то посередине и зависит от свойств конкретной функции .

Метод установления с помощью решения системы (3) иногда называют методом тяжелого шарика. Это название обусловлено следующими соображениями.

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

Ясно, что решение этой системы с течением времени установится к некоторой стационарной точке функции . Вблизи экстремума эта система близка к системе (3).

Большинство известных методов установления описывается уравнениями вида

или

где

и выполнены условия диссипативности, обеспечивающие сходимость к точке экстремума X. Вообще говоря, можно обратить операторы и и преобразовать эти уравнения к виду, где и — тождественные операторы. Однако исходная форма записи часто практически удобнее.

Может показаться, что построение таких нестационарных процессов, устанавливающихся к решению, уже полностью решает проблему отыскания минимума функции. Осталось «лишь» найти решение получившейся системы дифференциальных уравнений, используя какой-либо из численных методов решения задачи Коши.

В действительности сведение решения стационарной задачи к решению нестационарной не всегда дает удовлетворительное решение проблемы минимизации. Остается еще неясным существенный вопрос о выборе величины шагов численного интегрирования. Предположим, что решение нестационарной задачи устанавливается с требуемой точностью к решению стационарной за некоторый промежуток времени Т. Если интегрирование производится с малым шагом , то получаемые расчетные точки будут близки к рассматриваемой траектории и можно рассчитывать на попадание в малую окрестность точки минимума. Однако при этом число шагов может оказаться недопустимо большим (рис. 7.5.2).

Рис. 7.5.2

Рис. 7.5.3

Если шаг интегрирования берется очень большим, то может случиться, что расчетные точки начнут сильно отклоняться от рассматриваемого решения и никогда не попадут в искомую окрестность точки минимума (рис. 7.5.3).

Метод установления применим не только к задачам на экстремум функционала, но и к любым стационарным задачам . Строится некоторый процесс вида (5) или (6), где вместо стоит , и такой, что при , X — корень уравнения .

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

Напишем простейшую аппроксимацию метода установления

на временной сетке с постоянным шагом

Соответствующая расчетная формула

совпадает с расчетной формулой из § 6.3. Погрешности удовлетворяют соотношению . При имеем и скорость убывания погрешности определяется величиной . Там уже было установлено, что наиболее целесообразно брать , и тогда можно утверждать, что погрешность ведет себя как . Метод наискорейшего спуска можно также рассматривать как аппроксимацию метода установления, но уже на сетке с переменным шагом: ; шаг определяется каждый раз из условия .

Рассмотрим аппроксимацию метода установления

на временной сетке с постоянным шагом

— скалярный множитель. Погрешности удовлетворяют соотношениям

Разложим векторы по собственным векторам матрицы А:

Подставим выражения в (8); поскольку векторы независимы, то коэффициенты при них обращаются в нуль и получается система соотношений

Решения этих разностных уравнений записываются в виде

если — простые корни характеристического уравнения

и в виде

если корень (9) кратный. Во всех случаях определяющим фактором убывания является величина , которую можно мажорировать сверху величиной

где — максимальный по модулю корень уравнения

Мы не будем приводить полного решения задачи на экстремум (10), а ограничимся наводящими соображениями и выписыванием ответа.

При приближения записываются в виде (6.6.2). Поэтому рассматриваемый итерационный процесс не может дать лучшего приближения, чем оптимальный линейный итерационный процесс (6.6.19). При оптимальный линейный итерационный процесс переходит в итерационный процесс (6.6.23), который с учетом явного выражения может быть записан в виде

Можно подобрать и так, чтобы итерационный процесс совпадал с рассматриваемым. Для этого следует взять

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

Обратим внимание на поведение корней , соответствующих (11); имеем характеристическое уравнение

Запишем это уравнение в виде

Здесь — линейная функция от . Следовательно, при . Поэтому , имеют ненулевую мнимую часть и при .

Таким образом, указана совокупность коэффициента и шага , для которой

Неулучшаемость этой оценки усматривается из оценки скорости сходимости оптимального линейного итерационного процесса.

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

определяются из условия .

Соответствие между методами решения стационарных задач путем установления и обычными итерационными методами позволяет строить новые итерационные методы или новые процессы установления. Рассмотрим, например, расчетные формулы Ньютона

решения системы нелинейных уравнении . Этим формулам можно дать следующую интерпретацию: введем непрерывное время t и будем рассматривать величины как значения некоторой функции в моменты времени . Тогда соотношение (12), переписанное в виде

можно интерпретировать как получившееся при аппроксимации системы

Решение исходной задачи является стационарной точкой этой системы. При имеем

Таким образом,

Отсюда следует, что является асимптотически устойчивым решением (13).

Заменяя производную разностным отношением по значениям Функции в некоторых точках , получаем соотношения

иначе,

Таким образом, построение нестационарного процесса, соответствующего методу Ньютона, привело нас к получению итерационного процесса (14) более общего вида.

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

Задаются функционалом , например , нижняя грань которого, равная нулю, достигается при решении задачи. Последовательные приближения отыскиваются в виде (14), причем определяется из условия

Возникает вопрос о практическом нахождении величины , при которой достигается этот минимум.

Одна из распространенных процедур определения состоит в следующем. Задавая и — целое, при каждом последовательно вычисляют

и . Если при некотором оказалось , то вычисления прекращают и полагают в других процедурах находят и полагают .

Если

то возможны, например, такие варианты:

1) временный переход к другому методу;

2) остановка;

3) изменение значений параметров .

Отметим в заключение, что методы установления могут применяться и в случае минимизации функции в областях с ограничениями. Тогда уравнения (1), (3) следует дополнить какими-то уравнениями, которым будет подчиняться траектория точки, попавшей на границу.