40834

МЕТОДЫ НАХОЖДЕНИЯ МИНИМУМА ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ

Лекция

Математика и математический анализ

Постановка задачи Задача нахождения минимума функции одной переменной minfx нередко возникает в практических приложениях. Кроме того многие методы решения задачи минимизации функции многих переменных сводятся к многократному поиску одномерного минимума. Задача ставится следующим образом: требуется найти такое значение xm из отрезка [ b] при котором достигается минимум функции ym=fxm т.

Русский

2013-10-22

869.5 KB

92 чел.

ТЕМА 6. МЕТОДЫ НАХОЖДЕНИЯ МИНИМУМА ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ

6.1. Постановка задачи

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

Наиболее часто используемые методы можно разбить на два класса:

1) методы уточнения минимума на заданном интервале [a, b] (метод деления пополам, метод золотого сечения);

2) методы спуска к минимуму из некоторой начальной точки x0 (метод последовательного перебора, метод квадратичной параболы, метод кубической параболы).

Методы из класса 1 предназначены для нахождения условного минимума. Задача ставится следующим образом: требуется найти такое значение xm из отрезка [a, b], при котором достигается минимум функции ym=f(xm), т.е. для любого  выполняется условие .

 Методы из класса 2 предназначены для поиска и уточнения безусловного локального минимума. Задача ставится следующим образом: требуется найти такое значение  при котором достигается локальный минимум , т.е. для любого x из некоторой окрестности  выполняется     ym    f(x). В этом случае при нахождении точки  обычно нет достаточно точной информации о ее положении, более того, локальных минимумов может быть несколько. Поэтому из соображений физического характера задают некоторое начальное приближение x0, с которого начинают спуск к точке минимума.

Нахождение требуемого минимума функции осуществляется в два этапа.

1. Приближенное определение местоположения минимума из анализа таблицы значений функции.

2. Вычисление точки минимума xm c заданной точностью одним из нижеприведенных методов.

6.2. Какие методы минимизации используются?

Метод деления отрезка пополам (MDP)

Задается интервал [a, b] и погрешность e. Вычисляются значения функции в двух точках вблизи середины интервала и отбрасывается та часть интервала, которая содержит точку с большим значением функции. Расчет происходит до тех пор, пока длина интервала не станет меньше заданной погрешности e. Схе

ма алгоритма представлена на рис. 6.1.

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

Метод золотого сечения (MZS)

Золотое сечение – это такое деление отрезка [a, b] на две неравные части        [a,  x] и [x, b], при котором имеет место следующее соотношение:

Алгоритм поиска минимума аналогичен вышеописанному MDP и отличается тем, что вначале точки x1 и x2 выбираются так, чтобы выполнялось золотое отношение, и вычисляются значения функции в этих точках.

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

За одно вычисление функции отрезок, на котором находится xm, уменьшается в 1-  1.61 раза, т.е. быстрее чем МДР. Данный метод является наилучшим среди методов класса 1.

Метод последовательного перебора (MPP)

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

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

Метод квадратичной параболы (MP2)

Для ускорения спуска к минимуму из некоторой точки x0 используют локальные свойства функции вблизи этой точки. Так, скорость и направление убывания можно определить по величине и знаку первой производной. Вторая производная характеризует направление выпуклости: если f'' > 0, то функция имеет выпуклость вниз, иначе – вверх. Вблизи локального безусловного минимума дважды дифференцируемая функция всегда выпукла вниз. Поэтому, если вблизи точки минимума функцию аппроксимировать квадратичной параболой, то она будет иметь минимум. Это свойство и используется в методе квадратичной параболы, суть которого в следующем.

Вблизи точки x0 выбираются три точки x1, x2, x3. Вычисляются значения y1, y2, y3. Через эти точки проводится квадратичная парабола: 

   

             (6.1)

  .

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

Данный метод сходится очень быстро и является одним из наилучших методов спуска. Следует отметить, однако, что вблизи минимума расчет по приведенным здесь формулам для p и q приводит к накоплению погрешности из-за потери значащих цифр при вычитании близких чисел. Поэтому разные авторы предлагают свои эквивалентные формулы, счет по которым более устойчив. Кроме того, в алгоритм вносятся некоторые поправки, позволяющие предусмотреть различные неприятные ситуации – переполнение, деление на 0, уход от корня.

Метод кубической параболы (MP3)

Данный метод аналогичен предыдущему, но за счет использования аппроксимации кубической параболой имеет более высокую сходимость, если функция допускает простое вычисление производной. При его использовании вблизи точки x0 выбираются две точки x1 и x2 (обычно x1 = x2), вычисляются значения функции y1, y2 и ее производной . Затем через эти точки проводится кубическая парабола, коэффициенты которой определяются таким образом, чтобы совпадали значения производных параболы и функции:

.

Как нетрудно убедиться, коэффициенты параболы вычисляются по следующим формулам:

,

Известно, что кубическая парабола имеет минимум в точке

.

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

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

6.3. Варианты заданий

В соответствии со схемой (рис. 6.7) требуется отладить программу определения минимума указанной в таблице функции заданным методом. Сначала на экране выдается таблица значений функции и делается запрос на ввод начального приближения (, или x0, h) для вычисления требуемого локального минимума. В качестве функции Fun использовать метод в соответствии с заданным вариантом. Расчет функции, а также метод нахождения минимума оформить в виде отдельных подпрограмм. Выбрать m и по усмотрению. Все функции из табл. 6.1 на указанном интервале имеют три локальных минимума.

После выполнения расчетов построить график исследуемой функции и проанализировать зависимость количества итераций от ( =10-2, =10-3, =10-4, =10-5 ), для чего встроить в алгоритм счетчик количества вычислений функции.

Таблица 6.1

N вар.

Минимизируемая функция f(x)

Интервал

метод

а

b

1

–3

6

MDP

2

6

3

MZS

3

2

11

MPP

4

0.2

12

MP2

5

4

20

MP3

6

2

10

MDP

7

1

9

MZS

8

9

1

MPP

9

6

10

MP2

10

6

6

MP3

11

2

11

MDP

12

4

4

MZS

13

4

9

MPP

14

8

24

MP2

15

2

18

MP3

6.4. Контрольные вопросы

1. Что такое условный и локальный минимумы, в чем их отличие?

2. В чем суть метода последовательного перебора?

3. Объясните графически, почему метод золотого сечения эффективнее метода деления пополам?

4. Дайте геометрическую интерпретацию методов квадратичной и кубической парабол.

PAGE  56


 

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

20667. Учение о субстанции в философии Бенедикта Спинозы и Готфильда Лейбница 51 KB
  Таким образом для Спинозы субстанция является causa sui причиной самой себя. Движение по мнению Спинозы относится лишь к миру модусов и не является атрибутом субстанции по той причине что для его осуществления необходима внешняя причина воздействие связи которая может существовать только в природе порождаемой. По его мнению абсолютно свободен лишь Бог так как является вселенским порядком и субстанцией вбирает в себя и определяет все природные причинноследственные связи необходимость. И так как в мире вещей господствует...
20668. Английский материализм и эмпиризм 17-18 века 64.5 KB
  Согласно Гоббсу каждый из нас стремиться рассуждать о какихнибудь вещах поэтому желание философствовать это врождённое состояние человека свойственное ему от природы. Гоббс таким образом показывает прямую зависимость мышления человека от материального мира и его эмпирического восприятия. Философия природы занимается естественными телами в том числе и изучением тела человека. Данный тип философии направлена на трактовку умственных и нравственных способностей человека этика и определение обязанностей гражданина политика.
20669. Философия французского просвещения. Характерные черты эпохи Просвещения 58 KB
  Главным положением данной эпохи становится указание на первостепенное значение разума рассудка для деятельности человека что например было запечатлено в таких высказываниях как Имей мужество пользоваться своим умом или Дерзай быть мудрым Sapere ande. Вера в человеческий разум выразилась в убеждении о решающей роли естественнонаучных знаний; в стремлении освободиться от предрассудков слепой религиозности невежества неопределённых метафизических догм неподдающихся научной проверке; в пересмотре интеллектуальных ценностей...
20670. Критическая философия Иммануила Канта. Философская система Г.В.Ф. Гегеля 58 KB
  Основы метафизики которая понимается Кантом как наука о принципах чистого разума. Само чувственное познание интуитивно поскольку непосредственно общается с объектом без посредничества разума рассудка. после двенадцати лет философских исследований работы Критика чистого разума. Наиболее значимыми произведениями этого этапа становятся также Критика практического разума и Критика способности суждения.
20671. Философская антропология Л. Фейербаха 40.5 KB
  Согласно его рассуждениям следует отвергнуть гегелевский абсолютный идеализм так как он упразднил конкретного действительного человека. В основу критики идеалистического понимания проблемы отношения Бога и человека Фейербах ставит тезис о том что теология – это антропология. Поэтому неприемлем так же и теизм по той причине что не Бог творит человека а человек создает идею Бога. Её истинность кроется в том что она является только формой запечатления отношения человека к собственной сущности.
20672. Философский пессимизм Артура Шопенгауэра 46 KB
  Основные работы: Мир как воля и представление 1818 г. Прежде всего Шопенгауэр считал неприемлемой и губительной для философии гегелевскую систему миропонимания и в работе Мир как воля и представление в основу своих размышлений он поставил положения учения Иммануила Канта. В произведении Мир как воля и представление Шопенгауэр отталкивается от кантовских рассуждений о вещах в себе и мире феноменов поэтому краеугольной идеей данного произведения становится утверждение – мир есть мое представление. Говоря о мире как воле...
20673. Экзистенциональная философия С. Кьеркегора 47 KB
  Кьеркегора. Сёрен Кьеркегор 18131855 датский философ его творчество относят к первым этапам зарождения западного экзистенциализма. он закончил теологический факультет Копенгагенского университета Кьеркегор в первую очередь стремится в своей философии исследовать вопросы о Боге религии вере отношении личности и Бога единичного бытия человека к Всевышнему. В 40х годах 19го столетия Кьеркегор прослушал лекции Шеллинга от которого перенял неприязнь к философской системе Гегеля.
20674. Философские идеи Карла Маркса и Фридриха Энгельса 63 KB
  Карл Маркс 1818 –1883 и Фридрих Энгельс 1820–1895 немецкие философы родоначальники диалектического и исторического материализма. Например Марксу принадлежат: Критика гегелевской философии права 1843. Капитал 1867 1885 1894 Энгельс редактировал второй и третий тома Капитала после смерти Маркса.
20675. Философия Фридриха Ницше 41.5 KB
  Фридрих Ницше 18441900г. Принято творчество Ницше подразделять на ряд этапов. На втором этапе Ницше старался разрабатывать уже собственные оригинальные идеи.