Analisis Kecepatan \konvergensi

$Page 1: Analisis Kecepatan \konvergensi$
Prosiding Pertemuan IImiah Nasional Rekayasa Perangkat NuklirSerpong, 20 Nopember 2007

ISSN 1693-3346

ANALISIS KECEP ATAN KONVERGENSI PADA TEKNIK PENYELESAIANGAUSS-SEIDEL DIKOMBINASI DENGAN EKSTRAPOLASI AITKEN

DAN PENERAP ANNY A PADA RANG KAlAN RESISTIF

Oleh:

Entjie Mochamad SobbichPuslit KIM-LIPI

ABSTRAK

Salah satu kriteria yang sering digunakan untuk menyatakan 'baik-buruk' dari teknik

teknik penyelesaian yang iteratif adalah kecepatan konvergensi, yaitu kesegeraan dalam

mencapai (atau mendekati) jawaban eksak. Jadi, suatu teknik penyelesaian akan dianggap

tidak baik jika untuk mencapai nilai solusi eksaknya diperlukan (misalnya) 300 iterasi

padahal teknik lainnya mampu mencapainya hanya setelah (anggaplah) 20 iterasi. Didalam

makalah ini, sebuah contoh rangkaian resistif dicari penyelesaian untuk tegangan simpul

simpulnya secara analitis iteratif menggunakan teknik penyelesaian Gauss-Seidel, dan

kombinasinya dengan teknik ekstrapolasi Aitken untuk percepatan pencapaian solusi

eksak. Hasilnya, sebuah proses iterasi yang konvergenitasnya dicapai setelah 300 iterasi

dapat disegerakan menjadi hanya 20 iterasi.

Kata-kunci : teknik Gauss-Seidel, esktrapolasi Aitken. konvergensi, tegangan simpul.

ABSTRACT

One of criteria that is frequently used to define 'good-bad' of an iterative solution method

is the convergence SPEED, i.e. the speed on achieving (or closes) the exact solution. So, a

solution method should assumed as not good when it reaches the exact solution after (for

instance) 300 iterations, if the other method capable to reach it just after (let say it) 20

iteration. In this paper, an example of resistive circuit was found for the solution of their

nodal voltages by iterative analytic using Gauss-Seidel solution method, and the

combination with Aitken's extrapolation technique in order to make short in reaching the

exact solution. The result, the problem of which can be solved at 300 iteration can be make

short just in 20 iteration.

Keywords: Gauss-Seidel technique, Aitken extrapolation, convergence, nodal voltage.

273


PENDAHULUAN

ISSN 1693-3346

Di dunia nyata, kita sering menghadapi perosalan-persoalan dengan ukuran besar dan

dalam kerumitan tertentu. Solusi menggunakan cara manual dan analitis perlu mendapat

perhatian. Kekeliruan akan mudah terjadi, keraguan terhadap hasil-akhirpun dapat timbul,

bahkan yang lebih penting dan pasti terjadi adalah waktu eksekusi yang pasti sangat lama

sekali sebanding dengan ukuran serta kerumitan persoalan yang sedang dihadapi.

Jaman sudah berubah, komputer sudah hadir. Kita manfaatkan komputer agar mampu

melakukan pencarian solusi dari persoalan kita. Masalahnya : mesin hitung tersebut tidak

dapat dengan sendirinya melakukan suatu proses, ia harus dijalankan dengan

'memasukkan' suatu jalan-pemikiran yang umum dikenal dengan algoritma atau teknik

penyelesaian.

Didalam makalah ini diuraikan teknik numerik untuk menyelesaikan rangkaian yang

bersifat resistif.

TEORIDASAR

Apabila terdapat sebuah rangkaian yang hanya berisi sumber pembangkit arus listrik serta

resistor-resistor didalamnya maka analisis simpul-simpul akan menghasilkan persamaan

simultan yang linier dengan koefisien-koefisien yang berharga konstan. Secara umum

dapat dituliskan hasil analisisnya sebagai berikut :

II = gllV1 + gl2 V2 + gu V3 + .

h = g21VI + g22 V2 + g23 V3 + .

h = g31VI + g32V2 + g33V3 + .

(1)

274

Prosiding Pertemuan I1miah Nasional Rekayasa Perangkat NuklirSerpong, 20 Nopember 2007

Yang mana bila direpresentasikan dalam bentuk matrik akan menjadi :

ISSN 1693-3346

gll g12gl3...gill VI11

g21

g22g23...g211V2I,g31

g32g33...g3n•V,=1: I(2)

• >

..

............ .....

gnl

gn2gll3...gill/ VII111

dengan

gij

koefisien konstan (konduktansi)

Vijbe saran yang dicari (tegangan pada satu simpul)

Iijbesaran yang diketahui (arus dari sumber tegangan).

Persamaan simultan diatas akan sulit diselesaikan bila harus dilakukan secara analitis

ataupun manual. Oleh karena itu, satu-satunya cara yang dapat ditempuh adalah dengan

memanfaatkan metoda numerik (umumnya berupa sebuah cara iteratit), dalam kasus ini

akan ditempuh cara penyelesaian menggunakan algoritma Gauss-Siedel. Algoritma ini

dipilih sebagai teknik penyelesaian karena berbagai kelebihan, yaitu :

1. Mudah untuk di-kode-kan

2. Bersifat sangat robust

3. Kesalahan dapat direduksi sekecil mungkin berdasarkan kemampuan mesin penghitung

(komputer)

4. Banyaknya iterasi tidak bergantung pada dimensi (ukuran) jaringan.

Algoritma ini memerlukan penduga-mula terhadap solusi vektor V (missal: Vj = untukj =

1, 2, ... ,n). Dengan penduga- awal tersebut dilakukan penyelesaian untuk persamaan

pertama, lalu solusi vektor V I diperbarui (updating) menggunakan nilailharga barunya.

Selanjutnya lakukan penyelesaian V2 dari persamaan kedua, V3 dari persamaan ketiga

demikian seterusnya. Lakukan proses iterasi (pengulangan yang terus-menerus) yang

akhimya didapatkan harga vektor V yang konvergen menuju solusi sistem linier tersebut.

V(k) = _I [~ ..V (k) ~ V (k-IJ;I L., g '/' I + L., g If' I

gll .1=1 /=1+1

275


dirnana :y(O) =0i= 1,2, ... , nk = 1,2, 3, ...

ISSN 1693-3346

Pertarna kali rnembicarakan konvergensi berarti kita perlu memperbincangkan bagairnana

cara mernbangun matrik koefisien. Dengan memperhatikan pada konduktansi gik

(konduktansi an tara simpul i dan k) maka diagonal gii dapat diberikan [ormulasinya

sebagai :

n

gji = Lg,kk=O

k:;t i.

dirnana

giO konduktansi antara simpul i dan tanah (simpul 0).

CONTOH : Untuk rangkaian seperti pada Gambar-I, elemen diagonal gl I adalah sarna

dengan surnasi konduktansi-konduktansi bermula dari simpul I .

• 4il'.S 91~.>

ql" 1 91"'- - I •·~Vo/' ...I\.------~/Vv---~) I ! ')L t.. •....•c"

:~ g·o.;:.,.l. [I

Gambar-I : Contoh rangkaian resistip.

Jadi :

Catat bahwajika dua simpul tidak ada brunch, maka konduktansi mutual-nya berharga nol.

Pada contoh tersebut : g13 = g34 = g24 di O.

Matrik konduktansi dari rangkaian riil

n I' "

gj; ~ Lg,k ==:> Lg'k ~ Lg'kk=1 k=O k=1k,,; k", k",

1/ II

==:> g,o + Lg'k ~ Lg,kk=1 k=1k 1'-1 k'#.i

276

Prosiding Pertemuan Ilmiah Nasional Rekayasa Perangkat NuklirSerpong, 20 Nopember 2007

ISSN 1693-3346

Sederhananya adalah, kita dapatkan relasi giO 2: 0 yang selalu benar untuk bentuk

rangkaian apapun. Setidaknya, satu simpul harus terdapat konduktansi "tentu" ke tanah,

setidaknya, satu relasi dipenuhi dengan lam bang ">". Ini menunjukkan bahwasanya

matrik adalah dominant diagonal

sehingga algoritma Gauss-Seidel bersifat konvergen. Berikut adalah cara kerja dengan

menggunakan sebuah contoh.

Pada rangkaian seperti ditunjukkan pada Gambar-2, diasumsikan terdapat rangkaian

dengan 4 simpul yang hendak dicari tegangannya VI, V2, V3, V4• Resistor dalam Ohm.

Pembangkit arus mengalirkan arus listrik ke simpul I sebesar 1 Amp. Tahanan R

sebenarnya adalah sebuah nilai yang bisa parametris tetapi untuk keperluan memudahkan

analisis secara manual, disini diambil bernilai 100 Ohm.

4

50

Gambar-2 : Rangkaian resistif yang hendak dicari tegangan simpul-simpulnya

Untuk sistem linier ini berlaku :

[G].V = 1

dengan[G]VI

matrik konduktansi

vektor teganganvektor arus

Matrik Kondukstansi [G]0,03

-0,01-0,0 I0

-0,011,025-1-0.0 I

-0,01

-11,025-0,0 I0

-0,01-0,0 I0,04

277

Arus (I)1

ooo


k VI V2V3V4

0

0 000I 33,3339,523812,2455,4422

240,5916,6517,9096,399

344,85320,40121,11310,378

447,17122,47522,86411,335

548,44623,61323,82711,86

1049,99224,93124,94\12,468

1549,996,24,99724,99712,498

2050252512,5

ISSN 1693-3346

Berawal dengan vektor (0, 0, O. 0), algoritma konvergen secara cepat menghasilkan solusi

(50, 25, 25, 12,5). Dengan mengamati hasil seperti ditunjukkan pada Gambar-3 berikut

terlihat bahwa sesudah hanya dalam 20 kali iterasi kesalahannya mencapai dibawah 0,1 %,

mencapai sekitar I E-09 setelah 14 iterasi dan menjadi kurang dari 1*E-14 hanya setelah

iterasi 60.

I} '1

0.G01

1E-O:':·

1E-[l7

1 E-09

20 JC 60 80

1E-11

1E-'!

iE-1!5Error

I1

........_. ._.3

Gambar-3 : Kecepatan penurunan deviasi terhadap nilai eksak pad a bertambahnya iterasi

Pada contoh diatas, konvergensi 'kebetulan' didapatkan dalam iterasi yang sangat cepat.

Namun kondisi ini tidak berlaku umum untuk setiap jaringan. Untuk penghitungan dengan

parameter R = I Ohm hasilnya adalah : Vektor solusi memang tidak berubah tetapi

kecepatan konvergensi jauh lebih singkat dibandingkan yang sebelumnya.

278


ISSN 1693-3346

Matrik Kondukstansi [G]0,03

-0,01-0,010

-0,011,025-I-0,0 I

-0,01

-I1,025-0,010

-0,01-0,01~:~~ Arus (I)1

ooo

k VI V2V3V40

0 0001

33,3330,32520,64250,24192

33,6560,95751,26490,55563

34.0741,57191,87140,86084

34,4812,17052,46241,15825

34,8782,75393,03831,44816

35,2643,32243,59951,73057

35,6413,87634,14642,00578

36,0084,41614,67922,27389

36,3654,94215,19852,535110

36,7145,45465,70452,789812

37,3846,44086,6783,279714

38,027,37727,60243,744916

38,6258,26638,48024,186618

39,1999,11069,31374,606120

39,7449,912310,1055,0043...

'0 • .0.•• 0...300

49,992724,989324,989412,4947

Berawal dengan vektor (0, 0, 0, 0), algoritma mencapai keadaan konvergen dengan arnat

larnban untuk mencapai soilisi (50, 25, 25,12,5).

Setelah 20 iterasi hasilnya masih jallh dari solusi eksak, hasilnya baru (39,774; 9,9123;

10,105; 5,0043), sekitar separllh dari nilai eksaknya. Ternyata, dibutuhkan sekitar 300

iterasi untuk mencapai kesalahan sebesar kllrang dari I %.

Matrik Hill conditioned

Alasan terjadinya begitu ban yak perbedaan kecepatan konvergensi pada algoritma yang

sarna adalah bahwa matrik dalam contoh ini tetap dominan tetapi lebih kecil dari yang

pertarna. Pada kenyataannya. bahwa elemen yang sama yang diluar diagonal dekat dalam

rnodul dengan elemen diagonal pada baris yang sama. Jadi :

dan

279


ISSN 1693-3346

Sebaliknya, untuk yang konvergensi cepat terjadi keadaan :

la231«1a22

dan a]21 « IQ33

Situasi dengan konvergensi ini (matrik "hill-conditioned') dapat dideteksi dengan mudah

dengan cara melakukan inspeksi langsung pad a jaringan itu sendiri. Apabila rasio antara

resistor tertinggi dan terendah adalah tinggi maka berarti matrik terkait berada pada hill

conditioned. Semakin tinggi rasionya, semakin lamban fitur konvergensinya.

Pada rangkaian listrik umumnya terjadi nilai rasio sebesar 1000 atau bahkan lebih besar

dan ini menunjukkan bahwa algoritma ini tak dapat dipergunakan (useless). Untungnya

masih ada metoda yang efisien dan mudah untuk meningkatkan kecepatan konvergensi,

disebut : metoda ekstrapolasi kuadrat delta (delta square extrapolation)(Aitken's

extrapolation).

Definisikan: ~i = Xi - Xi-I

Formula ekstrapolasinya adalah :

2 ( )"~ x -x -X'= x _ n = ,. - 11 11-1n ..-\./1

~11 - ~n-I xn - 2x"_1 + X,,_2

dimana

X' aproksimasi terbaik dari tiga nilai terakhir Xn. x n-h X n-2

Pad a contoh yang terakhir, ambillah iterasi terakhir 18, 19,20 dari VI diperoleh :

k VI18

39,19874959698319

39,47475815364520

39,743713756203

I ekstrpl I 49,999999999979

280


ISSN 1693-3346

Terjadi percepatan yang sangat cepat menggunakan tiga iterasi terakhir dari 20 iterasi,

dengan formula ekstrapolasi ini telah dapat dicapai kesalahan lebih kecil dari IE-IO.

Metoda ini dapat diterapkan pula untuk V2 , V3 and V4 dan akan didapatkan hasi\ dengan

percepatan dengan kecepatan yang sama.

Formula ekstrapolasi bekerja sangat halus pada saat jaringan berkondisi hill-conditional.

Penting untuk melakukan kajian agak lebih mendalam. Disini akan diperoleh bentuk yang

agak sedikit berbeda (tetapi ekivalen) untuk ekstrapolasi Aitken. Diasumsikan bahwa

formula iterasi mempunyai bentuk linier sebagai berikut (paling sederhana)

(3)

Jadi, berawal dari V 0 didapatkan :

VI = a + fJYo

V2 = a + fJY1 = a + fJ(a + fJYo) = a + a.fJ + fJ2 Yo

V3 = a + fJY2 = a + fJ(a + afJ + fJ2 Y(J) = a + a.fJ + afJ2. + fJ3 Yo

V fJV fJ fJ2 fJ3 fJ"-1 fJnVn = a + . ,,_I= a + a. + a . + a . + ...+ a + 0

= a(1 + fJ + fJ2 + /I' + ...+ fJ"'I)+ fJ".vo

yang dapat dituliskan menjadi

Vn = aIfJk + fJ".vo == a[ I - fJ" ) + fJ" Yok=O I - fJ

Agar deret konvergen menuju suatu harga tertentu (finite) maka dalam kasus ini diperlukan

agar 113\ < I, mengingat bahwa lim fJ" = a jika ~ berupa pecahan sejati dibawah +1 atau-,,~a)

I, dengan demikian :

Urnv" ~ lirn[ a[ 1- (3" ) + (3"YoI= -"'11-><>0 n->'" J - fJ ) I - j3

281


ISSN 1693-3346

Solusi dapat diketahui jika kita mengetahui koefisien a dan ~. Keduaya dapat diperoleh

melalui tiga iterasi berurutan Vn-2, Vn-!, Vn dengan cara menyelesaikan sistem linier

berikut :

=> 13 = V" - V,,_IV I'n-I - I 11-2

Substitusikan, solusi untuk V akan menjadi :

a = V" - j3.V,,_1

v = ~ _ V" - j3'vII_1

1-13- 1-13dimana V -V"_I"

13 = V - Vn_20-1(4)

Eliminasi ~ dengan cara substitusi, diperoleh :

v = Vn'vn_2 - Vn_1 2 = V _ (V" - V"_IYV ,V +V "V,V +Vn-2 n-I n-2 11-2 II-I 11-2

Jadi, formula (4) adalah bentuk lain yang berbeda untuk ekstrapolasi kuadrat delta.

Pada kenyataannya, oleh karena asumsi awal (3) tidak eksak, berakibat nilai "V"

merupakan nilai perkiraan dari solusi eksak. Pengulangan formula dari setiap tiga (atau

lebih) iterasi memungkinkan kita untuk mendapatkan solusi dengan perkiraan tertinggi

yang bisa terjadi.

Untuk sistem dengan hill-conditioned, parameter ~ :::::1 atau I I - ~ I < 1>. (Biasanya E

sekitar 0, I -:-0,01). In i merupakan uj i yang tidak sekedar cuap-cuap (cheep) belaka

dan praktis untuk dideteksi untuk meningkatkan kecepatan konvergensi dengan formula

ekstrapo las i.

Untuk contoh ke-l dengan konvergensi cepat. didapatkan :

V(IO) _ V(9)

13 = (9) 10' ~ 0,543 => I - 13~ 0,456V -V

Sedangkan untuk contoh ke-2 yang konvergensinya lamban, didapatkan :

V(IO) _ V(9)

fJ = (9) (8) ~ 0,977 => 1- 13 ~ 0,022V -V

282

Prosiding Pertemuan I1miah Nasional Rekayasa Perangkat NuklirSerpong, 20 Nopember 2007

ISSN 1693-3346

CATATAN. Parameter ~ dapat dihitung dengan mengambil 3 iterasi berurutan yang

manapun, dalam contoh diatas dilakukan pengambilan dari iterasi (8, 9, 10). Kita dapatkan

hasil serupa bila mengambil dari iterasi (5,6. 7) ataupun (18, 19,20).

Penggunaan algoritma Gauss-Seidel bersama dengan ekstrapolasi formula Aitken telah

mampu merealisasikan metoda yang efisien untuk menyelesaikan suatu rangkaian resistif.

KESIMPULAN

Obyektif dari teknik iterasi adalah kecepatan konvergensi untuk mencapai sedekat

dekatnya dengan nilai eksak, yang juga berarti : tingkat efisiensi iterasi itu sendiri.

Didalam makalah ini, telah dilakukan analisis terhadap implementasi metoda iterasi Gauss

Seidel terhadap jaringan resistif seperti diberikan pada Gambar-I. Dengan mengambil

contoh numerik seperti Gambar-I, algoritma Gauss-Seidel ansich menghasilkan nilai eksak

(dengan kesalahan didalam I %) setelah terjadi 300-an iterasi. Dengan mencoba

melakukan kombinasi antara algoritma Gauss-Seidel dan Aitken banyaknya iterasi untuk

kasus yang sarna hanya memerlukan 20-an iterasi. suatu percepatan konvergensi yang

dapat dipandang sebagai sangat siknifikan.

DAFT AR PUST AKA

1. Floyd T.L., Electric CirclIit Fundamentals, Merrill Pub!. Co., Columbus, Ohio, 1987.

2. Van Valkenberg M.£., Nasution S.H .. Analisis Jaringan Listrik,

Penerbit Erlangga, 1988.

3. James M.L., and Smith G.M., Applied Numerical Methodsfor Digital Computers,

3rd Ed., Herfer & Rows Pub!., New York. 1985.

4. Gerald C.F., Wheatley P.O., Applied Numerical Analysis, 6th Ed.,

Addison Wesley. 1999.

5. Kreyszig E.,Advanced Engineering Mathematics. 8th Ed.. Chapters I, 5, 8, 9,

John Willey & Sons Inc., New York, 1999.

283

Analisis Kecepatan \konvergensi

Documents