Тема: Алгоритмы поиска экстремума функции многих переменных icon

Тема: Алгоритмы поиска экстремума функции многих переменных



НазваниеТема: Алгоритмы поиска экстремума функции многих переменных
страница1/2
Дата конвертации05.09.2012
Размер260.98 Kb.
ТипМетодические указания
  1   2
1. /lab_examp.doc
2. /Лаба 2 мотыль.doc
3. /Лаба 3 мотыль.doc
4. /Лаба 4 мотыль.doc
5. /Ложкин/другие/MOTK/ARA/0123.doc
6. /Ложкин/другие/MOTK/ARA/123.doc
7. /Ложкин/другие/MOTK/ARA/321.doc
8. /Ложкин/другие/MOTK/ARA/3210.doc
9. /Ложкин/другие/MOTK/lab_4_2000.rtf
10. /Ложкин/лаба 1/лаба 1.doc
11. /Ложкин/лаба 2/лаба 2.doc
12. /Ложкин/лаба 3/лаба 3.doc
13. /Ложкин/лаба 4/лаба 4.doc
14. /Ложкин/лаба 5/лаба 5.doc
15. /Ложкин/лаба 6/Отчёт по л.р. ь 6.doc
16. /Ложкин/лаба 6/лаба 6.doc
17. /Математические основы кибернетики_Мойталенко/МЕТ1_M.doc
18. /Математические основы кибернетики_Мойталенко/Титульник.doc
19. /Математические основы кибернетики_Мойталенко/отчет ь1.doc
20. /Мотайленко лабы/Отчёт по л.р. ь 2.doc
21. /Мотайленко лабы/Отчёт по л.р. ь 3.doc
22. /Мотайленко лабы/Отчёт по л.р. ь 4.doc
Тема: Алгоритмы поиска экстремума функции многих переменных
Выполнили: Студенты группы 084-091
Выполнили: студенты группы 084-091
Выполнили: студенты группы 084-091
Лабораторная работа №1 по дисциплине «Математические основы технической кибернетики» «Задача об определении кривой минимальной длины»
Лабораторная работа №2 по дисциплине «Математические основы технической кибернетики» «Задача о брахистохроне»
Лабораторная работа №3 по дисциплине «Математические основы технической кибернетики» «Задача Дидо»
Лабораторная работа №4 по дисциплине «Математические основы технической кибернетики» «Задача о минимизации переправы лодки через реку»
html">Лабораторная работа №5 по дисциплине «Математические основы технической кибернетики» «Синтез регуляторов по быстродействию»
Выполнили: Студенты группы 084-093
Лабораторная работа №6 по дисциплине «Математические основы технической кибернетики»
Введение
Псковский государственный политехнический институт Кафедра вт отчет по лабораторной работе №1
Псковский государственный политехнический институт
Выполнили: Студенты группы 083-094с леонов А. С. Смирнов С. М. Преподаватель
С. М. Преподаватель: Мотайленко Л. В. Псков 2007 Задача
С. М. Преподаватель: Мотайленко Л. В. Псков 2007 Задача

Методические указания

к исследовательской лабораторной работе по дисциплине

Математические основы кибернетики”

Тема: Алгоритмы поиска экстремума функции многих переменных.


Вопросы для исследования:

  1. Изучить постановку задачи и алгоритмы поиска экстремума функции многих переменных.

  2. Рассмотреть, проанализировать и сопоставить различные способы определения шага в алгоритмах наискорейшего спуска.

  3. Ознакомиться с принципами использования метода наискорейшего спуска в задаче оценки параметров объектов (задаче параметрической идентификации).


1. Необходимые теоретические сведения


1.1. Назначение задач поиска экстремума функции многих переменных

Прикладные задачи:

  1. Определение неизвестных параметров (коэффициентов) объекта управления (эмпирической формулы) по результатам последовательных наблюдений за входными воздействиями (причиной, вектором xi размерности n*1) и процессом на выходе (следствием, скаляром yi) для i = 1, ... , N (N - общее число наблюдений). Структура связи причина следствие считается заданной с точностью до k-мерного вектора неизвестных параметров a, определение которого и составляет существо прикладной задачи). Такая задача называется задачей параметрической идентификации.

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

Несмотря на различия, первая и вторая задачи имеют общие черты, позволяющие рассматривать их на единой теоретической базе:

  1. наличие нелинейной скалярной функции, имеющей (по крайней мере) один экстремум;

  2. отсутствие ограничений на значения искомого вектора параметров.

Значение для теории оптимизации:

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

1.2. Общая форма алгоритма наискорейшего спуска для решения

задачи нахождения экстремума функции многих переменных


Далее всюду будем рассматривать задачи нахождения минимума скалярной функции f(x) векторного аргумента (без ограничений общности: задача нахождения максимума ­решается так же с помощью переобозначения функции: эквивалентно ).

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

(1)

Общая формула для нахождения значения аргумента x(k+1) по значению x(k), найденному на k-м шаге работы алгоритма наискорейшего спуска:

(2)

где: s(k) - вектор единичной длины в направлении, противоположном направлению градиента f(x), определенном в точке x(k) (далее будет использоваться обозначение );




- норма (например, длина) вектора градиента f(x(k)):



- шаг градиентной процедуры (определяет число векторов единичной длины (если >0 - целое) или долей длины вектора (если  дробное), которое укладывается в направлении, противоположном градиенту при совершении (k+1)-го шага).

Геометрическая интерпретация алгоритма наискорейшего спуска: траектория x(k) ортогональна линиям равного уровня минимизируемой функции. Поскольку шаг движения к экстремуму имеет конечную длину, по мере перемещения к точке x(k+1) ортогональность нарушается. В точке x(k+1) направление корректируется и снова становится ортогональным к линиям равного уровня.

1.3. Классификация алгоритмов наискорейшего спуска


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

Классификация способов определения шага представлена на рис. 1.

Рис.1. Классификация способов определения шага в алгоритмах наискорейшего спуска

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


1) Если шаг (k) не зависит от k (является постоянным), то в окрестности экстремума будут наблюдаться незатухающие колебания, амплитуда которых зависит от величины  и от формы минимизируемой функции. Например, если функция имеет овраг, вытянутый вдоль одной из координат (пусть для конкретности вдоль j-той координаты), то частная производная минимизируемой функции по этой координате мала, значение проекции sj (k) на эту координату также мало, и колебания невелики. По тем координатам, вдоль которых функция f(x) в окрестности экстремума изменяется сильнее, колебания будут иметь большую амплитуду. В любом случае амплитуда колебаний пропорциональна величине .

Мы видим, что использование постоянного шага:

  1. позволяет построить наиболее простой вариант алгоритма;

  2. при больших значениях  обеспечивает быстрое движение к экстремуму, но приводит к заметным колебаниям в его окрестности;

  3. при малых значениях  приводит к низкой скорости сходимости к экстремуму;

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

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

, a, b, - положительные константы;

, d,  - положительные константы.

Наряду с очевидными достоинствами (простота и устранение колебаний при ) алгоритм имеет и недостаток, связанный с оторванностью значений (k) от формы минимизируемой функции. Если вдали от экстремума функция f(x) имеет малый градиент, то шаг успеет сильно уменьшиться еще вдали от экстремума. Из-за этого сходимость к экстремуму может оказаться недопустимо медленной.

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

1.5. Алгоритм наискорейшего спуска с шагом, длина которого зависит от свойств минимизируемой функции (использование производной по направлению)


Пусть найдена точка x(k) и в этой точке определено направление движения к минимуму, задаваемое вектором единичной длины s(k) (формула (3)). Тогда из (2) видно, что положение следующей точки x(k+1) и значение функции f(x(k+1)) в этой точке зависят только от единственной скалярной переменной (k). Возникает идея не изменять направления поиска (и соответственно не расходовать ресурсов ЭВМ) до тех пор, пока функция f(x) в направлении s(k) убывает (улучшается). Точка x(k+1) соответствует минимуму f(x) по направлению s(k).

В точке x(k+1) должно быть определено новое направление движения к минимуму s(k+1). Это направление будет ортогональным предыдущему s(k).

Значение (k) определим из условия минимума функции, являющейся квадратической аппроксимацией f(x) в точке x(k):

(ряд Тейлора с двумя слагаемыми) 

(5)

где ;

- матрица вторых производных, вычисленная в точке x(k):




После подстановки x(k) = ( k) s(k) в (5) получим:



(7)

Условие минимума квадратической аппроксимации f(x(k+1)) по ( k) (скаляру!):




Из (8) получим формулу для определения шага:



Последовательность вычислений для реализации алгоритма:

  1. задать (произвольно) точку начального приближения x(0);

  2. в цикле по номеру итерации k=0,1,… вычислить:

  3. значение вектора градиента в точке x=x(k) по формуле (1);

  4. значение нормы (длины) вектора градиента по (4);

  5. значение вектора единичной длины в направлении, противоположном вектору градиента s(k) по формуле (3);

  6. значение матрицы вторых производных  2f(x(k)) по (6);

  7. значение шага (k) по (9);

  8. новое значение приближения x(k+1) по (2);

  9. закончить итерационный процесс, используя одно из следующих условий:

  10. если по постановке задачи пользователя интересует значение функции в точке оптимумане значение аргумента x), то следует прекратить вычисления, если, начиная с k* - той итерации абсолютное значение нормированной разности между значениями функции в “соседних” не превышает наперед заданного малого числа :



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

  1. если же по постановке задачи пользователя интересует именно значение аргумента (а не функции), то следует прекратить вычисления, если, начиная с k** - той итерации Ошибка! Ошибка внедренного объекта. абсолютное значение нормированной разности между значениями аргумента в “соседних” точках не превышает наперед заданного малого числа Ошибка! Ошибка внедренного объекта.:



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

Можно было бы ожидать, что оба условия почти эквивалентны. Однако, это справедливо только в том случае, когда функция f(x) не имеет оврага по “дну” которого из-за малого значения градиента сходимость к точке минимума будет очень медленной. Поскольку при этом значение функции f(x) почти не изменяется (и если пользователя интересует именно функция), то процесс можно прервать сразу при достижении любой точки на “дне” оврага. Если же требуется найти значение аргумента, то приходится продолжать движение (к сожалению, медленно) по оврагу до окрестности минимума.

При использовании обоих правил остановки необходимы страховочные меры для предотвращения слишком длительных вычислений (наиболее простая из них – прерывание вычислений при Ошибка! Ошибка внедренного объекта., k*** - большое число порядка 105).

1. 6. Алгоритм наискорейшего спуска с шагом, длина которого зависит от свойств минимизируемой функции (использование вторых производных). Метод Ньютона


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

Вычисляя точку нового приближения по формуле: x(k+1)=x(k)+x(k) и разлагая f(x(k+1)) в ряд Тейлора, получим формулу квадратической аппроксимации fкв(x(k+1)):

, где




fкв(x(k+1))= f(x(k))+ [f(x(k))]T  x(k) +(1/2!)  [ x(k)]T 2f(x(k))  x(k) (12)

2f(x(k) – матрица вторых производных (см. формулу 6).

Условие минимума fкв(x(k+1)) по  x(k) : . Вычислим градиент из (12) и найдем значение  x(k) :



fкв(x(k+1))= fкв(x(k))+  2fкв(x(k))   x(k) = 0 (13)

Для учета фактических особенностей минимизируемой функции будем использовать в (13) значения градиента и матрицы вторых производных, вычисленных не по аппроксимирующей fкв( . ), а непосредственно по минимизируемой функции f(x). Заменяя

fкв( . ) в (13), найдем длину шага  x(k) :



x(k) = -[ 2f(x(k))]-1 f(x(k)) (14)

Последовательность вычислений для реализации алгоритма:

  1. задать (произвольно) точку начального приближения x(0);

  2. в цикле по номеру итерации k=0,1,… вычислить:

  1. значение вектора градиента в точке x=x(k) по формуле (1);

  2. значение матрицы вторых производных 2f(x(k)) по формуле (6);

  3. значение матрицы обратной матрице вторых производных ;

  4. значение шага по формуле (14);

  5. новое значение приближения x(k+1) по формуле (2);

  1. закончить итерационный процесс, используя одно из условий, описанных в п 1.5.

Достоинства метода Ньютона:

  1. если минимизируемая функция является квадратической, то метод позволит найти минимум за один шаг;

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

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

Недостатки метода Ньютона связаны с необходимостью вычислений и (главное!) обращения матриц вторых производных. При этом не только расходуется машинное время, но (это существеннее) могут появиться значительные вычислительные погрешности, если матрица 2f(x(k)) окажется плохо обусловленной (т.е. значение определителя этой матрицы будет близко к нулю).


2. Методика проведения работы


Существо лабораторной работы состоит в исследовании и сопоставлении различных модификаций метода наискорейшего спуска.


2.1. Общие положения

Данная лабораторная работа выполнена в виде страницы электронной книги в среде MathCad 7.0. Открыть лабораторную работу можно из основного меню электронной книги. Каждая из модификаций метода наискорейшего спуска описана в Электронном приложении 6. Все формулы в этом приложении “живые”, что позволит провести все необходимые исследования описанных выше алгоритмов. Кроме основной своей цели лабораторная работа позволяет продолжить освоение пакета программ MathCad 7.0 , в том числе познакомиться с символьными преобразованиями и построением различных видов трехмерных графиков.


2.2. Методика вычислительных экспериментов


Вычислительный эксперимент №1. Тема: Исследование алгоритмов наискорейшего спуска с шагом, не зависящим от свойств минимизируемой функции

Эксперимент 1: Исследование алгоритмов с постоянным шагом.

  1. Для f(x,y) с =1 (круговой параболоид) исследовать скорость сходимости, амплитуды автоколебаний по аргументам и функции от величины шага . Факт сходимости устанавливайте по достижению режима колебаний аргументов с постоянными амплитудами Ax и Ay, фиксируйте эти амплитуды и соответствующие им амплитуды автоколебаний значения минимизируемой функции Af(x,y). Изменяйте шаг в диапазоне =0.05…2.0 с приращением d=0.1. Постройте графики зависимостей Ax, Ay и Af(x,y) от шага . Для контроля обязательно вычисляйте размах колебаний аргумента (определяется как квадратный корень из (Ax)2+(Ay)2 ). Этот размах должен быть равен шагу с точностью до округлений.

Возможно, при малых значениях шага  максимального числа итераций , предусмотренного в исходном варианте (т.е. 20), окажется недостаточно для достижения сходимости, тогда увеличьте его.

Убедитесь. Что значение шага  выбирается из условия компромисса между скоростью сходимости (чем больше , тем лучше) и величиной автоколебаний (чем больше , тем хуже). Постройте график связи числа шагов до сходимости и размаха автоколебаний (получится область неулучшаемых решений, иначе – область Парето).

  1. Убедитесь, что факт сходимости не зависит от выбранной точки начального приближения (для этого варьируйте x0,y0).

  2. Исследуйте, как изменяется характер сходимости при появлении оврага. Для этого варьируйте значения параметра в формуле для минимизируемой функции в диапазоне =0.3…3 с шагом d=0.5. Рассмотрите по графику, как меняется форма функции.

Обратите внимание на изменение характера траектории движения к экстремуму и автоколебаний вблизи экстремума. Объясните, почему кривая имеет такую форму.

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


Эксперимент 2: Исследование алгоритмов с переменным шагом (убывающим с ростом числа итераций).

  1. Установите параметр =1 в формуле для f(x,y). Измените значения параметров в формуле для определения длины шага, например, установите =0.5, =0.3 в формуле для функции Step. Внимательно проследите, к чему приведет такая замена (должна ухудшиться скорость сходимости и уменьшится амплитуда автоколебаний).

Исследуйте зависимость числа итераций, необходимых для достижения сходимости и амплитуды автоколебаний в зависимости от параметра  (изменяйте его в диапазоне от 0.1 до 1.5 с шагом 0.1), постройте соответствующие графики. При больших значениях параметра  максимального числа итераций max , предусмотренного в исходном варианте (т.е. 20), окажется недостаточно для достижения сходимости, тогда увеличьте его.

  1. Испытайте какую-либо другую формулу убывания шага, например, =e- при =1 и =0.4. Постройте график зависимости числа итераций, обеспечивающих сходимость, от параметра  (факт сходимости фиксируйте по достижению точки с координатами минимума xmin=0 ymin=0, с точностью до округлений, т.е. когда выводимые в таблицу значения станут нулями).


Вычислительный эксперимент №2. Тема: Исследования алгоритмов с шагом, зависящим от формы функции

  1. Убедитесь, что алгоритм сохраняет высокую скорость сходимости при изменении формы минимизируемой функции. Для этого изменяйте один из параметров формулы функции (например, lx в диапазоне от –1 до 1). Следите, чтобы график функции f(x,y) сохранял “экстремальную” форму (при нескольких сочетаниях параметров она теряется). Постройте графики зависимости числа итераций, необходимых для достижения сходимости, от этого параметра.

  2. Замените (при исходных значениях параметров миинимизируемой функции) данный алгоритм на алгоритм с постоянным шагом. Сравните результаты.

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


Вычислительный эксперимент №3. Тема: Исследование метода Ньютона

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

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

  3. Оформите результаты (приведите графики, таблицы и комментарии). Сделайте вывод об области применимости и сравнительной эффективности всех исследованных в данной лабораторной работе алгоритмов.



3. Содержание отчета по лабораторной работе.


  1. Краткий конспект теоретической части.

  2. Результаты вычислительных экспериментов и комментарии к ним.

  3. Краткий сравнительный анализ всех рассмотренных алгоритмов.



ПРИЛОЖЕНИЯ

Приложение 1


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

Простейший вариант метода наискорейшего спуска рассмотрим на примере поиска минимума квадратической функции f(x,y) = x2 +y2 двух переменных с оврагом, пологость которого определяется параметром .

Прифункция f(x,y) представляет собой круговой параболоид.

При >1 параболоид становится эллиптическим, "вытягиваясь" вдоль оси x (при <1 - вдоль оси y).

Свойства минимизируемой функции

Представление о функции легче всего получить по ее графику. Используем для этого средства MathCad. Необходимо провести следующие операции:

а) задаться значением параметра ;

б) задаться числом точек отсчета по осям x, y и пронумеровать эти точки;

в) определить формулу для расчета координат x и y по заданному номеру точек (иными словами, задать величины дискретных отсчетов , между точками);

г) только после этого записать формулу функции с использованием знака оператора присваивания - в виде f(x,y) := x2 +y2;

д) подготовить матрицу значений функции в точках дискретных отсчетов (она понадобится для вывода графика);

е) вывести трехмерный график;

ж) преобразовать график в чертеж линий равного уровня (проекций сечений поверхности f(x,y) плоскостями f(x,y)= const)

з) "поэкспериментировать" с графиком - изменяя , убедиться в появлении оврага.

Проделаем выше описанные операции.

- значение параметра, определяющего пологость оврага.

- точки отсчета по оси x;

- точки отсчета по оси y;

- расчет координаты x, соответствующей точке i, и координаты y, соответствующей точке j;

- формула для расчета квадратической функции;

- формула для вычисления точек f(x,y) по значениям дискретных аргументов (элементов [i j] матрицы M).

Для того чтобы построить трехмерный график выберите в меню Graph пункт Surface Plot или нажмите сочетание клавиш Ctrl-2. Появится заготовка графика со слотом в нижнем левом углу, в который нужно вставить идентификатор поверхности (M). Для того чтобы преобразовать полученный график в чертеж линий равного уровня щелкните два раза мышью внутри области графика и в появившемся диалоговом окне выберите Contour Plot . Вы можете построить новый график линий равного уровня с помощью позиций меню Graph, Contour Plot или сочетания клавиш Ctrl-5.



Рис. 1 График минимизируемой функции Рис.2 Линии равного уровня для f(x,y)

На каждой линии равного уровня показаны значения, которые принимает функция. Мы видим, что линии равного уровня являются проекциями сечений поверхности f(x,y) плоскостями f(x,y) = const на плоскость XOY.


Подготовка данных для алгоритма наискорейшего спуска

В основной части описания лабораторной работы указывается, что для алгоритма наискорейшего спуска требуются следующие исходные данные:

а) координаты точки начального приближения x(0), y(0)(выбираются произвольно);

б) значение минимизируемой функции в этой точке f(x(0), y(0));

в) значение длины шага ;

г) максимальное число max итераций процесса движения к точке минимума.


Параметры и расчетные формулы для градиентного метода

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

- диапазон изменения номера итераций;

- начальное значение аргумента x;

- начальное значение аргумента y;

- значение минимизируемой функции в начальной точке;

- начальное значение шага к экстремуму.

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

Скопируем формулу для f(x,y) в свободную зону MathCad и рассчитаем элементы вектора градиента (которые являются частными производными f(x,y) по каждому аргументу).

Для того чтобы рассчитать частные производные f(x,y) по каждому аргументу:

- выделите (щелчком мыши) переменную (например, x) в формуле f(x,y);

- выберите позицию Меню Symbolics - Varifble - Differentiate;

- MathCad выведет частную производную по x, но обозначит ее как f(x,y);

- исправьте обозначение - например, замените на g_x(x,y);

- проделайте те же действия с аргументом y.

Будут получены формулы для частных производных функции f(x,y) по агрументам x, y - т.е. элементы вектора градиента этой функции.

- копия формулы для минимизируемой функции.

- частная производная по x после переобозначения.

- частная производная по y после переобозначения.

Теперь запишем формулы для определения элементов вектора - единичного шага в сторону, обратную направлению градиента:

а) Длина вектора (корень из суммы квадратов его элементов):

Знак корня набирается либо с арифметической панели (arithmetical palette, иконка с калькулятором), либо нажатием клавиши "обратный слэж" (\).



б) Проекции s_x(x,y) и s_y(x,y) на оси x,y шага единичной длины в направлении, противоположном направлению вектора градиента:



в) Формула для зависимости длины шага от номера такта (в первом задании шаг постоянен):

- параметры формулы для определения шага.



Для постоянного шага=1, =1, =0.

г) Определяем вектор начальных значений для итеративной градиентной процедуры. Компоненты вектора:

- итеративно изменяющееся значение аргумента x;

- итеративно изменяющееся значение аргумента y;

- значение минимизируемой функции.

Создаем вектор размерности 3*1. Присваиваем переменным с индексами их значения (для функции f(x,y) просто указываем значения аргументов). Получится:




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

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

Именно поэтому формула для f(x,y) записана так "длинно".



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

В рассматриваемом примере эта точка очевидна: x*=0, y*=0, f(x*,y*)=0.

Для вывода таблиц наберите идентификатор переменной (при необходимости- с индексом) и знак равенства.



По таблице можно установить, сколько тактов занял процесс сходимости к минимуму: при исходном сочетании параметров (=1, =0.3) автоколебания ( +0.122...-0.147 по оси x, -0.061...+0.073 по оси y и +0.09... +0.027 для f(x,y) имеют место начиная с 7-го такта. Рассчитаем амплитуду колебаний по аргументам:



(мы видим, что, как и следовало ожидать, с точностью до вычислительной погрешности значение амплитуды совпадает с величиной шага  =0.3).

Выведем графики, показывающие зависимости аргументов x,y и значений функции f(x,y) от номера итерации.

Выведем отдельный график изменения значения f(x,y) (поскольку масштабы функции и аргумента сильно разнятся, совмещение на одном графике нецелесообразно).



Рис.3 Сходимость к точке минимума Рис.4 Изменение значения

минимизируемой функции.

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

Движение к минимуму осуществляется по траектории, показанной на рис.5.



Рис.5 Пошаговое движение к минимуму

Для вывода графика, иллюстриру.эжхз-0ющего характер движения к минимуму, используйте "мастер" графиков (укажите Step в списке Trace Type).

Рис.5 показывает, что в окрестности минимума (x=0, y=0) происходят автоколебания. Будет также заметно, что проекция градиента перпендикулярна линиям равного уровня функции f(x,y) (в рассматриваемом примере - эллипсам, эксцентриситет которых зависит от коэффициента  в формуле для f(x,y) ).

Если параболоид круговой (т.е.=1), то амплитуда колебаний по обеим переменным одинакова (убедитесь в этом).


  1   2



Похожие:

Тема: Алгоритмы поиска экстремума функции многих переменных iconТема: «Применение производной для решения задач егэ по физике и математике» Тип
Повторение алгоритма решения задач на физический смысл производной и нахождение экстремума функции
Тема: Алгоритмы поиска экстремума функции многих переменных iconВ. Л. Вольфсон, канд техн наук Алгоритмы оптимального проектирования асу в задачах с известной целевой функцией, обладающей свойством доминирования
Мотренные алгоритмы применимы к задачам с целевой функцией (ЦФ) булевых и целочисленных переменных, обладающей свойством доминирования....
Тема: Алгоритмы поиска экстремума функции многих переменных iconУрок: «типы алгоритмов. Линейные алгоритмы» Тема: Типы алгоритмов. Линейные алгоритмы. Класс: 8 класс Цели урока: · познакомить учащихся с типами алгоритмов
Откройте тетради. Запишите тему урока: «Типы алгоритмов. Линейные алгоритмы»
Тема: Алгоритмы поиска экстремума функции многих переменных iconЭффективный поиск в Интернете
Всегда ли вы находите то, что ищете? В чем заключается основная ваша проблема? Считаете ли вы себя профессионалом в процедуре поиска?...
Тема: Алгоритмы поиска экстремума функции многих переменных iconУрок №1 Тема: Линейная функция и ее график
Цели: ввести понятие линейной функции, научить находить по формуле значение аргумента и значение функции; научить составлять формулу...
Тема: Алгоритмы поиска экстремума функции многих переменных iconДела студентов групп 01150– Институт информационных коммуникаций. 2012/2013 учебный год
Задание 1: Эксперимент по сравнению эффективности поиска сведений в Интернете. Выполнять по методическим указаниям здесь на сайте...
Тема: Алгоритмы поиска экстремума функции многих переменных iconПрактика ртф 150, 170
Повт: производные, частные производные, градиент и его геометрический смысл, экстремумы функции от 2 переменных, задача про min s...
Тема: Алгоритмы поиска экстремума функции многих переменных iconУрок №5 Тема: Прямая пропорциональность
Цели урока: упражнять учащихся в построении графиков прямой пропорциональности и линейной функции, учить находить с помощью графика...
Тема: Алгоритмы поиска экстремума функции многих переменных iconНазаркина Татьяна Николаевна Школа: моу «Лицей №43» г. Саранск Тема урок
Задачи: научить учащихся определять бесконечно малые и бесконечно большие функции при различных значениях параметров и вычислять...
Тема: Алгоритмы поиска экстремума функции многих переменных iconТема работы
Исследование эффективности поиска в Интернете по запросу «Информационно-поисковые системы»
Тема: Алгоритмы поиска экстремума функции многих переменных iconТема урока Кол-во
Уметь записывать условие ветвления в алгоритме, используя слова «если» и «то», выполнять алгоритмы с ветвлениями
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов