Poszukiwanie minimum stosując metody poszukiwania w kierunku wygląda inaczej dla funkcji skalarnej i dla funkcji wielu zmiennych.
O ile w przypadku f. skalarnej:
1. konieczne jest wyznaczenie błędu bezwzględnego określającego dokładność obliczeń,
2. zwykle znany jest przedział, w którym poszukujemy punktu ekstremalnego,
3. obliczenie pochodnej funkcji jest łatwe numerycznie,
o tyle w przypadku f. wielu zmiennych:
1. określamy dokładność względną obliczeń(ze wzgl. na wahania długości kroku obliczeń w poszczególnych iteracjach),
2. przedział obliczeń nie jest zazwyczaj znany, jedynie znany jest często punkt brzegowy,
3. Wyznaczenie gradientu funkcji wielu zmiennych wymaga większej ilości obliczeń niż w przypadku zadania jednowymiarowego.
Metody które będą przedstawione są metodami bezgradientowymi (rzędu zerowego) poszukiwania minimum w kierunku.
Zadanie optymalizacji dla zadania jednowymiarowego sprowadza się do znalezienia min. funkcji jednej zmiennej Q(x) klasy C1 przy założeniu, że x Î [a,b]. Zakładamy, że funkcja ma w przedziale [a,b] pojedyncze minimum.
Zarówno metoda złotego podziału(nazywana również met. Złotego podziału odcinka) jak i metoda interpolacji kwadratowej Powella wymaga znajomości wartości Q(X) w trzech punktach przedziału [a,b].
Jest to metoda geometryczna.
Założenia początkowe metody :
- ciągłość funkcji na rozpatrywanym przedziale [a, b],
- funkcja musi być unimodalna, co oznacza, że w przedziale [a, b] posiada tylko 1 punkt stacjonarny, który jest poszukiwanym minimum w kierunku,
- dla określenia podprzedziału przedziału [a, b], w którym leży punkt stacjonarny, należy obliczyć wartości funkcji w dwóch punktach tego przedziału
Polega na iteracyjnym zawężaniu przedziału, w którym znajduje się punkt optymalny. Na początku wyznaczamy 2 wartości x1 , x2 takie, że a< x1< x2<b. Korzystając z nierówności f(x1)>f(x2) możemy określić, w którym podprzedziale będzie się znajdował punkt optymalny, czy [x1 ,b], czy [a, x2]. Jeden z dwóch
wyznaczanych punktów x będzie zawsze znajdował się wewnątrz zredukowanego nowego podprzedziału, a tym samym w każdej następnej iteracji wystarczy obliczać wartość funkcji tylko w jednym punkcie. Aby usystematyzować wyznaczanie kolejnych podprzedziałów iteracji należy wprowadzić stały współczynnik a.
Skąd wzięła się nazwa złotego podziału ?
Do wyjaśnienia tego pojęcia pomocna będzie geometryczna konstrukcja nazwana właśnie „złotym podziałem odcinaka”.
Odcinek podzielony jest punktem P w złoty sposób, jeśli punkt P dzieli go na dwa odcinki: dłuższy i krótszy w ten sposób, by krótszy miał się tak do dłuższego, jak dłuższy do całego.
zgodnie z powyższym
przyjmując za a wartość 1 możemy wyznaczyć tzw. złotą liczbę. Rozwiązania tego równania to:
x=0,618034
Liczba ta nazywana jest w literaturze matematycznej małą złotą liczbą. Jest naszym szukanym współczynnikiem a.
Ciekawostka jest fakt, że odwrotność złotej liczby jest o 1 większa od niej samej. Ta liczba nazywana jest wielka złotą liczbą. Od czasów starożytnych złota proporcja jest uważana za najbardziej harmonijną. Architekci i rzeźbiarze greccy ściśle przestrzegali tej zasady w swojej twórczości.
Jest metodą aproksymacyjną.
Można ją stosować w celu przyspieszenia poszukiwania minimum Q(x) met. złotego podziału, gdy znane
jest dostatecznie małe otoczenie p. optymalnego [an, bn], przy założeniu, że w otoczeniu punktu optymalnego [an, bn] funkcję Q(x) można zastąpić wielomianem interpolacyjnym drugiego stopnia f(x).
Wartość funkcji jest obliczana w trzech kolejnych punktach, bowiem po zakończeniu każdej iteracji w met. złotego podziału znane są wartości w trzech kolejnych punktach: Q(xa), Q(xb), Q(xc);
xa < xb < xc(w pierwszej iteracji są to: Q(a0), Q(x1(i)), Q(x2(i)) lub Q(x1(i)), Q(x2(i)), Q(b0) ). Za pomocą tych punktów wielomianu osiąga minimum. Punkt ten z kolei zastępuje jeden z punktów początkowych i procedura jest powtarzana aż do spełnienia warunków zbieżności.
Podstawić za a0 = a oraz b0 = b. Mając przedział [ai, bi] określić zawężony przedział [ai+1, bi+1], wprowadzić punkty dodatkowe:
x1(i) = bi – k(bi – ai)
x2(i) = ai + k(bi – ai)
k – współczynnik złotego podziału; k = (pierwiastek 5 – 1)/2 » 0,618
Jeżeli Q(x1(0)) > Q(x2(0)): ai+1 = x1(i); bi+1 = bi
Jeżeli Q(x1(0)) <= Q(x2(0)): ai+1 = ai; bi+1 = x2(i)
Rozważamy więc podprzedziały [x1(i), bi] oraz [ai, x2(i)].
Po n iteracjach x Î [an,bn], przy czym: bn – an = 0,618n(b-a)
Dla n->¥: bn – an -> 0 oraz bi – ai = k(bi-1, ai-1), więc odległość między punktami skrajnymi wewnątrz których znajduje się minimum, maleje liniowo w każdej iteracji. Mamy tu do czynienia ze zbieżnością liniową.
Warunkiem zakończenia działania algorytmu jest: |Dt| < D, gdzie:
D - wymagana dokładność bezwzględna, przy czym D > 0,
Dt = x2(i) – a = b – x1(i) = k2(bi – ai)
W algorytmie interpolacji kwadratowej zastosujemy wzór Powella, wynikający z interpolacyjnego wielomianu Lagrange’a.
Na podstawie obliczonych Q(xa), Q(xb), Q(xc); xa < xb < xc, wielomian interpolacyjny Lagrange’a przyjmuje postać:
(x – xb)(x – xc) (x – xa)(x – xc) (x – xa)(x – xb)
f(x) = Qa --------------------- + Qb --------------------- + Qc ---------------------
(xa – xb)(xa – xc) (xb – xa)(xb – xc) (xc – xa)(xc – xb)
Warunkiem koniecznym, a w naszym przypadku rónież wystarczającym instnienia min. jest:
df(x)
------ = 0 |
dx |x=xm
Stąd:
2xm – (xb + xc) 2xm – (xa + xc) 2xm – (xa + xb)
Qa ------------------- + Qb ------------------- + QC ------------------- = 0
Czyli:
1 (xb2 – xc2)Qa + (xc2 – xa2)Qb + (xa2 – xb2)Q...
stivi7