産生背景
牛頓叠代法（Newton's method）又稱為牛頓-拉夫遜（拉弗森）方法（Newton-Raphson method），它是牛頓在17世紀提出的一種在實數域和複數域上近似求解方程的方法。多數方程不存在求根公式，因此求精确根非常困難，甚至不可能，從而尋找方程的近似根就顯得特别重要。方法使用函數f(x）的泰勒級數的前面幾項來尋找方程f(x) = 0的根。牛頓叠代法是求方程根的重要方法之一，其最大優點是在方程f(x) = 0的單根附近具有平方收斂，而且該法還可以用來求方程的重根、複根，此時線性收斂，但是可通過一些方法變成超線性收斂。另外該方法廣泛用于計算機編程中。
牛頓叠代公式
設r是
的根，選取
作為r的初始近似值，過點
做曲線
的切線L，L的方程為
，求出L與x軸交點的橫坐标
，稱x為r的一次近似值。過點
做曲線
的切線，并求該切線與x軸交點的橫坐标
，稱
為r的二次近似值。重複以上過程，得r的近似值序列，其中，
稱為r的
次近似值，上式稱為。
用牛頓叠代法解非線性方程，是把非線性方程
線性化的一種近似方法。把
在點
的某鄰域内展開成泰勒級數
，取其線性部分（即泰勒展開的前兩項），并令其等于0，即
，以此作為非線性方程
的近似方程，若
，則其解為
， 這樣，得到牛頓叠代法的一個叠代關系式：
。
已經證明，如果是連續的，并且待求的零點是孤立的，那麼在零點周圍存在一個區域，隻要初始值位于這個鄰近區域内，那麼牛頓法必定收斂。 并且，如果不為0, 那麼牛頓法将具有平方收斂的性能. 粗略的說，這意味着每叠代一次，牛頓法結果的有效數字将增加一倍。
軍人在進攻時常采用交替掩護進攻的方式，若在數軸上的點表示A，B兩人的位置，規定在前面的數大于後面的數，則是A>B，B>A交替出現。但現在假設軍中有一個膽小鬼，同時大家又都很照顧他，每次沖鋒都是讓他跟在後面，每當前面的人占據一個新的位置，就把位置交給他，然後其他人再往前占領新的位置。也就是A始終在B的前面，A向前邁進，B跟上，A把自己的位置交給B（即執行B = A），然後A 再前進占領新的位置，B再跟上，直到占領所有的陣地，前進結束。像這種兩個數一前一後逐步向某個位置逼近的方法稱為叠代法。
叠代法也稱輾轉法，是一種不斷用變量的舊值遞推新值的過程，跟叠代法相對應的是直接法（或者稱為一次解法），即一次性解決問題。叠代算法是用計算機解決問題的一種基本方法。它利用計算機運算速度快、适合做重複性操作的特點，讓計算機對一組指令（或一定步驟）重複執行，在每次執行這組指令（或這些步驟）時，都從變量的原值推出它的一個新值。
利用叠代算法解決問題，需要做好以下三個方面的工作：
一、确定叠代變量
在可以用叠代算法解決的問題中，至少存在一個可直接或間接地不斷由舊值遞推出新值的變量，這個變量就是叠代變量。
二、建立叠代關系式
所謂叠代關系式，指如何從變量的前一個值推出其下一個值的公式（或關系）。叠代關系式的建立是解決叠代問題的關鍵，通常可以使用遞推或倒推的方法來完成。
三、對叠代過程進行控制
在什麼時候結束叠代過程？這是編寫叠代程序必須考慮的問題。不能讓叠代過程無休止地執行下去。叠代過程的控制通常可分為兩種情況：一種是所需的叠代次數是個确定的值，可以計算出來；另一種是所需的叠代次數無法确定。對于前一種情況，可以構建一個固定次數的循環來實現對叠代過程的控制；對于後一種情況，需要進一步分析得出可用來結束叠代過程的條件。
示例
歐幾裡德算法
最經典的叠代算法是歐幾裡德算法，用于計算兩個整數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;
b = temp;
}
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⑴=0; fib⑵=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
{
if(func1(x0)==0.0)//若通過初值，函數返回值為0
{
printf("叠代過程中導數為0!n");
return 0;
}
x1=x0-func(x0)/func1(x0);//進行牛頓叠代計算
if(fabs(x1-x0)
{
*x=x1; //返回結果
return 1;
}
else //未達到結束條件
x0=x1; //準備下一次叠代
}
printf("叠代次數超過預期！n"); //叠代次數達到，仍沒有達到精度
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("該值附近的根為：%lfn",x);
else //若函數返回值為0
printf("叠代失敗！n");
getch();
return 0;
}
matlab代碼
定義函數
function y=f(x)
y=f(x）；%函數f(x）的表達式
end
function z=h(x)
z=h(x）；%函數h(x）的表達式
end
主程序
x=X;%叠代初值
i=0;%叠代次數計算
while i<= 100%叠代次數
x0=X-f(X)/h(X);%牛頓叠代格式
if abs(x0-X)>0.01；%收斂判斷
X=x0;
else break
end
i=i+1;
end
fprintf('n%s%.4ft%s%d'，'X='，X，'i='，i) %輸出結果
Python代碼
Python代碼以實例展示求解f(x) = (x-3）**3，f(x) = 0 的根。
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:
returnnewtonMethod(n+1,Next)
newtonMethod(0,4.0) ’''設置從0開始計數，x0 = 4.0'''
