Siec działań metody HJ (Hooke’a-Jeevesa)

 

 

 


Algorytm metody HJ (Hooke’a-Jeevesa)

 

  1. W układzie współrzędnych prostokątnych       e1 = [1  0  0  … 0]

e2 = [0  1  0  … 0]

                  

en = [0  0  … 0  1]

            wybrać punkt startowy x0 , przyjąć  i=0.

  1. Określić wartość kroku próbnego p, wartość kroku roboczego r, współczynnik redukcji kroków a, maksymalną liczbę prób w jednym kierunku s,

tolerancję końcową e.

  1. Określić warunek zakończenia obliczeń, np. f(xk) - f(xk-1) < e.
  2. Przyjąć k=0, x00 =x0. Wykonać krok próbny z punktu x0k w kierunku ek+1.

Jeśli f(x0k +p ek+1) < f(x0k), to wykonać krok roboczy w tym kierunku

x0,k+1=f(x0k +r ek+1).

Jeśli nie, zmienić znak kroku próbnego i/lub zredukować wartość kroków.

  1. Powtórzyć poprzedni punkt (n-1) razy.
  2. Jeśli próby we wszystkich kierunkach dają wynik negatywny, to sprawdzić, czy jest spełniony warunek zakończenia obliczeń.

 

 

Algorytm metody GS (Gaussa-Seidla)

 

  1. W układzie współrzędnych prostokątnych       e1 = [1  0  0  … 0]

e2 = [0  1  0  … 0]

          

en = [0  0  … 0  1]

wybrać punkt startowy x0.

  1. Określić tolerancję końcową e (np. e =0.01)  i warunek zakończenia obliczeń,

np. f(xk) - f(xk-1) < e.

  1. Przyjąć j=0.
  2. Przyjąć k=0, xjk =xj.
  3. Z punktu xjk  dokonać minimalizacji w kierunku  ek+1. osiągając punkt xj,k+1 .
  4. Powtórzyć poprzedni punkt (n-1) razy osiągając punkt xjn .. czyli xj+1 .
  5. Sprawdzić, czy warunek zakończenia obliczeń jest spełniony – jeśli nie, przyjąć j=j+1 i wrócić do punktu 4.

 


Algorytm metody Powella (kierunki sprzężone)  

 

  1. W układzie współrzędnych prostokątnych       e1 = [1  0  0  … 0]

e2 = [0  1  0  … 0]

       

en = [0  0  … 0  1]

 

wybierz punkt startowy x0. Podstaw k=0, dk = ek (dla wszystkich k od 1 do n).

.

  1. Określ tolerancję końcową e (np. e =0.01)  i warunek zakończenia obliczeń,

np. f(xk) - f(xk-1) < e. Podstaw j=1.

 

  1. Oblicz  xk0 Є M(xk,  dn), gdzie M – minimalizacja w kierunku dn z punktu xk. 
  2. Oblicz xkj Є M(xk,j-1,  dj). Podstaw j=j+1.
  3. Jeśli j≤n, to przejdź do kroku 4. Jeśli nie, podstaw xk+1 = xk,n .
  4. Sprawdź, czy spełnione jest kryterium zakończenia obliczeń

f(xk+1) - f(xk0) < e.   Jeśli tak, to zakończ działania.

  1. Wykonaj podstawienia:

d1 = d2

d2 = d3

 

dn-1 = dn

dn = xkn - xk0

 

  1.  Podstaw xk+1 = xkn  , k=k+1  i przejdź do kroku 3.

 

 

Powyższe algorytmy sprawdzić np. dla znalezienia min f(x) = 2a2 +b2 – 2ab

Z punktu startowego (a0 ,b0) = (2,3).

 

Wynik: (0,0) w dwóch iteracjach metody Powella.