240
6. Równania nieliniowe
powtarzać; natychmiast po znalezieniu pierwiastka wyłącza się go z wielomianu. W ten sposób mamy do czynienia 7. wielomianami coraz niższych stopni.
Oczywiście defiacja zmniejsza liczbę działań arytmetycznych. Inną jej zaletą jest t0 że iteracje nie mogą być zbieżne kilkakrotnie do tego samego pierwiastka pojedynczego' W tych przypadkach, gdy informacja o pierwiastkach jest zła, można działać w następujący sposób. Wybiera się mniej lub bardziej losowo przybliżenie początkowe. Z dużym prawdopodobieństwem otrzyma się zbieżność do pewnego pierwiastka. Można wyłączyć go z wie-lomianu i postępować tak dalej, aż do znalezienia wszystkich pierwiastków.
Pomijaliśmy dotąd to, że zk nie jest dokładnym pierwiastkiem równania p(2)-o Pominęliśmy też błędy zaokrągleń popełnianych w obliczaniu bQ, ó,,Oczywiście zachodzi obawa, że te błędy spowodują coraz większe odchylenia zer kolejnych ilorazów od zer wielomianu p(z). Dokładniejsza analiza (zob. Wilkinson [68]) pokazuje, że błędy wywołane dcflacją są pomijalne przy założeniu, że
1. pierwiastki wyznacza się w kolejności rosnących modułów,
2. każdy pierwiastek wyznacza się z graniczną dokładnością.
Pierwsze żądanie oczywiście trudno spełnić. W metodzie Laguerre^ jest jednak bardzo prawdopodobne, że przyjmując z0-0 (zob. przykład 6.8.1) uzyskamy zbieżność d<5 pierwiastka o najmniejszym module. Dla bezpieczeństwa można najpierw wyznaczyć wszystkie pierwiastki (używając przy tym deflacji), a potem dla każdego z nich wykonać jeszcze jedną iterację posługując się pierwotnym wielomianem p(z).
6.8.3. Żłe uwarunkowane równania algebraiczne
Zauważyliśmy wcześniej, że pierwiastki wielokrotne są na ogół źle uwarunkowane, tzn. są wrażliwe na zaburzenia spowodowane np. błędami zaokrągleń. Jest więc naturalne, żc jeśli równanie p(z) =0 ma kilka bliskich siebie pierwiastków (ma pierwiastki prawie wielokrotne), to są one wrażliwe na zaburzenia współczynników wielomianu p(z). Bardziej zaskakujące jest to, że te pierwiastki mogą być bardzo źle uwarunkowane nawet wtedy, gdy — j3k się wydaje — są wyraźnie rozdzielone. Kolejny przykład pokazuje, co może się zdarzyć.
Przykład 6.8.2. Rozważmy wielomian
p(z)=(z-l)(z-2)...(z-20) = z2o-210z,9 + ...+20!
o zerach 1, 2,...» 20. Niech wielomian p(z) powstaje z p(z) przez zmianę współczynnika ax = — 210 na
— (210+2“23)= -210.000000119...
Chociaż zmiana względna współczynnika jest rzędu lO"-10, wiele pierwiastków' równam* p(z)=0 różni się bardzo od pierwiastków równania p(z)=Q. To pierwsze równanie m* np. pierwiastki (dokładne do dziewięciu cyfr ułamkowych)
16.730737466 ± 2.812624894* (!).