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

powrót

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:

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 $$[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)\cdot 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)\cdot 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 $$\epsilon < a-b$$:

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

Przedstawione poniżej rozwiązanie 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. Funkcję

def f(a: float, b: float, epsilon: float) -> float:

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

Rozwiązanie w języku Python:

//algorytm.edu.pl
def f(x: float) -> float:
    #rozpatrujemy wielomian f(x) = x ^ 3 - 3x ^ 2 + 2x - 6
    return x * (x * (x - 3) + 2) - 6 # rozbijam schematem Hornera

def polowienie_przedzialow(a: float, b: float, epsilon: float) -> float:
    if f(a) == 0.0: return a
    if f(b) == 0.0: return b


    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 round((a + b) / 2, 5)

a = -10; b = 10; epsilon = 0.00001

print("Znalezione miejsce zerowe wynosi:", polowienie_przedzialow(a, b, epsilon))

Rozwiązanie rekurencyjne:

def polowienie_przedzialow(a: float, b: float, epsilon: float) -> float:
    if f(a) == 0.0:
        return a
    if f(b) == 0.0:
        return b

    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)