假设我有一个方阵$\mathbf{A} \in \mathbb{R}^{n\times n}$和一个向量$\mathbf{b}\in\mathbb{R}^n$. 在我的应用程序中，我需要完成两件事。

1. 我需要找到线性系统的解决方案$\mathbf{A}\mathbf{x}=\mathbf{b}$.
2. 我需要计算的对数行列式$\mathbf{A}$.

天真地，我可以通过计算特征分解来实现这一点$\mathbf{A} = \mathbf{Q}\Lambda\mathbf{Q}^{-1}$并使用它来获得逆$\mathbf{A}^{-1}=\mathbf{Q}\Lambda^{-1}\mathbf{Q}^{-1}$和对数行列式为$\sum_{i=1}^n \log \Lambda_{ii}$. 在这种方法中，我需要一个$\mathcal{O}(n^3)$计算特征分解和另一个的操作$\mathcal{O}(n^3)$操作以获得逆$\mathbf{Q}$. 这是最好的方法吗？是否有一个程序只涉及一个$\mathcal{O}(n^3)$手术？

矩阵$\mathbf{A}$确实有一定的特殊结构。它的形式$\mathbf{A} = \mathrm{Id}_n + \epsilon \mathbf{B}$在哪里$\mathbf{B}\in\mathbb{R}^{n\times n}$， 所以$\mathbf{A}$离身份不远了。