0 前置知识&&写在前面

学习牛顿迭代法需要能熟练地掌握求导QwQ

学习泰勒公式需要能熟练地掌握求导并对无穷级数有一定了解QwQ

要想看懂牛顿迭代法的二次收敛证明需要一定的高数基础QwQ（看不懂也无所谓，会用就行）

学习泰勒公式需要能熟练地掌握求导并对无穷级数有一定了解QwQ

一点都不会怎么办？没有问题，会用就行NOIP不考QwQ

求零点、不动点、函数近似值、极值、最值……基本可以认为是一类问题，所以本文以讨论如何**求零点的近似值为主**

因为笔者太弱所以没有遗传算法、模拟退火之类的玄学算法

笔者是∑狂魔，要是有式子不理解请展开QwQ

对于低于5次的多项式方程，我们有通用的公式解法求零点的精确值

对于一些特殊高次多项式方程（例如可以因式分解的或者满足一些特定形式的方程）的和一些特殊的超越方程，我们也有方法求零点的精确值

但是其余的情况呢？

目前来说我们只能求近似值QwQ（而且在实际应用中，精确值往往也会被转换成近似值）

1 二分法 (int\long long\etc.)

这个方法可以说相当常见了（括号里是此法经常被应用于的数据类型）QwQ

对于在区间[l,r]内单调、连续且有f(l)*f(r)<0成立的f(x)，做如下操作：

计算mid=(l+r)/2

若f(l)*f(mid)<0，则令r=mid，否则令l=mid

如果达到预定精度，跳转到4，否则跳转到1

结束

循环次数：

附程序：

2 0.618法\优选法 (float\double\long double)

可能有的读者没听说过，不过这个方法其实还是很常用的QwQ

这个方法更常用于求单峰函数最值，所以这里以求单峰函数最值为例讲解

先证明一下它的优越性（过程摘自人教版高中数学选修4-7 优选法与试验设计初步）（没错真的有这本选修QwQ）

一句话概括就是在缩小区间后可以只计算一个试点坐标，从而保证最优

操作流程如下（和二分法类似）

附程序：

读者们可以在洛谷P3382（）中测试一下(～o￣3￣)～（虽然是三分法模板但也可以用优选法\二分法做哦）

关于这个还有一个类似方法：斐波那契法。有兴趣的读者可以查阅相关资料才不是笔者不想写_(:3」∠)_

3 泰勒公式

先讲这个是为了为下文牛顿迭代法二次收敛的证明做铺垫，不想看证明的可以略过QwQ（不过还是推荐了解一下，挺有趣的）

这里假定函数f(x)在x_0处有任意阶导数

我们可以很容易地求出多项式和类指数函数的近似值，但是像三角函数、对数函数这样的我们又该如何求近似值呢

对了，就是用泰勒公式QwQ

泰勒公式的想法很简单，就是构造一个多项式函数，使得它与函数在处的原函数值和各阶导数均相等，即

因为

于是我们就得到了（解n元一次方程组，很简单的）

当n→∞时，我们可以认为f(x)=g(x)

而当n有一个确定的值时，f(x)就可以写成g(x)+R_n(x)了

其中R_n(x)是余项，它有好几种不同的写法，这里选用拉格朗日余项。因为它不仅在下文中牛顿迭代法的二次收敛证明中出现了，而且形式和前面的几项非常相近

其中ξ_L在x和x_0之间

要是了解过拉格朗日中值定理的读者应该很快就能领会

当n→∞时，有（泰勒级数）

特别地，当x_0=0时，有（麦克劳林级数）

另外注意应用麦克劳林级数并且x在某个范围之外时，得到的结果可能是发散的（就是，这个不展开讲，有兴趣的读者可以去学习无穷级数相关知识）

附上Wikipedia的动图

对证明感兴趣的读者可以自行查阅相关资料

不能理解无所谓反正NOIP不考，下面给出几个常见的泰勒级数

程序略QwQ

4 牛顿迭代法

先说说这个方法的过程

稍加计算便得到了

既然是迭代，那么自然就有

其中x_n代表第n次迭代

附上Wikipedia的动图（'s_method）

二次收敛证明（Wikipedia上的，笔者翻译QwQ）（还是那句话：看不懂无所谓，会用就行QwQ）：

程序：

当然，上述各方法的应用范围远不止于此，有兴趣的读者可以自行查阅相关资料QwQ

5 赠品

5.1 cos(x)=x的解析解

对于PhOer来说，cos(x)=x这个方程应该是相当熟悉了QwQ

笔者在这里放上解析解（近似值x=0.739），详情见参考文献[2]（文献里讲的是t sin( x)=x-m的解法，不过笔者太弱了，实在是看不懂QwQ）

5.2 快速求1/sqrt{x}

关于这个有一个相当有名的故事

为了节约篇幅，笔者把文章放在这里了（）

6 后记

这篇文章偏数学一些，如果不能理解的话请多读几遍QwQ

其实可写的还有很多，限于篇幅就到此为止了（现在在后台打个字都要卡两秒QwQ）

因为笔者是个蒟蒻，所以如果有错误，烦请各位dalao不吝赐教

7 主要参考资料

[1] 人教版高中数学选修4-7 优选法与试验设计初步

[2] Siewert C E, Burniston E E. An exact analytical solution of Kepler's equation[J]. Celestial Mechanics, 1972, 6(3):294-304.

[3]Newton's method - Wikipedia（'s_method）

[4]Taylor's theorem - Wikipedia（）

[5]一个Sqrt函数引发的血案（）（这个是笔者能找到的最早的一篇了QwQ）

本文发布于洛谷日报，特约作者：khong

原文地址：