ITERASI JACOBI PDF

Preview

Summary

Angga Debby Frayudha / Educational Technology 1 (2) (2016) Educational Technology 1 (2) (2016) Educational Technology http://journal.unnes.ac.id/sju/index.php/eduman ITERASI JACOBI Angga Debby Frayudha Program Pascasarjana, Universitas Negeri Semarang, Indonesia Info Artikel Abstrak Sejarah Artikel:...

Description

Angga Debby Frayudha / Educational Technology 1 (2) (2016)

Educational Technology 1 (2) (2016)

Educational Technology http://journal.unnes.ac.id/sju/index.php/eduman

ITERASI JACOBI

Angga Debby Frayudha Program Pascasarjana, Universitas Negeri Semarang, Indonesia

Info Artikel

Abstrak

Sejarah Artikel: Diterima April 2016 Disetujui April 2016 Dipublikasikan Mei 2016

Persoalan yang melibatkan model matematika banyak muncul dalam berbagai

Keywords:Leaders hip, compensation, motivation, employee performance.

rumit yang terkadang tidak dapat diselesaikan dengan rumus-rumus aljabar yang

disiplin ilmu pengetahuan, seperti dalam bidang fisika, kimia, ekonomi, atau pada persoalan rekayasa. Seringkali model matematika tersebut muncul dalam bentuk yang

sudah baku. Solusi SPL secara numeris umumnya selalu (harus) lebih efisien dan cepat dibandingkan dengan metode-metode analitis, seperti metode Cramer. Namun demikian, solusi numerik ini secara teknis adakalanya juga berkendala, karena: (1) ada beberapa persamaan yang mendekati kombinasi linier, akibat adanya “round off error” dari mesin penghitung pada, (2) suatu tahap perhitungan adanya akumulasi “round off error” pada proses komputasi akan berakibat domain bilangan nyata (fixed point) dalam perhitungan akan terlampaui (overflow), biasanya akibat dari jumlah persamaan yang terlalu besar.

Abstract Issues involving mathematical models have appeared in a variety of disciplines, such as in the fields of physics, chemistry, economics, or engineering issues. The mathematical models often appear in intricate shapes that sometimes can not be solved by algebraic formulas is standard. SPL solutions numerically generally always (have to) be more efficient and faster than analytical methods, such as method of Cramer. However, the numerical solution is technically sometimes also berkendala, because: (1) there are some similarities approaching a linear combination, due to "round off error" of mechanical calculating machines, (2) a stage of calculation of the accumulation of "round off error" the computing process will result in domain real numbers (fixed point) in the calculation will be exceeded (overflow), usually as a result of a number of equations that are too large.

© 2016 Universitas Negeri Semarang Alamat korespondensi: Kampus Unnes Bendan Ngisor, Semarang, 50233 Email : [email protected] Angga Debby Frayudha

ISSN 2252-7001

Angga Debby Frayudha / Educational Technology 1 (2) (2016)

prinsipnya merupakan solusi SPL dengan bentuk matrik

PENDAHULUAN

pita (satu diagonal bawah, satu diagonal utama, dan satu model diagonal atas) pada matriks A. matematika banyak muncul dalam berbagai disiplin Persoalan

yang

melibatkan

ilmu pengetahuan, seperti dalam bidang fisika, kimia,

2. Metode Tak-Langsung (Metode Iteratif)

ekonomi, atau pada persoalan rekayasa. Seringkali

a. Metode Jacobi, prinsipnya: merupakan metode model matematika tersebut muncul dalam bentuk yang iteratif yang melakuakn perbaharuan nilai x yang rumit yang terkadang tidak dapat diselesaikan dengan diperoleh tiap iterasi (mirip metode substitusi berurutan, rumus-rumus aljabar yang sudah baku.

successive substitution),

Solusi SPL secara numeris umumnya selalu b. Metode Gauss-Seidel, prinsipnya: mirip (harus) lebih efisien dan cepat dibandingkan dengan metode Jacobi, namun melibatkan perhitungan implisit, metode-metode analitis, seperti metode Cramer. c. Metode Successive Over Relaxation (SOR), Namun demikian, solusi numerik ini secara teknis prinsipnya: merupakan perbaikan secara langsung dari adakalanya juga berkendala, karena: Metode Gauss- Seidel dengan cara menggunakan faktor (1) ada beberapa persamaan yang mendekati relaksasi (faktor pembobot) pada setiap tahap/proses kombinasi linier, akibat adanya “round off error” dari iterasi. mesin penghitung pada, (2) suatu tahap perhitungan

Metode-metode tak-langsung seperti di atas pada

adanya akumulasi “round off error” pada proses umunya sangat tidak efisien dan ‘time consuming’ komputasi akan berakibat domain bilangan nyata (memerlukan CPU- time) yang jauh lebih besar dari (fixed point) dalam perhitungan akan terlampaui metode langsung. (overflow), biasanya akibat dari jumlah persamaan Metode Eliminasi Gauss, metode Dekomposisi yang terlalu besar. LU dan Metode Iterasi Jacobi merupakan metode yang METODE PENELITIAN dapat dijadikan sebagai alternatif untuk menyelesaikan Metode-metode solusi numerik yang banyak model matematika. Metode Eliminasi Gauss mereduksi dipakai, dapat diklasifikasikan sebagai: matriks koefisien A ke dalam bentuk matriks segitiga, 1. Metode Langsung

dan nilai-nilai variabel diperoleh dengan teknik Gauss substitusi. Pada metode Dekomposisi LU, matriks A (EGAUSS), prinsipnya: merupakan operasi eliminasi difaktorkan menjadi matriks L dan matriks U, dimana a.

Metode

Langsung

Eliminasi

dan substitusi variabel-variabelnya sedemikian rupa dimensi atau ukuran matriks L dan U harus sama sehingga dapat terbentuk matriks segitiga atas, dan dengan dimensi matriks A. akhirnya solusinya diselesaikan menggunakan teknik

Pada

metode

iterasi

Jacobi,

penyelesaian

substitusi balik (backsubstitution),

dilakukan secara iterasi, dimana proses iterasi dilakukan b. Metode Eliminasi Gauss ini. Eliminasi sampai dicapai suatu nilai yang konvergen dengan Gauss-Jordan (EGJ), prinsipnya: mirip sekali dengan toleransi yang diberikan. Dari hasil pengujian dapat metode EG, namun dalam metode ini jumlah operasi diketahui bahwa metode Iterasi Jacobi memiliki hasil numerik yang dilakukan jauh lebih besar, karena ketelitian yang lebih baik dan waktu komputasi yang matriks A mengalami inversi terlebih dahulu untuk lebih cepat dari metode Eliminasi Gauss dan metode mendapatkan matriks identitas (I). Karena kendala Dekomposisi LU. tersebut, maka metode ini sangat jarang dipakai, Penggunaan pendekatan dengan pemrograman namun sangat bermanfaat untuk menginversikan MATLAB, salah satu software komputer yang dapat matriks, digunakan untuk memberikan solusi komputasi numerik. c. Dekomposisi LU (DECOLU), prinsipnya: Karena metode – metode numerik dengan bahasa melakukan dekomposisi matriks A terlebih dahulu pemrograman yang sederhana, namun dapat sehingga dapat terbentuk matriks-matrik segitiga atas menyelesaikan permasalahan yang dihadapi oleh mereka dan bawah, kemudian secara mudah dapat melakukan yang bergerak dalam bidang matematika maupun substitusi balik (backsubstitution) untuk berbagai aplikasi matematika. vektor VRK (vektor ruas kanan). d. Solusi sistem TRIDIAGONAL (S3DIAG),

Angga Debby Frayudha / Educational Technology 1 (2) (2016)

C. Flow Chart Iterasi Jacobi

HASIL PEMBAHASAN A. Iterasi Jacobi Metode ini merupakan suatu teknik penyelesaian SPL berukuran n x n, AX = b, secara iteratif. Proses penyelesaian dimulai dengan suatu hampiran awal terhadap penyelesaian, X0, kemudian membentuk suatu serangkaian vector X1, X2, … yang konvergen ke X. Teknik iteratif jarang digunakan untuk menyelesaikan SPL berukuran kecil karena metode-metode langsung seperti metode eliminasi Gauss lebih efisien dari pada metode iteratif. Akan tetapi, untuk SPL berukuran besar dengan persentase elemen nol pada matriks koefisien besar, teknik iteratif lebih efisien daripada metode langsung dalam hal penggunaan memori komputer maupun waktu komputasi. Metode iterasi Jacobi, prinsipnya: merupakan metode iteratif yang melakuakn perbaharuan nilai x yang diperoleh tiap iterasi (mirip metode substitusi berurutan, successive substitution). B.

START AX = b

Input A, b, X0, T,

[X, g, H]= jacobi(A,b,X0,T,

xi =

Algoritma Iterasi Jacobi Untuk menyelesaikan system persamaan linier AX = b dengan A adalah matriks koefisien n x n, b vector konstan n x 1, dan X vektor n x 1 yang perlu dicari. INPUT : n, A, b, dan Himpunan awal Y = (y1 y2 y3…yn)T, batas toleransi T, dan maksimum iterasi N. OUTPUT: X = (x1 x2 x3 ..xn)T, atau pesan “ gagal “. LANGKAH – LANGKAH : 1. set penghitung iterasi ke =1 2. WHILE k ≤ n DO (a) FOR i = 1, 2, 3, ..., n, hitung

xi =

bi − ∑ j ≠i a ij y j aii

(b) Set X = (x1 x2 x3 ..xn)T (c) IF

3.

X −Y

< T THEN STOP

(d) Tambahan penghitung iterasi, k =k+1 (e) FOR i = 1, 2, 3, ..., n, Set yi = xi (f) set Y = (y1 y2 y3 ..yn)T STOP

bi − ∑ j ≠i a ij y aii

xi = ( x1 x2 x3 …xn)

STOP D. Iterasi Jacobi dengan Menggunaan Matlab 7 Jika x(k)menyatakan hampiran ke k penyelesaian SPL , AX = b, dengan x(0)adalah hampiran awal, maka metode iterasi Jacobi dapat dinyatakan sebagai berikut :

xi

(k )

=

1 aii

   bi − ∑ aij x j ( k −1)  ,   j ≠i  

i = 1,

2, 3, ..., n ; k = 1, 2, 3, .. Dalam bentuk matriks, rumus iterasi dapat dinyatakan sebagai X(k) = D-1(b-(L+U)X(k-1)), Dengan A = L + D + U ( L matriks segitiga bawah, D matriks diagonal, U Matriks segitiga atas). Berikut adalah gambaran bagaimana penggunaan metode iterasi Jacobi dengan sebuah contoh. Misalkan kita ingin menyelesaikan SPL. 10x1 – x2 + x3 = 6 -x1 + 11x2 – x3 + 3x4 = 25 2x1 – x2 + 10x3 – x4 = - 11 3x2 – x3 + 8x4 = 15 Mula – mulakita nyatakan setiap variabel dalam ketiga variabel yang lainnya 1. Nyatakan x1 dari persamaan (P1) dalam x2, x3, dan x4, 2. Nyatakan x2 dari persamaan (P2) dalam x1, x3, dan x4, 3. Nyatakan x3 dari persamaan (P3) dalam x1, x3, dan x4, 4. Nyatakan x4 dari persamaan (P4) dalam x1, x2, dan x3. Hasilnya adalah SPL

x1 =

x 2 x3 3 − + 10 5 5

Angga Debby Frayudha / Educational Technology 1 (2) (2016)

x1 x3 3 x 4 25 + − + 11 11 11 11 − x1 x 2 x 4 11 x3 = + + − 5 10 10 10 − 3 x 2 x3 15 x4 = + + 8 8 8 x2 =

Layar Editor MATLAB 7

Misalkan kita pilih hapiran penyelesaian awal (0 0 0 0)T, maka hampiran pertama terhadap penyelesaian SPL tersebut adalah

3 = 0 .6 = 1 5 25 x2 = = 2.2727 = 2 11 11 x3 = = −1.1 = -1 10 15 x4 = = 1.8750 = 2 8

x1 =

Sekarang dengan menggunakan nilai – nilai ini pada ruas kanan persamaan (P5) – (P8), kita dapat menghitung hampiran kedua. Proses ini dapat diulang-ulang sampai keakuratan hampiran yang diinginkan tercapai. Berikut adalah hasil proses iterasi dengan menggunakan komputer. No 1 2 3 4 5 6 7 8

x1 0.6 1.04727 0.932636 1.0152 0.988991 1.0032 0.998128 1.00063

x2 2.27273 1.71591 2.05331 1.9537 2.01141 1.99224 2.00231 1.99867

x3 -1.1 -0.805227 -1.04934 -0.968109 -1.01029 -0.994522 -1.00197 -0.999036

x4 1.875 0.885227 1.13088 0.973843 1.02135 0.994434 1.00359 0.998888

Setelah iterasi ke-8 diperoleh hampiran penyelesaian x = (1.00063 1.99867 -0.999036 0.998888)T bandingkan dengan penyelesaian eksaknya, yakni x = (1 2 -1 1)T. Menyelesaikan contoh SPL berikut ini dengan menggunakan metode iterasi Jacobi. 2x1 – x2 + 10x3 = -11 3x2 – x3 + 8x4 = -11 10x1 – x2 + 2x3 =6 -x1 + 11x2 – x3+ 3x4 = 25

E. Penulisan Logaritma dalam Layar Editor MATLAB 7 function [X,g,H]= jacobi(A,b,X0,T,N) H = X0'; n = length(b); X1 = X0; for k=1:N, for i = 1:n, S = b(i)-A(i,[1:i-1,i+1:n])*X0([1:i1,i+1:n]); X1(i)=S/A(i,i); end g = abs(X1-X0); err = norm(g); relerr = err/(norm(X1)+ eps); X0 = X1; H = [H;X0']; if (err A=[2 -1 10 0;0 3 -1 8;10 -1 2 0;-1 11 -1 3] A= 2 -1 10 0 0 3 -1 8 10 -1 2 0 -1 11 -1 3 >> b=[-11;-11;6;25] b= -11 -11 6 25 >> X0=[0;0;0;0] X0 = 0 0 0 0 >> T=.00001 T= 1.0000e-005 >> N=25 N= 25 >> [X,g,H]=jacobi(A,b,X0,T,N) X= 1.0e+017* -4.1950 0.5698 2.1380 0.0451 g= 1.0e+017* 3.7699 0.5442 1.2965 0.1535 H= 1.0e+017* 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000

Angga Debby Frayudha / Educational Technology 1 (2) (2016)

0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 0 . 0000 -0 . 0007 0 . 0000 0 . 0013 -0 . 0002 -0 . 0066 0 . 0009 0 . 0036 0 . 0000 -0 . 0173 0 . 0011 0 . 0333 -0 . 0042 -0 . 1661 0 . 0224 0 . 0873 0 . 0013 -0 . 4251 0 . 0256 0 . 8415 -0 . 1085 -4 . 0000 0 . 5698 2 . 1380 0 . 0451 Dari hasil diatas, metode Jacobi belum konvergen setelah melakukan iterasi. Untuk mengetahui penyelesaian SPL kita, selanjutnya gunakan metode langsung dengan menggunakan invers matriks A. MATLAB memberikan penyelesaian sebagai berikut. >> X=inv(A)*b X= 1.1039 2.9965 -1.0211 -2.6263

0.1511 H= -2 . 0000 1 . 0000 3 . 0000 -1 . 0000 1 . 1000 2 . 6364 -1 . 6000 -2 . 3750 1 . 9836 2 . 6023 -1 . 8564 -2 . 4386 1 . 0315 2 . 9494 -1 . 0365 -2 . 4579 1 . 1022 2 . 9426 -1 . 0114 -2 . 6106 1 . 1065 2 . 9930 -1 . 0262 -2 . 6049 1 . 1045 2 . 9895 -1 . 0200 -2 . 6256 1 . 1030 2 . 9965 -1 . 0220 -2 . 6236 1 . 1040 2 . 9856 -1 . 0209 -2 . 6264 1 . 1037 2 . 9966 -1 . 0212 -2 . 6260 1 . 1039 2 . 9964 -1 . 0211 -2 . 6264 1 . 1039 2 . 9965 -1 . 0211 -2 . 6263 1 . 1039 2 . 9965 -1 . 0211 -2 . 6263 1 . 1039 2 . 9965 -1 . 0211 -2 . 6263 Iterasi Jacobi konvergen (dengan menggunakan batas toleransi 0.0001) setelah iterasi ke-13. Penyelesaian yang diberikan persis sama dengan yang dihasilkan dengan metode langsung. Hampiran penyelesaian SPL kita adalah X = (1.1039 2.9965 -1.0211 2.6263)T. Layar MATLAB 7 (command window)

Apakah metode jacobi tidak dapat menghasilkan penyelesaian tersebut? Dengan mengubah susunan SPL, yakni persamaan pertama dan kedua dipindah menjadi persamaan ketiga dan keempat, metode Jacobi ternyata berhasil memberikan penyelesaian tersebut, sebagaimana terlihat pada hasil keluaran MATLAB berikut. >> A=[10 -1 2 0;-1 11 -1 3;2 -1 10 0;0 3 -1 8] A= 10 -1 2 0 -1 11 -1 3 2 -1 10 0 0 3 -1 8 >> b=[6;25;-11;-11] b= 6 25 -11 -11 >> X0=[-2;1;3;-1] X0 = -2 1 3 -1 >> [X,g,H]=jacobi(A,b,X0,T,N) X= 1.1039 2.9965 -1.0211 -2.6263 g= 0.0795 0.2004 0.0797

Dari contoh di atas bahwa urutan persamaan di dalam suatu SPL sangat berpengaruh terhadap penampilan metode iterasi Jacobi. Kalau kita amati lebih lanjut contoh di atas, kekonvergenan iterasi Jacobi pada strategi kedua dikarenakan kita telah mengubah susunan SPL sedemikian hingga elemen-elemen aii merupakan elemen-elemen terbesar pada setiap baris. Dengan kata lain, apabila matriks koefisien A merupakan matriks dominan secara diagonal, maka metode iterasi Jacobi akan konvergen. Suatu matrik A berukuran n x n dikatakan dominan secara diagonal apabila

| a ii |>| a i ,1 | +...+ | ai ,i −1 | + | ai ,i +1 | +...+ | ai ,n | untuk i = 1, 2, 3, ..., n.

Angga Debby Frayudha / Educational Technology 1 (2) (2016)

SIMPULAN Dari

pembahasan

di

atas

kita

dapat

mengambil kesimpulan bahwa. 1. Urutan persamaan di dalam suatu SPL sangat berpengaruh terhadap penampilan metode iterasi Jacobi. 2.

Dengan

menggunakan

pemrograman

MATLAB 7 dapat membantu pemrograman dalam dalam metode numeric khususnya metode iterasi Jacobi.

SARAN 1.

Dari hasil pembahasan disarankan untuk.

2.

1. Menggunakan metode iterasi Jacobi lebih efektif untuk memecahkan masalah numerik dalam SPL berukuran besar.

3.

2. Menggunakan program MATLAB 7 for Windows

dalam

membantu

metode iterasi Jacobi.

DAFTAR PUSTAKA .

pengolahan

Angga Debby Frayudha / Educational Technology 1 (2) (2016)...