牛顿迭代法
引入
本文介绍如何用牛顿迭代法（Newton's method for finding roots）求方程的近似解，该方法于 17 世纪由牛顿提出。
具体的任务是，对于在
解释
初始时我们从给定的
假设我们目前的近似解是
整理后得到如下递推式：
直观地说，如果
牛顿迭代法的收敛率是平方级别的，这意味着每次迭代后近似解的精确数位会翻倍。 关于牛顿迭代法的收敛性证明可参考 citizendium - Newton method Convergence analysis
当然牛顿迭代法也同样存在着缺陷，详情参考 Xiaolin Wu - Roots of Equations 第 18 - 20 页分析
求解平方根
我们尝试用牛顿迭代法求解平方根。设
在实现的时候注意设置合适的精度。代码如下
实现
=== "C++"
```cpp
double sqrt_newton(double n) {
const double eps = 1E-15;
double x = 1;
while (true) {
double nx = (x + n / x) / 2;
if (abs(x - nx) < eps) break;
x = nx;
}
return x;
}
```=== "Python"
```python
def sqrt_newton(n):
eps = 1e-15
x = 1
while True:
nx = (x + n / x) / 2
if abs(x - nx) < eps:
break
x = nx
return x
```求解整数平方根
尽管我们可以调用 sqrt() 函数来获取平方根的值，但这里还是讲一下牛顿迭代法的变种算法，用于求不等式
实现
=== "C++"
```cpp
int isqrt_newton(int n) {
int x = 1;
bool decreased = false;
for (;;) {
int nx = (x + n / x) >> 1;
if (x == nx || (nx > x && decreased)) break;
decreased = nx < x;
x = nx;
}
return x;
}
```=== "Python"
```python
def isqrt_newton(n):
x = 1
decreased = False
while True:
nx = (x + n // x) // 2
if x == nx or (nx > x and decreased):
break
decreased = nx < x
x = nx
return x
```高精度平方根
最后考虑高精度的牛顿迭代法。迭代的方法是不变的，但这次我们需要关注初始时近似解的设置，即
实现
给出 Java 代码的实现：
public static BigInteger isqrtNewton(BigInteger n) {
BigInteger a = BigInteger.ONE.shiftLeft(n.bitLength() / 2);
boolean p_dec = false;
for (;;) {
BigInteger b = n.divide(a).add(a).shiftRight(1);
if (a.compareTo(b) == 0 || a.compareTo(b) < 0 && p_dec)
break;
p_dec = a.compareTo(b) > 0;
a = b;
}
return a;
}实践效果：在
习题
-
本页面主要译自博文 Метод Ньютона (касательных) для поиска корней 与其英文翻译版 Newton's method for finding roots。其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0。
贡献者：@Menci@WenzelTian@hly1204@mgt@H-J-Granger@Ir1dXD@李瑞@Marcythm@Richard@landcold7@Xeonacid
本页面最近更新：2/3/2023, 12:00:00 AM，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用