Dekomposisi LU

Dalam analisis numerik dan aljabar linier, **dekomposisi** **lower-upper** **(LU)** atau **faktorisasi** faktorisasi matriks sebagai hasil kali matriks segitiga bawah dan matriks segitiga atas (lihat perkalian matriks dan dekomposisi matriks). Hasil perkalian ini terkadang juga mencakup matriks permutasi. Dekomposisi LU dapat dilihat sebagai bentuk matriks dari eliminasi Gaussian. Komputer biasanya menyelesaikan sistem persamaan linear bujur sangkar menggunakan dekomposisi LU, dan ini juga merupakan langkah penting ketika membalikkan matriks atau menghitung determinan matriks. Kadang-kadang juga disebut sebagai dekomposisi LR (faktorisasi ke dalam matriks segitiga kiri dan kanan). Dekomposisi LU diperkenalkan oleh astronom Polandia, Tadeusz Banachiewicz, pada tahun 1938.
## Definisi

Misalkan *A* adalah sebuah matriks persegi. **Faktorisasi LU** mengacu pada ekspresi *A* ke dalam hasil kali dua faktor – matriks segitiga bawah *L* dan matriks segitiga atas *U*:  A = LU.  Terkadang faktorisasi tidak mungkin dilakukan tanpa menyusun ulang *A* terlebih dahulu untuk mencegah pembagian dengan nol atau pertumbuhan kesalahan pembulatan yang tidak terkendali, maka ekspresi alternatifnya menjadi:  PAQ = LU , di mana dalam notasi formal matriks permutasi faktor P dan Q menunjukkan permutasi baris (atau kolom) dari *A*. Secara teori *P* (atau *Q*) diperoleh dengan permutasi baris (atau kolom) dari matriks identitas, dalam praktiknya permutasi yang sesuai diterapkan langsung pada baris (atau kolom) dari *A*. Matriks *A* dengan sisi  n memiliki  n^2 koefisien sedangkan dua matriks segitiga yang digabungkan mengandung  n(n+1) koefisien, oleh karena itu  n koefisien matriks LU tidak independen. Konvensi yang umum digunakan adalah dengan menetapkan L sebagai segitiga satuan, yaitu dengan semua  n elemen diagonal utama sama dengan satu. Namun, pengaturan matriks *U* unitriangular dapat direduksi menjadi prosedur yang sama setelah melakukan transposisi dari hasil kali matriks:  B = A^T = (LU)^T =U^TL^T, (lihat sifat-sifat transposisi). Sekarang U^T adalah segitiga bawah sementara L^T adalah faktor unitriangular atas dari *B*. Hal ini menunjukkan juga, bahwa operasi pada baris (misalnya pivoting) setara dengan operasi pada kolom matriks yang ditransposisi, dan pada umumnya pilihan algoritma baris atau kolom tidak memberikan keuntungan.

Pada matriks segitiga bawah, semua elemen di atas diagonal utama adalah nol, sedangkan pada matriks segitiga atas, semua elemen di bawah diagonal adalah nol. Sebagai contoh, untuk matriks *A* berukuran 3 × 3, dekomposisi LU-nya terlihat seperti ini:

: 
  \begin{bmatrix}
    a_{11} & a_{12} & a_{13} \\
    a_{21} & a_{22} & a_{23} \\
    a_{31} & a_{32} & a_{33}
  \end{bmatrix} =
  \begin{bmatrix}
    \ell_{11} &         0 & 0         \\
    \ell_{21} & \ell_{22} & 0         \\
    \ell_{31} & \ell_{32} & \ell_{33}
  \end{bmatrix}
  \begin{bmatrix}
    u_{11} & u_{12} & u_{13} \\
         0 & u_{22} & u_{23} \\
         0 &      0 & u_{33}
  \end{bmatrix}.


Tanpa susunan atau permutasi yang tepat dalam matriks, faktorisasi mungkin gagal terwujud. Sebagai contoh, mudah untuk memverifikasi (dengan memperluas perkalian matriks) bahwa a_{11} = \ell_{11} u_{11}. Jika a_{11} = 0, maka paling tidak salah satu dari \ell_{11} dan u_{11} haruslah nol, yang mengimplikasikan bahwa *L* atau *U* adalah tunggal. Hal ini tidak mungkin terjadi jika *A* tidak singular (dapat dibalik). Dalam hal operasi, pemusnahan/eliminasi elemen-elemen yang tersisa pada kolom pertama dari *A* melibatkan pembagian a_{21}, a_{31} dengan a_{11}, mustahil jika elemen-elemen tersebut bernilai 0. Hal ini merupakan sebuah masalah prosedural. Hal ini dapat dihilangkan hanya dengan menyusun ulang baris-baris *A* sehingga elemen pertama dari matriks permutasi tidak nol. Masalah yang sama pada langkah faktorisasi selanjutnya dapat dihilangkan dengan cara yang sama. Untuk kestabilan numerik terhadap kesalahan pembulatan/pembagian dengan angka-angka kecil, penting untuk memilih a_{11} nilai absolut yang besar (lihat pivoting).

### LU Melalui rekursi
Contoh matriks 3\times 3 di atas menunjukkan bahwa hasil kali matriks dari baris paling atas dan kolom paling kiri dari matriks-matriks yang terlibat memainkan peran khusus agar LU berhasil. Mari kita tandai versi matriks yang berurutan dengan (0),\;(1),\dots dan kemudian kita tuliskan hasil kali matriks A\equiv A^{(0)}=L^{(0)}U^{(0)} sedemikian rupa sehingga baris dan kolom tersebut terpisah satu dengan yang lainnya. Dalam melakukan hal ini kita akan menggunakan notasi matriks blok, sehingga misalnya a\equiv a_{11} adalah bilangan biasa, {\bf w}^T\equiv(a_{12}, a_{13})^T adalah vektor baris dan {\bf v}=(a_{21},a_{31}) adalah vektor kolom dan A' adalah sub-matriks dari matriks A^{(0)} tanpa baris teratas dan kolom paling kiri. Kemudian kita bisa mengganti A^{(0)}=L^{(0)}U^{(0)} dengan sebuah produk matriks blok. Ternyata kita dapat mengalikan blok matriks sedemikian rupa seolah-olah itu adalah bilangan biasa, yaitu baris dikalikan kolom, kecuali bahwa sekarang komponen-komponennya adalah sub-matriks, kadang-kadang direduksi menjadi skalar atau vektor. Dengan demikian, u{\bf l} menunjukkan vektor yang diperoleh dari {\bf l} setelah perkalian setiap komponen dengan sebuah angka u, {\bf lu}^T merupakan hasil kali luar dari vektor-vektor {\bf l, u}, yaitu sebuah matriks yang kolom pertamanya adalah u_{12}{\bf l}, berikutnya adalah u_{13}{\bf l} dan seterusnya untuk semua komponen dari {\bf u} dan L^{(1)}U^{(1)} merupakan hasil kali sub-matriks dari L^{(0)},\;U^{(0)}

: 
  \left( \begin{array}{c|ccc}
    a & & {\bf w}^\textsf{T} & \\ \hline
      & &              & \\
    {\bf v} & &           A' & \\
      & &              &
  \end{array} \right)\,=\,
\left( \begin{array}{c|ccc}
    {\rm 1} & & {\bf 0}^\textsf{T} & \\ \hline
      & &              & \\
    {\bf l} & &           L^{(1)} & \\
      & &              &
  \end{array} \right)\;
\left( \begin{array}{c|ccc}
    u & & {\bf u}^\textsf{T} & \\ \hline
      & &              & \\
    {\bf 0} & &           U^{(1)} & \\
      & &              &
  \end{array} \right)\,=
: \left( \begin{array}{c|ccc}
    u & & {\bf u}^\textsf{T} & \\ \hline
      & &              & \\
    u{\bf l} & &  {\bf lu}^\textsf{T} + L^{(1)}U^{(1)} & \\
      & &              &
  \end{array} \right)

Dari persamaan matriks pertama dan terakhir, berikut ini adalah hasil akhir u=a, \bf u=w, {\bf l}={(1/a)}{\bf v} sementara matriks A' diperbarui/diganti dengan A^{(1)}\equiv L^{(1)}U^{(1)}=A'-{\bf lu}^T. Sekarang, tibalah pada pengamatan penting: *tidak ada yang menghalangi kita untuk memperlakukan <math>A^{(1)}</math> dengan cara yang sama seperti yang kita lakukan pada <math>A^{(0)}</math>*, dan lagi, dan lagi... Jika dimensi dari A adalah n\times n, setelah n-1 langkah-langkah tersebut semua kolom \bf v membentuk bagian sub-diagonal dari matriks segitiga L dan semua pivot a digabungkan dengan baris {\bf w}^T membentuk matriks segitiga bagian atas U, sesuai yang dibutuhkan. Pada contoh di atas n=3 sehingga 2 langkah sudah cukup.

Prosedur di atas menunjukkan bahwa tidak ada elemen pivot diagonal atas a dari sub-matriks yang berurutan yang bisa bernilai nol. Untuk menghindarinya, kolom atau baris dapat ditukar sehingga a menjadi tidak nol. Prosedur yang melibatkan permutasi ini disebut LUP, dekomposisi dengan pivoting. Permutasi kolom berhubungan dengan produk matriks AQ^{(0)} dimana Q^{(0)} adalah matriks permutasi, yaitu matriks identitas I setelah permutasi kolom yang sama. Setelah semua langkah dekomposisi LUP tersebut berlaku untuk AQ^{(0)}\cdots Q^{(n-1)}\equiv AQ=LU. Skema komputasi yang sekarang dan yang serupa dalam Cormen dkk. adalah contoh-contoh *algoritma perulangan*. Mereka mendemonstrasikan dua sifat umum dari LU: (i) kebutuhan untuk melakukan pivot pada setiap langkah dan (ii) nilai akhir dari L,\;U matriks diperoleh secara bertahap, satu baris atau kolom per langkah. Algoritma perulangan tidak terlalu mahal dalam hal operasi aljabar, tetapi memiliki kelemahan praktis karena harus memperbarui dan menyimpan sebagian besar elemen dari A pada setiap langkah. Akan terlihat bahwa dengan mengurutkan ulang perhitungan, dimungkinkan untuk membuang penyimpanan nilai antara.

## Catatan kaki

## Referensi

* .
* .
* .
* .
* .
* .
* . See Section 3.5. *N*&nbsp;−&nbsp;1
* .
* .
* .
* .
* .
* .
* .
*