Miss Math: Dekomposisi LU

Dekomposisi matriks LU merupakan salah satu metode numerik untuk menyelesaikan persamaan matriks.

Apabila secara analitik, mungkin akan sangat mudah menyelesaikan persamaan matriks seperti ini AX=B, dimana kita hanya mengetahui nilai matriks A dan matriks B saja, sementara kita tidak tahu nilai dari matriks X. Secara analitik kita dapat tuliskan bahwa matriks X merupakan perkalian dari inverse matriks A dengan matriks B, atau dapat ditulis X=A^-1B.

Namun bagaimana jika matriks A merupakan matriks dengan dimensi 100×100 atau 1000×1000, walaupun dikasih uang satu juta saya juga ga bakalan mau ngerjain hal ‘sia-sia’ seperti itu secara analitik. Tetapi dengan metode numerik dan tentu saja dengan bantuan kemampuan programming hal seperti itu akan lebih mudah dikerjakan.

Pertanyaannya, apa sih kegunaan dekomposisi matriks di dunia real? Saya akan menjawab metode ini dapat digunakan untuk melakukan interpolasi polinomial secara numerik tentunya atau dalam bidang yang sedang saya geluti, metode ini dapat membantu saja menyelesaikan persamaan Difusi Netron.

Pada metode LU Decomposition, matriks A ditulis ulang sebagai perkalian matriks L dan U (matriks A diurai menjadi matriks L dan U). Matriks L dan U merupakan matriks segitiga. Matriks B tidak berubah, karena matriks A tidak berubah, melainkan hanya ditulis ulang.

Langkah:

1. Cari matriks L dan U sehingga A = LU. Matriks B tetap.

2. Definisikan sebuah matriks kolom baru, misalnya Y, yaitu Y = UX, sehingga LY = B. Lalu hitung y dengan substitusi maju (mulai dari Y₁ sampai Y_n ).

3. Hitung x dengan substitusi mundur (mulai dari X₁ sampai X_n).

Hmm… pasti masih ga kebayang kan ya??

Oke ini contoh sederhananya menggunakan matriks A dengan dimensi 4×4.

Pada dekomposisi matriks LU , A = LU sehingga didapatkan persamaan

$\begin{pmatrix} 1& 0& 0& 0\\ l_{21} & 1& 0&0 \\ l_{31} & l_{32} & 1&0 \\ l_{41}& l_{42} &l_{43} & 1 \end{pmatrix}\begin{pmatrix} u_{11} &u_{12} &u_{13} &u_{14} \\ 0&u_{22} &u_{23} &u_{24} \\ 0& 0&u_{33} &u_{34} \\ 0& 0& 0& u_{44} \end{pmatrix}=\begin{pmatrix} a_{11} &a_{12} &a_{13} &a_{14} \\ a_{21} &a_{22} &a_{23} &a_{24} \\ a_{31} &a_{32} &a_{33} &a_{34} \\ a_{41} &a_{42} &a_{43} &a_{44} \end{pmatrix}$

Dari perkalian matriks maka didapatkan

a₁₁ = u₁₁
a₁₂ = u₁₂
a₁₃ = u₁₃
a₁₄ = u₁₄
a₂₁= l₂₁u₁₁
a₂₂ = l₂₁u₁₂ + u₂₂
a₂₃ = l₂₁u₁₃ + u₂₃
a₂₄ = l₂₁u₁₄ + u₂₄
a₃₁ = l₃₁u₁₁
a₃₂ = l₃₁u₁₂+ l₃₂u₂₂
a₃₃ = l₃₁u₁₃ + l₃₂u₂₃ + u₃₃
a₃₄ = l₃₁u₁₄ + l₃₂u₂₄ + u₃₄
a₄₁= l₄₁u₁₁
a₄₂ = l₄₁u₁₂+ l₄₂u₂₂
a₄₃ = l₄₁u₁₃ + l₄₂u₂₃ + l₄₃u₃₃
a₄₄ = l₄₁u₁₄ + l₄₂u₂₄ + l₄₃u₂₃ + u₄₄

Sehingga dapat didefinisikan
u_1j = a_1j(j= 1, … ,n)

$l_{i1}=\frac{a_{i1}}{u_{11}}$

dengan (i = 2, …, n)

$u_{ij}=a_{ij}-\sum_{k=1}^{i-1}l_{ik}u_{kj}$

dengan (i =2, … ,n; j=i, …, n), kemudian

$l_{ij}=\frac{1}{u{ij}}\left ( a_{ij}-\sum_{k=1}^{j-1}l_{ik}u_{kj} \right )$

dengan (i=3, …, n; j=2, …, i-1)

LY=B, dalam bentuk matriks dapat ditulis

$\begin{pmatrix} 1 & 0 &0 &0 \\ l_{21}&1 &0 &0 \\ l_{31}&l_{32} &1 &0 \\ l_{41}&l_{42} &l_{43} & 1 \end{pmatrix}\begin{pmatrix} y_{1}\\ y_{2}\\ y_{3}\\ y_{4} \end{pmatrix}=\begin{pmatrix} b_{1}\\ b_{2}\\ b_{3}\\ b_{4} \end{pmatrix}$

Sehingga dapat didefinisikan
y₁= b₁

$y_{i}=b_{i}-\sum_{j=1}^{i-1}l_{ij}y_{j}$

dengan (i =2, …, n) dan

UX=Y, dalam bentuk matriks dapat dituliskan

$\begin{pmatrix} u_{11} &u_{12} &u_{13} &u_{14} \\ 0 &u_{22} &u_{23} &u_{24} \\ 0 &0 &u_{33} &u_{34} \\ 0 &0 &0 &u_{34} \end{pmatrix}\begin{pmatrix} x_{1}\\ x_{2}\\ x_{3}\\ x_{4} \end{pmatrix}=\begin{pmatrix} y_{1}\\ y_{2}\\ y_{3}\\ y_{4} \end{pmatrix}$