algoritma spl dengan dekomposisi lu_nuh akbar

ALGORITMA DOOLITTLE DAN CROUT

DALAM DEKOMPOSISI LU

Gatot Hardiyanto¹, Nuh Akbar², Resti Oktaviani³ 1,2,3Program Sarjana Magister Fakultas Ilmu Teknik Sipil Universitas Gunadarma

Kampus D, Gedung 2 Lantai 3

Jl. Margonda Raya 100 Depok 16424

e-mail: ¹gatmet@yahoo.com, ²smile.akbar@yahoo.co.id, ³resti.oktaviani@yahoo.com

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

Metode Doolittle. 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 … 𝑎𝑛𝑛

=

𝟏 𝟎 𝟎 … 𝟎𝑙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,1 · 𝑢1,1

𝑎3,2 = 𝑙3,1 · 𝑢1,2 + 𝑙3,2 · 𝑢2,2

𝑎3,3 = 𝑙3,1 · 𝑢1,3 + 𝑙3,2 · 𝑢2,3 + 𝑢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,𝑛 +

… + 𝑢𝑛 ,𝑛

Teori 3 : Notasi Matriks LU berdasarkan

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𝑛

⋮ ⋮ ⋮ ⋱ ⋮𝟎 𝟎 𝟎 ⋯ 𝟏

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−3 −4 12 −1 3

𝑥1

𝑥2

𝑥3

= 5−15

untuk proses dekomposisi menggunakan:

5 4 2−3 −4 12 −1 3

Proses membentuk matrik [U] secara simultan

diikuti dengan pembentukan matrik [L]

pengali 𝑚𝑖𝑘 = 𝑎𝑖𝑘 / 𝑎𝑘𝑘

5 4 2−3 −4 12 −1 3

kemudian 𝑟2 - 𝑟1(-3/5) → sebagai pengali →

menjadi 𝐿21 , dan 𝑟3 - 𝑟1(2/5) → sebagai

pengali → menjadi 𝐿31 , maka

[U] menjadi 5 4 20 −1.6 2.20 −2.6 2.2

kemudian 𝑟3-

𝑟2(-2.6/-1.6) → sebagai pengali → menjadi

𝐿32 , maka

[U] menjadi 5 4 20 −1.6 2.20 0 −1.375

Untuk mencari [L] :

Anggap [L] = 1 0 0𝑥 1 0𝑦 𝑧 1

untuk mencari nilai x,y, dan z yaitu

menggunakan notasi [A] = [L]·[U] dimana,

5 4 2−3 −4 12 −1 3

=

1 0 0𝑥 1 0𝑦 𝑧 1

5 4 20 −1.6 2.20 0 −1.375

Jadi nilai x, y, dan z yaitu -0.6, 0.4 dan 1.625

1 0 0

−0,6 1 00.4 1.625 1

Penyelesaian persamaan:

a) [L]·{z}=(b)

1 0 0

−0.6 1 00.4 1.625 1

𝑧1

𝑧2

𝑧3

= 5−15

𝑧1

𝑧2

𝑧3

= 52

−0.25

b) [U]·{x} ={z}

5 4 20 −1.6 2.20 0 −1.375

𝑥1

𝑥2

𝑥3

= 52

−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−3 −4 12 −1 3

𝑥1

𝑥2

𝑥3

= 5−15

untuk proses dekomposisi menggunakan:

5 4 2−3 −4 12 −1 3

Proses membentuk matrik [L] secara simultan

diikuti dengan pembentukan matrik [U]

pengali 𝑚𝑖𝑘 = 𝑎𝑖𝑘 / 𝑎𝑘𝑘

5 4 2−3 −4 12 −1 3

kemudian c2 - c 1 (4/5) →

sebagai pengali → menjadi 𝐾21 dan c3 - c 1

(2/5) → sebagai pengali → menjadi 𝐾31, maka

[L] menjadi 5 0 0−3 −1.6 2.22 −2.6 2.2

kemudian 𝑐3 -

𝑐2 (2.2/-1.6) → sebagai pengali →

menjadi 𝐾32, maka

[L] menjadi 5 0 0−3 −1.6 02 −2.6 −1.375

Untuk mencari [U] :

Anggap [U] = 1 𝑥 𝑦0 1 𝑧0 0 1

untuk mencari nilai x, y, dan z yaitu

menggunakan notasi [A] = [L]·[U] dimana,

5 4 2−3 −4 12 −1 3

= 5 0 0−3 −1.6 02 −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.40 1 −1.3750 0 1

Penyelesaian persamaan:

a) [L]·{z}=(b)

5 0 0−3 −1.6 02 −2.6 −1.375

𝑧1

𝑧2

𝑧3

= 5−15

𝑧1

𝑧2

𝑧3

= 1

−1.250.1818

b) [U]·{x} ={z}

1 0.8 0.40 1 −1.3750 0 1

𝑥1

𝑥2

𝑥3

= 1.7273−1.000.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

pembentukan matrik [U] pengali 𝑚𝑖𝑘

= 𝑎𝑖𝑘 / 𝑎𝑘𝑘

3. Setelah matriks [L] dan [U] terbentuk,

lalu mencari nilai z dengan persamaan

[L].{z}={b} 4. 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 :

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)

[m,n]=size (A); L=eye (m,n); U=A; if m~=n error('matrik tidak bujur sangkar') end; for k=1 :(n-1) for i= (k+1) :n if U (k,k)~=0 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 12 −1 3

𝑥1

𝑥2

𝑥3

= 5−15

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

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

5.0000 4.0000 2.0000 0 -1.6000 2.2000 0 0 -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