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.

 

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

71755. ИЗУЧЕНИЕ КОНСТРУКЦИЙ ПОДШИПНИКОВ КАЧЕНИЯ 1.05 MB
  Цель работы: ознакомиться с классификацией и конструкциями основных типов подшипников качения. 1 Классификация подшипников качения Подшипники качения классифицируют по следующим основным признакам: направление действия воспринимаемых нагрузок форме тел качения конструктивным...
71756. Типы и конструкции подшипников качения 225.5 KB
  Ознакомиться с типами и конструкциями наиболее распространенных подшипников качения и их условными обозначениями. Изучить конструкцию трех различных подшипников (получить у преподавателя), начертить их эскиз, измерить и поставить габаритные размеры и расшифровать их условное обозначение.
71757. Электротехнические материалы: Методические указания 344 KB
  Цель работы: Экспериментальное исследование магнитных характеристик ферромагнитных материалов. Снятие кривой намагничивания и гистерезисных циклов. Определение по кривой намагничивания магнитной проницаемости и ее зависимость от напряженности магнитного поля.
71758. ОПРЕДЕЛЕНИЕ ВАТТМЕТРОВЫМ МЕТОДОМ МАГНИТНЫХ СВОЙСТВ ЭЛЕКТРОТЕХНИЧЕСКОЙ СТАЛИ 340.5 KB
  Методические указания к лабораторной работе №7 по курсу «Электротехнические материалы» для студентов специальности 1-53 01 05 «Автоматизированные электроприводы» - ГУ ВПО «Белорусско-Российский университет», 2005 г. Методические указания содержат основные сведения о магнитных свойствах электротехнической стали.
71759. МАТЕРИАЛОВЕДЕНИЕ (Часть 2) 2.94 MB
  Изложены основные теоретические положения и методические указания к выполнению следующих лабораторных работ по курсу Материаловедение: Изучение зависимости между структурой и свойствами чугунов Закалка стали Отпуск закаленной стали Изучение зависимости между структурой и свойствами стали...
71760. МАТЕРИАЛОВЕДЕНИЕ (Часть 1) 1.87 MB
  Измерение твердости, вследствие быстроты и простоты осуществления, а также возможности без разрушения изделия судить о его свойствах, получило широкое применение для контроля качества металла в металлических изделиях и деталях. Существует целый ряд методов измерения твердости...
71761. МАТЕРИАЛОВЕДЕНИЕ (Часть 3) 1.47 MB
  Изложены основные теоретические положения и методические указания к выполнению следующих лабораторных работ по курсу Материаловедение: Химико-термическая обработка стали Цветные металлы и сплавы Выбор стали и назначение режима термической обработки.
71762. Исследование стабильности горения сварочной дуги переменного тока 905 KB
  Применяемое оборудование контрольно измерительные приборы и материалы При проведении лабораторной работы в распоряжении студента: сварочный трансформатор электроды электродо-держатель приспособление для закрепления электрода на штативе осциллограф С117 источник импульсного тока штангенциркуль.
71763. Исследование влияния силы сварочного тока на значения коэффициентов наплавки и расплавления 214.5 KB
  Основы теории тепловых процессов сварочной дуги и массопереноса металла через дуговой промежуток основные параметры электродуговой сварки Сварочная дуга является мощным концентрированным источником тепловой энергии. Однако не вся тепловая энергия выделяющаяся при горении...