Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
5. Сопряженные направления.Методы наискорейшего спуска или спуска по координатам даже для квадратичной функции требуют бесконечного числа итераций. Однако можно построить такие направления спуска, что для квадратичной функции
(где Положительно определенная матрица позволяет ввести норму вектора следующим образом:
Нетрудно проверить, что все аксиомы нормы при этом выполнены. Определение (31) означает, что под скалярным произведением двух векторов х и у теперь подразумевается величина
называют сопряженными (по отношению к данной матрице А). Ниже мы увидим, что поочередный спуск по сопряженным направлениям особенно выгоден при поиске минимума. На этом основана большая группа методов: сопряженных градиентов, сопряженных направлений, параллельных касательных и другие. Для квадратичной функции они применяются с одинаковым успехом. На произвольные функции наиболее хорошо обобщается метод сопряженных направлений, у которого детали алгоритма тщательно отработаны; этот метод излагается в данном пункте. а) Сначала рассмотрим, как применяется этот метод к квадратичной форме (30). Для этого нам потребуются некоторые свойства сопряженных векторов. Пусть имеется некоторая система попарно сопряженных векторов
Докажем, что взаимно сопряженные векторы линейно-независимы. Из равенства Это противоречие доказывает наше утверждение. Значит, система Пусть мы нашли некоторый сопряженный базис
Подставляя это выражение в правую часть формулы (30), преобразуем ее с учетом сопряженности базиса (33) к следующему виду:
Последняя сумма состоит из членов, каждый из которых соответствует только одной компоненте суммы (34). Это означает, что движение по одному из сопряженных направлений Совершим из точки Поясним геометрический смысл сопряженного базиса. Если осями координат сделать главные оси эллипсоидов уровня квадратичной функции, то один цикл спусков по этим координатам приводит точно в минимум. Если перейти к некоторым аффинным координатам, то функция останется квадратичной, но коэффициенты квадратичной формы изменятся. Можно формально рассмотреть нашу квадратичную функцию с измененными коэффициентами как некоторую новую квадратичную форму в декартовых координатах и найти главные оси ее эллипсоидов. Положение этих главных осей в исходных аффинных координатах будет некоторой системой сопряженных направлений. Разный выбор аффинных координат естественно приводит к разным сопряженным базисам. б) Сопряженный базис можно построить способом параллельных касательных плоскостей. Пусть некоторая прямая параллельна вектору Для этого воспользуемся выражением (35), где в сумме оставим только один член:
и положим
Пусть на какой-нибудь другой прямой, параллельной первой, функция принимает минимальное значение в точке гг; тогда аналогично найдем
Следовательно, направление, соединяющее точки минимума на двух параллельных прямых, сопряжено направлению этих прямых. Таким образом, всегда можно построить вектор, сопряженный произвольному заданному вектору Пусть имеются две параллельные Рассмотрим один цикл процесса построения сопряженного базиса. Пусть уже построен базис, в котором последние Теперь из точки Из точки Если одно из несопряженных направлений в базисе заменить направлением Начнем расчет циклов с произвольного базиса; для него можно считать, что в) Хотя понятие сопряженного базиса определено только для квадратичной функции, описанный выше процесс построен так, что его можно формально применять для произвольной функции. Разумеется, что при этом находить минимум вдоль направления надо методом парабол, не используя нигде формул, связанных с конкретным видом квадратичной функции (30). В малой окрестности минимума приращение достаточно гладкой функции обычно представимо в виде симметричной положительно определенной квадратичной формы типа (18). Если бы это представление было точным, то метод сопряженных направлений сходился бы за конечное число шагов. Но представление приближенно, поэтому число шагов будет бесконечным; зато сходимость этого метода вблизи минимума будет квадратичной. Благодаря квадратичной сходимости метод сопряженных направлений позволяет находить минимум с высокой точностью. Методы с линейной сходимостью обычно определяют экстремальные значения координат менее точно. Замечание 1. Реально даже для квадратичной функции процесс не всегда укладывается в Замечание 2. Теоретически безразлично, какое из несопряженных направлений выкинуть из базиса в конце цикла. Обычно выкидывают то направление, при спуске по которому на данном цикле функция изменилась менее всего. Поскольку для произвольной функции понятие сопряженности ввести нельзя, то направление наиболее слабого убывания выкидывают независимо от того, под каким номером оно стоит в базисе. Любопытно, что это оказывается выгодным даже для квадратичной функции, хотя на основании этого критерия иногда можно выкинуть сопряженное направление, оставив несопряженные; зато уменьшается потеря точности при ортогонализации. Замечание 3. Описанный выше цикл метода включает два спуска по сопряженным направлениям и один — по несопряженным. Более выгоден цикл, при котором сразу после нахождения нового сопряженного направления по нему делают спуск из точки При этом новое направление ставят в базис на последнее место и выкидывают то направление, на котором функция слабее всего уменьшилась при спусках от точки Метод сопряженных направлений является, по-видимому, наиболее эффективным методом спуска. Он неплохо работает и при вырожденном минимуме, и при разрешимых оврагах, и при наличии слабо наклонных участков рельефа — «плато»-, и при большом числе переменных — до двух десятков.
|
1 |
Оглавление
|