Penjelasan Dekomposisi Matriks
Muhammad Amirul muttaqin, Prof. Dr. Suhartono, M.kom
12/3/2021
Universitas : Universitas Islam Negeri Maulana Malik Ibrahim Malang
Jurusan : Teknik Informatika
Dekomposisi Matriks
Seringkali kita diminta untuk memperoleh nilai penyelesaian suatu persamaan linier Ax=BAx=B, dimana nilai vektor BB yang selalu berubah-ubah. Penggunaan metode eliminasi Gauss mengharuskan untuk menyelesaikan sistem persamaan linier Ax=BAx=B secara terpisah untuk setiap perubahan vektor BB. Untuk menghindari pekerjaan eliminasi yang selalu berulang-ulang, faktorisasi menjadi suatu hal yang dapat dilakukan untuk mempersingkat prosesnya. Faktorisasi atau dekomposisi matriks merupakan suatu algoritma untuk memecah matriks AA, hasil pemecahan ini selanjutnya digunakan untuk memperoleh penyelesaian sistem persamaan linier melalui perkalian antara vektor BB dan hasil faktorisasi matriks AA.
Dekomposisi LU Pada RStudio
Misalkan kita memiliki persamaan linier seperti yang ditunjukkan oleh Persamaan sebelumnya. Pada metode dekomposisi LU, matriks AA difaktorkan menjadi matriks LL dan matriks UU, dimana ukuran kedua matriks tersebut harus sama dengan ukuran matriks AA atau dapat kita tuliskan bahwa hasil perkalian kedua matriks tersebut akan menghasilkan matriks AA.
Kita dapat menyelesaikan sistem persamaan yang ditunjukkan pada Persamaan (6.24) dan Persamaan (6.25) menggunakan berbagai algoritma penyelesaian yang telah dibahas sebelumnya. Namun, karena matriks LL merupakan matriks segitiga bawah dengan nilai nol berada pada bagian atas diagonal utama, penyelesaian tt mengambil langkah yang lebih sedikit. Kondisi ini sama dengan kondisi penyelesaian matriks tridiagonal, dimana kita memanfaatkan sejumlah jalan pintas penyelesaiaannya guna mempercepat komputasi. Matriks segitia bawah LL akan berupa matriks persegi dengan ukuran mm, di mana mm merupakan jumlah baris matriks AA. Persamaan (6.25) dalam bentuk matriks akan terlihat seperti Persamaan dibawah
Jika diperhatikan, kita dapat mengetahui mengetahui nilai xn=tnum,nxn=tnum,n. Nilai tersebut selanjutnya dapat digunakan untuk melakukan proses susbtitusi pada nilai lainnya. Proses substitusi ini disebut sebagai backward substitution. Proses dekomposisi atau faktorisasi LU digambarkan pada Gambar 6.1.
Dekomposisi LU didasarkan pada operasi baris elementer. Pertama, kita perlu menemukan matriks segitiga atas yang sesuai dengan matriks AA. Solusi untuk melakukan dekomposisi bisa jadi tak terhingga, namun solusi yang paling sederhana adalah mengubah matriks AA menjadi matriks row echelon form. Kedua, LL harus menjadi matriks segitiga bawah yang mereduksi ke-ll dengan mengikuti operasi baris yang sama yag menghasilkan UU. Kita dapat menggunakan algoritma Doolittle untuk menghasilkan LL, di mana nilai setiap entri dalam matriks segitiga bawah merupakan pengali yang digunakan untuk menghilangkan entri yang sesuai untuk setiap proses row replacement.
Pada praktiknya, proses eliminasi Gauss untuk memperoleh matriks UU kadang menghasilkan nol di kolom pivotnya. Kondisi tersebut mengharuskan kita untuk melakukan proses row swapping atau pertukaran baris (biasanya dengan baris bawahnya) untuk pivot bukan nol. Jika proses tersebut berhasil dilakukan bisa jadi matriks AA mungkin setara dengan matriks LU, tetapi tidak sama dalam hal urutan nilai pada tiap barisnya. Agar kita dapat memperoleh hasil yang sama (matriks A sama dengan matriks LU), diperlukan matriks ketiga, PP. Matriks ini merupakan matriks identitas dengan ukuran sama dengan matriks AA. Jika pertukaran baris dilakukan selama proses pembentukan matriks UU, maka pertukaran baris yang sama juga akan diimplemenntasikan pada matriks PP. oleh karena itu, dalam praktiknya matriks A=PLUA=PLU dan perkalian dengan matriks PP berfungsi untuk mengembalikan urutan baris.
Contoh 6.6 Selesaikan sistem persamaan linier berikut menggunakan faktorisasi LU
Simpan pengali tiap tahapan pada masing-masing elemen matriks LL. Hasil operasi tersebut akan menghasilkan matriks triangular UU.
