Perhitungan faktor Cholesky

11

Jadi teorema dekomposisi Cholesky menyatakan bahwa setiap matriks definitif positif pasti simetris nyata memiliki dekomposisi Cholesky mana adalah matriks segitiga lebih rendah.MM=LLL

Mengingat , kita sudah tahu ada algoritma cepat untuk menghitung faktor Cholesky .ML

Sekarang, anggaplah saya diberi sebuah matriks persegi panjang , dan saya tahu bahwa adalah pasti positif. Adakah cara untuk menghitung faktor Cholesky dari tanpa menghitung secara eksplisit dan kemudian menerapkan algoritma faktorisasi Cholesky?m×nAAALAAAA

Jika adalah matriks segi empat yang sangat besar yang melakukan secara eksplisit tampak sangat mahal dan karenanya pertanyaannya.AAA

smilingbuddha
sumber
Lebih dari biaya pembentukan matriks lintas-produk, pendekatan ini juga kuadratkan nomor kondisi . Jika hampir tidak memiliki peringkat, maka ini tentu cara yang buruk untuk melanjutkan. AAA
JM
Pertanyaan ini dan pertanyaan ini menanyakan hal yang sama dengan cara yang berbeda. Jawaban di utas ini (dan jawaban di bawah) harus bermanfaat bagi Anda.
Damien

Jawaban:

8

Ya, Anda dapat memperoleh faktor (hingga tanda-tanda entri) menggunakan dekomposisi QR; lihat jawaban ini . Perhatikan bahwa jika semua yang Anda minati adalah menyelesaikan masalah kuadrat terkecil yang mengarah ke persamaan normal yang melibatkan , Anda dapat menggunakan dekomposisi QR secara langsung.ATA

Christian Clason
sumber
7

Iya. Hitung faktorisasi dan ambil ; skala ulang baris jika perlu (dengan mengubah beberapa tanda mereka) untuk membuat tanda diagonal nonnegatif (karena faktor Cholesky didefinisikan memiliki diagonal nonnegatif).L = R T RQRL=RTR

Untuk faktorisasi QR yang jarang, lihat, misalnya, http://dl.acm.org/citation.cfm?id=174408

Arnold Neumaier
sumber