Algoritma Metode Bisection dengan Contoh

Apa itu Metode Bisection?

Metode Bisection adalah salah satu teknik numerik paling mendasar untuk menemukan akar dari persamaan polinomial atau transendental. Metode ini bekerja dengan mengapit interval yang mengandung akar dan kemudian membagi interval tersebut menjadi dua bagian pada setiap iterasi hingga akar ditemukan dalam toleransi yang dapat diterima. Karena perilaku pengapitan ini, Metode Bisection juga disebut sebagai metode pengapitan.

Karena mekanisme kerjanya menyerupai pencarian biner, Metode Bisection juga dikenal sebagai metode pencarian biner, metode pembagian dua, atau metode dikotomi. Metode ini bertumpu pada landasan teoritis yang kuat: Teorema Nilai Tengah, yang menjamin bahwa fungsi kontinu yang berubah tanda pada suatu interval harus melewati nol di suatu tempat di dalam interval tersebut.

Setelah memahami definisi dasarnya, mari kita jelajahi mengapa menemukan akar persamaan itu penting dan bagaimana Metode Bisection cocok dalam gambaran yang lebih luas tersebut.

Menemukan Akar Persamaan

Dalam pembahasan ini, kita hanya berfokus pada persamaan dengan satu variabel independen. Persamaan tersebut dapat berupa persamaan linear atau non-linear. Persamaan linear menggambarkan grafik garis lurus, sedangkan persamaan non-linear menggambarkan kurva dan bentuk yang lebih kompleks.

Akar dari suatu persamaan adalah nilai variabel independen yang memenuhi persamaan tersebut. Misalnya, akar dari persamaan f(x) = 4 – x² = 0 adalah 2, karena f(2) = 4 – 2² = 0.

Mari kita anggap f(x) sebagai fungsi kontinu riil. Menurut Teorema Nilai Tengah, persamaan f(x) = 0 memiliki setidaknya satu akar di antara a dan b setiap kali f(a)f(b) < 0. Dengan kata lain, fungsi f(x) memiliki akar, "c," di suatu tempat di antara a dan b.

Sifat perubahan tanda inilah yang dimanfaatkan oleh Metode Bisection. Bagian selanjutnya akan menunjukkan bagaimana ide ini terlihat secara grafis.

Representasi Grafis dari Metode Bisection

Grafik berikut menggambarkan mekanisme kerja Metode Bisection. Dari grafik tersebut, kita dapat melihat bahwa akar sebenarnya dari persamaan ditandai dengan warna merah.

Prosedur tersebut dapat diringkas sebagai berikut:

• Pertama-tama kita memilih dua tebakan awal, yaitu₁ dan B₁, yang mana f(a)₁)f(b₁) < 0. Menurut Teorema Nilai Tengah, akarnya harus terletak di [a₁, b₁].
• Kemudian kita menghitung titik tengah dari a₁ dan B₁, yang merupakan b₂Interval awal sekarang dikurangi menjadi [a]₁, b₂] karena f(a₁)f(b₂) < 0.
• Dengan cara yang sama, interval tersebut dibagi dua lagi dan lagi hingga ditemukan solusi perkiraan dalam toleransi yang diinginkan.

Dengan pemahaman intuisi geometris yang jelas, kita sekarang dapat memformalkan prosedur tersebut sebagai algoritma langkah demi langkah.

Algoritma Metode Bagi Dua

Langkah-langkah untuk menerapkan algoritma Metode Bisection untuk menemukan akar persamaan f(x) = 0 adalah sebagai berikut.

Langkah 1) Pilih tebakan awal a, b, dan tingkat toleransi e.

Langkah 2) Jika f(a)f(b) >= 0, maka akarnya tidak terletak di interval ini. Dalam hal ini, tidak ada solusi di dalam [a, b].

Langkah 3) Carilah titik tengahnya, c = (a + b)/2.

(i) Jika nilai fungsi pada titik tengah f(c) = 0, maka c adalah akarnya. Lanjutkan ke langkah 5.
(ii) Jika f(a)f(c) < 0, akar terletak di antara a dan c. Maka tetapkan a = a, b = c.
(iii) Jika tidak, tetapkan a = c, b = b.

Langkah 4) Jika kesalahan absolut lebih tinggi dari tingkat toleransi, yaitu (b – a) > e, kembali ke langkah 3.

Langkah 5) Tampilkan c sebagai perkiraan root.

Mari kita lihat contoh penerapan algoritma Metode Bisection. Kita akan mencari akar dari fungsi kontinu berikut menggunakan rumus Metode Bisection.

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

Contoh Metode Bagi Dua

Langkah 1) Mari kita asumsikan,

         sebuah = -10,
         b = 10, dan
         e = 1% atau 0.01.

Langkah 2) Sekarang, kita akan memeriksa apakah f(a)f(b) >= 0 atau tidak.

         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

Oleh karena itu, akar dari fungsi di atas terletak pada interval [-10, 10].

Langkah 3) Selanjutnya, titik tengah c dihitung.

Sekarang kondisi berikut perlu diperiksa:

(i) Apakah f(c) = 0:
         f(c) = f(0) = (0)³ - (0)² + 2 = 2, yang tidak sama dengan 0.

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

Syaratnya terpenuhi. Untuk iterasi berikutnya, nilainya akan menjadi:

         a = a = -10
         b = c = 0

Langkah 4) Karena (b – a) = (0 – (-10)) = 10 > 0.01, proses diulang. Iterasi berikutnya ditunjukkan pada tabel di bawah ini.

Langkah 5) Pada iterasi ke-11, kondisi pada langkah ke-4 menjadi salah. Dengan demikian, akar perkiraan dari persamaan ini adalah -1.00586.

Setelah contoh numerik selesai, bagian selanjutnya menyajikan diagram logika yang menggambarkan alur kontrol secara lengkap.

Diagram Logika Metode Bagi Dua

Diagram alir di bawah ini merangkum logika pengambilan keputusan dari Metode Bisection, termasuk pemeriksaan tanda kurung, pembaruan titik tengah, dan uji toleransi.

Semu-Code

Kode semu di bawah ini mencerminkan algoritma tersebut dan berfungsi sebagai cetak biru untuk mengimplementasikan Metode Bisection dalam bahasa pemrograman apa pun.

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

Contoh Metode Bagi Dua di C/C++

Berikut ini C/C++ Program ini mengimplementasikan Metode Bisection untuk menemukan akar dari f(x) = x.³ - x² + 2 dalam interval [-10, 10].

Memasukkan:

#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;
}

Keluaran:

The root is :-1.00586

Contoh Metode Bagi Dua di Python

The Python Versi di bawah ini menghasilkan akar perkiraan yang sama menggunakan logika yang identik, sehingga ideal untuk eksperimen cepat dan pengajaran.

Memasukkan:

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)

Keluaran:

The root is :  -1.0059

Keunggulan dan Keterbatasan Metode Bisection

Seperti setiap teknik numerik, Metode Bisection memiliki kekuatan yang jelas dan beberapa kekurangan praktis. Tabel di bawah ini merangkum kelebihan dan kekurangan yang paling penting.

Penerapan Metode Bisection

Metode Bisection digunakan dalam banyak skenario komputasi praktis dan modern di mana langkah pencarian akar yang kuat diperlukan.

• Simulasi teknik: Menyelesaikan persamaan nonlinier yang muncul dalam perpindahan panas, dinamika fluida, dan analisis struktur.
• Pemodelan keuangan: Menghitung imbal hasil, tingkat pengembalian internal, dan titik impas di mana solusi bentuk tertutup tidak ada.
• Pembelajaran mesin dan AI: Menentukan ambang batas, mengkalibrasi model, dan menyetel hyperparameter di dalam pemecah numerik berbasis AI.
• Grafik komputer: Menentukan titik perpotongan sinar-permukaan dan nilai parameter di sepanjang kurva.
• Sistem tertanam: Memperkirakan akar pada pengontrol dengan sumber daya terbatas di mana kesederhanaan dan prediktabilitas lebih berharga daripada kecepatan.

Pertanyaan Umum Demo Slot