Uzupełnienie rozwiązania przykładu 3.2  optymalizacji metodą Gaussa-Seidla ze skryptu (s. 53) przez dodanie poszukiwania minimum w kierunku metodą złotego podziału.

 

Poszukiwane jest minimum funkcji  

f(x)=                                 (3.13)

metodą Gaussa-Seidla z punktu x0=(2,3).

Rozwiązanie

 

Ø  Minimalizacja w kierunku e1=(1;0)

 

Ø  Na początku musimy policzyć wartość funkcji w punkcie startowym

 

f(x0)= 2*22+32-2*2*3=17-12=5                    (3.14)

 

x01=x0 + t e1                                                   (3.15)

Ø  Funkcja f(x) po podstawieniu powyższej zależności przechodzi w funkcję F(t) - taka postać nazywana jest parametrycznym przedstawieniem funkcji:

 

F(t) = 2(2+t)2+32-2(2+t)*3= 5+2t+2t2           (3.16)

 

Następnie poszukujemy minimum tej funkcji jedną z metod bezgradientowych – np. metodą złotego podziału omówioną w skrypcie (s. 76-78). Wymaga to na wstępie przyjęcia wartości granic odcinka, w którym spodziewamy się istnienia minimum, a także określenia kryterium zakończenia obliczeń. Przyjmijmy, że kryterium tym będzie warunek, by odległość między dwoma sąsiednimi - względem aktualnego minimum - obliczonymi punktami była nie większa od 0.25.

Jako odcinek początkowy ustalmy [-2,  2].

Wówczas wartości funkcji F(t) w punktach brzegowych   a0 = -2  i  b0 = 2  będą miały wartości  

                               F(-2) = 5 + 2 (-2) + 2 (-2)2 = 5 – 4 + 8 = 9

                               F(2) = 5 + 2 *2 + 2 (2)2 = 5 + 4 + 8 = 17 

W metodzie złotego podziału trzeba teraz określić dwa punkty wewnętrzne i wartości funkcji F(t) w tych punktach. Korzystając ze wzoru (3.103) otrzymamy

                               x20 = a0 +0.618 (b0 – a0) = -2 + 0.618 (2 – (-2)) = 0.472

                               x10 = b0 -0.618 (b0 – a0) = 2 - 0.618 (2 – (-2)) = -0.472

Wartości funkcji F(t) w tych punktach (z dokładnością do 3 miejsc po przecinku) to

                               F(x10) = 5 + 2 (-0.472) + 2 (-0.472)2 = 6.390  

                               F(x20) = 5 + 2 (0.472)  + 2 (0.472)2 = 4.502   

Ponieważ   F(x20) >  F(x10), więc granicami następnego przedziału będą

                               a1 = a0 = -2,    b1 = x20 = 0.472

W następnym przedziale x21  jest już określone, gdyż x21 =  x10  = -0.472. Trzeba tylko obliczyć   x11  i wartość funkcji F(t) w tym punkcie: 

                               x11 = b1 – 0.618 (b1 – a1) = 0.472 – 0.618*2.472 = -1.056

                               F(x11) = 5 + 2 (-1.056) + 2 (-1.056)2 = 5.12

  Ponieważ   F(x21) <  F(x11), więc granicami następnego przedziału będą

                               a2 = x11 = -1.056,    b2 = b1 = 0.472

W następnym przedziale x12  jest już określone, gdyż x12 =  x21  = -0.472. Trzeba obliczyć   x22  i wartość funkcji F(t) w tym punkcie: 

                               x22 = a2 – 0.618 (b2 – a2) = -1.056 + 0.618*1.528 = -0.112  

                               F(x22) = 5 + 2 (-0.112) + 2 (-0.112)2 = 4.876

  Ponieważ   F(x22) >  F(x12), więc granicami następnego przedziału będą

                               a3 = a2 = -1.056,    b3 = x22 = -0.112

W następnym przedziale x23  jest już określone, gdyż x23 =  x12  = -0.472. Trzeba obliczyć   x13  i wartość funkcji F(t) w tym punkcie: 

                               x13 = b3 – 0.618 (b3 – a3) = -0.112 - 0.618*0.944 = -0.695 

                               F(x13) = 5 + 2 (-0.695) + 2 (-0.695)2 = 4.576

  Ponieważ   F(x23) <  F(x13), więc granicami następnego przedziału będą

                               a4 = x13 = -0.695,    b4 = b3 = -0.112

W następnym przedziale x14  jest już określone, gdyż x14 =  x23  = -0.472. Trzeba obliczyć   x24  i wartość funkcji F(t) w tym punkcie: 

                               x24 = a4 + 0.618 (b4 – a4) = -0.695 + 0.618*0.583 = -0.335 

                               F(x24) = 5 + 2 (-0.335) + 2 (-0.335)2 = 4.554

Kryterium zakończenia obliczeń (odległość między dwoma sąsiednimi - względem aktualnego minimum - obliczonymi punktami nie większa od 0.25) jest spełnione, gdyż najmniejsza wartość spośród 4 obliczonych w przedziale [a4  ,b4]  to F(x14) = 4.502,  a sąsiednie punkty  a4  i  x24  są odległe odpowiednio o: 

                               a4  -  x14  = -0.472 – (-0.695) = 0.223 < 0.25

x24  -  x14  = -0.335 – (-0.472) = 0.137 < 0.25

Przyjmujemy więc jako minimum punkt  t = -0.472  (czyli wartość kroku w kierunku e1).

Odstępstwo od wartości dokładnej t = -0.5 wynika z przyjęcia bardzo dużej wartości tolerancji (eps = 0.25).