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.

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: $${\displaystyle \frac{f(g)-0}{g-g^{\prime }}}=f^{\prime }(g)$$ czyli $${\displaystyle \frac{f(g)}{f^{\prime }(g)}}=g-g^{\prime }$$ i dalej $$g^{\prime }=g-{\displaystyle \frac{f(g)}{f^{\prime }(g)}}$$

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

Gdy $n=2$, wówczas $$g^{\prime }={\displaystyle \frac{1}{2}}(g+{\displaystyle \frac{w}{g}}).$$

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^{\prime }$ nie różni się zbytnio od poprzednio wyliczonej wartości $g$, czyli $|g-g^{\prime }|<\epsilon$ albo gdy wartość funkcji w punkcie $g^{\prime }$ nie różni się zbytnio od zera ($|f(g^{\prime })|<\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):

1. blisko(g, gprim) — funkcja o wartościach logicznych sprawdzająca czy $|g-g^{\prime }|\le \epsilon$,

2. lepszy(n, w, g) — funkcja rzeczywista wyliczająca następne, lepsze przybliżenie pierwiastka,

3. pierwiastek(n, w, g) — funkcja (rzeczywista) wyliczająca pierwiastek stopnia $n$ z $w$ zaczynając od przybliżenia $g$.

4. 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()

Schemat blokowy funkcji blisko()

Schemat blokowy rekurencyjnej wersji funkcji pierwiastek()

W tym przypadku rekurencja realizuje pętlę: każde wywołanie funkcji rozpoczyna wykonanie jej kodu od początku (z nowymi wartościami zmiennych). Rekurencję można zastąpić zwykłą pętlą…

Schemat blokowy funkcji main()

Zadania do wykonania

1. Zaprogramować metodę Newtona-Raphsona dla $n=2$. Przetestować jej działanie.

2. 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.

Uwaga

Gdy zachodzi wyliczenie potęgi¹ $x^y$ można użyć funkcji pow():

#include <math.h>
...
z = pow(x, y);