Untitled 43

156

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

3.5.1. Metody podziału

Podany powyżej lemat umożliwia wyznaczenie ciągu przedziałów <n^w; ó^(,)>, / = 0, 1, ..., a⁽⁰⁾ = a, b⁽⁰⁾ = b takich, że <n^(,+1); b^(i+l)) <= <a^(,); ó^(,)>. Jeśli tak wybieramy punkty, aby b^U) — a⁽ⁱ⁾-+0, to na mocy twierdzenia Cantora ciągi (a⁽ⁱ⁾) oraz (b^<0) są zbieżne do jednego punktu, którym jest a.

Przedstawiamy kilka sposobów podziału przedziału (a^<l>; b^<0) i porównamy je pod względem efektywności obliczeń. Ogólny schemat algorytmu jest przedstawiony na rys. 3.7. Liczba g oznacza tu pożądaną dokładność wyznaczenia punktu a, tzn. chcemy uzyskać taki punkt t, by ae</-g; t -(- g}. Jako miarę efektywności metody, służącą do porównania algorytmów o różnych sposobach wyboru punktów podziału t⁽p, ..., przyjmujemy liczbę obliczeń funkcji potrzebnych do wyznaczenia punktu t.

Metoda podziału na trzy części. Jako punkty podziału przyjmujemy ty = 2 1.12

= - a + -b, tty = - a + -b, które dzielą przedział    ; b) na trzy równe części.

W każdej iteracji następuje zmniejszenie długości przedziału 3/2 razy. Po / iteracjach uzyskamy zatem przedział o długości b — a = ( \ ) (b^<0) — a^(0>) przy 2/obliczeniach funkcji. W metodzie tej każde obliczanie wartości funkcji zmniejsza przedział średnio razy.

3    1

Metoda połowienia. Jako punkty podziału przyjmujemy t⁽,°= - a + -ó,

11    13

r⁽2° = -a + -b, t\3°= -a + -b, które dzielą przedział <a; ó) na cztery równe

części. W każdej iteracji następuje zmniejszenie długości przedziału 2 razy. Po

-

I iteracjach uzyskamy zatem przedział o długości b — a =

przy 214- 1 obliczeniach funkcji w najgorszym przypadku (w pierwszej iteracji obliczamy 3 lub 2 wartości funkcji).

W metodzie połowienia każde obliczenie wartości funkcji zmniejsza przedział średnio 2 razy, choć w korzystnym przypadku jedno obliczenie wartości funkcji może zmniejszyć przedział 4 razy. Widzimy, że metoda połowienia jest bardziej ekonomiczna niż metoda podziału na trzy części. Nasuwa się naturalne pytanie, jak należy wybierać punkty podziału, aby osiągnąć t przy najmniejszej liczbie obliczeń wartości funkcji? Zajmiemy się zatem tym zagadnieniem.

3.5.2. Metoda optymalnych podziałów

Spośród metod podziału najmniejszej liczby obliczeń funkcji wymaga metoda korzystająca z liczb Fibonacciego (uzasadnił to Johnson, patrz np. [24]).