迭代法

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

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

迭代法相对应的是直接法，設法用有限的步驟來找到解。若不考慮捨入誤差的話，直接法有可能得到正確答案（例如用高斯消去法求解線性系統A\mathbf{x}=\mathbf{b}時）。若是非線性方程，只能使用迭代法。不過，就算是線性系統，若是有許多的變數時（例如上百萬個），即使用目前最好的電腦，使用直接法的成本太高（而且有些情形下是不可行的），此時也可以用迭代法來計算。

吸引不動點
若方程式可以寫成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）用近似原始算子的算子來求解線性系統，基於對結果誤差的量測（），形成了修正方程，並且重覆此一步驟。此方法很容易推導、實現及分析，但只針對特定矩陣才能確保其收斂。
定義
迭代法可定義為
:
\mathbf{x}^{k+1} := \Psi ( \mathbf{x}^k ) \,, \quad k\geq0

針對特定的線性系統 A\mathbf x= \mathbf b 以及真實解 \mathbf{x}^* ，誤差為
:
\mathbf{e}^k := \mathbf{x}^k - \mathbf{x}^* \,, \quad k\geq0\,.

迭代法稱為線性，若存在以下矩陣 C \in \R^{n\times n} 使得
:
\mathbf{e}^{k+1} = C \mathbf{e}^k \quad \forall \, k\geq0

此一矩陣稱為迭代矩陣。
有特定迭代矩陣 C 的迭代法是收斂的，若下式成立
:
\lim_{k\rightarrow \infty} C^k=0\,.

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

基礎的迭代法作用原理是將矩陣 A 成
:
A = M - N

且此處的矩陣 M 需要是很容易取逆矩陣的。
因此，迭代法定義為
:
M \mathbf{x}^{k+1} = N \mathbf{x}^k + b \,, \quad k\geq0\,.

依此，迭代矩陣為
:
C = I - M^{-1}A = M^{-1}N\,.

範例
有些基礎的定常迭代法，會將矩陣 A 以以下方式分割
:
A = D+L+U\,,\quad D := \text{diag}( (a_{ii})_i)

其中 D 是 A 的對角線部份， L 是 A 的嚴格下三角矩阵，而 U 是 A 的嚴格上三角矩阵。

• ： M:=\frac{1}{\omega} I \quad (\omega \neq 0)
• 雅可比法： M:=D
• 阻尼雅可比法： M:=\frac{1}{\omega}D \quad (\omega \neq 0)
• 高斯-赛德尔迭代: M:=D+L
• 逐次超鬆弛迭代法（SOR）： M:=\frac{1}{\omega}D+L \quad (\omega \neq 0)
• 对称逐次超松弛迭代法 (SSOR): M := \frac{1}{\omega (2-\omega)} (D+\omega L) D^{-1} (D+\omega U)

\quad (\omega \not
\in \{0,2\})
線性定常迭代法也稱為。

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

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

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

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

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

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

參考資料
外部連結
*[http://www.netlib.org/linalg/html_templates/Templates.html Templates for the Solution of Linear Systems]
[http://www-users.cs.umn.edu/~saad/books.html Y. Saad: Iterative Methods for Sparse Linear Systems*, 1st edition, PWS 1996]