Penyelesaian SPL Menggunakan Python: Dekomposisi LU (bag. 2)
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.
Pada artikel sebelumnya (bag. 1) kita telah membahas bagaimana untuk suatu matriks A yang berdimensi n x n dapat dilakukan faktorisasi, menghasilkan matrik segitiga bawah L dan matriks segitiga atas U.
Pada artikel ini kita akan melanjutkan ke pembahasan mengenai forward substitution dan backward substitution yang merupakan proses lanjutan setelah kita berhasil melakukan faktorisasi pada matriks A.
Forward Substitution
Tinjau kembali persamaan matriks utama di atas. Dengan substitusi nilai matriks L dan matriks U ke matriks A, maka kita akan mendapatkan:
Untuk menentukan nilai x, terlebih dahulu kita akan mencari nilai vektor t yang didefinisikan sebagai berikut:
Kita dapat dengan mudah menentukan nilai vektor t dengan menggunakan operasi forward substitution karena untuk nilai matriks L di atas diagonal bernilai 0 dan untuk diagonalnya bernilai 1.
Kita dapat mulai mengalikan matriks L dan vektor t dari baris pertama kolom L dimana diperoleh persamaan t₁=b₁. Kemudian untuk baris kedua diperoleh l₂₁t₁+t₂=b₂, yang jika dilakukan pindahkan ruaskan akan diperoleh nilai t₂ dari nilai t₁ yang telah diketahui sebelumnya.
Jika diteruskan hingga baris ke-n, maka kita akan memperoleh pola sebagai berikut:
Backward Substitution
Nah, setelah nilai dari vektor t diketahui seluruhnya, kita akan lakukan pencarian nilai vektor x. Perhatikan bahwa nilai t dapat ditulis sebagai berikut:
Berbeda dengan cara sebelumnya untuk menentukan nilai vektor x, kita menggunakan backward substitution karena bagian matriks U dari diagonal hingga ke bawah bernilai 0 maka akan lebih mudah jika perhitungan dimulai dari baris ke-n lalu n-1, n-2, dan seterusnya.
Untuk baris ke-n, n-1, dan n-2 kita dapatkan persamaan sebagai berikut:
Sehingga jika dilakukan operasi aljabar biasa, maka kita dapat menentukan nilai dari elemen vektor x dengan melihat pola dari persamaan tersebut sebagai berikut:
Implementasi Python
Sebelum menambahkan fungsi forward substitution dan backward substitutuion, kita akan tampilkan terlebih dahulu SPL yang akan kita selesaikan beserta hasil faktorisasi LU dari matriks A.
Fungsi forward substitution digunakan untuk menentukan nilai dari vektor t. Oleh karena itu, pertama kita akan mendeklarasikan vektor t sebagai vektor berelemen 0 dengan panjang yang sama dengan vektor b.
Dengan menggunakan rumus umum untuk penentuan nilai dari elemen vektor t di atas, kita dapat mulai iterasi yang mengikuti indeks i yang bergerak hingga n. Kemudian kita akan menghitung penjumlahan dari hasil perkalian antara elemen L(i,j) dan t(j) dimana indeks j bergerak dari 1 hingga i-1.
Berikut merupakan fungsi untuk mengimplementasikan forward substitution dengan parameter input berupa vektor b dan matriks L yang sudah didapatkan sebelumnya.
# forward substitution
def forward_subs(b,L):
n = len(b)
t = [[0 for row in range(n)]
for col in range(n)] for i in range(n):
sum = 0
for j in range(i):
sum = sum + L[i][j]*t[j]
t[i] = b[i] - sum
return t
Fungsi di atas akan mengembalikan nilai dari vektor t. Hasil dari fungsi ini akan digunakan bersamaan dengan matriks U sebagai parameter input fungsi backward substitution.
Pada fungsi ini, kita akan mendapatkan nilai dari vektor x yang merupakan solusi dari SPL. Untuk itu terlebih dahulu kita akan buat vektor x yang berisikan nilai 0 dengan panjang n yang sama dengan vektor t.
Berbeda dengan fungsi sebelumnya, sesuai namanya fungsi ini bergerak dengan indeks i mundur dari n hingga 1. Penjumlahan juga dilakukan terlebih dahulu antara elemen U(i,j) dan x(j) dimana j dimulai dari i+1 hingga n. Lengkapnya dapat dilihat pada kode berikut:
# backward substitution
def backward_subs(t,U):
n = len(t)
x = [[0 for row in range(n)]
for col in range(n)] for i in range(n,0,-1):
sum = 0
for j in range(i,n):
sum = sum + U[i-1][j]*x[j]
x[i-1] = (1/U[i-1][i-1])*(t[i-1]-sum) return x
Pada loop backward, indeks i perlu dikurangi 1 langkah untuk menyesuaikan aturan indeks Python sehingga fungsi berjalan sesuai dengan yang kita harapkan.
Dengan fungsi di atas kita akan mendapatkan nilai vektor x. Tugas kita selanjutnya adalah menggabungkan ketiga fungsi ini sehingga dapat berjalan kontinu dari proses dekomposisi, forward substitution, hingga mendapatkan solusi di backward substitution.
def solve_LU(A,b):
n = len(A) # factorize matrix A
L,U = decomposition(A) # use vector b and matrix L for forward substitution
t = forward_subs(b,L) # use result above and matrix U for backward substitution
x = backward_subs(t,U)return x
Kita akan coba fungsi ini untuk mendapatkan solusi dari SPL kita di awal yang mana diketahui secara analitik memiliki solusi berturut-turut x₁, x₂, x₃ adalah 1, -2, dan -2.
# matrix A and vector b
A = [[3, 2, -1],
[2, -2, 4],
[-1, 0.5, -1]]b = [1,-2,0]# solve the system using function
x = solve_LU(A,b)# print the solution
for i in range(len(x)):
print('x_%d : %.2f' %(i+1,x[i]))
Dengan menjalankan kode di atas maka kita akan memperoleh hasil sebagai berikut yang sama dengan hasil yang diperoleh secara analitik.
x_1 : 1.00
x_2 : -2.00
x_3 : -2.00Konklusi
Kita telah mendapatkan solusi dari SPL menggunakan metode Dekomposisi LU seperti yang ditunjukkan di atas. Sangat disarankan pembaca mencoba sendiri dengan problem SPL yang berbeda dan dimensi yang lebih besar.
Salah satu sistem yang patut dicoba adalah SPL berikut.
Metode analitik sederhana dapat kita terapkan dengan mudah sehingga mendapat solusi yakni x=y=z=1. Tetapi apabila kita terapkan pada fungsi yang telah kita buat di atas, maka akan menghasilkan error seperti berikut:
Dari keterangan error dapat jelas diketahui bahwa terdapat pembagian terhadap nol pada proses menentukan nilai elemen matriks L. Untuk menghindari error ini dapat diterapkan partial pivoting yang akan kita bahas di artikel selanjutnya.
Baca artikel sebelumnya:
- Penyelesaian SPL Menggunakan Python: Dekomposisi LU (bag. 1)
Baca artikel selanjutnya:
- Penyelesaian SPL Menggunakan Python: Dekomposisi LU (bag. 3)
