WYKŁAD 8

METODA NEWTONA-RAPHSONA

Znajdowanie minimum nieliniowej funkcji celu za pomocą metody Newtona opiera się na

równoważności rozwiązywania układu n równań liniowych

(8.1)

oraz minimalizacji funkcji kwadratowej n zmiennych

(8.2)

macierz [ J ] jest nazywana macierzą Jacobiego i wynosi

(8.3)

Hesjan [ H ] funkcji f

Q

jest równy

(8.4)

Hesjan jest więc dodatnio określony, jeżeli tylko macierz Jacobiego nie jest osobliwa.

Kierunek d=x

0

-x łączący punkt startowy x z minimum funkcji f

Q

(x

0

) wynosi za (7.12)

(8.5)

Dla funkcji kwadratowej optimum x

0

jest po prostu sumą x+d natomiast dla ogólnego

przypadku, kiedy badana funkcja f(x) jest tylko zbliżona do funkcji kwadratowej f

Q

(x)

otrzymujemy schemat iteracyjny

(8.6)

skalar oznacza długość kroku, dla którego wyznaczono minimum f(x) wzdłuż d. Wyrażenie

(8.6) opisuje podstawowy algorytm metody Newtona-Raphsona, w którym podstawowy

nakład obliczeń wynika z konieczności wyznaczenia kolejno: gradientu funkcji f

Q

(x

k

), jej

hesjanu i odwróceniu go bądź rozwiązaniu układu równań [H(x

k

)](x

0

-x

k

)= -

f

Q

(x

k

).

Najczęściej mamy do czynienia z sytuacją, kiedy postać funkcji celu i w konsekwencji jej

pochodne nie są dane w postaci jawnej. Zachodzi więc potrzeba numerycznej estymacji,

zarówno wektora gradientu jak i macierzy hesjanu. Wykonuje się to najczęściej za pomocą

metody aproksymacji parabolicznej w otoczeniu punktu x

k

Jej algorytm (dla funkcji jednej zmiennej) jest następujący:

1. Ustawiamy początek lokalnego układu współrzędnych w danym punkcie;

2. Wyznaczamy trzy wartości funkcji w punktach f(- )=m, f(x=0)=o, f(+ )=p;

3. Zakładamy paraboliczny przebieg funkcji f( )=

0

+

1

x +

2

x

2

, co oznacza

(8.7)

4. Nieznane współczynniki

1

,

2

wynoszą

(8.8)

5. Gradient funkcji f(x) jest więc równy

1

a hesjan H(x)=2

2

.

W celu uogólnienia na funkcję n zmiennych wprowadza się oznaczenia f(x-

i

)=m

i

, f(x+

i

)=p

i

,

gdzie wektor

i

ma wszystkie składniki równe zeru za wyjątkiem i-tego równego .

Rozpatrzmy dowolny przekrój (0, x

i

, x

j

) pola funkcji f(x) pokazany na rys.8.1.

Rys.8.1. Schemat przekroju pola funkcji f(x) płaszczyzną (0 x

i

x

j

)

Składowe gradientu f(x) w punkcie (x

i

=0, x

j

=0) wynoszą

(8.9)

m

i

p

i

p

j

m

j

q

ij

r

ij

s

ij

t

ij

x

i

x

j

Diagonalne składniki hesjanu są równe

(8.10)

Wyznaczenie pozadiagonalnych składników hesjanu wymaga wprowadzenia dodatkowych

wartości funkcji f(x).

(8.11)

W wyniku otrzymuje się

(8.12)

Przybliżone wyznaczenie w danym punkcie hesjanu minimalizowanej funkcji n zmiennych

wymaga (2n+2n

2

) obliczeń funkcji w bezpośrednim otoczeniu tego punktu.

W analizie rzeczywistych funkcji celu mamy zazwyczaj do czynienia z dodatnimi ich

wartościami w całej dopuszczalnej przestrzeni optymalizacji, co wynika z ich sensu

fizycznego np. koszt, masa, pobór mocy. Wynika z tego, że diagonalne elementy hesjanu są

również dodatnie, a macierz z nich utworzona jest dodatnio określona

(8.13)

Fakt ten wykorzystuje modyfikacja Levenberga-Marquarta metody Newtona, której algorytm

jest następujący

1. W punkcie x

k

oblicz gradient f(x

k

) oraz hesjan [H(x

k

)];

2. Sprawdź czy hesjan jest dodatnio określony, jeśli tak to =

jeśli nie =1

3. Wyznacz kierunek d

k

spełniający [H(x

k

)+ diag[H(x

k

)]]d

k

= - f(x

k

);

4. Wykonaj minimalizację (określenie dodatniej liczby ) w kierunku d;

(8.14)

5. Sprawdź kryterium zatrzymania, jeśli nie jest spełnione to powrót do p.1.