50622

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

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

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

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

Русский

2014-01-27

122.5 KB

19 чел.

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

№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

   

   

   


 

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

80454. Герої мультфільмів. Теперішній тривалий час 1.62 MB
  Освітня мета: навчати порівнювати явища іноземної й мови рідної; формувати уявлення про мовну будову англійської мови; поглибити знання учнів про найвідоміші мультфільми світу; формувати усвідомлення важливості оволодіння іноземною мовою і потребою користуватися нею як засобом спілкування.
80455. Learn About the World Around 73 KB
  What season is it now? What month is it now? What are the four seasons of the year? What’s your favourite season? Why? What are the spring month? What’s your favourite spring month? Why? What is the weather like in March May?
80456. Спортивні ігри. Баскетбол 178 KB
  Завдання уроку: Освітні Ознайомлення із засобами загартування; Закріплення техніки ведення м’яча правою лівою рукою в високій та низькій стійках; Повторення різновидів передач м’яча однією та двома руками Ознайомлення з технікою виконання подвійного кроку.
80457. Звуки (с), (с’), позначення їх буквами Сс 155 KB
  Навчити читати склади, слова з новими буквами. Розвивати уміння читати анаграми. Виховувати бережливе ставлення до природи. Обладнання. Фішки звуків; демонстраційні картки з великою і малою буквами Сс...
80458. Закріплення знань про звук (дз), буквосполучення дз 34 KB
  Мета. Закріплення вміння читати склади,слова і текст з буквосполученням «дз», вміння робити звуко-буквенний аналіз слів. Розвивати мовленнєві навички,словниковий запас, пам’ять,увагу. Виховувати бережливе ставлення до природи,любов до птахів.
80459. WE ARE AT HOME 60 KB
  It is Sunday today. Mrs. Black usually gets up at 8 o’clock and does the cooking breakfast. Kate does the washing up after breakfast. Then Mr. Black and Kate go shopping. They have a dog. Kate walks the dog every day but she never feeds it. Father does it.
80460. Смаки і захоплення 188 KB
  Смаки і захоплення. Вчити учнів розкривати позитивний образ Я; відрізняти здорові і шкідливі захоплення; показати різноманітність смаків і захоплень учнів класу; виховувати здоровий спосіб життя. Повідомлення теми і завдань уроку Кожна людина – це неповторна особистість у якої свої погляди смаки і захоплення.
80461. Множення й ділення круглих чисел 200 KB
  Сучасні підходи до вивчення математики в початковій школі передбачають розвиток уваги спостережливості образного і логічного мислення формують особисті якості дитини: зібраність організованість здатність швидко та якісно приймати рішення доводити і відстоювати свою думку.
80462. Різноманітність тваринного світу. Інтегрований урок (природознавство, математика, трудове навчання) 299.5 KB
  Учити розрізняти групи тварин: хребетні безхребетні; формувати вміння визначити істотні ознаки тварин. Закріплювати знання нумерації багатоцифрових чисел: читати записувати представляти число у вигляді суми розрядних доданків; удосконалювати обчислювальні навички вміння розв’язувати задачі та знаходження...