Algoritma Spl Dengan Dekomposisi Lu_nuh Akbar

ALGORITMA DOOLITTLE DAN CROUT DALAM DEKOMPOSISI LU Gatot Hardiyanto¹, Nuh Akbar², Resti Oktaviani³ Program Sarjana Magister Fakultas Ilmu Teknik Sipil Universitas Gunadarma Kampus D, Gedung 2 Lantai 3 Jl. Margonda Raya 100 Depok 16424 e-mail: ¹[email protected], ²[email protected], ³[email protected] 1,2,3

ABSTRAK Suatu proses produksi, perakitan, dan pengiriman barang merupakan contoh peristiwa yang dapat dinyatakan dalam model matematika. Model matematika dapat memiliki bentuk yang sederhana, namun juga dapat berbentuk kompleks. Dengan menyelesaikan sistem persamaan itu, dapat diketahui penyelesaian masalah yang diminta model matematika tersebut. Dengan metode Dekomposisi LU, yaitu dengan cara membentuk matriks segitiga atas (upper) dan matriks segitiga bawah (lower) dari matriks koefisien A serta membentuk vektor matriks dari matriks hasil dengan aturan tertentu. Ada 2 metode untuk menyelesaikan dekomposisi LU, yaitu metode Doolittle dan metode Crout. Kelebihan dari metode dekomposisi LU adalah sangat efektif untuk menyelesaikan persamaan linier serentak yang berordo tinggi, dengan hasil yang mendekati nilai eksaknya, namun memerlukan cara yang cukup kompleks. Kata kunci: Triangular Atas, Triangular Bawah, Dekomposisi LU, Metode Doolittle, Metode Crout.

1 PENDAHULUAN Matematika adalah ilmu pasti yang hingga kini sesuai dengan perkembangannya telah mengalami perkembangan yang sangat pesat, yaitu dengan dikembangkannya oleh para ilmuwan di seluruh dunia yang mempunyai persepsi yang cukup berbeda. Mungkin ketika di SMU, kita hanya diajarkan materi dengan beberapa kasus serta cara penyelesaian yang belum terlalu kompleks, sehingga ketika bertemu dengan kasus yang sangat kompleks maka tidaklah efektif jika diselesaikan dengan cara yang sederhana. Oleh karena itu di dalam perkuliahan kita diajarkan cara penyelesaian yang mungkin dapat efektif dan efisien ketika kita ingin menyelesaikan suatu permasalahan yang sangat kompleks. Dalam hal ini, peranan para ilmuwan sangatlah penting. Seiring dengan kemajuan jaman yang semakin canggih kemampuan berfikir dan rasa ingin tahu serta kemampuan mengembangkan suatu teori beserta cara penyelesaian dari beberapa kasus yang kompleks dapat diselesaikan dengan lebih efektif dan efisien daripada dengan cara yang sederhana yang memerlukan banyak waktu, tenaga, dan pikiran. Dekomposisi LU adalah suatu metode penyelesaiaan sistem persamaan aljabar linier

serentak ordo tinggi secara efektif, efisien, dan dengan hasil yang sangat mendekati nilai eksaknya. Ada 2 metode untuk menyelesaikan dekomposisi LU, yaitu metode Doolittle dan metode Crout. Permasalahannya, “Apakah terdapat kesamaan hasil, dari 2 metode ini, dalam menyelesaikan persamaan linier simultan?”

2 LANDASAN TEORI Teori 1 : Prinsip Dekomposisi LU dan Matriks Identitas. Matriks [A] dari SPAL didekomposisi (difaktorisasis) menjadi matriks-matriks Lower Triangular (L) dan Upper Triangular (U) sedemikian rupa sehingga matrik identitasnya adalah: [A] = [L]·[U] atau A = L·U. Bila persamaan linear [A]{x} = (b), maka mengisikan matriks [A] dengan [L][U] menghasilkan [L][U]{x} = (b) Berarti terdapat dua sistem [L]{z}=(b) untuk mencari {z}, dan [U]{x}={z} untuk memperoleh {x}. Algoritma proses dekomposisi LU: 1. Mendapatkan matriks [L] dan [U]. 2. Menyelesaikan [L]{z} = (b). 3. Menyelesaikan [U]{x} = {z}

Teori 2 : Notasi Matriks LU berdasarkan

Teori 3 : Notasi Matriks LU berdasarkan

Metode Doolittle. Notasi matriks L dan U seperti di atas dituliskan sebagai berikut:

Metode Crout. Notasi matriks L dan U seperti di atas dituliskan sebagai berikut: 𝑎11 𝑎12 𝑎13 … 𝑎1𝑛 𝑎21 𝑎22 𝑎23 … 𝑎2𝑛 𝑎31 𝑎32 𝑎33 … 𝑎3𝑛 = ⋮ ⋮ ⋮ ⋱ ⋮ 𝑎𝑛1 𝑎𝑛2 𝑎𝑛3 … 𝑎𝑛𝑛 𝑙11 𝟎 𝟎 … 𝟎 𝑙21 𝑙22 𝟎 … 𝟎 𝑙31 𝑙32 𝑙33 ⋯ 𝟎 ⋮ ⋮ ⋮ ⋱ ⋮ 𝑙𝑛1 𝑙𝑛2 𝑙𝑛3 ⋯ 𝑙𝑛𝑛 𝟏 𝑢12 𝑢13 … 𝑢1𝑛 𝟎 𝟏 𝑢23 … 𝑢2𝑛 𝟎 𝟎 𝟏 ⋯ 𝑢3𝑛 ⋮ ⋮ ⋮ ⋱ ⋮ 𝟎 𝟎 𝟎 ⋯ 𝟏

𝑎11 𝑎12 𝑎13 … 𝑎1𝑛 𝑎21 𝑎22 𝑎23 … 𝑎2𝑛 𝑎31 𝑎32 𝑎33 … 𝑎3𝑛 = ⋮ ⋮ ⋮ ⋱ ⋮ 𝑎𝑛1 𝑎𝑛2 𝑎𝑛3 … 𝑎𝑛𝑛 𝟏 𝟎 𝟎 … 𝟎 𝑙21 𝟏 𝟎 … 𝟎 𝑙31 𝑙32 𝟏 ⋯ 𝟎 ⋮ ⋮ ⋮ ⋱ ⋮ 𝑙𝑛1 𝑙𝑛2 𝑙𝑛3 ⋯ 𝟏 𝑢11 𝑢12 𝑢13 … 𝑢1𝑛 𝟎 𝑢22 𝑢23 … 𝑢2𝑛 𝟎 𝟎 𝑢33 ⋯ 𝑢3𝑛 ⋮ ⋮ ⋮ ⋱ ⋮ 𝟎 𝟎 𝟎 ⋯ 𝑢𝑛𝑛 Jelas bahwa semua elemen diagonal dari matriks L di atas berharga 1 (satu), dan juga bahwa semua elemen yang terletak di bawah diagonal matriks U di atas (=𝑢1,1 …𝑢𝑛 ,𝑛 ) berharga 0 (nol). Notasi A = LU dalam Metode Doolittle seperti di atas dapat diuraikan dalam operasi perkalian matriks (sebagai contoh: matriks n x n) sebagai berikut: Baris 1 (i = 1): 𝒂𝟏,𝟏 = 𝒖𝟏,𝟏 𝒂𝟏,𝟐 = 𝒖𝟏,𝟐 ⋮ ⋮ 𝒖𝟏,𝒊 = 𝒂𝟏,𝒊 ; i=1,…,n 𝒂𝟏,𝒏 = 𝒖𝟏,𝒏 Baris 2 (i = 2): 𝑎2,1 = 𝑙2,1 · 𝑢1,1 𝑎2,2 = 𝑙2,1 · 𝑢1,2 + 𝑢2,2 𝑎2,3 = 𝑙2,1 · 𝑢1,3 + 𝑢2,3 ⋮ ⋮ 𝑎2,𝑛 = 𝑙2,1 · 𝑢1,𝑛 + 𝑢2,𝑛 Baris 3 (i = 3): 𝑎3,1 𝑎3,2 𝑎3,3 ⋮ 𝑎3,𝑛

= 𝑙3,1 · 𝑢1,1 = 𝑙3,1 · 𝑢1,2 + 𝑙3,2 · 𝑢2,2 = 𝑙3,1 · 𝑢1,3 + 𝑙3,2 · 𝑢2,3 + 𝑢3,3 ⋮ = 𝑙3,1 · 𝑢1,𝑛 + 𝑙3,2 · 𝑢2,𝑛 + 𝑢3,2

Baris n (i = n): 𝑎𝑛 ,1 = 𝑙𝑛,1 · 𝑢1,1 𝑎𝑛 ,2 = 𝑙𝑛,1 · 𝑢1,2 + 𝑙𝑛,2 · 𝑢2,2 𝑎𝑛 ,3 = 𝑙𝑛,1 · 𝑢1,3 + 𝑙𝑛,2 · 𝑢2,3 + 𝑙𝑛 ,3 · 𝑢3,3 ⋮ ⋮ 𝑎𝑛 ,𝑛−1 = 𝑙𝑛 ,1 · 𝑢1,𝑛−1 + 𝑙𝑛 ,2 · 𝑢2,𝑛−1 + 𝑙𝑛 ,3 · 𝑢3,𝑛−1 + … + 𝑙𝑛 ,𝑛−1 · 𝑢𝑛 −1,𝑛−1 𝑎𝑛 ,𝑛 = 𝑙𝑛 ,1 · 𝑢1,𝑛 + 𝑙𝑛 ,2 · 𝑢2,𝑛 + 𝑙𝑛,3 · 𝑢3,𝑛 + … + 𝑢𝑛,𝑛

Jelas bahwa semua elemen diagonal dari matriks L di atas tidak harus berharga 1 (satu), sedangkan, elemen-elemen di atas diagonal semuanya berharga 0 (nol) dan juga bahwa semua elemen diagonal (=𝑢1,1 … 𝑢𝑛,𝑛 ) berharga 1 (satu), sedangkan yang terletak di bawahnya berharga 0 (nol).

3. METODE PENELITIAN Metode pada penelitian ini adalah dengan secara langsung menguji atau menyelesaikan soal-soal persamaan linier untuk membuktikan kebenaran daripada tujuan dari metode Dekomposisi LU ini. Sebagai contoh, ditinjau dari proses dekomposisi LU untuk menyelesaikan persamaan:

1. Metode Dolittle 5𝑥1 + 4𝑥2 + 2𝑥3 = 5 -3𝑥1 − 4𝑥2 + 𝑥3 = -1 2𝑥1 − 𝑥2 + 3𝑥3 = 5 Dalam bentuk matriks : 5 4 2 𝑥1 5 −3 −4 1 𝑥2 = −1 2 −1 3 𝑥3 5 untuk proses dekomposisi menggunakan: 5 4 2 −3 −4 1 2 −1 3 Proses membentuk matrik [U] secara simultan diikuti dengan pembentukan matrik [L] pengali 𝑚𝑖𝑘 = 𝑎𝑖𝑘 / 𝑎𝑘𝑘 5 4 2 −3 −4 1 2 −1 3

kemudian 𝑟2 - 𝑟1 (-3/5) → sebagai pengali → menjadi 𝐿21 , dan 𝑟3 - 𝑟1 (2/5) → sebagai pengali → menjadi 𝐿31 , maka 5 4 2 [U] menjadi 0 −1.6 2.2 kemudian 𝑟3 0 −2.6 2.2 𝑟2 (-2.6/-1.6) → sebagai pengali → menjadi 𝐿32 , maka 5 4 2 [U] menjadi 0 −1.6 2.2 0 0 −1.375 Untuk mencari [L] : 1 0 0 Anggap [L] = 𝑥 1 0 𝑦 𝑧 1 untuk mencari nilai x,y, dan z yaitu menggunakan notasi [A] = [L]·[U] dimana, 5 4 2 −3 −4 1 = 2 −1 3 1 0 0 5 4 2 𝑥 1 0 0 −1.6 2.2 𝑦 𝑧 1 0 0 −1.375 Jadi nilai x, y, dan z yaitu -0.6, 0.4 dan 1.625 1 0 0 −0,6 1 0 0.4 1.625 1 Penyelesaian persamaan: a) [L]·{z}=(b) 1 0 0 𝑧1 5 −0.6 1 0 𝑧2 = −1 0.4 1.625 1 𝑧3 5 𝑧1 5 𝑧2 = 2 𝑧3 −0.25 b) [U]·{x} ={z} 𝑥1 5 4 2 5 𝑥 0 −1.6 2.2 2 2 = 0 0 −1.375 𝑥3 −0.25 𝒙𝟏 𝟏. 𝟕𝟐𝟕𝟑 𝒙𝟐 = −𝟏. 𝟎𝟎 𝒙𝟑 𝟎. 𝟏𝟖𝟏𝟖

2. Metode Crout 5𝑥1 + 4𝑥2 + 2𝑥3 = 5 -3𝑥1 − 4𝑥2 + 𝑥3 = -1 2𝑥1 − 𝑥2 + 3𝑥3 = 5 Dalam bentuk matriks : 5 4 2 𝑥1 5 −3 −4 1 𝑥2 = −1 2 −1 3 𝑥3 5 untuk proses dekomposisi menggunakan: 5 4 2 −3 −4 1 2 −1 3

Proses membentuk matrik [L] secara simultan diikuti dengan pembentukan matrik [U] pengali 𝑚𝑖𝑘 = 𝑎𝑖𝑘 / 𝑎𝑘𝑘 5 4 2 −3 −4 1 kemudian c2 - c 1 (4/5) → 2 −1 3 sebagai pengali → menjadi 𝐾21 dan c3 - c 1 (2/5) → sebagai pengali → menjadi 𝐾31 , maka 5 0 0 [L] menjadi −3 −1.6 2.2 kemudian 𝑐3 2 −2.6 2.2 𝑐2 (2.2/-1.6) → sebagai pengali → menjadi 𝐾32 , maka 5 0 0 [L] menjadi −3 −1.6 0 2 −2.6 −1.375 Untuk mencari [U] : 1 𝑥 𝑦 Anggap [U] = 0 1 𝑧 0 0 1 untuk mencari nilai x, y, dan z yaitu menggunakan notasi [A] = [L]·[U] dimana, 5 4 2 5 0 0 −3 −4 1 = −3 −1.6 0 2 −1 3 2 −2.6 −1.375 1 𝑥 𝑦 0 1 𝑧 0 0 1 Jadi nilai x,y, dan z yaitu 0.8, 0.4 dan -1.675 1 0.8 0.4 0 1 −1.375 0 0 1 Penyelesaian persamaan: a) [L]·{z}=(b) 𝑧1 5 0 0 5 𝑧 −3 −1.6 0 2 = −1 2 −2.6 −1.375 𝑧3 5 𝑧1 1 𝑧2 = −1.25 𝑧3 0.1818 b) [U]·{x} ={z} 𝑥1 1 0.8 0.4 1.7273 0 1 −1.375 𝑥2 = −1.00 𝑥3 0 0 1 0.1818 𝒙𝟏 𝟏. 𝟕𝟐𝟕𝟑 𝒙𝟐 = −𝟏. 𝟎𝟎 𝒙𝟑 𝟎. 𝟏𝟖𝟏𝟖

4 ALGORITMA MATEMATIS Dari operasi-operasi perkalian matriks LU pada metode Doolittle di atas, dapat disimpulkan beberapa hal berikut: 1. Ubah persamaan linier ke dalam bentuk matriks 2. Membentuk matrik [L] terlebih dahulu secara simultan diikuti dengan

3.

4.

pembentukan matrik [U] pengali 𝑚𝑖𝑘 = 𝑎𝑖𝑘 / 𝑎𝑘𝑘 Setelah matriks [L] dan [U] terbentuk, lalu mencari nilai z dengan persamaan [L].{z}={b} Kemudian mencari nilai akhir (x) dengan menggunakan persamaan [U].{x}={z}.

Sedangkan dari operasi-operasi perkalin matriks LU pada metode Crout di atas, dapat disimpulkan beberapa hal berikut: 1. Ubah persamaan linier ke dalam bentuk matriks 2. Membentuk matrik [U] terlebih dahulu secara simultan diikuti dengan pembentukan matrik [L] pengali 𝑚𝑖𝑘 = 𝑎𝑖𝑘 / 𝑎𝑘𝑘 3. Setelah matriks [U] dan [L] terbentuk, lalu mencari nilai z dengan persamaan [L].{z}={b} 4. Kemudian mencari nilai akhir (x) dengan menggunakan persamaan [U].{x}={z}.

5 ALGORITMA PROGRAM Algoritma penyelesaian persamaan simultan linier dengan metode dekomposisi LU menggunakan Matlab. (1) Kode Matlab untuk metode Eliminasi Gauss-Jordan adalah seperti di bawah ini :

[m,n]=size (A); L=eye (m,n); U=A; if m~=n error('matrik tidak sangkar') end; for k=1 :(n-1) for i= (k+1) :n if U (k,k)~=0

bujur

pengali=U(i,k)/U(k,k); L(i,k)=pengali; U(i,k)=0; end for j= (k+1):n U(i,j)=U(i,j)pengali*U(k,j); end; if jejak ==1 U L pause end; end; end; Penerapan dalam Soal 5 4 2 −3 −4 1 2 −1 3

𝑥1 5 𝑥2 = −1 𝑥3 5

>> A=[5,4,2;-3,-4,1;2,-1,3] function x = ElimGaussJordan (A,B,jejak) [n n] = size (A); A = [A';B']'; X = zeros(n,1); for p = 1:n, for k = [1:p-1,p+1:n], if A(p,p)==0, break, end pengali = A(k,p)/A(p,p); A(k,:) = A(k,:) pengali*A(p,:); A(k,:)=A(k,:)/A(k,k); if jejak==1 % untuk menampilkan langkah demi langkah dari proses A pause end end end x = A(:,n+1); % mendapatkan nilai x

(2) Kode Matlab untuk dekomposisi LU adalah seperti di bawah ini : function [L,U]=DekomLU (A,jejak)

A = 5 4 -3 -4 2 -1 >> b=[5;-1;5]

2 1 3

b = 5 -1 5 >> [L,U]=DekomLU(A,0) L = 1.0000 -0.6000 0.4000 U =

0 1.0000 1.6250

0 0 1.0000

5.0000 0 0

4.0000 -1.6000 0

2.0000 2.2000 -1.3750

>> z=ElimGaussJordan(L,b,0)

z = 5.0000 2.0000 -0.2500 >> x=ElimGaussJordan(U,z,0) x = 1.7273 -1.0000 0.1818

6 PENUTUP Dalam penggunaan kedua metode tersebut terbukti, baik metode Doolittle maupun metode Crout terdapat kesamaan hasil dalam penyelesaian persamaan linier simultan. Jadi kita dapat menggunakan kedua metode tersebut dalam SPAL. Kelemahan dari kedua metode tersebut adalah caranya sangat kompleks.

DAFTAR PUSTAKA [1] Choiron,Mochammad Agus,ST.,MT. http://mesin.brawijaya.ac.id/diktat_ajar/da ta/01_e_bab3_anum.pdf,Persamaan Aljabar linier serentak.26 November 2008,8:39 AM [2] Dr. Ir. Setijo Bismo, DEA.http://www.chemeng.ui.ac.id/~bism o/S2/mtks2/modul-2.pdf,Modul Sistem Persamaan Aljabar Linier.21 November 2008,10:48 AM [3] Nasution, Amrinsyah; Hasballah Zakaria. 2001.Metode Numerik dalam Ilmu Rekayasa Sipil. ITB.Bandung