0 前置知识&&写在前面
学习牛顿迭代法需要能熟练地掌握求导QwQ
学习泰勒公式需要能熟练地掌握求导并对无穷级数有一定了解QwQ
要想看懂牛顿迭代法的二次收敛证明需要一定的高数基础QwQ（看不懂也无所谓，会用就行）
学习泰勒公式需要能熟练地掌握求导并对无穷级数有一定了解QwQ
一点都不会怎么办？没有问题，会用就行NOIP不考QwQ
求零点、不动点、函数近似值、极值、最值……基本可以认为是一类问题，所以本文以讨论如何**求零点的近似值为主**
因为笔者太弱所以没有遗传算法、模拟退火之类的玄学算法
笔者是∑狂魔，要是有式子不理解请展开QwQ
-
计算mid=(l+r)/2
-
若f(l)*f(mid)<0，则令r=mid，否则令l=mid
-
如果达到预定精度，跳转到4，否则跳转到1
-
结束
-
稍加计算便得到了
-
这篇文章偏数学一些，如果不能理解的话请多读几遍QwQ
-
其实可写的还有很多，限于篇幅就到此为止了（现在在后台打个字都要卡两秒QwQ）
-
因为笔者是个蒟蒻，所以如果有错误，烦请各位dalao不吝赐教
-
[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（https://en.wikipedia.org/wiki/Newton's_method）
-
[4]Taylor's theorem - Wikipedia（https://en.wikipedia.org/wiki/Taylor%27s_theorem）
-
[5]一个Sqrt函数引发的血案（ ）（这个是笔者能找到的最早的一篇了QwQ）
对于低于5次的多项式方程，我们有通用的公式解法求零点的精确值
对于一些特殊高次多项式方程（例如可以因式分解的或者满足一些特定形式的方程）的和一些特殊的超越方程，我们也有方法求零点的精确值
但是其余的情况呢？
目前来说我们只能求近似值QwQ（而且在实际应用中，精确值往往也会被转换成近似值）
1 二分法 (int\long long\etc.)
这个方法可以说相当常见了（括号里是此法经常被应用于的数据类型）QwQ
对于在区间[l,r]内单调、连续且有f(l)*f(r)<0成立的f(x)，做如下操作：
循环次数：
附程序：
2 0.618法\优选法 (float\double\long double)
可能有的读者没听说过，不过这个方法其实还是很常用的QwQ
这个方法更常用于求单峰函数最值，所以这里以求单峰函数最值为例讲解
先证明一下它的优越性（过程摘自人教版高中数学选修4-7 优选法与试验设计初步）（没错真的有这本选修QwQ）
一句话概括就是在缩小区间后可以只计算一个试点坐标，从而保证最优
操作流程如下（和二分法类似）
附程序：
读者们可以在洛谷P3382（https://www.luogu.org/problemnew/show/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的动图（https://en.wikipedia.org/wiki/Newton'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}
关于这个有一个相当有名的故事
为了节约篇幅，笔者把文章放在这里了（https://www.luogu.org/paste/04z8pvrb）
6 后记
7 主要参考资料
本文发布于洛谷日报，特约作者：khong
原文地址：https://khong-biet.blog.luogu.org/methods-of-GetApproxNumber