Dekomposisi Matriks
Contents
Dekomposisi Matriks¶
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)\) [Burden and Faires, 2010]. 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.
Dekomposisi LU¶
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\).
Desain Algoritma untuk Dekomposisi LU¶
Algoritma: Eliminasi_Gauss_Scaled_Pivoting(A, b)
INPUT: Matriks A
Inisialisasi: L = Matriks Identitas, U = Matriks nol
Lakukan Eliminasi Maju untuk mendapatkan matriks segitiga atas U, bersamaan dengan itu kita dapatkan juga matriks segitiga bawah L
for i=1 to n
for j=i+1 to n
faktor = A[j,i]/A[i,i]
L[j,i] = faktor
(E_j - faktor*E_i) -> (E_j) -> menghasilkan U
import numpy as np
def dekomposisiLU(A):
n = len(A)
L = np.eye(n, dtype=np.double)
for i in range(n):
faktor = A[i+1:, i]/A[i,i]
L[i+1:, i] = faktor
A[i+1:] -= faktor[:, np.newaxis]*A[i]
U = A
return L,U
Contoh 1¶
Diberikan SPL
A = np.array([[1, 1, 0, 3],
[2, 1, -1, 1],
[3, -1, -1, 2],
[-1, 2, 3, -1]], dtype=np.float64)
b = np.array([4, 1, -3, 4], dtype=np.float64)
def subtitusi_maju(L,b):
n = len(b)
L_c = np.c_[L,b]
y = np.zeros_like(b, dtype=np.double)
# Lakukan subtitutsi mundur
y[0] = b[0]/L[0,0]
for i in range(1,n):
y[i] = (b[i] - np.dot(L[i,:i], y[:i])) / L[i,i]
return y
def subtitusi_mundur(U,y):
n = len(y)
x = np.zeros_like(y, dtype=np.double)
# Lakukan subtitutsi mundur
x[-1] = y[-1]/U[-1,-1]
for i in range(n-2, -1, -1):
x[i] = (y[i] - np.dot(U[i,i:], x[i:])) / U[i,i]
return x
def lu(A,b):
L, U = dekomposisiLU(A)
y = subtitusi_maju(L,b)
return subtitusi_mundur(U,y)
x = lu(A,b)
x
array([-1., 2., 0., 1.])
Matriks Permutasi¶
def dekomposisi_plu(A):
n = A.shape[0]
U = A.copy()
L = np.eye(n, dtype=np.double)
P = np.eye(n, dtype=np.double)
for i in range(n):
for k in range(i, n):
if ~np.isclose(U[i, i], 0.0):
break
U[[k, k+1]] = U[[k+1, k]]
P[[k, k+1]] = P[[k+1, k]]
factor = U[i+1:, i] / U[i, i]
L[i+1:, i] = factor
U[i+1:] -= factor[:, np.newaxis] * U[i]
return P, L, U
def plu(A, b):
P, L, U = dekomposisi_plu(A)
y = subtitusi_maju(L, np.dot(P,b))
return subtitusi_mundur(U, y)
A = np.array([[1e-17, -1],
[1,2]], dtype=np.double)
b = np.array([-1, 3], dtype=np.double)
plu(A,b)
array([1., 1.])
Singular Value Decomposition (SVD)¶
Diberikan suatu matriks \(A \in \mathbb{C}^{m \times n}\). Matriks \(A\) dapat didekomposisi ke dalam bentuk
dimana \(U \in \mathbb{C}^{m \times m}\) dan \(V \in \mathbb{C}^{n \times n}\) adalah matriks orthogonal, dan \(S \in \mathbb{R}^{m \times n}\) adalah matriks diagonal yang tak nol. Biasanya SVD dipakai untuk mendekomposisi matriks \(A\) ketika \(m \gg n\), oleh karena itu kita asumsikan bahwa matriks \(A\) memiliki ukuran \(m \gg n\).
Definisi 1
Misalkan \(A\) adalah matriks \(m \times n\). (i) Rank dari \(A\) dinotasikan \(Rank(A)\) adalah banyaknya baris yang bebas linear dari \(A\). (ii) Nullity dari \(A\) dinotasikan \(Nullity(A)\), adalah \(n - Rank(A)\), yaitu himpunan terbesar dari vektor bebas linear di \(\mathbb{R}^n\) untuk \(A\vec{v} = \vec{0}\)
Rank dan Nullity dari suatu matriks merupakan hal penting untuk mengetahui karakteristik dari matriks. Misalkan ketika matriksnya persegi maka kita dapat mengetahui apakah matriks tersebut memiliki invers atau tidak, dengan cara melihat apakah Nullity-nya 0 dan Rank-nya memiliki ukuran yang sama dari matriks tersebut.