Metoda bisekcji - więcej przykładów - PYI_R_W14_M28 Miejsca zerowe funkcji

R9U4TZCFMH62S

Podsumowanie

Ważne!

Metodę bisekcji możemy stosować dla dowolnej funkcji, o ile jest ona ciągła w badanym przedziale $< a, b >$ .

Przykład 1

Oto wykres przykładowej funkcji, której miejsce zerowe z przedziału $< - 2.5, 7 >$ można wyznaczyć za pomocą metody bisekcji:

RpmMnXH6a50jQ

Grafika przedstawia układ współrzędnych kartezjańskich, oś x przyjmuje krok 0,5, natomiast oś y przyjmuje krok o 5. Poprowadzono przez układ linię prostą przechodzącą przez punkty 0 2,5 oraz 1,5 0. — Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Zapoznajmy się z programem, który obliczy miejsce zerowe funkcji $f (x) = 1.7 x - 2.45$ metodą bisekcji w przedziale $< - 2, 3 >$ .

def f(x):
    return  (1.7 * x) - 2.45

def wyznaczenie_miejsca_zerowego(a, b, delta, epsilon):
    if f(a) * f(b) < 0:
        while abs(a - b) > delta:
            x = (a + b) / 2
            if abs(f(x)) <= epsilon:
                return x
            else:
                if f(a) * f(x) < 0:
                    b = x
                else:
                    a = x
        else:
            return x
    else:
        return None

        
# przykład wykonania
print(wyznaczenie_miejsca_zerowego(-2,3,0.000000001, 0.000000001))

Wykonanie przedstawionego kodu z podanymi argumentami da następujący wynik:

1.4411764703691006

Przykład 2

Wyznaczmy miejsce zerowe wielomianu funkcji $f (x) = 2 x^{3} + 2 x - 5$ w przedziale $< - 10, 10 >$ :

def f(x):
    return (2 * x ** 3) + (2 * x) - 5

def wyznaczenie_miejsca_zerowego(a, b, delta, epsilon):
    if f(a) * f(b) < 0:
        while abs(a - b) > delta:
            x = (a + b) / 2
            if abs(f(x)) <= epsilon:
                return x
            else:
                if f(a) * f(x) < 0:
                    b = x
                else:
                    a = x
        else:
            return x
    else:
        return None
        
# przykład wywołania
print(wyznaczenie_miejsca_zerowego(-10, 10, 0.00001, 0.00001))

Wykonanie przedstawionego kodu z podanymi argumentami da następujący wynik:

1.1147403717041016

Możemy sprawdzić poprawność wyniku, analizując przebieg badanej funkcji:

RhBERwmQQfhZt

Grafika przedstawia układ współrzędnych kartezjańskich, oś x przyjmuje krok 0,05, natomiast oś y przyjmuje krok o 0,1. Poprowadzono przez układ linię prostą przechodzącą przez punkt 1,11 0. — Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Zmodyfikujmy wcześniejszy kod w taki sposób, aby sprawdzić, jakie wyniki otrzymamy dla coraz mniejszej wartości przybliżenia (czyli dla coraz większej precyzji wyznaczenia miejsca zerowego). W celu wyświetlenia wyniku, zastosujemy konwencję f‑string:

Linia 1. def f otwórz nawias okrągły x zamknij nawias okrągły dwukropek. Linia 2. return otwórz nawias okrągły 2 asterysk x asterysk asterysk 3 zamknij nawias okrągły plus otwórz nawias okrągły 2 asterysk x zamknij nawias okrągły minus 5. Linia 4. def wyznaczenie podkreślnik miejsca podkreślnik zerowego podkreślnik print otwórz nawias okrągły a przecinek b przecinek delta przecinek epsilon zamknij nawias okrągły dwukropek. Linia 5. if f otwórz nawias okrągły a zamknij nawias okrągły asterysk f otwórz nawias okrągły b zamknij nawias okrągły otwórz nawias ostrokątny 0 dwukropek. Linia 6. while abs otwórz nawias okrągły a minus b zamknij nawias okrągły zamknij nawias ostrokątny delta dwukropek. Linia 7. x znak równości otwórz nawias okrągły a plus b zamknij nawias okrągły prawy ukośnik 2. Linia 8. if abs otwórz nawias okrągły f otwórz nawias okrągły x zamknij nawias okrągły zamknij nawias okrągły otwórz nawias ostrokątny znak równości epsilon dwukropek. Linia 9. return f cudzysłów Znaleziono wartość x znak równości otwórz nawias klamrowy x dwukropek kropka 15f zamknij nawias klamrowy cudzysłów. Linia 10. else dwukropek. Linia 11. if f otwórz nawias okrągły a zamknij nawias okrągły asterysk f otwórz nawias okrągły x zamknij nawias okrągły otwórz nawias ostrokątny 0 dwukropek. Linia 12. b znak równości x. Linia 13. else dwukropek. Linia 14. a znak równości x. Linia 15. else dwukropek. Linia 16. return f cudzysłów Ostatnia wartość x znak równości otwórz nawias klamrowy x dwukropek kropka 15f zamknij nawias klamrowy cudzysłów. Linia 17. else dwukropek. Linia 18. return None. Linia 20. kratka przykład wykonania. Linia 21. print otwórz nawias okrągły wyznaczenie podkreślnik miejsca podkreślnik zerowego podkreślnik print otwórz nawias okrągły minus 10 przecinek 10 przecinek 0 kropka 00001 przecinek 0 kropka 00001 zamknij nawias okrągły zamknij nawias okrągły. Linia 22. print otwórz nawias okrągły wyznaczenie podkreślnik miejsca podkreślnik zerowego podkreślnik print otwórz nawias okrągły minus 10 przecinek 10 przecinek 0 kropka 0000000001 przecinek 0 kropka 0000000001 zamknij nawias okrągły zamknij nawias okrągły. Linia 23. print otwórz nawias okrągły wyznaczenie podkreślnik miejsca podkreślnik zerowego podkreślnik print otwórz nawias okrągły minus 10 przecinek 10 przecinek 0 kropka 00000000000001 przecinek 0 kropka 00000000000001 zamknij nawias okrągły zamknij nawias okrągły.

def f(x):
    return (2 * x ** 3) + (2 * x) - 5

def wyznaczenie_miejsca_zerowego_print(a, b, delta, epsilon):
    if f(a) * f(b) < 0:
        while abs(a - b) > delta:
            x = (a + b) / 2
            if abs(f(x)) <= epsilon:
                return f"Znaleziono wartość x = {x:.15f}"
            else:
                if f(a) * f(x) < 0:
                    b = x
                else:
                    a = x
        else:
            return f"Ostatnia wartość x = {x:.15f}"
    else:
        return None

# przykład wykonania
print(wyznaczenie_miejsca_zerowego_print(-10, 10, 0.00001, 0.00001))
print(wyznaczenie_miejsca_zerowego_print(-10, 10, 0.0000000001, 0.0000000001))
print(wyznaczenie_miejsca_zerowego_print(-10, 10, 0.00000000000001, 0.00000000000001))

Przedstawiony kod po wykonaniu zwróci następujący komunikat:

Ostatnia wartość x = 1.114740371704102
Ostatnia wartość x = 1.114747109750169
Znaleziono wartość x = 1.114747109704517

Ważne!

Ograniczeniem przykładowego programu jest to, że funkcja f(x) została zdefiniowana statycznie. Nie możemy wykorzystywać zapisanego kodu w celu wyznaczania miejsc zerowych innych funkcji. Spróbujmy to zmienić. Użyjemy w tym celu funkcji eval(), która służy obliczaniu wartości wyrażenia podanego jej jako parametr tekstowy. Jeżeli w tym wyrażeniu znajdą się nazwy zmiennych, to funkcja eval() wykorzysta do wykonania podanego jej wyrażenia zapisane w nim zmienne, bez potrzeby przekazywania ich do funkcji.

Przykład 3

Napiszmy kod funkcji pobierającej jako argument inną funkcję (taką, której miejsce zerowe chcemy znaleźć).

Linia 1. def wyznaczenie podkreślnik miejsca podkreślnik zerowego podkreślnik fun otwórz nawias okrągły fun przecinek a przecinek b przecinek delta przecinek epsilon zamknij nawias okrągły dwukropek. Linia 2. cudzysłów cudzysłów cudzysłów fun należy podać z podkreślnik x podkreślnik jako parametrem przecinek będzie zamieniane wewnątrz funkcji cudzysłów cudzysłów cudzysłów. Linia 4. kratka tworzymy dwie wersje ciągów dla eval aby móc liczyć dla dwóch argumentów dwukropek a i x. Linia 5. fun podkreślnik x znak równości fun kropka replace otwórz nawias okrągły cudzysłów podkreślnik x podkreślnik cudzysłów przecinek cudzysłów x cudzysłów zamknij nawias okrągły. Linia 6. fun podkreślnik a znak równości fun kropka replace otwórz nawias okrągły cudzysłów podkreślnik x podkreślnik cudzysłów przecinek cudzysłów a cudzysłów zamknij nawias okrągły. Linia 7. fun podkreślnik b znak równości fun kropka replace otwórz nawias okrągły cudzysłów podkreślnik x podkreślnik cudzysłów przecinek cudzysłów b cudzysłów zamknij nawias okrągły. Linia 9. if eval otwórz nawias okrągły fun podkreślnik a zamknij nawias okrągły asterysk eval otwórz nawias okrągły fun podkreślnik b zamknij nawias okrągły otwórz nawias ostrokątny 0 dwukropek. Linia 10. while abs otwórz nawias okrągły a minus b zamknij nawias okrągły zamknij nawias ostrokątny delta dwukropek. Linia 11. x znak równości otwórz nawias okrągły a plus b zamknij nawias okrągły prawy ukośnik 2. Linia 12. if abs otwórz nawias okrągły eval otwórz nawias okrągły fun podkreślnik x zamknij nawias okrągły zamknij nawias okrągły otwórz nawias ostrokątny znak równości epsilon dwukropek. Linia 13. return x. Linia 14. else dwukropek. Linia 15. if eval otwórz nawias okrągły fun podkreślnik a zamknij nawias okrągły asterysk eval otwórz nawias okrągły fun podkreślnik x zamknij nawias okrągły otwórz nawias ostrokątny 0 dwukropek. Linia 16. b znak równości x. Linia 17. else dwukropek. Linia 18. a znak równości x. Linia 19. else dwukropek. Linia 20. return x. Linia 21. else dwukropek. Linia 22. return None. Linia 24. kratka przykładowe wykonanie funkcji. Linia 25. print otwórz nawias okrągły wyznaczenie podkreślnik miejsca podkreślnik zerowego podkreślnik fun otwórz nawias okrągły cudzysłów otwórz nawias okrągły 2 asterysk podkreślnik x podkreślnik asterysk asterysk 3 zamknij nawias okrągły plus otwórz nawias okrągły 2 asterysk podkreślnik x podkreślnik zamknij nawias okrągły minus 5 cudzysłów przecinek minus 10 przecinek 10 przecinek 0 kropka 00001 przecinek 0 kropka 00001 zamknij nawias okrągły zamknij nawias okrągły. Linia 26. print otwórz nawias okrągły wyznaczenie podkreślnik miejsca podkreślnik zerowego podkreślnik fun otwórz nawias okrągły cudzysłów otwórz nawias okrągły 3 asterysk podkreślnik x podkreślnik asterysk asterysk 3 zamknij nawias okrągły minus otwórz nawias okrągły 1 kropka 4 asterysk podkreślnik x podkreślnik zamknij nawias okrągły plus 3 kropka 1 cudzysłów przecinek minus 10 przecinek 10 przecinek 0 kropka 00001 przecinek 0 kropka 00001 zamknij nawias okrągły zamknij nawias okrągły.

def wyznaczenie_miejsca_zerowego_fun(fun, a, b, delta, epsilon):
    """fun należy podać z _x_ jako parametrem, będzie zamieniane wewnątrz funkcji"""

    # tworzymy dwie wersje ciągów dla eval aby móc liczyć dla dwóch argumentów: a i x
    fun_x = fun.replace("_x_", "x")
    fun_a = fun.replace("_x_", "a")
    fun_b = fun.replace("_x_", "b")

    if eval(fun_a) * eval(fun_b) < 0:
        while abs(a - b) > delta:
            x = (a + b) / 2
            if abs(eval(fun_x)) <= epsilon:
                return x
            else:
                if eval(fun_a) * eval(fun_x) < 0:
                    b = x
                else:
                    a = x
        else:
            return x
    else:
        return None

# przykładowe wykonanie funkcji
print(wyznaczenie_miejsca_zerowego_fun("(2*_x_**3) + (2*_x_) - 5", -10, 10, 0.00001, 0.00001))
print(wyznaczenie_miejsca_zerowego_fun("(3*_x_**3) - (1.4*_x_) + 3.1", -10, 10, 0.00001, 0.00001))

Jako wynik działania przedstawionego kodu otrzymamy:

1.1147403717041016
-1.1638355255126953

Przykład 4

Napiszmy program, który wyznaczy miejsce zerowe badanej funkcji z wykorzystaniem zaprezentowanego kodu oraz przedstawi rozwiązanie w postaci graficznej.

Linia 1. def stworz podkreślnik wykres podkreślnik fun otwórz nawias okrągły fun przecinek x podkreślnik min przecinek x podkreślnik max zamknij nawias okrągły dwukropek. Linia 2. import matplotlib kropka pyplot as plt. Linia 4. fun podkreślnik x znak równości fun kropka replace otwórz nawias okrągły cudzysłów podkreślnik x podkreślnik cudzysłów przecinek cudzysłów x cudzysłów zamknij nawias okrągły. Linia 5. kratka tworzymy listę x. Linia 6. ile podkreślnik punktow znak równości abs otwórz nawias okrągły x podkreślnik min zamknij nawias okrągły plus abs otwórz nawias okrągły x podkreślnik max zamknij nawias okrągły. Linia 7. X znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 8. for punkt in range otwórz nawias okrągły x podkreślnik min przecinek x podkreślnik min plus ile podkreślnik punktow zamknij nawias okrągły dwukropek. Linia 9. X kropka append otwórz nawias okrągły punkt zamknij nawias okrągły. Linia 10. kratka tworzymy wartości funkcji y. Linia 11. Y znak równości otwórz nawias kwadratowy eval otwórz nawias okrągły fun podkreślnik x zamknij nawias okrągły for x in X zamknij nawias kwadratowy. Linia 12. kratka obliczamy punkt zerowy. Linia 13. z znak równości wyznaczenie podkreślnik miejsca podkreślnik zerowego podkreślnik fun otwórz nawias okrągły fun przecinek x podkreślnik min przecinek x podkreślnik max przecinek 0 kropka 0001 przecinek 0 kropka 0001 zamknij nawias okrągły. Linia 14. plt kropka plot otwórz nawias okrągły X przecinek Y zamknij nawias okrągły. Linia 15. kratka dodajemy do wykresu wartość x określająca miejsce zerowe. Linia 16. kratka parametr apostrof r plus apostrof oznacza red otwórz nawias okrągły czerowny zamknij nawias okrągły. Linia 17. plt kropka plot otwórz nawias okrągły z przecinek 0 przecinek apostrof r plus apostrof zamknij nawias okrągły. Linia 18. plt kropka grid otwórz nawias okrągły True zamknij nawias okrągły. Linia 19. plt kropka show otwórz nawias okrągły zamknij nawias okrągły. Linia 21. kratka przykład wywołania. Linia 22. stworz podkreślnik wykres podkreślnik fun otwórz nawias okrągły cudzysłów otwórz nawias okrągły 2 asterysk podkreślnik x podkreślnik asterysk asterysk 3 zamknij nawias okrągły plus otwórz nawias okrągły 2 asterysk podkreślnik x podkreślnik zamknij nawias okrągły minus 5 cudzysłów przecinek minus 15 przecinek 15 zamknij nawias okrągły.

def stworz_wykres_fun(fun, x_min, x_max):
    import matplotlib.pyplot as plt

    fun_x =  fun.replace("_x_", "x")
    # tworzymy listę x
    ile_punktow = abs(x_min) + abs(x_max)
    X = []
    for punkt in range(x_min, x_min+ile_punktow):
        X.append( punkt )
    # tworzymy wartości funkcji y
    Y = [ eval(fun_x) for x in X ]
    # obliczamy punkt zerowy
    z = wyznaczenie_miejsca_zerowego_fun(fun, x_min, x_max, 0.0001, 0.0001)
    plt.plot(X,Y)
    # dodajemy do wykresu wartość x określająca miejsce zerowe
    # parametr 'r+' oznacza red (czerowny)
    plt.plot(z,0,'r+')
    plt.grid(True)
    plt.show()

# przykład wywołania
stworz_wykres_fun("(2*_x_**3) + (2*_x_) - 5", -15, 15)

Możemy w prosty sposób zwizualizować działanie programu – w podanym przykładzie miejsce zerowe oznaczone jest czerwonym znakiem $+$ :

R1Yd5mkaURKMp

Grafika przedstawia układ współrzędnych kartezjańskich, oś x przyjmuje krok 5, natomiast oś y przyjmuje krok o 2000. W układzie narysowano linię zakrzywioną w kształcie spłaszczonej litery es. Krzywa zaczyna się od lewego dolnego rogu a kończy w prawym górnym. — Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Już wiesz

Podsumujmy najważniejsze informacje:

Miejsca zerowe funkcji ciągłych można wyznaczać metodą bisekcji.
Moduł matplotlib można zastosować do przedstawiania wykresów funkcji.
Funkcja eval() umożliwia obliczenie wartości wyrażeń zapisanych w postaci tekstowej.

Słownik

eval()

wbudowana funkcja języka Python, która może służyć do dynamicznego wyliczania wartości wyrażenia; parsuje ona podane jej wyrażenie do kodu w języku Python i zwraca rezultat wykonania tego kodu

f‑string

sposób zapisywania zmiennych w łańcuchu znaków przeznaczonym do wyświetlenia za pomocą funkcji print(), dostępny począwszy od wersji 3.6 języka Python; polecenie wykorzystujące mechanizm f‑string ma postać: f"Napis, a w nim {zmienna} do wypisania"; dokładnie opisany w dokumencie PEP 498 – Literal String Interpolation

funkcja jako parametr

w języku Python istnieje możliwość przekazywania funkcji jako parametru innej funkcji; funkcja może też być zwracana po użyciu słowa kluczowego return

Implementacja algorytmu

Metoda stycznych

Podsumowanie

Słownik