牛顿法

牛顿法（）又称为牛顿-拉弗森方法（），它是一种在实数域和复数域上近似求解方程的方法。方法使用函数f(x)的泰勒级数的前面几项来寻找方程f(x)=0的根。

起源
牛顿法最初由艾萨克·牛頓在《流数法》（Method of Fluxions，1671年完成，在牛顿去世后於1736年公开发表）中提出。约瑟夫·鮑易也曾于1690年在Analysis Aequationum中提出此方法。

方法说明
首先，选择一个接近函数f(x)零点的x_0，计算相应的f(x_0)和切线斜率f'(x_0)（这里f'表示函数f的导数）。然后我们计算穿过点(x_0, f(x_0))并且斜率为f'(x_0)的直线和x轴的交点的x坐标，也就是求如下方程的解：

:0= (x-x_0)\cdot f'(x_0)+f(x_0)

我们将新求得的点的x坐标命名为x_1，通常x_1会比x_0更接近方程f(x)=0的解。若f'(x_0)\neq 0時，我们可以利用x_1开始下一轮迭代。當f'(x_n)\neq 0時，迭代公式可化简为如下所示：

:x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}

已有证明牛顿迭代法的二次收敛必须满足以下条件：

f'(x) \ne 0; 对于所有x\in I，其中I为区间，且x_0在区间其中I内，即 \left| \alpha-x_0 \right| \leq r 的;

对于所有x\in I，f*(x)是连续的;

x_0足够接近根。

然而当f(x) = 0在x = \alpha处有m重根时，这时牛顿法会降为线性收敛，虽然使用牛顿法也可以继续算下去，但收敛速度会减慢。

其它例子
第一个例子
求方程\cos(x) - x^3 = 0在[0,1]區間中的一個實根。令f(x) = \cos(x) - x^3，两边求导，得f'(x) = - \sin(x) - 3x^2。由于-1 \le \cos(x) \le 1 (\forall x)，则-1 \le x^3 \le 1，即-1 \le x \le 1，可知方程的根位于0和1之间。且f'(0.5)\neq 0，我们嘗試从x_0 = 0.5开始。

:\begin{matrix}
x_1 & = & x_0 - \frac{f(x_0)}{f'(x_0)} & = & 0.5 - \frac{\cos(0.5) - 0.5^3}{-\sin(0.5) - 3 \times 0.5^2} & = & 1.112141637097 \\
x_2 & = & x_1 - \frac{f(x_1)}{f'(x_1)} & = & \vdots & = & \underline{0.}909672693736 \\
x_3 & = & \vdots & = & \vdots & = & \underline{0.86}7263818209 \\
x_4 & = & \vdots & = & \vdots & = & \underline{0.86547}7135298 \\
x_5 & = & \vdots & = & \vdots & = & \underline{0.8654740331}11 \\
x_6 & = & \vdots &= & \vdots & = & \underline{0.865474033102}
\end{matrix}

第二个例子
牛顿法亦可发挥与泰勒展开式，对于函式展开的功能。

求a的m次方根(m\neq 0)。

x^m - a = 0

设f(x) = x^m - a，f'(x) = mx^{m-1}

而a的m次方根，亦是f(x)=0的解，

以牛顿法来迭代：

x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} if f'(x_n)\neq 0

x_{n+1} = x_n - \frac{x_n^m-a}{mx_n^{m-1}}

x_{n+1} = x_n - \frac{x_n}{m}(1-ax_n^{-m}) where mx_n^{m-1}\neq 0

應用
求解極值問題
牛頓法也被用於求函數的極值。由於函數取極值的點處的導數值為零，故可用牛頓法求導函數的零點，其疊代式為
:x_{n+1}=x_n-\frac{f^\prime(x_n)}{f^{\prime\prime}(x_n)}.
求拐点的公式以此类推

電腦程式
可以用程式寫出牛頓法:

例題:f(x)=x^3-10x^2+x+1=0 求x

用Python:
from math import pow
def f(x):
y = pow(x,3)-(10xx)+x+1
return y
def dx(x):
y = (3xx)-(20*x)+1
return y
x = 0
if dx(x) == 0:
print(f"Rejected Initial data: Initial dx({x}) is zero.")
else:
for i in range(1000):
if dx(x) == 0:
print(f"Failures: Derivative became zero at iteration {i}.")
break
else:
x = x - (f(x)/dx(x))
print(x)
用C語言:
#include
#include
double x = 1.0;
double f(double x){
double y = pow(x,3)-(10xx)+x+1;
return y;}
double dx(double x){
double y = (3xx)-(20*x)+1;
return y;}
int main (){
for(int i=0;i只要修改f(x)和dx(x)函數就可以解其他方程式

註解
外部連結

• [http://episte.math.ntu.edu.tw/java/jav_newton/ JAVA：牛頓勘根法]