Dekomposisi LU adalah singkatan dari Lower-Upper decomposition atau dekomposisi Lower-Upper. Nama ini berasal dari dua matriks hasil dekomposisi:
L (Lower) = Matriks segitiga bawah yang memiliki elemen nol di atas diagonal utama
U (Upper) = Matriks segitiga atas yang memiliki elemen nol di bawah diagonal utama
Mengapa kita memerlukan dekomposisi ini? Karena menyelesaikan sistem persamaan linear dengan matriks segitiga jauh lebih mudah daripada dengan matriks biasa.
Dekomposisi LU adalah cara memecah matriks menjadi perkalian dua matriks yang lebih sederhana. Bayangkan kita memiliki teka-teki yang rumit, lalu kita bongkar menjadi kepingan-kepingan yang lebih mudah disusun kembali.
Untuk matriks A yang diberikan, kita mendapatkan:
P⋅A=L⋅U
Di mana P adalah matriks permutasi (pengatur urutan baris), L adalah matriks segitiga bawah, dan U adalah matriks segitiga atas.
Eliminasi Gauss menghitung dekomposisi LU ini melalui serangkaian operasi baris yang sistematis. Proses ini dapat dituliskan sebagai:
U=Lr⋅Pr⋅…⋅L3⋅P3⋅L2⋅P2⋅L1⋅P1⋅A
dengan i=1,…,r, matriks pertukaran baris Pi atau Pi=I dan matriks eliminasi:
Li=1⋱λi+1i⋮λmi⋱1
Invers dari Li adalah:
Li−1=1⋱−λi+1i⋮−λmi⋱1
Karena Pi−1=Pi, kita dapat menulis ulang rangkaian operasi ini menjadi bentuk yang lebih sederhana hingga akhirnya mendapatkan L−1⋅P⋅A=U.
Algoritma eliminasi Gauss bekerja seperti pembersihan sistematis. Untuk setiap kolom, kita melakukan:
Cari elemen pivot terbaik
Tukar baris jika perlu
Eliminasi elemen di bawah pivot
Simpan informasi multiplier
Kompleksitas waktu untuk menghitung dekomposisi LU adalah 31n3+O(n2) operasi aritmatika. Pembuktian menunjukkan bahwa perkalian dan penjumlahan terjadi bersamaan dalam transformasi baris eliminasi aij:=aij+λir⋅arl.
Berikut adalah implementasi algoritma dekomposisi LU dalam Python:
lu_decomposition.py
import numpy as npdef lu_decomposition(A): """ Melakukan dekomposisi LU dengan pemilihan pivot parsial Masukan: Matriks A (n x n) Keluaran: L, U, P (matriks Bawah, Atas, dan Permutasi) """ n = A.shape[0] U = A.copy().astype(float) L = np.zeros((n, n)) P = np.eye(n) for i in range(n): max_row = i for k in range(i + 1, n): if abs(U[k, i]) > abs(U[max_row, i]): max_row = k if max_row != i: U[[i, max_row]] = U[[max_row, i]] P[[i, max_row]] = P[[max_row, i]] if i > 0: L[[i, max_row], :i] = L[[max_row, i], :i] for k in range(i + 1, n): if U[i, i] != 0: factor = U[k, i] / U[i, i] L[k, i] = factor U[k, i:] = U[k, i:] - factor * U[i, i:] np.fill_diagonal(L, 1) return L, U, Pdef forward_substitution(L, b): """ Substitusi maju untuk menyelesaikan L * y = b """ n = len(b) y = np.zeros(n) for i in range(n): y[i] = b[i] - np.dot(L[i, :i], y[:i]) return ydef backward_substitution(U, y): """ Substitusi mundur untuk menyelesaikan U * x = y """ n = len(y) x = np.zeros(n) for i in range(n - 1, -1, -1): if U[i, i] != 0: x[i] = (y[i] - np.dot(U[i, i+1:], x[i+1:])) / U[i, i] return xdef solve_linear_system(A, b): """ Menyelesaikan sistem Ax = b menggunakan dekomposisi LU """ L, U, P = lu_decomposition(A) pb = np.dot(P, b) y = forward_substitution(L, pb) x = backward_substitution(U, y) return x, L, U, P
Algoritma substitusi maju menyelesaikan L⋅y=P⋅b dengan matriks segitiga bawah reguler L dan vektor c=P⋅b. Proses ini seperti mengisi tangga dari bawah ke atas, di mana setiap langkah bergantung pada langkah sebelumnya.
Untuk setiap baris i=1,…,m, kita menghitung:
yi:=lii1⋅(ci−j=1∑i−1lij⋅yj)
Algoritma ini efisien karena kita hanya perlu menghitung satu nilai di setiap langkah. Elemen diagonal lii selalu bernilai 1 untuk matriks L dari dekomposisi LU, sehingga pembagian menjadi sederhana.
Algoritma substitusi mundur menyelesaikan U⋅x=y dengan matriks U dalam bentuk baris bertingkat dengan r langkah pada kolom-kolom j1,…,jr dan vektor d=y.
Pertama, kita periksa apakah sistem dapat diselesaikan. Jika r<m dan terdapat di=0 untuk i∈{r+1,…,m}, maka sistem tidak memiliki solusi.
Jika sistem dapat diselesaikan, kita inisialisasi matriks kernel K dengan ukuran n×(n−r), dan mulai dengan k=0 serta i=r.
Algoritma bekerja mundur dari kolom j=n hingga j=1. Untuk setiap kolom, kita periksa apakah kolom tersebut adalah langkah pivot atau bukan.
Jika kolom j adalah langkah pivot, artinya j=ji untuk langkah ke-i, maka kita hitung solusi untuk variabel xj:
xj:=uij1⋅di−l=j+1∑nuil⋅xl
Dan kita juga hitung kontribusi variabel ini terhadap matriks kernel:
Kjq:=uij1⋅−l=j+1∑nuil⋅Klq
untuk q=1,…,n−r, kemudian kita kurangi i dengan 1.
Jika kolom j bukan langkah pivot, artinya tidak ada pivot pada kolom tersebut, maka variabel xj adalah variabel bebas. Kita set:
k:=k+1
xj:=0 (solusi khusus)
Algoritma ini menghasilkan solusi x dan matriks K yang memenuhi U⋅x=d dan U⋅K=0.
Kolom-kolom dari matriks K membentuk basis untuk kernel (ruang null) dari matriks U. Ini berarti bahwa setiap kolom K adalah vektor yang ketika dikalikan dengan U menghasilkan vektor nol.
Mari kita lihat bagaimana dekomposisi LU digunakan untuk menyelesaikan sistem linear secara konkret. Misalkan kita memiliki vektor b=433 dan ingin menyelesaikan sistem A⋅x=b.
Langkah pertama adalah menghitung c=P⋅b. Karena matriks permutasi P menukar baris pertama dengan baris kedua, kita mendapatkan:
c=P⋅b=010100001433=343
Langkah kedua adalah substitusi maju untuk menyelesaikan L⋅y=c. Kita menggunakan matriks segitiga bawah L yang sudah kita peroleh. Proses ini dilakukan dari atas ke bawah seperti mengisi tangga satu per satu.
Untuk baris pertama dengan l11=1, kita dapatkan .
Langkah ketiga adalah substitusi mundur untuk menyelesaikan U⋅x=y. Matriks U dalam bentuk baris bertingkat memiliki pivot pada kolom 1,2,4. Kolom 3 tidak memiliki pivot sehingga menjadi variabel bebas.
Dari proses substitusi mundur, kita memperoleh solusi khusus:
Interpretasi hasil sangat penting untuk dipahami. Solusi x adalah satu solusi khusus dari sistem persamaan. Matriks K menunjukkan arah di mana kita bisa bergerak dalam ruang solusi tanpa mengubah hasil perkalian A⋅x.
Verifikasi matematis menunjukkan bahwa untuk setiap nilai parameter t1, solusi umum x+K⋅t1 tetap memenuhi persamaan asli.
Mari kita buktikan dengan menghitung A⋅(x+K⋅t1). Hasilnya adalah:
Dibandingkan dengan menghitung dekomposisi LU secara penuh, proses substitusi maju dan mundur ini jauh lebih efisien untuk menyelesaikan sistem linear dengan vektor ruas kanan yang berbeda-beda.
Untuk baris kedua dengan l22=1, kita dapatkan y2=c2=4.
Untuk baris ketiga dengan l33=1, kita hitung:
y3=c3−l31⋅y1−l32⋅y2
=3−31⋅3−21⋅4
=3−1−2=0
Sehingga diperoleh:
y=L−1⋅c=340
x=−1200
dan matriks kernel:
K=1−210
A⋅(x+K⋅t1)=A⋅−1200+A⋅1−210⋅t1
=433+000⋅t1=b
Perhatikan bahwa A⋅K=0, yang berarti vektor K berada dalam ruang null dari matriks A. Ini menjelaskan mengapa menambahkan kelipatan K pada solusi tidak mengubah hasil.
