Metoda Iterativ

Dalam komputasi teknik di bab 3 terdapat sebuah sebuah metode iteratif adalah prosedur matematis yang menghasilkan urutan untuk meningkatkan prakiraan solusi masalah. Sebuah implementasi khusus dari metode iteratif, termasuk kriteria penghentian, adalah suatu algoritma dari metode iteratif. Sebuah metode iteratif disebut konvergen jika konvergen urutan yang sesuai untuk perkiraan awal yang diberikan. 

Misalnya dalam permasalahan untuk menemukan akar dari persamaan, sebuah metode iteratif menggunakan teknik  tebakan awal untuk menghasilkan aproksimasi untuk solusi. Sebaliknya, metode langsung mencoba memecahkan masalah dengan urutan berhingga operasi. Dengan tidak adanya kesalahan pembulatan, metode langsung akan memberikan solusi yang tepat (seperti memecahkan sistem persamaan linear Ax = b dengan eliminasi Gauss). Metode iteratif sering satu-satunya pilihan untuk persamaan nonlinier. Namun, metode iteratif sering berguna bahkan untuk masalah linear melibatkan sejumlah besar variabel

Berikut adalah macam-macam metode iterative yang biasa digunakan :

1. Metode bisection
2. Metode False Position
3. Metode Newton-Raphson
4. Metode Secant

Berikut akan dijelaskan masing-masing metode iterative tersebut 

1. Metoda Bisection

Metode biseksi ini adalah metode untuk mencari akar-akar dari sebuah fungsi dengan cara menghitung nilai fungsi f(x) dari 2 nilai X : (X1,X2) yang diberikan.Tahap pertama proses adalah menetapkan nilai sembarang a dan b sebagai batas segmen nilai fungsi yang dicari. Batasan a dan b memberikan harga bagi fungsi f(x) untuk x = a dan x = b. Langkah selanjutnya adalah memeriksa apakah f(a) × f(b) < >

Dengan rumusan m = (a+b)/2, diperiksa apakah nilai mutlak f(m) < >-6 (batas simpangan kesalahan).  Jika benar, nilai x = m adalah solusi yang dicari. Jika tidak terpenuhi, ditetapkan batasan baru dengan mengganti nilai b = m apabila f(a)*f(m) < a =" m"> 0; proses menemukan m baru dilakukan seperti prosedur yang telah dijelaskan. 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 

(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)

1. Tebak harga interval [a,b]; tentukan e; 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) £ e 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.  

Kelebihan metode ini : Sangat Simple, konvergen terjamin
Kekurangan metode ini : proses converge lamban.

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, x₀ dan x₁, yang idealnya dipilih agar dekat dengan akar.
Misalnya diketahui x_n−1 dan x_n, kita menarik garis melalui titik-titik (x_n−1, f(x_n−1)) dan (x_n, f(x_n)), sebagaimana ditunjukkan gambar di kanan. Perhatikan bahwa garis ini adalah sekan dari grafik fungsi f.
Garis tersebut dapat dirumuskan sebagai:

Kita memilih x_n+1 sebagai akar garis ini, sehingga x_n+1 dipilih sedemikian sehingga

Memecahkan persamaan ini memberikan hubungan perulangan untuk metode secant

Kelebihan metode ini : fungsinya kontinyu

Kekurangan metode ini : perlu menganalisis turunan.

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, x₀ . Kemudian nilai x₁ 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 x_n. Maka kita dapat menurunkan hampiran yang lebih baik, x_n+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 x₀. Metode ini biasanya akan mengerucut pada akar, dengan syarat tebakan awal cukup dekat pada akar tersebut, dan bahwa ƒ'(x₀) ≠ 0.

Kelebihan metode ini : bisa menyelesaikan persamaan yang kompleks. dan paling efisien

Kekurangan metode ini : Sulit menghitung fungsi derivative, sering melakukan iterasi.

 

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)

1. Tebak harga interval [a,b]; tentukan e; dan itmax
2. Set xold = 2*b-a; iter = 0; flag = 0;
3. Tentukan atau hitung akar = c = b – f(b) [(b – a)/(f(b) – f(a)); iter = iter + 1;
4. Jika f(b)·f(c) £ 0 maka a = c jika tidak b = c;
5. 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;
6. Jika flag = 0 ulangi ke nomor 3;
7. 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 ini : konvergen terjamin

Kekurangan metode ini : juga lambat dalam proses konvergen