切比雪夫迭代

切比雪夫迭代是一种求解非对称问题的方法（Golub 和 van Loan 1996，§10.1.5；Varga，1962，第 5 章）。切比雪夫迭代避免了像其他非定常方法中那样需要计算内积。对于某些分布式内存架构，这些内积是效率瓶颈。避免内积的代价是，该方法需要充分了解系数矩阵 的谱，以便可以确定包络谱的椭圆；然而，通过 Manteuffel (1977) 开发并由 Ashby (1985) 实现的自适应构造可以克服这一困难。切比雪夫迭代适用于任何包络椭圆不包含原点的非对称线性系统。

切比雪夫迭代类似于共轭梯度法，只是不计算内积。必须选择标量 和 ，以便它们定义一系列具有共同中心 和焦点 和 的椭圆族，这些椭圆族包含包围 的谱（或更一般地，值域）的椭圆，并且对于该椭圆，收敛速率 是最小的

其中 是椭圆 轴的长度。

下面的伪代码假设椭圆退化为区间 ，即所有特征值都是实数。有关包括迭代参数 和 的自适应确定的代码，请参见 Ashby (1985)。

切比雪夫方法相对于广义最小残差法 (GMRES) 的优势在于只使用短的递归。另一方面，GMRES 保证在当前搜索空间中生成最小的残差。双共轭梯度法 (BCG) 也使用短的递归，但它不最小化某个合适的范数中的残差。然而，与切比雪夫迭代不同，它们不需要估计参数（ 的谱）。最后，由于超线性收敛行为，GMRES 和 BCG 在实践中可能更有效，而切比雪夫迭代不能期望获得超线性收敛行为。

对于对称正定系统，包络谱的椭圆退化为正 轴上的区间 ，其中 和 是 的最小和最大特征值，其中 是一个预处理器。在内积计算是瓶颈的情况下，可能有利的做法是首先使用共轭梯度法，从 CG 系数计算极端特征值的估计值，然后在这些近似值充分收敛后切换到切比雪夫迭代。对于从 GMRES 或 BCG 方法切换到切比雪夫迭代，也可以采用类似的策略。

在对称情况下（其中 和预处理器 都是对称的），如果从 和 计算 和 ，则切比雪夫迭代具有与共轭梯度法相同的上限。

高估或低估值域会带来严重的惩罚。例如，如果在对称情况下 被低估，则该方法可能会发散；如果它被高估，则收敛可能非常缓慢。对于非对称情况，可以做出类似的陈述。这意味着需要对 的谱有相当准确的界限，该方法才能有效（与共轭梯度法或广义最小残差法相比）。

在切比雪夫迭代中，一旦知道包含算子特征值（或者更确切地说，是值域）的椭圆，迭代参数就是已知的。因此，避免了像广义最小残差法和共轭梯度法中那样必要的内积计算。这避免了共轭梯度类型方法所需的同步点，因此具有分层或分布式内存的机器可以实现更高的性能（这也暗示了强大的并行化特性 (Saad 1989, Dongarra et al. 1991)）。具体来说，一旦计算出一个 段，我们就可以开始依次计算 、 和 的相应段。