Programowanie i algorytmy

KONKURS FRAKTAL

fraktal

VI edycja konkursu programistycznego

FRAKTAL

19-20 listopad 2016

czytaj więcej

Znajdowanie miejsca zerowego metodą połowienia przedziałów

powrót

Omawiany algorytm wyznacza miejsce zerowe z dokładnością do pewnego {tex}\epsilon{/tex} (dokładność tą ustalamy na początku programu) w przedziale obustronnie domkniętym {tex}[a,\ b]{/tex} przy następujących założeniach:

  1. Funkcja jest ciągła (oznacza to, że jej wykres narysujemy nie odrywając ołówka, chodź definicja funkcji ciągłej jest znacznie bardziej złożona)
  2. W przedziale {tex}[a,\ b]{/tex} funkcja ma dokładnie jedno miejsce zerowe.

 Przyjrzyjmy się poniższemu rysunkowi spełniającemu powyższe założenia:

polowienie przedzialów

Dla każdej takiej funkcji będzie zachodził warunek:

{tex}f(a)\cdot f(b)<0{/tex}

ponieważ wartości na krańcach przedziałów będą zawsze przeciwnych znaków (chyba, że miejsce zerowe znajduje się w jednym z krańców).

W pierwszym kroku wyznaczamy środek przedziału i sprawdzamy, czy nie jest on już miejscem zerowym. Jeśli nie to sprawdzamy czy 

{tex}f(a)\cdot f(srodek)<0{/tex}

Jeśli tak, to miejsce zerowe musi znajdować się w przedziale {tex}[a,\ srodek){/tex}, w przeciwnym razie w przedziale {tex}(srodek,\ b]{/tex}. W pierwszej sytuacji wartość {tex}b{/tex} zostanie zastąpiona wartością środka, w drugiej wartość {tex}a{/tex}. W omawianym przykładzie zachodzi sytuacja pierwsza:

metoda połowienia przedziałów

Czynności dzielenia przedziału {tex}[a,\ b]{/tex} powtarzamy do momentu, aż nie będzie spełniony warunek {tex}\epsilon < a-b{/tex}:

metoda połowienia przedziałów

Gdy osiągniemy szukaną dokładność, tzn. {tex}b-a<=\epsilon{/tex}, możemy wypisać miejsce zerowe, które przyjmuje wartość {tex}\frac{b-a}{2}{/tex}.

Przedstawione poniżej rozwiązanie szuka miejsca zerowego dla wielomianu:

{tex}f(x)=x^3-3x^2+2x-6{/tex},

który spełnia podane na początku artykułu założenia. Program wyznacza miejsce zerowe z dokładnością do pięciu miejsc po przecinku. Funkcję

double f(double a, double b, double epsilon)

 

możemy dowolnie zmieniać, tak samo przedział {tex}[a,\ b]{/tex} oraz {tex}\epsilon{/tex} pamiętając o założeniach. 

Rozwiązanie w C++:

#include<iostream>
#include<iomanip>
using namespace std;
 
double f(double x)
{
  //rozpatrujemy wielomian f(x) = x^3 - 3x^2 + 2x - 6 
  return x*(x*(x-3)+2)-6; //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;
 
  while(b-a > epsilon)
  {
    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;
  }
  return (a+b)/2;
}
 
int main()
{
  double a = -10, b = 10, epsilon = 0.00001;
 
  cout<<"Znalezione miejsce zerowe wynosi: ";
  cout<<fixed<<setprecision(5)<<polowienie_przedzialow(a, b, epsilon);
 
  cin.get();
  return 0;
}
 

 

Rozwiązanie rekurencyjne:

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 = (a+b)/2;
 
  if(b-a <= epsilon) return srodek;
 
  if(f(a)*f(srodek)<0) 
    return polowienie_przedzialow(a, srodek, epsilon);
 
  return polowienie_przedzialow(srodek, b, epsilon);
}