Mengenal "Bisection Method" dan Implementasinya dalam Python3

Maret 28, 2020   python3

Bagaimana sebuah komputer dapat menghitung akar dari suatu persamaan polinomial? Komputer ‘tidak secerdas manusia’, tetapi perhitungannya cepat. Oleh karena itu, metode numerik lumrah dipakai dalam metode komputasi dibanding metode analitik. Metode numerik salah satunya berpusat pada perhitungan secara berulang sehingga hasil akhirnya semakin mendekati nilai sebenarnya atau nilai analitik. Salah satu metode numerik yang paling mudah untuk menyelesaikan suatu persamaan adalah metode biseksi (“bisection method”).

Anggap kita mempunyai sebuah fungsi f(x) dimana r merupakan salah satu akar dari f(x) sehingga f(r) = 0. Pertama-tama, kita akan mempunyai seri x₁, x₂, …, x_n dengan x_n paling mendekati nilai r. x₁ dan x₂ harus dipilih sehingga r berada di antara keduanya atau x₁ < r < x₂. Karena f(r) = 0, maka f(x₁) dan f(x₂) harus memiliki tanda yang berbeda sehingga f(x0)*f(x1) < 0. Sementara itu, x₃ adalah nilai tengah dari x₁ dan x₂ yang diharapkan lebih mendekati nilai r dibandingkan pendahulunya, maka: 

x₃ = 0.5 * (x₁ + x₂). 

Kemudian, kita hitung lagi f(x₃): Apakah bernilai positif atau negatif? Jika bernilai positif, maka x₃ harus dipasangkan dengan yang nilainya negatif dan sebaliknya. Nilai r harus tetap “dikurung” oleh sepasang x_i yang baru, sehingga x₄ akan dipilih menjadi nilai tengah dari x₁ dan x₃ ataukah nilai tengah dari x₃ dan x₂. Seterusnya, hingga mencapai nilai presisi yang diinginkan. (Diterjemahkan dengan penyuntingan dari “Numerical Methods” oleh Chasnov, 2012)

Metode biseksi merupakan metode numerik yang masih terbilang sederhana. Untuk memahaminya, menghitung secara manual menggunakan tabel layak untuk di coba. Berikut adalah contoh menyelesaikan akar dari fungsi kuadrat sederhana f(x) = x² – 25.

Akar pertama, tebakan awal x1 = -6 dan x2 = -1.

iteration	x1	x2	x_mid	f1	f2	f_mid
1	-6.000	-1.000	-3.500	11.000	-24.000	-12.750
2	-6.000	-3.500	-4.750	11.000	-12.750	-2.440
3	-6.000	-4.750	-5.380	11.000	-2.440	3.890
4	-5.380	-4.750	-5.060	3.890	-2.440	0.630
5	-5.060	-4.750	-4.910	0.630	-2.440	-0.930
6	-5.060	-4.910	-4.980	0.630	-0.930	-0.160
7	-5.060	-4.980	-5.020	0.630	-0.160	0.230
8	-5.020	-4.980	-5.000	0.230	-0.160	0.040
9	-5.000	-4.980	-4.990	0.040	-0.160	-0.060
10	-5.000	-4.990	-5.000	0.040	-0.060	-0.010

Akar kedua, tebakan awal x1 = 0 dan x2 = 7.

iteration	x1	x2	x_mid	f1	f2	f_mid
1	0.000	7.000	3.500	-25.000	24.000	-12.750
2	3.500	7.000	5.250	-12.750	24.000	2.560
3	3.500	5.250	4.380	-12.750	2.560	-5.860
4	4.380	5.250	4.810	-5.860	2.560	-1.840
5	4.810	5.250	5.030	-1.840	2.560	0.310
6	4.810	5.030	4.920	-1.840	0.310	-0.780
7	4.920	5.030	4.980	-0.780	0.310	-0.230
8	4.980	5.030	5.000	-0.230	0.310	0.040
9	4.980	5.000	4.990	-0.230	0.040	-0.100
10	4.990	5.000	5.000	-0.100	0.040	-0.030

Pengulangan/iteration dapat terus dilanjutkan sampai selisih x1 dan x2 kurang dari nilai presisi tertentu. 

Jika kita plot x1, x2, dan x_mid pada sebuah grafik, x1 dan x2 terus mengerucut ke arah nilai akar r (garis putus-putus) sejalan dengan nilai tengahnya x_mid. (Sehingga metode ini dinamai metode biseksi)

Fungsi sda. tetapi x1 = 0 dan x2 = 30.

Algoritma yang kita lakukan pada penghitungan tabel dapat kita tuliskan kembali ke dalam bahasa pemrograman. Berikut adalah contoh implementasi algoritma metode biseksi dalam naskah kode Python.

"""
contoh metode numerik biseksi
Alwan Darussalam (28/03/2020)
"""

# fungsi tes f(x) = x^2 - 25
fun = lambda x: x**2 - 25

x0 = 0.0
x1 = 30.0
conv = 1e-5
max_iter = 100 

f0 = fun(x0)
f1 = fun(x1)

#collect_x0 = [x0]
#collect_x1 = [x1]

# syarat metode bisection berlaku hanya jika f0*f1 < 0
if f0 * f1 < 0:
    for i in range(max_iter):
        x2 = x0 + 0.5 * (x1 - x0)
        f2 = fun(x2)

        if f0 * f2 < 0:
            x1 = x2 # geser x1 ke kiri
        else:
            x0 = x2 # geser x0 ke kanan
#        collect_x0.append(x0)
#        collect_x1.append(x1)       
        if abs(f2) <= conv:
            print("Perhitungan konvergen di x =", x2)
            break # menghentikan loop
    r = x2
    print('Sehingga, r=', r, 'f(r)=', f2)
else:
    print("r tidak terkurung, ubah nilai x0 atau x1")

Metode biseksi sudah terimplementasi secara praktis dalam SciPy. (scipy.optimize.bisect) Masukan yang diperlukan cukup fungsi yang akan diselesaikan serta tebakan pertama untuk x1 dan x2. Walaupun begitu, menulis naskah metode biseksi dari awal sangat bagus untuk latihan memahami algoritma pemrograman.