迭代法

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

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

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

吸引不動點

若方程式可以寫成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）用近似原始算子的算子來求解線性系統，基於對結果誤差的量測（餘量（英語：Residual (numerical analysis)）），形成了修正方程，並且重覆此一步驟。此方法很容易推導、實現及分析，但只針對特定矩陣才能確保其收斂。

定義

迭代法可定義為

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

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

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

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

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

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

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

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

${\displaystyle \rho (C)<1\,.}$

基礎的迭代法作用原理是將矩陣${\displaystyle A}$分割（英語：Matrix splitting）成

${\displaystyle A=M-N}$

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

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

依此，迭代矩陣為

${\displaystyle C=I-M^{-1}A=M^{-1}N\,.}$

範例

有些基礎的定常迭代法，會將矩陣${\displaystyle A}$以以下方式分割

${\displaystyle A=D+L+U\,,\quad D:={\text{diag}}((a_{ii})_{i})}$

其中${\displaystyle D}$是${\displaystyle A}$的對角線部份，${\displaystyle L}$是${\displaystyle A}$的嚴格下三角矩陣，而${\displaystyle U}$是${\displaystyle A}$的嚴格上三角矩陣。

• 理察森法（英語：Modified Richardson iteration）：${\displaystyle M:={\frac {1}{\omega }}I\quad (\omega \neq 0)}$
• 雅可比法：${\displaystyle M:=D}$
• 阻尼雅可比法：${\displaystyle M:={\frac {1}{\omega }}D\quad (\omega \neq 0)}$
• 高斯-賽德爾迭代: ${\displaystyle M:=D+L}$
• 逐次超鬆弛迭代法（英語：Successive over-relaxation）（SOR）：${\displaystyle M:={\frac {1}{\omega }}D+L\quad (\omega \neq 0)}$
• 對稱逐次超鬆弛迭代法 (SSOR): ${\displaystyle M:={\frac {1}{\omega (2-\omega )}}(D+\omega L)D^{-1}(D+\omega U)\quad (\omega \not \in \{0,2\})}$

線性定常迭代法也稱為鬆弛迭代法（英語：Relaxation (iterative method)）。

克雷洛夫子空間法

主條目：克雷洛夫子空間

克雷洛夫子空間法（Krylov subspace method）的作法是初始餘量在A的前N次冪下（始於${\displaystyle A^{0}=I}$）的列空間張成的線性子空間。 近似解可以用在形成的數列上使餘量為最小值來求得。 克雷洛夫子空間法的原形方法是共軛梯度法（CG），其中假設系統矩陣${\displaystyle A}$是對稱正定。 針對對稱矩陣（也可能包括半正定矩陣）${\displaystyle A}$，可以用最小餘量法（英語：Minimal residual method）（MINRES）。 若是非對稱矩陣，可以用廣義最小餘量法（英語：generalized minimal residual method）（GMRES）及雙共軛梯度法（英語：biconjugate gradient method）（BiCG）。

克雷洛夫子空間法的收斂

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

預處理子

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

歷史

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

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

參見

• 數學主題

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

參考資料

1. Amritkar, Amit; de Sturler, Eric; Świrydowicz, Katarzyna; Tafti, Danesh; Ahuja, Kapil. Recycling Krylov subspaces for CFD applications and a new hybrid recycling solver. Journal of Computational Physics. 2015, 303: 222. Bibcode:2015JCoPh.303..222A. arXiv:1501.03358 . doi:10.1016/j.jcp.2015.09.040.

外部連結

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