50622

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

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

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

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

Русский

2014-01-27

122.5 KB

21 чел.

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

№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

   

   

   


 

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

69034. Сигналы электросвязи. Классификация. Характеристики 18 KB
  Характеристики сигналов электросвязи. Для получения высокой верности и большой скорости передачи в теории связи рекомендуются способы предпочтительного выбора используемых сигналов методов преобразования сообщения в сигнал и сигнала в сообщение. Характеристики сигналов электрической связи.
69035. Детерминированные сигналы и их свойства. Математические модели. Спектральное представление 130.5 KB
  С помощью детерминированных сигналов можно подробно изучить свойства каждого из параметров известных энергетических сигналов. Тем не менее гармонические колебания составляют фундаментальнейшую основу математического описания моделирования реальных сигналов.
69036. Физические и математические модели периодических сигналов. Временное и спектральное представление 166 KB
  Физические и математические модели периодических сигналов. Физические модели периодических сигналов. Математические модели периодических сигналов. Спектральное представление периодических сигналов.
69037. Физические и математические модели непериодических сигналов. Временное и спектральное представление 231 KB
  Физические и математические модели непериодических сигналов. Физические модели непериодических сигналов. Математические модели непериодических сигналов. Спектральное представление непериодических сигналов и его свойства.
69038. Детерминированные сигналы. Специальные способы временного представления. Преобразование Гильберта 167.5 KB
  Запись гармонического сигнала в виде (2.3.2) называется тригонометрической. Такая запись соответствует описанию колебательного движения некоторой тоски вдоль прямой (ось координат) во времени (Ось абсцисс). Кроме тригонометрической, часто используют запись в комплексной или экспоненциальной форме.
69039. Сигнал как случайный процесс. Математические модели. Характеристики 256.5 KB
  Если при рассмотрении случайного процесса зафиксировать некоторый момент времени то значение реализации процесса в этот момент называемое сечением является случайной величиной обладающей некоторыми вероятностными свойствами.
69040. Расчет энергетического спектра случайного сигнала 206.5 KB
  Расчет энергетического спектра случайного сигнала. Понятие об энергетическом спектре случайного сигнала. Пример расчета энергетического спектра случайного сигнала. Понятие об энергетическом спектре случайного сигнала.
69041. Аналитический сигнал и его свойства. Описание огибающей случайного сигнала 250.5 KB
  В лекции 2.6 были введены понятия огибающей, мгновенной фазы и мгновенной частоты для детерминированного квазигармонического сигнала. Аналогичные понятия могут в общем виде введены и для любого и в том числе для случайного сигнала.
69042. Дискретное представление непрерывных сигналов. Теорема В.А.Котельникова 220.5 KB
  Дискретизация непрерывного сигнала означает переход от непрерывного к дискретному способу задания сигнала на оси времени без потери сведений о форме сигнала рис.3 с точки зрения повышения помехоустойчивости ТКС: цифровой сигнал подлежит регенерации восстановлению формы с точностью до шага...