12249

Методы минимизации функции одной переменной, использующие информацию о производных целевой функции

Лабораторная работа

Информатика, кибернетика и программирование

Лабораторная работа 2. Методы минимизации функции одной переменной использующие информацию о производных целевой функции. Постановка задачи: Требуется найти безусловный минимум функции одной переменной fx т.е. такую точку что . Значение точки минимума вычисл

Русский

2013-04-24

781.11 KB

30 чел.

Лабораторная работа 2.

Методы минимизации функции одной переменной,

использующие информацию о производных целевой функции.

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

В лабораторной работе № 1 были рассмотрены прямые методы решения задачи минимизации функции одной переменной. В данной работе рассматриваются методы минимизации, которые используют информацию о производной целевой функции.

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

Метод средней точки.

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

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

Алгоритм:

  1. Задать начальный интервал неопределенности L0 и точность ε.
  2. Положить . Вычислить .
  3. Проверка на окончание поиска: если , то положить ,  и завершить поиск, иначе – перейти к шагу 4.
  4. Сравнить  с нулем. Если , то продолжить поиск на отрезке , положив , иначе перейти к отрезку , положив . Перейти к шагу 2.

Метод хорд.

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

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

Координата этой точки равна:

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

Алгоритм:

  1. Выбрать начальный интервал неопределенности L0 и точность .
  2. Вычислить значения , .
  3. Положить , , , .
  4. Вычислить точку и значение .
  5. Если , то перейти к шагу 8.
  6. Если , то положить , , в противном случае положить , .
  7. Перейти к шагу 4.
  8. Выбрать приближенно , . Поиск завершен.

Метод Ньютона (метод касательных).

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

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

Выберем в качестве следующего приближения к  точку  пересечения касательной с осью абсцисс:

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

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

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

Алгоритм:

  1. Выбрать начальное приближение x0, точность ε и предельное число итераций M.
  2. Положить k = 0 (k – номер итерации).
  3. Вычислить , .
  4. Вычислить точку и значения производных , .
  5. Если , то перейти к шагу 8.
  6. Положить k = k +1.
  7. Если k < M  перейти к шагу 4, в противном случае завершить поиск (последовательность расходится, необходимо повторить поиск с другим начальным приближением).
  8. Выбрать приближенно , . Поиск завершен.

Вопросы и задания

  1. Написать функции, реализующие три предложенных метода.
  2. Выбрать для выполнения лабораторной работы тестовую функцию, номер которой соответствует последней цифре номера Вашего компьютера (данная функция совпадает с функцией, использованной в лабораторной работе 1)
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  
  11.  
  12.  
  13. Для выбранной функции и для каждого реализованного метода изучить зависимость скорости работы (числа вычислений функции N) от заданного значения точности ε. Для этого необходимо определить число вычислений функции N при нескольких (от трех до пяти) значениях точности, например, при  и построить график зависимости .
  14.  Провести сравнение методов между собой: сравнить сложность реализации, скорость работы (точность). Какой из рассмотренных методов более оптимален для низкой точности () и для высокой точности ()?
  15.  Сравнить результаты полученные в настоящей работе с результатами, полученными в работе 1.

 

А также другие работы, которые могут Вас заинтересовать

76871. Центральные органы иммунной системы 184.18 KB
  Общая масса костного мозга medull ossium составляет 253 кг 4547 от массы тела около половины приходится на красный мозг medull ossium rubr столько же на желтый – medull ossium flv. В красном костном мозге благодаря многократному делению – более 100 раз росту и усложнению структуры стволовые клетки превращаются в эритроциты лейкоциты лимфо и моноциты тромбоциты. Влимфоциты образующиеся в красном мозге участвуют в реакциях гуморального иммунитета вырабатывая антитела.
76872. Периферические иммунные органы 184.32 KB
  В белой пульпе вокруг ветвей и веточек селезеночной артерии располагаются лимфоидные узелки сформированные в периартериальные лимфоидные влагалища вокруг пульпарных ветвей эллипсоидные диски с осевым смещением вокруг центральных веточек и гильзы вокруг кисточковых артериол. В петлях сети находятся лимфоидные узелки и диффузная лимфоидная ткань. Корковое вещество лежит под капсулой и содержит лимфоидные узелки в 051 мм диаметром часть из них имеет центры размножения.
76873. Селезенка (lien, splen) и ее строение 182.4 KB
  Селезенка lien splen располагается глубоко в преджелудочной сумке верхнего этажа брюшной полости проецируется в левой подреберной области на уровне IXXI ребер. Селезенка лиен сплен имеет: массу в 20 40 лет у мужчин 192 г у женщин 153 г; длину в 1014 см ширину в 610 см толщину в 34 см; цвет темнокрасный; поверхности: диафрагмальную выпуклую; висцеральную плоскую или слегка вогнутую с лежащим посредине углублением воротами; края: верхний передний острый нижний задний – тупой; концы: задний закругленный ...
76874. Значение нервной системы 184.15 KB
  Условно нервная система подразделяется: на центральную часть в составе головного и спинного мозга; на периферическую часть в составе черепных 12 пар и спинномозговых 31 пара нервов и образующих их корешков; нервных узлов нервных сплетений отдельных ветвей и их нервных окончаний в органах и тканях. Внутри головного мозга нейроны формируют скопления в виде крупных и мелких ядер и сети ретикулярной формации. Нервные волокна мозга подразделяются на ассоциативные комиссуральные и проекционные все они образуют проводящие пути для...
76875. Понятие о нейроне 187.43 KB
  Отростки нейронов нервные волокна в периферической системе образуют корешки пучки нервы и нервные сплетения. Главной частью нервного волокна является осевой цилиндр представляющий короткий или длинный вырост цитоплазмы окруженный внутренней оболочкой неврилеммой. Мякотные или миелиновые волокна которые содержат в наружной шванновской оболочке миелин химическое вещество липоидного характера. Безмякотные безмиелиновые волокна не содержат миелина в наружной оболочке.
76876. Спинной мозг 186.68 KB
  Пластинки возникают из нервного лентовидного гребня расположенного вдоль спинного мозга сзади. Утолщение стенок изменение общей формы развивающегося мозга сопровождается сужением центрального канала. У детей 35 лет и новорожденных сильнее выражены шейногрудное и поясничнокрестцовое утолщения спинного мозга.
76877. Развитие головного мозга 184.2 KB
  Стабилизация или элиминация межнейронных связей наступает в конце созревания мозга. Вначале 5ой недели разделяется задний пузырь для образования заднего и продолговатого мозга. Изза неравномерности роста развивающегося мозга появляются в пузырях сагиттальные изгибы ориентированные выпуклостью в дорсальную сторону первые два и вентральную третий: теменной изгиб самый ранний возникает в области среднемозгового пузыря отделяя средний мозг от промежуточного и конечного; затылочный изгиб в заднем пузыре отделяет спинной мозг от...
76878. Серое и белое вещество головного мозга 182.07 KB
  Базальные ядра хвостатое чечевицеобразное миндалевидное по происхождению и развитию подразделяются: на новые ядра неостриатум в составе хвостатого ядра и скорлупы чечевицеобразного; на старые ядра палеостриатум в составе бледных шаров: медиального и латерального; на древние архистриатум миндалевидное ядро и гиппокамп. Базальные ядра относят к подкорковым структурам. Среди базальных ядер выделяют стриапаллидарную систему включающую головку хвостатого ядра скорлупу и бледные шары. Хвостатое ядро nucleus cudtus имеет:...
76879. Верхнелатеральная поверхность полушарий 184.05 KB
  В функциональном отношении борозды и извилины с сосредоточенными в них полями и нейронами составляют ядра чувствительных или двигательных анализаторов. Они начинаются на лобном полюсе располагаются параллельно друг другу и заканчиваются у предцентральной извилины. Между ними находятся хорошо выраженные извилины: Верхняя лобная извилина часть которой лежит и на медиальной поверхности полушария. В середине нижней лобной извилины поле 45 располагается ядро анализатора пения при поражении которого возникают вокальная амузия и аграмматизм...