导数和牛顿迭代

发表于 更新于 分类于

$\ \ \ \ \ \ \ \,$关于导数和牛顿迭代的复习笔记：

导数

$\ \ \ \ \ \ \,$导数是描述一个函数的变化情况的函数，函数$f$的导数记作$f’$。

$\ \ \ \ \ \ \,$导数（英语：Derivative）是微积分学中重要的基础概念。一个函数在某一点的导数描述了这个函数在这一点附近的变化率。导数的本质是通过极限的概念对函数进行局部的线性逼近$\ \ \ \ \ \ $——wiki。

导数的运算法则

  • $(f+g)’=f’+g’$

  • $(f-g)’=f’-g’$

  • $(f\cdot g)’=f’\cdot g’$

  • $(af)’=af’$

  • $(fa)’=f’a+a\cdot f’$

  • $(f/g)’=\frac{f’\cdot g-f\cdot g’}{g^2}$

常见函数的导数

  • $(x^k)’=kx^{k-1}$

  • $(a^x)’=a^x\cdot \ln a$

  • $(e^x)’=e^{x}$

  • $(\log _a x)’=\frac{1}{x \cdot \ln a}$

  • $(\ln x)’=\frac{1}{x}$

  • $(\sin x)’=\cos x$

  • $(\cos x)’=-\sin x$

  • $(\tan x)’=\sec ^2x$

  • $(\cot x)’=-\csc ^2x$

  • $(\sec x)’=\tan x\cdot\csc x$

  • $(\csc x)’=-\cot x\cdot\csc x$

  • $(\arcsin x)’=\frac{1}{\sqrt{1-x^2}}$

  • $(\arccos x)’=-\frac{1}{\sqrt{1-x^2}}$

  • $(\arctan x)’=\frac{1}{1-x^2}$

  • $({\rm arccot}\ x)’=-\frac{1}{1-x^2}$

  • $({\rm sh}\ x)’={\rm ch}\ x$

  • $({\rm ch}\ x)’={\rm sh}\ x$

牛顿迭代

$\ \ \ \ \ \ \,$这里简单地讲一下 一阶牛顿迭代 ，牛顿迭代是应用在最优化领域非常重要的一种算法，由于具有二阶收敛性，所以相比二分法能大大降低迭代次数，只能求一个可导函数的零点，或者有二阶导函数的极值，一种全局搜索算法用来解np问题最优解的算法，在算法竞赛中的运用比较少见（Psyduck说）。

$\ \ \ \ \ \ \,$先放wiki的动图，牛顿迭代动态示例图：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CIMMV2UR-1644815019693)(https://upload.wikimedia.org/wikipedia/commons/e/e0/NewtonIteration_Ani.gif)]

$\ \ \ \ \ \ \,$容易看出一个重要问题：对函数的一个点做切线，这个切线与$x$轴的交点当做新的点，重复操作，得到的点就会越来越趋近于零点。

$\ \ \ \ \ \ \,$具体证明涉及 泰勒展开，就不细讲了。

$\ \ \ \ \ \ \,$说到函数切线，自然就需要求导。

$\ \ \ \ \ \ \,$在$\ f(x)\ $上，点$\ x=a\ $的斜率为$f’(a)$，所以这个切线与$x$轴的交点当做新的点，应该是$\ a-\frac{f\left(a\right)}{f’\left(a\right)}\ $。

$\ \ \ \ \ \ \,$所以，我们定义:
$F(x)=F(x-1)-\frac{f\left(F(x-1)\right)}{f’\left(F(x-1)\right)}$

$\ \ \ \ \ \ \,$也就是不断去求点，可得这个点是越来越趋近某一个零点的。也就是说，我们的答案，就是$\ F(+∞)\ $，既函数$\ F(x)\ $的收敛值。

$\ \ \ \ \ \ \,$若$f(x)$二阶可导，那么在待求的零点$\ F(+∞)\ $值周围存在一个区域，只要起始点$\ F(0)\ $位于这个邻近区域内，那么牛顿迭代必定收敛。

$\ \ \ \ \ \ \,$不过……我们显然不需要算无限次，保证精度在一个范围内就行了，显然，牛顿迭代可以做到极快收敛到我们需要的精度，我们并不需要计算太多次。

$\ \ \ \ \ \ \,$我们最终答案的计算效率、精度，还与迭代系数，也就是最初赋值的$\ F(0)\ $有很大关系。（但是因为比较小的x取值范围，本题没有卡迭代系数的选定）。

$\ \ \ \ \ \ \,$然后贴出一阶牛顿迭代的模板：

$\ \ \ \ \ \ \,$（如果迭代次数过少或者无解，那么会返回一个错误的答案）

1
2
3
4
double Newton_Iteration(double F,int tim){//输入迭代系数F=F(0)，迭代次数tim
  while(tim--)F=F-f(F)/f1(F);//f1(x)=f'(x)
  return F;
}

$\ \ \ \ \ \ \,$这里只是简单地讲一下 一阶牛顿迭代 ，具体的讲解，有兴趣可以戳下面的链接，博主觉得讲得很清晰 （还有互交动画啊XD） 。

—·—·—《推荐讲解文章》—·—·—

$\ \ \ \ \ \ \,$而对于 二阶牛顿迭代 呢，就是在一阶导数上面做 一阶牛顿迭代 ，求一阶导数上面的零点，就是求原函数的极值了，也就是下面这个函数的收敛值：

$F(x)=F(x-1)-\frac{f’\left(F(x-1)\right)}{f’’\left(F(x-1)\right)}$

$\ \ \ \ \ \ \,$例题在这里，是我出的:【P4986 逃离】【题解】