迭代法

迭代法（），在计算数学中，迭代是通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的数学过程，为实现这一过程所使用的算法统称，每一次找到的近似解都會用來求得下一個近似解。

迭代法有許多種實現的方式，也有各自的迭代終止條件。常见的迭代法是梯度下降法、爬山算法、牛顿法，也有些屬於擬牛頓法（例如BFGS算法）。迭代法收斂是指在給定的近似初值下，對應的近似解數列收斂。一般會針對迭代法算法進行數學上嚴謹的收斂分析。不過也常常看到啟發式的迭代法。

迭代法相对应的是直接法，設法用有限的步驟來找到解。若不考慮捨入誤差的話，直接法有可能得到正確答案（例如用高斯消去法求解線性系統時）。若是非線性方程，只能使用迭代法。不過，就算是線性系統，若是有許多的變數時（例如上百萬個），即使用目前最好的電腦，使用直接法的成本太高（而且有些情形下是不可行的），此時也可以用迭代法來計算。
吸引不動點
若方程式可以寫成f(x) = x的形式，且有一個解x是函數f的吸引不动点，則可以從x的吸引盆地中的一個點x1開始，令xn+1 = f(xn)，n ≥ 1，則數列{xn}n ≥ 1會收斂在解x。此處xn是x第n次迭代或是近似的值，而xn+1則是下一次迭代或是近似的值。在數值方法中，常會用有括號的上標表示迭代次數，加上括號的目的是不會和其他上標的意義弄混（例如，x(n+1) = f(x(n))）。若函數f是連續可微，其收斂的充份條件是在不動點的附近，其導數的谱半径嚴格小於1。若在不動點處滿足此條件，必定在不動點附近存在夠小的鄰區（吸引盆地）。
 线性系统 
求解线性方程组的迭代方法主要分为两类，分别是定常迭代法和克雷洛夫子空间法。

 定常迭代法 
 簡介 
定常迭代法（Stationary iterative methods）用近似原始算子的算子來求解線性系統，基於對結果誤差的量測（），形成了修正方程，並且重覆此一步驟。此方法很容易推導、實現及分析，但只針對特定矩陣才能確保其收斂。
定義
迭代法可定義為

針對特定的線性系統以及真實解，誤差為

迭代法稱為線性，若存在以下矩陣使得

此一矩陣稱為迭代矩陣。
有特定迭代矩陣的迭代法是收斂的，若下式成立

有一個重要的定理，提到有特定迭代矩陣的迭代法，其收斂的條件若且唯若其谱半径小於1，也就是

基礎的迭代法作用原理是將矩陣成

且此處的矩陣需要是很容易取逆矩陣的。
因此，迭代法定義為

依此，迭代矩陣為

範例
有些基礎的定常迭代法，會將矩陣以以下方式分割

其中是的對角線部份，是的嚴格下三角矩阵，而是的嚴格上三角矩阵。
 ：
 雅可比法：
 阻尼雅可比法：
 高斯-赛德尔迭代: 
 逐次超鬆弛迭代法（SOR）：
 对称逐次超松弛迭代法 (SSOR): 
線性定常迭代法也稱為。

 克雷洛夫子空间法 

克雷洛夫子空间法（Krylov subspace method）的作法是初始余量在A的前N次幂下（始于）的列空间张成的线性子空间。 
近似解可以用在形成的數列上使余量為最小值來求得。
克雷洛夫子空间法的原形方法是共轭梯度法（CG），其中假設系統矩陣是對稱正定。
針對對稱矩陣（也可能包括半正定矩陣），可以用（MINRES）。
若是非對稱矩陣，可以用（GMRES）及（BiCG）。

克雷洛夫子空间法的收斂
因為這些方法會形成基，可以可知此方法會在N次迭代後收斂，其中N是系統大小。不過若是考慮捨入誤差，上述的論點就不成立，而且，實務上的N可以非常的大，迭代過程在到達N次之前，已達到所需的精。這類方法的分析很困難，視算子的譜函數之複雜程度而定。

預處理子
出現在定常迭代法的近似算子也可以整合到像是广义最小残量方法（GMRES）的克雷洛夫子空间法裡（的克雷洛夫子空间法，也可以視為是定常迭代法的加速），會將原始的運算子轉換為大概條件更好的運算子。預處理子（preconditioner）的建構是很大的研究領域。

歷史
13世紀的伊朗數學家卡西曾用迭代法，在《The Treatise of Chord and Sine》中計算sine 1°以及到很高的精度。
在卡爾·弗里德里希·高斯給學生的一封信中有用迭代法求解線性系統，其中求解一個四變數的系統，其作法是反覆的解出餘量最大的那個變數。

定常迭代法在在1950年代開始的研究中有穩固的基礎。共軛梯度法也是在1950年代開始的，由、及分別獨立的發現，但當時對其本質以及應用都還有誤解。數學家要到1970年代才瞭解此方法應用在偏微分方程上的效果也很好，特別是在橢圓型偏微分方程。

 参见 

解析解
迭代
迭代函数
逼近
数值分析
非线性最小二乘法
求根算法

參考資料

外部連結

Templates for the Solution of Linear Systems 
Y. Saad: Iterative Methods for Sparse Linear Systems, 1st edition, PWS 1996 


Category:数值分析