RESUMEMETODA NUMERIKPERSAMAAN SISTEM LINEAR

OLEH:SUCI MUHARRA YUNNISA1310952052

DOSEN:HERU DIBYO LAKSONO

JURUSAN TEKNIK ELEKTROFAKULTAS TEKNIKUNIVERSITAS ANDALASPADANG2015

SISTEM PERSAMAAN LINIER

Di dalam matematika, system persamaan linier adalah kumpulan persamaan-persamaan linier yang memiliki variabel-variabel yang sama. Bentuk umum dari sistem persamaan linier dengan n peubah dinyatakan sebagai berikut:

Dengan mengunakan perkalian matriks, kita dapat menulis persamaan di atas sebagai persamaan matriks Ax = b Yang dalam hal ini,

adalah matriks berukuran n x n

adalah matriks berukuran n x 1

adalah matriks berukuran n x 1 (disebut juga vektor kolom)Yaitu:

A. Metoda Eliminasi Gauss

Eliminasi Gauss merupakan salah satu metode penyelesaian sistem persamaan aljabar linier. Strategi penyelesaian sistem n buah persamaan linier Ax = b, di mana A adalah matriks bujur sangkar biasa dilakukan dengan: 1. Mereduksi Ax = b menjadi Ux = c, di mana U adalah matriks segitiga atas berorder n, dan2. Menyelesaikan sistem Ux = c tersebut di atas dengan metode substitusi balik (backward substitution), sehingga diperoleh x.

Metode pereduksian tersebut di atas disebut proses eliminasi Gauss, dan akan diilustrasikan dalam contoh berikut ini:

Bentuk matriks perbesarannya:

Langkah-langkahnya: 1. Buatlah elemen-elemen di bawah a11 menjadi bernilai nol, dengan cara:a. Hitunglah

b. Baris ke-2 baru = baris ke-2 lama l21 (baris ke-1) Baris ke-3 baru = baris ke-3 lama l31 (baris ke-1) Baris ke-4 baru = baris ke-4 lama l41(baris ke-1)

sehingga diperoleh:

2. Buatlah elemen-elemen di bawah a22 (yang baru) menjadi bernilai nol, dengan cara: a. Hitunglah:

b. Baris ke-3 baru = baris ke-3 lama l32 (baris ke-2) Baris ke-4 baru = baris ke-4 lama l42 (baris ke-2)

sehingga diperoleh:

3. Buatlah elemen-elemen di bawah a33 (yang baru) menjadi bernilai nol, dengan cara: a. Hituglah:

b. Baris ke-4 baru = baris ke-4 lama l43 (baris ke-3)

sehingga diperoleh:

Proses eliminasi selesai setelah (n-1) tahap/langkah, di mana n adalah order dari matriks koefisien.

Penyelesaian persamaan:

selanjutnya dapat dilakukan dengan cara substitusi balik:

sehingga diperoleh: x = [0 1 -1 0]T

verifikasi nilai =

Persoalan yang Muncul dan Pemecahannya Persoalan-persoalan yang dapat dijumpai dalam penyelesaian sistem persamaan linier dengan metode eliminasi Gauss meliputi:

1. Division by ZeroPembagian dengan bilangan nol sangat mungkin terjadi dalam penyelesaian sistem persamaan linier dengan eliminasi Gauss. Contoh: Gunakan eliminasi Gauss untuk menyelesaikan kumpulan persamaan:

(Perhatikan bahwa tahap reduksi atau eliminasi yang pertama akan gagal, karena a11=0)Persoalan yang sama dapat dijumpai jika elemen diagonal matriks koefisiennya mendekati nol (sangat kecil). 2. Round-Off Errors Error yang disebabkan oleh pembulatan bilangan yang terjadi selama proses eliminasi

3. Ill-Conditioned Systems Penyelesaian sebuah sistem persamaan ditentukan oleh kondisi sistem tersebut. Pada well-conditioned systems, perubahan kecil dalam satu ataulebih koefisiennya mengakibatkan perubahan yang kecil dalam penyelesaiannya. Dan sebaliknya, pada ill-conditioned systems, perubahan kecil dalam satu atau lebih koefisiennya mengakibatkan perubahan yang besar dalam penyelesaiannya. Ill-conditioned systemsjuga memungkinkan terjadinya jawaban dengan rentang yang lebar, yang merupakan penyelesaian dari sistem persamaan tersebut.

4. Singular Systems Kasus ini terjadi jika determinan matriks koefisien sistem persamaan bernilai nol (atau merupakan matriks tak wajar), sehingga tidak mempunyai penyelesaian. Persoalan tersebut di atas (1-3) dapat dipecahkan melalui beberapa cara, seperti (1) Penggunaan significant figuresyang lebih banyak, (2) Pivoting, maupun (3) Scaling.

B. Metode Gauss-Jordan Metode eliminasi Gauss merupakan separuh jalan dari metode Gauss-Jordan, yakni metode yang dilakukan untuk mengubah matriks bujur sangkar A menjadi sebuah matriks diagonal D. Proses eliminasi yang dilakukan terhadap matriks segitiga atas U agar menjadi matriks diagonal D dilakukan melalui langkah-langkah yang serupa. Ilustrasi dalam contoh sebelumnya akan diproseslebih lanjut menggunakan metode Gauss-Jordan. (lihat kembali contoh sebelumnya)

Matriks perbesaran

Eliminasi Gauss

Dengan demikian:

(sama dengan hasil yang diperoleh sebelumnya, dengan metode eliminasi Gauss) Karena penyelesaian Ax = b sudah dapat dicapai secara efisien dengan metode eliminasi Gauss, penggunaan metode Gauss-Jordan bukanlah dalam penyelesaian sistem persamaan linier, melainkan dalam perhitungan manual penentuan matriks kebalikan (atau invers) A-1 dari matriks bujur sangkar A. A . A-1 = I(dapat ditentukan/dicari dengan metode Gauss Jordan)Contoh:

Tentukan invers dari matriks A = , dengan metode Gauss-Jordan! Penyelesaian:

tahap pertama eliminasi gauss

tahap kedua eliminasi gauss

tahap pertama gauss jordan(keadaan pada tahap akhir eliminasi Gauss)

tahap pertama gauss jordan

Selanjutnya, baris pertama dibagi dengan 2, baris kedua dibagi dengan (-1), dan baris ketiga dibagi dengan (-4), sehingga diperoleh:

Verifikasi hasil:

Jadi, matriks invers A adalah:

C. Metode Gauss Seidel

Metode interasi Gauss-Seidel : metode yang menggunakan proses iterasi hingga diperoleh nilai-nilai yang berubah. Bila diketahui persamaan linier simultan

Berikan nilai awal dari setiap xi (i=1 s/d n) kemudian persamaan linier simultan diatas dituliskan menjadi:

Dengan menghitung nilai-nilai xi (i=1 s/d n) menggunakan persamaan-persamaan di atas secara terus-menerus hingga nilai untuk setiap xi (i=1 s/d n) sudah sama dengan nilai xi pada iterasi sebelumnya maka diperoleh penyelesaian dari persamaan linier simultan tersebut. Atau dengan kata lain proses iterasi dihentikan bila selisih nilai xi (i=1 s/d n) dengan nilai xi pada iterasi sebelumnya kurang dari nilai tolerasi error yang ditentukan.Untuk mengecek kekonvergenan

Teknik Penyelesaian1. Hitung nilai nilai xi (i = 1...n) dari peramaan diatas2. Lakukan sehingga nilai-nilai xi tersebut menekati nilai xi pada iterasi sebelumnya, dengan bata toleransi tertentu3. Proses iterasi akan berhenti ketika selisih xi dengan xi-1 kurang dari nilai toleransi error yang di tentukan

Contoh Soal,1. Tentukan solusi SPL

Jawab:

Berikan nilai awal Susun persamaan menjadi

Lakukan proses iterasi

Iterasi 1

Iterasi 2

Iterasi 3

Kxy2

0000

11.753.53

21.8753.93752.9625

31.993753.9921882.999063

41.9982813.9990232.999508

51.9998793.9998782.999976

61.9999753.9999852.999993

71.9999983.9999983

8243

9243

10243

Terlihat bahwa selisih nilai x,y,z pada iterasi ke 7 dan ke 8 semakn kecil sehinggaX=2, y=4, z=3D. Metode InversiPada matriks, operasi pembagian matriks tidak didefinisikan, akan tetapi operasi matriks yang serupa dengan pembagian adalah matriks inversi. Bila A adalah MBS, maka matriks inversinya adalah A1, sedemikian sehingga:

AA1 = A1A = I, dengan I adalah matriks identitas.Selain itu matriks inversi dapat digunakan untuk menyelesaikan sistem yang berbentuk:AX = C atau A-1CNilai X dapat dihitung dengan mengalikan matriks inversi dari koefisien matriks A dengan ruas kanan dari sistem persamaan yaitu C.Metode Gauss-Jordan dapat digunakan untuk mencari matriks inversi, untuk itu koefisien matriks ditingkatkan dengan matriks identitas. Metode Gauss-Jordan dipakai untuk mereduksi koefisien matriks menjadi matriks identitas, setelah selesai, sisi kanan dari matriks yang ditingkatkan merupakan matriks inversi.Prosedur dari hitungan matriks inversi:

A I I A-1

Contoh soal:

Cari matriks inversi dari matriks sebagai berikut: A = Penyelesaian:Dilakukan dengan menggunakan metode Gauss-Jordan, dengan terlebih dahulu dilakukan peningkatan matriks dengan matriks identitas.

a) Matriks ditingkatkan, menjadi: b) Baris pertama dibagi 3 (nilai yang akan dijadikan 1), menjadi:

c) Baris kedua dikurangi hasil dari baris pertama dikali 4, dan baris ketiga dikurangi hasil dari baris pertama dikali 2, menjadi:

d) Baris kedua dibagi 5,6667 (nilai yang akan dijadikan 1), menjadi:

e) Baris pertama dikurangi hasil dari baris kedua dikali 0,3333 dan baris ketiga ditambah hasil dari baris kedua dikali 2,6667 menjadi:

f) Baris ketiga dibagi 4,8824 (nilai yang akan dijadikan 1), menjadi:

g) Baris pertama ditambah hasil dari baris ketiga dikali 0,2353 dan baris kedua ditambah hasil dari baris ketiga dikali 0,2941 menjadi:

maka matriks inversnya adalah =

E. Dekomposisi LU

Prinsip Dekomposisi LU dan Matriks Identitas Matriks [A] dari SPAL didekomposisi (difaktorisasis) menjadi matriks-matrik segitiga bawah (L) dan segitiga atas (U) sedemikian rupa sehingga identitasnya adalah: [A] = [L][U] atau A = LUDekomposisi matriks LU merupakan salah satu metode numerik untuk menyelesaikan persamaan matriks. Apabila secara analitik, mungkin akan sangat mudah menyelesaikan persamaan matriks seperti ini AX=B, dimana kita hanya mengetahui nilai matriks A dan matriks B saja, sementara kita tidak tahu nilai dari matriks X. Secara analitik kita dapat tuliskan bahwa matriks X merupakan perkalian dari inverse matriks A dengan matriks B, atau dapat ditulis X=A-1B.

Dari perkalian matriks maka didapatkan

Sehingga dapat didefinisikan u1j= a1j(j= 1, ,n)

dengan(i = 2, , n)

dengan (i =2, ,n; j=i, , n), kemudian

dengan (i=3, , n; j=2, , i-1)LY=B, dalam bentuk matriks dapat ditulisSehingga dapat didefinisikany1= b1

dengan (i =2, , n) danUX=Y, dalam bentuk matriks dapat dituliskan sehingga dapat didefiniskanx = yn

dengan (i =1, , n-1)

Contoh Soal:Tentukan determinan matriks berikut:A=Solusi:

Tahap 1:

Tahap 2:

Tahap 3:

Tahap 4:

Tahap 5:

=.

a. Metode CroutNotasi Matriks LU berdasarkan Metode Crout Notasi matriks L seperti di atas dituliskan sbb:

Perhatikan, bahwa semua elemen diagonal dari matriks L di atas tidak harus berharga 1 (satu), sedangkan, elemen-elemen di atas diagonal semuanya berharga 0 (nol) ! Notasi matriks U dituliskan sbb:

Perhatikan, bahwa semua elemen diagonal (= u1,1 un,n) berharga 1 (satu), sedangkan yang terletak di bawahnya berharga 0 (nol) !

Notasi Matriks LU sebagai dekomposan matriks A dapat dituliskan dalam SPAL sbb: [A] [x] = [L][U][x] = [b]

Sehingga notasi Metode Crout dapat dituliskan:

b. Metode DoolitleNotasi Matriks LU berdasarkan Metode Doolittle Notasi matriks L seperti di atas dituliskan sbb:

Perhatikan, bahwa semua elemen diagonal dari matriks L di atas berharga 1 (satu) ! Sedangkan semua elemen di atas diagonal semuanya berharga 0 (nol) ! Notasi matriks U dituliskan sbb:

Perhatikan, bahwa semua elemen diagonal (= u1,1 un,n) berharga 1 (satu), sedangkan yang terletak di bawahnya berharga 0 (nol) !

Notasi Matriks A dan LU dalam SPAL Notasi Matriks LU sebagai dekomposan matriks A dapat dituliskan dalam SPAL sbb: [A] [x] = [L][U][x] = [b] Sehingga, dalam notasi Metode Doolittle dapat dituliskan

Notasi A = LU dalam Metode Doolittle seperti di atas dapat diuraikan dalam operasi perkalian matriks (sebagai contoh: matriks n x n) sbb:

Algoritma solusi numerik dengan Metode Doolittle:

c. Metode CholenskyMatriks Tridiagonal (Metode Sapuan Ganda Choleski) Disebut juga metode penyelesaian langsung, karena pemakaiannya mudah dan matriks tridiagonal banyak dijumpai dalam berbagai permasalahan terutama dalam penyelesaian persamaan diferensial order dua.Dipandang sistem persamaan sebagai berikut:

(2.14)Baris pertama pada persamaan (2.14) dari sistem memungkinkan untuk menulis bilangan tak diketahui x1 sebagai fungsi bilangan tak diketahui x2 dalam bentuk:

x1 = x2 + atau x1 = P1 x2 + Q1(2.15)

dengan P1 = dan Q1 = , bila nilai x1 disubstitusikan ke dalam baris kedua persamaan (2.14), maka didapat:

a2 (x2 + ) + b2 x2 + c2 x3 = d2 atau ( + b2 ) x2 = c2 x3 + (d2 a2)dapat pula ditulis sebagai: x2 = P2 x3 + Q2

dengan P2 = dan Q2 = , persamaan ini menunjukkan bahwa x2 merupakan fungsi dari x3, langkah seperti tadi dapat diulangi lagi untuk semua baris pada persamaan berikutnya. Dengan demikian setiap bilangan tak diketahui dapat dinyatakan sebagai bilangan tak diketahui berikutnya.Misalnya telah diperoleh persamaan sebagai berikut:xi 1 = Pi 1 xi + Qi 1 Apabila nilai xi 1 disubstitusikan ke dalam baris ke i dari sistem persamaan (2.14), maka:ai (Pi 1 xi + Qi 1) + bi xi + ci xi + 1 = di(ai Pi 1 + bi ) xi + ci xi + 1 = di (ai Qi 1)

xi = + Persamaan tersebut diatas dapat ditulis dalam bentuk:xi = Pi xi + 1 + Qi

dengan:Pi = dan

Qi =Untuk i = 1, maka persamaan (2.16a), menjadi:x1 = P1x2 + Q1

dengan:P1 = dan

Q1 =Perbandingan persamaan (2.17) dan (2.15), menunjukkan bahwa:P0 = 0 dan Q0 = 0Persamaan (2.17) dan (2.18), memungkinkan untuk menghitung koefisien Pi serta Qi dari nilai i = 1 sampai i = n, langkah ini merupakan sapuan pertama. Setelah sampai titik ke n hitungan dilakukan dalam arah kebalikannya, yaitu dari n ke 1, untuk menghitung bilangan tak diketahui xi. Untuk itu persamaan terakhir dari sistem persamaan (2.14) ditulis dalam bentuk:an xn 1 + bn xn = dn Pada sistem persamaan (2.16), apabila i = n 1, maka:xn 1 = Pn 1 xn + Qn 1 Substitusi dari persamaan (2.20) ke dalam persamaan (2.19), akan memberikan:an(Pn 1 xn + Qn 1) + bnxn = dn(anPn 1 + bn ) xn = dn an Qn 1

xn = Sesuai dengan persamaan (2.16a), maka: xn = Qn.Nilai xn dapat diperoleh, berdasarkan nilai xn yang didapat maka nilai xn 1 dapat dihitung pula dengan persamaan sebagai berikut: xn 1 = Pn 1 xn + Qn 1.Dari nilai xn 1 kemudian dihitung nilai xn 2, xn 3, dan seterusnya hingga ke nilai x1.

Contoh soal:Selesaikan sistem persamaan berikut ini dengan menggunakan metode sapuan ganda.

Penyelesaian:Sistem persamaan diatas dapat ditulis dalam bentuk matriks tridiagonal, yang penyelesaiannya dapat dilakukan dengan menggunakan persamaan berikut:

xi = Pi xi + 1 + Qi

dengan:Pi = dan

Qi =Skema penyelesaian sistem persamaan dengan metode sapuan ganda sebagai berikut:

x1i = 4 i = 3 i = 2 i = 1 P4 , Q4 P3 , Q3 P2 , Q2 P1 , Q1 Pi , Qi (i = 1,2,3,4)x2 x3 x4xi (i = 4,3,2,1)

Langkah pertama dihitung nilai Pi dan Qi (i = 1, 2, 3, 4) dari kiri ke kanan. Setelah sampai ke titik i = n = 4, dihitung nilai xn = Qn. Berdasarkan nilai xn tersebut, kemudian hitungan dilanjutkan dari kanan ke kiri untuk mendapatkan nilai xi (i = 4, 3, 2, 1).

a) Menghitung koefisien Pi dan Qi (i = 1, 2, 3, 4) Koefisien Pi dan Qi dihitung dengan menggunakan persamaan (c3) dan (c4), berdasarkan sistem persamaan (c1).Untuk i = 1, P0 = 0 dan Q0 = 0.

P1 = = = = 0,5.

Q1 = = = = 3,5.Untuk i = 2, P1 = 0,5 dan Q1 = 3,5.

P2 = = = 6.

Q2 = = = = 27.Untuk i = 3, P2 = 6 dan Q2 = 27.

P3 = = = = 0,02941.

Q3 = = = = 4,97059.

Untuk i = n = 4, Pn = 0 dan Qn = , maka:

x4 = Q4 = = = = 1,00.Setelah nilai Pi dan Qi (i = 1, 2, 3, 4) didapat, lalu dihitung nilai xi (i = 4, 3, 2, 1).

b) Menghitung xi (i = 4, 3, 2, 1) Variabel xi (i = 4, 3, 2, 1) dihitung dengan menggunakan persamaan (c2):xi = Pi xi + 1 + QiUntuk i = 4, maka x4 = Q4 = 1,00.Untuk i = 3, maka x3 = P3x4 + Q3 = (0,02941(1,00)) + 4,97059 = 5,00.Untuk i = 2, maka x2 = P2x3 + Q2 = (6(5,00)) + (27) = 3,00.Untuk i = 1, maka x1 = P1x2 + Q1 = (0,5(3,00)) + 3,5 = 2,00.Dengan demikian hasil yang diperoleh adalah:x1 = 2,00; x2 = 3,00; x3 = 5,00; x4 = 1,00.Untuk mengetahui benar atau tidaknya hasil yang diperoleh, maka nilai-nilai tersebut dimasukkan ke dalam persamaan yang telah diselesaikan.

DAFTAR PUSTAKA

http://fauziahnurulhakiqi.blogspot.com/2013/12/metode-numerik-metode-eliminasi-gauss.html

https://diyarkholisoh.files.wordpress.com/2008/12/sistem-aljabar-linier-doc-dy.pdf

http://elista.akprind.ac.id/upload/files/4460_Bab_2.doc

http://oc.its.ac.id/ambilfile.php?idp=2071

https://www.academia.edu/9537504/penggunaan_metode_Eliminasi_Gauss_dan_LU_Dekomposition