计算科学 - 给定一个 SPD 三对角线性系统，我们可以预先计算以使任何三个索引都可以在 O(1) 时间内链接起来吗？ - 吾爱随笔录

给定一个 SPD 三对角线性系统，我们可以预先计算以使任何三个索引都可以在 O(1) 时间内链接起来吗？

计算科学线性代数泊松

2021-12-18 02:56:56

考虑一个对称正定三对角线性系统其中和。给定三个索引，如果我们假设只有严格在和之间的方程行成立，我们可以消除中间变量以获得形式为的。该方程将的值与相关联，而与“外部”影响无关（例如，如果引入了影响的约束）。

A x = b

$A x = b$

A \in R^{n \times n}

$A \in \mathbb{R}^{n \times n}$

b \in R^{n}

$b \in \mathbb{R}^n$

0 \leq i < j < k < n

$0 \le i < j < k < n$

i

$i$

k

$k$

u x_{i} + v x_{j} + w x_{k} = c

$u x_i + v x_j + w x_k = c$

v > 0

$v > 0$

x_{j}

$x_j$

x_{i}, x_{k}

$x_i,x_k$

x_{0}

$x_0$

问题：是否可以在时间内预处理线性系统，以便可以在的链接方程？ $Ax = b$ $O(n)$ $(i,j,k)$ $O(1)$

如果的对角线为 2，非对角线为且，则所需结果是离散泊松方程的解析结果。不幸的是，在不破坏三对角结构的情况下，不可能将一般的 SPD 三对角系统转换为常系数泊松方程，这主要是因为不同的变量可以有不同的“筛选”级别（局部严格的正定性）。例如，进行简单的对角线缩放自由度的一半，但不能消除另一半。 $A$ $-1$ $b = 0$ $x$ $2n-1$ $A$

直观地说，这个问题的解决方案需要安排问题，以便筛选量可以累积到线性大小的数组中，然后以某种方式“取消”以得出给定三元组的链接方程。

更新（更直观）：就 PDE 而言，我有一个一维离散线性椭圆问题，我想知道我是否可以在预计算中花费来产生某种可以查找的“分析”解决方案在时间内，我可以改变边界条件的位置。 $O(n)$ $O(1)$

3个回答

这是一个有点不稳定的解决方案，仅当变量之间的耦合始终是非退化的时才有效。为简单起见，假设。首先，为预先计算链接方程，例如 $b = 0$ $n$ $(0,i,n-1)$ $0 \le i < n$

x_{i} = a_{i} x_{0} + b_{i} x_{n - 1}

$x_i = a_i x_0 + b_i x_{n-1}$

现在，给定，我们可以结合第个和第个链接方程并消除得到 $i < j$ $i$ $j$ $x_{n-1}$

\begin{aligned} b_{j} x_{i} & = a_{i} b_{j} x_{0} + b_{i} b_{j} x_{n - 1} \\ b_{i} x_{j} & = a_{j} b_{i} x_{0} + b_{i} b_{j} x_{n - 1} \\ b_{j} x_{i} - b_{i} x_{j} & = (a_{i} b_{j} - a_{j} b_{i}) x_{0} \\ x_{i} & = \frac{a_{i} b_{j} - a_{j} b_{i}}{b_{j}} x_{0} + \frac{b_{i}}{b_{j}} x_{j} \end{aligned}

$\begin{aligned} b_j x_i &= a_i b_j x_0 + b_i b_j x_{n-1} \\ b_i x_j &= a_j b_i x_0 + b_i b_j x_{n-1} \\ b_j x_i - b_i x_j &= (a_i b_j - a_j b_i) x_0 \\ x_i &= \frac{a_i b_j - a_j b_i}{b_j} x_0 + \frac{b_i}{b_j} x_j \end{aligned}$

可以再次重复此过程以消除给定。不幸的是，我们在附近失去稳定性，或者一般来说，如果三对角系统解耦成独立的块。如果这没问题，但我担心微小但正值的故障。 $x_0$ $(i,j,k)$ $b_j = 0$ $b_j = 0$

我想知道您是否可以对 A 的循环归约分解（我相信它仍然是 O(n) 大小）做一些有用的事情，重用在分解 A 的连续主子矩阵时保持不变的尽可能多的块。我怀疑它给你O（1），但也许O（log n）......

这里再尝试一下，比对消法稳定，但还是不太好。

如果 $A$ 是一个 SPD 三对角矩阵，Meurant [1] 为 $B = A^{-1}$

B_{i j} = b_{i + 1} \dots b_{j} \frac{d_{j + 1} \dots d_{n}}{δ_{i} \dots δ_{n}}

$B_{ij} = b_{i+1}\cdots b_j \frac{d_{j+1}\cdots d_n}{\delta_i \cdots \delta_n}$

在哪里 $i \le j$ , $b_i$ 是负的非对角项和 $d_i,\delta_i$ 来源于 $UL$ 和 $LU$ 因式分解 $A$ . 链接公式为 $i < j < k$ 有形式

x_{j} = {(\begin{matrix} B_{j i} \\ B_{k i} \end{matrix})}^{T} {(\begin{array}{cc} B_{i i} & B_{i k} \\ B_{k i} & B_{k k} \end{array})}^{- 1} (\begin{matrix} x_{i} \\ x_{k} \end{matrix})

$x_j = \left(\begin{array}{c}B_{ji} \\ B_{ki}\end{array}\right)^T \left(\begin{array}{cc}B_{ii} & B_{ik} \\ B_{ki} & B_{kk}\end{array}\right)^{-1} \left(\begin{array}{c}x_i \\ x_k\end{array}\right)$

不幸的是，这个公式仍然不稳定。直觉上，如果 $i$ 和 $k$ 合理地接近三角洲源 $i$ 类似于一个在 $k$ , 和倒置的 $2 \times 2$ 矩阵接近奇异。

[1]：Gerard Meurant (1992)，“对称对角矩阵和块三对角矩阵的逆矩阵的评论”。

其它你可能感兴趣的问题

上一篇异步元胞自动机的并行 (GPU) 算法下一篇大型稀疏整数矩阵的算法