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

i	x	y	z
	0.5	0.5	0.5
	0.875	0.5	0.375
	0.78981	0.49662	0.36993
	0.78521	0.49662	0.36992

Останавливаясь на приближении x ⁽³⁾, будем иметь:

x = 0.7852; y = 0.4966; z =0.3699.

4.3. Решение нелинейных систем методами спуска

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

Для использования наглядной геометрической интерпретации приводимых ниже рассуждений и их результатов ограничимся, как и в предыдущем пункте, рассмотрением системы, состоящей из двух уравнений с двумя неизвестными

(4.16)

Из функций , системы (4.16) образуем новую функцию

. (4.17)

Так как эта функция неотрицательная, то найдется точка (вообще говоря,

не единственная) , такая, что

.

Следовательно, если тем или иным способом удается получить точку , минимизирующую функцию , и если при этом окажется, что , то точка - истинное решение системы (4.16), поскольку

Последовательность точек - приближений к точке минимума функции - обычно получают по рекуррентной формуле

(4.18)

где - вектор, определяющий направление минимизации, а - скалярная величина, характеризующая величину шага минимизации (шаговый множитель). Учитывая геометрический смысл задачи минимизации функций двух переменных - «спуск на дно» поверхности (рис. 4.1), итерационный метод (4.18) можно назвать методом спуска, если вектор при каждом k является направлением спуска (т.е. существует такое , что ) и если множитель подбирается так, чтобы выполнялось условие релаксации , означающее переход на каждой итерации в точку с меньшим значением минимизируемой функции.

Таким образом, при построении численного метода вида (4.18) минимизации функции следует ответить на два главных вопроса: как выбирать направление спуска и как регулировать длину шага в выбранном направлении с помощью скалярного параметра - шагового множителя . Приведем простые соображения по этому поводу.

При выборе направления спуска естественным является выбор такого направления, в котором минимизируемая функция убывает наиболее быст­ро.

Рис. 4.1. Пространственная интерпретация метода наискорейшего спуска для функции (4.17)	Рис. 4.2. Траектория наискорейшего спуска для функции (4.17)

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

- антиградиент функции . Таким образом, из семейства мето­дов (4.18) выделяем градиентный метод

. (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;

end;

end;

2. Построение графиков исследуемой функции при различных значениях параметра m

N=23;

Xmin=-5;Xmax=5;

Ymin=-5;Ymax=5;

i=1:N;j=1:N;

x(i)=Xmin+i*(Xmax-Xmin)/N;

y(j)=Ymin+j*(Ymax-Ymin)/N;

M1=F_L4(x,y,0.5);M2=F_L4(x,y,1);M3=F_L4(x,y,1.5);

[X Y]=meshgrid(x,y);

surfc(X,Y,M1); colormap gray

surfc(X,Y,M2); colorap gray

surfc(X,Y,M3); colormap gray

Рис. 4.3. Поверхность и карта линий уровня функции

Рис. 4.4. Поверхность и карта линий уровня функции

Рис. 4.5. Поверхность и карта линий уровня функции

Из рис. 4.3-4.5 видно, что при функция представляет собой параболоид вращения, при параболоид становится эллиптическим, «вытягиваясь» вдоль оси оХ (при - вдоль оси оY).

3. Создание файла Dx_F_L4.m, содержащего описание функции, возвращающей значения частной производной, по переменной x.

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

function z=Dx_F_L4(x,y,mu)

N=length(x);

z=zeros(N);

i=1:N;

j=1:N;

for i=1:N

for j=1:N

z(i,j)=2*x(i);

end;

end;

4. Создание файла Dy_F_L4.m, содержащего описание функции, возвращающей значения частной производной, по переменной y.

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

function z=Dy_F_L4(x,y,mu)

N=length(x);

z=zeros(N);

i=1:N;

j=1:N;

for i=1:N

for j=1:N

z(i,j)=2*mu*x(i);

end;

end;

5. Создание файла L_Grad.m, содержащего описание функции, возвращающей длину градиента функции f (x, y, m)

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

function z=L_Grad(x,y,mu)

N=length(x);

z=zeros(N);

for i=1:N

for j=1:N

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

z(i,j)=z(i,j).^0.5;

end;

end;

6. Создание файла S_x.m, содержащего описание функции, возвращающей значение проекции на ось oX нормированного единичного вектора, сонаправленного с вектором, направление которого противоположно направлению вектора градиента

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

function z=S_x(x,y,mu);

N=length(x);

z=zeros(N);

i=1:N;

j=1:N;

for i=1:N

for j=1:N

z(i,j)=-Dx_F_L4(x(i),y(j),mu)./L_Grad(x(i),y(j),mu);

end;

end;

7. Создание файла S_y.m, содержащего описание функции, возвращающей значение проекции на ось oY нормированного единичного вектора, сонаправленного с вектором, направление которого противоположно направлению вектора градиента

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

function z=S_y(x,y,mu);

N=length(x);

z=zeros(N);

for i=1:N

for j=1:N

z(i,j)=-Dy_F_L4(x(i),y(j),mu)./L_Grad(x(i),y(j),mu);

end;

end;

8. Создание файла Lambda.m, содержащего описание функции, возвращающей значение шага

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

function z=Lambda(x,y,nu,alpha,beta,gamma,lambda0);

z=alpha*lambda0/(beta+gamma*nu);

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

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

function [X,Y,ff]=MG(x0,y0,mu,nu,alpha,beta,gamma,lambda0)

X(1)=x0;

Y(1)=y0;

ff(1)=F_L4(x0,y0,mu);

for i=2:nu

X(i)=X(i-1)+Lambda(X(i-1),Y(i-1),nu,alpha,beta,gamma,…

lambda0)*s_x(X(i-1),Y(i-1),mu);

Y(i)=Y(i-1)+Lambda(X(i-1),Y(i-1),nu,alpha,beta,gamma,…

ambda0)*s_y(X(i-1),Y(i-1),mu);

ff(i)=F_L4(X(i),Y(i),mu);

end;

10. Нахождение минимума функции f (x, y, m) и визуализация итерационного процесса

Vmax=20; % максимальное число шагов итерационного процесса

x0=2; y0=-1; % начальное приближение

lambda0=0.3; % начальное значение шага к экстремуму

beta=1; alpha=1; gamma=1; % параметры, используемые для

% определения шага

mu=1;nu=20;

[X,Y,ff]=MG(x0,y0,mu,nu,alpha,beta,gamma,lambda0);

plot(X);

Дата добавления: 2014-01-06