ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.10.2024
Просмотров: 148
Скачиваний: 0
центр тяжести пика относительной заселенности соответствует ф, равному 66°, что совпадает с опытным значением (см. раздел 3,
гл. 1).
Если поиск начинается из нулевого приближения, далекого от минимума, то выгоднее всего использовать линейные методы, в частности метод скорейшего спуска. Однако в окрестности ми нимума эти методы дают медленную сходимость, и тогда более эффективными оказываются квадратичные методы.
Итерационные процедуры минимизации позволяют построить последовательность векторов независимых переменных
jc(1>, ..., x ik), ..., которая сходится в точке минимума. Линейные методы характеризуются следующими рекуррентными соотноше ниями между векторами
x ( k +i ) = x (k) _ |
(*(*)) |
(2. ю з) |
где h {k) ^ 0 — шаг в направлении |
антиградиента —U '(x^)\ |
|
в простом варианте этого метода /г(*> считается постоянным. В ме тоде скорейшего спуска, который, по крайней мере, для кон-
формационных задач более эффективен, |
выбирается |
из усло |
||||
вия |
минимума |
на направлении |
спуска —U '(xik)) (на прямой), |
|||
т. е. |
|
|
|
|
|
|
|
U [ x w |
— h i k ) U ' ( х ^ ) ] = |
m i n U |
\ x {k) — |
h U ( x w ) ] |
(2.104) |
|
|
|
h->0 |
|
|
|
(о том, как найти минимум на прямой, |
будет сказано при обсуж |
|||||
дении |
квадратичного метода). |
|
|
|
|
|
Кроме метода скорейшего спуска, известно еще несколько модификаций линейных методов 1173—175]. Из них особого вни мания заслуживает метод сопряженных градиентов, в котором
направление спуска |
на |
(к |
1)-ой итерации |
выбирается |
с уче |
|
том направления на £-ой итерации, |
а именно |
|
||||
|
д.(*-н) _ |
*(*) _ |
/,(*) £>(*) |
|
(2 . 105) |
|
где |
|
|
|
|
|
|
D<*> = |
- V |
(*<*>) + |
|
D<k~ " |
(2.106) |
|
и || U'(x) || — длина соответствующего вектора, |
т. е. |
|
|
П |
|
\\ U' |
(х)|| - = [ 2 ( d U l d x i Y ^ 12 |
(2.107) |
|
7=1 |
|
(шаг h S k \ как и прежде, |
находится из условия минимума на пря |
|
мой). |
|
|
Здесь уместно сделать небольшое отступление относительно нормировки вектора, указывающего направление спуска. Для того, чтобы сделать начальный шаг т спуска на прямой [см. вы ражение (2.116)] относительно универсальным (одинаковым для различных методов минимизации), все векторы имеет смысл нор
9 - 7 6 |
219 |
мировать на их длину, т. е. считать, например, что в выражении (2.103) вместо U'(x) стоит нормированный вектор градиента U' (x)!\\U' (х) ||. В частности, в приводимых ниже примерах поиска минимума (табл. 2.8) нормировка позволила провести все вычис ления с одинаковым шагом — 0,00005.
Метод сопряженных градиентов обычно дает более быструю сходимость, чем метод скорейшего спуска, поскольку он не так инертен на «поворотах» траектории поиска. Недостаток его состоит в том, что при удалении от начальной точки лг<°> происхо дит накопление ошибок в вычислении очередного направления спуска. По этой причине траектория поиска, практически дойдя до минимума, может из него «выскочить».
Отметим еще «метод тяжелого шарика», в котором вместо вы ражения (2.103) строится последовательность векторов
x (k+\) = |
x (k) h (k) ц , (*(*)) + р (jc<*>— х(*-1>) |
(2 .108) |
|
учитывающая опыт предыдущего поиска (|3 > 0, |
но близко к 0). |
||
Этот метод обладает |
свойством нелокальности |
и |
обеспечивает |
в некоторых случаях обходы мелких впадин. Но вблизи минимума он сходится очень медленно. Испытания метода тяжелого шарика на конформационных задачах показали, что он весьма редко оказывается эффективнее метода скорейшего спуска.
В окрестности минимума поверхности уровней потенциальной функции скорее напоминают эллипсоиды, чем сферы, поэтому квадратичные методы, которые дают направление спуска на центр эллипсоида, быстрее сходятся, чем градиентные. Опишем коротко одну из модификаций метода Ньютона — Рафсона, испытанную на большом числе конформационных задач [176, 177]. Пусть
по-прежнему строится последовательность |
векторов лг(0), д:(1), |
..., х (к), ..., сходящаяся к минимуму. Около |
точки х ^ разложим |
минимизируемую функцию в степенной ряд, отбросив члены третьего порядка малости, и, переходя к координатной записи, получим
и (*,) = и (х/( 1)) -!- ]£] агДх(- + -у- 5 ] |
bij&x^Xj |
(2.109) |
|
‘ |
' |
/ |
|
где
Чтобы найти минимум функции (2.109), необходимо прирав нять нулю ее частные производные по Дхг и решить систему ли нейных уравнений
J ] bijbxj + щ = 0 i=l,2,..., л |
(2.111) |
130
Обозначим через х г точку, соответствующую решению (2.111.) Тогда движение по направлению от будет соответствовать спуску к центру эллипсоида, т. е.
х<ь+\) = x(k) + hkXl |
(2.112) |
Остается решить два вопроса — как |
вычислить производные |
и как найти оптимальное значение hk, соответствующее минимуму функции на прямой (это необходимо делать и в методе скорей шего спуска).
Наиболее простым способом вычисления производных яв
ляется применение метода конечных разностей |
|
||||
|
|
Ш_ |
U (Xj + б) |
(2.113) |
|
|
|
dxt |
~ |
б |
|
|
|
|
|||
|
d2U |
U (*,- + |
6) + |
U (Xj — б) — 2U (Xj) |
|
|
дх? |
— |
|
б5 |
(2.П4) |
d*U |
U (х, + б, х, +- б) + U (xiXj) - U (xt + б) - |
U (х, + б) |
|||
с)x(dxj |
— |
|
|
б 5 |
' ( 2 - 4 5 ) |
где 6 — малое приращение |
аргумента. Если |
U выражается в |
|||
ккал/моль, расстояния — в А и углы — в радианах, то хорошая точность достигается при б = 0,0003.
Хотя этот способ самый простой, он в то же время не может претендовать на экономичность. Дело в том, что выражения, вхо дящие в производные, -вычисляются в процедуре-функции. Ис пользование их в точных формулах для первых и вторых произ водных позволило бы сэкономить машинное время; при этом для задач с большим числом переменных можно было бы добиться сокращения машинного времени почти на порядок. Большинство авторов, рассчитывавших конформации молекул, ограничились конечными разностями, но С. Г. Галактионов [178, с. 81 нашел удобные аналитические выражения для производных и в даль нейшем применял их в расчетах. Лифсон и Варшел 11791 первые производные находили аналитически, а вторые — методом ко нечных'разностей, используя для них выражение (2.113), в пра вой части которого вместо функции U фигурировали значения ее производных ди1дхг.
Перейдем к вопросу о поиске минимума на прямой. Как мы указывали, в простом градиентном методе шаг hk в выражении (2.103) считается постоянным, и после того, как этот шаг будет сделан, вновь проводится вычисление градиента. Заранее трудно сказать, каково должно быть универсальное пк, и потому жела тельна его оптимизация; этого и добиваются в методе скорейшего
9 * |
131 |
спуска. Возьмем малое положительное число т и вместо (2.103) напишем последовательность
|
x[k+l) = |
xw — TU' (х{к>) |
|
||
|
х(к+Х) = |
х (к) — 2тU' (х <fc)) |
|
||
|
4 ft+I) = |
x (A) — ЗтU'(x{k)) |
(2.116) |
||
|
|
= |
jc<A) — ixU' (х(к>) |
|
|
Вычисляя |
функцию в |
каждой из |
этих точек, |
найдем такое |
|
U ( X m + X)), |
ДЛЯ которого |
Tm+1) ^ |
U { X m - Р ) . Тогда точку X |
||
можно принять за минимум на направлении спуска и для сле дующей итерации считать ее нулевой, т. е. убрать нижний ин декс.
Метод скорейшего спуска с описанной стратегией поиска на прямой неоднократно применялся в конформационных расчетах Ц80, 181, 123]. Не говоря уже о том, что линейные методы не являются наилучшими при уточнении положения минимума, заметим, что для поиска минимума на прямой можно найти более эффективную процедуру. Вернемся к квадратичному методу и пусть направление от х (к) к х 1 уже найдено (2.112). Возьмем попрежнему малое положительное число т, но вместо выражения (2.116) построим иную последовательность
Л(*+о = х(*) + |
|
|||
V<*+4 . |
|
|
-f- 2тхг |
(2.117) |
х2 |
|
|
||
г(А+1).— x (k> + 4t * i |
|
|||
(*+!)_ *.<*) |
+ 2‘- h Xl |
|
||
XV |
x w |
|
|
|
Вычисляем функцию до тех пор, пока не будет |
выполнено |
|||
условие |
|
|
|
|
и „ = и ( ,Й +1)) > |
u m- 1 = и ( } ) ) |
(2.118) |
||
(поскольку степень 2 в уравнениях (2.117) быстро растет, то этого не придется долго дожидаться). Запомним три последние значе ния функции Ит_2, £/,„_! и Um и проведем для них параболиче
скую интерполяцию, т. е. будем считать, что точки Хт-Р, Хт-Х\ и х \к+1’>находятся на параболе. Минимум параболы будет соот ветствовать
JC(fc+1>— *<*>+ |
,3 |
• 2т-1т- Um- |
5и, |
■1+ 4Uт-2 |
(2.119) |
|
8 |
U,n - |
W , |
■1+ 2(Ут_2 |
|
(нижний индекс у х отсутствует, поскольку на (2.119) заканчи вается итерация в квадратичном методе).
132