Wyznaczanie przybliżonej wartości miejsca zerowego funkcji


METODA ołowienia przedziałów
Metoda bisekcji

Opisana w tym rozdziale metoda jest najwolniej zbieżną metodą znajdowania przybliżonych pierwiastków funkcji w zadanym przedziale argumentów . Metodę bisekcji można zastosować, jeśli funkcja jest ciągła i na krańcach przedziału posiada różne znaki. W takim przypadku twierdzenie o wartościach pośrednich mówi nam, iż:
jeśli f(xA) < 0 < f(xB) lub f(xA) > 0 > f(xB), to istnieje taki punkt x0, xA < x0 < xB, że f(x0) = 0
Innymi słowy twierdzenie to gwarantuje nam istnienie przynajmniej jednego pierwiastka w danym przedziale. Metoda bisekcji (połowienia, krojenia na pół) polega na dzieleniu zadanego przedziału argumentów na dwie równe połówki. Dokonujemy tego znajdując punkt środkowy przedziału jako średnią arytmetyczną jego krańców.

Schemat blokowy 




//  Metoda bisekcji      


#include <iostream>
#include <iomanip>
#include <math.h>

using namespace std;

double f(double x)
{
  //rozpatrujemy wielomian f(x) = x^3 -5x^2 + 4x - 1
  return x*(x*(2*x-5)+4)-1; //rozbijam schematem Hornera
}

double polowienie_przedzialow(double a, double b, double epsilon)
{
  if(f(a)==0.0)return a;
  if(f(b)==0.0)return b;

  double srodek;
    int licznik=0;
  while(fabs(b-a) > epsilon)
  {
    licznik++;
    srodek = (a+b)/2;

    if(f(srodek) == 0.0) //jesli miejsce zerowe jest w srodku
      return srodek;

    if(f(a)*f(srodek)<0)
      b = srodek;
    else
      a = srodek;
  }
  cout<<"Licznik = " << licznik <<endl;
  return (a+b)/2;
}

int main()
{
  double a, b, epsilon = 0.00001;
  cout << "Podaj poczatek przedzialu  ";
  cin >> a;
  cout << endl;
  cout << "Podaj koniec przedzialu  ";
  cin>>b;
  cout<<endl;

  cout <<"Znalezione miejsce zerowe wynosi: ";
  cout<<fixed<<setprecision(5)<<polowienie_przedzialow(a, b, epsilon);

  cin.get();
  return 0;
}
Metoda ta, zwana również metodą Newtona-Raphsona lub metodą stycznych, pozwala obliczyć miejsca zerowe funkcji nieliniowych w przedziałach, musi ona jednak spełniać następujące warunki:
  • funkcja f oraz jej pierwsza i druga pochodna są ciągłe w badanym przedziale <a, b>,
  • wewnątrz <a, b> znajduje się dokładnie jeden pierwiastek,
  • f(a)*f(b) < 0, pierwsza i druga pochodna mają stały znak w badanym przedziale <a ,b>. Metoda przebiega następująco: badamy znaki funkcji i drugiej pochodnej na krańcach badanego przedziału <a, b>. Za punkt x(0) wybieramy ten koniec przedziału, w którym funkcja i jej druga pochodna mają równe znaki, a wzór na kolejne punkty wygląda następująco:

    x[i]=x[i−1]−(f(x[i-1]/f'(x[i-1])


    f(xi−1) f'(xi−1) Geometryczną konstrukcję kolejnych przybliżeń pierwiastków obrazuje poniższy wykres (z którego można zresztą powyższe zależności wyznaczyć). Z punktu prowadzimy styczną do krzywej miejsce przecięcia z osią OX tworzy nowy punkt, z którego prowadzimy kolejną styczną, itd...

    Schemat blokowy 

    W schemacie blokowym używamy następujące symbole:

f(..)	funkcja, której pierwiastka poszukujemy w przedziale 
xA	punkty startowy do poszukiwań pierwiastka funkcji f(x)
x0	punkt przecięcia stycznej do wykresu funkcji w punkcie xA z osią x
fA	wartość funkcji f(x) w punkcie xA
dfA	wartość pochodnej funkcji f(x) w punkcie xA
f0	wartość funkcji f(x) w punkcie x0
eps	założona dokładność obliczeń (epsilon) - otoczenie zera
i	licznik obiegów pętli uniemożliwiający zablokowanie się algorytmu
maxi	maksymalna liczba obiegów pętli wewnętrznej


    


//  Metoda stycznych zwanej również metodą Newtona      


#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <iomanip>
#include <iostream>

//*********************************************************
//**  Tutaj definiujemy funkcję wg wzoru algebraicznego  **
//**  Funkcja:                                           **
//**    f(x) = x^3 + x^2 - x - 1                         **
//*********************************************************

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

using namespace std;


main()
{
  const double eps = 0.00001;  // dokladnosc oblioczen
  const int maxi = 64;         // max liczba obiegow pętli

  double xA, x0, fA, dfA, f0;
  int i;



 cout.precision(6);      // 6 cyfr po przecinku
 cout.setf(ios::fixed);  // format stałoprzecinkowy

  cout << "Obliczanie przyblizonego pierwiastka funkcji" << endl
       << "f(x) = x^3 + x^2 - x - 1" << endl
       << "przy pomocy metody stycznych - Newtona" << endl

       << endl << "Podaj punkt startowy : ";
  cin >> xA;
  cout << endl;

// algorytm stycznych

  fA = f(xA);
  for(i = 1; i <= maxi; i++)
  {
    dfA = (f(xA + eps) - fA) / eps;
    x0  = xA - fA / dfA;
    f0  = f(x0);
    if(fabs(f0) < eps)
    {
      cout << "Wyniki" << endl
           << "------" << endl << endl
           << "x0    = " << setw(10) << x0 << endl
           << "f(x0) = " << setw(10) << f0
           << " przy eps = " << setw(10) << eps << endl
           << "Obieg = " << i << endl;
      break;
    };
    fA = f0;
    xA = x0;
    if(i == maxi)
    {
      cout << "Przekroczono liczbe obiegow" << endl
           << "Wynik moze byc niepoprawny." << endl
           << "---------------------------" << endl
           << endl
           << "x0    = " << setw(10) << x0 << endl
           << "f(x0) = " << setw(10) << f0
           << " przy eps = " << setw(10) << eps << endl;
    };
  };

// kończymy program czekając na klawisz...

  cout << endl << "Nacisnij dowolny klawisz...";
  cout.flush();
  
}

    Opis wybranych poleceń:

    Plik nagłówkowy iostream.h zawiera definicje klas oraz metod (funkcji):
cout.width()	steruje odstępami na WY
cout.fill()	zastęuje znaki na WY podanym symbolem
cout.setprecision()	określa liczbę cyfr dziesiętnych
cout.put()	wyświetla po jednym znaku
cout.flush()	opróżnia bufor