Penyelesaian SPL Menggunakan Python: Dekomposisi LU (bag. 1)
Pada seri artikel ini akan dibahas salah satu metode dalam menyelesaikan Sistem Persamaan Linear (SPL), yakni Dekomposisi LU. Artikel ini dibagi menjadi 3 bagian: (1) proses faktorisasi, (2) proses forward and backward substitution, dan (3) Dekomposisi LU menggunakan pivoting.
Persamaan linear merupakan persamaan yang mengandung perkalian antara konstanta dengan suatu variabel tunggal sehingga jika digambarkan di koordinat Kartesius akan membentuk garis lurus. Contoh dari suatu persamaan linear adalah sebagai berikut:
Sedangkan jika persamaan linear tersebut bergabung dengan persamaan linear lain dengan variabel yang sama, maka akan membentuk yang kita sebut sebagai sistem persamaan linear.
Sistem di atas disebut sebagai sistem persamaan linear tiga variabel karena memuat 3 variabel: x, y, dan z. Tiga variabel inilah yang akan kita cari nilainya yang mana disebut sebagai solusi sistem linear. Dari Wikipedia, kita mengetahui solusi untuk sistem di atas adalah x=1, y=-2, dan z=-2.
Secara umum, SPL yang mengandung n persamaan untuk n buah variabel xᵢ yang tidak diketahui, sistem ini dapat digeneralisasi sebagai berikut:
SPL ini kemudian dapat kita sederhanakan menjadi bentuk matriks A . x = b, dimana nilai dari matriks A, vektor x, dan vektor b adalah sebagai berikut:
Salah satu metode yang dapat digunakan untuk menentukan nilai dari vektor x adalah dengan metode Dekomposisi LU.
Sedikit berbeda dengan metode Newton-Raphson yang namanya diambil dari yang mengembangkan metode tersebut, metode Dekomposisi LU tidak dikembangkan pertama kali oleh Lu Bu dari Dinasti Han, tetapi pertama kali dikenalkan oleh Doolitle dan Crout yang dikembangkan dari metode Eliminasi Gauss (sumber).
Secara singkat, proses mendapatkan solusi menggunakan metode ini adalah sebagai berikut:
- A = LU : Faktorisasi matriks A menjadi matriks L dan matriks U
- Lt = b : Forward substitution untuk mendapatkan solusi t.
- Ux = t : Backward substitution untuk mendapatkan solusi x.
Faktorisasi Matriks A
Ternyata, nama ‘LU’ diambil karena metode ini melakukan faktorisasi matriks A menjadi dua matriks: matriks segitiga bawah L (lower) dan matriks segitiga atas U (upper) yang memiliki dimensi yang sama dengan matriks A.
Disini kita akan melakukan faktorisasi matriks A menggunakan metode Crout. Untuk menyederhanakan, kita tinjau matriks L,U, dan A dengan ukuran 3 x 3 yang memenuhi persamaan berikut:
Dari persamaan di atas, maka kita dapat memperoleh nilai untuk masing-masing matriks L dan matriks U dengan langkah sebagai berikut (sumber):
- Untuk baris pertama U diperoleh dari:
- Untuk kolom pertama L diperoleh dari:
- Untuk baris kedua U diperoleh dari:
- Untuk kolom kedua L diperoleh dari:
- Dan terakhir, baris ketiga U diperoleh dari:
Jika diperhatikan, maka kita akan melihat pola untuk membuat rumus umum penentuan nilai elemen matriks U dan matriks L sebagai berikut:
dengan p=1, 2, 3, … n dan j=p, p+1, p+2, … n ,
dengan q=1, 2, 3, … n-1 dan i=q+1, q+2, … n. Untuk rumus umum matriks L disini perlu diperhatikan terdapat syarat dimana penyebut tidak boleh sama dengan 0.
Proses mendapatkan solusi dari SPL setelah mendapatkan matriks L dan U akan dilanjutkan di artikel berikutnya. Namun sebelum itu, kita akan coba implementasikan konsep faktorisasi ini ke Python.
Implementasi Python
Misalkan kita akan menemukan solusi dari SPL berikut yang telah ditampilkan di atas.
Terlebih dahulu kita akan buat SPL tersebut menjadi dalam bentuk persamaan matriks.
dimana x₁=x, x₂=y, dan x₃=z. Kita akan menyimpan matriks A dan vektor b di Python menggunakan array.
# declaration for matrix A
A = [[3, 2, -1],
[2, -2, 4],
[-1, 0.5, -1]]# declaration for vector b
b= [1, -2, 0]
***
Note: Untuk mempermudah kita dalam melakukan pengecekan nilai matriks, kita akan membuat fungsi show() untuk menampilkan nilai matriks.
# create function to show element of matrix
def show(matrix):
n = len(matrix)
for row in range(n):
for col in range(n):
print('%.2f' % matrix[row][col], end="\t")
print("")show(A)
***
Faktorisasi matriks A yang berdimensi n x n dapat dilakukan dengan terlebih dahulu membuat matriks U dan L sebagai matriks 0 berdimensi n x n.
# get number of rows from A
n = len(A)# create zeros matrix of L and U
L = [[0 for row in range(n)]
for col in range(n)]
U = [[0 for row in range(n)]
for col in range(n)]
Selanjutnya, kita akan melakukan faktorisasi berdasarkan rumus umum yang telah kita peroleh sebelumnya untuk menentukan nilai matriks U dan nilai matriks L. Agar pembaca mudah dalam membandingkan kode dan rumus umum, disini saya akan menggunakan indeks yang sama dengan yang ditampilkan di rumus umum.
Pertama kita akan menggunakan iterasi yang mengikuti indeks p pada rumus umum matriks U. Kemudian bergerak dengan mengikuti indeks j yang dimulai dari nilai p saat itu. Seperti yang dapat dilihat pada rumus umum, terdapat penjumlahan nilai dari perkali L(p,k) dan U(k,j). Kita akan menghitungan hasil dari penjumlahan ini yang kemudian akan digunakan pada rumus umum U.
for p in range(n):
# upper matrix
for j in range(p,n):
# summation of L(p,k)*U(k,j)
sum = 0
for k in range(p):
sum = sum + L[p][k]*U[k][j]
U[p][j] = A[p][j] - sumProses ini hanya dapat dilakukan untuk nilai p=1 (atau pada Python p=0), karena disini kita membutuhkan nilai matriks L yang baru diketahui hanya pada baris pertama (1, 0, 0, … 0). Oleh karena itu, kita akan lanjutkan dengan penentuan nilai matriks L.
Indeks q pada rumus umum matriks L akan menggunakan nilai yang sama dengan indeks p sedangkan indeks i akan bergerak dari nilai q saat itu. Penjumlahan juga dilakukan seperti sebelumnya, namun untuk perkalian nilai L(i,k) dan U(k,q).
# lower matrix
q = p
for i in range (q,n):
if (i==q):
# diagonal of L
L[i][q]=1
else:
# summation of L(i,k)*U(k,q)
sum = 0
for k in range(q):
sum = sum + L[i][k]*U[k][q]
L[i][q] = (A[i][q] - sum)/U[q][q]Dengan menambahkan implementasi rumus umum matriks U dan L tersebut ke kode sebelumnya lalu dibungkus dalam satu fungsi decomposition(), maka kita akan memperoleh kode sebagai berikut.
def decomposition(A):
# get number of rows from A
n = len(A) # create zeros matrix of L and U
L = [[0 for row in range(n)]
for col in range(n)]
U = [[0 for row in range(n)]
for col in range(n)]
for p in range(n):
# upper matrix
for j in range(p,n):
# summation of L(p,k)*U(k,j)
sum = 0
for k in range(p):
sum = sum + L[p][k]*U[k][j]
U[p][j] = A[p][j] - sum # lower matrix
q = p
for i in range (q,n):
if (i==q):
# diagonal of L
L[i][q]=1
else:
# summation of L(i,k)*U(k,q)
sum = 0
for k in range(q):
sum = sum + L[i][k]*U[k][q]
L[i][q] = (A[i][q] - sum)/U[q][q] return L, U
Untuk memanggil fungsi ini dan mengimplementasikannya pada matriks A. Kita akan gunakan kode berikut.
# matrix A
A = [[3, 2, -1],
[2, -2, 4],
[-1, 0.5, -1]]# calculate L and U
L, U = decomposition(A)# show L and U
print("Matrix L :")
show(L)print("\nMatrix U :")
show(U)
Hasil yang dioleh untuk matriks L dan matriks U adalah sebagai berikut:
Matrix L :1.00 0.00 0.00
0.67 1.00 0.00
-0.33 -0.35 1.00Matrix U :3.00 2.00 -1.00
0.00 -3.33 4.67
0.00 0.00 0.30
Konklusi
Kita telah sampai pada proses hingga mendapatkan dekomposisi A menjadi matriks L dan matriks U. Untuk menguji apakah faktorisasi LU yang kita lakukan sudah benar atau belum, kita dapat mengalikan matriks L dan matriks U secara dot product. Apabila hasilnya sama dengan matriks A, maka faktorisasi sudah berjalan dengan benar.
Pada artikel selanjutnya, kita akan membahas proses forward substitution yang memanfaatkan matriks L hasil dari dekomposisi dan proses backward substitution yang memanfaatkan matriks U untuk memperoleh solusi dari SPL
Baca artikel selanjutnya:
- Penyelesaian SPL Menggunakan Python: Dekomposisi LU (bag. 2)
