Mengulas Dekomposisi Cholesky dan Dekomposisi LU Dibidang Matematika – Dalam aljabar linier, dekomposisi Cholesky atau faktorisasi Cholesky adalah dekomposisi matriks Hermitian, berdefinisi positif menjadi produk matriks segitiga bawah dan transpos konjugasinya, yang berguna untuk efisiensi solusi numerik, misalnya simulasi Monte Carlo.
Mengulas Dekomposisi Cholesky dan Dekomposisi LU Dibidang Matematika
transitionmathproject – Itu ditemukan oleh André-Louis Cholesky untuk matriks nyata. Jika dapat diterapkan, dekomposisi Cholesky kira-kira dua kali lebih efisien daripada dekomposisi LU untuk menyelesaikan sistem persamaan linier, di mana L adalah matriks segitiga satuan bawah (unit segitiga), dan D adalah matriks diagonal. Artinya, elemen diagonal dari L harus 1 dengan biaya tambahan matriks diagonal D dalam dekomposisi. Keuntungan utama adalah bahwa dekomposisi LDL dapat dihitung dan digunakan dengan algoritma yang pada dasarnya sama, tetapi menghindari ekstraksi akar kuadrat.
Baca Juga : Matriks Jarang, Matriks Yang Rata – Rata Elemennya Bernilai 0
Aplikasi
Sistem berbentuk Ax = b dengan A simetris dan pasti positif cukup sering muncul dalam aplikasi. Misalnya, persamaan normal dalam masalah kuadrat terkecil linier adalah dalam bentuk ini. Mungkin juga terjadi bahwa matriks A berasal dari fungsi energi, yang harus positif dari pertimbangan fisik. ini sering terjadi dalam solusi numerik persamaan diferensial parsial. Dekomposisi Cholesky umumnya digunakan dalam metode Monte Carlo untuk mensimulasikan sistem dengan beberapa variabel berkorelasi. Matriks kovarians didekomposisi untuk menghasilkan segitiga bawah L.
Menerapkan ini ke vektor sampel yang tidak berkorelasi u menghasilkan vektor sampel Lu dengan sifat kovarians dari sistem yang dimodelkan. Filter Kalman yang tidak diberi wewangian biasanya menggunakan dekomposisi Cholesky untuk memilih satu set yang disebut titik sigma. Filter Kalman melacak keadaan rata-rata sistem sebagai vektor x dengan panjang N dan kovarians sebagai matriks N × N P. Matriks P selalu positif semi-pasti dan dapat didekomposisi menjadi LLT. Kolom L dapat ditambahkan dan dikurangkan dari mean x untuk membentuk himpunan vektor 2N yang disebut titik sigma. Titik sigma ini sepenuhnya menangkap mean dan kovarians dari status sistem.
Ada berbagai metode untuk menghitung dekomposisi Cholesky. Kompleksitas komputasi dari algoritma yang umum digunakan adalah O(n3) secara umum. Algoritma yang dijelaskan di bawah semua melibatkan sekitar (1/3)n3 FLOP (n3/6 perkalian dan jumlah penambahan yang sama) untuk rasa nyata dan ( 4/3)n3 FLOPs untuk rasa kompleks, di mana n adalah ukuran matriks A. Oleh karena itu, mereka memiliki setengah biaya dekomposisi LU, yang menggunakan 2n3/3 FLOPs (lihat Trefethen dan Bau 1997). Untuk matriks kompleks dan real, perubahan tanda arbitrer yang tidak penting dari elemen diagonal dan elemen off-diagonal terkait diperbolehkan. Ekspresi di bawah akar kuadrat selalu positif jika A real dan pasti-positif.
Misalkan kita ingin menyelesaikan sistem persamaan linier yang dikondisikan dengan baik. Jika dekomposisi LU digunakan, maka algoritme tidak stabil kecuali jika kita menggunakan semacam strategi pivot. Dalam kasus terakhir, kesalahan tergantung pada apa yang disebut faktor pertumbuhan matriks, yang biasanya (tetapi tidak selalu) kecil. Sekarang, anggaplah bahwa dekomposisi Cholesky dapat diterapkan. Seperti disebutkan di atas, algoritma akan dua kali lebih cepat. Selanjutnya, tidak perlu memutar, dan kesalahannya akan selalu kecil.
Salah satu perhatian dengan dekomposisi Cholesky yang harus diperhatikan adalah penggunaan akar kuadrat. Jika matriks yang difaktorkan adalah pasti positif seperti yang disyaratkan, angka-angka di bawah akar kuadrat selalu positif dalam aritmatika eksak. Sayangnya, angka bisa menjadi negatif karena kesalahan pembulatan, dalam hal ini algoritme tidak dapat dilanjutkan.
Namun, ini hanya dapat terjadi jika matriks sangat tidak berkondisi. Salah satu cara untuk mengatasi hal ini adalah dengan menambahkan matriks koreksi diagonal ke matriks yang sedang didekomposisi dalam upaya untuk mempromosikan definititas positif. Meskipun ini mungkin mengurangi keakuratan dekomposisi, ini bisa sangat menguntungkan karena alasan lain. misalnya, ketika melakukan metode Newton dalam optimasi, menambahkan matriks diagonal dapat meningkatkan stabilitas ketika jauh dari optimal.
Dekomposisi LU
Dalam analisis numerik dan aljabar linier, dekomposisi bawah-atas (LU) atau faktorisasi memfaktorkan matriks sebagai produk dari matriks segitiga bawah dan matriks segitiga atas. Produk terkadang menyertakan matriks permutasi juga. Dekomposisi LU dapat dilihat sebagai bentuk matriks dari eliminasi Gaussian. Dekomposisi LU diperkenalkan oleh matematikawan Polandia Tadeusz Banachiewicz pada tahun 1938. Di atas kita mensyaratkan bahwa A adalah matriks bujur sangkar, tetapi semua dekomposisi ini dapat digeneralisasikan ke matriks persegi panjang juga.
Dalam kasus tersebut, L dan D adalah matriks bujur sangkar yang keduanya memiliki jumlah baris yang sama dengan A, dan U memiliki dimensi yang persis sama dengan A. Segitiga atas harus ditafsirkan hanya memiliki nol entri di bawah diagonal utama, yang dimulai dari pojok kiri atas. Demikian pula, istilah yang lebih tepat untuk U adalah bahwa itu adalah “bentuk eselon baris” dari matriks A. Sistem persamaan ini kurang ditentukan. Dalam hal ini, dua elemen tak-nol dari matriks L dan U adalah parameter dari solusi dan dapat diatur secara sewenang-wenang ke sembarang nilai bukan-nol.
Oleh karena itu, untuk menemukan dekomposisi LU yang unik, perlu dilakukan pembatasan pada matriks L dan U. Sebagai contoh, kita dapat dengan mudah meminta matriks segitiga bawah L menjadi matriks segitiga satuan (yaitu mengatur semua entri diagonal utamanya menjadi satu). Dekomposisi ini disebut dekomposisi Cholesky. Dekomposisi Cholesky selalu ada dan unik asalkan matriksnya pasti positif. Lebih lanjut, menghitung dekomposisi Cholesky lebih efisien dan secara numerik lebih stabil daripada menghitung beberapa dekomposisi LU lainnya. Untuk matriks (tidak selalu dapat dibalik) pada bidang apa pun, kondisi yang diperlukan dan cukup yang tepat di mana ia memiliki faktorisasi LU diketahui.
Kondisi diekspresikan dalam bentuk rangking dari submatriks tertentu. Algoritma eliminasi Gaussian untuk mendapatkan dekomposisi LU juga telah diperluas untuk kasus yang paling umum ini. Perhatikan bahwa dekomposisi yang diperoleh melalui prosedur ini adalah dekomposisi Doolittle: diagonal utama L hanya terdiri dari 1s. Jika kita melanjutkan dengan menghilangkan elemen di atas diagonal utama dengan menambahkan kelipatan kolom (daripada menghilangkan elemen di bawah diagonal dengan menambahkan kelipatan baris), kita akan memperoleh dekomposisi Crout, di mana diagonal utama U adalah 1s. Algoritma khusus telah dikembangkan untuk memfaktorkan matriks sparse yang besar. Algoritma-algoritma ini berusaha menemukan faktor-faktor sparse L dan U.
Baca Juga : Matematikawan Membangun Algoritme Untuk Korelasi Foton Sinar-X
Idealnya, biaya komputasi ditentukan oleh jumlah entri bukan nol, bukan oleh ukuran matriks. Algoritme ini menggunakan kebebasan untuk bertukar baris dan kolom untuk meminimalkan pengisian (entri yang berubah dari nol awal ke nilai bukan nol selama eksekusi suatu algoritme). Perlakuan umum pemesanan yang meminimalkan fill-in dapat diatasi dengan menggunakan teori graf. Prosedur di atas dapat diterapkan berulang kali untuk menyelesaikan persamaan beberapa kali untuk b yang berbeda. Dalam hal ini lebih cepat (dan lebih nyaman) untuk melakukan dekomposisi LU dari matriks A sekali dan kemudian menyelesaikan matriks segitiga untuk b yang berbeda, daripada menggunakan eliminasi Gaussian setiap kali.
Matriks L dan U dapat dianggap telah “mengkodekan” proses eliminasi Gaussian. Kita dapat menggunakan algoritma yang sama yang disajikan sebelumnya untuk menyelesaikan setiap kolom matriks X. Sekarang anggaplah B adalah matriks identitas berukuran n. Ini akan mengikuti bahwa hasil X harus invers dari A. Persamaan kedua mengikuti dari fakta bahwa determinan matriks segitiga hanyalah produk dari entri diagonalnya, dan bahwa determinan matriks permutasi sama dengan (− 1)S di mana S adalah jumlah pertukaran baris dalam dekomposisi.