iterasi-jacobi

5/12/2018 iterasi-jacobi - slidepdf.com

http://slidepdf.com/reader/full/iterasi-jacobi-55a35cfe88c0e 1/11

1

PENDAHULUAN

A. Latar Belakang

Persoalan yang melibatkan model matematika banyak muncul dalam

berbagai disiplin ilmu pengetahuan, seperti dalam bidang f isika, kimia, ekonomi,

atau pada persoalan rekayasa. Seringkali model matematika tersebut muncul dalam bentuk yang r umit yang terkadang tidak dapat diselesaikan dengan r umus-r umus aljabar yang sudah bak u.

Solusi SPL secara numeris umumnya selalu (har us) lebih ef isien 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 kom binasi linier, akibat adanya ³round off error ́ dari mesin penghitung pada, (2) suatu tahap perhitungan adanya

ak umulasi ³round off error ́ pada proses kom putasi akan berakibat domain bilangan nyata ( fixed point ) dalam perhitungan akan terlam paui (overflow),

biasanya akibat dari jumlah persamaan yang terlalu besar. Metode-metode solusi numerik yang banyak dipakai, dapat diklasif ikasikan

sebagai:

1. Metode Langsung

a. Metode Langsung Eliminasi Gauss (EGAUSS), prinsipnya: mer u pakan

operasi eliminasi dan su bstitusi variabel-variabelnya sedemikian r u pa sehingga dapat terbentuk matriks segitiga atas, dan akhirnya solusinya

diselesaikan menggunakan teknik su bstitusi balik (backsub stitution), b. Metode Eliminasi Gauss ini. Eliminasi Gauss-Jordan (EGJ), prinsipnya:

mirip sekali dengan metode EG, namun dalam metode ini jumlah operasi

numerik yang dilak ukan jauh lebih besar, karena matriks A mengalami inversi terlebih dahulu untuk mendapatkan matriks identitas ( I ). K arena kendala tersebut, maka metode ini sangat jarang dipakai, namun sangat

ber manf aat untuk menginversikan matriks, c. Dekomposisi LU (DECOLU), prinsipnya: melak ukan dekom posisi matriks

A terlebih dahulu sehingga dapat terbentuk matriks-matrik segitiga atas dan bawah, kemudian secara mudah dapat melak ukan su bstitusi balik

(backsub stitution) untuk berbagai vektor VRK (vektor r uas kanan). d. Solusi sistem TRIDIAGONAL (S3DIAG), prinsipnya mer u pakan solusi

SPL dengan bentuk matrik pita (satu diagonal bawah, satu diagonal utama, dan satu diagonal atas) pada matriks A.

2. Metode Tak-Langsung (Metode Iteratif)

a. Metode Jacobi, prinsipnya: mer u pakan metode iteratif yang melak uakn perbahar uan nilai x yang diperoleh tiap iterasi (mirip metode su bstitusi

ber ur utan, successive sub stitution), b. Metode Gauss-Seidel, prinsipnya: mirip metode Jacobi, namun melibatkan

perhitungan im plisit,



2

c. Metode Successive Over Relaxation (SOR), prinsipnya: mer u pakan perbaikan secara langsung dari Metode Gauss- Seidel dengan cara

menggunakan f aktor relaksasi (f aktor pem bobot) pada setiap tahap/proses iterasi.

Metode-metode tak-langsung seperti di atas pada umunya sangat tidak ef isien dan µtime consuming¶ (memerlukan CPU- time) yang jauh lebih besar dari metode langsung.

Metode Eliminasi Gauss, metode Dekom posisi LU dan Metode Iterasi Jacobi

mer u pakan metode yang dapat dijadikan sebagai alternatif untuk menyelesaikan model matematika. Metode Eliminasi Gauss mereduksi matriks koefisien A ke

dalam bentuk matriks segitiga, dan nilai-nilai variabel diperoleh dengan teknik sub stitusi. Pada metode Dekom posisi LU, matriks A dif aktorkan menjadi matriks

L dan matriks U, dimana dimensi atau uk uran matriks L dan U har us sama dengan dimensi matriks A.

Pada metode iterasi Jacobi, penyelesaian dilak ukan secara iterasi, dimana

proses iterasi dilak ukan sam pai dicapai suatu nilai yang konvergen dengan toleransi yang diberikan. Dari hasil pengu jian dapat diketahui bahwa metode

Iterasi Jacobi memiliki hasil ketelitian yang lebih baik dan waktu kom putasi yang lebih cepat dari metode Eliminasi Gauss dan metode Dekom posisi LU.

Penggunaan pendekatan dengan pemrograman MATLAB, salah satu

software kom puter yang dapat digunakan untuk mem berikan solusi kom putasi numerik. K arena metode ± metode numerik dengan bahasa pemrograman yang

sederhana, namun dapat menyelesaikan per masalahan yang dihadapi oleh mereka

yang bergerak dalam bidang matematika mau pun aplikasi matematika.

B. Rumusan Masalah

Dari uraian di atas, dapat dir umuskan per masalahannya. 1. A pakah ur utan persamaan di dalam suatu SPL berpengar uh terhadap

penam pilan metode iterasi Jacobi? 2. A pakah program MATLAB 7 dapat digunakan sebagai solusi pemrograman

dalam metode numerik khususnya metode iterasi Jacobi?

C. Batasan Masalah

Dalam makalah ini akan mem bahas tentang penggunaan metode iterasi

Jacob

i dalam penyelesaian Sistem Persamaan Linear (SPL) ber uk uran besar dengan persentase elemen nol pada matriks koef isien besar dengan pemrograman

MATLAB 7 for Windows.



3

D. Tujuan

Tu juan penulisan makalah sebagai berik ut.

1. Mem berikan solusi dalam mem peroleh ur utan persamaan di dalam suatuSPL dengan menggunakan metode iterasi Jacobi.

2. Penggunaan MATLAB 7 untuk mem bantu menyelesaikan pemrograman

dalam penyelesaian Sistem Persamaan Linear (SPL) dengan metode iterasi Jacobi.

E. Manfaat

Dapat diam bil manf aatnya sebagia berik ut.

1. Dapat digunakan sebagai solusi dalam mem peroleh ur utan persamaan di dalam suatu SPL ber uk uran besar dengan menggunakan metode iterasi

Jacobi.2. Mem beri kemudahan dalam menyelesaikan Sistem Persamaan Linear (SPL)

ber uk uran besar dengan metode iterasi Jacobi dengan pemrograman MATLAB 7 for Windows.



4

PEMBAHASAN

A. Iterasi Jacobi

Metode ini mer u pakan suatu teknik penyelesaian SPL ber uk uran n x n, AX =b, secara iteratif . Proses penyelesaian dimulai dengan suatu ham piran awal terhadap penyelesaian, X 0, kemudian mem bentuk suatu serangkaian vector X 1, X 2,

« yang konvergen ke X .

Teknik iteratif jarang digunakan untuk menyelesaikan SPL ber uk uran kecil karena metode-metode langsung seperti metode eliminasi Gauss lebih ef isien dari

pada metode iteratif . Akan tetapi, untuk SPL ber uk uran besar dengan persentase elemen nol pada matriks koef isien besar, teknik iteratif lebih ef isien daripada

metode langsung dalam hal penggunaan memori kom puter mau pun waktukom putasi. Metode iterasi Jacobi, prinsipnya: mer u pakan metode iteratif yang

melak uakn perbahar uan nilai x yang diperoleh tiap iterasi (mirip metode su bstitusi ber ur utan, successive sub stitution).

B. Algoritma Iterasi Jacobi

Untuk menyelesaikan system persamaan linier AX = b dengan A adalah matriks koef isien n x n, b vector konstan n x 1, dan X vektor n x 1 yang perlu

dicari.

INPUT : n, A, b, dan Him punan 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 =12. WHILE k n DO

(a) FOR i = 1, 2, 3, ..., n, hitung ii

i j jiji

ia

yab

x§ {

!

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

(c) IF Y X < T THEN STOP

(d) Tam bahan penghitung iterasi, k = k + 1

(e) FOR i = 1, 2, 3, ..., n, Set yi = xi

(f ) set Y = (y1 y2 y3 ..yn)T

3. STOP



5

C. Flow Chart Iterasi Jacobi

D. Iterasi Jacobi dengan Menggunaan Matlab 7

Jika x(k)

menyatakan ham piran ke k penyelesaian SPL , AX = b , dengan x(0)adalah ham piran awal, maka metode iterasi Jacobi dapat dinyatakan sebagai

berik ut :

¹¹ º

¸©©ª

¨! §

{

i j

k

jiji

ii

k

i xaba

x)1()( 1

, i = 1, 2, 3, ..., n ; k = 1, 2, 3, ..

Dalam bentuk matriks, r umus 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).

Berik ut adalah gam baran bagaimana penggunaan metode iterasi Jacobi dengan sebuah contoh. Misalkan kita ingin menyelesaikan SPL.

10x1 ± x2 + x3 = 6

-x1 + 11x2 ± x3 + 3x4 = 252x1 ± 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,

START

STOP

AX = b

ii

i j jiji

ia

yab x § {!

Input A, b, X0, T, N

xi = ( x1 x2 x3 «xn)

[X, g, H]=acobi A,b,X0,T, N



6

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

5

3

510

321 !

x x x

11

25

11

3

1111

4312 !

x x x x

10

11

10105

421

3

!

x x x x

8

15

88

3 32

4

!

x x x

Misalkan kita pilih hapiran penyelesaian awal (0 0 0 0)T

, maka ham piran

pertama terhadap penyelesaian SPL tersebut adalah

6.05

3

1

!! x = 1

2727.211

252 !! x = 2

1.110

113 !! x = -1

8750.18

154 !! x = 2

Sekarang dengan menggunakan nilai ± nilai ini pada r uas kanan persamaan

(P5) ± (P8), kita dapat menghitung ham piran kedua. Proses ini dapat diulang-ulang sam pai keak uratan ham piran yang diinginkan tercapai. Berik ut adalah hasil

proses iterasi dengan menggunakan kom puter. No x1 x2 x3 x4

1

2

3

4

56

7

8

0.6

1.04727

0.932636

1.0152

0.9889911.0032

0.998128

1.00063

2.27273

1.71591

2.05331

1.9537

2.011411.99224

2.00231

1.99867

-1.1

-0.805227

-1.04934

-0.968109 -1.01029 -0.994522

-1.00197

-0.999036

1.875

0.885227

1.13088

0.973843

1.021350.994434

1.00359

0.998888

Setelah iterasi ke-8 diperoleh ham piran 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 berik ut ini dengan menggunakan metode iterasi

Jacobi.2x1 ± x2 + 10x3 = -113x2 ± x3 + 8x4 = -11

10x1 ± x2 + 2x3 =6

-x1 + 11x2 ± x3+ 3x4 = 25



7

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;

f or k =1: N, f or i = 1:n,

S = b(i)-A(i,[1:i-1,i+1:n])*X0([1:i-1,i+1:n]);

X1(i)=S/A(i,i);

end g = abs(X1-X0);

err = nor m(g);relerr = err/(nor m(X1)+ eps);

X0 = X1;

H = [H;X0'];

if (err <T)|(relerr <T),break,end end

Layar Editor MATLAB 7

F. Hasil Output fungsi MATLAB 7

Berik ut adalah contoh pemakaian fungsi MATLAB 7 jacobi dan hasil

keluaran dari yang diperoleh: >> 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 810 -1 2 0

-1 11 -1 3

>> b=[-11;-11;6;25]

b =

-11



8

-11

6

25>> X0=[0;0;0;0]

X0 =

00

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.13800.0451

g =

1.0e+017*

3.7699

0.54421.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

0 . 0000 0 . 0000 0 . 0000 0 . 00000 . 0000 0 . 0000 0 . 0000 0 . 0000

0 . 0000 0 . 0000 0 . 0000 0 . 0000

0 . 0000 0 . 0000 0 . 0000 0 . 00000 . 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 . 00000 . 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 . 00000 . 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



9

Dari hasil diatas, metode Jacobi belum konvergen setelah melak ukan iterasi. Untuk mengetahui penyelesaian SPL kita, selanjutnya gunakan metode langsung

dengan menggunakan invers matriks A. MATLAB mem berikan penyelesaian sebagai berik ut. >> X=inv(A)*b X =

1.1039

2.9965

-1.0211

-2.6263

A pakah metode jacobi tidak dapat menghasilkan penyelesaian tersebut? Dengan mengu bah susunan SPL, yakni persamaan pertama dan kedua dipindah

menjadi persamaan ketiga dan keem pat, metode Jacobi ternyata berhasil mem berikan penyelesaian tersebut, sebagaimana terlihat pada hasil keluaran

MATLAB berik ut.

>> 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 32 -1 10 00 3 -1 8

>> b=[6;25;-11;-11]

b =

6

25

-11

-11

>> X0=[-2;1;3;-1]

X0 =

-21

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.07970.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



10

1 . 1030 2 . 9965 -1 . 0220 -2 . 6236

1 . 1040 2 . 9856 -1 . 0209 -2 . 6264

1 . 1037 2 . 9966 -1 . 0212 -2 . 62601 . 1039 2 . 9964 -1 . 0211 -2 . 6264

1 . 1039 2 . 9965 -1 . 0211 -2 . 6263

1 . 1039 2 . 9965 -1 . 0211 -2 . 62631 . 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. Ham piran penyelesaian SPL kita adalah X = (1.1039

2.9965 -1.0211 -2.6263)T. Layar MATLAB 7 (command window)

Dari contoh di atas bahwa ur utan persamaan di dalam suatu SPL sangat berpengar uh terhadap penam pilan metode iterasi Jacobi. K alau kita amati lebih

lanjut contoh di atas, kekonvergenan iterasi Jacobi pada strategi kedua dikarenakan kita telah mengu bah susunan SPL sedemikian hingga elemen-elemen

aii mer u pakan elemen-elemen terbesar pada setiap baris. Dengan kata lain, apabila matriks koef isien A mer u pakan matriks dominan secara diagonal, maka metode

iterasi Jacobi akan konvergen. Suatu matrik A ber uk uran n x n dikatakan dominan secara diagonal apabila

||...||||...|||| ,1,1,1, niiiiiiii aaaaa "

untuk i = 1, 2, 3, ..., n.



11

SIMPULAN

A. Sim pulan

Dari pem bahasan di atas kita dapat mengam bil kesim pulan bahwa. 1. Ur utan persamaan di dalam suatu SPL sangat berpengar uh terhadap

penam pilan metode iterasi Jacobi.

2.

Dengan menggunakan pemrograman MATLAB 7 dapat mem bantu pemrograman dalam dalam metode numeric khususnya metode iterasi Jacobi

B. Saran Dari hasil pem bahasan disarankan untuk.

1. Menggunakan metode iterasi Jacobi lebih ef ektif untuk memecahkan masalah numerik dalam SPL ber uk uran besar.

2. Menggunakan program MATLAB 7 f or Windows dalam mem bantu pengolahan metode iterasi Jacobi.

iterasi-jacobi

Documents