Metoda Newtona jest połączeniem idei iteracji i lokalnej
aproksymacji liniowej. W tej metodzie iteracyjnej xn+1 jest określone
jako odcięta punktu przecięcia z osią x stycznej do krzywej y=f(x) w punkcie
(xn,f(xn)).
Przybliżanie krzywej y=f(x) styczną do niej w punkcie (x0,f(x0)) jest równoważne zastąpieniu funkcji dwoma początkowymi składnikami jej szeregu Taylora w punkcie x=x0. Odpowiednie przybliżanie dla funkcji wielu zmiennych ma również ważne zastosowania.
Do wyznaczenia xn+1 służy równanie
Metodę Newtona określa następujący wzór iteracyjny:
gdzie
Iteracje można przerwać, gdy |hn| stało się mniejsze od dopuszczalnego błędu pierwiastka (trzeba tu uwzględnić również błędy zaokrągleń i inne błędy popełniane w obliczaniu hn).
Różnym od kreślenia stycznej sposobem lokalnej aproksymacji krzywej jest wybór dwóch sąsiednich punktów na niej i przybliżanie jej sieczną łączącą te punkty
Przykład
Dana jest funkcja f(x)=sinx-(0.5x)2. Wtedy
f '(x)=cosx-0.5x. Chcemy obliczyć dodatni pierwiastek z 5 poprawnymi cyframi ułamkowymi.
Przyjmijmy x0=1.5. Wyniki obliczeń podano w tablicy (jej ostatnią kolumnę można wypełnić dopiero po obliczeniu pierwiastka).
Szukanym pierwiastkiem jest 1.93375. Potrzebne były tylko cztery iteracje, mino że początkowe przybliżenie było dość kiepskie. Widzimy też, że |hn| maleje coraz szybciej aż do momentu, gdy zaczynają dominować błędy zaokrągleń.
Przyjmijmy x0=1.5. Wyniki obliczeń podano w tablicy (jej ostatnią kolumnę można wypełnić dopiero po obliczeniu pierwiastka).
Szukanym pierwiastkiem jest 1.93375. Potrzebne były tylko cztery iteracje, mino że początkowe przybliżenie było dość kiepskie. Widzimy też, że |hn| maleje coraz szybciej aż do momentu, gdy zaczynają dominować błędy zaokrągleń.
Oczywiście, gdy przybliżenie jest dalekie od
pierwiastka, nie trzeba (w obliczeniach ręcznych) używać zbyt wielu
cyfr. W powyższym przykładzie
trzeba tylko obliczyć f(xn) z tyloma cyframi ułamkowymi, ile mogłoby
być poprawnych w xn+1, gdyby hn obliczono dokładnie. Co
ważniejsze, ze zbyt dużą dokładnością obliczano pochodną. Wartość
f '(xn) jest tylko środkiem do obliczenia poprawki
Dlatego wystarczy obliczać f '(xn) z taką dokładnością względną, z jaką oblicza się f(xn). Ponieważ dokładność względna wartości f(xn) maleje, gdy xn zbliża się do pierwiastka, więc w powyższym przykładzie można by użyć wartości f '(x2) nawet dla n=3 i n=4. Takie uproszczenia mogą być czasem ważne nawet w obliczeniach komputerowych.
Dlatego wystarczy obliczać f '(xn) z taką dokładnością względną, z jaką oblicza się f(xn). Ponieważ dokładność względna wartości f(xn) maleje, gdy xn zbliża się do pierwiastka, więc w powyższym przykładzie można by użyć wartości f '(x2) nawet dla n=3 i n=4. Takie uproszczenia mogą być czasem ważne nawet w obliczeniach komputerowych.
en=xn-a
Przy powyższych założeniach możemy otrzymać zależność między en i en+1. Rozwijając funkcję f w szereg Taylora w otoczeniu xn, otrzymujemy
0=f(a)=f(xn)+(a-xn)f '(xn)+0.5(a-xn)2f "(x) gdzie xÎint(xn,a)
czyli, po podzieleniu przez f '(xn),
Stąd
a dla xna
Brak komentarzy:
Prześlij komentarz