Metoda Newtona: szybko znajdź miejsca zerowe dzięki iteracyjnej aproksymacji

Niektóre równania po prostu nie mają eleganckiego rozwiązania algebraicznego.

Można rozkładać na czynniki i podstawiać do woli, ale część równań nie ma postaci domkniętej. Na przykład wielomiany stopnia piątego i wyższego nie mają ogólnego rozwiązania algebraicznego. Funkcje mieszające wykładniki z wielomianami, jak e^x = 3x, należą do tej samej kategorii. W takich przypadkach potrzebne jest inne podejście.

Tym podejściem jest metoda Newtona. Numerycznie znajduje miejsca zerowe, wykonując coraz trafniejsze przybliżenia — każde z nich wyznaczane przez styczną do funkcji w bieżącym oszacowaniu.

W tym artykule omówię wzór stojący za metodą Newtona, jej działanie krok po kroku, kiedy się zbiega, a kiedy nie — z konkretnymi przykładami, które utrwalą teorię.

Szukają Państwo więcej zagadnień matematycznych potrzebnych w data science? Proszę przeczytać nasz wpis Szeregi geometryczne: wzór, zbieżność i przykłady, aby zobaczyć ich zastosowania w finansach, fizyce i informatyce.

Czym jest metoda Newtona?

Metoda Newtona to technika iteracyjna służąca do znajdowania miejsc zerowych funkcji. Miejsca zerowe to wartości argumentu, dla których funkcja przyjmuje wartość zero.

Proces zaczyna się od wstępnego oszacowania. Następnie metoda wykorzystuje geometrię funkcji w tym punkcie, by zaproponować lepsze oszacowanie. Powtarza się te kroki, a każda iteracja przybliża do właściwego miejsca zerowego.

To cała idea. Potrzebna jest jedynie sprytna, powtarzalna reguła aktualizacji, która zbiega do rozwiązania.

Wzór metody Newtona

Sednem metody Newtona jest pojedyncza reguła aktualizacji, którą stosuje się wielokrotnie, aż wynik będzie dostatecznie blisko miejsca zerowego.

Oto wzór:

Wzór metody Newtona

Każda iteracja bierze bieżące oszacowanie x_n i wytwarza lepsze, x_{n+1}. Aktualizacje powtarza się, aż wynik będzie wystarczająco blisko zera.

Wzór ma trzy składowe:

• x_n — bieżące oszacowanie miejsca zerowego

• f(x_n) — wartość funkcji w tym oszacowaniu

• f'(x_n) — pochodna funkcji w tym punkcie, która mówi o nachyleniu stycznej

Jeśli f(x_n) jest duże, oznacza to, że daleko nam do miejsca zerowego. Jeśli f'(x_n) jest strome, funkcja szybko się zmienia, więc można wykonać większy krok. Iloraz f(x_n) / f'(x_n) dokładnie wskazuje, jak daleko się przesunąć — i odejmujemy go od bieżącego oszacowania, aby się przybliżyć.

Gdy f'(x_n) wynosi zero lub jest bliskie zeru, wzór w praktyce nie działa. Dzielilibyśmy przez zero, co oznacza, że metoda nie potrafi wyznaczyć kolejnego oszacowania. Omówię to szerzej w sekcji o ograniczeniach.

Jak działa metoda Newtona

Metoda Newtona w każdej iteracji wykonuje te same cztery kroki.

1. Wybierz wstępne oszacowanie: Proszę wybrać wartość początkową x_0 gdzieś w pobliżu miejsca zerowego. Nie musi być dokładnie — wystarczy na tyle blisko, by funkcja zachowywała się przewidywalnie w tej okolicy. Wyjaśnię, co znaczy „wystarczająco blisko”, w sekcji o zbieżności.

2. Oblicz wartość funkcji: Proszę obliczyć f(x_0). To pokazuje, jak daleko funkcja jest od zera przy bieżącym oszacowaniu. Jeśli f(x_0) = 0, to koniec — znaleziono miejsce zerowe.

3. Oblicz pochodną: Proszę obliczyć f'(x_0). To daje nachylenie funkcji w punkcie x_0, czyli nachylenie stycznej w tym miejscu.

4. Zaktualizuj oszacowanie: Proszę zastosować regułę aktualizacji według wzoru z poprzedniej sekcji.

I gotowe!

Nowa wartość x_1 to punkt, w którym styczna przecina oś x. Geometrycznie: rysują Państwo prostą, która dotyka krzywej w x_0, i prowadzą ją do zera. Punkt przecięcia to kolejne, lepsze oszacowanie.

Następnie proszę powtórzyć. Podstawić x_1 z powrotem w kroki 2–4, aby uzyskać x_2, potem x_3 itd. Każda iteracja rysuje nową styczną w zaktualizowanym punkcie i znajduje jej przecięcie z osią x.

Proces zatrzymuje się, gdy f(x_n) jest wystarczająco bliskie zeru — zwykle gdy spadnie poniżej małego progu zdefiniowanego z góry.

Geometryczna interpretacja metody Newtona

Proszę wyobrazić sobie krzywą na wykresie — to Państwa funkcja f(x). Miejsce zerowe to punkt, w którym krzywa przecina oś x. Nie wiadomo jeszcze, gdzie to przecięcie się znajduje, więc zaczynamy od oszacowania x_0 gdzieś na osi x.

W każdym kroku nanoszą Państwo punkt (x_0, f(x_0)) na krzywej, a następnie rysują styczną w tym punkcie — prostą, która dotyka krzywej i ma takie samo nachylenie. Ta styczna nie jest pozioma. Jest nachylona i po przedłużeniu przetnie oś x w pewnym miejscu. To przecięcie to kolejne oszacowanie, x_1.

Potem powtarzamy. W punkcie x_1 rysujemy nową styczną i znajdujemy jej przecięcie z osią x. To daje x_2. Każda styczna jest lokalną liniową aproksymacją krzywej, a każdy punkt przecięcia ląduje bliżej właściwego miejsca zerowego.

Poniższy wykres pokazuje dwie iteracje metody Newtona zastosowane do f(x) = x^2 - 2, zaczynając od x_0 = 2.5:

Wykres interpretacji geometrycznej

To działa, ponieważ styczna jest najlepszą prostoliniową aproksymacją krzywej w danym punkcie. Im bliżej miejsca zerowego, tym bardziej styczna przypomina samą krzywą — a kolejny krok staje się dokładniejszy.

W praktyce oszacowania nie „pełzną” ku miejscu zerowemu. Skaczą tam szybko, często podwajając liczbę poprawnych miejsc po przecinku w każdej iteracji.

Przykład metody Newtona krok po kroku

Zastosujmy metodę Newtona do f(x) = x^2 - 2. Miejsce zerowe tej funkcji to x = sqrt(2) ≈ 1.4142 — innymi słowy, obliczamy pierwiastek kwadratowy z 2.

Pochodna to f'(x) = 2x, więc reguła aktualizacji przyjmuje postać:

Przykład (reguła aktualizacji)

Zacznijmy od wstępnego oszacowania x_0 = 2.5.

Iteracja 1:

Przykład (iteracja 1)

Iteracja 2:

Przykład (iteracja 2)

Iteracja 3:

Przykład (iteracja 3)

Zaledwie po trzech iteracjach mamy już dokładność do czterech miejsc po przecinku. Błąd spadł z 1.086 przy x_0 do 0.0001 przy x_3 — i dalej maleje z każdym krokiem.

Tak wygląda wizualizacja oszacowań i błędów:

Wizualny przegląd oszacowań i błędu

Panel po lewej pokazuje, jak każde oszacowanie zbliża się do sqrt(2) ≈ 1.4142, a panel po prawej przedstawia malejący błąd w skali logarytmicznej — każda iteracja mniej więcej podwaja precyzję poprzedniej.

Zbieżność metody Newtona

Metoda Newtona może zbiegać szybko, ale tylko przy spełnieniu odpowiednich warunków.

Gdy wstępne oszacowanie jest blisko miejsca zerowego, a funkcja jest gładka w tym obszarze, metoda wykazuje zbieżność kwadratową. To techniczny termin opisujący to, co było widać w przykładzie: każda iteracja w przybliżeniu podnosi do kwadratu błąd z poprzedniej. Dwa poprawne miejsca po przecinku stają się czterema, cztery — ośmioma itd.

Aby to działało, muszą być spełnione dwa warunki:

• Dobre wstępne oszacowanie: Im bliżej rzeczywistego miejsca zerowego leży x_0, tym szybciej metoda się zbiega. Jeśli start jest zbyt odległy, styczna w tym punkcie może poprowadzić w złą stronę.
• Dobrze zachowująca się funkcja: Funkcja powinna być gładka i różniczkowalna w pobliżu miejsca zerowego. Ostro zakręcające lub płaskie fragmenty mogą zaburzyć aproksymację styczną.

Najczęstszym trybem awarii jest pochodna bliska zeru. 

Jeśli f'(x_n) jest bliska zeru, w regule aktualizacji dzielą Państwo przez bardzo małą liczbę, co przenosi kolejne oszacowanie daleko od miejsca zerowego. W najgorszym przypadku f'(x_n) = 0 i obliczenia przestają działać, bo nie można dzielić przez zero.

Słaby punkt startowy może też powodować oscylacje lub rozbieżność. Zamiast zbliżać się do miejsca zerowego, oszacowania skaczą tam i z powrotem albo z każdą iteracją oddalają się.

Metoda Newtona premiuje dobre przygotowanie. Rozsądne wstępne oszacowanie i gładka funkcja wystarczą, by zbiegała — i to szybko.

Zalety metody Newtona

Gdy warunki są spełnione, metoda Newtona jest trudna do pobicia.

Największą zaletą jest zbieżność kwadratowa. Większość metod numerycznych zbliża się do miejsca zerowego w tempie liniowym, tzn. każda iteracja redukuje błąd o stałą wartość. Metoda Newtona zamiast tego podnosi błąd do kwadratu, co oznacza szybkie osiąganie wysokiej dokładności przy bardzo niewielu iteracjach.

Jest też uniwersalna. Można ją stosować do szerokiej gamy funkcji — wielomianowych, trygonometrycznych, wykładniczych — bez zmian w samej metodzie. Dlatego pojawia się w tak wielu dziedzinach, od symulacji inżynierskich po trenowanie modeli uczenia maszynowego.

Ograniczenia metody Newtona

Za tę szybkość metoda Newtona sporo wymaga. Oto kilka ograniczeń, o których warto pamiętać:

• Wymaga pochodnej: Potrzebna jest analityczna postać f'(x), zanim wykona się choć jedną iterację. Dla funkcji, dla których pochodną trudno obliczyć (lub nie istnieje), trzeba użyć innego podejścia.

• Jest wrażliwa na punkt startowy: Jeśli start jest zbyt daleko od miejsca zerowego, metoda może poprowadzić w złą stronę.

• Może się nie zbiegać: Jeżeli funkcja ma płaskie obszary lub ostre zakręty, aproksymacja styczną po prostu nie zadziała.

• Może się rozbiegać lub oscylować: W niekorzystnych przypadkach oszacowania nie zbliżają się do rozwiązania, lecz oddalają albo bez końca skaczą w tę i z powrotem.

Dlatego zanim sięgną Państwo po metodę Newtona, proszę dobrze zrozumieć swoją funkcję.

Metoda Newtona a inne metody znajdowania miejsc zerowych

Metoda Newtona nie jest jedynym sposobem znajdowania miejsc zerowych i nie zawsze będzie dla Państwa najlepsza.

Często pojawiają się jeszcze dwie: metoda bisekcji i metoda siecznych. Krótko je wyjaśnię.

Metoda bisekcji

Metoda bisekcji jest najprostsza z trzech. Zaczyna się od przedziału [a, b], w którym funkcja zmienia znak — co oznacza, że gdzieś w środku musi istnieć miejsce zerowe. Następnie wielokrotnie dzieli się przedział na pół, zachowując tę połówkę, w której wciąż zachodzi zmiana znaku.

Działa, ale jest wolna. Błąd zmniejsza się o połowę w każdej iteracji, co daje zbieżność liniową. Za to jest gwarantowana, o ile funkcja jest ciągła, a początkowy przedział obejmuje miejsce zerowe. Pochodne nie są potrzebne.

Metoda siecznych

Metoda siecznych jest bliską krewną metody Newtona. Zamiast analitycznie liczyć pochodną, aproksymuje ją, korzystając z dwóch poprzednich oszacowań:

Wzór metody siecznych

To dobre podejście, gdy pochodną trudno obliczyć. Ceną jest szybkość zbieżności — metoda siecznych jest szybsza niż bisekcja, ale wolniejsza niż metoda Newtona.

Zastosowania metody Newtona

Metoda Newtona pojawia się w nauce, inżynierii i uczeniu maszynowym. Oto jak dokładnie.

Numeryczne rozwiązywanie równań

Najbardziej bezpośrednie zastosowanie. Gdy funkcja nie ma rozwiązania w postaci domkniętej, metoda Newtona znajduje miejsce zerowe. To pojawia się nieustannie w obliczeniach naukowych — proszę pomyśleć o znajdowaniu punktów równowagi w reakcjach chemicznych czy rozwiązywaniu równań transcendentalnych w przetwarzaniu sygnałów.

Optymalizacja

Znalezienie minimum lub maksimum funkcji f(x) oznacza znalezienie punktów, gdzie jej pochodna f'(x) = 0. To problem znajdowania miejsc zerowych — a więc można zastosować metodę Newtona. Wystarczy uruchomić algorytm na f'(x) zamiast na f(x), używając drugiej pochodnej f''(x) w miejsce pierwszej.

Ta odmiana nazywa się metodą Newtona w optymalizacji i zbiega szybciej niż spadek gradientowy dla gładkich, dobrze zachowujących się funkcji.

Uczenie maszynowe

W uczeniu maszynowym trenowanie modelu oznacza minimalizację funkcji straty. Metoda Newtona i jej odmiany pojawiają się tu w kilku miejscach.

L-BFGS (Limited-memory Broyden-Fletcher-Goldfarb-Shanno) to quasi-newtonowski optymalizator, który aproksymuje drugą pochodną, by uniknąć jej bezpośredniego wyznaczania. To standardowy wybór dla regresji logistycznej i innych problemów wypukłych. Metoda Newtona stanowi też podstawę aktualizacji Newtona-Raphsona stosowanych w dopasowywaniu modeli statystycznych, takich jak uogólnione modele liniowe.

Fizyka i inżynieria

Metoda Newtona jest wszechobecna w symulacji i projektowaniu. Inżynierowie używają jej do rozwiązywania nieliniowych układów równań opisujących systemy fizyczne — na przykład w analizie wytrzymałości konstrukcji czy dynamice płynów. W każdym przypadku problem sprowadza się do znalezienia punktu, w którym układ równań przyjmuje wartość zero.

Częste błędy w metodzie Newtona

Większość problemów z metodą Newtona sprowadza się do tych samych czterech błędów. Oto one:

• Start zbyt daleko od miejsca zerowego: Słabe wstępne oszacowanie to najczęstszy powód rozbieżności lub oscylacji. Jeśli nie mają Państwo dobrej intuicji, gdzie leży miejsce zerowe, warto najpierw narysować wykres funkcji. To podpowie, gdzie zacząć.

• Błędna pochodna: Reguła aktualizacji zależy od f'(x). Zła pochodna — czy to wskutek pomyłki rachunkowej, czy błędu w kodzie — od pierwszej iteracji daje błędne oszacowania, a błąd narasta z kolejnymi krokami.

• Brak kontroli dzielenia przez zero. Jeśli f'(x_n) równa się zero lub jest mu bardzo bliska, krok aktualizacji nie zadziała. Proszę dodać zabezpieczenie w implementacji: jeśli pochodna spada poniżej małego progu, należy przerwać i zgłosić niepowodzenie zamiast zwracać bezsensowny wynik.

• Zbyt wczesne zatrzymanie. Przerwanie iteracji przed zbieżnością pozostawia wynik, który wygląda na bliski, ale taki nie jest. Proszę ustawić warunek stopu na rzeczywistym błędzie — gdy |f(x_n)| lub |x_{n+1} - x_n| spadnie poniżej celowo wybranego progu, a nie po z góry ustalonej liczbie iteracji.

Wnioski

Metoda Newtona to jedno z najprzydatniejszych narzędzi w obliczeniach numerycznych. Pojedyncza reguła aktualizacji, stosowana wielokrotnie, potrafi znaleźć miejsca zerowe z dowolną precyzją w zaledwie kilku iteracjach.

Za tę szybkość płaci się warunkami. Aby szybko zbiegać, potrzebne jest dobre wstępne oszacowanie, funkcja nie może być płaska ani „kolczasta”, a pochodna nie może być zerowa. Wystarczy rozumieć te warunki, by wiedzieć, kiedy sięgnąć po metodę Newtona, a kiedy użyć czegoś innego (np. metod bisekcji lub siecznych).

Najlepszym sposobem na zbudowanie intuicji jest ćwiczenie na prostych przykładach. Proszę zacząć od f(x) = x^2 - 2, wypróbować różne punkty startowe i obserwować, co się dzieje. Następnie przejść do funkcji z wieloma miejscami zerowymi lub płaskimi fragmentami i zobaczyć, gdzie metoda się wykłada.

Jeśli podoba się Państwu koncepcja optymalizacji przez iteracje, warto poznać spadek gradientowy. Proszę przeczytać Gradient Descent in Machine Learning: A Deep Dive, aby dowiedzieć się, jak optymalizuje modele uczenia maszynowego.