切比雪夫迭代

切比雪夫迭代是一種求解非對稱問題的方法（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)）。具體來說，一旦計算出一個 段，我們就可以開始依次計算 、 和 的相應段。