3
多项式牛顿迭代
source link: https://xiaocairush.github.io/math/poly/newton/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
多项式牛顿迭代
描述¶
给定多项式 g(x)，已知有 f(x) 满足：
g(f(x))≡0(modxn)
求出模 xn 意义下的 f(x)。
Newton's Method¶
考虑倍增。
首先当 n=1 时，[x0]g(f(x))=0 的解需要单独求出。
假设现在已经得到了模 x⌈n2⌉ 意义下的解 f0(x)，要求模 xn 意义下的解 f(x)。
将 g(f(x)) 在 f0(x) 处进行泰勒展开，有：
∑i=0+∞g(i)(f0(x))i!(f(x)−f0(x))i≡0(modxn)
因为 f(x)−f0(x) 的最低非零项次数最低为 ⌈n2⌉，故有：
∀2⩽i:(f(x)−f0(x))i≡0(modxn)
∑i=0+∞g(i)(f0(x))i!(f(x)−f0(x))i≡g(f0(x))+g′(f0(x))(f(x)−f0(x))≡0(modxn)
f(x)≡f0(x)−g(f0(x))g′(f0(x))(modxn)
例题¶
多项式求逆¶
设给定函数为 h(x)，有方程：
g(f(x))=1f(x)−h(x)≡0(modxn)
应用 Newton's Method 可得：
f(x)≡f0(x)−1f0(x)−h(x)−1f02(x)(modxn)≡2f0(x)−f02(x)h(x)(modxn)
时间复杂度
T(n)=T(n2)+O(nlogn)=O(nlogn)
多项式开方¶
设给定函数为 h(x)，有方程：
g(f(x))=f2(x)−h(x)≡0(modxn)
应用 Newton's Method 可得：
f(x)≡f0(x)−f02(x)−h(x)2f0(x)(modxn)≡f02(x)+h(x)2f0(x)(modxn)
时间复杂度
T(n)=T(n2)+O(nlogn)=O(nlogn)
多项式 exp¶
设给定函数为 h(x)，有方程：
g(f(x))=lnf(x)−h(x)(modxn)
应用 Newton's Method 可得：
f(x)≡f0(x)−lnf0(x)−h(x)1f0(x)(modxn)≡f0(x)(1−lnf0(x)+h(x))(modxn)
时间复杂度
T(n)=T(n2)+O(nlogn)=O(nlogn)
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK