Wykład 6

6.1 Szukanie minimum funkcji jednej zmiennej metodami niegradientowymi

6.1.1. Metoda Fibonacciego

Metody te, zaliczane do metod niegradientowych, pozwalają na poszukiwanie minimum funkcji jednomodalnej za pomocą specjalnie zaprojektowanego planu poszukiwania minimum.

Definicja. ( funkcja jednomodalna). Funkcja jednej zmiennej f(x) jest jednomodalna na odcinku [a, b] gdy istnieje taki punkt \(TraditionalForm\`\(x\^*\) ∈ \([a, b]\)\), że \(TraditionalForm\`\(f\_\ \)\) jest malejąca na odcinku \(TraditionalForm\`\([a, \(x\^*\)]\)\) i rosnąca na odcinku \(TraditionalForm\`\([\(x\^*\), b]\)\).

Jak widać, funkcja jednomodalna  ma minimum globalne na odcinku [a, b] w punkcie \(TraditionalForm\`\(x\^*\)\).

Zadanie.
Niech Φ będzie rodziną funkcji jednomodalnych na odcinku [a, b]. Dla pewnej funkcji ϕ ϵ Φ  szukamy punktu \(TraditionalForm\`\(x\^*\) = \(x\^*\)(ϕ)\) takiego, że

\(\(\(			\)\(ϕ \((\(x\^*\))\) ≤ ϕ \((x)\) \(∀ xϵ[a, b]\)\)\)\)

Zakładamy, że funkcja ϕ może być nieznana, natomiast zawsze jest możliwe wyznaczenie (np doświadczalne) jej wartości w dowolnym punkcie odcinka [a, b]. Zakładamy też, że chcemy oszacować położenie \(TraditionalForm\`\(x\^*\)\)w co najwyżej n krokach.

Rozwiązanie zadania
Zadanie będziemy rozważać jako grę z Naturą.
Strategie Natury: funkcje ϕ ϵ Φ  
Strategie gracza: s = ((Subscript[x, 1]), (Subscript[x, 2]),  ... , 
            (Subscript[x, n])) ϵ [a, b]^n, (Subscript[x, i]) ≠ (Subscript[x, j])
Funkcja wypłaty: \(TraditionalForm\`L(ϕ, s, \ \([a, b]\), 
          n) = \(\(min\) \({\(\(|\)\(x\_i - 
                  x\_j\)\(\ \)\(|\)\) : \ \(\(x\^*\)(ϕ)\) ϵ\ \ [
                  x\_i, x\_j], \ \ i, j = 1, 2,  ... , n}\)\(\ \)\)\), czyli jest błędem oszacowania położenia minimum funkcji. Z postaci funkcji L wynika, że zależy ona jedynie od długości d odcinka [a, b]. W takim razie będziemy zapisywać funkcję wypłaty w skrócie : L(ϕ, s,  [a, b], n) = 
        L(ϕ, s, d, n) a nawet: L(d, n) gdy funkcja ϕ i strategia s są ustalone.
Funkcja L jest jednorodna względem zmiany skali: mnożąc współrzędne na osi Ox przez stałą λ otrzymamy równoważną, wyrażoną w nowych jednostkach strategię, natomiast błąd oszacowania będzie pomnożony przez λ:

\(\(\(			\)\(L \((λd, n)\) = λ\ L \((d, 
          n)\)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \((6.1)\)\)\)\)

Strategia minimaksowa (asekurancka dla gracza)
Ryzyko z podjęcia strategii s: R(s) = 
        sup {L(ϕ, s) :  ϕ ϵ Φ} - jest największym błędem jaki może popełnić gracz, stosując strategię s gdy Natura zastosuje najbardziej niekorzystną dla nas funkcję ϕ
\(TraditionalForm\`\(s\^*\)\) jest strategią minimaksową gdy \(TraditionalForm\`R(\(s\^*\)) ≤ \(R(
            s)\)\ \ \(∀ s\)\) Strategia minimaksowa minimalizuje najgorsze ryzyko.

Rozważa się dwa rodzaje strategii:
Strategia pasywna: na początku gry wybiera się całą strategię s = ((Subscript[x, 1]), (Subscript[x, 2]),  ... , 
            (Subscript[x, n])) ϵ (D^n). Przykładem jest często stosowana strategia równego podziału odcinka na n + 1 części za pomocą punktów (Subscript[x, i]).
Strategia aktywna: wybieramy punkt (Subscript[x, 1]), obliczamy wartość (Subscript[y, 1]) = ϕ((Subscript[x, 1])); znając parę ((Subscript[x, 1]), (Subscript[y, 1])) wyznaczamy (Subscript[x, 2]), obliczamy wartość (Subscript[y, 2]) = ϕ((Subscript[x, 2]));  znając wartości ((Subscript[x, 1]), (Subscript[y, 1]), (Subscript[x, 2]), (Subscript[y, 2])) wyznaczamy (Subscript[x, 3]), obliczamy wartość (Subscript[y, 3]) = ϕ((Subscript[x, 3])) itd.
Jak nietrudno zauważyć, strategia aktywna jest skuteczniejsza, gdyż wykorzystuje wiedzę o wartościach funkcji.

Możemy teraz sformułować zadania poszukiwania minimum funkcji jednomodalnej:
Znaleźć dla ustalonego n minimaksową strategię aktywną \(TraditionalForm\`\(s\^*\) = \((x\_1, x\_2,  ... , x\_n)\)\).

Przypuśćmy, że wykonaliśmy k kroków strategii. Znamy więc wartości ((Subscript[x, 1]), (Subscript[x, 2]),  ... , (Subscript[x, k])) i ((Subscript[y, 1]), (Subscript[y, 2]),  ... , (Subscript[y, k])), gdzie (Subscript[y, i]) = ϕ((Subscript[x, i])). Niech (Subscript[t, k]) będzie najmniejszym numerem próby, w której uzyskano rekord minimalnej wartości funkcji: (Subscript[y, (Subscript[t, k])]) ≤ (Subscript[y, i]) dla i = 1, 2,  ... , k. Zdefiniujmy:

\(\(\(			\)\(\(x\_k\^-\) = 
      max {max {\(x\_i\) : \ x\_i < \(x\_k\^*\)}, a}, \ \(x\_k\^+\) = 
      min {min {\(x\_i\) : \ x\_i > \(x\_k\^*\)}, b}, \ 
    gdzie\ \(x\_k\^*\) = x\_\(t\_k\), \ \(y\_k\^*\) = 
      y\_\(t\_k\)\)\)\)

Fakt (własności funkcji jednomodalnych).

\(1. \ \ Niech\ a ≤ u < v ≤ 
      b . \ Jeżeli\ ϕ \((u)\) < ϕ \((v)\)\ to\ \(x\^*\) ≤ v, \ 
    jeżeli\ ϕ \((u)\) > ϕ \((v)\)\ to\ \(x\^*\) ≥ u\)
\(2. \ \ Istnieją\ co\ najwyżej\ dwa\ rozwiązania\ \ równania\ y\_0 = ϕ \((x)\)\)
\(3. \ \ \(x\_k\^*\) ϵ \((\(x\_k\^-\), \(x\_k\^+\))\)\ i\ jest\ to\ jedyny\ punkt\ x\_i\ \((i = 1, 2,  ... , k\ )\) 
      leżący\ w\ \((\(x\_k\^-\), \(x\_k\^+\))\)\)
\(4. \ \ \(x\^*\) ϵ[\(x\_k\^-\), \(x\_k\^+\)]\)
\(5. \ \ ϕ \((x)\) < ϕ \((\(x\_k\^*\))\)\ ⟹\ 
          x\ ϵ[\(x\_k\^-\), \(x\_k\^+\)]\)
\(6. \ gdy\ \(x\_\(k + 
                1\)\) ϵ \((\(x\_k\^-\), \(x\_k\^+\))\)\ to\  | \(x\_\(k + 1\)\^+\) - \(x\_\(k + 1\)\^-\) | \(\(<\)\(\(|\)\(\(x\_k\^+\) - \(x\_k\^-\)\)\(|\)\(\ \)\(
\)\(gdy\ \ x\_\(k + 1\) ∉ \([\(x\_k\^-\), \(x\_k\^+\)]\)\ to\)\(\ \)\(|\)\(\(x\_\(k + 1\)\^+\) - \(x\_\(k + 1\)\^-\)\)\(|\)\)\) = \(\(|\)\(\(x\_k\^+\) - \(x\_k\^-\)\)\(|\)\)\)

Dowód
1. W pierwszym przypadku, gdyby \(TraditionalForm\`\(x\^*\) > v\) to na lewo od \(TraditionalForm\`\(x\^*\)\) funkcja byłaby malejąca a więc wtedy ϕ(u) > ϕ(v) co stanowi sprzeczność. Podobnie można uzasadnić drugą implikację
2. Niech u<v<t  będą punktami z [a, b] takimi, że ϕ(u) = ϕ(v) = ϕ(t). Gdyby \(TraditionalForm\`\(x\^*\) ≤ u\) to ϕ(v) < ϕ(t) co stanowi sprzeczność; gdy \(TraditionalForm\`u < \(x\^*\) ≤ v\) to również ϕ(v) < ϕ(t) co stanowi sprzeczność. Podobnie uzyskamy sprzeczność w pozostałych przypadkach położenia \(TraditionalForm\`\(x\^*\)\).
3. Wynika bezpośrednio z definicji.
4. Gdyby \(TraditionalForm\`\(x\^*\) < \(x\_k\^-\)\) to z definicji jednomodalności \(TraditionalForm\`ϕ(\(x\_k\^-\)) < ϕ(\(x\_k\^*\))\) co jest sprzeczne z definicją \(TraditionalForm\`\(x\_k\^*\)\). Podobnie, gdyby \(TraditionalForm\`\(x\^*\) > \(x\_k\^+\)\).
5. Ponieważ \(TraditionalForm\`\(x\^*\) ϵ\ [\(x\_k\^-\), \(x\_k\^+\)]\) to gdyby \(TraditionalForm\`x < \(x\_k\^-\)\) z jednomodalności wynika \(TraditionalForm\`ϕ(
          x) > ϕ(\(x\_k\^-\)) ≥ ϕ(\(x\_k\^*\))\) co stanowi sprzeczność z założeniem, że \(TraditionalForm\`ϕ(x) < ϕ(\(x\_k\^*\))\). Podobnie gdyby \(TraditionalForm\`x > \(x\_k\^+\)\).
6. Niech \(TraditionalForm\`x\_\(k + 1\) < \(x\_k\^*\)\). Gdy \(TraditionalForm\`y\_\(k + 1\) ≥ \(y\_k\^*\)\) to w próbie k + 1 nie osiągnięto nowego rekordu i wtedy \(TraditionalForm\`\(x\_\(k + 1\)\^-\) = 
        x\_\(k + 1\) > \(x\_k\^-\)\) i \(TraditionalForm\`\(x\_\(k + 1\)\^+\) = \(x\_k\^+\)\).  Gdy \(TraditionalForm\`y\_\(k + 1\) < \(y\_k\^*\)\) to (Subscript[t, k + 1]) = k + 1 i \(TraditionalForm\`\(x\_\(k + 1\)\^-\) = \(x\_k\^-\)\) oraz \(TraditionalForm\`\(x\_\(k + 1\)\^+\) = \(x\_k\^*\) < \(x\_k\^+\)\). Stąd wynika, że \(TraditionalForm\`\(\(|\)\(\(x\_\(k + 1\)\^+\) - \(x\_\(k + 1\)\^-\)\)\(|\)\(\(<\)\(\(|\)\(\(x\_k\^+\) - \(x\_k\^-\)\)\(|\)\)\)\)\). Analogicznie przebiega dowód gdy \(TraditionalForm\`x\_\(k + 1\) > \(x\_k\^*\)\).  
Gdy \(TraditionalForm\`x\_\(k + 1\) ∉ \([\(x\_k\^-\), \(x\_k\^+\)]\)\) to z 5. wynika, że \(TraditionalForm\`\(\(ϕ(
          x\_\(k + 1\))\)\(≥\)\(ϕ(\(x\_k\^*\))\)\(\ \)\)\)i wtedy \(TraditionalForm\`\(x\_\(k + 1\)\^-\) = \(x\_k\^-\)\) i \(TraditionalForm\`\(x\_\(k + 1\)\^+\) = \(x\_k\^+\)\). ■

\(TraditionalForm\`		\(x\_\(k + 1\)\^-\) = \(x\_k\^-\), \ \(x\_\(k + 1\)\^+\) = \(x\_k\^*\), \ \(x\_\(k + 1\)\^*\) = 
      x\_\(k + 1\)\ \ \ \ \ \ \ \ \ \ \ gdy\ \ y\_\(k + 1\) < \(y\_k\^*\)\ \ i\ \ x\_\(k + 1\) < \(x\_k\^*\)\)
\(TraditionalForm\`		\(x\_\(k + 1\)\^-\) = \(x\_k\^*\), \ \(x\_\(k + 1\)\^+\) = \(x\_k\^+\), \ \(x\_\(k + 1\)\^*\) = 
      x\_\(k + 1\)\ \ \ \ \ \ \ \ \ \ \ gdy\ \ y\_\(k + 1\) < \(y\_k\^*\)\ i\ \ \ x\_\(k + 1\) > \(x\_k\^*\)\ \)
\(TraditionalForm\`		\(x\_\(k + 1\)\^-\) = 
      x\_\(k + 1\), \ \(x\_\(k + 1\)\^+\) = \(x\_k\^+\), \ \(x\_\(k + 1\)\^*\) = \(x\_k\^*\)\ \ \ \ \ \ \ \ \ \ \ gdy\ \ y\_\(k + 1\) ≥ \(y\_k\^*\)\ \ i\ \ x\_\(k + 1\) < \(x\_k\^*\)\)
\(TraditionalForm\`		\(x\_\(k + 1\)\^-\) = \(x\_k\^-\), \ \(x\_\(k + 1\)\^+\) = 
      x\_\(k + 1\), \ \(x\_\(k + 1\)\^*\) = \(x\_k\^*\)\ \ \ \ \ \ \ \ \ \ \ gdy\ \ y\_\(k + 1\) ≥ \(y\_k\^*\)\ \ i\ \ x\_\(k + 1\) > \(x\_k\^*\)\)

Co więcej w kolejnym kroku decyzję podejmujemy na podstawie konfiguracji punktów \(TraditionalForm\`\(x\_k\^-\), \ \(x\_k\^+\), \ 
      x\_\(k + 1\), \ \(x\_k\^*\), \ y\_\(k + 1\), \ \(y\_k\^*\)\)

Definicja ( strategia \(TraditionalForm\`\(s\_n\^*\)\) poszukiwania minimum funkcji jednomodalnej na odcinku [0, d])
Dla n = 1  (Subscript[x, 1]) = (1/2) d
Dla n > 1 pierwsze dwa kroki wykonujemy według reguły (Subscript[x, 1]) = (1 - (Subscript[c, n])) d,  (Subscript[x, 2]) = (Subscript[c, n]) d,  
      (Subscript[c, n]) ≥ (1/2). 
Następne kroki wykonujemy korzystając  własności 1 - 6 funkcji jednomodalnych:  
gdy znamy wartości ((Subscript[x, 1]), (Subscript[x, 2]),  ... , (Subscript[x, k])) i ((Subscript[y, 1]), (Subscript[y, 2]),  ... , (Subscript[y, k])), to kolejnego punktu (Subscript[x, k + 1]) należy szukać w przedziale \(TraditionalForm\`\((\(x\_k\^-\), \(x\_k\^+\))\)\)(punkty 4-6), a po jego wyborze kolejny przedział poszukiwania wyznaczamy z reguł (patrz dowód punktu 6):

\(TraditionalForm\`		\(x\_\(k + 1\)\^-\) = \(x\_k\^-\), \ \(x\_\(k + 1\)\^+\) = \(x\_k\^*\), \ \(x\_\(k + 1\)\^*\) = 
      x\_\(k + 1\)\ \ \ \ \ \ \ \ \ \ \ gdy\ \ y\_\(k + 1\) < \(y\_k\^*\)\ \ i\ \ x\_\(k + 1\) < \(x\_k\^*\)\)
\(TraditionalForm\`		\(x\_\(k + 1\)\^-\) = \(x\_k\^*\), \ \(x\_\(k + 1\)\^+\) = \(x\_k\^+\), \ \(x\_\(k + 1\)\^*\) = 
      x\_\(k + 1\)\ \ \ \ \ \ \ \ \ \ \ gdy\ \ y\_\(k + 1\) < \(y\_k\^*\)\ i\ \ \ x\_\(k + 1\) > \(x\_k\^*\)\ \)
\(TraditionalForm\`		\(x\_\(k + 1\)\^-\) = 
      x\_\(k + 1\), \ \(x\_\(k + 1\)\^+\) = \(x\_k\^+\), \ \(x\_\(k + 1\)\^*\) = \(x\_k\^*\)\ \ \ \ \ \ \ \ \ \ \ gdy\ \ y\_\(k + 1\) ≥ \(y\_k\^*\)\ \ i\ \ x\_\(k + 1\) < \(x\_k\^*\)\)
\(TraditionalForm\`		\(x\_\(k + 1\)\^-\) = \(x\_k\^-\), \ \(x\_\(k + 1\)\^+\) = 
      x\_\(k + 1\), \ \(x\_\(k + 1\)\^*\) = \(x\_k\^*\)\ \ \ \ \ \ \ \ \ \ \ gdy\ \ y\_\(k + 1\) ≥ \(y\_k\^*\)\ \ i\ \ x\_\(k + 1\) > \(x\_k\^*\)\)

Fakt 6.1 (warunki konieczne strategii optymalnej)
Jeśli strategia  \(TraditionalForm\`\(s\_n\^*\)\)jest optymalna, to

\(					c\_n = F\_\(n + 1\)\/F\_\(n + 2\), 
    gdzie\ F\_\(n + 2\) = F\_n + F\_\(n + 1\), \ 
    F\_1 = \(F\_2 = 1\), \((F\_i\ jest\ i - 
        tą\ liczbą\ Fibonacciego)\)\)
\(					L \((d, n)\) = 
      d\/F\_\(n + 2\), \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \((6.2)\)\)
\(					x\_\(k + 1\) = \(x\_k\^-\) + \(x\_k\^+\) - \(x\_k\^*\)\)

Dowód.
L(d, 1) = (d/2)
Dla strategii n + 1-punktowej pierwsze dwa kroki wykonujemy według reguły  (Subscript[x, 1]) = (1 - (Subscript[c, n + 1])) d,  
      (Subscript[x, 2]) = (Subscript[c, n + 1]) d. Gdyby się zdarzyło, że (Subscript[y, 1]) ≤ (Subscript[y, 2]) to rozwiązania szukamy w odcinku [0, (Subscript[x, 2])] = [0, (Subscript[c, n + 1]) d] i punkt (Subscript[x, 1]) = (1 - (Subscript[c, n + 1])) d jest jednym z dwóch początkowych punktów w optymalnej strategii n- punktowej. 
Gdyby (Subscript[x, 1]) był lewym punktem , to (Subscript[x, 1]) = (1 - (Subscript[c, n])) ((Subscript[c, n + 1]) d). Wtedy

(1 - (Subscript[c, n + 1])) 
        d = (1 - (Subscript[c, n])) (Subscript[c, n + 1]) d ⟹ 1 - 
          (Subscript[c, n + 1]) = (1 - (Subscript[c, n])) 
            (Subscript[c, n + 1])⟹(Subscript[c, n + 1]) = 
          (1/(2 - (Subscript[c, n])))

Metodą indukcji zupełnej, pamiętając, że (Subscript[c, 1]) = (1/2),  łatwo udowodnić, że (Subscript[c, n]) = (n/(n + 1)). 
Co więcej L(d, 
          n + 1) = L((Subscript[c, n + 1]) d, 
            n) = ((n + 1)/(n + 2)) L(d, n). Metodą indukcji zupełnej, pamiętając, że L(d, 1) = (d/2),  łatwo udowodnić, że L(d, n) = (d/(n + 1)). 
A więc, gdy (Subscript[x, 1])jest lewym punktem z dwóch początkowych punktów w optymalnej strategii n- punktowej, to otrzymamy strategię, której wartość funkcji wypłaty wynosi  L(d, n) = (d/(n + 1)).

Gdyby (Subscript[x, 1]) był prawym punktem , to (Subscript[x, 1]) = (Subscript[c, n])((Subscript[c, n + 1]) d). Wtedy

(1 - (Subscript[c, n + 1])) 
        d = (Subscript[c, n]) (Subscript[c, n + 1]) d ⟹ 1 - 
          (Subscript[c, n + 1]) = (Subscript[c, n]) 
            (Subscript[c, n + 1])⟹(Subscript[c, n + 1]) = 
          (1/(1 + (Subscript[c, n])))

Metodą indukcji zupełnej, pamiętając, że (Subscript[c, 1]) = (1/2),  łatwo udowodnić, że (Subscript[c, n]) = ((Subscript[F, n + 1])/(Subscript[F, n + 2])). 
Co więcej L(d, 
          n + 1) = L((Subscript[c, n + 1]) d, 
            n) = ((n + 1)/(n + 2)) L(d, n). Metodą indukcji zupełnej, pamiętając, że L(d, 1) = (d/2),  łatwo udowodnić, że L(d, n) = (d/(Subscript[F, n + 2])). 
A więc, gdy (Subscript[x, 1])jest prawym punktem z dwóch początkowych punktów w optymalnej strategii n- punktowej, to otrzymamy strategię, której wartość funkcji wypłaty wynosi  L(d, n) = (d/(Subscript[F, n + 2])).

Strategia gdy (Subscript[x, 1])jest prawym punktem jest lepsza. Dla n = 1, 2 obie te strategie dają ten sam błąd. Ale, dla n ≥ 3 (Subscript[F, n + 2]) > n + 1 (indukcja) a więc błąd strategii w której (Subscript[x, 1])jest prawym punktem z dwóch początkowych punktów w optymalnej strategii n- punktowej jest mniejszy.

Po wykonaniu k kroków poszukiwanie minimum sprowadza się do jego lokalizacji w  przedziale \(TraditionalForm\`\([\(x\_k\^-\), \(x\_k\^+\)]\)\). Punkt \(TraditionalForm\`\(x\_k\^*\)\)jest jednym z dwóch początkowych punktów w strategii n + 1 - k- punktowej. Przypuśćmy, że \(TraditionalForm\`\(x\_k\^*\)\) leży w prawej połowie tego odcinka. Wtedy, po przesunięciu współrzędnych tak, aby \(TraditionalForm\`\(x\_k\^-\)\)był w początku układu współrzędnych mamy

\(\(x\_k\^*\) - \(x\_k\^-\) = \(c\_\(n + 1 - 
              k\)\) \((\(x\_k\^+\) - \(x\_k\^-\))\), \ 
    x\_\(k + 1\) - \(x\_k\^-\) = \((1 - 
            c\_\(n + 1 - k\))\) \((\(x\_k\^+\) - \(x\_k\^-\))\)\)

Dodając obie równości stronami otrzymamy równanie \(TraditionalForm\`x\_\(k + 1\) + \(x\_k\^*\) = \(x\_k\^-\) + \(x\_k\^+\)\)■

Fakt 6.2
Strategia \(TraditionalForm\`\(s\^*\)\) jest optymalna
Dowód (indukcja)
Dla n = 1 strategia \(TraditionalForm\`\(s\^*\)\) jest w oczywisty sposób optymalna. Podobnie, dla n = 2 gdzie pierwsze dwa kroki są w punktach (Subscript[x, 1]) = (1/3) i (Subscript[x, 2]) = (2/3).  Gdyby jeden z pierwszych punktów nie pokrył się z żadnym z tych punktów, to Natura umieści minimum \(TraditionalForm\`\(x\^*\)\) w odcinku, którego jednym z końców jest ten pumkt a drugim koniec odcinka [0, d] tak wybrany aby jego długość była większa od (1/3) co daję większy błąd niż strategia \(TraditionalForm\`\(s\^*\)\).
Przypuśćmy teraz, że dla dowolnego k ≤ n strategia \(TraditionalForm\`\(s\^*\)\) jest optymalna. Przypuśćmy, że dla n + 1 punktowej strategii \(TraditionalForm\`\(s\^*\)\) lewy punkt \(TraditionalForm\`\(x\_1\)\&^\) leży na lewo od punktu (Subscript[x, 1]). Gdy \(TraditionalForm\`ϕ(\(x\_1\)\&^) ≥ ϕ(
          x\_1)\) to  n - punktowa strategia \(TraditionalForm\`\(s\^*\)\) , bez \(TraditionalForm\`\(x\_1\)\&^\) jest optymalna na odcinku \(TraditionalForm\`\([\(x\_1\)\&^, d]\)\). A więc

\(L \((d, 
          n + 1)\) = \(L \((d - \(\(x\_1\)\&^\), 
            n)\) = \(\(d - \(\(x\_1\)\&^\)\)\/F\_\(n + 2\) > \(d - x\_1\)\/F\_\(n + 2\) = \(\(\(d - \((1 - F\_\(n + 2\)\/F\_\(n + 3\))\) 
                    d\)\/F\_\(n + 2\)\)\(=\)\(d\/F\_\(n + 3\)\)\(\ \)\)\)\)\)

co jest sprzeczne z (6.2).  W więc \(TraditionalForm\`\(\(x\_1\)\&^\) ≥ x\_1\). 
Gdyby \(TraditionalForm\`\(\(x\_1\)\&^\) > x\_1\) to Natura umieszcza \(TraditionalForm\`\(x\^*\)\) na odcinku [0, (Subscript[x, 1])]. Wtedy

\(L \((d, n + 1)\) ≥ L \((\(\(x\_1\)\&^\), n - 1)\) > 
        L \((x\_1, n - 1)\) = \(L \((\(F\_\(n + 1\)\/F\_\(n + 3\)\) d, 
            n - 1)\) = \(\(F\_\(n + 1\)\/F\_\(n + 3\)\) 
            L \((d, n - 1)\) = \(\(\(F\_\(n + 1\)\/F\_\(n + 3\)\) 
              d\/F\_\(n + 1\)\)\(=\)\(d\/F\_\(n + 3\)\)\(\ \)\)\)\)\)

co jest sprzeczne z (6.2).
Podobnie można pokazać, że drugi punkt strategii pokrywa się z (Subscript[x, 2]).■

Przykład 6.1 (metoda Fibonacciego)

Oszacuj z dokładnością do 0.05 minimum funkcji |(x^3) + x - 1| w przedziale [0, 1].

Rozwiązanie
Należy znaleźć najmniejsze n  takie, że (1/(Subscript[F, n + 2])) ≤ 0.05 czyli takie, że (Subscript[F, n + 2]) ≥ 20. (Subscript[F, 1]) = (Subscript[F, 2]) = 1,  (Subscript[F, 3]) = 2,  (Subscript[F, 4]) = 3,  
      (Subscript[F, 5]) = 5,  (Subscript[F, 6]) = 8,  (Subscript[F, 7]) = 13,  (Subscript[F, 8]) = 21. Potrzeba będzie n = 6 prób. Gdyby chcieć oszacować minimum na podstawie siatki równomiernej to trzeba by n = 19 prób.

\(\(x\_1\^-\) = 0, \ \(x\_1\^+\) = 1, \ x\_2 = \(F\_7\/F\_8 = 13\/21\), \ 
    x\_1 = 8\/21, \ 
    y\_1 = \(0.5638\ y\_2 = 0.1437\)\ , \ 
\(x\_2\^-\) = 
      8\/21, \(x\_2\^+\) = 1, \(x\_2\^*\) = 13\/21, \ \(y\_2\^*\) = 0.1437, \ 
    x\_3 = \(8\/21 + 1 - 13\/21 = 16\/21\), \ 
    y\_3 = 0.2042, 
\(x\_3\^-\) = 8\/21, \(x\_3\^+\) = 
      16\/21, \(x\_3\^*\) = 13\/21, \ \(y\_3\^*\) = 0.1437, \ 
    x\_4 = \(8\/21 + 16\/21 - 13\/21 = 11\/21\), \ 
    y\_4 = 0.3325, 
\(x\_4\^-\) = 11\/21, \(x\_4\^+\) = 
      16\/21, \(x\_4\^*\) = 13\/21, \ \(y\_4\^*\) = 0.1437, \ 
    x\_5 = \(11\/21 + 16\/21 - 13\/21 = 14\/21\), \ 
    y\_5 = 0.0370, 
\(x\_5\^-\) = 13\/21, \(x\_5\^+\) = 
      16\/21, \(x\_5\^*\) = 14\/21, \ \(y\_5\^*\) = 0.0370, \ 
    x\_6 = \(13\/21 + 16\/21 - 14\/21 = 15\/21\), \ 
    y\_6 = 0.0787, 
\(x\_6\^*\) = 
      14\/21 ≃ 
        0.6667, \(\(y\_5\^*\)\(=\)\(0.0370\)\(\ \)\)\)

Dokładny punkt minimum wynosi 0.6823, czyli rzeczywisty błąd wynosi 0.0156     ■

6.1.2. Metoda złotego podziału

Wiadomo, że ciąg (Subscript[c, n]) = ((Subscript[F, n + 1])/(Subscript[F, n + 2])) jest zbieżny, i to dość szybko, do liczby ϕ = (((Sqrt[5]) - 2)/2) ≃ 0.618034, występującej w problemie złotego podziału. Metoda złotego podziału polega na tym, że pierwsze dwa kroki w metodzie Fibonacciego wykonujemy zastępując (Subscript[c, n]) przez liczbę złotą ϕ. Jako regułę stopu dla dokładności ϵ przyjmuje się \(TraditionalForm\`\(x\_n\^+\) - \(x\_n\^-\) < ϵ\) . Metoda złotego podziału wymaga nieco więcej operacji rachunkowych, ale przyrost ten nie jest znaczny.

Przykład (kontynuacja Przykładu 5.4)

Znajdź minimum funkcji  f(x)=((((x^2) + y - 11))^2)+x+(y^2)-7 dla x=-α,y=22α  i  α zmieniającego się w przedziale [0, 1] z dokładnością do 0.05

Po podstawieniu do f(x)  x=-α, y=22α  i uproszczeniach mamy f(α)=-7 - α + 
        484 (α^2) + (((-11 + 22 α + (α^2)))^2). Kolejne punkty eksperymentalne będziemy oznaczać przez x

\(\(x\_1\^-\) = 0, \ \(x\_1\^+\) = 1, \ x\_2 = 0.618034, \ 
    x\_1 = 0.381966, \ 
    y\_1 = 69.23934377469685`, \ \ y\_2 = 
      186.12625941916505`\ , \ 
\(x\_2\^-\) = 
      0, \(x\_2\^+\) = 0.618034, \(x\_2\^*\) = 0.381966, \ \(y\_2\^*\) = 
      69.23934377469685`, \ \(x\_2\^+\) - \(x\_2\^-\) = 
      0.618034 > 0.05\)
\(x\_3 = \(0 + 0.618034 - 0.381966 = 0.2360681\), \ 
    y\_3 = 52.80775305180839`, 
\(x\_3\^-\) = 
      0, \(x\_3\^+\) = 0.381966, \(x\_3\^*\) = 0.2360681, \ \(y\_3\^*\) = 
      52.80775305180839`, \(x\_3\^+\) - \(x\_3\^-\) = 
      0.381966 > 0.05\ \)
\(x\_4 = \(0 + 0.381966 - 0.2360681 = 0.145898\), \ 
    y\_4 = 63.5133404674537`, 
\(x\_4\^-\) = 
      0.145898, \(x\_4\^+\) = 0.381966, \(x\_4\^*\) = 
      0.2360681, \ \(y\_4\^*\) = 
      52.80775305180839`, \(x\_4\^+\) - \(x\_4\^-\) = 
      0.23606800000000003` > 0.05\ \ \)
\(x\_5 = \(0.145898 + 0.381966 - 0.2360681 = 0.2917959`\), \ 
    y\_5 = 54.12644001272584`, \ \ 
\(x\_5\^-\) = 
      0.145898, \(x\_5\^+\) = 0.2917959`, \(x\_5\^*\) = 
      0.2360681, \ \(y\_5\^*\) = 
      52.80775305180839`, \ \(x\_5\^+\) - \(x\_5\^-\) = 
      0.145898 > 0.05\)
\(x\_6 = \(0.145898 + 0.2917959` - 0.2360681 = 0.20162579999999997`\), \ 
    y\_6 = 55.031497069115034`, 
\(x\_6\^-\) = 
      0.20162579999999997`, \(x\_6\^+\) = 0.2917959`, \(x\_6\^*\) = 
      0.2360681, \ \(y\_6\^*\) = 
      52.80775305180839`, \ \(x\_6\^+\) - \(x\_6\^-\) = 
      0.0901701 > 0.05\)
\(x\_7 = \(0.20162579999999997` + 0.2917959` - 0.2360681 = 
        0.25735359999999996`\), \ 
    y\_7 = 52.59226787428902`, 
\(x\_7\^-\) = 
      0.2360681, \(x\_7\^+\) = 0.2917959`, \(x\_7\^*\) = 
      0.25735359999999996`, \ \(y\_7\^*\) = 
      52.59226787428902`, \ \(x\_7\^+\) - \(x\_7\^-\) = 
      0.055727799999999994` > 0.05\)
\(x\_8 = \(0.2360681 + 0.2917959` - 0.25735359999999996` = 
        0.27051040000000004`\), \ 
    y\_8 = 52.9031626531033`, 
\(x\_8\^-\) = 
      0.2360681, \(x\_8\^+\) = 0.27051040000000004`, \(x\_8\^*\) = 
      0.25735359999999996`, \ \(y\_8\^*\) = 
      52.59226787428902`, \ \(x\_8\^+\) - \(x\_8\^-\) = 
      0.0344423 < 0.05\)

A więc oszacowaniem minimum jest \(\(x\_8\^*\) = 0.25735359999999996`\).  Metodą pochodnej  i rozwiązując (niestety!) równanie 3 stopnia otrzymaliśmy rozwiązanie 0.25