Laboratorium 6: Funkcje. Metoda Newtona-Raphsona

Postawienie problemu

Załóżmy, że mamy wyznaczyć pierwiastek stopnia $n$ z liczby $w$, czyli znaleźć taką liczbę $x$, że: $$x^n=w$$ lub inaczej: $$x^n-w=0$$ Jeżeli oznaczymy $f(x)=x^n-w$ to zadanie to można zapisać ogólniej: należy znaleźć takie $x$, że $f(x)=0$.

Jeżeli zadanie dodatkowo uprościmy zakładając:

funkcja ma dokładnie jedno miejsce zerowe,
jest różniczkowalna,
jej pochodna w całym przedziale jest albo dodatnia albo ujemna;

to możemy naszkicować rysunek (rys. 1) ilustrujący nasze zadanie.

Przykład funkcji spełniającej założenia oraz ilustracja pierwszych kroków algorytmu

Zaczynamy w punkcie $g$; wartość funkcji w tym punkcie wynosi $f(g)$. Musimy w jakiś sposób zdecydować w którym kierunku należy wykonać następny krok. Zauważmy, że możemy w tym celu wykorzystać pochodną (czerwona, przerywana linia na poprzednim rysunku). Jeżeli przybliżymy funkcję za pomocą pochodnej (stycznej do) funkcji, przechodzącej przez punk $(g,f(g))$ to następnym przybliżeniem miejsca zerowego będzie punkt przecięcia stycznej z osią $x$.

Z równania prostej mamy: $$\frac{f(g)-0}{g-g’}=f’(g)$$ czyli $$\frac{f(g)}{f’(g)}=g-g’$$ i dalej $$g’=g-\frac{f(g)}{f’(g)}$$

Jeżeli zauważymy, że $f(x)=x^n-w$ oraz, że $f’(x)=nx^{n-1}$ to kolejne przybliżenie wyliczane będzie ze wzoru: $$g’=g-\frac{g^n-w}{ng^{n-1}}$$ albo $$g’ = \frac{ng^n-g^n+w}{ng^{n-1}} = \frac{(n-1)g^n+w}{ng^{n-1}} = \frac{1}{n} \left((n-1)g + \frac{w}{g^{n-1}}\right)$$

Gdy $n=2$, wówczas $$g’ = \frac{1}{2}\left(g+\frac{w}{g}\right).$$

Istotą algorytmu jest powtarzanie powyższych kroków „w nieskończoność". Procedura jest asymptotycznie zbieżna i umawiamy się, że program kończy pracę gdy kolejna poprawka $g’$ nie różni się zbytnio od poprzednio wyliczonej wartości $g$, czyli $|g-g’|<\varepsilon$ albo gdy wartość funkcji w punkcie $g’$ nie różni się zbytnio od zera ($|f(g’)|<\delta$). Można stosować oba te kryteria:

łącznie — połączone spójnikiem logicznym AND,
które „zadziała" pierwsze (spójnik logiczny OR).

Realizacja programowa

Program będzie się składał z trzech części (funkcji):

blisko(g, gprim) — funkcja o wartościach logicznych sprawdzająca czy $|g-g’|\le\varepsilon$,
lepszy(n, w, g) — funkcja rzeczywista wyliczająca następne, lepsze przybliżenie pierwiastka,
pierwiastek(n, w, g) — funkcja (rzeczywista) wyliczająca pierwiastek stopnia $n$ z $w$ zaczynając od przybliżenia $g$.
i, oczywiście, funkcji main.

Uwaga: Dalszy przykład zakłada $n = 2$.

Na kolejnych rysunkach przedstawione są schematy blokowe poszczególnych funkcji. Funkcja pierwiastek realizowana jest w sposób rekurencyjny, ale można z rekurencji zrezygnować i obliczenia przeprowadzać w pętli (na przykład while).

Kod do wykorzystania znajduje się w bryku na stronach 104 i następnych.

Schemat blokowy funkcji `lepszy()`

flowchart LR A((Start)) --> B["`return 0.5*(g+w/g);`"] --> C((Koniec))

Schemat blokowy funkcji `blisko()`

flowchart LR A((Start)) --> B{"fabs(g-gprim)" <= EPS} --N--> C[return FALSE] B --T--> D[return TRUE] C --> E((Koniec)) D --> E

Schemat blokowy rekurencyjnej wersji funkcji pierwiastek

flowchart LR A((Start)) --> B["gprim=lepszy(w,g)"] --> C{"blisko(g,gprim)"} C --T--> D[return gprim] C --F--> E["return pierwiastek(w,gprim)"] D --> F((Stop)) E --> F

Schemat blokowy funkcji `main()`

flowchart A((Start)) --> B[wprowadź w] --> C[ustal 1. przybliżenie g] C --> D["wynik=pierwiastek(w,g)"] D --> E[wydrukuj wynik] -->F((Koniec))

Zadania do wykonania

Zaprogramować metodę Newtona-Raphsona dla $n=2$. Przetestować jej działanie.
Zmodyfikować schematy blokowe i programy aby metoda mogła działać dla dowolnego $n$ (Uwaga: $n$ nie musi być całkowite!). Przetestować.

Program może być rekurencyjny lub nie.