Algorytm metody bisekcji z przykładami

Czym jest metoda bisekcji?

Metoda bisekcji to jedna z najbardziej podstawowych technik numerycznych służących do znajdowania pierwiastka równania wielomianowego lub przestępnego. Polega ona na uwzględnieniu przedziału zawierającego pierwiastek w nawiasach, a następnie podzieleniu go na połowy w każdej iteracji, aż pierwiastek znajdzie się w akceptowalnym zakresie tolerancji. Ze względu na ten mechanizm, metoda bisekcji jest również nazywana metodą bracketingu.

Ponieważ jej mechanizm działania przypomina przeszukiwanie binarne, metoda bisekcji jest również znana jako metoda przeszukiwania binarnego, metoda podziału na pół lub metoda dychotomii. Opiera się ona na silnych podstawach teoretycznych: twierdzeniu o wartościach pośrednich, które gwarantuje, że funkcja ciągła zmieniająca znak w pewnym przedziale musi przechodzić przez zero w którymś miejscu tego przedziału.

Mając już podstawową definicję, możemy teraz zbadać, dlaczego znajdowanie pierwiastków równań jest tak ważne i jak metoda bisekcji wpisuje się w ten szerszy obraz.

Znajdowanie pierwiastków równań

W tej dyskusji skupimy się wyłącznie na równaniach z jedną zmienną niezależną. Takie równania mogą być liniowe lub nieliniowe. Równania liniowe opisują wykres linii prostej, podczas gdy równania nieliniowe opisują krzywe i bardziej złożone kształty.

Pierwiastek równania to wartość zmiennej niezależnej, która spełnia równanie. Na przykład pierwiastek równania f(x) = 4 – x² = 0 to 2, ponieważ f(2) = 4 – 2² = 0.

Rozważmy f(x) jako funkcję ciągłą rzeczywistą. Zgodnie z twierdzeniem o wartościach pośrednich, równanie f(x) = 0 ma co najmniej jeden pierwiastek między a i b, gdy f(a)f(b) < 0. Innymi słowy, funkcja f(x) ma pierwiastek „c” gdzieś między a i b.

Ta właściwość zmiany znaku jest dokładnie tym, co wykorzystuje metoda bisekcji. W następnej sekcji pokazano, jak ta koncepcja wygląda graficznie.

Graficzna reprezentacja metody bisekcji

Poniższy wykres przedstawia mechanizm działania metody bisekcji. Na wykresie widać, że rzeczywisty pierwiastek równania jest zaznaczony na czerwono.

Procedurę można podsumować następująco:

• Najpierw wybieramy dwa początkowe przypuszczenia,₁ oraz b₁, dla którego f(a₁)pełne wyżywienie₁) < 0. Zgodnie z twierdzeniem o wartościach pośrednich pierwiastek musi leżeć w [a₁b₁].
• Następnie obliczamy punkt środkowy₁ oraz b₁, który jest b₂Początkowy interwał został teraz skrócony do [a₁b₂], ponieważ f(a₁)pełne wyżywienie₂) < 0.
• W ten sam sposób przedział jest wielokrotnie zmniejszany o połowę, aż do znalezienia przybliżonego rozwiązania mieszczącego się w żądanej tolerancji.

Mając jasną intuicję geometryczną, możemy teraz sformalizować procedurę jako algorytm krok po kroku.

Algorytm metody Bisekcji

Poniżej przedstawiono kroki zastosowania algorytmu metody bisekcji w celu znalezienia pierwiastka równania f(x) = 0.

Krok 1) Wybierz początkowe przypuszczenia a, b i współczynnik tolerancji e.

Krok 2) Jeżeli f(a)f(b) >= 0, to pierwiastek nie leży w tym przedziale. W takim przypadku nie ma rozwiązania w przedziale [a, b].

Krok 3) Znajdź punkt środkowy, c = (a + b)/2.

(i) Jeśli wartość funkcji w punkcie środkowym f(c) = 0, to c jest pierwiastkiem. Przejdź do kroku 5.
(ii) Jeśli f(a)f(c) < 0, pierwiastek leży między a i c. Wówczas przyjmijmy, że a = a, b = c.
(iii) W przeciwnym wypadku ustaw a = c, b = b.

Krok 4) Jeżeli błąd bezwzględny jest wyższy od współczynnika tolerancji, czyli (b – a) > e, wróć do kroku 3.

Krok 5) Wyświetl c jako przybliżony pierwiastek.

Zobaczmy przykład algorytmu metody bisekcji w akcji. Obliczymy pierwiastek poniższej funkcji ciągłej, używając wzoru metody bisekcji.

fa(x) = x³ - x² + 2

Przykład metody bisekcji

Krok 1) Załóżmy,

         a = -10,
         b = 10 i
         e = 1% lub 0.01.

Krok 2) Teraz sprawdzimy, czy f(a)f(b) >= 0, czy nie.

         f(a) = f(-10) = (-10)³ – (-10)² + 2 = -1098
         f(b) = f(10) = (10)³ - (10)² + 2 = 902
         f(a)f(b) = f(-10)f(10) = (-1098)(902) < 0

Zatem pierwiastek powyższej funkcji leży w przedziale [-10, 10].

Krok 3) Następnie obliczany jest punkt środkowy c.

Teraz należy sprawdzić następujące warunki:

(i) Czy f(c) = 0:
         f(c) = f(0) = (0)³ - (0)² + 2 = 2, co nie jest równe 0.

(ii) Czy f(a)f(c) < 0:
         f(c)f(a) = 2 * (-1098) < 0

Warunek jest spełniony. W kolejnej iteracji wartości będą następujące:

         a = a = -10
         b = do = 0

Krok 4) Gdy (b – a) = (0 – (-10)) = 10 > 0.01, proces jest powtarzany. Kolejne iteracje przedstawiono w poniższej tabeli.

Krok 5) W 11. iteracji warunek z kroku 4 staje się fałszywy. Zatem przybliżony pierwiastek tego równania wynosi -1.00586.

Po zakończeniu przykładu liczbowego następna sekcja prezentuje diagram logiczny obrazujący cały przepływ sterowania.

Schemat logiczny metody bisekcji

Poniższy schemat blokowy podsumowuje logikę decyzyjną metody Bisekcji, w tym sprawdzenie nawiasów, aktualizację punktu środkowego i test tolerancji.

Rzekomy-Code

Poniższy pseudokod odzwierciedla algorytm i stanowi wzór do implementacji metody Bisekcji w dowolnym języku programowania.

Start
Set a, b, e
if f(a)*f(b) >= 0
    Output("Root does not exist in this interval")
    Stop
while (b-a) > e do
    c ← (a + b)/2
    if f(c) = 0
        break
    end if
    if f(c)*f(a) < 0 then
        b ← c
    else
        a ← c
end while
Output(c)
Stop

Przykład metody bisekcji w C/C++

Następujące C/C++ program implementuje metodę bisekcji w celu znalezienia pierwiastka równania f(x) = x³ - x² + 2 w przedziale [-10, 10].

Wejście:

#include <bits/stdc++.h>
using namespace std;
#define Error 0.01
double value(double x)
{
    return x*x*x - x*x + 2;
}
void bisection_method(double a, double b)
{
    if (value(a) * value(b) >= 0)
    {
        cout << "The root does not lie in this interval\n";
        return;
    }
    double c = a;
    while ((b-a) >= Error)
    {
        c = (a+b)/2;
        if (value(c) == 0.0)
            break;
        else if (value(c)*value(a) < 0)
            b = c;
        else
            a = c;
    }
    cout << "The root is :" << c;
}
int main()
{
    double a = -10, b = 10;
    bisection_method(a, b);
    return 0;
}

Wyjście:

The root is :-1.00586

Przykład metody bisekcji w Python

Python wersja poniżej generuje ten sam przybliżony pierwiastek, stosując identyczną logikę, dzięki czemu idealnie nadaje się do szybkiego eksperymentowania i nauczania.

Wejście:

def value(x):
    return x*x*x - x*x + 2

def bisection_method(a, b):
    if (value(a) * value(b) >= 0):
        return
    c = a
    while ((b-a) >= 0.01):
        c = (a+b)/2
        if (value(c) == 0.0):
            break
        if (value(c)*value(a) < 0):
            b = c
        else:
            a = c
    print("The root is : ", "%.4f" % c)

a = -10
b = 10
bisection_method(a, b)

Wyjście:

The root is :  -1.0059

Zalety i ograniczenia metody bisekcji

Jak każda technika numeryczna, metoda bisekcji ma wyraźne zalety i kilka praktycznych wad. Poniższa tabela podsumowuje najważniejsze zalety i wady.

Zastosowania metody bisekcji

Metoda bisekcji jest stosowana w wielu praktycznych i nowoczesnych scenariuszach obliczeniowych, w których wymagany jest solidny krok znajdowania pierwiastków.

• Symulacje inżynierskie: Rozwiązywanie równań nieliniowych występujących w przenoszeniu ciepła, dynamice płynów i analizie strukturalnej.
• Modelowanie finansowe: Obliczanie rentowności, wewnętrznych stóp zwrotu i punktów rentowności w przypadku, gdy nie istnieją rozwiązania w formie zamkniętej.
• Uczenie maszynowe i AI: Lokalizowanie progów, kalibracja modeli i dostrajanie hiperparametrów w ramach numerycznych rozwiązań opartych na sztucznej inteligencji.
• Grafika komputerowa: Wyznaczanie przecięć promieni i powierzchni oraz wartości parametrów wzdłuż krzywych.
• Systemy wbudowane: Przybliżone korzenie w kontrolerach o niskim zasobie, gdzie prostota i przewidywalność są ważniejsze niż szybkość.

FAQ