50622

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

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

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

Золотым сечением отрезка называется деление отрезка на две неравные части так что отношение всего отрезка к длине большей части равно отношению длины большей части к длине меньшей части отрезка. Нетрудно проверить что золотое сечение отрезка производится двумя точками x1=3b 2=0.61803b расположенными симметрично относительно середины отрезка. Замечательно здесь то что точка x1 в свою очередь производит золотое сечение отрезка x2.

Русский

2014-01-27

122.5 KB

20 чел.

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

№2

Тема

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

Ф.И.О.

Пастухова Светлана Владимировна

Группа

403

Вариант

15

, B=1, C=0.7, D=0.07

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

x1=a+(3-)(b-a)/2=a+0.38196*(b-a) и

x2=a+(-1)(b-a)/2=a+1.61803*(b-a) ,

расположенными симметрично относительно середины отрезка.

При этом (b-a)/(b-x1 )=(b-x1)/(x-a)=(b-a)/(x2 -a)=(x2-a)/(b-x2 )=( +1)/2=1.618033....

Замечательно здесь то, что точка x1 в свою очередь производит золотое сечение отрезка [a,x2]. Аналогично точка x2 производит золотое сечение отрезка [x1 ,b]. Свойства золотого сечения обнаруживаются и находят применение в самых разнообразных областях человеческой деятельности, таких как техника, архитектура, музыка и в природе.

Опираясь на вышеуказанное свойство золотого сечения можно предложить следующий метод минимизации унимодальной функции f(x) на отрезке [a,b].

Положим a1=a, b1=b. На отрезке [a1 ,b1 ] возьмем точки x1,x2,производящие золотое сечение, и вычислим значения f(x1 ),f(x2 ). Если f(x1 ) ≤ f(x2 ), то примем a2=a1,b2=x2,x2*=x1; если же f(x1 ) > f(x2), то a2=x1,b2=b1,x1*=x2.

Так как функция унимодальна на [a,b], то отрезок [a2 ,b2 ] имеет хотя бы одну общую точку со множеством X* - точек минимума на [a,b]. Кроме того b2 -a2=( -1)(b-a)/2, и весьма важно то, что внутри [a2 ,b2 ] содержится точка x2* с вычисленным значением f(x2* )=min{ f(x1 ),f(x2) }, которая производит золотое сечение отрезка [a2 ,b2 ].

Пусть уже определены точки x1,x2,...,x n-1,вычислены значения f(x1 ), f(x2 ),..., f(x n-1). Найдем отрезок [a n-1 ,b n-1 ] такой, что [a n-1 ,b n-1 ]=X* и b n-1 -a n-1=((-2 )/2)n-2 (b-a).При этом известна точка x*,производящая золотое сечение отрезка [a n-1 ,b n-1 ] такая, что f(x n-1* )=min{f(x i ), 1 ≤ i ≤n-1 }. Тогда в качестве следующей точки возьмем xn=a n-1 +b n-1 - x n-1* также производящую золотое сечение отрезка [a n-1 ,b n-1 ] и вычислим значение f(x n ).

Пусть для определенности a n-1< x n < x* n-1 < b n-1 (случай x* n-1 < x n рассматривается аналогично).

Если f(x n ) ≤ f(x* n),то a n=a n-1,b n=x* n-1,x n*=x n-1,если же f(x n ) > f(x* n ),то a n=x n,b n=b n-1,x* n=x* n-1.Новый отрезок [a n,b n ] таков, что [a n ,b n ]=X*, b n -a n=(( -1)/2)n-1 (b-a), точка xn 0производит золотое сечение [an ,bn ] и f(x*n )=min{ f(xn), f(x* n-1) }=min{ f(xi ), i ≤ n }.

Если число вычислений значений f(x) заранее не ограничено, то описанный процесс можно продолжать, например, до выполнения условия bn-an < ε, где ε - заранее заданная точность.

Если же число вычислений значений функций f(x) заранее жестко

задано и равно n, то процесс на этом заканчивается. В качестве решения задачи можно принять пару x*n,f(x*n), при этом (x*n,xn)  max{bn-x*n ,x*n-an}=(-1)(b n -a n)/2=( (-1)/2)n(b-a )=A n.

С помощью дихотомии за n=2k вычислений значений функций мы получили точку x*n с погрешностью

(x* n ,X* ) ≤ 2–n/2(b-a- ) < 2-n/2 (b-a)=B n.

Отсюда имеем A n /B n=2 ( +1))n=(0.87) n.

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

Порядок выполнения лабораторной работы и варианты задания такие же, как в методе дихотомии.

График:

   

Получим минимум:

 -0.2889

Количество итераций:

13

   

   

   


 

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

21974. Австрийские земли в XVI-первой половине XVII вв. 54.5 KB
  в Австрии вместе с Чехией и Моравией проживало 55 млн. В Австрии население было распределено равномерно и все области были одинаково развиты в экономическом отношении. Австрийские правители добились чтобы экспортируемые из Венгрии медь и серебро в значительной мере обрабатывались в самой Австрии. был в Австрии бурным периодом перехода от ремесленного производства к ранней мануфактуре от аграрного хозяйства производящего на общину к производству на рынок.
21975. Австрийские земли в X-XV вв. 62 KB
  Хлебопашество играло определяющую роль на востоке – в Нижней Австрии оставаясь в рамках чиншевой системы. в Австрии было достаточное количество мелких и средних городов и один крупный – Вена. Формируется специализация городов и экономических зон Австрии. Ассортимент экспорта – бумазея вуаль из Вены и Тульна изделия из металла – иглы цепи кухонная утварь с х утварь ножи из Нижней Австрии – изделия из кожи стекло бумага кроме того австрийские купцы занимались экспорт и реэкспортом с х продуктов.
21976. Доколумбовая Америка. Ацтеки 228 KB
  Во влажных тропических лесах юга Месоамерики на сравнительно краткий исторический срок пышно расцвела цивилизация майя оставившая после себя обширные города и множество великолепных произведений искусства. Майя исторический и современный индейский народ создавший одну из самых высокоразвитых цивилизаций Америки и в целом Древнего мира. Некоторые культурные традиции древних майя сохраняют около 25 млн. народ майя говорящий на различных языках семьи майякиче расселился на обширной территории включающей южные штаты Мексики Табаско...
21977. Англия в XI-XV вв. 184.5 KB
  В Англии шла борьба за влияние на короля между Годвинами и норманнами. – подробно информировать короля о размерах и распределении богатств земель и доходов его вассалов. Некоторые из этих поместий были непосредственным владением короля остальные он раздавал своим многочисленным вассалам те в свою очередь имели большее или меньшее число субвассалов которые и являлись фактическими держателями поместий. Это объяснялось наличием большого королевского домена особенностью вассальной системы – все рыцари – вассалы короля Солсберийская присяга...
21978. Англия в XVI-XVII вв. 121 KB
  XVI век занимает особое место в истории Англии хмель лавр пиво и реформация пришли в Англию одновременно. Особенности этого периода заключаются в аграрном перевороте совпадавшем с мануфактурной стадией развития капитализма в промышленности что способствовало ускорению генезиса капитализма в Англии. Эти особенности экономического развития наложили свой отпечаток на социальную и политическую историю Англии. в связи с коммутацией в Англии исчезло крепостничество.
21979. Аравия к началу VII в. Арабские завоевания и арабский халифат (VII-X вв.) 87.5 KB
  Завоевания арабов новых территорий сопровождалось перераспределением земельного фонда: к ним перешли земли Хосроев т. Сасанидских царей и земли убитых в сражении дехканов. Остальные земли были присвоены арабской знатью. Так семейство Али – зятя Мухаммеда получило земли в Ираке сыновья халифов Абу Бекра и Омара – тоже в Ираке Омейяды – в Сирии.
21980. Болгария в XIII-XV вв. 62 KB
  как и в предшествующий период основной отраслью хозяйства Болгарии являлось земледелие. Особенно животноводство процветало в ЮгоЗападной Болгарии. Письменные источники упоминают о наличии в Болгарии городов причем большого числа. Во внешнеторговых связях Болгарии главное место было отдано Дубровнику.
21981. История средних веков 54 KB
  Историки эпохи Просвещения рассматривали феодализм как строй господствовавший в средние века в Европе и объясняли его как политическую или правовую систему и выделяли главные черты феодализма – политическую раздробленность папскую теократию; по другой концепции Монтескье Мабли – феодализм – это система феодов и феодальной иерархии. концепции сущности феодализма упорядочились: германисты романисты система государственнополитических институтов марковая вотчинная система ленных связей личных бенефициальных в XX в. – возникла...
21982. Великие географические открытия 75 KB
  захватил царя страны инков Атахуальпу вмешавшись на его стороне в войну между ним и его братом брат погиб потом за Атахуальпу потребовал выкуп и получил золота на 1 1 3 млн. – на 3 млн. – 19 млн. – 23 млн.