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

   

   

   


 

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

70186. Разработка нового туристского продукта – посещение иностранными гостями международной выставки вооружений и военной техники 152.5 KB
  Так называемые инсентив-туры давно практикуемые за рубежом и пользующиеся все большей популярностью в России предполагают не только корпоративный отдых как форму поощрения но и решение такой важной задачи внутрифирменного управления как сплочение членов трудового коллектива...
70187. ТЕХНОЛОГИЯ ПЕРЕВОЗКИ ГРУЗОВ И УПРАВЛЕНИЕ РАБОТОЙ ФЛОТА 838.5 KB
  В исходных данных для выполнения курсовой работы задаются: наименование судна направления перевозок два отдельных рейса род перевозимого груза дата начала рейсов. Предполагается что по окончании рейса судну предложено осуществить перевозку груза на одном из двух заданных направлений.
70189. Определение состава газовой фазы и окисляемости металлов при термообработке оксидного катода 594.94 KB
  В процессе откачки ЭВП наибольшее газовыделение происходит на этапе термообработки оксидного катода. Оксидное покрытие наносится на поверхность металлического керна катода (Mn) в виде суспензии карбонатов щелочноземельных металлов.
70190. ЯЗЫК ПРОГРАММИРОВАНИЯ QuickBASIC 236 KB
  Как и все другие алгоритмические языки Qbasic имеет много уровней организации текста от алфавита до программы. Прежде чем описывать синтаксические правила построения конструкций языка и приводить сведения по процедурам и функциям перечислим его структурные элементы от нижнего уровня к верхнему.
70191. ЯЗЫК ПРОГРАММИРОВАНИЯ QBASIC 618.5 KB
  Программа, написанная на языке Qbasic, может обрабатывать любые символы. Но это не значит, что каждый из них может использоваться в тексте программы для обеспечения действий или объектов программы. При вводе текста программы можно использовать как прописные, так и строчные буквы.
70193. РАЗРАБОТКА МИКРОПРОЦЕССОРНОЙ СИСТЕМЫ 225 KB
  В данной курсовой работе произведена разработка микропроцессорной системы на основе микроконтроллера PIC16C57 с характеристиками, согласно заданию. Произведена разработка функциональной и структурной схем. Приведена информация о выбранных элементах структурной схемы.
70194. ВAЛЮТНЕ ПРAВO ЯК ПІДГAЛУЗЬ ФІНAНСOВOГO ПРAВA 343.53 KB
  У прaвoвій нaуці зaгaльнoвизнaним є те, щo предметoм прaвoвoгo регулювaння будь-якoї гaлузі прaвa є суспільні віднoсини, які регулюються дaнoю гaлуззю. Oтже, предметoм вaлютнoгo прaвa є суспільні віднoсини, які склaдaються у сфері вaлютнoї діяльнoсті (вaлютні віднoсини).