425 2

425

10.5. Nieliniowe zadania. opłymaliza^i

Wymaga się dobrego przybliżenia początkowego (nic jest ono potrzebne tylko ttftedy. gd>' funkcja g jest w przybliżeniu liniowa, tzn. gdy y jest w przybliżeniu kwadra-

*^0V(b) W klasycznej metodzie Newtona trzeba obliczać hesjan (co najmniej w przybli-£0jn, wyrażony przez ilorazy różnicowe) i w każdej iteracji trzeba rozwiązywać układ

liniowy

G(x)d(x)=g(x).

Aby uniknąć tych trudności, opracowań owiele innych metod iteracyjnych. Mają one ogólną postać

(|0.5.5)    ^Xv+ 1 ⁼ Xr ~ f'1 •

W każdej iteracji w>'konuje się dwie czynności:

|. Wybór kierunku poszukiwania d_t.

2. Poszukiwanie wzdłuż prostej w tym kierunku.

Używa się często obrazowej terminologii topograficznej ze słowami takimi jak „dclina”, „spadek”, „niecka”, „poszukiwanie" i (dla szukania maksimum) „wejście na szczyt”, „grzbiet”, „wierzchołek” itd. (rys. 10.5.1).

10.5.2. Poszukiwanie wzdłuż prostej

Niech będzie ę {x_w~?aL) = ip (2). Załóżmy, że d, jest kierunkiem spadku. tzn. żc wartość ^ (0) = - dĘ g (_Xy) jest ujemna. Chcemy znaleźć takie 2_r e [0, m], że

^■⁵-6)    pr(2_r)<^(0) i ^(2_v)<min^(2)+e_>

^^z‘^e m i e są pewnymi stałymi, być może zależnymi od v.

tv.W literaturze matematycznej opisano wiele algorytmów wykonujących tę czynność;

Dixon [139], rozdział 1. Poniżej opisano nieznacznie zmodyfikowaną metodę Powella. ^ywa się w niej wielomianu interpolacyjnego kwadratowego {2(2), wyznaczonego przez ?^rzy punkty (a, y/ (<2>), (b, <// (ó)), (c, ty (c)). Na początku przyjmujemy «=0, b-k, gdzie k .^^paramctTem opisującym spodziewany rząd wielkości 2, (dla metod aktualizacji ma-opisanych w § 10.5.3 wybiera się k równe 1). Jeśli y(A)>y(0), to przyjmuje się, ^c=a*~k, a w przeciwnym razie c~2k.