Sunday, May 14, 2017

Komputasi Numeris: Metode Setengah Interval (Bisection Method).

Pendahuluan

Walaupun primitif dan merupakan metode dengan segala keterbatasan yang ada, metode setengah interval adalah metode paling sederhana dan paling mudah untuk dipahami sehingga cocok sebagai pembelajaran awal mata kuliah "Komputasi/ Metode Numeris". Kesederhanaan yang penulis maksud adalah kemudahan untuk menjelaskan istilah "interval" yang nanti akan kita gunakan pada metode secant pada pembahasan berikutnya. Metode ini metode iteratif yang digunakan untuk mencari akar persamaan (linier maupun non-linear) yang memiliki akar real.

Dasar Teori

1. Menentukan area awal

Metode setengah interval dimulai dari menentukan area (interval) awal sedemikian rupa sehingga, interval tsb mengapit akar pesamaan yang akan kita cari.
Gambar 1: Penentuan Area Awal
 
Ini kesulitan pertama metode setengah interval. Area awal yang dipilih HARUS mengapit akar yang akan dicari. Cara paling mudah adalah menentukan area awal, selebar-lebarnya, tapi ini akan berakibat pada jumlah iterasi yang semakin banyak.

Okay sementara, abaikan jumlah iterasi yang banyak tersebut, yang penting, ketemu dulu akarnya. :)

2. Membagi dua area.

Setelah interval awal kita tentukan, berikutnya, kita bagi area tersebut menjadi dua (red: inilah yang menyebabkan metode ini disebut metode setengah interval) sehingga grafiknya menjadi seperti berikut:

Gambar 2: Pembagian Dua Area

Proses ini mudah, tinggal jumlahkan nilai X1 dan X3 kemudian dibagi 2. Dapatlah nilai X2.

3. Membuang area yang tidak diperlukan.

Bagian ini sedikit sulit. Jika kita melihat grafik, mungkin tidak sulit bagi kita untuk menentukan bahwa area yang akan dibuang adalah area antara X1 s.d. X2. Tapi bagaimana jika dilakukan menggunakan program?

Untuk membuang daerah yang tidak diperlukan kita bisa memasukkan nilai X1, X2 dan X3 pada persamaan yang akan kita cari yaitu f(X1), f(X2) dan f(X3) seperti terlihat pada gambar berikut:

Gambar 3: Penentuan Titik-Titik Fungsi

Setelah kita tentukan, nilai f(X1), f(X2) dan f(X3), berikutnya kita "pilih" yang mana dari nilai X1 atu X3 yang akan kita "replace" dengan X2. Kata me-replace di sini artinya dibuang.

Caranya?

Kita pilih di antara X1 dan X3 yang memiliki tanda yang sama dengan X2. Sama-sama positif atau sama-sama negatif. Menentukannya mana di antara X1 dan X3 yang memiliki tanda yang sama dengan X2, cukup kalikan saja f(X1) dengan f(X2). Jika menghasilkan nilai positif ( > 0 ) maka f(X1) memiliki tanda yang sama dengan f(X2). Ini sesuai kodrat alam yang mengatakan:

"Jika dua bilangan dikalikan menghasilkan bilangan positif, maka kedua bilangan tersebut sama tandanya dan jika negatif maka kedua bilangan tersebut berbeda tanda"

 Sehingga grafik di atas menjadi:

Gambar 4: Area Setelah Dibagi Dua.

4. Mencari Error

Kata orang, mencari kesalahan adalah usaha paling mudah. Apalagi "kesalahan orang lain". Di sinipun, mencari kesalahan bisa menggunakan beberapa cara. Misalnya:
  • Mencari selisih antara X2 dengan nilai X2 sebelumnya.
  • Selisih antara nilai mutlak f(X2) dengan 0
Saya menggunakan cara yang kedua.

Apabila selisih antara f(X2) dengan 0 sudah lebih kecil dari toleransi error yang diberikan, maka selesailah sudah. Nilai X2 itulah yang menjadi akar persamaan. Jika belum, ulangi langkah 2.

5. Hasil akhir

Proses lengkap dari metode bisection ini digambarkan sebagai berikut:

Gambar 5. Iterasi Bisection


Algoritma Metode Bisection

Setelah kita paham metode bisection, saatnya kita tulis algoritma sederhananya (dulu).
  1. Tentukan nilai awal X1 dan X3, toleransi_error=0.0001, f(X2) = 1 dan jumlah_langkah = 0.
  2. Ketika f(X2) > toleransi error:
  3. Cari X2 = (X1 + X3) / 2  
  4. Cari f(X1) dan f(X2)
  5. Jika (f(X1) * f(X2)) > 0
  6. X1 = X2
  7. Jika tidak, X3 = X2
  8. Cari nilai mutlak f(X2) = | f(X2)|
  9. Loop ke langkah 2.
  10. Tampilkan hasil persamaan = X2.
  11. Selesai
Algoritma di atas, adalah algoritma sederhana dari metode bisection. Silahkan improvisasi sendiri untuk anomali-anomali yang ada.

  • Nilai X1 dan X3 ternyata tidak mengapit akar persamaan yang dicari
  • Ada lebih dari satu akar pada arena X1 dan X3 yang ditentukan.
Listing program:

Asumsikan persamaan yang akan kita cari adalah: f(x) = x^2 - x - 6 dimana akar yang akan kita peroleh seharusnya 3 dan -2.

#include <iostream>
using namespace std;

void main() {

    float x1,x2,x3,fx1,fx2,fx3,toleransi_error;
    int iterasi;

    cout << "Masukkan Nilai X1 : ";
    cin >> x1;
    cout << "Masukkan Nilai X3 : ";
    cin >> x3;

    toleransi_error=1;
    iterasi=0;
   
    while (toleransi_error > 0.00001)
    {
        iterasi++;
        fx1 = (x1 * x1) - x1 - 6;
        fx3 = (x3 * x3) - x3 - 6;

        x2 = (x1 + x3) / 2;
        fx2 = (x2 * x2) - x2 - 6;

        if ((fx1 * fx2) > 0)
            x1 = x2;
        else
            x3 = x2;

        if (fx2 < 0)
            toleransi_error = fx2 * -1;
        else
            toleransi_error = fx2;

    }

    cout << "Jumlah iterasi : " << iterasi << endl;
    cout << "Akar persamaan : " << x2 <<endl;

    system ("pause");
}


Testing Program

Setelah kita tulis kode program, saatnya kita jalankan program sederhana tersebut.


 
Gambar 6: Output Program

Ingat, contoh di atas adalah penerapan metode bisection paling sederhana dengan mengabaikan anomali-anomali yang ada. Silahkan di-improvisasi sendiri untuk anomali-anomali tersebut.

Versi Excel

Berikut angka-angka metode bisection jika ditulis menggunakan MS Excel:

Silahkan unduh versi excelnya di sini.

Selamat mencoba.