迭代法(英語: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. 

外部連結

編輯