1. 迭代法基本思想

迭代法的實現，一般需要確定以下三個要點。

1.1 確定迭代變量：

迭代變量一般就是要求解的問題的解，利用迭代遞推公式可以不斷地由舊值遞推出新值。根據問題的不同，迭代變量可以是一個，也可以是多個。

確定迭代變量，通常還要根據迭代遞推關系給出迭代變量的初始值，這一點也很重要。

1.2 確定迭代遞推關系：

迭代遞推關系是根據舊值計算新值的關系或公式，這是迭代法實現的關鍵，如果不能確定迭代關系，則無法用迭代法實現算法。

1.3 確定迭代終止條件：

迭代終止條件是控制迭代過程退出的關鍵條件。迭代不可能無休止地進行，必須設置迭代終止條件，在適當的時候退出迭代。

迭代終止條件一般有三種假設：

• 其一，是迭代變量已經求得問題的精確值；
• 其二，是迭代變量無法得到精確值，但是某個迭代的值的精度已經滿足要求；
• 其三，是指定明確的迭代計算次數。

迭代算法的具體實現，可根據問題的類型選擇迭代終止條件。一般情況下，為了防止迭代關系在某個區間上發散（不收斂）使得算法進入死循環，都會把第三個條件作為異常退出條件和其他迭代終止條件配合使用，也就是說，即使無法得到符合條件的解，只要迭代計算次數達到某個限制值，也退出迭代過程。

2. 實例

2.1 用迭代法求 平方根

公式：求 a 的平方根的迭代公式為： X_n+1=(X_n + a/X_n)/2 要求前后兩次求出的 x 的差的絕對值小于10^-5 時結束，并輸出每次迭代的結果和最后結果

def func(a):i = 0x = 1.0ret = 0while True:i += 1previous_ret = ret		ret = (x + a/x)/2.0		# 迭代遞推關系x = ret					# 迭代變量print "i is {}".format(i)if abs(ret - previous_ret) <= 10**(-5):		# 迭代終止條件breakprint "ret is {}".format(ret)func(81)

2.2 二分迭代求解低階非線性方程

對于 f(x) = 2x² + 3.2x - 1.8 求在 [-0.8, 8] 區間使得 f(x) = 0 的解，由于計算機無法對兩個浮點數直接做相等的判斷，故對其精度誤差要求小于 10^-9

def fun(x):f = 2*x**2 + 3.2*x - 1.8return fdef main(value_range):begin = value_range[0]end = value_range[1]i = 0while True:i += 1print "i is {}".format(i)mid = (begin + end) / 2print "mid is {}".format(mid)if fun(begin) * fun(mid) > 0.0:begin = midelse:end = midif abs(begin - end) < 10**(-9):print midbreakif __name__ == "__main__":main([-0.8, 8])

總結

以上是生活随笔為你收集整理的算法设计思想（3）— 迭代法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。