迭代方法的复杂性？

Question

问题：

我想实现Jacobi 方法。它类似于不动点方法：

Xn+1 = P Xn +Q

if X* verify X=PX +Q 

then if Xn converge then it converge to X*

假设我成功找到 alpha <1，使得：

||PX|| < alpha * ||X|| （通常 alpha 是 P 的特征值的最大值，但这里并不重要）

然后我的方法将收敛。

复杂度：

我想计算这种算法的复杂度。假设我想要 ||Xn-X*||小于 epsilon。 对于给定的 alpha，我可以计算 n，从而验证上述不等式。但就我而言，我可以证明这样的阿尔法存在，但我没有他的价值。

是否有在不明确知道 alpha 的情况下计算此类迭代方法的复杂性的方法？

提前致谢

Answer 1

没有更多信息：否。

为了有一个界限，您需要证明该过程在所有 alpha 值上均匀收敛。但这种收敛并不存在（除非你有更强的条件，例如 alpha < 0.9

不知道为什么你不能生成一个建设性的过程来找到 alpha 的上限 <1 if你可以证明存在性。证明一个方法收敛只是简单地通过明确地找到其值来找到一个相关范数，其中矩阵范数

。

证明

让epsilon > 0。
假设我们可以通过一些 f(x) 来限制迭代次数，其中 f: R+ --> N。
即，如果e_n = ||Xn - X*||，我们假设对于所有n > f(ε)。 e_n < epsilon。

我们将证明存在一个有效的 alpha 和一个 N ，使得 N > f(ε)。 e_N＞ epsilon。

关键的观察结果是要注意我们的函数 f 与 alpha 的值无关。我们假设迭代过程存在某个上限，但不知道 alpha 的值，只知道 alpha<1。因此，找到满足该条件的 alpha 就足够了，该 alpha 打破了对 f 的初始假设，从而达到了我们想要的矛盾。

这一点很微妙，因为有效边界 f 的存在实际上取决于 alpha，因为假设它限制基于 alpha 所在矩阵的迭代。是“定义”的。尽管由于 alpha 本身未知，我们必须证明 f 对于 alpha 的所有值都有效，这就是我们从正常收敛转向一致收敛的地方。

我们选择了 epsilon，并采用 N = f(epsilon)+1。
根据我们的假设e_N < epsilon，所以我们简单地取 alpha = (2*epsilon/e_0) ^ 1/2N 假设 2*epsilon/e_0 1 否则我们可以将 epsilon 替换为任何值 << 1.

e_n+1 = || X(n+1) - X* ||
      = || PXn + Q - PX* - Q ||
      = || P(Xn - X*) ||
      <= ||P|| ||Xn-X*||
      = ||P|| e_n

正如我所说，在没有额外信息的情况下，很容易构造 P 使得上面的不等式实际上相等。例如，P = I*k 产生所有实数 k 的相等性。因此存在 P 使得 e_n+1 = ||P|| e_n = ... = ||P||^(n+1) * e_0

我们最后的观察结果是，即使 ||PX|| < alpha * ||X|| 可能存在 X 使得： ||PX|| > alpha^2 * ||X||。
例如，如果P = I * alpha，我们知道alpha<1并且前述对于所有X都成立。 （同样，由于 P 上没有其他信息，因此可能存在这样的 X 就足够了。）

如果我们插入 alpha > 我们得出以下结论是可能的：

e_N = ||P||^N * e_0
    > (alpha^2)^N * e_0
    = alpha^2N * e_0
    = 2*epsilon  // since alpha = (2*epsilon/e_0) ^ 1/2N
    > epsilon
    > e_N // since we assumed we had a bound, and e_N < epsilon

数字不能大于其自身。

量子ED。