查看“︁迭代法”︁的源代码

{{NoteTA
|T=zh-hans:迭代法;zh-hant:迭代法;
|1=zh-hans:迭代;zh-hant:迭代;
|G1 = Math
}}

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

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

迭代法相对应的是直接法，設法用有限的步驟來找到解。若不考慮[[捨入誤差]]的話，直接法有可能得到正確答案（例如用[[高斯消去法]]求解線性系統<math>A\mathbf{x}=\mathbf{b}</math>時）。若是[[非線性系統|非線性方程]]，只能使用迭代法。不過，就算是線性系統，若是有許多的變數時（例如上百萬個），即使用目前最好的電腦，使用直接法的成本太高（而且有些情形下是不可行的），此時也可以用迭代法來計算<ref>{{Cite journal|doi=10.1016/j.jcp.2015.09.040|title=Recycling Krylov subspaces for CFD applications and a new hybrid recycling solver|year=2015|last1=Amritkar|first1=Amit|last2=de Sturler|first2=Eric|last3=Świrydowicz|first3=Katarzyna|last4=Tafti|first4=Danesh|last5=Ahuja|first5=Kapil|journal=Journal of Computational Physics|volume=303|page=222|arxiv=1501.03358|bibcode=2015JCoPh.303..222A}}</ref>。
==吸引不動點==
若方程式可以寫成''f''(''x'') = ''x''的形式，且有一個解'''x'''是函數''f''的吸引[[不动点]]，則可以從'''x'''的[[吸引子|吸引盆地]]中的一個點''x''<sub>1</sub>開始，令''x''<sub>''n''+1</sub> = ''f''(''x''<sub>''n''</sub>)，''n''&nbsp;≥&nbsp;1，則數列{''x''<sub>''n''</sub>}<sub>''n''&nbsp;≥&nbsp;1</sub>會收斂在解'''x'''。此處''x''<sub>''n''</sub>是''x''第''n''次迭代或是近似的值，而''x''<sub>''n''+1</sub>則是下一次迭代或是近似的值。在數值方法中，常會用有括號的上標表示迭代次數，加上括號的目的是不會和其他上標的意義弄混（例如，''x''<sup>(''n''+1)</sup> = ''f''(''x''<sup>(''n'')</sup>)）。若函數''f''是[[連續可微]]，其收斂的充份條件是在不動點的附近，其導數的[[谱半径]]嚴格小於1。若在不動點處滿足此條件，必定在不動點附近存在夠小的鄰區（吸引盆地）。
== 线性系统 ==
求解[[线性方程组]]的迭代方法主要分为两类，分别是定常迭代法和[[克雷洛夫子空间]]法。

=== 定常迭代法 ===
==== 簡介 ====
定常迭代法（Stationary iterative methods）用近似原始[[算子]]的算子來求解線性系統，基於對結果誤差的量測（{{le|餘量 (數值分析)|Residual (numerical analysis)|餘量}}），形成了修正方程，並且重覆此一步驟。此方法很容易推導、實現及分析，但只針對特定矩陣才能確保其收斂。
====定義====
迭代法可定義為
:<math>
  \mathbf{x}^{k+1} := \Psi (  \mathbf{x}^k ) \,, \quad k\geq0
</math>
針對特定的線性系統<math> A\mathbf x= \mathbf b </math>以及真實解<math> \mathbf{x}^* </math>，誤差為
:<math>
  \mathbf{e}^k := \mathbf{x}^k - \mathbf{x}^* \,, \quad k\geq0\,.
</math>
迭代法稱為線性，若存在以下矩陣<math> C \in \R^{n\times n} </math>使得
:<math>
  \mathbf{e}^{k+1} = C  \mathbf{e}^k   \quad \forall \, k\geq0
</math>
此一矩陣稱為迭代矩陣。
有特定迭代矩陣<math> C </math>的迭代法是收斂的，若下式成立
:<math>
  \lim_{k\rightarrow \infty} C^k=0\,.
</math>

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

基礎的迭代法作用原理是將矩陣<math> A </math>{{le|矩陣分割|Matrix splitting|分割}}成
:<math>
  A = M - N
</math>
且此處的矩陣<math> M </math>需要是很容易[[非奇异方阵|取逆矩陣]]的。
因此，迭代法定義為
:<math>
  M \mathbf{x}^{k+1} = N \mathbf{x}^k + b \,, \quad k\geq0\,.
</math>
依此，迭代矩陣為
:<math>
  C = I - M^{-1}A = M^{-1}N\,.
</math>
====範例====
有些基礎的定常迭代法，會將矩陣<math> A </math>以以下方式分割
:<math>
  A = D+L+U\,,\quad D := \text{diag}( (a_{ii})_i)
</math>
其中<math> D </math>是<math> A </math>的對角線部份，<math> L </math>是<math> A </math>的嚴格下[[三角矩阵]]，而<math> U </math>是<math> A </math>的嚴格上三角矩阵。
* {{le|變形理察森迭代法|Modified Richardson iteration|理察森法}}：<math> M:=\frac{1}{\omega} I \quad (\omega \neq 0) </math>
* [[雅可比法]]：<math> M:=D </math>
* 阻尼[[雅可比法]]：<math> M:=\frac{1}{\omega}D \quad (\omega \neq 0) </math>
* [[高斯-赛德尔迭代]]: <math> M:=D+L </math>
* [[逐次超鬆弛迭代法]]（SOR）：<math> M:=\frac{1}{\omega}D+L \quad (\omega \neq 0) </math>
* [[对称逐次超松弛迭代法]] (SSOR): <math> M := \frac{1}{\omega (2-\omega)} (D+\omega L) D^{-1} (D+\omega U) 
\quad (\omega \not 
\in \{0,2\}) </math>
線性定常迭代法也稱為{{le|鬆弛迭代法|Relaxation (iterative method)}}。

=== 克雷洛夫子空间法 ===
{{main|克雷洛夫子空间}}
克雷洛夫子空间法（Krylov subspace method）的作法是初始余量在''A''的前''N''次幂下（始于<math>A^0=I</math>）的[[列空间]][[线性生成空间|张成]]的[[线性子空间]]。 
近似解可以用在形成的數列上使余量為最小值來求得。
克雷洛夫子空间法的原形方法是[[共轭梯度法]]（CG），其中假設系統矩陣<math> A </math>是[[對稱矩陣|對稱]][[正定矩陣|正定]]。
針對對稱矩陣（也可能包括半正定矩陣）<math> A </math>，可以用{{le|最小餘量法|Minimal residual method}}（MINRES）。
若是非對稱矩陣，可以用{{le|廣義最小餘量法|generalized minimal residual method}}（GMRES）及{{le|雙共軛梯度法|biconjugate gradient method}}（BiCG）。

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

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

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

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

== 参见 ==
{{Portal|数学}}
*[[解析解]]
*[[迭代]]
*[[迭代函数]]
*[[逼近]]
*[[数值分析]]
*[[非线性最小二乘法]]
*[[求根算法]]

==參考資料==
{{reflist}}
==外部連結==
{{Commons category|Iterative methods}}
*[http://www.netlib.org/linalg/html_templates/Templates.html Templates for the Solution of Linear Systems] {{Wayback|url=http://www.netlib.org/linalg/html_templates/Templates.html |date=20241117193847 }}
*[http://www-users.cs.umn.edu/~saad/books.html Y. Saad: ''Iterative Methods for Sparse Linear Systems'', 1st edition, PWS 1996] {{Wayback|url=http://www-users.cs.umn.edu/~saad/books.html |date=20210323110655 }}

{{求根演算法}}
{{Authority control}}

[[Category:迭代法| ]]
[[Category:数值分析]]