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

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: $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 prakteknya 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^{T}L^{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 ${\textstyle a_{11}=\ell _{11}u_{11}}$. Jika ${\textstyle a_{11}=0}$, maka paling tidak salah satu dari ${\textstyle \ell _{11}}$ dan ${\textstyle 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 ${\textstyle a_{21},a_{31}}$ dengan ${\textstyle 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 ${\textstyle 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 $A^{(1)}$ dengan cara yang sama seperti yang kita lakukan pada $A^{(0)}$, 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.

Referensi

• Banachiewicz, T. (1938), "Méthode de résolution numérique des équations linéaires …" (PDF), Bull. Intern. De l'Acad. Polonaise, Série A. Sc. Math.: 393–404.
• Bunch, James R.; Hopcroft, John (1974), "Triangular factorization and inversion by fast matrix multiplication", Mathematics of Computation, 28 (125): 231–236, doi:10.2307/2005828, hdl:1813/6003, ISSN 0025-5718, JSTOR 2005828.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009), Introduction to Algorithms (Edisi 3rd), MIT Press and McGraw-Hill, ISBN 978-0-262-03293-3.
• Dwyer, Paul S. (1951), Linear Computations, New York: Wiley.
• Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations (Edisi 3rd), Baltimore: Johns Hopkins, ISBN 978-0-8018-5414-9.
• Hart, Roger (2011), The Chinese Roots of Linear Algebra, Baltimore: Johns Hopkins, ISBN 978-0801897559.
• Horn, Roger A.; Johnson, Charles R. (1985), Matrix Analysis, Cambridge University Press, ISBN 978-0-521-38632-6. See Section 3.5. N − 1
• Householder, Alston S. (1975), The Theory of Matrices in Numerical Analysis, New York: Dover Publications, MR 0378371.
• Lay, David C.; Lay, Steven R.; McDonald, Judi J. (2021), Linear Algebra and its Applications (Edisi Sixth), Pearson, ISBN 978-0-13-585125-8.
• Okunev, Pavel; Johnson, Charles R. (1997), Necessary And Sufficient Conditions For Existence of the LU Factorization of an Arbitrary Matrix, arXiv:math.NA/0506382.
• Poole, David (2006), Linear Algebra: A Modern Introduction (Edisi 2nd), Canada: Thomson Brooks/Cole, ISBN 978-0-534-99845-5.
• Ralston, Anthony (1965), A First Course in Numerical Analysis, New York: McGraw-Hill, Inc, ISBN 978-0-070-51157-6.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 2.3", Numerical Recipes: The Art of Scientific Computing (Edisi 3rd), New York: Cambridge University Press, ISBN 978-0-521-88068-8.
• Trefethen, Lloyd N.; Bau, David (1997), Numerical linear algebra, Philadelphia: Society for Industrial and Applied Mathematics, ISBN 978-0-89871-361-9.
• Rigotti, Luca (2001), ECON 2001 - Introduction to Mathematical Methods, Lecture 8