86210 (612684), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Метод спуска по координатам несложен и легко программируется на ЭВМ. Но сходится он медленно, а при наличии оврагов – очень плохо. Поэтому его используют в качестве первой попытки при нахождении минимума.

Пример. Рассмотрим квадратичную функцию и выберем нулевое приближение . Выполняя вычисления, получим

.

Уточнение по Эйткену дает , т. е. точное положение минимума (заметим, что делать уточнение с использованием нулевого приближения нельзя).

2.3 Наискорейший спуск

Спускаться можно не только параллельно осям координат. Вдоль любой прямой функция зависит только от одной переменной, , и минимум на этой прямой можно найти.

Наиболее известным является метод наискорейшего спуска, когда выбирается , т. е. направление, в котором функция быстрее всего убывает при бесконечно малом движении из данной точки. Спуск по этому направлению до минимума определяет новое приближение . В этой точке снова определяется градиент и делается следующий спуск.

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

Если функция является положительно определенной квадратичной функцией

, (16)

то формулы наискорейшего спуска приобретают несложный вид. Вдоль прямой функция (16) квадратично зависит от параметра :

. (17)

Из уравнения легко находим ее минимум

, (18)

дающий нам следующую точку спуска:

(19)

направление наискорейшего спуска определяется градиентом квадратичной функции (16):

. (20)

Подставляя это значение в формулы (18) – (19), получим окончательные выражения для вычисления последовательных спусков.

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

, где ; (21)

здесь – собственные значения положительно определенной матрицы (они вещественны и положительны). Если , что соответствует сильно вытянутым эллипсам – линиям уровня, то и сходимость может быть очень медленной.

Есть такие начальные приближения (рис. 4), когда точно реализуется наихудшая возможная оценка, т. е. в (21) имеет место равенство.

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

Для улучшения метода наискорейшего спуска предлагают «кухонные» поправки к алгоритму – например, совершают по каждому направлению спуск не точно до минимума. Наиболее любопытным представляется такое видоизменение алгоритма. Будем делать по направлению, противоположному градиенту, только бесконечно малый шаг и после него вновь уточнять направление спуска. Это приводит к движению по кривой , являющейся решением системы обыкновенных дифференциальных уравнений:

. (22)

Вдоль этой кривой , т. е. функция убывает, и мы движемся к минимуму при . Уравнение (22) моделирует безынерционное движение материальной точки вниз по линии градиента. Можно построить и другие уравнения – например, дифференциальное уравнение второго порядка, моделирующее движение точки при наличии вязкого трения.

Однако от идеи метода еще далеко до надежного алгоритма. Фактически систему дифференциальных уравнений (22) надо численно интегрировать. Если интегрировать с большим шагом, то численное решение будет заметно отклоняться от линии градиента. А при интегрировании малым шагом сильно возрастает объем расчетов. Кроме того, если рельеф имеет извилистые овраги, то трудно ожидать хорошей сходимости этого метода.

Алгоритмы наискорейшего спуска и всех его видоизменений сейчас недостаточно отработаны. Поэтому метод наискорейшего спуска для сложных нелинейных задач с большим числом переменных ( ) редко применяется, но в частных случаях он может оказаться полезным.

2.4 Случайный поиск

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

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

Даже при миллионе пробных точек вероятность того, что хотя бы одна точка попадет в небольшую окрестность локального минимума, ничтожно мала. В самом деле, пусть диаметр котловины около минимума составляет от пределов изменения каждой координаты. Тогда объем этой котловины составляет часть объема -мерного куба. Уже при ни одна точка в котловину не попадет.

Поэтому берут небольшое число точек и каждую точку рассматривают как нулевое приближение. Из каждой точки совершают спуск, быстро попадая в ближайший овраг или котловину; когда шаги спуска сильно укорачиваются, его прекращают, не добиваясь высокой точности. Этого уже достаточно, чтобы судить о величине функции в ближайшем локальном минимуме с удовлетворительной точностью.

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

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

Пусть, например, координаты – это размеры деталей механической конструкции, а минимизируемая функция есть мера качества конструкции. Если мы нашли минимум точно, то мы находимся в самом центре котловины около минимума. В этом случае вариации координат влияют на функцию слабее, чем в точках, расположенных ближе к краям котловины. А безопасные вариации координат имеют в данном примере смысл допусков на точность обработки деталей. Значит, при аккуратном вычислении координат минимума мы можем разрешить большие допуски, т. е. удешевить обработку деталей.

Метод случайного поиска зачастую позволяет найти все локальные минимумы функции от 10-20 переменных со сложным рельефом. Он полезен и при исследовании функции с единственным минимумом; в этом случае можно обойтись заметно меньшим числом случайных точек. Недостаток метода в том, что надо заранее задать область, в которой выбираются случайные точки. Если мы зададим слишком широкую область, то ее труднее детально исследовать, а если выберем слишком узкую область, то многие локальные минимумы могут оказаться вне ее. Правда, положение несколько облегчается тем, что при спусках траектории могут выйти за пределы заданной области и сойтись к лежащим вне этой области минимумам.

ЗАКЛЮЧЕНИЕ

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Калиткин Н.Н. Численные методы. М.: Наука, 1978. 512с.

2. Амосов А.А., Дубинский Ю.А., Копченова Н. В. Вычислительные методы для инженеров. М.: Высшая школа, 1994. 543с.

3. Ракитин В.И., Первушин В.Е. Практическое руководство по методам вычислений. М.: Высшая школа, 1998. 383с.

Приложение 1

Листинг программы:

{Методом покоординатного спуска найти точки локального минимума функции Химмельблау f(x)=(x1*x1+x2-11)*(x1*x1+x2-11)+(x1+x2*x2-7)*(x1+x2*x2-7) с точностью e=0.01}

program spusk;

uses crt;

const n=2; k=2;

type vector=array[1..n] of real;

var i:integer;

d,e,e1,h,h1,z:real;

x:vector; ch:char;

procedure pausa;

begin

writeln;

writeln ('Для выхода нажмите любую клавишу…');

repeat ch:=readkey until ch <> '';

end;

function f(x:vector):real;

var a,b:real;

begin a:=x[1]*x[1]+x[2]-11;

b:=x[1]+x[2]*x[2]-7;

f:=a*a+b*b;

end;

procedure scan (i:integer);

var a:boolean;

d1,z1:real;

begin z:=f(x);

repeat d1:=abs(h1); x[i]:=x[i]+h1; z1:=f(x); a:=(z1>=z);

if a then h1:=-h1/k;

z:=z1;

until a and (d1

end;

begin

clrscr;

writeln ('Введите координаты начального вектора (x1,x2):');

for i:=1 to n do read (x[i]);

writeln ('Задайте точность нахождения точки min f(x):');

read (e);

h:=0.2; e1:=e/k;

repeat d:=abs(h);

for i:=1 to n do

begin

h1:=h; scan (i);

end;

h:=h/k;

until d

writeln ('Точка минимума: x1=',x[1]:9:6,' ','x2=',x[2]:9:6);

writeln ('Погрешность:',e:9:6);

pausa;

end.

Приложение 2

Результат работы программы:

Введите координаты начального вектора (x1,x2):

1

2

Задайте точность нахождения точки min f(x):

0.01

Точка минимума: x1= 2.996875 x2= 2.000000

Погрешность: 0.010000

Для выхода нажмите любую клавишу.

1 Множество компактно, если из каждого бесконечного и ограниченного его подмножества можно выделить сходящуюся последовательность.

2 Множество замкнуто, если предел любой сходящейся последовательности его элементов принадлежит этому множеству.

3 Это верно не при всяких делениях отрезка, но для деления в соответствии (4) это справедливо.

4 См. предыдущую сноску.

5 Квадратичная форма называется положительно определенной, если при любых (за исключением обращающихся одновременно в нуль) она положительна.

32

Характеристики

Список файлов курсовой работы