迭代演算法的例子

㈠ 迭代的演算法是什麼

在計算數學中，迭代是通過從一個初始估計出發尋找一系列近似解來解決問題（一般是解方程或者方程組）的數學過程，為實現這一過程所使用的方法統稱。

跟迭代法相對應的是直接法（或者稱為一次解法），即一次性解決問題。一般如果可能，直接解法總是優先考慮的。

但當遇到復雜問題時，特別是在未知量很多，方程為非線性時，我們無法找到直接解法（例如五次以及更高次的代數方程沒有解析解，參見阿貝爾定理），這時候或許可以通過迭代法尋求方程（組）的近似解。

最常見的迭代法是牛頓法。其他還包括梯度下降法、共軛迭代法、變尺度迭代法、最小二乘法、線性規劃、非線性規劃、單純型法、懲罰函數法、斜率投影法、遺傳演算法、模擬退火等等。

方法

1、定常迭代法

這種方法易於推導，方便實現和分析，但只能保證某些特定形式矩陣求解的收斂性。定常迭代法的例子包括雅可比法，高斯-賽德爾迭代，以及逐次超鬆弛迭代法（SOR）。線性定常迭代法又稱為鬆弛法。

2、Krylov子空間法

通過在子空間上最小化餘量來得到近似解。Krylov子空間法的原型是是共軛梯度法（CG），其它方法還包括廣義最小殘量法（GMRES）和雙共軛梯度方法（BiCG）。

㈡ 數學牛頓迭代法的例子

牛頓迭代公式編輯
設r是

的根，選取

作為r的初始近似值，過點

做曲線

的切線L，L的方程為

，求出L與x軸交點的橫坐標

，稱x1為r的一次近似值。過點

做曲線

的切線，並求該切線與x軸交點的橫坐標

，稱

為r的二次近似值。重復以上過程，得r的近似值序列，其中，

稱為r的

次近似值，上式稱為牛頓迭代公式。
用牛頓迭代法解非線性方程，是把非線性方程

線性化的一種近似方法。把

在點

的某鄰域內展開成泰勒級數

，取其線性部分（即泰勒展開的前兩項），並令其等於0，即

，以此作為非線性方程

的近似方程，若

，則其解為

， 這樣，得到牛頓迭代法的一個迭代關系式：

。
已經證明，如果是連續的，並且待求的零點是孤立的，那麼在零點周圍存在一個區域，只要初始值位於這個鄰近區域內，那麼牛頓法必定收斂。 並且，如果不為0, 那麼牛頓法將具有平方收斂的性能. 粗略的說，這意味著每迭代一次，牛頓法結果的有效數字將增加一倍。[1]
軍人在進攻時常採用交替掩護進攻的方式，若在數軸上的點表示A，B兩人的位置，規定在前面的數大於後面的數，則是A>B，B>A交替出現。但現在假設軍中有一個膽小鬼，同時大家又都很照顧他，每次沖鋒都是讓他跟在後面，每當前面的人占據一個新的位置，就把位置交給他，然後其他人再往前佔領新的位置。也就是A始終在B的前面，A向前邁進，B跟上，A把自己的位置交給B（即執行B = A），然後A 再前進佔領新的位置，B再跟上，直到佔領所有的陣地，前進結束。像這種兩個數一前一後逐步向某個位置逼近的方法稱為迭代法。
迭代法也稱輾轉法，是一種不斷用變數的舊值遞推新值的過程，跟迭代法相對應的是直接法（或者稱為一次解法），即一次性解決問題。迭代演算法是用計算機解決問題的一種基本方法。它利用計算機運算速度快、適合做重復性操作的特點，讓計算機對一組指令（或一定步驟）重復執行，在每次執行這組指令（或這些步驟）時，都從變數的原值推出它的一個新值。
利用迭代演算法解決問題，需要做好以下三個方面的工作：
一、確定迭代變數
在可以用迭代演算法解決的問題中，至少存在一個可直接或間接地不斷由舊值遞推出新值的變數，這個變數就是迭代變數。
二、建立迭代關系式
所謂迭代關系式，指如何從變數的前一個值推出其下一個值的公式（或關系）。迭代關系式的建立是解決迭代問題的關鍵，通常可以使用遞推或倒推的方法來完成。
三、對迭代過程進行控制
在什麼時候結束迭代過程？這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地執行下去。迭代過程的控制通常可分為兩種情況：一種是所需的迭代次數是個確定的值，可以計算出來；另一種是所需的迭代次數無法確定。對於前一種情況，可以構建一個固定次數的循環來實現對迭代過程的控制；對於後一種情況，需要進一步分析得出可用來結束迭代過程的條件。