Modul 5 METODE BIDANG-PARUH (BISECTION) untuk Solusi Akar PERSAMAAN ALJABAR NON-LINIER TUNGGAL
A. Pendahuluan Persamaan Aljabar Non-Linier Tunggal atau PANLT merupakan sembarang fungsi atau persamaan aljabar yang terbentuk berdasarkan proyeksi ‘fungsional’ variabel bebasnya (pada sumbu datar, absis) pada variabel terikatnya (pada sumbu tegak, ordinat): y ( x) ≡
f ( x)
Sedangkan problem utama yang dijumpai dalam pencarian akar suatu PANLT adalah: ‘perpotongan’ persamaan (kurva) itu dengan sumbu datar pada titik α (sehingga akarnya disebut juga sebagai α), dan pada saat yang bersamaan fungsi f(x) tersebut juga mencapai ‘nilai nol’nya. Bentuk umum PANLT ini dapat dituliskan sebagai: f ( x) = 0
Berbagai teknik telah dikembangkan untuk pencarian akar (atau akar-akar) dari suatu PANLT dengan bentuk umum seperti di atas. Bebarapa di antaranya dapat dikelompokkan dalam metode-metode berikut: 1. ‘Metode Titik Tetap’ (fixed-point), yaitu suatu metode pendekatan numeris yang terbentuk dari reorganisasi PANLT sedemikian rupa sehingga dihasilkan 2 buah fungsi, di sisi yang satu hanya mengandung variabel bebasnya saja sedangkan di sisi lainnya berbentuk g(x), suatu fungsi dalam bentuk yang lain. Metode ini memerlukan 1 (satu) buah harga x (disebut sebagai xawal) sebagai ‘tebakan’ untuk memulai proses iterasi. Karena sifatnya yang kurang praktis, bahkan tidak efisien dan juga lambat dalam mencapai konvergensi, maka metode ini tidak akan dibicarakan lebih lanjut dalam kuliah ini. Seri Kuliah Metode Numerik (Modul 5: Metode Bisection untuk Solusi PANLT (Persamaan Aljabar Non-Linier Tunggal)
(1/1)
2. ‘Metode Bidang Bebas’ atau lebih spesifik lagi ‘Metode Bidang Paruh’ (Bisection). Prinsip dari metode ini adalah “pemaruhan” (nilai rata-rata) dari nilai estimasi akar suatu PANLT yang dibentuk dengan cara ‘menebak’ 2 buah harga awal pada interval [a,b] yang bertempat-kedudukan ‘mengapit’ (di kiri dan kanan) akar atau jawab yang sebenarnya. Metode ini pada umumnya memerlukan 2 (dua) buah tebakan untuk harga-harga x-awal (x0 dan x1). 3. ‘Metode Tangent’ atau yang dikenal sebagai Metode Newton atau Metode Newton-Raphson, yang dihasilkan dari ekspansi f(α) sampai suatu harga x tertentu (xn) menggunakan deret Taylor, dengan cara mengabaikan term order (α - xn)2 atau yang lebih tinggi. Alternatif lain, penurunan tersebut juga dapat dilakukan secara geometris, yang akan dijelaskan lebih lanjut pada Modul 7. 4. ‘Metode Secant’, yang terbentuk dari pendekatan melalui ‘garis secant’ di sekitar jawab atau akar persamaan α. Di sisi lain, metode ini sebenarnya bentuk atau ‘varian numeris’ dari bentuk turunan yang dipersyaratkan oleh Metode Newton Raphson. Metode ini akan dijelaskan lebih jauh pada Modul 8.
B. Solusi Akar PANLT dengan Metode Bisection Solusi akar (atau akar-akar) dengan menggunakan Metode Bisection memiliki sifat-sifat numeris sebagai berikut: (a) Selalu melakukan pembagian dua (pemaruhan) interval [a,b] yang mengapit akar α, sehingga setelah n kali iterasi akan didapatkan akar persamaan yang berdekatan dengan harga yang sebenarnya (solusi analitis), dengan memperhitungkan ‘kriteria’ (akurasi) yang diinginkan. (b) Kecepatan atau laju konvergensi dari metode bisection dapat diperkirakan menggunakan persamaan pendekatan: α − cn
≤
( ) (b − a ) 1 n 2
Seri Kuliah Metode Numerik (Modul 5: Metode Bisection untuk Solusi PANLT (Persamaan Aljabar Non-Linier Tunggal)
(2/2)
yang dapat dibuktikan bahwa: α
=
lim cn
n →∞
(c) Panjang (b − a ) menggambarkan ‘panjang interval’ yang digunakan sebagai ‘harga awal’ untuk memulai proses iterasi dalam ‘metode bisection’; yang berarti bahwa metode ini memiliki ‘konvergensi linier’ dengan laju 1 2 .
C. Representasi Grafis dari Metode Bisection Representasi grafis dari metode bisection sebagai berikut: f(x)
[a
b]
X0
X2
X1
x
Gambar 5.1. Representasi grafis metode bisection.
Dari representasi grafis di atas, dapat diambil kesimpulan dengan jelas, bahwa: x2
=
x1 − x0 2
sehingga setelah n kali iterasi akan diperoleh: atau xn +1
=
x1 − x0 2n
Pada saat panjang interval [a,b] tidak melampaui suatu harga t (yang di dalamnya terdapat akar α), sedemikian rupa sehingga jarak Seri Kuliah Metode Numerik (Modul 5: Metode Bisection untuk Solusi PANLT (Persamaan Aljabar Non-Linier Tunggal)
(3/3)
akar α tersebut dengan ekstremitas interval tidak melebihi t, maka pada saat itu toleransi perhitungan sudah dapat dilakukan.
D. Algoritma Metode Bisection Asumsi awal yang harus diambil adalah: ‘menebak’ interval awal [a,b] dimana f(x) adalah kontinu padanya, demikian pula harus terletak ‘mengapit’ (secara intuitif) nilai akar α, sedemikian rupa sehingga: f (a) ⋅ f (b) ≤ 0
Algoritma BISECT(f,a,b,akar,ε,iter,itmax,flag) 1. Tebak harga interval [a,b]; tentukan ε; dan itmax 2. Set f0 = f(a); iter = 0; flag = 0; 3. Tentukan atau hitung akar = c := (a + b)/2; iter = iter + 1; 4. Jika f(a)·f(c) ≤ 0 maka b = c jika tidak a = c dan f0 = f(a); 5. Jika (b – a) ≤ ε maka flag = 1 jika iter > itmax maka flag = 2; 6. Jika flag = 0 ulangi ke nomor 3; 7. Akar persamaan adalah: akar = (a + b)/2, sebagai akar terbaru; 8. Selesai.
Seri Kuliah Metode Numerik (Modul 5: Metode Bisection untuk Solusi PANLT (Persamaan Aljabar Non-Linier Tunggal)
(4/4)
E. Listing Program Metode Bisection Diberikan persoalan untuk mengitung akar (akar-akar) persamaan f(x) = 0, sebagai berikut: f ( x) ≡
x − e1 x
= 0
Listing program sederhana (non-subroutine) dan program dengan subroutine disertakan dalam gambar-gambar 5.2. dan 5.3. di bawah ini, yang ditulis dalam Bahasa FORTRAN 77 (kompatibel dengan Bahasa FORTRAN 90/95): C C C C C C C C
Program: Solusi Persamaan Aljabar Non-Linier Tunggal (PANLT) dengan Metode 'Bisection' VARIAN: Program sederhana/Non-Subroutine Kondisi proses dinyatakan dalam variabel 'flag' flag = 0; berarti sistem masih dalam proses iterasi flag = 1; berarti proses telah mencapai konvergensi flag = 2; berarti jumlah iterasi maksimum telah terlampaui ------------------------------------------------------------implicit none REAL*8 eps,f,fx,f0,x,x0,x1 INTEGER flag,iter,maxiter
WRITE(*,'(A,$)') 'Harga-harga awal x0, x1 : ' READ(*,*) x0,x1 WRITE(*,'(A,$)') 'Jumlah iterasi maksimum : ' READ(*,*) maxiter WRITE(*,'(A,$)') 'Epsilon/kriteria proses : ' READ(*,*) eps f0 = f(x0) iter = 0 flag = 0 DO WHILE(flag .EQ. 0) iter = iter + 1 x = (x0 + x1)/2 fx = f(x) IF ((f0*fx) .LE. 0.0D0) THEN x1 = x ELSE x0 = x f0 = fx ENDIF IF ((x1 - x0) .LE. eps) THEN flag = 1 ELSEIF (iter .GT. maxiter) THEN flag = 2 ENDIF ENDDO
Seri Kuliah Metode Numerik (Modul 5: Metode Bisection untuk Solusi PANLT (Persamaan Aljabar Non-Linier Tunggal)
(5/5)
x = (x0 + x1)/2 WRITE(*,*) WRITE(*,*) WRITE(*,*) WRITE(*,*) WRITE(*,*)
'x0 = ',x0 'x1 = ',x1 'x = ',x 'f(x) = ',f(x) 'Jumlah iterasi = ',iter
STOP END
FUNCTION f(x) REAL*8 f,x f = x - exp(1.0D0/x) RETURN END
Gambar 5.2. Listing program sederhana (tanpa subroutine).
C C C C
Program: Solusi Persamaan Aljabar Non-Linier Tunggal (PANLT) dengan Metode 'Bisection' VARIAN: Program dengan Subroutine ------------------------------------------------------------implicit none external f REAL*8 eps,f,x,x0,x1 INTEGER flag,iter,maxiter WRITE(*,'(A,$)') 'Harga-harga awal x0, x1 : ' READ(*,*) x0,x1 WRITE(*,'(A,$)') 'Jumlah iterasi maksimum : ' READ(*,*) maxiter WRITE(*,'(A,$)') 'Epsilon/kriteria proses : ' READ(*,*) eps CALL BISECT(f,x0,x1,x,eps,iter,maxiter,flag) WRITE(*,*) WRITE(*,*) WRITE(*,*) WRITE(*,*) WRITE(*,*)
'x0 = ',x0 'x1 = ',x1 'x = ',x 'f(x) = ',f(x) 'Jumlah iterasi = ',iter
STOP END
FUNCTION f(x) REAL*8 f,x f = x - exp(1.0D0/x) RETURN END Seri Kuliah Metode Numerik (Modul 5: Metode Bisection untuk Solusi PANLT (Persamaan Aljabar Non-Linier Tunggal)
(6/6)
SUBROUTINE BISECT(ff,x0,x1,x,eps,itnum,itmax,prflag) -------------------------------------------------------Sub-program: Solusi PANLT dengan metode BISECTION | atau NILAI PARUH | ff : fungsi f(x) = 0 yang akan dicari akarnya | x0 : nilai x-awal di sebelah kiri akar f(x) | x1 : nilai x-awal di sebelah kanan akar f(x) | x : akar f(x), nilai paruh (antara x0 dan x1) | eps : kriteria atau ketelitian penghitungan | itnum : jumlah iterasi yang dilakukan proses | itmax : jumlah pembatas iterasi untuk proses | prflag : identifikasi untuk konvergensi, yaitu: | 0 = proses sedang/akan berlangsung | 1 = proses mencapai konvergensinya | 2 = jumlah iterasi maksimum (itmax) telah | terlampaui | --------------------------------------------------------
C C C C C C C C C C C C C C C C
REAL*8 eps,ff,fx,f0,x,x0,x1 INTEGER prflag,itnum,itmax f0 = ff(x0) itnum = 0 prflag = 0 DO WHILE(prflag .EQ. 0) itnum = itnum + 1 x = (x0 + x1)/2 fx = ff(x) IF ((f0*fx) .LE. 0.0D0) THEN x1 = x ELSE x0 = x f0 = fx ENDIF IF ((x1 - x0) .LE. eps) THEN prflag = 1 ELSEIF (itnum .GT. itmax) THEN prflag = 2 ENDIF ENDDO x = (x0 + x1)/2 RETURN END
Gambar 5.3. Listing program dengan subroutine.
Tugas: Cari akar (akar-akar) dari persamaan:
f ( x) = e − x ⋅ ln( x) !
Seri Kuliah Metode Numerik (Modul 5: Metode Bisection untuk Solusi PANLT (Persamaan Aljabar Non-Linier Tunggal)
(7/7)
F. Pustaka yang bersesuaian Atkinson, Kendal E., “An Introduction to Numerical Analysis”, John Wiley & Sons, Toronto, pp. 39-44, 1978. Atkinson, L.V., Harley, P.J., “An Introduction to Numerical Methods with Pascal”, Addison-Wesley Publishing Co., Tokyo, pp. 46-49, 1983. Bismo, Setijo, “Kumpulan Bahan Kuliah Metode Numerik”, Jurusan TGP-FTUI, 1999.
Seri Kuliah Metode Numerik (Modul 5: Metode Bisection untuk Solusi PANLT (Persamaan Aljabar Non-Linier Tunggal)
(8/8)
