LU Dekomposisi

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:

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:

dengan $i = 1, \ldots, r$, matriks pertukaran baris $P_i$ atau $P_i = I$ dan matriks eliminasi:

Invers dari $L_i$ adalah:

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$.

Struktur Hasil Dekomposisi

Dari eliminasi Gauss dengan langkah-langkah $j_1, \ldots, j_r$, kita mendapatkan tiga matriks dengan struktur khusus:

Matriks $P$ diperoleh dari penerapan vektor permutasi $p$ 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$

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.

   $$A = \begin{pmatrix} 3 & 3 & 3 & 3 \\ 0 & 2 & 4 & 2 \\ 1 & 2 & 3 & 1 \end{pmatrix}$$

   $$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.

Hasil akhir:

Dari hasil eliminasi ini, kita peroleh:

Pembuktian menunjukkan bahwa $L \cdot U = P \cdot A$ untuk matriks $A$ 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}$.

Implementasi Algoritma dalam Python

Berikut adalah implementasi algoritma dekomposisi LU dalam Python:

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

Penyelesaian Sistem Linear

Setelah mendapatkan dekomposisi LU, menyelesaikan sistem $A \cdot x = b$ 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:

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.

Untuk setiap baris $i = 1, \ldots, m$, kita menghitung:

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.

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$.

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.

Jika sistem dapat diselesaikan, kita inisialisasi matriks kernel $K$ dengan ukuran $n \times (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.

1. Jika kolom j adalah langkah pivot, artinya $j = j_i$ untuk langkah ke-$i$, maka kita hitung solusi untuk variabel $x_j$:

   $$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:

   $$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)

Algoritma ini menghasilkan solusi $x$ dan matriks $K$ yang memenuhi $U \cdot x = d$ dan $U \cdot 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.

Himpunan solusi lengkap adalah:

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$.

1. Langkah pertama adalah menghitung $c = P \cdot b$. Karena matriks permutasi $P$ menukar baris pertama dengan baris kedua, kita mendapatkan:

   $$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:

   $$y_3 = c_3 - l_{31} \cdot y_1 - l_{32} \cdot y_2$$

   $$= 3 - \frac{1}{3} \cdot 3 - \frac{1}{2} \cdot 4$$

   $$= 3 - 1 - 2 = 0$$

   Sehingga diperoleh:

   $$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, dan 4. Kolom 3 tidak memiliki pivot sehingga menjadi variabel bebas.

   Dari proses substitusi mundur, kita memperoleh solusi khusus:

   $$x = \begin{pmatrix} -1 \\ 2 \\ 0 \\ 0 \end{pmatrix}$$

   dan matriks kernel:

   $$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:

   $$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$$

   $$= \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.

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.