1. 首頁 > 生活經驗 > >

什么是牛頓迭代法 迭代算法原理

知識百科經驗分享


迭代法計算步驟迭代法計算步驟
迭代法
迭代法（Iteration）是一種不斷用變量的舊值遞推出新值的解決問題的方法 。迭代算法是用計算機解決問題的一種基本方法，一般用于數值計算 。累加、累乘都是迭代算法的基礎應用 。典型案例：牛頓迭代法
步驟：
確定迭代模型：分析得出前一個（或幾個）值與其下一個值的迭代關系數學模型；
建立迭代關系式
對迭代過程進行控制
經典案例：
示例： 斐波那契數列：1、1、2、3、5、8、13、21、34
對于斐波那契數列，當n趨于無窮時，數列最后的兩項的商 (xn-1/xn) 趨于黃金分割數0.618
迭代算法是什么啊?迭代算法就是實現數值分析中通過從一個初始估計出發尋找一系列近似解來解決問題（一般是解方程或者方程組）的過程的方法 。
最常見的迭代法是牛頓法 。其他還包括最速下降法、共軛迭代法、變尺度迭代法、最小二乘法、線性規劃、非線性規劃、單純型法、懲罰函數法、斜率投影法、遺傳算法、模擬退火等等 。
迭代法的應用：
迭代法的主要研究課題是對所論問題構造收斂的迭代格式，分析它們的收斂速度及收斂范圍 。迭代法的收斂性定理可分成下列三類：
1、局部收斂性定理：假設問題解存在，斷定當初始近似與解充分接近時迭代法收斂 。
2、半局部收斂性定理：在不假定解存在的情況下，根據迭代法在初始近似處滿足的條件，斷定迭代法收斂于問題的解 。
3、大范圍收斂性定理：在不假定初始近似與解充分接近的條件下，斷定迭代法收斂于問題的解 。
迭代法在線性和非線性方程組求解，最優化計算及特征值計算等問題中被廣泛應用 。
請問迭代是什么意思？？？望得到準確回答，謝謝 。。。是迭代法吧?
迭代法迭代法也稱輾轉法，是一種不斷用變量的舊值遞推新值的過程,跟迭代法相對應的是直接法（或者稱為一次解法），即一次性解決問題 。迭代法又分為精確迭代和近似迭代 ?！岸址ā焙汀芭ｎD迭代法”屬于近似迭代法 。
迭代算法是用計算機解決問題的一種基本方法 。它利用計算機運算速度快、適合做重復性操作的特點，讓計算機對一組指令（或一定步驟）進行重復執行，在每次執行這組指令（或這些步驟）時，都從變量的原值推出它的一個新值 。
利用迭代算法解決問題，需要做好以下三個方面的工作：
一、確定迭代變量 。在可以用迭代算法解決的問題中，至少存在一個直接或間接地不斷由舊值遞推出新值的變量，這個變量就是迭代變量 。
二、建立迭代關系式 。所謂迭代關系式，指如何從變量的前一個值推出其下一個值的公式（或關系） 。迭代關系式的建立是解決迭代問題的關鍵，通常可以使用遞推或倒推的方法來完成 。
三、對迭代過程進行控制 。在什么時候結束迭代過程？這是編寫迭代程序必須考慮的問題 。不能讓迭代過程無休止地重復執行下去 。迭代過程的控制通?？煞譃閮煞N情況：一種是所需的迭代次數是個確定的值，可以計算出來；另一種是所需的迭代次數無法確定 。對于前一種情況，可以構建一個固定次數的循環來實現對迭代過程的控制；對于后一種情況，需要進一步分析出用來結束迭代過程的條件
迭代法的算法迭代是數值分析中通過從一個初始估計出發尋找一系列近似解來解決問題（一般是解方程或者方程組）的過程，為實現這一過程所使用的方法統稱為迭代法（Iterative Method） 。
一般可以做如下定義：對于給定的線性方程組（這里的x、B、f同為矩陣，任意線性方程組都可以變換成此形式），用公式 （代表迭代k次得到的x，初始時k=0)逐步帶入求近似解的方法稱為迭代法（或稱一階定常迭代法） 。如果存在，記為x*，稱此迭代法收斂 。顯然x*就是此方程組的解，否則稱為迭代法發散 。
跟迭代法相對應的是直接法（或者稱為一次解法），即一次性的快速解決問題，例如通過開方解決方程x +3= 4 。一般如果可能，直接解法總是優先考慮的 。但當遇到復雜問題時，特別是在未知量很多，方程為非線性時，我們無法找到直接解法（例如五次以及更高次的代數方程沒有解析解，參見阿貝耳定理），這時候或許可以通過迭代法尋求方程（組）的近似解 。
最常見的迭代法是牛頓法 。其他還包括最速下降法、共軛迭代法、變尺度迭代法、最小二乘法、線性規劃、非線性規劃、單純型法、懲罰函數法、斜率投影法、遺傳算法、模擬退火等等 。
利用迭代算法解決問題，需要做好以下三個方面的工作： 例 1 ：一個飼養場引進一只剛出生的新品種兔子，這種兔子從出生的下一個月開始，每月新生一只兔子，新生的兔子也如此繁殖 。如果所有的兔子都不死去，問到第 12 個月時，該飼養場共有兔子多少只？
分析：這是一個典型的遞推問題 。我們不妨假設第 1 個月時兔子的只數為 u 1，第 2 個月時兔子的只數為 u 2，第 3 個月時兔子的只數為 u 3，……根據題意，“這種兔子從出生的下一個月開始，每月新生一只兔子”，則有
u 1 = 1，u 2 = u 1 + u 1 × 1 = 2，u 3 = u 2 + u 2 × 1 = 4，……
根據這個規律，可以歸納出下面的遞推公式：
u n = u(n － 1）× 2 (n ≥ 2）
對應 u n 和 u(n － 1），定義兩個迭代變量 y 和 x，可將上面的遞推公式轉換成如下迭代關系：
y=x*2
x=y
讓計算機對這個迭代關系重復執行 11 次，就可以算出第 12 個月時的兔子數 。參考程序如下：
cls
x=1
for i=2 to 12
y=x*2
【什么是牛頓迭代法 迭代算法原理】x=y
next i
print y
end
例 2 ：阿米巴用簡單分裂的方式繁殖，它每分裂一次要用 3 分鐘 。將若干個阿米巴放在一個盛滿營養參液的容器內，45 分鐘后容器內充滿了阿米巴 。已知容器最多可以裝阿米巴 220,220個 。試問，開始的時候往容器內放了多少個阿米巴？請編程序算出 。
分析：根據題意，阿米巴每 3 分鐘分裂一次，那么從開始的時候將阿米巴放入容器里面，到 45 分鐘后充滿容器，需要分裂 45/3=15 次 。而“容器最多可以裝阿米巴2^ 20 個”，即阿米巴分裂 15 次以后得到的個數是 2^20 。題目要求我們計算分裂之前的阿米巴數，不妨使用倒推的方法，從第 15 次分裂之后的 2^20 個，倒推出第 15 次分裂之前（即第 14 次分裂之后）的個數，再進一步倒推出第 13 次分裂之后、第 12 次分裂之后、……第 1 次分裂之前的個數 。
設第 1 次分裂之前的個數為 x 0 、第 1 次分裂之后的個數為 x 1 、第 2 次分裂之后的個數為 x 2 、……第 15 次分裂之后的個數為 x 15，則有
x 14 =x 15 /2 、 x 13 =x 14 /2 、…… x n-1 =x n /2 (n ≥ 1）
因為第 15 次分裂之后的個數 x 15 是已知的，如果定義迭代變量為 x，則可以將上面的倒推公式轉換成如下的迭代公式：
x=x/2 （x 的初值為第 15 次分裂之后的個數 2^20）
讓這個迭代公式重復執行 15 次，就可以倒推出第 1 次分裂之前的阿米巴個數 。因為所需的迭代次數是個確定的值，我們可以使用一個固定次數的循環來實現對迭代過程的控制 。參考程序如下：
cls
x=2^20
for i=1 to 15
x=x/2
next i
print x
end
ps:java中冪的算法是Math.pow（2,20）；返回double，稍微注意一下
例 3 ：驗證谷角猜想 。日本數學家谷角靜夫在研究自然數時發現了一個奇怪現象：對于任意一個自然數 n，若 n 為偶數，則將其除以 2 ；若 n 為奇數，則將其乘以 3，然后再加 1 。如此經過有限次運算后，總可以得到自然數 1 。人們把谷角靜夫的這一發現叫做“谷角猜想” 。
要求：編寫一個程序，由鍵盤輸入一個自然數 n，把 n 經過有限次運算后，最終變成自然數 1 的全過程打印出來 。
分析：定義迭代變量為 n，按照谷角猜想的內容，可以得到兩種情況下的迭代關系式：當 n 為偶數時，n=n/2 ；當 n 為奇數時，n=n*3+1 。用 QBASIC 語言把它描述出來就是：
if n 為偶數 then
n=n/2
else
n=n*3+1
end if
這就是需要計算機重復執行的迭代過程 。這個迭代過程需要重復執行多少次，才能使迭代變量 n 最終變成自然數 1，這是我們無法計算出來的 。因此，還需進一步確定用來結束迭代過程的條件 。仔細分析題目要求，不難看出，對任意給定的一個自然數 n，只要經過有限次運算后，能夠得到自然數 1，就已經完成了驗證工作 。因此，用來結束迭代過程的條件可以定義為：n=1 。參考程序如下：
cls
input Please input n=;n
do until n=1
if n mod 2=0 then
rem 如果 n 為偶數，則調用迭代公式 n=n/2
n=n/2
print —;n;
else
n=n*3+1
print —;n;
end if
loop
end
迭代法開平方：
#include<stdio.h>
#include<math.h>
void main()
{
double a,x0,x1;
printf(Input a:
);
scanf(%lf,&a);//因為a是double型數據，所以要用%lf，而不是%f
if(a<0)
printf(Error!
);
else
{
x0=a/2;
x1=(x0+a/x0)/2;
do
{
x0=x1;
x1=(x0+a/x0)/2;
}while(fabs(x0-x1）>=1e-6）；
}
printf(Result:
);
printf(sqrt(%g)=%g
,a,x1）；
}
求平方根的迭代公式：x1=1/2*(x0+a/x0） 。
算法：1.先自定一個初值x0，作為a的平方根值，在我們的程序中取a/2作為a的初值；利用迭代公式求出一個x1 。此值與真正的a的平方根值相比，誤差很大 。
⒉把新求得的x1代入x0中，準備用此新的x0再去求出一個新的x1.
⒊利用迭代公式再求出一個新的x1的值，也就是用新的x0又求出一個新的平方根值x1，此值將更趨近于真正的平方根值 。
⒋比較前后兩次求得的平方根值x0和x1，如果它們的差值小于我們指定的值，即達到我們要求的精度，則認為x1就是a的平方根值，去執行步驟5；否則執行步驟2，即循環進行迭代 。
迭代法是用于求方程或方程組近似根的一種常用的算法設計方法 。設方程為f(x)=0，用某種數學方法導出等價的形式x=g(x），然后按以下步驟執行：
⑴ 選一個方程的近似根，賦給變量x0；
⑵ 將x0的值保存于變量x1，然后計算g(x1），并將結果存于變量x0；
⑶ 當x0與x1的差的絕對值還小于指定的精度要求時，重復步驟⑵的計算 。
若方程有根，并且用上述方法計算出來的近似根序列收斂，則按上述方法求得的x0就認為是方程的根 。上述算法用C程序的形式表示為：
【算法】迭代法求方程的根
{ x0=初始近似根；
do {
x1=x0；
x0=g(x1）； /*按特定的方程計算新的近似根*/
} while (fabs(x0-x1）>Epsilon）；
printf（“方程的近似根是%f
”，x0）；
}
迭代算法也常用于求方程組的根，令
X=（x0，x1，…，xn-1）
設方程組為：
xi=gi(X) (I=0，1，…，n-1）
則求方程組根的迭代算法可描述如下：
【算法】迭代法求方程組的根
{ for (i=0;i
x=初始近似根；
do {
for (i=0;i
y=x;
for (i=0;i
x=gi(X);
for (delta=0.0,i=0;i
if (fabs(y-x)>delta) delta=fabs(y-x）；
} while (delta>Epsilon）；
for (i=0;i
printf（“變量x[%d]的近似根是 %f”，I，x）；
printf（“
”）；
}
具體使用迭代法求根時應注意以下兩種可能發生的情況：
⑴ 如果方程無解，算法求出的近似根序列就不會收斂，迭代過程會變成死循環，因此在使用迭代算法前應先考察方程是否有解，并在程序中對迭代的次數給予限制；
⑵ 方程雖然有解，但迭代公式選擇不當，或迭代的初始近似根選擇不合理，也會導致迭代失敗 。
遞歸
遞歸是設計和描述算法的一種有力的工具，由于它在復雜算法的描述中被經常采用，為此在進一步介紹其他算法設計方法之前先討論它 。
能采用遞歸描述的算法通常有這樣的特征：為求解規模為N的問題，設法將它分解成規模較小的問題，然后從這些小問題的解方便地構造出大問題的解，并且這些規模較小的問題也能采用同樣的分解和綜合方法，分解成規模更小的問題，并從這些更小問題的解構造出規模較大問題的解 。特別地，當規模N=1時，能直接得解 。
【問題】 編寫計算斐波那契（Fibonacci）數列的第n項函數fib（n） 。
斐波那契數列為：0、1、1、2、3、……，即：
fib(0)=0;
fib⑴=1;
fib(n)=fib(n-1）+fib(n-2） （當n>1時） 。
寫成遞歸函數有：
int fib(int n)
{ if (n==0) return 0;
if (n==1） return 1;
if (n>1） return fib(n-1）+fib(n-2）；
}
遞歸算法的執行過程分遞推和回歸兩個階段 。在遞推階段，把較復雜的問題（規模為n）的求解推到比原問題簡單一些的問題（規模小于n）的求解 。例如上例中，求解fib(n），把它推到求解fib(n-1）和fib(n-2） 。也就是說，為計算fib(n），必須先計算fib(n-1）和fib(n- 2），而計算fib(n-1）和fib(n-2），又必須先計算fib(n-3）和fib(n-4） 。依次類推，直至計算fib⑴和fib(0），分別能立即得到結果1和0 。在遞推階段，必須要有終止遞歸的情況 。例如在函數fib中，當n為1和0的情況 。
在回歸階段，當獲得最簡單情況的解后，逐級返回，依次得到稍復雜問題的解，例如得到fib⑴和fib(0）后，返回得到fib⑵的結果，……，在得到了fib(n-1）和fib(n-2）的結果后，返回得到fib(n）的結果 。
在編寫遞歸函數時要注意，函數中的局部變量和參數知識局限于當前調用層，當遞推進入“簡單問題”層時，原來層次上的參數和局部變量便被隱蔽起來 。在一系列“簡單問題”層，它們各有自己的參數和局部變量 。
由于遞歸引起一系列的函數調用，并且可能會有一系列的重復計算，遞歸算法的執行效率相對較低 。當某個遞歸算法能較方便地轉換成遞推算法時，通常按遞推算法編寫程序 。例如上例計算斐波那契數列的第n項的函數fib(n）應采用遞推算法，即從斐波那契數列的前兩項出發，逐次由前兩項計算出下一項，直至計算出要求的第n項 。
【問題】 組合問題
問題描述：找出從自然數1、2、……、n中任取r個數的所有組合 。例如n=5，r=3的所有組合為：⑴5、4、3 ⑵5、4、2 ⑶5、4、1
⑷5、3、2 ⑸5、3、1 ⑹5、2、1
⑺4、3、2 ⑻4、3、1 ⑼4、2、1
⑽3、2、1
分析所列的10個組合，可以采用這樣的遞歸思想來考慮求組合函數的算法 。設函數為void comb(int m,int k）為找出從自然數1、2、……、m中任取k個數的所有組合 。當組合的第一個數字選定時，其后的數字是從余下的m-1個數中取k-1數的組合 。這就將求m 個數中取k個數的組合問題轉化成求m-1個數中取k-1個數的組合問題 。設函數引入工作數組a[ ]存放求出的組合的數字，約定函數將確定的k個數字組合的第一個數字放在a[k]中，當一個組合求出后，才將a[ ]中的一個組合輸出 。第一個數可以是m、m-1、……、k，函數將確定組合的第一個數字放入數組后，有兩種可能的選擇，因還未去頂組合的其余元素，繼續遞歸去確定；或因已確定了組合的全部元素，輸出這個組合 。細節見以下程序中的函數comb 。
【程序】
# include
# define MAXN 100
int a[MAXN];
void comb(int m,int k)
{ int i,j;
for (i=m;i>=k;i--)
{ a[k]=i;
if (k>1）
comb(i-1,k-1）；
else
{ for (j=a[0];j>0;j--)
printf（“%4d”，a[j]);
printf（“
”）；
}
}
}
void main()
{ a[0]=3;
comb（5,3）；
}
【問題】 背包問題
問題描述：有不同價值、不同重量的物品n件，求從這n件物品中選取一部分物品的選擇方案，使選中物品的總重量不超過指定的限制重量，但選中物品的價值之和最大 。
設n 件物品的重量分別為w0、w1、…、wn-1，物品的價值分別為v0、v1、…、vn-1 。采用遞歸尋找物品的選擇方案 。設前面已有了多種選擇的方案，并保留了其中總價值最大的方案于數組option[ ]，該方案的總價值存于變量maxv 。當前正在考察新方案，其物品選擇情況保存于數組cop[ ] 。假定當前方案已考慮了前i-1件物品，現在要考慮第i件物品；當前方案已包含的物品的重量之和為tw；至此，若其余物品都選擇是可能的話，本方案能達到的總價值的期望值為tv 。算法引入tv是當一旦當前方案的總價值的期望值也小于前面方案的總價值maxv時，繼續考察當前方案變成無意義的工作，應終止當前方案，立即去考察下一個方案 。因為當方案的總價值不比maxv大時，該方案不會被再考察，這同時保證函數后找到的方案一定會比前面的方案更好 。
對于第i件物品的選擇考慮有兩種可能：
⑴ 考慮物品i被選擇，這種可能性僅當包含它不會超過方案總重量限制時才是可行的 。選中后，繼續遞歸去考慮其余物品的選擇 。
⑵ 考慮物品i不被選擇，這種可能性僅當不包含物品i也有可能會找到價值更大的方案的情況 。
按以上思想寫出遞歸算法如下：
try（物品i，當前選擇已達到的重量和，本方案可能達到的總價值tv)
{ /*考慮物品i包含在當前方案中的可能性*/
if（包含物品i是可以接受的）
{ 將物品i包含在當前方案中；
if (i
try(i+1,tw+物品i的重量，tv);
else
/*又一個完整方案，因為它比前面的方案好，以它作為最佳方案*/
以當前方案作為臨時最佳方案保存；
恢復物品i不包含狀態；
}
/*考慮物品i不包含在當前方案中的可能性*/
if （不包含物品i僅是可男考慮的）
if (i
try(i+1,tw,tv-物品i的價值）；
else
/*又一個完整方案，因它比前面的方案好，以它作為最佳方案*/
以當前方案作為臨時最佳方案保存；
}
為了理解上述算法，特舉以下實例 。設有4件物品，它們的重量和價值見表：
物品 0 1 2 3
重量 5 3 2 1
價值 4 4 3 1
并設限制重量為7 。則按以上算法，下圖表示找解過程 。由圖知，一旦找到一個解，算法就進一步找更好的佳 。如能判定某個查找分支不會找到更好的解，算法不會在該分支繼續查找，而是立即終止該分支，并去考察下一個分支 。
按上述算法編寫函數和程序如下：
【程序】
# include
# define N 100
double limitW,totV,maxV;
int option[N],cop[N];
struct { double weight;
double value;
}a[N];
int n;
void find(int i,double tw,double tv)
{ int k;
/*考慮物品i包含在當前方案中的可能性*/
if (tw+a.weight<=limitW)
{ cop=1;
if (i
else
{ for (k=0;k
option[k]=cop[k];
maxv=tv;
}
cop=0;
}
/*考慮物品i不包含在當前方案中的可能性*/
if (tv-a.value>maxV)
if (i
else
{ for (k=0;k
option[k]=cop[k];
maxv=tv-a.value;
}
}
void main()
{ int k;
double w,v;
printf（“輸入物品種數
”）；
scanf（（“%d”，&n);
printf（“輸入各物品的重量和價值
”）；
for (totv=0.0,k=0;k
{ scanf（“%1f%1f”，&w,&v);
a[k].weight=w;
a[k].value=https://pipe99.com/new/v;
totV+=V;
}
printf（“輸入限制重量
”）；
scanf（“%1f”，&limitV);
maxv=0.0;
for (k=0;k find(0,0.0,totV);
for (k=0;k
if (option[k]) printf（“%4d”，k+1）；
printf（“
總價值為%.2f
”，maxv);
}
作為對比，下面以同樣的解題思想，考慮非遞歸的程序解 。為了提高找解速度，程序不是簡單地逐一生成所有候選解，而是從每個物品對候選解的影響來形成值得進一步考慮的候選解，一個候選解是通過依次考察每個物品形成的 。對物品i的考察有這樣幾種情況：當該物品被包含在候選解中依舊滿足解的總重量的限制，該物品被包含在候選解中是應該繼續考慮的；反之，該物品不應該包括在當前正在形成的候選解中 。同樣地，僅當物品不被包括在候選解中，還是有可能找到比目前臨時最佳解更好的候選解時，才去考慮該物品不被包括在候選解中；反之，該物品不包括在當前候選解中的方案也不應繼續考慮 。對于任一值得繼續考慮的方案，程序就去進一步考慮下一個物品 。
【程序】
# include
# define N 100
double limitW;
int cop[N];
struct ele { double weight;
double value;
} a[N];
int k,n;
struct { int ;
double tw;
double tv;
}twv[N];
void next(int i,double tw,double tv)
{ twv.=1;
twv tw=tw;
twv tv=tv;
}
double find(struct ele *a,int n)
{ int i,k,f;
double maxv,tw,tv,totv;
maxv=0;
for (totv=0.0,k=0;k
totv+=a[k].value;
next(0,0.0,totv);
i=0;
While (i>=0)
{ f=twv.;
tw=twv tw;
tv=twv tv;
switch(f)
{ case 1: twv.++;
if (tw+a.weight<=limitW)
if (i
{ next(i+1,tw+a.weight,tv);
i++;
}
else
{ maxv=tv;
for (k=0;k
cop[k]=twv[k].!=0;
}
break;
case 0: i--;
break;
default: twv.=0;
if (tv-a.value>maxv)
if (i
{ next(i+1,tw,tv-a.value);
i++;
}
else
{ maxv=tv-a.value;
for (k=0;k
cop[k]=twv[k].!=0;
}
break;
}
}
return maxv;
}
void main()
{ double maxv;
printf（“輸入物品種數
”）；
scanf（（“%d”，&n);
printf（“輸入限制重量
”）；
scanf（“%1f”，&limitW);
printf（“輸入各物品的重量和價值
”）；
for (k=0;k
scanf（“%1f%1f”，&a[k].weight,&a[k].value);
maxv=find(a,n);
printf（“
選中的物品為
”）；
for (k=0;k
if (option[k]) printf（“%4d”，k+1）；
printf（“
總價值為%.2f
”，maxv);
}

什么是迭代算法？迭代算法是用計算機解決問題的一種基本方法 。它利用計算機運算速度快、適合做重復性操作的特點，讓計算機對一組指令（或一定步驟）進行重復執行，在每次執行這組指令（或這些步驟）時，都從變量的原值推出它的一個新值 。
利用迭代算法解決問題，需要做好以下三個方面的工作：
一、確定迭代變量 。在可以用迭代算法解決的問題中，至少存在一個直接或間接地不斷由舊值遞推出新值的變量，這個變量就是迭代變量 。
二、建立迭代關系式 。所謂迭代關系式，指如何從變量的前一個值推出其下一個值的公式（或關系） 。迭代關系式的建立是解決迭代問題的關鍵，通?？梢允褂眠f推或倒推的方法來完成 。
三、對迭代過程進行控制 。在什么時候結束迭代過程？這是編寫迭代程序必須考慮的問題 。不能讓迭代過程無休止地重復執行下去 。迭代過程的控制通?？煞譃閮煞N情況：一種是所需的迭代次數是個確定的值，可以計算出來；另一種是所需的迭代次數無法確定 。對于前一種情況，可以構建一個固定次數的循環來實現對迭代過程的控制；對于后一種情況，需要進一步分析出用來結束迭代過程的條件 。
例 1 ： 一個飼養場引進一只剛出生的新品種兔子，這種兔子從出生的下一個月開始，每月新生一只兔子，新生的兔子也如此繁殖 。如果所有的兔子都不死去，問到第 12 個月時，該飼養場共有兔子多少只？
分析： 這是一個典型的遞推問題 。我們不妨假設第 1 個月時兔子的只數為 u 1，第 2 個月時兔子的只數為 u 2，第 3 個月時兔子的只數為 u 3，……根據題意，“這種兔子從出生的下一個月開始，每月新生一只兔子”，則有
u 1 ＝ 1，u 2 ＝ u 1 ＋ u 1 × 1 ＝ 2，u 3 ＝ u 2 ＋ u 2 × 1 ＝ 4，……
根據這個規律，可以歸納出下面的遞推公式：
u n ＝ u n － 1 × 2 (n ≥ 2)
對應 u n 和 u n － 1，定義兩個迭代變量 y 和 x，可將上面的遞推公式轉換成如下迭代關系：
y=x*2
x=y
讓計算機對這個迭代關系重復執行 11 次，就可以算出第 12 個月時的兔子數 。參考程序如下：
cls
x=1
for i=2 to 12
y=x*2
x=y
next i
print y
end
例 2 ： 阿米巴用簡單分裂的方式繁殖，它每分裂一次要用 3 分鐘 。將若干個阿米巴放在一個盛滿營養參液的容器內，45 分鐘后容器內充滿了阿米巴 。已知容器最多可以裝阿米巴 2 20 個 。試問，開始的時候往容器內放了多少個阿米巴？請編程序算出 。
分析： 根據題意，阿米巴每 3 分鐘分裂一次，那么從開始的時候將阿米巴放入容器里面，到 45 分鐘后充滿容器，需要分裂 45/3=15 次 。而“容器最多可以裝阿米巴 2 20 個”，即阿米巴分裂 15 次以后得到的個數是 2 20。題目要求我們計算分裂之前的阿米巴數，不妨使用倒推的方法，從第 15 次分裂之后的 2 20 個，倒推出第 15 次分裂之前（即第 14 次分裂之后）的個數，再進一步倒推出第 13 次分裂之后、第 12 次分裂之后、……第 1 次分裂之前的個數 。
設第 1 次分裂之前的個數為 x 0 、第 1 次分裂之后的個數為 x 1 、第 2 次分裂之后的個數為 x 2 、……第 15 次分裂之后的個數為 x 15，則有
x 14 =x 15 /2 、 x 13 =x 14 /2 、…… x n-1 =x n /2 (n ≥ 1)
因為第 15 次分裂之后的個數 x 15 是已知的，如果定義迭代變量為 x，則可以將上面的倒推公式轉換成如下的迭代公式：
x=x/2 （ x 的初值為第 15 次分裂之后的個數 2 20 ）
讓這個迭代公式重復執行 15 次，就可以倒推出第 1 次分裂之前的阿米巴個數 。因為所需的迭代次數是個確定的值，我們可以使用一個固定次數的循環來實現對迭代過程的控制 。參考程序如下：
cls
x=2^20
for i=1 to 15
x=x/2
next i
print x
end
什么是牛頓迭代法？產生背景
牛頓迭代法（Newton's method）又稱為牛頓-拉夫遜方法（Newton-Raphson method），它是牛頓在17世紀提出的一種在實數域和復數域上近似求解方程的方法 。多數方程不存在求根公式，因此求精確根非常困難，甚至不可能，從而尋找方程的近似根就顯得特別重要 。方法使用函數f(x)的泰勒級數的前面幾項來尋找方程f(x) = 0的根 。牛頓迭代法是求方程根的重要方法之一，其最大優點是在方程f(x) = 0的單根附近具有平方收斂，而且該法還可以用來求方程的重根、復根,此時線性收斂，但是可通過一些方法變成超線性收斂 。另外該方法廣泛用于計算機編程中 。
編輯本段牛頓迭代公式
設r是f(x) = 0的根，選取x0作為r初始近似值，過點（x0,f(x0)）做曲線y = f(x)的切線L，L的方程為y = f(x0)+f'(x0)(x-x0)，求出L與x軸交點的橫坐標 x1 = x0-f(x0)/f'(x0)，稱x1為r的一次近似值 。過點（x1,f(x1)）做曲線y = f(x)的切線，并求該切線與x軸交點的橫坐標 x2 = x1-f(x1)/f'(x1)，稱x2為r的二次近似值 。重復以上過程，得r的近似值序列，其中x(n+1)=x(n)－f(x(n))/f'(x(n))，稱為r的n+1次近似值，上式稱為牛頓迭代公式 。解非線性方程f(x)=0的牛頓法是把非線性方程線性化的一種近似方法 。把f(x)在x0點附近展開成泰勒級數 f(x) = f(x0)+(x－x0)f'(x0)+(x－x0)^2*f''(x0)/2! +… 取其線性部分，作為非線性方程f(x) = 0的近似方程，即泰勒展開的前兩項，則有f(x0)+f'(x0)(x－x0)=0 設f'(x0)≠0則其解為x1=x0－f(x0)/f'(x0) 這樣，得到牛頓法的一個迭代序列：x(n+1)=x(n)－f(x(n))/f'(x(n)) 。牛頓迭代法示意圖
軍人在進攻時常采用交替掩護進攻的方式，若在數軸上的點表示A，B兩人的位置，規定在前面的數大于后面的數，則是A>B，B>A交替出現 。但現在假設軍中有一個膽小鬼，同時大家又都很照顧他，每次沖鋒都是讓他跟在后面，每當前面的人占據一個新的位置，就把位置交給他，然后其他人再往前占領新的位置 。也就是A始終在B的前面，A向前邁進，B跟上，A把自己的位置交給B（即執行B = A操作），然后A 再前進占領新的位置，B再跟上……直到占領所有的陣地，前進結束 。像這種兩個數一前一后逐步向某個位置逼近的方法稱之為迭代法 。迭代法也稱輾轉法，是一種不斷用變量的舊值遞推新值的過程,跟迭代法相對應的是直接法（或者稱為一次解法），即一次性解決問題 。迭代算法是用計算機解決問題的一種基本方法 。它利用計算機運算速度快、適合做重復性操作的特點，讓計算機對一組指令（或一定步驟）進行重復執行，在每次執行這組指令（或這些步驟）時，都從變量的原值推出它的一個新值 。利用迭代算法解決問題，需要做好以下三個方面的工作： 一、確定迭代變量 。在可以用迭代算法解決的問題中，至少存在一個直接或間接地不斷由舊值遞推出新值的變量，這個變量就是迭代變量 。二、建立迭代關系式 。所謂迭代關系式，指如何從變量的前一個值推出其下一個值的公式（或關系） 。迭代關系式的建立是解決迭代問題的關鍵，通常可以使用遞推或倒推的方法來完成 。三、對迭代過程進行控制 。在什么時候結束迭代過程？這是編寫迭代程序必須考慮的問題 。不能讓迭代過程無休止地重復執行下去 。迭代過程的控制通?？煞譃閮煞N情況：一種是所需的迭代次數是個確定的值，可以計算出來；另一種是所需的迭代次數無法確定 。對于前一種情況，可以構建一個固定次數的循環來實現對迭代過程的控制；對于后一種情況，需要進一步分析出用來結束迭代過程的條件 。最經典的迭代算法是歐幾里德算法，用于計算兩個整數a,b的最大公約數 。其計算原理依賴于下面的定理： 定理：gcd(a, b) = gcd(b, a mod b) 證明：a可以表示成a = kb + r，則r = a mod b。假設d是a,b的一個公約數，則有 a%d==0, b%d==0，而r = a - kb，因此r%d==0，因此d是(b, a mod b)的公約數 同理，假設d 是(b, a mod b)的公約數，則 b%d==0 , r%d==0，但是a = kb +r，因此d也是(a,b)的公約數。因此(a,b)和(b,a mod b)的公約數是一樣的，其最大公約數也必然相等，得證 。歐幾里德算法就是根據這個原理來做的，歐幾里德算法又叫輾轉相除法，它是一個反復迭代執行，直到余數等于0停止的步驟，這實際上是一個循環結構 。其算法用C語言描述為： int Gcd_2(int a, int b)// 歐幾里德算法求a, b的最大公約數 { if (a<=0 || b<=0) //預防錯誤 return 0; int temp; while (b > 0) //b總是表示較小的那個數，若不是則交換a，b的值 { temp = a % b; //迭代關系式 a = b%a; //是那個膽小鬼，始終跟在b的后面 b = temp%b; //向前沖鋒占領新的位置 } return a; } 從上面的程序我們可以看到a，b是迭代變量，迭代關系是temp = a % b; 根據迭代關系我們可以由舊值推出新值，然后循環執a = b; b = temp;直到迭代過程結束（余數為0） 。在這里a好比那個膽小鬼，總是從b手中接過位置，而b則是那個努力向前沖的先鋒 。還有一個很典型的例子是斐波那契(Fibonacci)數列 。斐波那契數列為：0、1、1、2、3、5、8、13、21、…，即 fib(1)=0; fib(2)=1; fib(n)=fib(n-1)+fib(n-2) (當n>2時) 。在n>2時，fib(n)總可以由fib(n-1)和fib(n-2)得到，由舊值遞推出新值，這是一個典型的迭代關系，所以我們可以考慮迭代算法 。int Fib(int n) //斐波那契(Fibonacci)數列 { if (n < 1)//預防錯誤 return 0; if (n == 1 || n == 2)//特殊值，無需迭代 return 1; int f1 = 1, f2 = 1, fn;//迭代變量 int i; for(i=3; i<=n; ++i)//用i的值來限制迭代的次數 { fn = f1 + f2; //迭代關系式 f1 = f2; //f1和f2迭代前進，其中f2在f1的前面 f2 = fn; } return fn; }
編輯本段C語言代碼
double func(double x) //函數 { return x*x*x*x-3*x*x*x+1.5*x*x-4.0; } double func1(double x) //導函數 { return 4*x*x*x-9*x*x+3*x; } int Newton(double *x,double precision,int maxcyc) //迭代次數 { double x1,x0; int k; x0=*x; for(k=0;k<maxcyc;k++) { if(func1(x0)==0.0)//若通過初值，函數返回值為0 { printf("迭代過程中導數為0!
"); return 0; } x1=x0-func(x0)/func1(x0);//進行牛頓迭代計算 if(fabs(x1-x0)<precision || fabs(func(x1))<precision) //達到結束條件 { *x=x1; //返回結果 return 1; } else //未達到結束條件 x0=x1; //準備下一次迭代 } printf("迭代次數超過預期!
"); //迭代次數達到，仍沒有達到精度 return 0; } int main() { double x,precision; int maxcyc; printf("輸入初始迭代值x0:"); scanf("%lf",&x); printf("輸入最大迭代次數:"); scanf("%d",&maxcyc); printf("迭代要求的精度:"); scanf("%lf",&precision); if(Newton(&x,precision,maxcyc)==1) //若函數返回值為1 printf("該值附近的根為:%lf
",x); else //若函數返回值為0 printf("迭代失敗!
"); getch(); return 0; }
編輯本段C++代碼
//此函數是用來求3元一次方程ax^3+bx^2+cx+d=0的解 //比如 x^3-27=0,我們就可以輸入1 0 0 -27，這樣我們就可以得到一個解 #include<iostream> #include<cmath> using namespace std; int main() { double diedai(double a,double b,double c,double d,double x); double a,b,c,d; double x=10000.0; cout<<"請依次輸入方程四個系數："; cin>>a>>b>>c>>d; x=diedai(a,b,c,d,x); cout<<x<<endl; return 0; } double diedai(double a,double b,double c,double d,double x) { while(abs(a*x*x*x+b*x*x+c*x+d)>0.000001) { x=x-(a*x*x*x+b*x*x+c*x+d)/(3*a*x*x+2*b*x+c); } return x; }
編輯本段matlab代碼
1.定義函數
function y=f(x) y=f(x)；%函數f(x)的表達式 function y=z(x) y=z(x)；%函數z(x)的表達式
2.主程序
x=X；%迭代初值 i=0；%迭代次數計算 while i<= I；%迭代次數 y=x-y(x)/z(x)；%牛頓迭代格式 if abs(y-x)>ε；%收斂判斷 x=y； else break end i=i+1； end fprintf('
%s%.4f\t%s%d'，'x='，x，'i='，i) %輸出結果
編輯本段Python代碼
Python代碼以實例展示求解f(x) = (x-3)**3，f(x) = 0 的根 。
[1]def f(x): return (x-3)**3 ’''定義f(x) = (x-3)**3''' def fd(x): return 3*((x-3)**2) ’''定義f'(x) = 3*((x-3)**2) def newtonMethod(n,assum): time = n x = assum Next = 0 A = f(x) B = fd(x) print('A = ' + str(A) + ',B = ' + str(B) + ',time = ' + str(time)) if f(x) == 0.0: return time,x else: Next = x - A/B print('Next x = '+ str(Next)) if A == f(Next): print('Meet f(x) = 0 , x = ' + str(Next)) ’''設置迭代跳出條件，同時輸出滿足f(x) = 0的x值''' else: return newtonMethod(n+1,Next) newtonMethod(0,4.0) ’''設置從0開始計數，x0 = 4.0'''
關于迭代算法和迭代算法原理的內容就分享到這兒！更多實用知識經驗，盡在 m.apearl.cn