# Nakafa Learning Content
> For AI agents: use [llms.txt](https://nakafa.com/llms.txt) for the site index. Markdown versions are available by appending `.md` to content URLs or sending `Accept: text/markdown`.
URL: https://nakafa.com/id/materi/ai-ds/metode-linear-ai/lu-dekomposisi
Source: https://raw.githubusercontent.com/nakafaai/nakafa.com/refs/heads/main/packages/contents/material/lesson/ai-ds/linear-methods/lu-decomposition/id.mdx
Pelajari dekomposisi LU: faktorisasi matriks menjadi bentuk segitiga bawah/atas dengan eliminasi Gauss, implementasi Python dan penyelesaian sistem.
---
## Apa itu Dekomposisi LU?
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.
## Konsep Dasar Dekomposisi LU
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:
Visible text: Untuk matriks yang diberikan, kita mendapatkan:
```math
P \cdot A = L \cdot U
```
Di mana $$P$$ adalah matriks permutasi (pengatur urutan baris), $$L$$ adalah matriks segitiga bawah, dan $$U$$ adalah matriks segitiga atas.
Visible text: Di mana adalah matriks permutasi (pengatur urutan baris), adalah matriks segitiga bawah, dan adalah matriks segitiga atas.
Eliminasi Gauss menghitung dekomposisi LU ini melalui serangkaian operasi baris yang sistematis. Proses ini dapat dituliskan sebagai:
```math
U = L_r \cdot P_r \cdot \ldots \cdot L_3 \cdot P_3 \cdot L_2 \cdot P_2 \cdot L_1 \cdot P_1 \cdot A
```
dengan $$i = 1, \ldots, r$$, matriks pertukaran baris $$P_i$$ atau $$P_i = I$$ dan matriks eliminasi:
Visible text: dengan , matriks pertukaran baris atau dan matriks eliminasi:
```math
L_i = \begin{pmatrix} 1 & & & \\ & \ddots & & \\ & & \lambda_{i+1i} & \\ & & \vdots & \ddots \\ & & \lambda_{mi} & & 1 \end{pmatrix}
```
Invers dari $$L_i$$ adalah:
Visible text: Invers dari adalah:
```math
L_i^{-1} = \begin{pmatrix} 1 & & & \\ & \ddots & & \\ & & -\lambda_{i+1i} & \\ & & \vdots & \ddots \\ & & -\lambda_{mi} & & 1 \end{pmatrix}
```
Karena $$P_i^{-1} = P_i$$, kita dapat menulis ulang rangkaian operasi ini menjadi bentuk yang lebih sederhana hingga akhirnya mendapatkan $$L^{-1} \cdot P \cdot A = U$$.
Visible text: Karena , kita dapat menulis ulang rangkaian operasi ini menjadi bentuk yang lebih sederhana hingga akhirnya mendapatkan .
## Struktur Hasil Dekomposisi
Dari eliminasi Gauss dengan langkah-langkah $$j_1, \ldots, j_r$$, kita mendapatkan tiga matriks dengan struktur khusus:
Visible text: Dari eliminasi Gauss dengan langkah-langkah , kita mendapatkan tiga matriks dengan struktur khusus:
```math
\begin{pmatrix} 0 & u_{1j_1} & \cdots & & \cdots & u_{1n} \\ l_{21} & 0 & 0 & u_{2j_2} & \cdots & u_{2n} \\ l_{31} & l_{32} & 0 & 0 & \ddots & \\ \vdots & \vdots & \ddots & 0 & 0 & u_{rj_r} \cdots u_{rm} \\ & & & l_{(r+1)r} & 0 & 0 & 0 & 0 \\ \vdots & \vdots & & \vdots & 0 & 0 & 0 & 0 \\ l_{m1} & l_{m2} & \cdots & l_{mr} & 0 & 0 & 0 & 0 \end{pmatrix}
```
Matriks $$P$$ diperoleh dari penerapan vektor permutasi $$p$$ pada baris-baris matriks identitas. Ketiga matriks memiliki sifat:
Visible text: Matriks diperoleh dari penerapan vektor permutasi pada baris-baris matriks identitas. Ketiga matriks memiliki sifat:
1. $$U$$ adalah matriks segitiga atas dalam bentuk baris bertingkat dengan peringkat $$r$$
2. $$L$$ adalah matriks segitiga bawah reguler dengan $$1$$ pada diagonal
3. $$P$$ adalah matriks permutasi dengan $$P^{-1} = P^T$$
Visible text: 1. adalah matriks segitiga atas dalam bentuk baris bertingkat dengan peringkat
2. adalah matriks segitiga bawah reguler dengan pada diagonal
3. adalah matriks permutasi dengan
## Langkah Eliminasi Gauss
Mari kita lihat contoh konkret. Bayangkan kita sedang membersihkan rumah lantai demi lantai, mulai dari atas.
1. **Kolom pertama** dengan elemen pivot $$a_{21} = 3$$. Kita tukar baris pertama dan kedua seperti menukar posisi furniture.
```math
A = \begin{pmatrix} 3 & 3 & 3 & 3 \\ 0 & 2 & 4 & 2 \\ 1 & 2 & 3 & 1 \end{pmatrix}
```
```math
r = 1, \text{ Langkah } = \{1\}, p = (2,1,3), v = 1
```
Eliminasi entri lain pada kolom tersebut: $$\lambda_{21} = 0$$, $$\lambda_{31} = -\frac{1}{3}$$
2. **Kolom kedua** dengan elemen pivot $$a_{22} = 2$$. Tidak ada pertukaran diperlukan.
Eliminasi: $$\lambda_{32} = -\frac{1}{2}$$
3. **Kolom ketiga** tidak memiliki elemen pivot yang bisa digunakan.
4. **Kolom keempat** dengan elemen pivot $$a_{34} = -1$$. Tidak ada operasi lagi diperlukan.
Visible text: 1. **Kolom pertama** dengan elemen pivot . Kita tukar baris pertama dan kedua seperti menukar posisi furniture.
Eliminasi entri lain pada kolom tersebut: ,
2. **Kolom kedua** dengan elemen pivot . Tidak ada pertukaran diperlukan.
Eliminasi:
3. **Kolom ketiga** tidak memiliki elemen pivot yang bisa digunakan.
4. **Kolom keempat** dengan elemen pivot . Tidak ada operasi lagi diperlukan.
Hasil akhir:
```math
r = 3, \text{Langkah} = \{1, 2, 4\}, p = (2,1,3), v = 1
```
Dari hasil eliminasi ini, kita peroleh:
Component: MathContainer
Children:
```math
U = \begin{pmatrix} 3 & 3 & 3 & 3 \\ 0 & 2 & 4 & 2 \\ 0 & 0 & 0 & -1 \end{pmatrix}
```
```math
L = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1/3 & 1/2 & 1 \end{pmatrix}
```
```math
P = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}
```
Pembuktian menunjukkan bahwa $$L \cdot U = P \cdot A$$ untuk matriks $$A$$ yang diberikan awalnya.
Visible text: Pembuktian menunjukkan bahwa untuk matriks yang diberikan awalnya.
## Algoritma dan Kompleksitas
Algoritma eliminasi Gauss bekerja seperti pembersihan sistematis. Untuk setiap kolom, kita melakukan:
1. Cari elemen pivot terbaik
2. Tukar baris jika perlu
3. Eliminasi elemen di bawah pivot
4. Simpan informasi multiplier
Kompleksitas waktu untuk menghitung dekomposisi LU adalah $$\frac{1}{3}n^3 + O(n^2)$$ operasi aritmatika. Pembuktian menunjukkan bahwa perkalian dan penjumlahan terjadi bersamaan dalam transformasi baris eliminasi $$a_{ij} := a_{ij} + \lambda_{ir} \cdot a_{rl}$$.
Visible text: Kompleksitas waktu untuk menghitung dekomposisi LU adalah operasi aritmatika. Pembuktian menunjukkan bahwa perkalian dan penjumlahan terjadi bersamaan dalam transformasi baris eliminasi .
Component: MathContainer
Children:
```math
\sum_{j=1}^n \sum_{i=j+1}^n \sum_{l=j+1}^n 1 = \sum_{j=1}^n (n-j)^2
```
```math
= \sum_{j=1}^n (n^2 - 2nj + j^2)
```
```math
= n^3 - 2n \sum_{j=1}^n j + \sum_{j=1}^n j^2
```
```math
= n^3 - 2n \frac{n(n+1)}{2} + \frac{n(n+1)(2n+1)}{6}
```
```math
= n^3 - n^3 + \frac{2}{6}n^3 + O(n^2)
```
```math
= \frac{1}{3}n^3 + O(n^2)
```
## Implementasi Algoritma dalam Python
Berikut adalah implementasi algoritma dekomposisi LU dalam Python:
File: lu_decomposition.py
```python
import numpy as np
def 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, P
def 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 y
def 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 x
def 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
```
## Penyelesaian Sistem Linear
Setelah mendapatkan dekomposisi LU, menyelesaikan sistem $$A \cdot x = b$$ menjadi seperti menyelesaikan teka-teki yang sudah diurutkan.
Visible text: Setelah mendapatkan dekomposisi LU, menyelesaikan sistem menjadi seperti menyelesaikan teka-teki yang sudah diurutkan.
Sistem $$A \cdot x = b$$ berubah menjadi $$U \cdot x = L^{-1} \cdot P \cdot b$$ melalui dua tahap:
Visible text: Sistem berubah menjadi melalui dua tahap:
### Substitusi Maju
Algoritma substitusi maju menyelesaikan $$L \cdot y = P \cdot b$$ dengan matriks segitiga bawah reguler $$L$$ dan vektor $$c = P \cdot b$$. Proses ini seperti mengisi tangga dari bawah ke atas, di mana setiap langkah bergantung pada langkah sebelumnya.
Visible text: Algoritma substitusi maju menyelesaikan dengan matriks segitiga bawah reguler dan vektor . Proses ini seperti mengisi tangga dari bawah ke atas, di mana setiap langkah bergantung pada langkah sebelumnya.
Untuk setiap baris $$i = 1, \ldots, m$$, kita menghitung:
Visible text: Untuk setiap baris , kita menghitung:
```math
y_i := \frac{1}{l_{ii}} \cdot \left( c_i - \sum_{j=1}^{i-1} l_{ij} \cdot y_j \right)
```
Algoritma ini efisien karena kita hanya perlu menghitung satu nilai di setiap langkah. Elemen diagonal $$l_{ii}$$ selalu bernilai $$1$$ untuk matriks $$L$$ dari dekomposisi LU, sehingga pembagian menjadi sederhana.
Visible text: Algoritma ini efisien karena kita hanya perlu menghitung satu nilai di setiap langkah. Elemen diagonal selalu bernilai untuk matriks dari dekomposisi LU, sehingga pembagian menjadi sederhana.
### Substitusi Mundur
Algoritma substitusi mundur menyelesaikan $$U \cdot x = y$$ dengan matriks $$U$$ dalam bentuk baris bertingkat dengan $$r$$ langkah pada kolom-kolom $$j_1, \ldots, j_r$$ dan vektor $$d = y$$.
Visible text: Algoritma substitusi mundur menyelesaikan dengan matriks dalam bentuk baris bertingkat dengan langkah pada kolom-kolom dan vektor .
Pertama, kita periksa apakah sistem dapat diselesaikan. Jika $$r < m$$ dan terdapat $$d_i \neq 0$$ untuk $$i \in \{r + 1, \ldots, m\}$$, maka sistem tidak memiliki solusi.
Visible text: Pertama, kita periksa apakah sistem dapat diselesaikan. Jika dan terdapat untuk , maka sistem tidak memiliki solusi.
Jika sistem dapat diselesaikan, kita inisialisasi matriks kernel $$K$$ dengan ukuran $$n \times (n-r)$$, dan mulai dengan $$k = 0$$ serta $$i = r$$.
Visible text: Jika sistem dapat diselesaikan, kita inisialisasi matriks kernel dengan ukuran , dan mulai dengan serta .
Algoritma bekerja mundur dari kolom $$j = n$$ hingga $$j = 1$$. Untuk setiap kolom, kita periksa apakah kolom tersebut adalah langkah pivot atau bukan.
Visible text: Algoritma bekerja mundur dari kolom hingga . Untuk setiap kolom, kita periksa apakah kolom tersebut adalah langkah pivot atau bukan.
1. **Jika kolom j adalah langkah pivot**, artinya $$j = j_i$$ untuk langkah ke-$$i$$, maka kita hitung solusi untuk variabel $$x_j$$:
```math
x_j := \frac{1}{u_{ij}} \cdot \left( d_i - \sum_{l=j+1}^n u_{il} \cdot x_l \right)
```
Dan kita juga hitung kontribusi variabel ini terhadap matriks kernel:
```math
K_{jq} := \frac{1}{u_{ij}} \cdot \left( - \sum_{l=j+1}^n u_{il} \cdot K_{lq} \right)
```
untuk $$q = 1, \ldots, n - r$$, kemudian kita kurangi $$i$$ dengan $$1$$.
2. **Jika kolom j bukan langkah pivot**, artinya tidak ada pivot pada kolom tersebut, maka variabel $$x_j$$ adalah variabel bebas. Kita set:
- $$k := k + 1$$
- $$x_j := 0$$ (solusi khusus)
- $$K_{jk} := 1$$ (basis kernel)
Visible text: 1. **Jika kolom j adalah langkah pivot**, artinya untuk langkah ke-, maka kita hitung solusi untuk variabel :
Dan kita juga hitung kontribusi variabel ini terhadap matriks kernel:
untuk , kemudian kita kurangi dengan .
2. **Jika kolom j bukan langkah pivot**, artinya tidak ada pivot pada kolom tersebut, maka variabel adalah variabel bebas. Kita set:
-
- (solusi khusus)
- (basis kernel)
Algoritma ini menghasilkan solusi $$x$$ dan matriks $$K$$ yang memenuhi $$U \cdot x = d$$ dan $$U \cdot K = 0$$.
Visible text: Algoritma ini menghasilkan solusi dan matriks yang memenuhi dan .
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.
Visible text: Kolom-kolom dari matriks membentuk basis untuk kernel (ruang null) dari matriks . Ini berarti bahwa setiap kolom adalah vektor yang ketika dikalikan dengan menghasilkan vektor nol.
Himpunan solusi lengkap adalah:
```math
\left\{ x + K \cdot \begin{pmatrix} t_1 \\ \vdots \\ t_{n-r} \end{pmatrix} : t_1, \ldots, t_{n-r} \in \mathbb{R} \right\}
```
## Contoh Penerapan
Mari kita lihat bagaimana dekomposisi LU digunakan untuk menyelesaikan sistem linear secara konkret. Misalkan kita memiliki vektor $$b = \begin{pmatrix} 4 \\ 3 \\ 3 \end{pmatrix}$$ dan ingin menyelesaikan sistem $$A \cdot x = b$$.
Visible text: Mari kita lihat bagaimana dekomposisi LU digunakan untuk menyelesaikan sistem linear secara konkret. Misalkan kita memiliki vektor dan ingin menyelesaikan sistem .
1. **Langkah pertama** adalah menghitung $$c = P \cdot b$$. Karena matriks permutasi $$P$$ menukar baris pertama dengan baris kedua, kita mendapatkan:
```math
c = P \cdot b = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 4 \\ 3 \\ 3 \end{pmatrix} = \begin{pmatrix} 3 \\ 4 \\ 3 \end{pmatrix}
```
2. **Langkah kedua** adalah substitusi maju untuk menyelesaikan $$L \cdot 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 $$l_{11} = 1$$, kita dapatkan $$y_1 = c_1 = 3$$.
Untuk baris kedua dengan $$l_{22} = 1$$, kita dapatkan $$y_2 = c_2 = 4$$.
Untuk baris ketiga dengan $$l_{33} = 1$$, kita hitung:
```math
y_3 = c_3 - l_{31} \cdot y_1 - l_{32} \cdot y_2
```
```math
= 3 - \frac{1}{3} \cdot 3 - \frac{1}{2} \cdot 4
```
```math
= 3 - 1 - 2 = 0
```
Sehingga diperoleh:
```math
y = L^{-1} \cdot c = \begin{pmatrix} 3 \\ 4 \\ 0 \end{pmatrix}
```
3. **Langkah ketiga** adalah substitusi mundur untuk menyelesaikan $$U \cdot 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:
```math
x = \begin{pmatrix} -1 \\ 2 \\ 0 \\ 0 \end{pmatrix}
```
dan matriks kernel:
```math
K = \begin{pmatrix} 1 \\ -2 \\ 1 \\ 0 \end{pmatrix}
```
4. **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 \cdot x$$.
5. **Verifikasi matematis** menunjukkan bahwa untuk setiap nilai parameter $$t_1$$, solusi umum $$x + K \cdot t_1$$ tetap memenuhi persamaan asli.
Mari kita buktikan dengan menghitung $$A \cdot (x + K \cdot t_1)$$. Hasilnya adalah:
```math
A \cdot (x + K \cdot t_1) = A \cdot \begin{pmatrix} -1 \\ 2 \\ 0 \\ 0 \end{pmatrix} + A \cdot \begin{pmatrix} 1 \\ -2 \\ 1 \\ 0 \end{pmatrix} \cdot t_1
```
```math
= \begin{pmatrix} 4 \\ 3 \\ 3 \end{pmatrix} + \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix} \cdot t_1 = b
```
Perhatikan bahwa $$A \cdot K = 0$$, yang berarti vektor $$K$$ berada dalam ruang null dari matriks $$A$$. Ini menjelaskan mengapa menambahkan kelipatan $$K$$ pada solusi tidak mengubah hasil.
Visible text: 1. **Langkah pertama** adalah menghitung . Karena matriks permutasi menukar baris pertama dengan baris kedua, kita mendapatkan:
2. **Langkah kedua** adalah substitusi maju untuk menyelesaikan . Kita menggunakan matriks segitiga bawah yang sudah kita peroleh. Proses ini dilakukan dari atas ke bawah seperti mengisi tangga satu per satu.
Untuk baris pertama dengan , kita dapatkan .
Untuk baris kedua dengan , kita dapatkan .
Untuk baris ketiga dengan , kita hitung:
Sehingga diperoleh:
3. **Langkah ketiga** adalah substitusi mundur untuk menyelesaikan . Matriks dalam bentuk baris bertingkat memiliki pivot pada kolom . Kolom tidak memiliki pivot sehingga menjadi variabel bebas.
Dari proses substitusi mundur, kita memperoleh solusi khusus:
dan matriks kernel:
4. **Interpretasi hasil** sangat penting untuk dipahami. Solusi adalah satu solusi khusus dari sistem persamaan. Matriks menunjukkan arah di mana kita bisa bergerak dalam ruang solusi tanpa mengubah hasil perkalian .
5. **Verifikasi matematis** menunjukkan bahwa untuk setiap nilai parameter , solusi umum tetap memenuhi persamaan asli.
Mari kita buktikan dengan menghitung . Hasilnya adalah:
Perhatikan bahwa , yang berarti vektor berada dalam ruang null dari matriks . Ini menjelaskan mengapa menambahkan kelipatan pada solusi tidak mengubah hasil.
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.