Untitled 44

3. Przybliżone rozwiązywanie równań nieliniowych i ich układów 158

Przypominamy, że liczby Fibonacciego F, są określone wzorem rekurencyj-nym

F₀ = Fi = 1, Fj = F,_, + F,_₂, i = 2, 3, ... Na przykład: F₁ = 21,    F,₀ = 89.

b^m _ _fl(0) Q

Algorytm optymalnego podziału jest następujący. Niech c = Znajdujemy takie N, aby F_N_, < c ^ F_N. Określamy

t⁽p= ' - (b — a) + a Fn-i+ i

t⁽2°= -_fi —(6-a) + a, i = 1,2, ..., A — 2 •'W-/+1

Zgodnie z rys. 3.7 w każdej iteracji obliczamy nowe punkty a i b w sposób następujący:

Jeżeli/(/⁽j⁾) ^    to a pozostaje bez zmiany, b = t⁽%.

Jeżeli /(f⁽j^}) > f{t⁽2), to a — t⁽ⁱJ, a b pozostaje bez zmiany.

P

Po /-tej iteracji długość przedziału <a; i) zostaje zmniejszona    -—

Ff/-i+\

razy bez względu na to, która nierówność jest spełniona.

Po (N — 2) iteracjach długość przedziału zostaje zmniejszona do wartości

(b-a) =

Fn-1 Fn-2    _

F_N F_n_ 1    F_:

*V⁰⁾ - a⁽⁰⁾) = 2

_bw _ _fl(0)

Wykonano łącznie N — 1 obliczeń wartości funkcji.

Przykład. Znaleźć minimum funkcji f(x) = |jc| zlokalizowane w przedziale <—4; 4>. Pożądana dokładność q = 1.

Przykład ten rozwiążemy dwiema metodami:

a)    Metoda połowienia

/V>= -2, ty>=o, ry>=2

/(-2) </(0), /(2) >/(0) =- <u; ń> = <-2; 2> f<²⁾= -l, r«)=o, t‘²>= 1

/(-1) >/(0), /(l) >/(0) =><—u; 6> = <1; l>=>f = 0

/(O = 0

Wykonano łącznie 5 obliczeń funkcji.

b)    Metoda Johnsona

b — a

F_s = 8 =-, więc N = 5

e

3.5. Poszukiwanie minimów funkcji jednej zmiennej

159

/(,”= I'⁸ + (-4) = -1, ry’ = |-8 + (-4) = 1 /(-i)=/(i)=»<«; *> = <-4; i>

/<²>=?-5 + (-4)= -2,    ł?>=j-5 + (-4)=-l

/(—2) >/(—1)=> <a; by = <—2; 1>

,w=i-3 + (—2) = —1,    f⁽2^3,= j-3 + (-2) = 0

/(— 1) >/(0) =>(a;    = < — 1; l>~/ = 0

/(O = o

Wykonano łącznie 4 obliczenia wartości funkcji.

Uwaga. Ponieważ do zmniejszenia — razy długości przedziału potrzeba N — 1 obliczeń

N-\ [F~_N

wartości funkcji, więc jedno obliczenie wartości funkcji zmniejsza średnio przedział    /—

275

1,61.

razy. Można wykazać, że    Iz^/£)

Zatem lim

yv—oo

*->IT_n 1+75

1,22, a dla

Dla porównania wskaźnik ten dla metody podziału na trzy części wynosi metody połowienia J2 a 1,41.

3.5.3. Metoda złotego podziału

< Metoda ta polega na takim wyborze punktów podziału t\⁰ oraz t⁽2°, aby przedział (a; b) zmniejszał swą długość po każdej iteracji tyle samo razy oraz by po wyznaczeniu punktów nowego podziału, tzn. t⁽(⁺ 0 i t⁽2⁺ jeden z tych punktów pokrywał się z wyznaczonym punktem podziału w poprzedniej iteracji. Ma to na celu zmniejszenie obliczeń wartości funkcji, gdyż jedynie w pierwszej iteracji obliczamy dwie wartości funkcji, w następnych zaś już tylko jedną wartość funkcji. Zauważmy, że cechę tę miał omówiony poprzednio algorytm optymalny. Wymagania powyższe spełnia algorytm, w którym

Ą⁰ — a = b — t\° = x {b — a),    x e (0; 1)

b - t<j> = x(b - t<?)

Stąd t² + x — 1 = 0, czyli x =    « 0,62. Liczba x jest stosunkiem