求助,关于多项式牛顿迭代法
  • 板块学术版
  • 楼主Daniel_yuan
  • 当前回复4
  • 已保存回复4
  • 发布时间2020/7/23 17:13
  • 上次更新2023/11/6 22:30:09
查看原帖
求助,关于多项式牛顿迭代法
71955
Daniel_yuan楼主2020/7/23 17:13

最近学习了多项式的牛顿迭代法,在尝试推 exp 的时候用了一个比较奇怪的操作:

假设需要求 AA 的 exp,设 B=eAB=e^A,那么就有 lnBA0 ( mod xn)\ln B-A\equiv 0~(~{\rm{mod}}~x^n)。假设现在已经求出了 lnB0A0 ( mod xn2)\ln B_0-A\equiv 0~(~{\rm{mod}}~x^\frac{n}{2}),考虑用 B0B_0 推出 BB

lnB\ln B 牛顿迭代,那么就有 lnB=lnB0+lnB0(BB0)+lnB0(BB0)22...\ln B=\ln B_0+\ln' B_0\cdot(B-B_0)+\frac{\ln'' B_0\cdot(B-B_0)^2}{2}...,然后对 xnx^n 取模,就有 lnBlnB0+lnB0(BB0) ( mod xn)\ln B\equiv\ln B_0+\ln' B_0\cdot(B-B_0)~(~{\rm{mod}}~x^n),带回原式,就有 lnB0+lnB0(BB0)A ( mod xn) \ln B_0+\ln' B_0\cdot(B-B_0)-A\equiv~(~{\rm{mod}}~x^n)。因为 lnx=1x\ln' x=\frac{1}{x},所以就得到了 BB0(A+1lnB0) ( mod xn)B\equiv B_0\cdot(A+1-\ln B_0)~(~{\rm{mod}}~x^n)

然后就这样得到了 exp 的递推式,而且还是对的……

并且在这样得到正确的递推式之后,尝试着把它用去求逆,也就是设 B=A1B=A^{-1},那么 1BA=0\frac{1}{B}-A=0,然后求出 B0B_0 后对 1B\frac{1}{B} 进行牛顿迭代,最后也可以得到多项式求逆的正确递推式。

虽然这样可以得到正确结果,但是感觉很奇怪,因为好像网上大多是对 lnBA=0\ln B-A=0 这个整体进行牛顿迭代的,也不知道我的做法的正确性,故向各位神犇求助。

感激不尽!!!

2020/7/23 17:13
加载中...