GOY'S BLOG: Metode iterative

pada kesempatan kali ini saya akan mencoba sekilas membahas tentang apa itu metode iterative.

Metode iterative merupakan suatu metode penyelesaian suatu persamaan atau persoalan matematika yang menggunakan iterasi dengan nilai awal yang telah ditentukan untuk menghasilkan urutan atau rentetan solusi untuk tiap permasalahan tersebut.
metode iterative ini biasa digunakan untuk menyelesaikan permasalahan yang melibatkan bilangan – bilangan yang sangat besar dan kompleks dimana apabila dikerjakan dengan cara biasa akan sangat menyulitkan. dengan menggunakan metode iterative ini dimaksudkan agar kita dapat menyelesaikan permasalahan tersebut dengan cara yang lebih cepat dan mudah serta membuat kita memahami hal yang kompleks tersebut menjadi lebih simple.
adapun beberapa metode iterative yang ada adalah :
1. metode Jacobi
2. metode Gauss-Seidel
3. metode SOR (Succesive Over Relaxation)
4. Metode False position

5. Metode Newton – Rhapson

6. Metode Secant

7. metode bisection

sebenarnya masih terdapat beberapa lagi metode lainnya, akan tetapi metode lainnya merupakan penjabaran – penjabaran ataupun gabungan dari metode yang telah ada.

1. metode jacobi

Metode Iterasi Jacobi merupakan salah satu bidang analisis numerik yang digunakan untuk menyelesaikan permasalahan persamaan linear dan sering dijumpai dalam berbagai disiplin ilmu. Metode Iterasi Jacobi merupakan salah satu metode tak langsung, yaitu bermula dari suatu hampiran penyelesaian awal dan kemudian berusaha memperbaiki hampiran dalam tak berhingga namun langkah konvergen. Metode Iterasi Jacobi ini digunakan untuk menyelesaikan persamaan linear berukuran besar dan proporsi koefisien nolnya besar.
Metode ini ditemukan oleh matematikawan yang berasal dari Jerman,Carl Gustav Jakob Jacobi. Penemuan ini diperkirakan pada tahun 1800-an.
Kalau kita mengubah dalam Sistem Persamaan Linear, maka dapat ditulis sebagai berikut

$A x = b.\,$

Kemudian, diketahui bahwa $A = D+\left({L + U} \right)$ , di mana $D$ merupakan matriks diagonal, $L$ merupakan matriks segitiga bawah, dan $U$ merupakan matriks segitiga atas.
Kemudian, persamaan di atas dapat diubah menjadi :

$D x+\left({L + U} \right)x = b.$

Kemudian,

$x = D^{ - 1} \left[b -\left({L + U} \right)x \right], $

Jika ditulis dalam aturan iteratif, maka metode Jacobi dapat ditulis sebagai :

$ x^{(k+1)} = D^{ - 1} \left[b-\left({L + U} \right)x^{(k)}\right], $

di mana $k$ merupakan banyaknya iterasi. Jika $x^{(k)}$ menyatakan hampiran ke- $k$ penyelesaian SPL, maka $x^{(0)}$ adalah hampiran awal.

$ x^{(k)}_i = \frac{1}{a_{ii}} \left(b_i -\sum_{j\ne i}a_{ij}x^{(k-1)}_j\right),\, i=1,2,\ldots,n. $

sumber : http://id.wikipedia.org/wiki/Metode_Jacobi
2. metode Gauss-Seidel
Metode Gauss-Seidel digunakan untuk menyelesaikan sistem persamaan linear (SPL) berukuran besar dan proporsi koefisien nolnya besar, seperti sistem-sistem yang banyak ditemukan dalam sistem persamaan diferensial. Metode iterasi Gauss-Seidel dikembangkan dari gagasan metode iterasi pada solusi persamaan tak linier.
Teknik iterasi jarang digunakan untuk menyelesaikan SPL berukuran kecil karena metode-metode langsung seperti metode eliminasi Gauss lebih efisien daripada metode iteratif. Akan tetapi, untuk SPL berukuran besar dengan persentase elemen nol pada matriks koefisien besar, teknik iterasi lebih efisien daripada metode langsung dalam hal penggunaan memori komputer maupun waktu komputasi. Dengan metode iterasi Gauss-Seidel sesatan pembulatan dapat diperkecil karena dapat meneruskan iterasi sampai solusinya seteliti mungkin sesuai dengan batas sesatan yang diperbolehkan.
contoh persoalan metode gaus :
2×1 + 3×2 + 5×3 = 23
3×1 + 4×3 + x3 = 14
6×1 + 7×2 + 2×3 = 26

Formula :

3. metode SOR (Succesive Over Relaxation)
Dalam aljabar linear numerik , metode Succesive Over Relaxation (SOR) adalah varian dari metode Gauss-Seidel untuk memecahkan sistem persamaan linier yang digunakan untuk mecapai konvergensi lebih cepat.
Formula :

$Sebuah \ mathbf x = \ mathbf b$

dimana:

$A = \ begin {bmatrix} a_ {11} a_ {12 &} & \ cdots & a_ {1n} \ \ a_ {21} a_ {22 &} & \ cdots & a_ {2n} \ \ \ vdots & \ vdots & \ ddots & \ vdots \ \ a_ {} n1 n2 & a_ {} & \ cdots & a_ {nn} \ end {bmatrix}, \ qquad \ mathbf {x} = \ begin {bmatrix} x_ {1} \ \ x_2 \ \ \ vdots \ \ x_n \ end {bmatrix}, \ qquad \ mathbf {b} = \ begin {bmatrix} b_ {1} \ \ b_2 \ \ \ vdots \ \ b_n \ end {bmatrix}.$

Maka A dapat diuraikan menjadi diagonal D komponen, dan komponen L dan U:

$A = D + L + U,$

dimana

$D = \ begin {bmatrix} a_ {11} & 0 & \ cdots & 0 \ \ 0 & a_ {22} & \ cdots & 0 \ \ \ vdots & \ vdots & \ ddots & \ vdots \ \ 0 & 0 & \ cdots & a_ {nn} \ end {bmatrix}, \ quad L = \ begin {bmatrix} 0 & 0 & \ cdots & 0 \ \ a_ {21} & 0 & \ cdots & 0 \ \ \ vdots & \ vdots & \ ddots & \ vdots \ \ a_ {} n1 n2 & a_ {} & \ cdots & 0 \ end {bmatrix}, \ quad U = \ begin {bmatrix} a_ {0 & 12 &} \ cdots & a_ {1n } \ \ 0 & 0 & \ cdots & a_ {2n} \ \ \ vdots & \ vdots & \ ddots & \ vdots \ \ 0 & 0 & \ cdots & 0 \ end {bmatrix}.$

Sistem persamaan linier dapat ditulis kembali sebagai:

$(D + \ omega L) \ mathbf {x} = \ omega \ mathbf {b} - [\ omega U + (\ omega-1) D] \ mathbf {x}$

untuk ω konstan> 1.
maka

$\ Mathbf {x} ^ {(k +1)} = (A + \ omega L) ^ {-1} \ besar (\ omega \ mathbf {b} - [\ omega U + (\ omega-1) D] \ mathbf {x} ^ {(k)} \ besar).$

bentuk segitiga (D + ωL), unsur-unsur dari x ^(k +1) dapat dihitung secara berurutan menggunakan subtitusi :

$x ^ {(k +1)} _i = (1 - \ omega) x ^ {(k)} _i + \ frac {\ omega} {a_ {ii}} \ left (B_i - \ sum_ {j> i} a_ {ij} x ^ {(k)} _j - \ sum_ {j <i} a_ {ij} x ^ {(k +1)} _j \ right), \ quad i = 1,2, \ ldots, n .$

kelebihan : metode umum dan mudah dimengerti

kekurangan : keakurasian data dan nilai konvergensi tidak dapat dipastikan

4. Metode False position

Metode False Postion adalah istilah untuk metode pemecahan masalah pada aljabar dan kalkulus. Simplenya, metode ini dimulai dengan mencoba mengeavluasi masalah dengan uji nilai (false) untuk variabel, dan juga mengatur nilai yang sesuai. Dalam aljabat, metode False Position biasanya juga mengarahkan kepada basic metode trial dan error pemecahan persamaan, dengan uji nilai subtitusi untuk variabel dalam persamaan. Denga persamaan sebagai berikut :

Kelebihan metode ini : konvergen terjamin

Kekurangan metode ini : juga lambat dalam proses konvergen

5. Metode Newton – Rhapson

Dalam analisis numerik, metode Newton ( merupakan metode yang paling dikenal untuk mencari hampiran terhadap 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 . Hampiran yang lebih baik x1 adalah

$x_{1} = x_0 - \frac{f(x_0)}{f'(x_0)}.\,\!$

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.

6. Metode Secant
Sama seperti metode newton-raphson, metode secant adalah salah satu dari metode numerik untuk mencari solusi persamaan dari sebuah fungsi.
Metoda secant merupakan salah satu metoda yang digunakan untuk mencari nilai akar dari persamaan y=f(x). Metoda ini dapat dipahami dengan menggunakan bantuan model segitiga dalam penyelesainnya seperti berikut, dengan X0 dan X1 merupakan batas yang dijadikan acuan awal untuk mencari nilai X yang sebenarnya :

Misalkan dengan menggunakan gambar ilustrasi di atas kita dapat mengambil persamaan dari sifat segitiga sebangun sebagai berikut :

dimana :
BD = f(x1)
BA = x1-x0
CD = f(x1)
CE = x1-x2
Dan jika dirubah, rumusnya akan menjadi :

Dari rumus di atas bisa kita lihat bahwa yang dicari adalah Xn+1,( Xn+1) ini merupakan nilai X yang dicari sebagai pendekatan terhadap nilai X yang sebenarnya seperti untuk nilai X2 kemudian X3 pada gambar dibawah, semakin lama nilai Xn+1 akan mendekati titik X yang sebenarnya.

Jika perhitungan di atas terus dilakukan maka pada akhirnya akan di dapat nilai X yang paling mendekati dengan jumlah eror dan iterasi yang bisa kita tentukan sesuai dengan flowchart algoritma di bawah.

gambar dibawah merupakan grafik yang terbentuk dari persamaan Y = f(x), maka untuk mencari titik X pada titik Y=0 rumus secant yang telah kita turunkan tadi bisa langsung digunakan disini.

jika kita melihat grafik diatas kita dapat memperkirakan bahwa X yang akan kita cari berada di antara titik X=0,8 dan X=0,9. maka dua titik ini bisa dijadikan batas untuk mencari nilai X yang kita cari.

setelah melakukan iterasi sebanyak tiga kali maka kita akhirnya menemukan nilai X = 0882543 yang merupakan pendekatan terhadap akar dari Y=f(x).

7. metode bisection

Metode Bisection atau disebut juga dengan metode bagi dua merupakan salah satu jenis metode pencarian instrumental dimana selang/range selalu dibagi dua atau membagi range menjadi 2 bagian.Ide awal metode ini adalah metode table, dimana suatu area dibagi menjadi N bagian. Pada Metode Bisection ini jika suatu fungsi berubah tanda pada suatu selang, maka nilai fungsi dihitung pada titik tengah, kemudian lokasi akar ditentukan sebagai titik tengah selang bagian terjadinya perubahan tanda.
>>Prinsip dari Metode Bisection adalah :
– membagi range menjadi 2 bagian, dari dua bagian ini dipilih bagian mana yang mengandung akar dan membuang bagian yang tidak mengandung akar. Hal ini dilakukan berulang -ulang hingga diperoleh akar persamaan. Berikut adalah langkah-langkah dalam menyelesaikan Metode Bisection (metode bagi dua), yaitu :
– Langkah 1 : Pilih a sebagai batas bawah dan b sebagai batas atas untuk taksiran akar sehingga terjadi perubahan tanda fungsi dalam selang interval.
– Langkah 2 : Taksiran nilai akar baru yaitu c diperoleh dari :
Atau perumusan akar dengan
– Langkah 3 : Menentukan daerah yang berisi akar fungsi:
* Jika |f(c)| ≤ toleransi, maka harga c adalah harga x yang dicari, bila tidak dilanjutkan ke tahap 4.
– Langkah 4 :
 Jika f(c) > 0, maka a baru = a dan b baru = c, sehingga daerah akar fungsi a < x < c
 Jika f(c) < 0, maka a baru = c dan b baru = b, sehingga daerah akar fungsi c < x < b. Kmudian kembali ke tahap 2 tadi.

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

sumber : https://randywicaksono.wordpress.com/2012/03/29/metode-iterative/

GOY'S BLOG

Kamis, 02 Maret 2017

Metode iterative

pada kesempatan kali ini saya akan mencoba sekilas membahas tentang apa itu metode iterative.

Tidak ada komentar:

Posting Komentar