牛顿迭代+泰勒展开+群论选讲

我就想写一个题,发现我要补三个知识点。。。

牛顿迭代

用于求解方程

示例

求解平方根,求解$x^2=5$,考虑这个怎么求,那么把这个东西看成一个函数$f(x)=x^2-5$

那么就是找$f(x)$当$f(x)=0$时$x$的取值,这个函数是一个抛物线,就是找他和$x$的焦点

先找到$2$,发现不是很准确,那么在$x=2$的位置对$f(x)$的图像做切线,和$x$轴产生交点

我们可以得到$x=2,y=4$,斜率$f'(x)=2x,f'(2)=4$,得到交点$x=2.25$

然后再次迭代,带入,做切线,找交点,计算$log$次得到近似解

那么考虑一般情况,就大概构造函数,找到他在$y=0$的近似解就好了

而且可以求解多项式...强悍如斯

牛顿迭代求解定义域为多项式的函数零点

上文说的牛顿迭代的过程是对于函数不断做切线快速求出一个函数的近似解

我们发现一些多项式可以由自己表示自己

大概长$F(x)=G(x)F(x)^2+A(x)$

这样的式子也可以移项转化成一个关于多项式的函数,求这个函数等于$0$,时候的解是多少

就是求得多项式过程了

过程大致一样,找切点,迭代求解

那么怎么找$f(F(x))$的零点

零点可能是个无穷次多项式,我们只需要前$n$项

定义$f(F(x))$是一个定义域是多项式的函数

$f(F(x))=F(x)^2-G(x)=0$

有了这个东西,就需要求解

首先$F(x)$是未知项,$G(x)$是常数项


------------


泰勒展开

公式

$f(x)=\sum_{i=0}\frac{f^{(i)}(x_0)}{i!}(x-x_0)^i$

这个就是能用导数求得原函数值

考虑倍增求解

假设求出了$G(x)$满足$f(G(x))=0 \ mod \ x^{\frac{n}{2}}$

大概就是找的一个解,带入原函数,求导,做切线,继续迭代

带入$f(F)$在$G$位置的泰勒展开,求导

$f(F)=\sum_{i=0}\frac{f^{(i)}(G)}{i!}(F-G)^i$

考虑对原式子泰勒展开,

多项式求逆告诉我们$(F-G)^2=0(mod\ x^n)$

那么$f(F)=f(G)+f'(G)(F-G)=0$

$F=G-\frac{f(G)}{f'(G)}$

首先显然的是,$G$已知,那么$G$就是在$mod \ x^{\frac{n}{2}}$的解,那么

------

$LOJ6538$烷基计数

考虑答案多项式$A(x)$,第$n$项系数就是个数为$n$的生成树的方案数

那么不考虑算重复的计数是$A(x)=1+x\times A(x)^3$

就是说儿子的所有方案相乘再右移一位

但是这样会出现空间同构的情况,那么考虑用群论找出本质相同的情况

所有的置换一共有$6=3!$种

由$Burnside$引理可知,不动点数量等于$\frac{1}{|S|}\sum_{i=1}^{|S|}$(当前置换的不动点数量)

那么这个系数就是对应的置换有几个,那么就显然了

那么最后的式子就是

$A(x)=1+x\times\frac{A(x)^3+3A(x^2)A(x)+2A(x^3)}{3!}$

那么对于这个式子,怎么求解

假设我们求出$G(x)=F(x)(mod \ x^{\frac{n}{2}})$

那么我们可以知道$F(x^2),F(x^3)$

为什么,因为这个选两个的话方案是一样的,只需要乘一次,那么现在选$2\times x$的方案数实际上是选$x$个的方案数

既然这样,这个式子已经知道$mod \ x^{\frac{n}{2}}$

那么可以知道$F(x^2),F(x^3)$,直接查系数就好了

设$F(x^2)=A,F(x^3)=B$

我们考虑牛顿迭代解

$f(F)=F-x\times\frac{F^3+3\times A\times  F+2\times B}{6}-1=0$

对于$F(x)$求导

$f'(F)=1-\frac{x}{6}(3F^2+3A)$

$f(F)=\sum_{i=1}\frac{f^{(i)}(G)}{i!}(F-G)^i$

$F=G-\frac{f(G)}{f'(G)}$

$F=G-\frac{G- \frac{x}{6}(G^3+3A*G+2B)-1}{1=\frac{x}{6}(3G^2+3A)}$

$F=\frac{\frac{x}{6}(2B-2G^2)+1}{1-\frac{x}{6}(3G^2+3A)}$

或许时间的差距无法弥补,那就尽自己最大努力就好啦,我希望省选完之后的我是无悔的。

或许再给我一次机会,我还会选$OI$,因为热爱,尽管可能不尽如人意,就是这样,赢要赢的漂漂亮亮,输要输的开开心心

$OI$,我仍怀着赤诚的心,我会努力到最后一刻的$!$