Untitled 39

148

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

i

E = p^k gdzie p — rząd metody, a k — koszt jednej iteracji. Koszt jednej iteracji zależy głównie od tego, ile razy w każdym kroku trzeba obliczać wartość funkcji f(x) lub jej pochodnych, natomiast mało zależy od operacji arytmetycznych wykonywanych na wartościach tych funkcji. Będziemy dalej przyjmować, że koszt obliczenia wartości funkcji f(x) jest równy 1.

Metoda połowienia, podobnie jak metoda reguła falsi są rzędu 1 i ich wskaźnik efektywności jest także równy 1. Metoda siecznych jest szybciej od

nich zbieżna i jest rzędu ^(1 + ^/ó) a; 1,62; tyle samo wynosi wskaźnik

efektywności E dla tej metody. Dla metody Newtona, która jest rzędu 2, mamy£ = 2^1/(1 +k), gdzie k' jest kosztem obliczania pochodnej/'(jc). Ralston [50] sugeruje, że gdy k' < 0,44, lepiej stosować metodę Newtona zamiast metody siecznych.

W przypadku pierwiastków wielokrotnych metoda Newtona jest rzędu 1, natomiast gdy znana jest krotność pierwiastka r i można korzystać ze wzoru (3.21) rząd metody wzrasta do 2. Podobnie podstawienie (3.22) poprawia rząd, lecz efektywność metody staje się nieco niższa.

W przypadku pierwiastków zespolonych metoda Newtona jest zbieżna, jeżeli tylko przybliżenie początkowe jest dostatecznie bliskie pierwiastka, a jej rząd zbieżności jest równy 2. Podobnie metoda siecznych jest dla dostatecznie bliskich przybliżeń początkowych zbieżna do pojedynczych pierwiastków

zespolonych, a jej rząd jest równy ^(1 + ,/5). Metoda Bairstowa jest metodą rzędu 2.

Ciekawe porównanie szybkości zbieżności dla metody siecznych i metody stycznych przedstawiono w tablicy 3/10. Są to wyniki rozwiązywania równania jc³ + x + 10 = 0 w przedziale < — 3; 1) z dokładnością e = 10^-5. Wyraźnie można zaobserwować, jak w miarę zbliżania się do wartości pierwiastka zbieżność ciągu kolejnych przybliżeń w metodzie siecznych jest coraz powolniejsza (wynika to, między innymi, ze wzorów (3.11) i (3.19) na oszacowanie błędu w poszczególnych metodach).

3/10

Nr iteracji	Metoda siecznych	Metoda stycznych	Nr iteracji	Metoda siecznych	Metoda stycznych
1	-1.5714286	-2.285714286	8	-1.9996824
2	-1.8361045	-2.032173457	9	-1.9998888
3	-1.9406551	-2.000468841	10	-1.9999611
4	-1.9789723	-2.000000101	11	-1.9999864
5	-1.9926082		12	-1.9999952
6	-1.9974089		13	-1.9999983
7	-1.9990926

Przy poszukiwaniu zer wielomianu po znalezieniu przybliżenia pierwiastka badanego wielomianu wygodnie jest podzielić ten wielomian przez czynnik liniowy zawierający ten pierwiastek i następne pierwiastki wyznaczać dla tak otrzymanego ilorazu. Zastąpienie wyjściowego wielomianu wielomianem niższego stopnia nazywa się obniżeniem stopnia lub deflacją. Korzyści ze stosowania deflacji polegają przede wszystkim na stopniowym zmniejszaniu pracochłonności przy wyznaczaniu następnych pierwiastków i związaną z tym oszczędnością pamięci maszyny, a także na uniknięciu powtórnego wyznaczenia tych samych pierwiastków. Często bowiem zdarza się, że nawet przy starcie z punktu położonego w pobliżu innego pierwiastka procedura iteracyjna doprowadza nas do uprzednio już znalezionego pierwiastka.

Wilkinson [68] wykazał, że błędy powstające przy deflacji są do pominięcia gdy:

—    pierwiastki obliczamy kolejno ze wzrostem ich wartości bezwzględnych,

—    każdy pierwiastek zostaje obliczony z maksymalną graniczną dokładnością.

W każdej z omawianych powyżej metod możemy osiągnąć maksymalną graniczną dokładność przybliżenia pierwiastka [38].

n

Dzieląc wielomian /(z) = £ a_tzⁿ~^l przez czynnik liniowy z — x, mamy

i-0

n    n — 1

Z Oj z" ~' = Z bjZⁿ~‘~'(z - x) = Q(z)(z - x)

i=0    i=0

Stąd otrzymujemy układ równań dla wyznaczania współczynników ó, wielomianu Q (z)

b_n = b._l = 0 a_i = b_i-b_i__ix, i = 0, 1, 2, ..., n

Układ ten rozwiązujemy zazwyczaj albo zwykłym algorytmem Homera (3.31), albo odwrotnym algorytmem Homera (dla x ¥= 0)

b_n = 0

(3.55)

ó,_, = (bi - a,)/x, i = n,n-1,    1

Można także wykorzystać oba te sposoby, wyznaczając dla dowolnego

k = 0,1,2,..., n współczynniki b₀, b.....,b_k ze wzoru (3.31), a b_k+l, b_kJrl,...

..., b_n z (3.55) —jest to tzw. sklejany algorytm Homera. W pracy [38] można znaleźć dane na temat „sklejania” algorytmu Homera i oszacowanie zaburzeń zer wielomianu Q (z) w wyniku deflacji, a także w wyniku p etapów deflacji. Wykazano tam, że zera wielomianu R (z), otrzymanego po p etapach deflacji, są zerami zaburzonego wielomianu /(z) z zaburzeniami rzędu 2~‘pn, gdzie t — liczba cyfr mantysy binarnej, a n — stopień wielomianu (kolejność