Metoda Newtona


Tematy pokrewne

 

Algorytm

Mamy daną funkcję f(x), jeden punkty startowy xo i przedział <a,b> poszukiwań pierwiastka, do którego należy punkt xo. W przedziale poszukiwań pierwiastka funkcja musi spełniać następujące warunki:

Gdy funkcja f(x) spełnia podane warunki, to w przedziale <a,b> istnieje pierwiastek i możemy go wyszukać metodą Newtona. Jeśli we wzorze metody siecznych:

 

 

punkty xi-1 i xi-2 zaczną się do siebie zbliżać dążąc w granicy do równości, to ułamek tam występujący przejdzie w odwrotność pochodnej funkcji f(x) w punkcie xi-1:

 

 

Sieczna w granicy stanie się styczną. Otrzymany wzór nosi nazwę wzoru Newtona. Pozwala on wyliczyć punkt przecięcia stycznej do wykresu funkcji w punkcie xi-1 z osią OX. Do wyznaczenia kolejnego przybliżenia pierwiastka xi potrzebujemy tylko jednego punktu, który został wyznaczony w poprzednim obiegu - w metodzie siecznych potrzebne były dwa punkty.

Zaletą metody Newtona jest bardzo szybka zbieżność. Wadą - we wzorze występuje pochodna, której obliczenie może być trudne dla niektórych funkcji. Jednakże metodę Newtona najczęściej stosuje się do wielomianów, których pochodne są bardzo proste i liczy się je algorytmicznie.

Zasada metody Newtona jest następująca:

 

Obliczenia rozpoczynamy od punktu xo leżącego dostatecznie blisko poszukiwanego pierwiastka funkcji. W przedziale pomiędzy punktem xo a docelowym pierwiastkiem funkcja musi posiadać niezerową pierwszą pochodną. Pożądane jest również, aby w punkcie xo druga pochodna miała ten sam znak, co funkcja f(x). W przeciwnym razie metoda Newtona zamiast zbliżać się do punktu pierwiastka ucieknie od niego.

Obliczamy nowy punkt xo zgodnie ze wzorem i sprawdzamy, czy wartość funkcji w tym punkcie jest dostatecznie bliska 0. Jeśli tak, kończymy. W przeciwnym razie wyznaczony kolejny punkt xo wykorzystując ostatnio wyliczony. Działania te prowadzimy dotąd, aż zbliżymy się dostatecznie do pierwiastka funkcji - różnica pomiędzy dwoma kolejno wyznaczonymi pierwiastkami będzie dostatecznie mała.

Ponieważ metoda Newtona może być rozbieżna przy źle wybranym punkcie startowym, będziemy zliczali obiegi - jeśli rozwiązanie nie pojawi się po wykonaniu zadanej ich liczby, przerwiemy obliczenia.


 

Przykład:

Znanym przykładem zastosowania metody Newtona jest rekurencyjne wyliczanie pierwiastka kwadratowego z danej liczby p. Wartość pierwiastka jest miejscem zerowym funkcji:

 

f(x) = x2 - p

 

Pochodna tej funkcji jest bardzo prosta i wyraża się wzorem:

 

f '(x) = 2x

 

Przyjmijmy za punkt startowy pewną liczbę x0. Wtedy pierwsze przybliżenie otrzymamy wg wzoru:

 

 

Kolejne przybliżenie otrzymamy podstawiając we wzorze za x0 otrzymane x1. Wg tej metody postępujemy dotąd, aż różnica dwóch ostatnich przybliżeń będzie mniejsza od pożądanej dokładności wyznaczenia pierwiastka. Dla przykładu wyznaczmy tą metodą pierwiastek z liczby 5 z dokładnością do 0,01. Za punkt początkowy przyjmijmy 5.

 

 

Sprawdźmy: 2,2360688952  =  5,000004103. Przybliżenie jest zatem bardzo dobre!

 

Dane wejściowe

f(x) - funkcja, której pierwiastek liczymy. Musi być ciągła i określona w przedziale poszukiwań pierwiastka.
fp(x) - pierwsza pochodna funkcji f(x). W przedziale poszukiwań pierwiastka nie może przyjmować wartości 0.
xo - punkt startowy, od którego rozpoczynamy obliczenia pierwiastka funkcji f(x). xoR

Dane wyjściowe

xo - pierwiastek funkcji f(x)

Zmienne pomocnicze i funkcje

i - licznik obiegów pętli. Obiegi są zliczane wstecz od wartości i = 64.  i ∈ C
x1 - poprzednie przybliżenie pierwiastka funkcji f(x).   x1R
fo - wartość funkcji w punkcie xo.   foR
f1 - wartości pierwszej pochodnej funkcji punkcie xo.   f1R
εo - określa dokładność porównania z zerem.   εo = 0.0000000001
εx - określa dokładność wyznaczania pierwiastka xo.     εx = 0.0000000001

 

Lista kroków

  K01: Czytaj xo
  K02: x1xo - 1;    fof(xo);    i ← 64
  K03: Dopóki (i > 0) ∧ (| x1 - xo | > εx) ∧ (| fo | > εo):  wykonuj K04...K07
K04:      f1fp(xo)
K05:     Jeśli | f1 | < εo, to pisz "Zły punkt startowy" i zakończ
K06:
    x1xo  xoxo -  fo ;    fof(xo)
f1
K07:     i ← i - 1
  K08: Jeśli i = 0, to pisz "Przekroczony limit obiegów" i zakończ
  K09: Pisz xo i zakończ

 

Schemat blokowy

Algorytm wyznaczania pierwiastka funkcji metodą Newtona rozpoczyna się od odczytu punktu startowego xo. W następnym kroku ustalamy wartość punktu x1 - będzie on przechowywał poprzednie przybliżenie pierwiastka. Jednakże na początku "poprzednie" przybliżenie jeszcze nie zostało policzone, zatem zmiennej x1 nadajemy taką wartość, aby wykonała się pętla wyliczająca pierwiastek funkcji. Dodatkowo do zmiennej fo wpisujemy wartość funkcji w punkcie xo oraz ustalamy maksymalną liczbę obiegów pętli na 64 w zmiennej i.

Rozpoczynamy pętlę wyliczającą kolejne przybliżenia pierwiastka. Pętla jest przerywana w następujących przypadkach:

 

1. Licznik i osiągnął 0. Oznacza to, iż algorytm nie wyznaczył pierwiastka w zadanej liczbie obiegów. Ponieważ metoda Newtona jest bardzo szybko zbieżna, to sytuacja taka może wystąpić tylko wtedy, gdy pomiędzy punktem startowym, a pierwiastkiem pierwsza pochodna zeruje się (styczna staje się równoległa do osi OX). W tej sytuacji algorytm wypisuje odpowiedni komunikat i kończy pracę.

2. Kolejne dwa przybliżenia różnią się o mniej niż εx. Kończymy algorytm wypisując wyznaczone w poprzednim obiegi xo.

3. Jeśli wyznaczona w poprzednim obiegu wartość funkcji w punkcie xo jest równa zero z dokładnością do εo. Kończymy algorytm wypisując xo.

 

Jeśli nie zajdzie żadna z opisanych powyżej trzech sytuacji, Wyznaczamy wartość pierwszej pochodnej w punkcie xo i umieszczamy wynik w zmiennej f1. Następnie sprawdzamy, czy wyliczona pochodna jest równa zero. Jeśli tak, musimy zakończyć algorytm z odpowiednim komunikatem, ponieważ we wzorze na przybliżony pierwiastek f1 występuje w mianowniku ułamka. Sytuacja taka może pojawić się przy źle dobranym punkcie startowym xo.

Przesuwamy xo do x1 zapamiętując w ten sposób poprzednio wyznaczony pierwiastek przybliżony funkcji. Obliczamy nowe przybliżenie pierwiastka i umieszczamy wynik w zmiennej xo. Wyznaczamy wartość funkcji w punkcie xo i umieszczamy wynik w zmiennej fo. Na końcu pętli zmniejszamy licznik i wykonujemy kolejny obieg.


 

Programy

Programy wyznaczają miejsce zerowe funkcji:

 

f(x) = x3(x + sin(x2 - 1) - 1) - 1

 

Pierwiastków należy poszukiwać w przedziałach <-1,0> i <1,2>.

 

Efekt uruchomienia programu
Obliczanie pierwiastka funkcji - metoda Newtona
f(x) = x^3*(x+sin(x^2-1)-1)-1
-----------------------------------------------
(C)2006 mgr Jerzy Wałaszek      I LO w Tarnowie

Podaj punkt startowy x0 = 1

-----------------------------------------------

WYNIK:

x0 =      1,18983299

-----------------------------------------------
Koniec. Naciśnij klawisz Enter...

 

Free Pascal
// Program znajduje miejsce zerowe funkcji f(x)
// za pomocą algorytmu Newtona
//---------------------------------------------
// (C)2006 mgr J.Wałaszek       I LO w Tarnowie

program mzf1;

uses math;

const
  EPS0 = 0.0000000001; // dokładność porównania z zerem
  EPSX = 0.0000000001; // dokładność wyznaczenia pierwiastka

// Funkcja, której miejsce zerowe obliczamy
// f(x) = x^3*(x+sin(x^2-1)-1)-1
// <-1,0> i <1,2>
//-----------------------------------------

function f(x : real) : double;
begin
  Result := x * x * x * (x + sin(x * x - 1) - 1) - 1;
end;

// Oblicza pochodną funkcji f(x)
// f'(x) =2x^4*COS(x^2 - 1) + 3x^2*SIN(x^2 - 1) + 4x^3 - 3x^2
//-----------------------------------------------------------

function fp(x : real) : double;
begin
  Result := x * x * (2 * x * x * cos(x * x - 1) + 3 * sin(x * x - 1) + 4 * x - 3)
end;

//-----------------------------------------------------
// Program główny
//-----------------------------------------------------

var
  x0,x1,f0,f1 : double;
  i           : integer;

begin
  writeln('Obliczanie pierwiastka funkcji - metoda Newtona');
  writeln('f(x) = x^3*(x+sin(x^2-1)-1)-1');
  writeln('-----------------------------------------------');
  writeln('(C)2006 mgr Jerzy Walaszek      I LO w Tarnowie');
  writeln;
  write('Podaj punkt startowy x0 = '); readln(x0);
  writeln;
  writeln('-----------------------------------------------');
  writeln('WYNIK:');
  writeln;
  x1 := x0 - 1; f0 := f(x0); i := 64;
  while (i > 0) and (abs(x1 - x0) > EPSX) and (abs(f0) > EPS0) do
  begin
    f1 := fp(x0);
    if abs(f1) < EPS0 then
    begin
      writeln('Zly punkt startowy');
      i := 0;
      break;
    end;
    x1 := x0;
    x0 := x0 - f0 / f1;
    f0 := f(x0);
    dec(i);
    if i = 0 then writeln('Przekroczony limit obiegow');
  end;
  if i > 0 then writeln('x0 = ',x0:15:8);
  writeln;
  writeln('-----------------------------------------------');
  writeln('Koniec. Nacisnij klawisz Enter...');
  readln;
end.
Code::Blocks
// Program znajduje miejsce zerowe funkcji f(x)
// za pomocą algorytmu Newtona
//---------------------------------------------
// (C)2006 mgr J.Wałaszek       I LO w Tarnowie

#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdlib>

using namespace std;

const double EPS0 = 0.0000000001; // dokładność porównania z zerem
const double EPSX = 0.0000000001; // dokładność wyznaczenia pierwiastka

// Funkcja, której miejsce zerowe obliczamy
// f(x) = x^3*(x+sin(x^2-1)-1)-1
// <-1,0> i <1,2>
//-----------------------------------------

double f(double x)
{
  return x * x * x * (x + sin(x * x - 1) - 1) - 1;
}

// Oblicza pochodną funkcji f(x)
// f'(x) =2x^4*COS(x^2 - 1) + 3x^2*SIN(x^2 - 1) + 4x^3 - 3x^2
//-----------------------------------------------------------

double fp(double x)
{
  return x * x * (2 * x * x * cos(x * x - 1) + 3 * sin(x * x - 1) + 4 * x - 3);
}

//-----------------------------------------------------
// Program główny
//-----------------------------------------------------

int main()
{

  double x0,x1,f0,f1;
  int    i;

  cout << setprecision(8)     // 8 cyfr po przecinku
       << fixed;              // format stałoprzecinkowy

  cout << "Obliczanie pierwiastka funkcji - metoda Newtona\n"
          "f(x) = x^3*(x+sin(x^2-1)-1)-1\n"
          "-----------------------------------------------\n"
          "(C)2006 mgr Jerzy Walaszek      I LO w Tarnowie\n\n"
          "Podaj punkt startowy x0 = ";
  cin >> x0;
  cout << "\n-----------------------------------------------\n\n"
          "WYNIK:\n\n";
  x1 = x0 - 1; f0 = f(x0); i = 64;
  while (i && (fabs(x1 - x0) > EPSX) && (fabs(f0) > EPS0))
  {
    f1 = fp(x0);
    if(fabs(f1) < EPS0)
    {
      cout << "Zly punkt startowy\n";
      i = 0;
      break;
    }
    x1 = x0;
    x0 = x0 - f0 / f1;
    f0 = f(x0);
    if(!(--i)) cout << "Przekroczony limit obiegow\n";
  }
  if(i) cout << "x0 = " << setw(15) << x0 << endl;
  cout << "\n-------------------------------------------\n\n";
  system("pause");
  return 0;
}
FreeBASIC
' Program znajduje miejsce zerowe funkcji f(x)
' za pomocą algorytmu Newtona
'---------------------------------------------
' (C)2006 mgr J.Wałaszek       I LO w Tarnowie

Declare Function f(x As Double) As Double
Declare Function fp(x As Double) As Double

Const EPS0 As Double = 0.0000000001 ' dokładność porównania z zerem
Const EPSX As Double = 0.0000000001 ' dokładność wyznaczenia pierwiastka

'-----------------------------------------------------
' Program główny
'-----------------------------------------------------

Dim As double x0, x1, f0, f1
Dim i As Integer

print "Obliczanie pierwiastka funkcji - metoda Newtona"
print "f(x) = x^3*(x+sin(x^2-1)-1)-1"
print "-----------------------------------------------"
print "(C)2006 mgr Jerzy Walaszek      I LO w Tarnowie"
Print
Input "Podaj punkt startowy x0 = ", x0
Print
print "-----------------------------------------------"
Print
print "WYNIK:"
Print

x1 = x0 - 1 : f0 = f(x0) : i = 64

While (i > 0) And (Abs(x1 - x0) > EPSX) And (Abs(f0) > EPS0)
   f1 = fp(x0)
   If Abs(f1) < EPS0 Then
      Print "Zly punkt startowy"
      i = 0
      Exit While
   End If
   x1 = x0
   x0 = x0 - f0 / f1
   f0 = f(x0)
   i -= 1
   If i = 0 Then Print "Przekroczony limit obiegow"
Wend

If i > 0 Then Print Using "x0 = ######.########"; x0

Print
print "-----------------------------------------------"
Print
print "Koniec. Nacisnij klawisz Enter..."

Sleep

End

' Funkcja, której miejsce zerowe obliczamy
' f(x) = x^3*(x+sin(x^2-1)-1)-1
' <-1,0> i <1,2>
'-----------------------------------------

Function f(x As Double) As Double
   Return x * x * x * (x + Sin(x * x - 1) - 1) - 1
End Function

' Oblicza pochodną funkcji f(x)
' f'(x) =2x^4*COS(x^2 - 1) + 3x^2*SIN(x^2 - 1) + 4x^3 - 3x^2
'-----------------------------------------------------------

Function fp(x As Double) As Double
   Return x * x * (2 * x * x * Cos(x * x - 1) + 3 * Sin(x * x - 1) + 4 * x - 3)
End Function
JavaScript
<html>
  <head>
  </head>
  <body>
    <form style="BORDER-RIGHT: #ff9933 1px outset; PADDING-RIGHT: 4px;
                 BORDER-TOP: #ff9933 1px outset; PADDING-LEFT: 4px;
                 PADDING-BOTTOM: 1px; BORDER-LEFT: #ff9933 1px outset;
                 PADDING-TOP: 1px; BORDER-BOTTOM: #ff9933 1px outset;
                 BACKGROUND-COLOR: #ffcc66" name="frmbincode">
      <h3 style="TEXT-ALIGN: center">
        Obliczanie pierwiastka funkcji metodą Newtona
      </h3>
      <p style="TEXT-ALIGN: center">
        <i>f(x) = x<sup>3</sup>(x + sin(x<sup>2</sup> - 1) - 1) - 1</i>
      </p>
      <p style="TEXT-ALIGN: center">
        (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
      </p>
      <hr>
      <p style="text-align: center">
        Wpisz do pola edycyjnego punkt startowy
      </p>
      <div align="center">
        <table border="0" id="table144" cellpadding="8"
               style="border-collapse: collapse">
          <tr>
            <td>
              x<sub>0</sub> = <input type="text" name="wsp_x0" size="20"
                                     value="1" style="text-align: right">
            </td>
            <td>
              <input type="button" value="Szukaj pierwiastka" name="B1"
                     onclick="main()">
            </td>
          </tr>
        </table>
      </div>
      <div id="out" align=center>...</div>
    </form>

<script language=javascript>

// Program znajduje miejsce zerowe funkcji f(x)
// za pomocą algorytmu Newtona
//---------------------------------------------
// (C)2006 mgr J.Wałaszek I LO w Tarnowie

var EPS0 = 0.0000000001; // dokładność porównania z zerem
var EPSX = 0.0000000001; // dokładność wyznaczenia pierwiastka

// Funkcja, której miejsce zerowe obliczamy
// f(x) = x^3*(x+sin(x^2-1)-1)-1
// <-1,0> i <1,2>
//-----------------------------------------

function f(x)
{
  return x * x * x * (x + Math.sin(x * x - 1) - 1) - 1;
}

// Oblicza pochodną funkcji f(x)
// f'(x) =2x^4*COS(x^2 - 1) + 3x^2*SIN(x^2 - 1) + 4x^3 - 3x^2
//-----------------------------------------------------------

function fp(x)
{
  return x * x * (2 * x * x * Math.cos(x * x - 1) +
         3 * Math.sin(x * x - 1) + 4 * x - 3);
}

//-----------------------------------------------------
// Program główny
//-----------------------------------------------------

function main()
{

  var x0,x1,f0,f1,i,t;

  x0 = parseFloat(document.frmbincode.wsp_x0.value);
  if(isNaN(x0))
    t = "<font color=red><b>Błędne dane wejściowe</b></font>";
  else
  {
    x1 = x0 - 1; f0 = f(x0); i = 64;
    while (i && (Math.abs(x1 - x0) > EPSX) && (Math.abs(f0) > EPS0))
    {
      f1 = fp(x0);
      if(Math.abs(f1) < EPS0)
      {
        t = "<font color=red><b>Zly punkt startowy</b></font>";
        i = 0;
        break;
      }
      x1 = x0;
      x0 = x0 - f0 / f1;
      f0 = f(x0);
      if(!(--i)) t = "<font color=red><b>Przekroczony limit obiegow</b></font>";
    }
    if(i) t = "x<sub>0</sub> = " + x0;
  }
  document.getElementById("out").innerHTML = t;
}

</script>
    </div>
  </body>
</html>

 

Tutaj możesz przetestować działanie prezentowanego skryptu. Przykładowa funkcja posiada pierwiastki w przedziałach <-1,0> oraz <1,2>.

Obliczanie pierwiastka funkcji metodą Newtona

f(x) = x3(x + sin(x2 - 1) - 1) - 1

(C)2006 mgr Jerzy Wałaszek I LO w Tarnowie


Wpisz do pola edycyjnego punkt startowy

x0 =
...


List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.