跳转到内容

迭代法

本页使用了标题或全文手工转换
维基百科,自由的百科全书

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

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

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

吸引不動點

[编辑]

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

线性系统

[编辑]

求解线性方程组的迭代方法主要分为两类,分别是定常迭代法和克雷洛夫子空间法。

定常迭代法

[编辑]

簡介

[编辑]

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

定義

[编辑]

迭代法可定義為

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

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

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

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

基礎的迭代法作用原理是將矩陣分割英语Matrix splitting

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

依此,迭代矩陣為

範例

[编辑]

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

其中的對角線部份,的嚴格下三角矩阵,而的嚴格上三角矩阵。

線性定常迭代法也稱為鬆弛迭代法英语Relaxation (iterative method)

克雷洛夫子空间法

[编辑]

克雷洛夫子空间法(Krylov subspace method)的作法是初始余量在A的前N次幂下(始于)的列空间张成线性子空间。 近似解可以用在形成的數列上使余量為最小值來求得。 克雷洛夫子空间法的原形方法是共轭梯度法(CG),其中假設系統矩陣對稱正定。 針對對稱矩陣(也可能包括半正定矩陣),可以用最小餘量法英语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 LanczosMagnus Hestenes英语Magnus HestenesEduard 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. 

外部連結

[编辑]