Dekomposisi LU
Contents
10. Dekomposisi LU#
Pada prinsipnya Eliminasi Gauss adalah teknik yang secara umum digunakan untuk menyelesaikan Sistem Persamaan Linear (SPL). Namun, waktu komputasi yang dibutuhkan oleh Eliminasi Gauss cenderung lama seiring bertambahnya ukuran matriks atau dapat dinotasikan \(O(n^3 /3)\). Hal ini banyak dipengaruhi oleh operasi aritmatika dari proses eliminasi yang terjadi di dalam Eliminasi Gauss. Dengan demikian, kita memerlukan suatu cara agar dapat meminimalkan waktu komputasi, salah satunya dengan melakukan dekomposisi matriks.
Diberikan suatu SPL yang dapat dibentuk dalam bentuk matriks-vektor sebagai berikut
dimana \(A \in \mathbb{R}^{n \times n}\) dan \(\vec{x}, \vec{b} \in \mathbb{R}^n\). Kemudian untuk menyelesaikan SPL tersebut, kita gunakan eliminasi Gauss tanpa pivoting dan kita asumsikan juga bahwa elemen pivot di \(A\) tak nol seiring berjalannya proses eliminasi pada setiap iterasinya, atau dapat ditulis \(a_{ii}^{(k)}\), untuk \(k = 1,2, ..., n\) dan \(i = 1,2,...,n\). Proses eliminasi pada iterasi pertama dilakukan dengan cara
atau operasi ini dapat direpresentasikan sebagai matriks transformasi Gaussian pertama
Sehingga, hasil perkalian matriks antara \(M^{(1)}\) dan \(A^{(1)}\) adalah
Secara umum, ketika kita melakukan perkalian matriks A dengan matriks transformasi Gaussian pada iterasi ke \(k\) akan menghasilkan
Proses ini akan berhenti pada \(A^{(n)} \vec{x} = \vec{b}^{(n)}\), dimana \(A^{(n)}\) menjadi matriks segitiga atas
diberikan oleh
Kemudian kita panggil kembali
dimana \(M^{(k)}\) dihasilkan dari operasi baris
Jika kita ingin mengembalikan nilai dari matriks \(A^{(k+1)} ke A^{(k)}\), maka kita perlu operasi balikan
berarti ini sama saja mencari invers dari matriks \(M\), \([M^{(k)}]^{-1}\). Dengan demikian, jika kita teruskan operasi invers ini sampai dengan iterasi pertama, maka akan menghasilkan matriks \(A\), dan operasi invers dari matriks \(M\) dapat kita tuliskan ekivalen dengan matriks segitiga bawah \(L\) atau dapat ditulis
Jadi, \(A\) dapat kita dekomposisi menjadi hasil kali dari matriks segitiga bawah \(L\) dan matriks segitiga atas \(U\), atau dapat ditulis
Teorema
Jika Eliminasi Gauss tanpa penukaran baris dapat digunakan untuk menyelesaikan \(A\vec{x} = \vec{b}\), maka matriks \(A\) dapat didekomposisi ke dalam perkalian matriks antara matriks segitiga bawah \(L\) dan matriks segitiga atas \(U\), \(A = LU\)
dimana \(m_{ji} = \frac{a_{ji}^{(i)}}{a_{ii}^{(i)}}\), untuk \(i,j = 1,2,\cdots, n\).
10.1. Dekomposisi LU untuk menyelesaikan SPL#
Algoritma:
Lakukan dekomposisi matriks \(A\) menjadi \(LU\): eliminasi maju untuk menghasilkan matriks \(U\) dan dalam proses ini juga kita akan mendapatkan matriks \(L\).
SPL \(A\textbf{x} = \textbf{b}\) menjadi \(L(U \textbf{x}) = \textbf{b}\) dan kita misalkan \(U \textbf{x} = y\) sehingga \(L \textbf{y} = \textbf{b}\). Selesaikan \(L \textbf{y} = \textbf{b}\) menggunakan subtitusi maju dan akan menghasilkan \(\textbf{y}\).
Selesaikan \(U \textbf{x} = y\) menggunakan subtitusi mundur dan aka mendapatkan solusi SPL \(\textbf{x}\).
function dekomposisi_lu(A)
n = size(A, 1)
L = zeros(n, n)
U = zeros(n, n)
for i = 1:n
L[i, i] = 1
for j = i:n
sum = 0.0
for k = 1:i-1
sum += L[i, k] * U[k, j]
end
U[i, j] = A[i, j] - sum
end
for j = i+1:n
sum = 0.0
for k = 1:i-1
sum += L[j, k] * U[k, i]
end
L[j, i] = (A[j, i] - sum) / U[i, i]
end
end
return L, U
end
dekomposisi_lu (generic function with 1 method)
function subtitusi_maju(L, b)
y = zeros(length(b))
for i = 1:length(b)
sum = 0.0
for j = 1:i-1
sum += L[i, j] * y[j]
end
y[i] = (b[i] - sum) / L[i, i]
end
return y
end
subtitusi_maju (generic function with 1 method)
function subtitusi_mundur(U, y)
n = length(y)
x = zeros(n)
for i = n:-1:1
sum = 0.0
for j = i+1:n
sum += U[i, j] * x[j]
end
x[i] = (y[i] - sum) / U[i, i]
end
return x
end
subtitusi_mundur (generic function with 1 method)
10.2. Contoh 1#
Diberikan
A = [1 1 0 3; 2 1 -1 1; 3 -1 -1 2; -1 2 3 -1]
b = [8; 7; 14; -7];
# Dekomposisi A menjadi LU
L, U = dekomposisi_lu(A)
display(L)
4×4 Matrix{Float64}:
1.0 0.0 0.0 0.0
2.0 1.0 0.0 0.0
3.0 4.0 1.0 0.0
-1.0 -3.0 0.0 1.0
display(U)
4×4 Matrix{Float64}:
1.0 1.0 0.0 3.0
0.0 -1.0 -1.0 -5.0
0.0 0.0 3.0 13.0
0.0 0.0 0.0 -13.0
# subtitusi maju untuk Ly = b
y = subtitusi_maju(L,b)
display(y)
4-element Vector{Float64}:
8.0
-9.0
26.0
-26.0
# subtitusi mundur untuk Ux = y
x = subtitusi_mundur(U, y)
display(x)
4-element Vector{Float64}:
3.0
-1.0
0.0
2.0
10.3. Matriks Permutasi#
Matriks permutasi adalah matriks \(n \times n\) yang berasal dari matriks identitas dan jika kita tukar suatu baris dari \(I\) kemudian kita kalikan dengan \(A\) maka akan menghasilkan matriks \(A\) yang barisnya sudah tertukar. Misalkan kita punya
kemdian kita kalikan \(P\) dan \(A\) menghasilkan
Matriks permutasi digunakan untuk menangani matriks yang ill-conditioned.
Note
Jika \(P^{-1}\) ada maka \(P^{-1} = P^t\).
10.4. Matriks PLU untuk menyelesaikan SPL#
Diberikan \(A\textbf{x} = \textbf{b}\) dan kita kalikan kedua ruas dengan matriks permutasi \(P\) maka menghasilkan
Kemudian asumsikan bahwa kita dapat menyelesaikannya tanpa menukar baris, ini berarti \(P = I\) untuk \(I\) adalah matriks identitas. Sehingga ketika \(A\) kita dekomposisi menjadi \(LU\) maka dapat ditulis
Karena \(P^{-1} = P^t\) maka matriks \(A\) dapat ditulis
Note
Matriks \(U\) tetap menjadi matriks segitiga atas, tapi \(P^tL\) bukan matriks segitiga bawah kecuali \(P = I\).
Dengan demikian, bentuk \(PA\textbf{x} = P\textbf{b}\) kita ubah menjadi
Kita misalkan \(U \textbf{x} = \textbf{y}\) maka
dan selesaikan menggunakan subtitusi maju. Selanjutnya kita terapkan subtitusi mundur untuk menyelesaikan \(U \textbf{x} = \textbf{y}.\)
10.5. Contoh 2#
Diberikan
Kita ingin mendekomposisi \(A\) menjadi bentuk \((P^tL)U\)
using LinearAlgebra
function dekomposisi_plu(A)
n = size(A, 1)
L = zeros(n, n)
U = copy(A)
P = Matrix{Float64}(I, n, n)
for k in 1:n
# Cari baris pivot
pivot = argmax(abs.(U[k:n, k])) + k - 1
# Tukar baris di U
U[[k, pivot], k:n] = U[[pivot, k], k:n]
# Tukar baris di P
P[[k, pivot], :] = P[[pivot, k], :]
# Tukar baris di L
L[[k, pivot], 1:k-1] = L[[pivot, k], 1:k-1]
# Dekomposisi LU
for i in k+1:n
L[i, k] = U[i, k] / U[k, k]
U[i, k:n] -= L[i, k] * U[k, k:n]
end
end
# Diagonal L harus 1
for i in 1:n
L[i, i] = 1.0
end
return P, L, U
end
dekomposisi_plu (generic function with 1 method)
A = [0 0 -1 1; 1 1 -1 2; -1 -1 2 0; 1 2 0 2]
display(A)
4×4 Matrix{Int64}:
0 0 -1 1
1 1 -1 2
-1 -1 2 0
1 2 0 2
P, L, U = dekomposisi_plu(A)
display(P)
4×4 Matrix{Float64}:
0.0 1.0 0.0 0.0
0.0 0.0 0.0 1.0
0.0 0.0 1.0 0.0
1.0 0.0 0.0 0.0
display(L)
4×4 Matrix{Float64}:
1.0 0.0 0.0 0.0
1.0 1.0 0.0 0.0
-1.0 0.0 1.0 0.0
0.0 0.0 -1.0 1.0
display(U)
4×4 Matrix{Int64}:
1 1 -1 2
0 1 1 0
0 0 1 2
0 0 0 3
transpose(P)*L*U # = A
4×4 Matrix{Float64}:
0.0 0.0 -1.0 1.0
1.0 1.0 -1.0 2.0
-1.0 -1.0 2.0 0.0
1.0 2.0 0.0 2.0
10.6. Contoh 3#
Dari [](#Contoh 2)
Pb = P*b
display(Pb)
4-element Vector{Float64}:
7.0
-7.0
14.0
8.0
y = subtitusi_maju(L, Pb)
display(y)
4-element Vector{Float64}:
7.0
-14.0
21.0
29.0
x = subtitusi_mundur(U,y)
display(x)
4-element Vector{Float64}:
5.0000000000000036
-15.666666666666668
1.6666666666666679
9.666666666666666
A*x # = vektor b
4-element Vector{Float64}:
7.999999999999998
7.0
14.0
-7.0