Miejsca Zerowe Funkcji - Metoda Newtona

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

Funkcja f(x) jest określona.
Funkcja f(x) jest ciągła.
Funkcja f(x) na krańcach przedziału [a,b] przyjmuje różne znaki.
W przedziale [a,b] pierwsza pochodna f '(x) jest różna od zera.

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 x_i-1 i x_i-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 x_i-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 x_i-1 z osią OX. Do wyznaczenia kolejnego przybliżenia pierwiastka x_i 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.

obrazek

Zasada metody Newtona jest następująca:

Obliczenia rozpoczynamy od punktu x_o leżącego dostatecznie blisko poszukiwanego pierwiastka funkcji. W przedziale pomiędzy punktem x_o a docelowym pierwiastkiem funkcja musi posiadać niezerową pierwszą pochodną. Pożądane jest również, aby w punkcie x_o 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 x_o 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 x_owykorzystują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:

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

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

Kolejne przybliżenie otrzymamy podstawiając we wzorze za x0 obliczone 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,236068895² = 5,000004103. Przybliżenie jest zatem bardzo dobre!

Na początek: podrozdziału strony

Specyfikacja problemu

Dane wejściowe

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

Dane wyjściowe

x_o

–

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
x₁	– poprzednie przybliżenie pierwiastka funkcji f(x). x₁ ∈ R
f_o	– wartość funkcji w punkcie x_o. f_o ∈ R
f₁	– wartości pierwszej pochodnej funkcji punkcie xo. f₁ ∈ R
ε_o	– określa dokładność porównania z zerem.	ε_o = 0.0000000001
ε_x	– określa dokładność wyznaczania pierwiastka x_o.	ε_x = 0.0000000001

Lista kroków

	K01:	Czytaj x_o
	K02:	x₁ ← x_o - 1; f_o ← f(x_o); i ← 64
	K03:	Dopóki (i > 0) ∧ (\| x₁ - x_o \| > ε_x) ∧ (\| f_o \| > εo): wykonuj kroki K04...K07
	K04:	f₁ ← f_p(x_o)
	K05:	Jeśli \| f₁ \| < ε_o, to pisz "Zły punkt startowy" i zakończ
	K06:
	K07:	i ← i - 1
	K08:	Jeśli i = 0, to pisz "Przekroczony limit obiegów" i zakończ
	K09:	Pisz x_oi zakończ

Schemat blokowy

obrazek

Algorytm wyznaczania pierwiastka funkcji metodą Newtona rozpoczyna się od odczytu punktu startowego x_o. W następnym kroku ustalamy wartość punktu x₁ - będzie on przechowywał poprzednie przybliżenie pierwiastka. Jednakże na początku "poprzednie" przybliżenie jeszcze nie zostało policzone, zatem zmiennej x₁ nadajemy taką wartość, aby wykonała się pętla wyliczająca pierwiastek funkcji. Dodatkowo do zmiennej f_o wpisujemy wartość funkcji w punkcie x_o 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:

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ę.
Kolejne dwa przybliżenia różnią się o mniej niż ε_x. Kończymy algorytm wypisując wyznaczone w poprzednim obiegi x_o.
Jeśli wyznaczona w poprzednim obiegu wartość funkcji w punkcie x_o jest równa zero z dokładnością do ε_o. Kończymy algorytm wypisując x_o.

Jeśli nie zajdzie żadna z opisanych powyżej trzech sytuacji, Wyznaczamy wartość pierwszej pochodnej w punkcie x_o i umieszczamy wynik w zmiennej f₁. 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 f₁ występuje w mianowniku ułamka. Sytuacja taka może pojawić się przy źle dobranym punkcie startowym x_o.

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

Na początek: podrozdziału strony

Programy wyznaczają miejsce zerowe funkcji:

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

C++

// 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;
}

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.

Basic

' 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>

Wynik:

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

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

Na początek: podrozdziału strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Metoda Newtona

Algorytm

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze i funkcje

Lista kroków

Schemat blokowy

Programy

Obliczanie pierwiastka funkcji metodą Newtona