Metoda Newtona¶

Pętle bardzo często używane są w programach obliczających wartości liczbowe, które zaczynają od wyników przybliżonych i iteracyjnie go poprawiają.

Przykładowo jedną z metod oblicznania pierwiastka kwadratowego jest metoda Newtona. Załóżmy, że musicie obliczyć pierwiastek kwadratowy z liczby n. Jeżeli wystartujecie z dowolnej wartości przybliżonej, to możecie obliczyć bardziej zbliżoną do prawdziwego wyniku wartość, używając wzoru:

lepiej =  1/2 * (przyblizona + n/przyblizona)

Wykonajcie taką operację kilkukrotnie. Czy widzicie dlaczego każda iteracja przybliża wasze oszacowanie do prawdziwego wyniku? Jedną z niezwykłych własności tego algorytmu jest jego bardzo szybka zbieżność do poprawnego wyniku.

Poniższa implementacja metody Newtona wymaga użycia dwóch parametrów. Pierwszym jest liczba, której pierwiastek będziemy przybliżać. Drugą jest ilość iteracji obliczeń w celu uzyskania lepszego przybliżenia.

Możecie zauważyć, że drugie i trzecie wywołanie funkcji newton_sqrt w powyższym przykładzie, zwracają takie same wartości pierwiastka kwadratowego z liczby 10. Użycie 10 iteracji zamiast 5 nie poprawiło zbytnio wyniku. W ogólności można powiedzieć, że metoda Newtona zawsze dojdzie do takiego punktu, że kolejna iteracja nie polepszy obencego przybliżenia. W tym punkcie powinniśmy po prostu zatrzymać program. Innymi słowy — poprzez wielokrotne użycie tego wzoru do momentu, gdy kolejne przybliżenie nie będzie się znacząco różnić od poprzedniego, możemy napisać funkcję, która będzie obliczać pierwiastek kwadratowy, używając dokładnie tyle iteracji, ile potrzeba, nie więcej.

Implementacja tej idei pokazana w codelens używa pętli while z warunkiem, sprawdzającym czy przybliżenie już się nie zmienia. Przy każdym obrocie pętli obliczamy „lepsze” przybliżenie za pomocą wzrou opisanego na początku. Tak długo jak „lepsze” jest różne od obecnego, próbujemy jeszcze raz. Przejdź przez program i zwróć uwagę na poprawiające się przybliżenie.