Metode iterative adalah suatu prosedur matematika dimana
akan didapat nilai yang diinginkan dari persamaan-persamaan matematika dengan
terlebih dahulu memberikan nilai awal. Nilai awal adalah nilai sembarang yang
dimasukkan diawal. Dengan memasukkan nilai awal tersebut, maka komputer akan
melakukan perhitungan sampai error mendekati atau bahkan nol. Ketika error
masik sangat besar, maka computer akan terus melakukan perhitungan sampai pada
akhirnya error mendekati atau sama dengan nol. Kondisi ini yang disebut sebagai
kondisi konvergen.
Berikut adalah macam-macam metode iterative yang biasa
digunakan :
- Metode
bisection
- Metode
False Position
- Metode
Newton-Raphson
- Metode
Secant
Berikut akan dijelaskan masing-masing metode iterative
tersebut
Metode Bisection
‘Metode Bidang Bebas’ atau lebih spesifik lagi ‘Metode
Bidang Paruh’ (Bisection) adalah “pemaruhan”(nilai rata-rata) dari nilai
estimasi akar suatu persamaan aljabar non-linear tunggal 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).
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 a,
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:
Yang dapat dibuktikan bahwa
(c)
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.
Representasi grafik dari metode bisection adalah sebagai
berikut :
Dari
representasi grafis di atas, dapat diambil kesimpulan dengan jelas, bahwa:
sehingga
setelah n kali iterasi akan diperoleh: atau
Pada
saat panjang interval [a,b] tidak melampaui suatu harga t (yang
di dalamnya terdapat akar a), sedemikian rupa sehingga jarak akar a tersebut dengan ekstremitas
interval tidak melebihi t, maka pada saat itu toleransi perhitungan
sudah dapat dilakukan.
Adapun
algoritma metode bisection adalah sebagai berikut :
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 a, sedemikian rupa sehingga:
f (a) × f (b)
£ 0
Algoritma BISECTION
(f,a,b,akar,e,iter,itmax,flag)
- Tebak harga interval [a,b];
tentukan e; dan itmax
- Set f0 = f(a);
iter = 0; flag = 0;
- Tentukan atau hitung akar
= c := (a + b)/2; iter = iter + 1;
- Jika f(a)·f(c)
£ 0
maka b = c jika tidak a = c dan f0 = f(a);
- Jika (b – a)
£ e
maka flag = 1 jika iter > itmax maka flag = 2;
- Jika flag = 0
ulangi ke nomor 3;
- Akar persamaan adalah: akar
= (a + b)/2, sebagai akar terbaru;
- Selesai.
Kelebihan metode bisection : Sangat simple, konvergen terjamin
Kekurangan metode bisection : Proses konvergen lamban.
Metode False
Position
Solusi
akar (atau akar-akar) dengan menggunakan Metode Regula-Falsi merupakan
modifikasi dari Metode Bisection dengan cara memperhitungkan ‘kesebangunan’
yang dilihat pada kurva berikut:
Perhatikan
kesebangunan 2 segitiga Pcb dan PQR, sehingga persamaan berikut dapat
digunakan:
Atau
Sehingga
Persamaan
di atas disebut sebagai persamaan rekursif dari Metode Regula Falsi.
Kecepatan
atau laju konvergensi dari Metode Regula-Falsi sama dengan Metode Bisection,
yaitu ‘konvergensi linier’, namun dengan faktor pengali (konstanta) yang
lebih besar dari 1 2 (factor pengali berkisar antara 1/ 2 … 1).
Adapun
algoritma dari metode false position adalah :
Asumsi
awal yang harus diambil adalah sama seperti pada Metode Bisection, yaitu: ‘menebak’
interval awal [a,b] dimana f(x) adalah kontinu
padanya, demikian pula interval tersebut harus terletak ‘mengapit’ (secara
intuitif) nilai akar a,
sedemikian rupa sehingga:
f (a) × f (b)
£ 0
Meskipun
pada algoritma berikut masih mengandung beberapa kelemahan, namun secara umum
masih sangat menguntungkan untuk dipakai. Perbaikan dan modifikasi secara
numeris dilakukan oleh Brent (Atkinson, 1978), untuk algoritma tersebut.
Algoritma REGFAL(f,a,b,akar,e,iter,itmax,flag)
- Tebak harga interval [a,b];
tentukan e; dan itmax
- Set xold = 2*b-a;
iter = 0; flag = 0;
- Tentukan atau hitung akar
= c = b – f(b) [(b – a)/(f(b)
– f(a)); iter = iter + 1;
- Jika f(b)·f(c)
£ 0
maka a = c jika tidak b = c;
- Jika abs(c – xold) £ e
maka flag = 1 atau jika iter > itmax maka
flag = 2 atau jika tidak maka iter = iter + 1 dan akar
= c;
- Jika flag = 0
ulangi ke nomor 3;
- Selesai.
Sehingga
formula rekursif dari Metode REGULA-FALSI: dapat dituliskan dalam
resume berikut:
Adapun
sifat atau karakteristik metode ini secara umum adalah:
- Memerlukan 2 harga awal (º a0 dan
b0 sedemikian rupa sehingga f(a0)·f(b0) £ 0)
- Konvergensi Superlinier
(º Sedang,
antara linier dan kuadrat)
- Baik digunakan untuk
fungsi yang turunannya tak terdefinisi dengan jelas (diskontinyu)
- Divergen (RTE,
run time error) bila an = bn (º D @ emesin)
- Kriteria penghentian
iterasi : - £e
b n a n dan atau f ( x
n ) £
e
Kelebihan metode False Position : Konvergen terjamin
Kekurangan metode False Position : Proses lambat untuk mencapai konvergen
Metode
Newton Raphson
Dalam
analisis numerik,
metode Newton
Raphson , yang mendapat nama dari
Isaac Newton dan Joseph Raphson, merupakan
metode yang paling dikenal untuk mencari himpunan penyelesaian dari akar fungsi riil. Metode Newton
sering konvergen dengan cepat, terutama bila iterasi dimulai "cukup
dekat" dengan akar yang diinginkan. Namun bila iterasi dimulai jauh dari
akar yang dicari, metode ini dapat meleset tanpa peringatan. Implementasi
metode ini biasanya mendeteksi dan mengatasi kegagalan konvergensi.
Diketahui fungsi ƒ(x) dan turunannya
ƒ '(x), kita memulai dengan tebakan pertama, x0 .
Kemudian nilai x1 adalah sebagai berikut :
Gagasan metode ini adalah sebagai berikut: kita
memulai dengan tebakan awal yang cukup dekat terhadap akar yang sebenarnya,
kemudian fungsi tersebut dihampiri dengan garis singgungnya (yang
dapat dihitung dengan alat-alat kalkulus, dan kita dapat menghitung perpotongan garis ini
dengan sumbu-x (yang dapat dilakukan dengan mudah menggunakan aljabar
dasar). Perpotongan dengan sumbu-x ini biasanya merupakan hampiran yang
lebih baik ke akar fungsi daripada tebakan awal, dan metode ini dapat
diiterasi.
Misalkan ƒ : [a, b] → R
adalah fungsi terturunkan
yang terdefinisi pada selang [a, b] dengan nilai merupakan bilangan riil R.
Rumus untuk menghampiri akar dapat dengan mudah diturunkan. Misalkan kita
memiliki hampiran mutakhir xn. Maka kita dapat menurunkan
hampiran yang lebih baik, xn+1 dengan merujuk pada
diagram di kanan. Kita tahu dari definisi turunan pada suatu titik bahwa itu
adalah kemiringan garis singgung pada titik tersebut, yaitu:
Di sini, f ' melambangkan turunan
fungsi f. Maka dengan aljabar sederhana kita mendapatkan
Kita memulai proses dengan nilai awal sembarang x0.
Metode ini biasanya akan mengerucut pada akar, dengan syarat tebakan awal cukup
dekat pada akar tersebut, dan bahwa ƒ'(x0) ≠ 0.
Kelebihan metode Newton Raphson : Mampu menyelesaikan persamaan yang kompleks, Paling sering digunakan karena cepat mencapai konvergen (tidak membutuhkan waktu lama untuk mencapai konvergen).
Kekurangan metode Newton Raphson : Sulit menghitung fungsi derivative.
Metode Secant
Dalam analisis numerik, metode secant (sekan)
adalah algoritma pencari akar yang menggunakan secara
berturut-turut akar dari garis sekan untuk menghampiri akar dari fungsi matematika f.
Metode secant didefinisikan oleh
hubungan
perulangan
Seperti yang dapat dilihat dari hubungan perulangan tersebut, metode secant mensyaratkan
dua nilai awal,
x0 dan
x1, yang idealnya
dipilih agar dekat dengan akar.
Misalnya diketahui
xn−1 dan
xn,
kita menarik garis melalui titik-titik (
xn−1,
f(
xn−1))
dan (
xn,
f(
xn)), sebagaimana
ditunjukkan gambar di kanan. Perhatikan bahwa garis ini adalah sekan dari
grafik fungsi
f.
Garis tersebut dapat dirumuskan sebagai:
Kita memilih
xn+1 sebagai akar garis ini,
sehingga
xn+1 dipilih sedemikian sehingga
Memecahkan persamaan ini memberikan hubungan perulangan untuk metode secant
Kelebihan metode Secant : Fungsinya kontinyu
Kekurangan metode Secant : Perlu menganalisis turunan.
