Menghitung determinan sambil menyelesaikan

11

Saya memecahkan untuk matriks definitif positif jarang besar menggunakan metode konjugat gradien (CG). Dimungkinkan untuk menghitung penentu menggunakan informasi yang dihasilkan selama penyelesaian? $Ax=b$ $A$ $A$

linear-algebra optimization krylov-method conjugate-gradient Manuel Schmidt
sumber

Mengapa Anda ingin menghitung determinan? Hasil seperti itu pasti akan menjadi underflow atau overflow untuk matriks yang besar pula. Saya akan lebih amal jika Anda diminta untuk menghitung nomor kondisi, tetapi jangan buang waktu Anda pada faktor penentu!

Anda mungkin sudah tahu itu, tetapi nilai-nilai Ritz selama proses gradien konjugasi konvergen ke nilai eigen dari matriks, dan Anda bisa mendapatkan estimasi sederhana untuk penentu dari ini.

shuhalo

10

Menghitung determinan matriks jarang biasanya semahal pemecahan langsung, dan saya ragu bahwa CG akan sangat membantu dalam menghitungnya. Dimungkinkan untuk menjalankan CG untuk iterasi (di mana adalah ) untuk menghasilkan informasi untuk seluruh spektrum , dan untuk kemudian menghitung determinan sebagai produk dari nilai eigen, tetapi ini akan menjadi lambat dan secara numerik tidak stabil. $n$ $A$ $n \times n$ $A$

Ini akan menjadi ide yang lebih baik untuk menghitung faktorisasi Cholesky yang jarang-langsung dari matriks Anda, katakanlah , di mana adalah segitiga yang lebih rendah. Kemudian mana hanyalah produk dari entri diagonal dari matriks segitiga-bawah karena nilai eigen dari matriks segitiga terletak di sepanjang diagonal-nya. $A = L L^H$ $L$

det (A) = det (L) det (L^{H}) = | det (L) |^{2},

$\text{det}(A) = \text{det}(L) \text{det}(L^H) = |\text{det}(L)|^2,$

det (L)

$\text{det}(L)$

L

$L$

Dalam kasus matriks non-singular umum, dekomposisi LU yang diputar harus digunakan, katakanlah , di mana adalah matriks permutasi, sehingga Karena adalah matriks permutasi, , dan, dengan konstruksi, $PA=LU$ $P$

det (A) = det (P^{- 1}) \cdot det (L) \cdot det (U) .

$\text{det}(A) = \text{det}(P^{-1}) \cdot \text{det}(L) \cdot \text{det}(U).$

P

$P$

det (P) = \pm 1

$\text{det}(P)=\pm 1$

L

$L$ biasanya akan memiliki diagonal dari semua yang, yang menyiratkan bahwa

. Dengan demikian Anda dapat menghitung

sebagai

dan sekali lagi mengenali bahwa determinan matriks segitiga adalah produk dari entri diagonalnya. Dengan demikian, biaya komputasi penentu pada dasarnya hanya biaya faktorisasi.

det (L) = 1

$\text{det}(L)=1$

det (A)

$\text{det}(A)$

\pm det (U)

$\pm \text{det}(U)$

Jack Poulson
sumber

A

$A$

10^{6} x 10^{6}

$10^6 x 10^6$

@ManuelSchmidt Matriks jarang dengan ukuran sebesar itu yang dihasilkan dari diskritisasi tipe elemen hingga biasanya dapat dengan mudah difaktorkan dengan (misalnya) metode multifrontal. Saya setuju bahwa faktorisasi Cholesky harus digunakan jika matriks Anda adalah HPD (dan generalisasi argumen saya di atas sudah jelas).

Jack Poulson

Terima kasih atas jawaban & balasan cepat Anda. Sayangnya matriks tidak memiliki struktur spezial (yang akan memungkinkan faktorisasi yang mudah).

Manuel Schmidt

2

Saya ingin tahu mengapa Anda perlu menghitung penentu matriks. Apakah nilai eigen tertinggi dan terendah tidak memadai?

Jack Poulson

Ini adalah bagian dari fungsi distribusi probabilitas yang kompleks dan tidak hanya konstanta normalisasi. Saya tahu distribusi dapat diperhitungkan (dan itulah yang kami lakukan saat ini) namun kami memiliki banyak data untuk dimodelkan dan masing-masing faktor menjadi sangat besar.

Manuel Schmidt

6

$A$ $B$ $\textrm{dim}A \ll \textrm{dim} B$ $\textrm{dim}B=\infty$

$B$ $A$ $B$ $A$ $B$ $\textrm{det}A$ $\textrm{det}B$ $A$ $B$

det A = \prod_{j = 1 \dots dim A} λ_{i} (A) \approx \prod_{j = 1 \dots dim A} λ_{i} (B) \prod_{j = dim A + 1 \dots dim B} λ_{i} (B)

$\textrm{det}A = \prod_{j=1\ldots \textrm{dim}A} \lambda_i(A) \approx \prod_{j=1\ldots \textrm{dim}A} \lambda_i(B) \prod_{j=\textrm{dim}A+1\ldots \textrm{dim}B} \lambda_i(B)$

B

$B$

A

$A$

dim B = \infty

$\textrm{dim}B=\infty$

det A

$\textrm{det}A$

det B

$\textrm{det}B$

Wolfgang Bangerth
sumber

Ternyata ada beberapa algoritma kami yang benar-benar indah dan praktis yang melibatkan perhitungan faktor penentu yang cukup besar. Lihat www-m3.ma.tum.de/foswiki/pub/M3/Allgemeines/…

Matt Knepley

2

Tanpa memasukkan (lagi) ke dalam mengapa dan bagaimana faktor-faktor penentu itu jahat, mari kita asumsikan bahwa operator Anda tidak mudah dipengaruhi faktor atau tidak tersedia sebagai matriks sama sekali dan bahwa Anda benar - benar perlu memperkirakan faktor penentu tersebut.

$A$ $A$

Anda mungkin dapat merekayasa balik bagaimana estimasi penentu ini muncul dalam penerapan standar CG dengan mengikuti Bagian 6.7.3 buku ini.

Dominique
sumber

2

d e t (A) = \prod_{i = 1}^{n} α_{k}^{- 1},

$det(A) = \prod_{i = 1}^n \alpha_k^{-1},$

α_{k} = \frac{r_{k}^{T} r_{k}}{p_{k}^{T} A p_{k}}

$\alpha_k = \cfrac{r_k^Tr_k}{p_k^TAp_k}$

r_{k} \neq 0 \forall k = 1, \dots, n

$r_k \ne 0 \;\,\forall k=1, \ldots, n$

R

$R$

r_{k}

$r_k$

P

$P$

p_{k}

$p_k$

p_{k} = - r_{k} + \sum_{i = 1}^{k - 1} γ_{i} r_{i} .

$p_k = -r_k + \sum_{i=1}^{k-1}\gamma_i r_i.$

d e t (P) = (- 1)^{n} d e t (R)

$det(P) = (-1)^n det(R)$

r_{k}

$r_k$

p_{k}

$p_k$

A

$A$

\prod_{k = 1}^{n} α_{k} = \prod_{k = 1}^{n} \frac{r_{k}^{T} r_{k}}{p_{k}^{T} A p_{k}} = \frac{d e t (R^{T} R)}{d e t (P^{T} A P)} = \frac{d e t (R^{T} R)}{d e t (A) d e t (P^{T} P)} = (d e t (A))^{- 1} .

$\prod_{k = 1}^n \alpha_k = \prod_{k = 1}^n \frac{r_k^T r_k}{p_k^TAp_k} = \frac{det(R^TR)}{det(P^TAP)} = \frac{det(R^TR)}{det(A)det(P^TP)}= (det(A))^{-1}.$

Yermek
sumber

Menghitung determinan sambil menyelesaikan

Jawaban: