Laboratorium 6: Funkcje. Metoda Newtona-Raphsona

1 Postawienie problemu

Załóżmy, że mamy wyznaczyć pierwiastek stopnia n z liczby w, czyli znaleźć taką liczbę x, że:

n x = w (1)

lub inaczej:

n x − w = 0 (2)

Jeżeli oznaczymy f(x) = xn− 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.

PIC
Rysunek 1: 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:

f(g)− 0 -----′- = f′(g) g− g (3)

czyli

f(g) -′---= g− g′ f (g) (4)

i dalej

′ -f(g)- g = g− f′(g) (5)

Jeżeli zauważymy, że f(x) = xn−w oraz, że f′(x) = nxn−1 to kolejne przybliżenie wyliczane będzie ze wzoru:

g′ = g− gn −-w ngn−1 (6)

albo

( ) g′ = ngn-−-gn +-w-= (n-−-1)gn-+-w-= 1 (n − 1)g + -w-- ngn− 1 ngn−1 n gn−1 (7)

Gdy n = 2, wówczas

1( w ) g′ = - g+ -- . 2 g (8)

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′| < ε albo gdy wartość funkcji w punkcie g′ nie różni się zbytnio od zera (|f(g′)| < δ). Można stosować oba te kryteria:

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

2 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′|≤ ε,
  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 rysunkach 2–5 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).

PIC
Rysunek 2: Schemat blokowy funkcji lepszy
PIC
Rysunek 3: Schemat blokowy funkcji blisko (TRUE to 1, a FALSE to 0)
PIC
Rysunek 4: Schemat blokowy rekurencyjnej wersji funkcji pierwiastek
PIC
Rysunek 5: Schemat blokowy funkcji main

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

4 Wersja PDF tego dokumentu…

…pod adresem.

Wersja: 16 z drobnymi modyfikacjami! data ostatniej modyfikacji 2016-03-14 20:58:43 +0100