Вычисление определителя при решении

Я решаю для огромной разреженной положительно определенной матрицы используя метод сопряженного градиента (CG). Можно вычислить детерминант А, используя информацию, полученную в ходе решения?$Ax=b$$A$$A$

Вычисление детерминанта разреженной матрицы обычно так же дорого, как и прямое решение, и я скептически отношусь к тому, что CG очень поможет в ее вычислении. Можно было бы запустить CG для итераций (где A - n × n ), чтобы сгенерировать информацию для всего спектра A , а затем вычислить определитель как произведение собственных значений, но это будет как медленно, так и численно нестабильный.$n$$A$$n \times n$$A$

Лучше было бы вычислить разреженную факторизацию Холецкого вашей матрицы, скажем, , где L - нижнетреугольная. Тогда det ( A ) = det ( L ) det ( L H ) = | дет ( L ) | 2 , где det ( L ) является просто произведением диагональных элементов нижней треугольной матрицы L, поскольку собственные значения треугольной матрицы лежат вдоль ее диагонали.$A = L L^H$$L$

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

В случае общей неособой матрицы следует использовать развернутое LU-разложение, скажем, , где P - матрица перестановок, так что det ( A ) = det ( P - 1 ) ⋅ det ( L) ) ⋅ дет ( U ) . Поскольку P - матрица перестановок, det ( P ) = ± 1 и, по построению, $PA=LU$$P$

$$\text{det}(A) = \text{det}(P^{-1}) \cdot \text{det}(L) \cdot \text{det}(U).$$ $P$$\text{det}(P)=\pm 1$$L$будет обычно иметь диагональ всех единиц, что означает, что . Таким образом, вы можете вычислить det ( A ) как ± det ( U ) и снова признать, что определитель треугольной матрицы является просто произведением ее диагональных элементов. Таким образом, стоимость вычисления детерминанта, по сути, равна стоимости факторизации.$\text{det}(L)=1$$\text{det}(A)$$\pm \text{det}(U)$

$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$

$$\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$$A$$\textrm{dim}B=\infty$$\textrm{det}A$$\textrm{det}B$

Не вдаваясь (опять же) в то, почему и как детерминанты являются злыми, давайте предположим, что ваш оператор либо не легко разложим, либо просто не доступен как матрица вообще, и вам действительно нужно оценить его детерминант.

$A$$A$

Вы можете, вероятно, перепроектировать, как эта оценка детерминанта происходит в стандартной реализации CG, следуя внимательно Разделу 6.7.3 книги.

$$det(A) = \prod_{i = 1}^n \alpha_k^{-1},$$ $\alpha_k = \cfrac{r_k^Tr_k}{p_k^TAp_k}$$r_k \ne 0 \;\,\forall k=1, \ldots, n$$R$$r_k$$P$$p_k$ $$p_k = -r_k + \sum_{i=1}^{k-1}\gamma_i r_i.$$ $det(P) = (-1)^n det(R)$$r_k$$p_k$$A$ $$\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}.$$