Loading AI tools
来自维基百科,自由的百科全书
迭代法(英語: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年代才瞭解此方法應用在偏微分方程上的效果也很好,特別是在橢圓型偏微分方程。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.