:~$ newsletter --subscribe
cat ~/artykuly/algorytmy/rozwiazywanie-ukladu-rownan-nieliniowych-metoda-newtona.md

Rozwiązywanie układu równań nieliniowych metodą Newtona

Załóżmy, że mamy do rozwiązania układ równań nieliniowych czyli taki, który przybiera postać f(x) = 0 lub g(x) = h(x). Cały problem polega jednak na tym, że nasz układ jest tak duży, iż rozwiązanie go „metodą tradycyjną” przy użyciu kartki i długopisu nie wchodzi w grę. Trzeba więc do tego celu skorzystać z dobrodziejstw techniki czyli komputera. I tutaj zaczynają się kolejne schody…

Jak pewnie większości z Was obiło się o uszy, przy tego typu problemach nie możemy tak po prostu nakazać komputerowi wykonać konkretne obliczenia i czekać na wynik, gdyż albo w ogóle go nie dostaniemy (bo algorytm będzie wykonywał się przez kilkanaście lat) albo będzie on niepoprawny. Nie ma jednak się czym załamywać bowiem już jakiś czas temu kilku mądrych ludzi opracowało stosowne metody numeryczne, które pomogą nam rozwiązać niniejszy problem.

Należy jednak przy tym pamiętać, że równanie nieliniowe charakteryzuje się tym, że może nie mieć żadnego rozwiązania lub też może mieć ich wiele. Nie możemy więc tak po prostu zastosować znanej wszystkim metody Newtona. Będziemy musieli wprowadzić tutaj pewne modyfikacje. Różnica bowiem polega na tym, że w tym przypadku działamy na zmiennych macierzowych, a zamiast pochodnej liczymy macierz Jacobiego (macierz pochodnych cząstkowych).

Przeanalizujmy to na przykładzie…

Mamy dany następujący układ równań:

Do dalszych rozważań przyjmujemy punkt startowy:

Po przekształceniu równań otrzymujemy następującą postać:

Dostajemy więc układ równań nieliniowych:

Kolejnym krokiem będzie obliczenie wcześniej wspomnianej macierzy Jacobiego (w przypadku pojedynczego równania liczylibyśmy zwykłą pochodną):

Wzór ogólny:

Przykład:

Dalej postępujemy analogicznie jak w „tradycyjnej” wersji metody Newtona:

Dla przypomnienia w metodzie Newtona kolejne przybliżenia dane są wzorem rekurencyjnym:

W naszym przypadku będzie to tak:

Wzór ogólny:

Przykład:

1 iteracja:

2 iteracja:

Drugą iterację i każdą kolejną wykonujemy analogicznie z tym wyjątkiem, że startujemy od „nowego” wektora uzyskanego w iteracji poprzedniej. Czyli w naszym przypadku będzie to wektor:

Iteracje kontynuujemy do momentu uzyskania satysfakcjonującej dokładności.

.xlsxPobierz arkusz Excela z przykładowym rozwiązaniem nieliniowego układu równań metodą NewtonaNewtonDydaktycznie-w-Excelu.xlsx[ pobierz ]

Metoda Newtona na przykładzie: pierwiastek z 2

Zobaczmy metodę w akcji na najprostszym możliwym przykładzie. Szukamy pierwiastka z 2, czyli rozwiązania równania f(x) = x² – 2 = 0. Pochodna to f'(x) = 2x, a wzór iteracyjny metody Newtona ma postać:

x(n+1) = x(n) - f(x(n)) / f'(x(n))

Startujemy ze zgadniętego x = 1 i patrzymy, jak szybko kolejne przybliżenia zbiegają do prawdziwej wartości 1,41421356:

IteracjaxBłąd
01,000000000,41
11,500000000,086
21,416666670,0025
31,414215690,0000021
41,41421356~10⁻¹²

Cztery iteracje i mamy dwanaście cyfr dokładności. To jest właśnie słynna zbieżność kwadratowa metody Newtona: liczba poprawnych cyfr z grubsza PODWAJA się w każdym kroku.

Implementacja w Pythonie

python
def newton(f, df, x0, epsilon=1e-10, max_iter=50):
    x = x0
    for i in range(max_iter):
        fx = f(x)
        if abs(fx) < epsilon:          # warunek stopu: blisko zera
            return x, i
        x = x - fx / df(x)             # wzor Newtona
    return x, max_iter


# pierwiastek z 2: f(x) = x^2 - 2
wynik, kroki = newton(lambda x: x*x - 2, lambda x: 2*x, x0=1.0)
print(f"x = {wynik:.10f} po {kroki} iteracjach")   # x = 1.4142135624 po 5

Kiedy metoda Newtona zawodzi?

Szybkość ma swoją cenę: metoda nie zawsze zbiega. Cztery sytuacje, na które trzeba uważać:

  • Pochodna bliska zeru – dzielimy przez f'(x), więc płaski fragment funkcji wystrzeliwuje przybliżenie w kosmos.
  • Zły punkt startowy – iteracje mogą zbiec do INNEGO pierwiastka niż szukany albo wpaść w cykl i skakać w kółko.
  • Brak pochodnej w postaci wzoru – gdy f'(x) nie umiemy wyliczyć, stosuje się metodę siecznych, która przybliża pochodną z dwóch ostatnich punktów.
  • Pierwiastek wielokrotny – zbieżność spada z kwadratowej do liniowej i iteracji robi się wyraźnie więcej.

W praktyce te ograniczenia obchodzi się prosto: startujemy blisko szukanego rozwiązania (na przykład po zgrubnym zawężeniu metodą bisekcji) i zawsze ustawiamy limit iteracji, tak jak w kodzie powyżej.

Implementacje w Javie i C#

Java:

java
public class Main {

    static double f(double x)  { return x * x - 2; }   // szukamy pierwiastka z 2
    static double df(double x) { return 2 * x; }

    public static void main(String[] args) {
        double x = 1.0;
        for (int i = 0; i < 50 && Math.abs(f(x)) >= 1e-10; i++) {
            x = x - f(x) / df(x);   // wzor Newtona
        }
        System.out.printf("x = %.10f%n", x);   // x = 1.4142135624
    }
}

C#:

csharp
using System;

class Program
{
    static double F(double x)  => x * x - 2;
    static double Df(double x) => 2 * x;

    static void Main()
    {
        double x = 1.0;
        for (int i = 0; i < 50 && Math.Abs(F(x)) >= 1e-10; i++)
        {
            x = x - F(x) / Df(x);
        }
        Console.WriteLine($"x = {x:F10}");   // x = 1.4142135624
    }
}
Łukasz Dudziński
Łukasz Dudziński · założyciel i autor
Pasjonat informatyki, a zwłaszcza programowania. Zwariowany maniak na tle nowych technologii oraz komputerów. W wolnych chwilach bloger... więcej-o-mnie →
ls ~/artykuly/powiazane --limit 3
komentarze --count 0
rss dla komentarzy →

// brak komentarzy — bądź pierwszy

dodaj-komentarz

Komentarze są moderowane. Podane dane przetwarzamy wyłącznie w celu publikacji komentarza (polityka prywatności).