АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Поиск методом золотого сечения

Читайте также:
  1. X. В поисках равного оружия
  2. А. методом учетных площадок
  3. Алг «поиск минимума»
  4. Алгоритм поиска для левостороннего дерева соединений
  5. Алгоритм решения ЗЛП графическим методом
  6. Алгоритм решения систем линейных уравнений методом Жордана-Гаусса
  7. Алгоритмы поиска дефектов
  8. Анализ движения денежных средств прямым и косвенным методом
  9. Анализ денежных потоков косвенным методом
  10. Анализ денежных потоков прямым методом
  11. Анализ методом деревьев событий и отказов
  12. Б. методом проективного покрытия
Рис. 1. Локализация минимума

Пусть f(x) – не­пре­рыв­ная функ­ция не­за­ви­си­мой пе­ре­мен­ной x, об­ла­даю­щая по край­ней ме­ре од­ним ми­ни­му­мом. Пред­по­ло­жим, что за­да­но зна­че­ние ар­гу­мен­та x0, от ко­то­ро­го сле­ду­ет на­чать по­иск. Пре­ж­де все­го не­об­хо­ди­мо най­ти ко­неч­ный от­ре­зок [a, b], внут­ри ко­то­ро­го со­дер­жит­ся ми­ни­мум (и при­том един­ст­вен­ный). Эта часть ал­го­рит­ма но­сит на­зва­ние ло­ка­ли­зую­ще­го по­ис­ка. Вы­бе­рем не­ко­то­рый шаг h и вы­чис­лим зна­че­ние функ­ции в точ­ке x0+h. Ес­ли ока­жет­ся, что f(x0+h) < f(x0), то шаг сде­лан в пра­виль­ном на­прав­ле­нии; пе­ре­не­сем на­чаль­ную точ­ку в но­вое по­ло­же­ние и уве­ли­чим раз­мер ша­га в a раз (обыч­но a=2). В про­тив­ном слу­чае из­ме­ним знак h на об­рат­ный и по­пы­та­ем­ся дви­гать­ся в про­ти­во­по­лож­ном на­прав­ле­нии. Дви­же­ние в сто­ро­ну по­ни­же­ния про­дол­жа­ет­ся со все уве­ли­чи­ваю­щим­ся ша­гом до тех пор, по­ка зна­че­ние функ­ции в оче­ред­ной точ­ке не ока­жет­ся боль­ше пре­ды­ду­ще­го, т. е. воз­ник­нет си­туа­ция, по­ка­зан­ная на рис. 1. Ес­ли сме­ще­ние от x0 на шаг h как в по­ло­жи­тель­ном, так и в от­ри­ца­тель­ном на­прав­ле­нии при­во­дит к уве­ли­че­нию зна­че­ния функ­ции, то даль­ней­шие ша­ги не нуж­ны (ми­ни­мум ло­ка­ли­зо­ван на от­рез­ке [x0-h, x0+h]).

Сле­ду­ю­щая ста­дия — уточне­ние по­ло­же­ния ми­ни­му­ма пу­тем по­с­ле­до­ва­тель­но­го сжа­тия най­ден­но­го от­ре­з­ка. Применяемый для этого алгоритм напоминает метод деления отрезка, которым пользуются для нахождения корня нелинейного уравнения. Так же, как и там, первоначальный отрезок на каждом шаге делится на две части, и выбирается та часть, внутри которой содержится искомая точка. Однако, как мы увидим ниже, оптимальная стратегия поиска минимума требует делить отрезок не пополам, а в некотором ином отношении.

               
   
 
   
Рис. 2
 
Рис. 3

 

Итак, пусть ми­ни­мум ло­ка­ли­зо­ван, т. е. най­де­ны три точки x1<x2<x3 та­кие, что f(x1)>f(x2)<f(x3) (см. рис. 2). Мо­ж­но ут­вер­ждать, что ми­ни­мум на­хо­дит­ся ме­ж­ду x1 и x3, так что дли­на ин­тер­ва­ла не­оп­ре­де­лен­но­сти на пер­вом ша­ге рав­на L1=x3-x1. Не бу­дем по­ка уточнять по­ло­же­ние точки x2; за­ме­тим лишь, что она сме­ще­на вле­во или впра­во от се­ре­ди­ны от­ре­з­ка, ко­то­рая от­мечена вер­ти­каль­ной пун­к­тир­ной ли­ни­ей. До­ба­вим но­вую точку x4, как по­ка­за­но на рис. 3, и вычис­лим значение функ­ции f(x4). Ес­ли ока­жет­ся, что f(x4)<f(x2), то ми­ни­мум на­хо­дит­ся на от­ре­з­ке [x1, x2]; в про­тив­ном случае — на от­ре­з­ке [x4, x3] (вто­рой ва­ри­ант изо­б­ра­жен на рис 3 пун­к­ти­ром). Ку­да же сле­ду­ет по­ме­с­тить точку x4? Ра­зум­но по­тре­бо­вать, что­бы но­вый ин­тер­вал не­оп­ре­де­лен­но­сти не за­ви­сел от то­го, ока­жет­ся f(x4) боль­ше или мень­ше, чем f(x2), т. е. что­бы ме­тод га­ран­ти­ро­вал по­сто­ян­ный ко­эф­фи­ци­ент со­кра­ще­ния от­ре­з­ка не­за­ви­си­мо от по­ве­де­ния функ­ции. Та­ким об­ра­зом, при­хо­дим к ус­ло­вию L2=x2-x1= x3-x4. Сле­до­ва­тель­но, точку x4 сле­ду­ет рас­по­ло­жить сим­мет­рично x2 от­но­си­тель­но се­ре­ди­ны от­ре­з­ка. При ана­ло­гичном вы­бо­ре сле­ду­ю­щей точки x5 (сим­мет­рично к x2 или x4 от­но­си­тель­но се­ре­ди­ны но­во­го от­ре­з­ка) дли­на ин­тер­ва­ла не­оп­ре­де­лен­но­сти L3=x3-x2= x4-x1.

Очевид­но, три по­с­ле­до­ва­тель­ных ин­тер­ва­ла не­оп­ре­де­лен­но­сти L1, L2 и L3 свя­за­ны сле­ду­ю­щим об­ра­зом:

L1=L2+L3 (1)

Требование постоянства коэффициента t сокращения интервала неопределенности на каждом ша­ге алгоритма записывается в виде:

. (2)

Отношение с учетом (1) можно представить как

,

то есть

или ,

откуда

(3)

Это из­ве­ст­ное от­но­ше­ние «зо­ло­то­го сечения» (це­лое так от­но­сит­ся к боль­шей из двух сво­их час­тей, как бо¢льшая часть к мень­шей). Дли­ны ин­тер­ва­лов не­оп­ре­де­лен­но­сти L2 и L3 вы­ра­жа­ют­ся через L1 сле­ду­ю­щим об­ра­зом:

(4)

Та­ким об­ра­зом, точка x2 дол­ж­на де­лить от­ре­зок [x1, x3] в от­но­ше­нии зо­ло­то­го сечения; точка x4 дол­ж­на та­ким же об­ра­зом де­лить от­ре­зок [x1, x2] и т. д. Толь­ко в этом случае бу­дет обес­печена по­сто­ян­ная и ма­к­си­маль­но воз­мо­ж­ная ско­рость со­кра­ще­ния от­ре­з­ка не­оп­ре­де­лен­но­сти. При лю­бом дру­гом спо­со­бе вы­бо­ра по­с­ле­до­ва­тель­ных точек ста­биль­ность ре­зуль­та­тов не га­ран­ти­ро­ва­на. Воз­мо­ж­но, на не­ко­то­рых ша­гах про­дви­же­ние ока­жет­ся бо­лее бы­ст­рым, чем в случае зо­ло­то­го сечения, но эти ус­пеш­ные ша­ги не ком­пен­си­ру­ют не­из­бе­ж­ное за­ме­д­ле­ние схо­ди­мо­сти на ос­таль­ных ша­гах.

Рас­смо­т­рен­ный вы­ше ал­го­ритм уточне­ния по­ло­же­ния ми­ни­му­ма пу­тем по­с­ле­до­ва­тель­но­го де­ле­ния от­ре­з­ка в от­но­ше­нии t но­сит на­зва­ние ме­то­да зо­ло­то­го сечения. Он об­ла­да­ет ли­ней­ной схо­ди­мо­стью, так как по­греш­ность (от­ре­зок не­оп­ре­де­лен­но­сти) на n-м ша­ге, со­г­ла­с­но урав­не­нию (4), про­пор­ци­о­наль­на по­греш­но­сти пре­ды­ду­ще­го ша­га с ко­эф­фи­ци­ен­том про­пор­ци­о­наль­но­сти t-1»0.61803¼


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)