Dekomposisi LU, langkah demi langkah

Memfaktorkan matriks menjadi bagian segitiga bawah dan atas, kenapa itu lebih cepat daripada mengulang eliminasi, dan bagaimana Cholesky mengkhususkannya.

Dekomposisi LU menuliskan matriks persegi sebagai hasil kali matriks segitiga bawah dengan segitiga atas: A = L·U. Faktornya keluar langsung dari eliminasi Gauss — U adalah bentuk eselon barisnya, dan L mencatat pengali yang Anda pakai untuk sampai ke sana.

Untuk apa

Karena faktorisasinya bisa dipakai ulang. Menyelesaikan Ax = b dari awal memakan sekitar n³/3 operasi. Begitu L dan U ada, setiap ruas kanan baru hanya memakan n²: selesaikan Ly = b dengan substitusi maju, lalu Ux = y dengan substitusi mundur. Dengan puluhan ruas kanan, keuntungannya besar sekali.

Determinannya pun jadi gratis — ia adalah hasil kali diagonal U, dikali −1 untuk setiap penukaran baris yang dilakukan.

Pemilihan pivot

Tidak semua matriks menerima A = L·U polos: nol di posisi pivot merusaknya. Solusinya matriks permutasi, sehingga menjadi P·A = L·U. Dalam praktiknya pivot tetap dipakai, karena memilih pivot terbesar yang tersedia menjaga galat pembulatan tetap terkendali.

Cholesky: kasus simetris

Bila A simetris dan definit positif, ia terfaktor menjadi A = L·Lᵀ — cukup satu faktor segitiga. Cholesky kira-kira dua kali lebih cepat daripada LU dan sangat stabil secara numerik, itulah sebabnya ia mendominasi di optimasi, kuadrat terkecil, dan statistika (matriks kovarians simetris definit positif menurut konstruksinya).

Jika algoritmanya sampai meminta akar kuadrat dari bilangan negatif, berarti matriksnya bukan definit positif — jadi Cholesky sekaligus menjadi uji untuk sifat itu.