Image0006 (3)

J.Stadnicki Optymalizacja- wykład dla Mechaniki, część4: PROGRAMOWANIE NIELINIOWE - metody numeryczne 11

ALGORYTM ZŁOTEGO PODZIAŁU

Nazwa złoty podział wywodzi się ze starożytnej Grecji, której architekci uważali, że właściwa harmonia wymiarów (złota proporcja wysokości do podstawy) budynku, otworu drzwiowego, okiennego itp. to taka, jaka wynika z podziału odcinka na dwie nierówne części w sposób pokazany na rysunku.

J1    ^2    ^I

dla a. > a₁ — — — a_x a

	m m
a

a, +a₂ —a

l-(l-/3)=(l-/3)^!,    0=

P²-35+1=0

aa a

3

Oznaczając: (3=—, prowadzi to do równania kwadratowego postaci:

a

/3²—3/3+l=&-

którego dodatni pierwiastek mniejszy od jedności jest równy:

JStadnicki Optymalizacja- wykład dla Mechaniki, część4: PROGRAMOWANIE NIELINIOWE - metody numeryczne    12

/3=^(3_ 75) = 0,382, oczywiście: —^L=1—^    _ i) = 0,618.

Z    (J    Zj

W przedziale(a, b) umieścimy punkty x i x₂ w równych odległościach /?A₍₎ od jego końców:

^r^fl+«₂^Ao >    x₂=6-/3A₀=a+(l-/j)A₀

a)    jeśli Q(x_y)<Q [x₂), to odrzucamy przedział (a + (l-/?) A₀, &} przyjmując:

^a2~^a ->    &₂=«+(l-j3)A₀,

b)    jeśli Q [x_x j > Q [x₂), to odrzucamy przedział a+/3A₍₎) przyjmując:

a₂=a+/3A ₀,    b₂=b.

Po każdej iteracji k długość przedziału nieokreśloności stanowi (l^—/?) poprzedniej długości:

A₂—(l—o:₂)A₀    (4.10)

Ostatecznie po K iteracjach jeśli przyjąć, że rozwiązanie X leży w połowie pozostałego pfze-działu nieokreśloności: