algoritma spl dengan dekomposisi lu_nuh akbar
DESCRIPTION
Nuh Akbar,[email protected],Universitas Gunadarma,Matematika,Tekni Sipil,Cariu,ALGORITMA DOOLITTLE DAN CROUTDALAM DEKOMPOSISI LU,METODE PENELITIAN,Metode Dolittle,Metode Crout,ALGORITMA MATEMATIS,5 ALGORITMA PROGRAM,: Triangular Atas, Triangular Bawah,Sistem Persamaan Aljabar LinierTRANSCRIPT
![Page 1: Algoritma Spl Dengan Dekomposisi Lu_nuh Akbar](https://reader031.vdokumen.com/reader031/viewer/2022012316/5571f2c749795947648d0a65/html5/thumbnails/1.jpg)
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: ¹[email protected], ²[email protected], ³[email protected]
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}
![Page 2: Algoritma Spl Dengan Dekomposisi Lu_nuh Akbar](https://reader031.vdokumen.com/reader031/viewer/2022012316/5571f2c749795947648d0a65/html5/thumbnails/2.jpg)
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
![Page 3: Algoritma Spl Dengan Dekomposisi Lu_nuh Akbar](https://reader031.vdokumen.com/reader031/viewer/2022012316/5571f2c749795947648d0a65/html5/thumbnails/3.jpg)
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
![Page 4: Algoritma Spl Dengan Dekomposisi Lu_nuh Akbar](https://reader031.vdokumen.com/reader031/viewer/2022012316/5571f2c749795947648d0a65/html5/thumbnails/4.jpg)
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 =
![Page 5: Algoritma Spl Dengan Dekomposisi Lu_nuh Akbar](https://reader031.vdokumen.com/reader031/viewer/2022012316/5571f2c749795947648d0a65/html5/thumbnails/5.jpg)
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
![Page 6: Algoritma Spl Dengan Dekomposisi Lu_nuh Akbar](https://reader031.vdokumen.com/reader031/viewer/2022012316/5571f2c749795947648d0a65/html5/thumbnails/6.jpg)
![Page 7: Algoritma Spl Dengan Dekomposisi Lu_nuh Akbar](https://reader031.vdokumen.com/reader031/viewer/2022012316/5571f2c749795947648d0a65/html5/thumbnails/7.jpg)