README.md

Programming-course-cpp

Jakub Piskorowski on 31/10/2023 wersja: 1.0

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

Przedstawienie działania algorytmu znajdowanie miejsca zerowego metodą połowienia przedziałów

Kod źródłowy: set-precision.cpp
polowienie-przedzialow-iteracyjnie.cpp
polowienie-przedzialow-rekurencyjnie.cpp

📕 Poziom 3

Powrót do Algorytmika

---

Objaśnienie

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

• 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)
• W przedziale [a,b] funkcja ma dokładnie jedno miejsce zerowe.

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

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

f(a) * f(b) < 0

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:

f(a) * f(srodek) < 0

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

Czynności dzielenia przedziału [a, b] powtarzamy do momentu, aż nie będzie spełniony warunek ϵ < a−b.

Gdy osiągniemy szukaną dokładność, tzn. b - a <= ϵ, możemy wypisać miejsce zerowe, które przyjmuje wartość (b-a) / 2.

Przedstawiony algorytm szuka miejsca zerowego dla wielomianu:

f(x) = x^3 - 3x^2 + 2x - 6

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.

Ustawienie dokładności

#include <iostream>     // fixed
#include <iomanip>      // setprecision
using namespace std;

int main(){
	double f =3.14159;

	cout << setprecision(5) << f << '\n';
	cout << setprecision(9) << f << '\n';
	cout << fixed;
	cout << setprecision(5) << f << '\n';
	cout << setprecision(9) << f << '\n';

	system("pause");
	return 0;
}

Kod źródłowy: set-precision.cpp

Wynik działania programu:

3.1416
3.14159
3.14159
3.141590000

---

Algorytm znajdowanie miejsca zerowego

Funkcja f

Rozpatrujemy wielomian f(x) = x^3 - 3x^2 + 2x - 6
Rozbijamy go schematem Hornera i obliczamy jego wartość
Wejście:
x - argument funkcji

Lista kroków:
K1:   zwróć x*(x*(x-3)+2)-6;  

Funkcja połowienia przedziałów rozwiązanie iteracyjne

Wejście:
a = -10 – lewy kraniec przedziału
b = 10 - prawy kraniec przedziału
epsilon = 0.00001 - dokładność wyznaczania miejsca zerowego

Zmienne pomocnicze:
srodek - wyznaczenie srodka, przedziału

Lista kroków:
K1:   jeżeli f(a) = 0.0
      zwróć a
K2:   jeżeli f(b) = 0.0
      zwróć b
K3:   dopóki b-a > epsilon
      wykonuj kroki K4...k6
K4:   srodek ← (a+b)/2
K5:   jeżeli f(srodek) = 0   jeżeli miejsce zerowe jest w środku
      zwróć środek
K6:   jeżeli f(a)*f(srodek) < 0
      b ← środek
      w przeciwnym razie a ← srodek
K7:   zwróć (a+b)/2

Wynik działania programu:

Znalezione miejsce zerowe wynosi: 3.00000

Kod źródłowy: polowienie-przedzialow-iteracyjnie.cpp

---

Funkcja połowienia przedziałów rozwiązanie rekurencyjne

Wejście:
a = -10 – lewy kraniec przedziału
b = 10 - prawy kraniec przedziału
epsilon = 0.00001 - dokładność wyznaczania miejsca zerowego

Zmienne pomocnicze:
srodek - wyznaczenie srodka, przedziału

Lista kroków:
K1:  jeżeli f(a) = 0.0
      zwróć a
K2:   jeżeli f(b) = 0.0
      zwróć b
K3:   srodek ← (a+b)/2
K4:   jeżeli b-a <= epsilon
      zwróć środek
K5:   jeżeli f(a)*f(srodek) < 0
      zwroc PolowieniePrzedzialow(a, srodek, epsilon)
K6:   zwróć PolowieniePrzedzialow(srodek, b, epsilon)

Kod źródłowy: polowienie-przedzialow-rekurencyjnie.cpp