牛顿迭代法

0.结论#

设 $x _ i$ 是方程 $f(x) = 0$ 的近似解，则有 $x _ {i + 1} = x _ i - \frac{f(x _ i)}{f'(x _ i)}$

一般情况下，足够精确的解可以在 $\Omicron(\log n)$ 的时间复杂度内求出。

同时，牛顿迭代法一次只能求出一个零点，所以你可以事先判断零点的大概位置，再多取几个初始值。

既然有个 OI 标签那就给个代码吧

1
2
3
4
5
6
7

double Newton(double x)
{
    t = /*迭代次数*/;
    while(t--)
        x = x - (f(x) / df(x)); //函数 & 导函数求值
    return x;
}

1.实例#

问就是 OI Wiki 没教证明

求 $\sqrt[k]{n}$#

构造 $f(x) = x ^ k - n$，则 $f'(x) = kx ^ {k - 1}$

发现该函数至多有一个零点，所以随便取个初值就行（不然还得考虑牛顿分形）。

其实这玩意能讲的挺少的。