迭代法

迭代法（英語：Iterative Method），在計算數學中，迭代是通過從一個初始估計出發尋找一系列近似解來解決問題（一般是解方程式或者方程組）的數學過程，為實現這一過程所使用的算法統稱，每一次找到的近似解都會用來求得下一個近似解。

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

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

吸引不動點

若方程式可以寫成f(x) = x的形式，且有一個解x是函數f的吸引不動點，則可以從x的吸引盆地中的一個點x₁開始，令x_n+1 = f(x_n)，n ≥ 1，則數列{x_n}_n ≥ 1會收斂在解x。此處x_n是x第n次迭代或是近似的值，而x_n+1則是下一次迭代或是近似的值。在數值方法中，常會用有括號的上標表示迭代次數，加上括號的目的是不會和其他上標的意義弄混（例如，x⁽ⁿ⁺¹⁾ = f(x⁽ⁿ⁾)）。若函數f是連續可微，其收斂的充份條件是在不動點的附近，其導數的譜半徑嚴格小於1。若在不動點處滿足此條件，必定在不動點附近存在夠小的鄰區（吸引盆地）。

線性系統

求解線性方程組的迭代方法主要分為兩類，分別是定常迭代法和克雷洛夫子空間法。

定常迭代法

簡介

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

定義

迭代法可定義為

$\mathbf {x} ^{k+1}:=\Psi (\mathbf {x} ^{k})\,,\quad k\geq 0$

針對特定的線性系統$A\mathbf {x} =\mathbf {b}$以及真實解$\mathbf {x} ^{*}$，誤差為

$\mathbf {e} ^{k}:=\mathbf {x} ^{k}-\mathbf {x} ^{*}\,,\quad k\geq 0\,.$

迭代法稱為線性，若存在以下矩陣$C\in \mathbb {R} ^{n\times n}$使得

$\mathbf {e} ^{k+1}=C\mathbf {e} ^{k}\quad \forall \,k\geq 0$

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

$\lim _{k\rightarrow \infty }C^{k}=0\,.$

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

$\rho (C)<1\,.$

基礎的迭代法作用原理是將矩陣$A$分割成

$A=M-N$

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

$M\mathbf {x} ^{k+1}=N\mathbf {x} ^{k}+b\,,\quad k\geq 0\,.$

依此，迭代矩陣為

$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年代開始的，由Cornelius Lanczos、Magnus Hestenes及Eduard Stiefel分別獨立的發現，但當時對其本質以及應用都還有誤解。數學家要到1970年代才瞭解此方法應用在偏微分方程式上的效果也很好，特別是在橢圓型偏微分方程式。

參見

• 解析解
• 迭代
• 迭代函數
• 逼近
• 數值分析
• 非線性最小平方法
• 求根算法

外部連結

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