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 
jmpl|300x300px|Dekomposisi LDU dari matriks Walsh
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:  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: , 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  memiliki  koefisien sedangkan dua matriks segitiga yang digabungkan mengandung  koefisien, oleh karena itu  koefisien matriks LU tidak independen. Konvensi yang umum digunakan adalah dengan menetapkan L sebagai segitiga satuan, yaitu dengan semua  elemen diagonal utama sama dengan satu. Namun, pengaturan matriks U unitriangular dapat direduksi menjadi prosedur yang sama setelah melakukan transposisi dari hasil kali matriks: , (lihat sifat-sifat transposisi). Sekarang  adalah segitiga bawah sementara  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:



Tanpa susunan atau permutasi yang tepat dalam matriks, faktorisasi mungkin gagal terwujud. Sebagai contoh, mudah untuk memverifikasi (dengan memperluas perkalian matriks) bahwa . Jika , maka paling tidak salah satu dari  dan  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  dengan , 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  nilai absolut yang besar (lihat pivoting).

 LU Melalui rekursi 
Contoh matriks  di atas menunjukkan bahwa hasil kali matriks dari baris paling atas dan kolom paling kiri dari matriks-matriks yang terlibat memainkan peran khusus agar  berhasil. Mari kita tandai versi matriks yang berurutan dengan  dan kemudian kita tuliskan hasil kali matriks  sedemikian rupa sehingga baris dan kolom tersebut terpisah satu dengan yang lainnya. Dalam melakukan hal ini kita akan menggunakan notasi matriks blok, sehingga misalnya  adalah bilangan biasa,  adalah vektor baris dan  adalah vektor kolom dan  adalah sub-matriks dari matriks  tanpa baris teratas dan kolom paling kiri. Kemudian kita bisa mengganti  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,  menunjukkan vektor yang diperoleh dari  setelah perkalian setiap komponen dengan sebuah angka ,  merupakan hasil kali luar dari vektor-vektor , yaitu sebuah matriks yang kolom pertamanya adalah , berikutnya adalah  dan seterusnya untuk semua komponen dari  dan  merupakan hasil kali sub-matriks dari 




Dari persamaan matriks pertama dan terakhir, berikut ini adalah hasil akhir , ,  sementara matriks  diperbarui/diganti dengan . Sekarang, tibalah pada pengamatan penting: tidak ada yang menghalangi kita untuk memperlakukan  dengan cara yang sama seperti yang kita lakukan pada , dan lagi, dan lagi... Jika dimensi dari  adalah , setelah  langkah-langkah tersebut semua kolom  membentuk bagian sub-diagonal dari matriks segitiga  dan semua pivot  digabungkan dengan baris  membentuk matriks segitiga bagian atas , sesuai yang dibutuhkan. Pada contoh di atas  sehingga 2 langkah sudah cukup.

Prosedur di atas menunjukkan bahwa tidak ada elemen pivot diagonal atas  dari sub-matriks yang berurutan yang bisa bernilai nol. Untuk menghindarinya, kolom atau baris dapat ditukar sehingga  menjadi tidak nol. Prosedur yang melibatkan permutasi ini disebut , dekomposisi dengan pivoting. Permutasi kolom berhubungan dengan produk matriks  dimana  adalah matriks permutasi, yaitu matriks identitas  setelah permutasi kolom yang sama. Setelah semua langkah dekomposisi LUP tersebut berlaku untuk . Skema komputasi yang sekarang dan yang serupa dalam Cormen dkk. adalah contoh-contoh algoritma perulangan. Mereka mendemonstrasikan dua sifat umum dari : (i) kebutuhan untuk melakukan pivot pada setiap langkah dan (ii) nilai akhir dari  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  pada setiap langkah. Akan terlihat bahwa dengan mengurutkan ulang perhitungan, dimungkinkan untuk membuang penyimpanan nilai antara.

 Catatan kaki 

 Referensi 

 .
 .
 .
 .
 .
 .
 . See Section 3.5. N − 1
 .
 .
 .
 .
 .
 .
 .


LU