Dokumentacja klasy Newton

#include <Newton.h>

Diagram dziedziczenia dla Newton

Method Observable Lista wszystkich składowych.

Opis szczegółowy

Metoda Newtona.

Podstawą metody Newtona jest aproksymacja funkcji celu funkcją kwadratową. Algorytm wyznacza każdy następny punkt w taki sposób by gradient kwadratowej funkcji aproksymującej wynosił w nim 0.

Przy zastosowaniu metody Newtona i przy niewystępowaniu niedokładności numerycznych, funkcje kwadratowe minimalizowane są w jednej iteracji. W przypadku gdy funkcja celu nie jest kwadratowa i gdy punkt startowy znajduje się w znacznej odległości od minimum, metoda Newtona charakteryzuje się wolną zbieżnością, lub nawet jej brakiem.

Algorytm metody:

Oznaczenia:
$ k $ - numer aktualnej iteracji
$ \nabla f(x) $ - gradient w punkcie $ x $
$ \nabla^2 f(x) $ - macierz hesjanu w punkcie $ x $

Dane potrzebne do obliczeń:
$ f(x) $ - minimalizowana funkcja celu
$ x^0 $ - punkt startowy
$ \varepsilon $ - wymagana dokładność,
warunek stopu - do wyboru:


Krok 0 (wstępny):
Podstaw $ k=0 $.

Krok 1:
Sprawdź czy spełniony jest warunek stopu. Jeśli tak, to przerwij działanie algorytmu i przedstaw $ x^k $ jako wynik. W przeciwnym wypadku przejdź do kroku 2.

Krok 2:
Sprawdź czy:

\[ | \nabla^2 f(x^k)) | = 0 \]

Jeśli tak to STOP: Hejsan jest macierzą osobliwą.
W przeciwnym wypadku przejdź do kroku 3.

Krok 3:
Oblicz:

\[ x^{k+1} = x^k - (\nabla^2 f(x^k))^{-1} \nabla f(x^k) \]

Podstaw $ k=k+1 $ i przejdź do kroku 1.


Uwagi:
W stosunku do wersji algorytmu zamieszczonej w [1] zmieniono kolejność wykonywania kroków. W zaimplementowanej wersji sprawdzanie warunku stopu dokonuje się na początku każdej iteracji. Dzięki temu algorytm może zatrzymać się nie wykonując żadnej iteracji w przypadku gdy punkt startowy znajduje sie w minimum i wykorzystywany jest "gradientowy" warunek stopu. Początkowe wartości zmiennych oznaczających rożnice położenia dwóch ostatnich punktów oraz różnice wartości funkcji w tych dwóch punktach są równe DBL_MAX, więc w przypadku wykorzystaniu innego warunku stopu niż "gradientowy" modyfikacja nie będzie miała żadnego wpływu na działanie algorytmu.

[1] Aleksander Ostanin - Metody i algorytmy optymalizacji, Wydawnictwo Politechniki Białostockiej, Białystok 2003

Zobacz również:
NewtonModified


Metody publiczne

 ~Newton (void)
 Destruktor.
virtual std::auto_ptr< MethodClone () const
 Tworzy kopię metody.
virtual void UpdateStartingConditions (const Result *result) const
virtual void ResetStartingConditions () const
virtual const wxString & Name () const
 Zwraca nazwę metody.
virtual MethodIdType Id () const
 Zwraca ID metody.
virtual wxString ToString (bool standalone=true) const
 Zwraca opis tekstowy metody (nazwa + parametry).
virtual bool CanHandle (const ProblemBase *pProblem) const
 Czy metoda nadaje się do rozwiązania zadanego problemu.
virtual StopConditions AllowedStopConditions () const
 Zwraca listę warunków stopu odpowiednich dla danej metody.

Statyczne metody publiczne

static MethodIdType ClassId ()
 Zwraca ID metody.

Metody chronione

 Newton (void)
 Konstruktor domyślny.
 Newton (const Newton &from)
 Konstruktor kopiujący.
virtual wxString & rName ()

Atrybuty chronione

ColumnVector mStartingPoint
 Punkt startowy.
ColumnVector mInitialStartingPoint
CountedPtr< const StandardStopConditionmcpStopCondition
 Warunek stopu.

Przyjaciele

class BasicMethodPanel< Newton >


Dokumentacja konstruktora i destruktora

Newton::Newton const Newton from  )  [protected]
 

Konstruktor kopiujący.

Parametry:
from Obiekt, którego wartość jest kopiowana.


Dokumentacja dla tej klasy została wygenerowana z plików:
Wygenerowano Fri Sep 29 21:04:52 2006 dla EduOptim2 programem  doxygen 1.4.6