1626435584-7c6402f545ecf856225d6cf8d21519c9 (844233), страница 47
Текст из файла (страница 47)
При попадании траектории в истинный овраг спуск прекращается, а в разрешимом овраге сильно замедляется. Если функция является положительно определенной квадратичной функцией Ф (г) = (», Аг) + (И, г) + с, (22) то формулы наискорейшего спуска приобретают несложный вид. Вдоль прямой г = г„+ а( функция (22) квадратично зависит от параметра 7: <р(1)= — Ф(гв+а7)=Ф(г„)+(2А»,+И, а)1+(а, Аа)(в. (23) Из уравнения (аЧ~/А1) =О легко находим ее минимум г= — (2Аг„+И, а)/2(а, Аа), (24) дающий нам следующую точку спуска: »в+в г» + а(~ (2Авв+ Ь, а)в (25) 4(вв, Аа) Направление наискорейшего спуска определяется градиентом квадратичной функции (22): а= — (йгаб Ф), = — (2Аг„+И).
(26) пОиск минимумА 1гл уп Подставляя это значение в формулы (24) — (25), получим окончательные выражения для вычисления последовательных спусков. Если воспользоваться разложением всех движений по базису, состоящему из собственных векторов матрицы А, то можно доказать, что для квадратичной функции метод наискорейшего спуска линейно сходится, причем (г„,— ю ,'«-д(г,— я"), где д= " '" 1; (27) Хаааа+Х(ып здесь й — собственные значения положительно определенной матрицы А (они вещественны и положительны). Если )а ы~(~Х,„, что соответствует сильно вытянутым эллипсам — линиям уровня, то д — 1 и сходимость может быть у очень медленной. Есть такие начальные приближения (рнс.
39), когда точно реализуется наихудшая возможная оценка, т. е. в (27) + имеет место равенство. Причины нетрудно понять. Вопервых, в данной точке любую прямую, в том числе невыгодную для спуска, можно сделать направлением градиента, если спеРис. 39. циально подобрать изменение мас- штабов по осям. Во-вторых, каждый спуск кончается в точке, где его направление касается линии (поверхности) уровня. Градиент перпендикулярен поверхности уровня. Следовательно, в методе наискорейшего спуска каждый спуск перпендикулярен предыдущему. В двумерном случае это означает, что мы совершаем спуск по координатам, повернутым так, что одна ось параллельна градиенту в начальной точке.
Для улучшения метода наискорейшего спуска предлагают «кухонные» поправки к алгоритму — например, совершают по каждому направлению спуск не точно до минимума. Наиболее любопытным представляется такое видоизменение алгоритма. Будем делать по направлению, противоположному градиенту, только бесконечно малый шаг и после него вновь уточнять направление спуска. Это приводит к движению по кривой г(Г), являющейся решением системы обыкновенных дифференциальных уравнений: — „, = — дгас(Ф(г'(()). (2о) Вдоль этой кривой ОФ(п(= (с(Ф/й') (й (й) = — (ягаб Ф)' (О, т.
е. функция убывает, и мы движемся к минимуму при ( — «+оо. минимум ч>ункции мнОГих переменных 209 Уравнение (28) моделирует безынерционное движение материальной точки вниз по линии градиента. Можно построить и другие уравнения — например, дифференциальное уравнение второго порядка, моделирующее движение точки при наличии вязкого трения. Однако от идеи метода еще далеко до надежного алгоритма.
Фактически систему дифференциальных уравнений (28) надо численно интегрировать (см. главу ЧП)). Если интегрировать с большим шагом, то численное решение будет заметно отклоняться от линии градиента. А при интегрировании малым шагом сильно возрастает объем расчетов. Кроме того, если рельеф имеет извилистые овраги, то трудно ожидать хорошей сходимости этого метода. Алгоритмы наискорейшего спуска и всех его видоизменений сейчас недостаточно отработаны. Поэтому метод наискорейшего спуска для сложных нелинейных задач с большим числом переменных (и ) 5) редко применяется, но в частных случаях он может оказаться полезным. 4. Метод оврагов. Рассмотрим задачу Ф(г)=ш>п. Выберем произвольно точку рэ и спустимся из нее (напрнмер, по координатам), делая не очень много шагов, т, е.
не требуя высокой точности сходимости. Конечную точну спуска обозначим гг. Если рельеф овражный, эта точна окажется вблизи дна оврага (рис. 40). Теперь выберем другую точку р, не слишком далеко ат первой, Из нее также сделаем спуск и попадем в некоторую точку г,. Зта точка тоже лежит вблизи дна оврага. Проведем через точки г„и г, на дне оврага прямую— приблизительную линию дна оврага, передвинемся по этой линии в сторону убывания функции и выбереы новую точку р, = г, ->- (г, †) й, 6=сопи ) О. (29) В формуле (29) выбирается плюс, если Ф(г,) (Ф(г„), и минус в об- Рис. 40.
ратном случае, так что движение направлено в сторону пони>кения дна оврага. Величина Д называется овражным и>агом и для каждой функции подбирается в ходе расчета. Дно оврага не является отрезком прямой, поэтому точна рз на самом деле лежит не на дне оврага, а на склоне. Из этой точки снова спустимся на дно и попадем в некоторую точку гз. Затем соединим точки г, и гз прямой, нанетим новую линию дна оврага и сделаем новый шаг по оврагу.
Продолжим процесс до тех пор, пока значения функции на дне оврага, т. е. в точках г„, убывают. В случае, когда Ф (г,,) > Ф (г„), процесс надо прекратить и значение г„, не испольэовать. Метод оврагов рассчитан на то, чтобы пройти вдоль оврага и выйти в котловину около минимума. В этой котловине значения минимума лучше уточнять другими методами. 210 1гл. Уп ПОИСК МИНИМУМА Методом оврагов удается находить минимумы достатонио сложных функций от 5 — 10 переменных. Но этот метод довольно капризен. Для каждой функции приходится подбирать свой овражный шаг, визуально наблюдать эа ходом расдета и вносить коррективы.
Программирование этого метода иа ЭВМ иесаожпо. 5. Сопряженные направления. Методы наискорейшего спуска или спуска по координатам даже для квадратичной функции требуют бесконечного числа итераций. Однако можно построить такие направления спуска, что для квадратичной функции Ф (г) = (г, Аг) -1- ((т, г) -(-с (30) (где г есть и-мерный вектор) с симметричной положительно определенной матрицей А процесс спуска сойдется точно к минимуму за конечное число шагов. Положительно определенная матрица позволяет ввести норму вектора следующим образом: )х)~~~=(х, Ах))0 при хФО. (31) Нетрудно проверить, что все аксиомы нормы при этом выполнены. Определение (31) означает, что под скалярным произведением двух векторов х и у теперь подразумевается величина (х, Ау). Векторы, ортогональные в смысле этого скалярного произведения (х, Ау) =О, (32) называют сопряженносми (по отношению к данной матрице А).
Ниже мы увидим, что поочередный спуск по сопряженным направлениям особенно выгоден прн поиске минимума. На этом основана большая группа методов: сопряхгенных градиентов, сопряженных направлений, параллельных касательных и другие. Для квадратичной функции они применяются с одинаковым успехом. На произвольные функции наиболее хорошо обобщается метод сопряженных направлении, у которого детали алгоритма тщательно отработаны; этот метод излагается в данном пункте.
а) Сначала рассмотрим, как применяется этот метод к квадратичной форме (30). Для этого нам потребуются некоторые свойства сопряженных векторов. Пусть имеется некоторая система попарно сопряженных векторов хь Нормируем каждый из этих векторов в смысле нормы (31); тогда соотношения между ними примут вид (хн Аху) =бн. (33) Докажем, что взаимно сопряженные векторы линейно-независимы. Из равенства х,= ~ сс;хг следует (х,, Ахь) =- )~ ссз(х„Ах;)=О, с-а т а МИНИМУМ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ 21! $21 что противоречит положительной определенности матрицы, Это противоречие доказывает наше утверждение.
Значит, система п сопряженных векторов является базисом в и-мерном пространстве. Для данной матрицы имеется бесчисленное множество базисов, состоящих из взаимно сопряженных векторов. Пусть мы нашли некоторый сопряженный базис х2, 1 «! «и. Выберем произвольную точку г,. Любое движение из этой точки можно разложить по сопряженному базису г=г,+~ а!х!. (34) Подставляя это выражение в правую часть формулы (30), преобразуем ее с учетом сопряженности базиса (33) к следующему виду: л Ф (г) = Ф (г) + ~ , '[а2+ 2а! (х2, А1,) + а! (хп Ь)1.
(35) Последняя сумма состоит из членов, каждый из которых соответствует только одной компоненте суммы (34). Зто означает, что движение по одному из сопряженных направлений х! меняет только один член суммы (35), не затрагивая оогальных. Совершим из точки г, поочередные спуски до минимума по каждому из сопряженных направлений хи Каждый спуск минимизирует свой член суммы (35), так что минимум квадратичной функции точно досп!игается после выполнения одного цикла спусков, то есть за конечное число действий. Поясним геометрический смысл сопряженного базиса. Если осями координат сделать главные оси эллипсоидов уровня квадратичной функции, то один цикл спусков по этим координатам приводит точно в минимум. Если перейти к некоторым аффинным координатам, то функция останется квадратичной, но коэффициенты квадратичной формы изменятся. Можно формально рассмотреть нашу квадратичную функцшо с измененными коэффициентами как некоторую новую квадратичную форму в декартовых координатах и найти главные оси ее эллипсоидов.
Положение этих главных осей в исходных аффинных координатах будет некоторой системой сопряженных направлений. Разный выбор аффинных координат естественно приводит к разным сопряженным базисам. б) Сопряженный базис можно построить способом параллельных касательных плоскостей. Пусть некоторая прямая параллельна вектору х, а квадратичная функция достигает на этой прямой минимального значения в точке г,. Подставим уравнение этой прямой г=гл+ах в выражение (30) и потребуем выполнения условия минимума 2!2 ПОИСК МИНИМУМА 1гл.
Уп функции >р(сс) = Ф(г',+ах) в точке г"=1',, т. е, при а=О. Для этого воспользуемся выражением (35), где в сумме оставим только один член: Ч Ох) = Ф(Р'ч)+сс'+се (х, 2ЛА;+ Ь), и положим (>(ч>.,>>(а)„,=0. Отсюда следует уравнение, которому удовлетворяет точка минимума: (х, 2Аг»+Ь) =О. (36) Пусть на какой-нибудь другой прямой, параллельной первой, функция принимает минимальное значение в точке >,; тогда аналогично найдем (х, 2Лг; + Ь) = О. Вычитая это равенство из (36), получим (х, А (т 1 — т;)) = О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
