牛顿迭代的初值该怎么设置

· · 个人记录

作为一个初学者一直以为牛顿迭代的初值可以随便设置，但实际上不然。

https://oi-wiki.org/math/newton/ OI-Wiki 的页面上提出 x_0 可以随便设置，其实是不对的，因为我之前随便测了一下怎么都没办法逼近答案。。

所以牛顿迭代的初值到底该怎么设置。。牛顿迭代有公式

x_{i+1}=x_i-\frac{f(x_i)}{f'(x_i)}

原理暂略，假设我们要求 \sqrt n ，构造 f(x)=x^2-n 那么 f'(x)=2x

x_{i+1}=x_i-\frac{x_i^2-n}{2x_i}

然后发现这个式子有除法，我们应当避免，那么构造

f(x)=x^{-2}-n

显然 \frac{1}{\sqrt n} 为该方程的根，那么 \sqrt n 只需求出之后再乘以 n 即可，而 f'(x)=-2x^{-3} 那么

x_{i+1}=x_i-\frac{x_i^{-2}-n}{-2x_i^{-3}}=\frac{3x_i-nx_i^3}{2}

设误差 \epsilon_i=1-nx_i^2 那么

&=1-n\left(\frac{3x_i-nx_i^3}{2}\right)^2\\ &=1-n\left(\frac{x_i(2+\epsilon_i)}{2}\right)^2\\ &=1-\frac{nx_i^2(2+\epsilon_i)^2}{4}\\ &=1-\frac{(1-\epsilon_i)(2+\epsilon_i)^2}{4}\\ &=\frac{\epsilon_i^3+3\epsilon_i^2}{4}\\ &=\epsilon_i^2\frac{\epsilon_i+3}{4}\end{aligned}

如果 \vert\epsilon_i\vert \lt 1 那么 \epsilon_i^2\lt \vert \epsilon_i\vert 且 \left\vert\frac{\epsilon_i+3}{4}\right\vert\lt 1 且收敛速度是比较快的。

再来看一组倒数的例子，假设要求 \frac{1}{n} 我们构造 f(x)=\frac{1}{x}-n 显然 \frac{1}{n} 为根，代入有

x_{i+1}=x_{i}(2-nx_i)

设误差为 \epsilon_i =1-nx_i 那么

&=1-nx_{i}(2-nx_i)\\ &=1-2nx_i+n^2x_i^2\\ &=(1-nx_i)^2\\ &=\epsilon_i^2\end{aligned}

这没有上面的收敛那么快。

所以说初值那可不是随便设的，例如上面倒数的初值必须让 \vert\epsilon_0\vert\lt 1 否则误差会越来越大。