產生背景
牛頓疊代法（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",≺ision);if(Newton(&x,precision,maxcyc)==1） //若函式返回值為1printf("該值附近的根為：%lf\n",x);else //若函式返回值為0printf("疊代失敗！\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%.4f\t%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'''
