查看“︁牛顿法”︁的源代码

{{NoteTA
|G1 = Math
|1 = zh-cn:域; zh-tw:體;
|2 =zh-hans:迭代;zh-hant:疊代;
}}
[[File:Ganzhi001.jpg|right|200px]]
'''牛顿法'''（{{lang-en|Newton's method}}）又称为'''牛顿-拉弗森方法'''（{{lang-en|Newton-Raphson method}}），它是一种在实数域和复数域上近似求解方程的方法。方法使用函数<math>f(x)</math>的[[泰勒级数]]的前面几项来寻找方程<math>f(x)=0</math>的根。

==起源==

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

== 方法说明 ==
[[Image:NewtonIteration Ani.gif|alt Illustration of Newton's method|thumb|right|300px|蓝线表示方程<math>f</math>而红线表示切线。可以看出<math>x_{n+1}</math>比<math>x_n</math>更靠近<math>f</math>所要求的根<math>x</math>。]]

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

:<math>0= (x-x_0)\cdot f'(x_0)+f(x_0)</math>

我们将新求得的点的<math>x</math>坐标命名为<math>x_1</math>，通常<math>x_1</math>会比<math>x_0</math>更接近方程<math>f(x)=0</math>的解。因此我们现在可以利用<math>x_1</math>开始下一轮[[迭代]]。迭代公式可化简为如下所示：

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

已有证明牛顿迭代法的'''二次收敛'''<ref>{{Cite web |url=https://cs.nyu.edu/overton/NumericalComputing/newton.pdf |title=存档副本 |access-date=2018-06-26 |archive-date=2021-04-24 |archive-url=https://web.archive.org/web/20210424004511/https://cs.nyu.edu/overton/NumericalComputing/newton.pdf |dead-url=no }}</ref>必须满足以下条件：<br>
<math>f'(x) \ne 0</math>; 对于所有<math>x\in I</math>，其中<math>I</math>为区间{{math|[''α'' − ''r'', ''α'' + ''r'']|big=}}，且<math>x_0</math>在区间其中<math>I</math>内，即 <math>\left| \alpha-x_0 \right| \leq r</math> 的; <br>
对于所有<math>x\in I</math>，<math>f''(x)</math>是连续的; <br>
<math>x_0</math>足够接近根{{math | α}}。<br>

然而当<math>f(x) = 0</math>在<math>x = \alpha</math>处有m重根时，这时牛顿法会降为'''线性收敛'''，虽然使用牛顿法也可以继续算下去，但收敛速度会减慢。<ref name="ZhangHW">{{cite book |editor=张宏伟，金光日，施吉林，董波 |title=计算机科学计算 |date=2005 |publisher=高等教育出版社 |location=北京 |isbn=9787040365955 |page=138 |edition=2013年第2版}}</ref>

==其它例子==
=== 第一个例子 ===

求方程<math>\cos(x) - x^3 = 0</math>的根。令<math>f(x) = \cos(x) - x^3</math>，两边求导，得<math>f'(x) = - \sin(x) - 3x^2</math>。由于<math>-1 \le \cos(x) \le 1 (\forall x)</math>，则<math>-1 \le x^3 \le 1</math>，即<math>-1 \le x \le 1</math>，可知方程的根位于<math>0</math>和<math>1</math>之间。我们从<math>x_0 = 0.5</math>开始。

:<math>\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}
</math>

=== 第二个例子 ===

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

求<math>a</math>的<math>m</math>次方根。

<math>x^m - a = 0</math>

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

而a的m次方根，亦是x的解，

以牛顿法来迭代：

<math>x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}</math>

<math>x_{n+1} = x_n - \frac{x_n^m-a}{mx_n^{m-1}}</math>

<math>x_{n+1} = x_n - \frac{x_n}{m}(1-ax_n^{-m})</math>

（或 <math>x_{n+1} = x_n - \frac{1}{m}\left(x_n-a\frac{x_n}{x_n^m}\right)</math>）

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

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

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

用Python:<syntaxhighlight lang="python3" line="1">
from math import pow
def f(x):
    y = pow(x,3)-(10*x*x)+x+1
    return y
def dx(x):
    y = (3*x*x)-(20*x)+1
    return y
x = 1
for i in range(1000):
    x = x - (f(x)/dx(x))
print(x)
</syntaxhighlight>用C語言:<syntaxhighlight lang="c" line="1">
#include <stdio.h>
#include <math.h>
double x = 1.0;
double f(double x){
    double y = pow(x,3)-(10*x*x)+x+1;
    return y;}
double dx(double x){
    double y = (3*x*x)-(20*x)+1;
    return y;}
int main (){
    for(int i=0;i<1000;i++){
    x = x - (f(x)/dx(x));}
    printf(" %f",x);
    return 0;
}
</syntaxhighlight>只要修改f(x)和dx(x)函數就可以解其他方程式

== 註解 ==
{{Reflist|2}}

== 外部連結 ==
{{Portal|数学}}
* [http://episte.math.ntu.edu.tw/java/jav_newton/ JAVA：牛頓勘根法] {{Wayback|url=http://episte.math.ntu.edu.tw/java/jav_newton/ |date=20210424004538 }} {{zh-tw}}

{{求根演算法}}
{{艾薩克·牛頓}}
{{authority control}}

[[Category:最优化算法]]
[[Category:求根算法]]
[[Category:艾萨克·牛顿]]