对多项式牛顿迭代算法的一些理解
Fuyuki
·
·
个人记录
求解一类多项式函数：
G(F(x))=0\pmod{x^n}
假设已知F_0(x)\equiv F(x)\pmod{x^{\lceil\frac{n}{2}\rceil}}，求F_1(x)\equiv F(x)\pmod{x^n}。
根据泰勒公式，在F_0(x)处展开G(F(x))。
G(F(x))=\sum_{i=0}^{\infty}\frac{G^{(i)}(F_0(x))}{i!}(F(x)-F_0(x))^i
可以发现，F(x)-F_0(x)\equiv 0\pmod{x^{\lceil\frac{n}{2}\rceil}}，所以(F(x)-F_0(x))^k\equiv 0\pmod{x^n}在k\geq2时成立。
因此：
G(F_1(x))\equiv G(F_0(x))+G(F_1(x))(F_1(x)-F_0(x))\pmod{x^n}
根据G(F_1(x))\equiv0\pmod{x^n}整理得：
F_1(x)=F_0(x)-\frac{G(F_0(x))}{G'(F_0(x))}\pmod{x^n}
这便是大家熟知的牛顿迭代公式。
但是，在将其推广到微分方程的时候，却会出现一些问题，比如G(F_0(x))关于F_0(x)求导时F_0'(x)这一项无法定义，所以难以计算。
于是，需要引进一些新的方法。
可以将任意方程转化为：
G(F(x))\equiv A(F(x))\pmod{x^n}
其中G(x)不含有求导以及积分的运算，而A(x)可以含有。
重复上述牛顿迭代的部分，在这一步停下：
G(F_1(x))\equiv G(F_0(x))+G(F_1(x))(F_1(x)-F_0(x))\pmod{x^n}
因为满足F(x)-F_0(x)\equiv 0\pmod{x^{\lceil\frac{n}{2}\rceil}}，所以推导到这一步是正确的。
这时，直接用A(F_1(x))替换G(F_1(x))：
F_1(x)=F_0(x)-\frac{G(F_0(x))-A(F_0(x))}{G'(F_0(x))}\pmod{x^n}
这样处理之后，依旧涉及到微分方程，但是可以发现除了微分的部分其余部分必定是线性的。
在这种情况下，存在一个基本解法：
已知C(x)，D(x)。求解：
F'(x)=C(x)F(x)+D(x)
构造U(x)，V(x)使得U'(x)=C(x)U(x)，V(x)=\frac{F(x)}{U(x)}。
计算U(x)：
\frac{U'(x)}{U(x)}=C(x)
\ln U(x)=\int C(x)dx\Longrightarrow U(x)=\exp(\int C(x)dx)
计算V(x)：
(U(x)V(x))'=C(x)U(x)V(x)+D(x)
U(x)V'(x)+U'(x)V(x)=U'(x)V(x)+D(x)
V'(x)=\frac{D(x)}{U(x)}\Longrightarrow V(x)=\int\frac{D(x)}{U(x)}dx
那么就可以使用F(x)=U(x)V(x)计算了。
对于其他形式的微分方程，可以将其转化为上述形式进行计算。
（什么时候遇到了含有高阶导的微分方程再来考虑高阶的部分吧）。