迭代法
![本頁使用了標題或全文手工轉換](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
迭代法(英語:Iterative Method),在計算數學中,迭代是通過從一個初始估計出發尋找一系列近似解來解決問題(一般是解方程式或者方程組)的數學過程,為實現這一過程所使用的算法統稱,每一次找到的近似解都會用來求得下一個近似解。
迭代法有許多種實現的方式,也有各自的迭代終止條件。常見的迭代法是梯度下降法、爬山算法、牛頓法,也有些屬於擬牛頓法(例如BFGS算法)。迭代法收斂是指在給定的近似初值下,對應的近似解數列收斂。一般會針對迭代法算法進行數學上嚴謹的收斂分析。不過也常常看到啟發式的迭代法。
迭代法相對應的是直接法,設法用有限的步驟來找到解。若不考慮捨入誤差的話,直接法有可能得到正確答案(例如用高斯消去法求解線性系統時)。若是非線性方程式,只能使用迭代法。不過,就竹是線性系統,若是有許多的變數時(例如上百萬個),即使用目前最好的電腦,使用直接法的成本太高(而且有些情形下是不可行的),此時也可以用迭代法來計算[1]。
吸引不動點
[編輯]若方程式可以寫成f(x) = x的形式,且有一個解x是函數f的吸引不動點,則可以從x的吸引盆地中的一個點x1開始,令xn+1 = f(xn),n ≥ 1,則數列{xn}n ≥ 1會收斂在解x。此處xn是x第n次迭代或是近似的值,而xn+1則是下一次迭代或是近似的值。在數值方法中,常會用有括號的上標表示迭代次數,加上括號的目的是不會和其他上標的意義弄混(例如,x(n+1) = f(x(n)))。若函數f是連續可微,其收斂的充份條件是在不動點的附近,其導數的譜半徑嚴格小於1。若在不動點處滿足此條件,必定在不動點附近存在夠小的鄰區(吸引盆地)。
線性系統
[編輯]求解線性方程組的迭代方法主要分為兩類,分別是定常迭代法和克雷洛夫子空間法。
定常迭代法
[編輯]簡介
[編輯]定常迭代法(Stationary iterative methods)用近似原始算子的算子來求解線性系統,基於對結果誤差的量測(餘量),形成了修正方程式,並且重覆此一步驟。此方法很容易推導、實現及分析,但只針對特定矩陣才能確保其收斂。
定義
[編輯]迭代法可定義為
針對特定的線性系統以及真實解,誤差為
迭代法稱為線性,若存在以下矩陣使得
此一矩陣稱為迭代矩陣。 有特定迭代矩陣的迭代法是收斂的,若下式成立
有一個重要的定理,提到有特定迭代矩陣的迭代法,其收斂的條件若且唯若其譜半徑小於1,也就是
基礎的迭代法作用原理是將矩陣分割成
且此處的矩陣需要是很容易取逆矩陣的。 因此,迭代法定義為
依此,迭代矩陣為
範例
[編輯]有些基礎的定常迭代法,會將矩陣以以下方式分割
其中是的對角線部份,是的嚴格下三角矩陣,而是的嚴格上三角矩陣。
線性定常迭代法也稱為鬆弛迭代法。
克雷洛夫子空間法
[編輯]克雷洛夫子空間法(Krylov subspace method)的作法是初始餘量在A的前N次冪下(始於)的列空間張成的線性子空間。 近似解可以用在形成的數列上使餘量為最小值來求得。 克雷洛夫子空間法的原形方法是共軛梯度法(CG),其中假設系統矩陣是對稱正定。 針對對稱矩陣(也可能包括半正定矩陣),可以用最小餘量法(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年代才瞭解此方法應用在偏微分方程式上的效果也很好,特別是在橢圓型偏微分方程式。
參見
[編輯]參考資料
[編輯]- ^ 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
|
|