Penyelesaian SPL Menggunakan Python: Dekomposisi LU (bag. 3)
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.
Secara sederhana, kita telah membuat fungsi yang menjalankan metode Dekomposisi LU untuk menyelesaikan sistem persamaan linear (baca bag.1 dan bag. 2). Namun terdapat kasus khusus dimana dalam proses faktorisasi matriks A menjadi matriks L dan matriks U terjadi error yang diakibatkan pembagian oleh bilangan 0.
Di atas merupakan contoh SPL yang ditampilkan pada artikel sebelumnya yang jika kita terapkan fungsi Dekomposisi LU akan menghasilkan ZeroDivisionError.
Secara umum, kasus ini biasa terjadi apabila pada diagonal matriks A terdapat elemen bernilai 0 atau sangat kecil dibandingkan elemen lain di kolom yang sama. Pada kasus SPL di atas terjadi karena terdapat elemen pada diagonal matriks U (hasil faktorisasi matriks A) yang bernilai 0 sehingga perlu dilakukan penyesuaian pada matriks A. Untuk mensiasati hal ini, startegi yang dapat digunakan adalah dengan melakukan pivoting.
Strategi pivoting dapat dibagi menjadi dua macam, yakni pivoting sebagian dan pivoting lengkap. Pada pivoting sebagian proses penyesuaian pada matriks A adalah hanya dengan melakukan pertukaran baris, sedangan pada pivoting lengkap pertukaran kolom juga dilakukan. Pada artikel ini hanya akan dibahas partial pivoting saja yang lebih sering digunakan dibandingkan pivoting penuh.
Strategi Partial Pivoting
Ide utama dari strategi ini adalah menjamin agar tiap elemen diagonal suatu matriks tidak bernilai 0 atau bernilai sangat kecil. Namun untuk mengeneralisirnya kita dapat mengatur sedemikian rupa agar elemen diagonal merupakan elemen yang bernilai paling besar di antara elemen matriks lain di kolom yang sama.
Misalkan terdapat matriks A seperti persamaan di atas. Proses pivoting dimulai dari baris pertama dengan elemen diagonalnya di a₁₁. Kita harus menjamin bahwa a₁₁ merupakan elemen dengan nilai absolut terbesar untuk kolom 1. Caranya adalah dengan membandingkan a₁₁ dengan a₂₁ dan a₃₁. Jika misalkan a₂₁ lebih besar, maka lakukan pertukaran baris untuk seluruh elemen di baris ke-1 dan baris ke-2. Proses ini terus dilakukan untuk baris selanjutnya dengan elemen diagonal masing-masing namun perbandingan hanya dilakukan dengan baris-baris setelahnya. Hasil dari pertukaran baris ini kita misalkan dengan matriks Aₚ yang selanjutnya akan digunakan untuk melakukan faktorisasi LU.
Perlu diingat bahwa sistem persamaan linear tidak hanya terdiri dari matriks A saja, namun memiliki bentuk umum Ax=b. Oleh karena itu, apabila kita telah menyesuaikan matriks A maka akan berdampak pada sistem secara keseluruhan.
Untuk itu kita memerlukan satu matriks baru yaitu matriks P yang merupakan matriks identitas (matriks dengan diagonal bernilai 1) untuk menyimpan urutan pertukaran baris yang telah dilakukan. Ukuran dari matriks P adalah sama dengan ukuran dari matriks A. Sebagai contoh, matriks P yang digunakan untuk penyelesaian SPL dengan matriks A di atas adalah sebagai berikut.
Cara kerja dari matriks P ini adalah dengan mengikuti pertukaran baris yang dialami oleh matriks A. Dengan begitu apabila kita lihat kembali pada contoh matriks A di atas yang mengalami pertukaran baris menjadi matriks Aₚ, maka kita akan mendapatkan matriks P sebagai berikut:
Matriks P di atas akan kita sisipkan ke persamaan umum SPL sehingga:
Karena perkalian matriks PA dapat difaktorisasi menjadi matriks LU dan misalkan vaktor d merupakan hasil perkalian matriks Pb. Maka kita akan memperoleh persamaan baru sebagai berikut:
Jika dibandingkan dengan persamaan pada bag. 2, kita dapat melihat pola yang sama dimana kita dapat melakukan forward substitution namun kali ini menggunakan vektor d yang menggantikan vektor b sebelumnya. Setelah didapatkan nilai t, maka kita dapat memperoleh nilai x menggunakan backward substitution.
Implementasi Python
Kali ini kita cukup menambah satu fungsi yang akan disisipkan pada kode yang telah kita bangun sebelumnya. Kita akan beri nama fungsi ini sebagai pivot_matrix dengan inputan berupa matriks A dari SPL sebagai variabel matrix.
Hal pertama yang kita lakukan adalah dengan mendefinisikan matriks P yang berupa matriks identitas dengan dimensi yang sama dengan matriks A yaitu n x n.
n = len(matrix)
P = [[1 if row==col else 0 for row in range(n)]
for col in range(n)]Selanjutnya kita akan akan mengecek apakah elemen diagonal di tiap baris merupakan nilai terbesar di kolom yang sama. Untuk itu terlebih dahulu kita akan asumsikan bahwa elemen diagonal di baris i yang akan kita cek (ingat, elemen diagonal berarti ketika indeks baris sama dengan indeks kolom) sebagai nilai terbesar max.
Kemudian kita akan bergerak ke baris-baris selanjutnya (indeks k) untuk menguji apakah nilai absolut elemen di baris tersebut lebih besar dibandingkan nilai absolut variabel max. Jika benar, maka dilakukan pertukaran baris antara elemen di baris i dan elemen di baris k.
Proses pertukaran ini membutuhkan satu variabel sementara temp untuk menyimpan nilai-nilai di baris row sebelum digantikan oleh nilai-nilai di baris row2. Kemudian kita akan menggantikan nilai di baris row2 dengan nilai pada variabel temp.
Lakukan hal yang sama terhadap matriks P. Setelah proses pergantian baris ini dilakukan pada matriks A dan matriks P, kita akan memperbarui nilai max sebelumnya dengan nilai setelah dilakukan pertukaran baris.
Namun apabila saat melakukan pengecekan nilai elemen diagonal di baris k tidak lebih besar dari elemen diagonal di baris i, maka kita tidak perlu melakukan pertukaran baris. Apabila seluruh baris k hingga n telah dibandingkan dengan baris i, maka kita akan lanjutkan perbandingan terhadap baris ke-i+1 dan seterusnya hingga baris ke-(n-1) .
Berikut merupakan fungsi untuk melakukan pivoting matriks A yang mengembalikan nilai berupa hasil pivoting matriks dan matriks P yang digunakan.
def pivot_matrix(matrix):
# create identity matrix P
n = len(matrix)
P = [[1 if row==col else 0 for row in range(n)]
for col in range(n)] for i in range(n-1):
# let the diagonal element in row i has the largest value
max = matrix[i][i]
for k in range(i+1,n):
# compare value in column i
if (abs(A[k][i])>abs(max)):
# swap row i and row k for matrix
temp = matrix[i]
matrix[i] = matrix[k]
matrix[k] = temp # swap row i and row k for P
temp = P[i]
P[i] = P[k]
P[k] = temp max = matrix[i][i]
return matrix, P
Sebelum kita lanjutkan ke proses forward dan backward substitution, kita akan uji fungsi di atas untuk matriks sederhana. Salah satu penyebab gagalnya faktorisasi LU adalah terdapatnya nilai 0 pada elemen diagonal matriks A. Hal ini berlaku pada matriks A berikut:
Kita dapat membuktikan gagalnya faktorisasi dengan mengimplementasikan fungsi decomposition yang sudah dibuat pada bag. 1 yakni menghasilkan ZeroDivisionError. Oleh karena itu sebelum melakukan faktorisasi kita akan melakukan pivoting terlebih dahulu. Jalankan kode berikut untuk melakukan pivoting dan faktorisasi hasil pivoting dari matriks A.
A = [[0,1,2],
[1,2,3],
[3,1,2]]A,P = pivot_matrix(A)print('Matrix A after pivoting:')
show(A)print('\nMatrix P:')
show(P)L,U = decomposition(A)print('\nMatrix L:')
show(L)print('\nMatrix U:')
show(U)
note: Fungsi show() yang digunakan untuk menampilkan nilai matriks telah dijelaskan pada bag. 1.
Hasil dari menjalan kode di atas adalah sebagai berikut:
Matrix A after pivoting:
3.00 1.00 2.00
1.00 2.00 3.00
0.00 1.00 2.00Matrix P:
0.00 0.00 1.00
0.00 1.00 0.00
1.00 0.00 0.00Matrix L:
1.00 0.00 0.00
0.33 1.00 0.00
0.00 0.60 1.00Matrix U:
3.00 1.00 2.00
0.00 1.67 2.33
0.00 0.00 0.60
Dapat dilihat bahwa terjadi pertukaran baris pada matriks A yang menghasilkan matriks yang dapat difaktorisasi menjadi matriks L dan matriks U. Jika dijabarkan, proses pivoting yang terjadi sehingga menghasilkan matriks di atas adalah sebagai berikut:
A :
0.00 1.00 2.00
1.00 2.00 3.00
3.00 1.00 2.00*Check diagonal element in row 1Row 1 <-> Row 2
1.00 2.00 3.00
0.00 1.00 2.00
3.00 1.00 2.00Row 1 <-> Row 3
3.00 1.00 2.00
0.00 1.00 2.00
1.00 2.00 3.00*Check diagonal element in row 2Row 2 <-> Row 3
3.00 1.00 2.00
1.00 2.00 3.00
0.00 1.00 2.00
Setelah menjamin bahwa proses pivoting telah sesuai dengan yang diharapkan. Maka kita akan lanjutkan ke proses forward dan backward substitution. Secara umum, tidak ada perbedaan dengan fungsi yang telah dijelaskan pada bagian sebelumnya. Tetapi untuk kasus menggunakan pivoting, parameter vektor b yang digunakan pada fungsi forward substitution diganti dengan vektor d yang merupakan hasil perkalian dotantara matriks P dan vektor b.
import numpy as np# calculate vector d as dot product of P and b
d = np.dot(P,b)
Untuk melakukan hal ini, kita membutuhkan fungsi perkalian dot yang terdapat pada library numpy. Kode di atas akan kita sisipkan pada fungsi utama solve_LU() yang khusus untuk kasus menggunakan pivoting akan kita sebut sebagai solve_PLU(). Fungsi lengkapnya adalah sebagai berikut.
import numpy as npdef solve_PLU(A,b):
# do pivoting for matrix A
A, P = pivot_matrix(A) # factorize matrix A
L,U = decomposition(A) # calculate vector d as dot product of P and b
d = np.dot(P,b) # use vector d and matrix L for forward substitution
t = forward_subs(d,L) # use result from forward substitution and matrix U for backward substitution
x = backward_subs(t,U)return x
Akhirnya, disini kita akan kembali ke SPL di awal yang menjadi problem akibat munculnya ZeroDivisionError. Kita akan implementasikan fungsi dengan menggunakan pivoting di atas pada SPL tersebut.
# matrix A
A = [[-1, 1, 1],
[2, 2, 1],
[1, 1, -1]]b = [1,5,1]x = solve_PLU(A,b)
for i in range(len(x)):
print('x_%d : %.2f' %(i+1,x[i]) )
Dan… Ya. Kita peroleh hasil yang sesuai dengan menggunakan metode analitik, yakni:
x_1 : 1.00
x_2 : 1.00
x_3 : 1.00Konklusi
Phew.. Saya pikir awalnya membahas metode Dekomposisi LU akan memakan waktu yang sebentar dan saya dapat lanjut ke pembahasan numerik lainnya dengan cepat, ternyata membutuhkan hingga 3 artikel.
Proses pivoting disini penting dijelaskan karena dalam praktiknya tidak jarang ditemukan matriks yang tidak dapat langsung dilakukan faktorisasi LU. Terutama jika digunakan pada kesatuan proses numerik yang lebih besar atau simulasi sistem fisis tertentu, saya menyarankan untuk secara default menggunakan metode dengan pivoting agar kontinuitas perhitungan tidak terhambat.
Tujuan utama membuat sendiri fungsi seperti yang kita lakukan ini adalah having fun dan juga pembelajaran. Selain membuat sendiri fungsi untuk menyelesaikan SPL, untuk kebutuhan praktis kita juga dapat menggunakan fungsi yang sudah disediakan dari libary seperti NumPy dan SciPy. Penggunaannya dapat dilihat di artikel berikut:
Semoga semua having fun dan sampai ketemu di pembahasan metode numerik lainnya.
Baca artikel sebelumnya:
- Penyelesaian SPL Menggunakan Python: Dekomposisi LU (bag. 2)
