ПОИСК Статьи Рисунки Таблицы О некоторых качественных квантовохимических подходах к анализу сравнительной эффективности различных механизмов химических реакций из "Прикладная квантовая химия Расчеты реакционной способности и механизмов химических реакций" Величина к часто определяется условием минимизации функции вдоль направления 8, поэтому существенной частью многих алгоритмов является одномерная минимизация функции. [c.106] Эффективность алгоритмов минимизации часто оценивают порядком (или скоростью) сходимости. Говорят, что последовательность сходится к линейно, если последовательность расстояний я —q п] убывает как геометрическая прогрессия, т. е. [c.106] На практике поэтому используют так называемые квазиньютоновские методы, в которых на основе имеющейся информации о значениях функции, или также и о значениях производных, определяется приближенная матрица О или или же используется алгоритм, который позволяет за конечное число шагов минимизировать квадратичную функцию. При этом обычно используются процедуры, которые позволяют строить так называемые сопряженные направления. Два направления 8 8 считаются сопряженными относительно матрицы А, если 8 А8 = 0. Можно показать, что последовательная минимизация выпуклой квадратичной формы вдоль последовательности К линейно независимых сопряженных направлений (где К — размерность пространства координат q) определяет точный минимум квадратичной формы. Таким образом, К шагов подобных алгоритмов имитируют один шаг метода Ньютона — Рафсона. [c.108] Так как ф1 = ф2, ф1 + ф2 = 1, то при последующем делении отрезка одна из точек, для которой значение функции было вычислено на предыдущей итерации, уже будет удовлетворять условию (2.134), так что на каждом с те-дующем шаге потребуется вычисление функции только в одной новой точке. Аналогичная процедура, использующая последовательность чисел Фибоначчи, описана в [232]. Там же дан алгоритм, в котором используется движение вдоль отрезка с постоянным шагом до тех пор, пока не будет найдена точка, в которой значение функции возрастает затем шаг уменьшается и процесс повторяется до тех пор, пока значение минимума не будет установлено с желаемой точностью (см. [232, с. 270]). [c.109] Число вычислений функции в рассмотренных процедурах поиска связано с точностью отыскания Я, . Так, в методе золотого сечения за каждые 5 шагов точность повышается примерно на порядок. [c.110] Эффективный метод одномерной минимизации, который включает поиск интервала, содержащего минимум, по методу удвоения шага и квадратичную интерполяцию по Пауэллу, описан в монографии Химмельблау [231, с. 50]. [c.110] Многомерная минимизация. Простейшие методы поиска основаны на определенной стратегии последовательного перебора точек в многомерном пространстве. [c.110] в методе Хука и Дживса на каждой отдельной итерации каждой координате дается по очереди некоторое конечное приращение и, если функция при этом убывает,, то новое значение координаты используют вместо старого. В противном случае делают щаг по данной коор-динате в противоположном направлении и в зависимости от того, убывает функция или нет, приписывают координате новое значение или сохраняют старое. Далее переходят к следующей координате. После перебора всех координат переходят к следующей итерации, и так до тех пор, пока перебор всех координат не приведет к сохранению старых значений. На этом алгоритм может быть закончен, либо щаг может быть уменьщен. [c.111] Симплексный метод основан на сравнении значений функции в верщинах правильного многогранника ( симплекса ), содержащего (М+1) верщину, в М-мерном пространстве. Худщая точка, в которой значение функции максимально, заменяется новой, расположенной симметрично по отнощению к (М—1)-мерной грани симплекса, что приводит к построению нового симплекса и т. д. В [231] описан модифицированный метод, в котором симплекс деформируется с учетом особенностей формы поверхности (метод деформируемых многогранников). [c.111] Достоинством указанных методов является их простота, так что их программирование не требует особого труда, однако сходимость подобных процедур весьма медленна и движение к экстремальной точке требует очень большого числа вычислений функции, особенно когда размерность пространства велика. [c.111] Если построенные векторы линейно зависимы, то к ним добавляется нужное число базисных векторов и с полученным семейством векторов производится процедура ортогонализации. Метод Дэвиса — Свенна — Кемпи можно рассматривать как метод асимптотически сопряженных направлений, так как в пределе получающиеся направления аппроксимируют набор собственных векторов матрицы О. [c.112] Рассмотрим ряд методов, в которых при выборе направления спуска используются производные. [c.112] Большей эффективностью обладают методы, исполь-з тощие сопряженные направления. С использованием производных сопряженные направления строятся особенно просто. [c.113] За К шагов метод обеспечивает минимизацию положительно определенной квадратичной формы, в случае произвольных функций алгоритм может быть продолжен, пока градиент функции не станет достаточно мал. [c.114] Как и в предыдущих методах, последовательность направлений оказывается сопряженной в случае положительно определенной квадратичной функции и метод сходится за К итераций, причем в конце итераций оказывается, что A = G т. е. метод обеспечивает автоматическое построение матрицы, обратной гессиану. В случае произвольных функций соответствующее утверждение справедливо лишь в условиях сходимости к точке минимума. [c.115] Мы описали только принципиальные схемы каждого из алгоритмов для того, чтобы читатель мог представить их структуру, а также количество вычислений и объем машинной памяти при решении тех или иных задач. На самом деле, при практической реализации необходимо учесть много математических тонкостей. Более подробные сведения о свойствах алгоритмов и детальное их описание читатель найдет в цитированных руководствах. [c.115] Все градиентные методы не зависят от выбора направления координатных осей, но масштабирование переменных с учетом известной информации о силовых постоянных в молекулах может существенно повысить их эффективность. [c.116] Поскольку методы сопряженных направлений за К шагов имитируют один шаг метода Ньютона — Рафсона, они, вообще говоря, обладают квадратичной скоростью сходимости. Однако это их свойство проявляется лишь в достаточной близости к экстремальной точке. В случае расчета стабильных структур использование известной структурной информации позволяет достаточно хорошо выбирать начальное приближение. Известные значения силовых постоянных (из эксперимента или из родственных расчетов) можно использовать при задании начального приближения для матрицы А (A 5iG ) в методах переменной метрики. Интересной особенностью градиентных методов сопряженных направлений является их эквивалентность в случае выпуклой квадратичной функции [234], когда они приводят к одной и той же последовательности сопряженных направлений. Но для произвольных функций, особенно вблизи точек перегиба, разные методы приводят к разным результатам. Наибольшей устойчивостью, по-видимому, обладают методы переменной метрики, но в задачах с очень большим числом переменных необходимость работы с матрицей высокого порядка может приводить к затруднениям тогда следует пользоваться более простыми методами параллельных касательных или сопряженных градиентов. Предварительно полезно улучшить начальное приближение с помощью метода скорейшего спуска. [c.116] Особо следует остановиться на вопросе о сохранении симметрии ядерной конфигурации при проведении оптимизации. Все градиентные методы сохраняют симметрию начального приближения. Это утверждение вытекает из того, что градиент некоторой функции имеет ту же симметрию, что и сама функция, а симметрия функции потенциальной энергии должна быть не ниже, чем симметрия ядерной конфигурации. Часто для уменьшения числа варьируемых параметров с самого начала вводят координаты симметрии и варьируют только полносимметричные координаты. В том и другом случае найденный экстремум может оказаться не минимумом по отношению к несимметричным деформациям, что в действительности часто и происходит. Можно исправить ситуацию, если чередовать итерационные циклы основной процедуры с одним циклом координатного спуска (метод, который свободен от ограничений по симметрии). С другой стороны, когда симметрия заранее обусловлена требованиями задачи, применение градиентных методов позволяет обойтись без использования симметризованных переменных, так как поиск экстремума автоматически осуществляется в подпространстве требуемой размерности. [c.117] Вернуться к основной статье