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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


практическая работа Нахождение экстремумов функций двух переменных приближёнными методами

Информация:

Тип работы: практическая работа. Добавлен: 18.09.2012. Сдан: 2011. Страниц: 4. Уникальность по antiplagiat.ru: < 30%

Описание (план):


ВСР №4. Тема: «Нахождение экстремумов функций двух переменных приближёнными методами».
Цель: изучить приближённые методы нахождение экстремумов функций двух переменных
Содержание  учебного материала:
    Функции нескольких переменных.
    Частные производные и полный дифференциал 1-го порядка.
    Градиент функции. Производная по направлению.
    Экстремум функции двух переменных.
    Приближённые методы решения задач.
      Метод Хука – Дживса.
      Метод Нелдера – Мида.
      Метод полного  перебора (метод сеток).
      Метод покоординатного  спуска.
    Примеры решения задач в MathCAD.
    Вопросы и задания.
    Список рекомендуемых источников.
Функции нескольких переменных
Определение. Переменная z называется функцией переменных х и у, если каждой паре значений х и у в некоторой области их изменения поставлено в соответствие  одно значение z. Функциональную зависимость z от х и у записывают в виде: z=f(x,у). Это уравнение определяет некоторую поверхность в пространстве R3
     Геометрическим образом функции z=x2+y2 является параболоид. Пусть z=a, тогда x2+y2=a, т.е. линия пересечения плоскости z= a с поверхностью z=x2+y2 есть окружность x 2+ y 2= a радиуса . Пусть у=0, тогда z=x2 и, следовательно, при пересечении плоскости Oхz с поверхностью получается парабола. Метод сечений дает возможность лучше представить себе геометрический образ данной функции.

 
 
       
     Определение. Число А называется пределом функции z=f(x,у) в точке М0(х0, у0), если для каждого числа ?>0 найдется такое число ?>0, что для всех точек М(х,у), для которых выполняется неравенство |ММ0|<?, будет выполняться неравенство | f(x,у)– A|< ? 
    

Обозначим
  . 
     Определение. Функция z=f(x,у) называется непрерывной в точке М0(х0,у0), если имеет место равенство

  .
 


Частные производные и  полный дифференциал 1-го порядка
Определение. Производная от функции z=f(x,у) по х, найденная в предложении, что у остается постоянным, называется частной производной от z по х и обозначается  или f'x (x,у). Аналогично определяется и обозначается частная производная z по у
     Если функция z=f(x,у) имеет в точке (х,у) непрерывные частные производные, то ее полное приращение может быть представлено в виде:  
     ,                                             (1) 
     где  при . 
     Определение.  Выражение  является главной частью полного приращения ?z и называется полным дифференциалом функции z=f(x,у) и обозначается dz
     .                                                          (2) 
     Полагая в формуле (2) z равным х, найдем , а при z=y . Поэтому  
     .                                                           (3) 
     Из (1) следует, что . 
     Функция f(x,y) называется дифференцируемой в точке (х,у), если она имеет в этой точке полный дифференциал. 
     Пример. Найти полный дифференциал функции . 
     Решение. Сначала найдем частные производные 
      
      
     Производная  найдена в предположении, что у постоянна, а  найдена в предположении, что х постоянна. По формуле (3): 
     . 
     Ответ. dz=(10 x–6xy3) dx+(9 x2 y2+6) dy.

Градиент  функции. Производная  по направлению
Определение. z=f(x,у) дифференцируемая функция двух переменных. Тогда вектор  называется градиентом функции z=f(x,у)
     Он обладает следующими свойствами: 
      
      
      
     Пусть  – направляющие косинусы некоторого вектора , т.е. . Тогда  – производная функции z=f(x,у) в данном направлении .

Экстремум функции двух переменных
Определение. Функция z=f(x,у) имеет в точке М0(х0,у0) максимум, если в окрестности этой точки выполняется равенство f(x,у)<f(x0,у0). 
      Аналогично определяется минимум функции z=f(x,у) в точке М0(х0, у0). 
Необходимый признак экстремума 
     Если М (х0,у0) – точка экстремума дифференцируемой функции z=f(x,у)), то  
      то есть

Достаточный признак экстремума 
     Пусть z=f(x,у) – функция, для которой существуют производные первого и второго порядка в точке М(х0,у0):     . Составим выражение ?=АС–В2
     Если ?>0, то М(х0, у0) – точка экстремума, а именно: точка максимума при A<0 (если C<0), точка минимума при A>0 (или С>0). Если ?<0, то в точке М нет экстремума.

Приближённые  методы решения задач
       Подавляющее число реальных задач оптимизации, представляющих практический интерес, являются многомерными: в них целевая  функция зависит от нескольких аргументов, причем иногда их число может быть весьма большим.
       Математическая  постановка таких задач аналогична их постановке в одномерном случае: ищется наименьшее (наибольшее) значение целевой функции, заданной на некотором множестве G возможных значений ее аргументов.
       Как и в одномерном случае, характер задачи и соответственно возможные  методы решения существенно зависят  от той информации о целевой функции, которая нам доступна в процессе ее исследования. В одних случаях целевая функция задается аналитической формулой, являясь при этом дифференцируемой функцией. Тогда можно вычислить ее частные производные, получить явное выражение для градиента, определяющего в каждой точке направления возрастания и убывания функции, и использовать эту информацию для решения задачи. В других случаях никакой формулы для целевой функции нет, а имеется лишь возможность определить ее значение в любой точке рассматриваемой области (с помощью расчетов, в результате эксперимента и т.д.). В таких задачах в процессе решения мы фактически можем найти значения целевой функции лишь в конечном числе точек, и по этой информации требуется приближенно установить ее наименьшее значение для всей области.
1. Метод Хука –  Дживса
     Этот  метод был разработан в 1961 году, но до сих пор является весьма эффективным и оригинальным. Поиск состоит из последовательности шагов исследующего поиска вокруг базисной точки, за которой в случае успеха следует поиск по образцу.
     Описание  этой процедуры представлено ниже:
     А. Выбрать начальную базисную точку b1 и шаг длиной hj для каждой переменной xj, j = 1, 2, ..., n. В приведенной ниже программе для каждой переменной используется шаг h, однако указанная выше модификация тоже может оказаться полезной.
     Б. Вычислить f(x) в базисной точке b1 с целью получения сведений о локальном поведении функции f(x). Эти сведения будут использоваться для нахождения подходящего направления поиска по образцу, с помощью которого можно надеяться достичь большего убывания значения функции. Функция f(x) в базисной точке b1 находится следующим образом:
     1. Вычисляется значение функции f(b1) в базисной точке b1.
     2. Каждая переменная по очереди  изменяется прибавлением длины  шага.
     Таким образом, мы вычисляем значение функции f(b1 + h1e1), где e1 - единичный вектор в направлении оси х1. Если это приводит к уменьшению значения функции, то b1 заменяется на b1 + h1e1. В противном случае вычисляется значение функции f(b1 – h1e1), и если ее значение уменьшилось, то b1 заменяем на b1-h1e1. Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b1 остается неизменной и рассматриваются изменения в направлении оси х2, т.е. находится значение функции f(b1 + h2e2) и т.д. Когда будут рассмотрены все n переменные, мы будем иметь новую базисную точку b2.
     3. Если b2 = b1, т.е. уменьшение функции не было достигнуто, то исследование повторяется вокруг той же базисной точки b1, но с уменьшенной длиной шага. На практике удовлетворительным является уменьшение шага (шагов) в десять раз от начальной длины.
     4. Если  , то производится поиск по образцу.
     В. При поиске по образцу используется информация, полученная в процессе исследования, и минимизация функции завершается поиском в направлении, заданном образцом. Эта процедура производится следующим образом:
     1. Разумно двигаться из базисной  точки b2 в направлении b2 - b1, поскольку поиск в этом направлении уже привел к уменьшению значения функции. Поэтому вычислим функцию в точке образца
           (5)
     В общем случае
           (6)
     2. Затем исследование следует продолжать  вокруг точки P1 (Pj).
     3. Если наименьшее значение на  шаге В,2 меньше значения в базисной точке b2 (в общем случае bj+1), то получают новую базисную точку b3 (bj+2), после чего следует повторить шаг В,1. В противном случае не производить поиск по образцу из точки b2 (bj+1) а продолжить исследования в точке b2 (bj+1).
     Г. Завершить этот процесс, когда длина шага (длины шагов) будет уменьшена до заданного малого значения.
     Ниже  приведена блок-схема данного  метода.

 
Рис. 2. 

 
Рис. 3. 
Метод Нелдера – Мида
     Метод Нелдера — Мида (называется также поиском по деформируемому многограннику) является развитием симплексного метода Спендли, Хекста и Химсворта. Множество (n + 1)-й равноудаленной точки в n-мерном пространстве называется регулярным симплексом. Эта конфигурация рассматривается в методе Спендли, Хекста и Химсворта. Следовательно, в двумерном пространстве симплексом является равносторонний треугольник, а в трехмерном пространстве — правильный тетраэдр. Идея метода состоит в сравнении значений функции в (n + 1) вершинах симплекса и перемещении симплекса в направлении оптимальной точки с помощью итерационной процедуры. В симплексном методе, предложенном первоначально, регулярный симплекс использовался на каждом этапе. Нелдер и Мид предложили несколько модификаций этого метода, допускающих, чтобы симплексы были неправильными. В результате получился очень надежный метод прямого поиска, являющийся одним из самых эффективных, если .
     В методе Спендли, Хекста и Химсворта симплекс перемещается с помощью трех основных операций: отражения, растяжения и сжатия. Смысл этих операций станет понятным при рассмотрении шагов процедуры.
     A. Найдем значения функции f1=f(x1),f2=f(x2) ... fn+1=f(хn+1) в вершинах симплекса.
     Б. Найдем наибольшее значение функции fh, следующее за наибольшим значением функции fg наименьшее значение функции fl и соответствующие им точки xh, xg, xl.
     B. Найдем центр тяжести всех точек, за исключением точки хh. Пусть центром тяжести будет
      (7)
     и вычислим f(x0)=f0.
     Г. Удобнее всего начать перемещение от точки xh. Отразив точку xh относительно точки х0, получим точку хr и найдем f(xr) = fr. Операция отражения иллюстрируется (Рис 4.). Если а > 0 - коэффициент отражения, то положение точки хr определяется следующим образом:
     
     т.е.
      (8)
     Замечание:
     Д. Сравним значения функций fr и fl.
     1. Если fr < fl, то мы получили наименьшее значение функции. Направление из точки x0 в точку xr наиболее удобно для перемещения. Таким образом, мы производим растяжение в этом направлении и находим точку xe и значение функции fe = f(xe). (рис. 5) иллюстрирует операцию растяжения симплекса.
     
      
Рис. 4. 

     
      
Рис. 5. 

     Коэффициент растяжения можно найти из следующих соотношений:
     
     т.е.
      (9)
     Замечание:
     а) Если fe < fl, то заменяем точку xh на точку xe и проверяем (n + 1)-ую точку симплекса на сходимость к минимуму (см. шаг Б). Если сходимость достигнута, то процесс останавливается; в противном случае возвращаемся на шаг Б.
     б) Если fe > fl, то отбрасываем точку xe. Очевидно, мы переместились слишком далеко от точки x0 к точке xr. Поэтому следует заменить точку xh на точку xr, в которой было получено улучшение (шаг Д, 1), проверить сходимость и, если она не достигнута, вернуться на шаг Б.
     2. Если fr > fl, но fr < fg, то xr является лучшей точкой по сравнению с другими двумя точками симплекса и мы заменяем точку xh на точку xr и, если сходимость не достигнута, возвращаемся на шаг Б, т.е. выполняем пункт 1,6, описанный выше.
     3. Если fr > fe и fr > fg, перейдем на шаг Е.
Е. Сравним значения функций fr и fh.
1. Если fr > fh, то переходим непосредственно к шагу сжатия Е,2.
Если fr < fh, то заменяем точку xh на точку xr и значение функции fh на значение функции fr. Запоминаем значение fr > fg из шага Д,2, приведенного выше. Затем переходим на шаг Е,2.
2. В этом случае fr > fh, поэтому ясно, что мы переместились слишком далеко от точки xh к точке x0. Попытаемся исправить это, найдя точку xc (а затем fc) с помощью шага сжатия, показанного на (Рис. 6) Если fr > fh, то сразу переходим к шагу сжатия и находим точку xc из соотношения

где - коэффициент сжатия. Тогда
(10)
Если fr < fh, то сначала заменим точку xh на точку xr, а затем произведем сжатие. Тогда точку xc найдем из соотношения

т.е.
(11)
(рис. 7).

 
Рис. 6. 


 
Рис. 7. 

Ж. Сравним значения функций fc и fh.
1. Если fc < fh, то заменяем точку xh на точку xc и если сходимость не достигнута, то возвращаемся на шаг Б.
2. Если fc > fh, то очевидно, что все наши попытки найти значение меньшее fh закончились неудачей, поэтому мы переходим на шаг 3.
3. На этом шаге мы уменьшаем размерность симплекса делением пополам расстояния от каждой точки симплекса до x1 - точки, определяющей наименьшее значение функции.
Таким образом, точка xj заменяется на точку , т.е. заменяем точку xi точкой
(12)
Затем вычисляем fi для i = 1, 2, ...,(n+1), проверяем сходимость и, если она не достигнута, возвращаемся на шаг В.
И. Проверка сходимости основана на том, чтобы стандартное отклонение (n + 1)-го значения функции было меньше некоторого заданного малого значения е. В этом случае вычисляется
(13)
где .
Если  , то все значения функции очень близки друг к другу, и поэтому они, возможно, лежат вблизи точки минимума функции xl. Исходя из этого, такой критерий сходимости является разумным, хотя Бокс, Дэвис и Свенн предлагают то, что они считают более "безопасной" проверкой.
Шаги этой процедуры  представлены в виде блок-схемы на рис. 8.
Коэффициенты  в вышеприведенной процедуре являются соответственно коэффициентами отражения, сжатия и растяжения. Нелдер и Мид рекомендуют брать . Рекомендация основана на результатах экспериментов с различными комбинациями значений. Эти значения параметров позволяют методу быть эффективным, но работать в различных сложных ситуациях.
Начальный симплекс выбирается на наше усмотрение. В данном случае точка x1 является начальной точкой, затем формируются точки
(14)
где k - произвольная длина шага, a ej - единичный вектор.

 
Рис. 8. 

 


Метод полного перебора (метод  сеток)

     Многомерные задачи, естественно, являются более  сложными и трудоемкими, чем одномерные, причем обычно трудности при их решении  возрастают при увеличении размерности. Для того чтобы вы лучше почувствовали это, возьмем самый простой по своей идее приближенный метод поиска наименьшего значения функции. Покроем рассматриваемую область сеткой G с шагом h (Рис. 9) и определим значения функции в ее узлах. Сравнивая полученные числа между собой, найдем среди них наименьшее и примем его приближенно за наименьшее значение функции для всей области.
     
      
Рис. 9. 
     Как мы уже говорили выше, данный метод  используется для решения одномерных задач. Иногда он применяется также  для решения двумерных, реже трехмерных задач. Однако для задач большей  размерности он практически непригоден из-за слишком большого времени, необходимого для проведения расчетов. Действительно, предположим, что целевая функция зависит от пяти переменных, а область определения G является пятимерным кубом, каждую сторону которого при построении сетки мы делим на 40 частей. Тогда общее число узлов сетки будет равно . Пусть вычисление значения функции в одной точке требует 1000 арифметических операций (это немного для функции пяти переменных). В таком случае общее число операций составит 1011. Если в нашем распоряжении имеется ЭВМ с быстродействием 1 млн. операций в секунду, то для решения задачи с помощью данного метода потребуется 105 секунд, что превышает сутки непрерывной работы. Добавление еще одной независимой переменной увеличит это время в 40 раз. Проведенная оценка показывает, что для больших задач оптимизации метод сплошного перебора непригоден. Иногда сплошной перебор заменяют случайным поиском. В этом случае точки сетки просматриваются не подряд, а в случайном порядке. В результате поиск наименьшего значения целевой функции существенно ускоряется, но теряет свою надежность.

Метод покоординатного  спуска

     Рассмотрим  функцию двух переменных. Ее линии  постоянного уровня представлены на рис. 10, а минимум лежит в точке . (Напомним, что линией постоянного уровня называется кривая в двумерном сечении пространства параметров (в данном случае в плоскости (х1, х2), значение функции на которой - константа). Простейшим методом поиска является метод покоординатного спуска. Из точки А
и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.