计算科学 - 单次 Gauss-Seidel 迭代中的唯一坐标（解） - 吾爱随笔录

单次 Gauss-Seidel 迭代中的唯一坐标（解）

计算科学线性代数矩阵迭代法计算几何线性求解器

2021-12-15 01:24:28

我设法将某些计算问题简化为以下线性系统的 Gauss-Seidel 解：

A x = L y,

$Ax=Ly,$ 在哪里

A, L \in R^{n \times n}

$A, L\in\mathbb{R}^{n\times n}$ 是加权拉普拉斯矩阵（对称，半正定；负非对角线条目，行（列）总和（绝对值）到正对角线条目；矩阵特征值

0

$0$ 对应于

1_{n}

$1_n$ 零空间的特征向量），和

x, y \in R^{n \times 2}

$x,y\in\mathbb{R}^{n\times 2}$ 是未知的向量

x

$x$ . 解决方案有形式

x_{i}^{[k + 1]} = (b_{i} - \sum_{j = 1}^{i - 1} a_{i j} x_{j}^{[k + 1]} - \sum_{j = i + 1}^{n} a_{i j} x_{j}^{[k]}) / a_{i i},

$x_i^{[k+1]} = \left.\left(b_i - \sum_{j=1}^{i-1}a_{ij}x_j^{[k+1]} - \sum_{j=i+1}^{n}a_{ij}x_j^{[k]}\right)\middle/a_{ii}\right.,$ 在哪里

b_{i}

$b_i$ 是个

i^{t h}

$i^{th}$ 进入

L y

$Ly$ . 注意，使用 Gauss-Seidl，更新

x_{i}

$x_i$ 立即生效，即计算如下

x_{i + 1}

$x_{i+1}$ 是基于新的价值

x_{i}

$x_i$ 之前已经计算过了。

现在，假设一个迭代由所有的单个更新组成 $x_i$ 以某种任意顺序。换句话说，每个 $x_i$ 在迭代中只考虑一次（并且只更新一次）。我的问题是：是否可以保证在初始的单次迭代之后 $x^{[0]}=y$ ，解决方案 $x^{[1]}$ 具有所有唯一坐标，即没有两行 $x^{[1]}$ 那是平等的吗？

你可以假设初始 $x^{[0]}=y$ 具有非唯一坐标。如果无法以这种方式解决唯一性，我将不胜感激关于坐标遍历顺序的建议，以增加实现唯一性的机会（即，没有两个坐标具有相同的值）。

3个回答

更新新解决方案的顺序对从初始数据到第一个近似值产生的值有很大影响。一些更新的值将与 jacobi 迭代相同，而其他值将包含最新信息，如 Gauss-Seidel。给定一个特定的顺序，如果初始向量可能有两个相同的值 $x_0$ 具有非唯一值。但是对于两个不同的排序，如果解向量很大，并且更新 gauss-seidel 公式的顺序是随机的，那么产生相似的第一次迭代的可能性就越大。我不确定是否有证据证明不同的排序会产生唯一的第一次迭代，但即使它们可能是非唯一的，这种可能性也很小。

Gauss-Seidel 的应用是一个非奇异仿射算子（对于 Gauss-Seidel 收敛的矩阵和排序），我们称线性部分 $G$ . 也就是说，与 $A = L + D + U$ ，我们有 $x_1 = (L+D)^{-1}(b - U x_0) = \tilde b + G x_0$ . 不失一般性，我们取 $b = 0$ ，在这种情况下 $\tilde b = (L+D)^{-1} b = 0$ ，因此 $x_1 = G x_0$ 和 $G = (L+D)^{-1} U$ 非奇异的。

如果我理解你的问题，你是在问是否观察 $G x_0 = G y_0$ （即 Gauss-Seidel 一次迭代后的相同结果）意味着 $x_0 = y_0$ . 好吧， $G (x_0 - y_0) = 0$ 只有当 $x_0 - y_0 = 0$ 或者如果 $G$ 是单数。

请注意，Gauss-Seidel 可能会非常快地抑制某些模式，因此即使初始向量不同，您也可以获得非常接近的迭代。

这个问题是不恰当的。Gauss-Seidel 是一种求解线性方程组的迭代方法，该方程组保证对某些矩阵收敛。如果线性方程组的解包含非唯一值，则 Gauss-Seidel 将收敛到非唯一值。应用更新的迭代次数和顺序无关紧要。

其它你可能感兴趣的问题

上一篇尝试通过传递 -mat_view_draw 让 PETSc 绘制到 X 终端时出现错误消息下一篇多维最小化：GNU GSL C++ 错误代码 27 - 迭代没有朝着解决方案取得进展