Последовательные приближения корней

. (4.19)

Оптимальный шаг в направлении антиградиента - это такой шаг, при котором значение - наименьшее среди всех других значений Ф(х,у) в этом фиксированном направлении, т.е. когда точка является точкой условного минимума. Следовательно, можно рассчитывать на наиболее быструю сходимость метода (4.19). если полагать в нем

. (4.20)

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

Геометрическая интерпретация этого метода хорошо видна из рис. 4.1, 4.2. Характерны девяностоградусные изломы траектории наиско­рейшего спуска, что объясняется исчерпываемостью спуска и свойством градиента (а значит, и антиградиента) быть перпендикулярным к линии уровня в соответствующей точке.

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

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

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

Главное достоинство градиентных методов решения нелинейных систем - глобальная сходимость. Нетрудно доказать, что процесс гради­ентного спуска приведет к какой-либо точке минимума функции из лю­бой начальной точки. При определенных условиях найденная точка минимума будет искомым решением исходной нелинейной системы.

Главный недостаток - медленная сходимость. Доказано, что сходи­мость этих методов - лишь линейная[1], причем, если для многих методов, таких, как метод Ньютона, характерно ускорение сходимости при прибли­жении к решению, то здесь имеет место скорее обратное. Поэтому есть ре­зон в построении гибридных алгоритмов, которые начинали бы поиск ис­комой точки - решения данной нелинейной системы - глобально сходя­щимся градиентным методом, а затем производили уточнение каким-то быстросходящимся методом, например, методом Ньютона (разумеется, ес­ли данные функции обладают нужными свойствами).

Разработан ряд методов решения экстремальных задач, которые со­единяют в себе низкую требовательность к выбору начальной точки и вы­сокую скорость сходимости. К таким методам, называемымквазиньюто-новскими, можно отнести, например,метод переменной метрики (Дэвидона-Флетчера-Пауэлла), симметричный и положительно определен­ный методы секущих (на основе формулы пересчета Бройдена).

При наличии негладких функций в решаемой задаче следует отка­заться от использования производных или их аппроксимаций и прибегнуть к так называемымметодам прямого поиска {циклического покоорди­натного спуска. Хука и Дживса, Роленброка и т.п.). Описание упомяну­тых и многих других методов такого типа можно найти в учебной и в спе­циальной литературе, посвященной решению экстремальных задач (см., например. [17-19]).

Замечание 1. Для разных семейств численных методов минимиза­ции могут быть рекомендованы свои критерии останова итерационного процесса. Например, учитывая, что в точке минимума дифференцируемой функции должно выполняться необходимое условие экстремума, на конец счета градиентным методом можно выходить, когда достаточно малой становится норма градиента. Если принять во внимание, что минимизация применяется к решению нелинейной системы, то целесообразнее отслеживать близость к нулю минимизируемой неотрицательной функции, т.е. судить о точности получаемого приближения по квадрату его евклидовой метрике.

Замечание 2.Для решения n-мерной системы (4.1) следует свести задачу к решению экстремальной задачи:

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

Пример 4.1. Алгоритм поиска экстремума с шагом,не зависящим от свойств минимизируемой функции.

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

1. Создание файла F_L4.m, с>держащего описание функции, возвращающей значения функции f(x,y) в узлах координатной сетки

% листинг файла F_L4.m

function z=F_L4(x,y,mu)

N=length(x);

z=zeros(N);

for i=1:N

for j=1:N

z(i,j)=x(i).^2+mu*y(j).^2;