多项式牛顿迭代
给定多项式 g ( x ) g(x) g(x)，求 f ( x ) f(x) f(x)，满足 g ( f ( x ) ) ≡ 0 ( m o d x n ) g(f(x)) \equiv 0 \pmod {x ^ n} g(f(x))≡0(modxn)。
泰勒展开
对于现有得 f ( x ) f(x) f(x)，构造一个多项式 g ( x ) g(x) g(x)，使得 f ( n ) ( x ) = g ( n ) ( x ) f^{(n)}(x) = g ^{(n)} (x) f(n)(x)=g(n)(x)，也就是两者得 n n n阶导数是相等的。
假设 g ( x ) = a 0 + a 1 x + a 2 x 2 + ⋯ + a n − 1 x n − 1 + a n x n g(x) = a_0 + a_1 x + a_2 x ^ 2 + \dots + a_{n - 1} x ^{n -1} + a_n x ^n g(x)=a0+a1x+a2x2+⋯+an−1xn−1+anxn
考虑通过 ( 0 , f ( 0 ) ) (0, f(0)) (0,f(0))来构造，显然有 g ( 0 ) = a 0 = f ( 0 ) g(0) = a_0 = f(0) g(0)=a0=f(0)，对任意阶倒数相同有 g ( n ) = n ! a n = f ( n ) ( 0 ) g ^{(n)} = n ! a_n = f ^{(n)}(0) g(n)=n!an=f(n)(0)，则 a n = f ( n ) ( 0 ) n ! a_n = \frac{f^{(n)}(0)}{n!} an=n!f(n)(0)
所以构造出 g ( x ) = f ( 0 ) + f ( 1 ) ( 0 ) 1 ! x + f ( 2 ) ( 0 ) 2 ! x 2 + ⋯ + f ( n − 1 ) ( 0 ) ( n − 1 ) ! x n − 1 + f ( n ) ( 0 ) n ! x n … g(x) = f(0) + \frac{f^{(1)}(0)}{1!} x + \frac{f^{(2)}(0)}{2!} x ^ 2 + \dots + \frac{f^{(n - 1)}(0)}{(n - 1) !} x^{n - 1} + \frac{f^{(n)}(0)}{n !} x ^ n \dots g(x)=f(0)+1!f(1)(0)x+2!f(2)(0)x2+⋯+(n−1)!f(n−1)(0)xn−1+n!f(n)(0)xn…
对于任意点 ( x 0 , f ( x 0 ) ) (x_0, f(x_0)) (x0,f(x0))，可得 g ( x ) = f ( 0 ) + f ( 1 ) ( 0 ) 1 ! ( x − x 0 ) + f ( 2 ) ( 0 ) 2 ! ( x − x 0 ) 2 + ⋯ + f ( n − 1 ) ( 0 ) ( n − 1 ) ! ( x − x 0 ) n − 1 + f ( n ) ( 0 ) n ! ( x − x 0 ) n … g(x) = f(0) + \frac{f^{(1)}(0)}{1!} (x - x_0) + \frac{f^{(2)}(0)}{2!} (x - x_0) ^ 2 + \dots + \frac{f^{(n - 1)}(0)}{(n - 1) !} (x - x_0)^{n - 1} + \frac{f^{(n)}(0)}{n !} (x - x_0) ^ n \dots g(x)=f(0)+1!f(1)(0)(x−x0)+2!f(2)(0)(x−x0)2+⋯+(n−1)!f(n−1)(0)(x−x0)n−1+n!f(n)(0)(x−x0)n…
牛顿迭代
迭代求函数零点
对于 f ( x ) f(x) f(x)，任意选取一个点 ( x 0 , f ( x 0 ) ) (x_0, f(x_0)) (x0,f(x0))作为当前我们预估的零点，取他的泰勒展开前两项 g ( x ) = f ( 0 ) + f ′ ( x ) ( x − x 0 ) g(x) = f(0) + f'(x)(x - x_0) g(x)=f(0)+f′(x)(x−x0)，
解出方程 g ( x ) = 0 g(x) = 0 g(x)=0，得到 x 1 x_1 x1，然后重复上述操作，最后 x n x_n xn会趋近于我们所要的正解。
考虑如何应用到多项式上
边界条件 n = 1 n = 1 n=1时， [ x 0 ] g ( f ( x ) ) = 0 [x ^0]g(f(x)) = 0 [x0]g(f(x))=0，的解单独求出。
假设我们已经求得膜
x
⌈
n
2
⌉
x ^{\lceil\frac{n}{2} \rceil}
x⌈2n⌉下的解
f
0
(
x
)
f_0(x)
f0(x)，要求膜
x
n
x ^n
xn下的解
f
(
x
)
f(x)
f(x)，得到该点的泰勒展开：
∑
i
=
0
∞
g
(
i
)
(
f
0
(
x
)
)
i
!
(
f
(
x
)
−
f
0
(
x
)
)
n
f
(
x
)
−
f
0
(
x
)
前
面
的
项
已
经
被
截
了
,
所
以
最
低
次
幂
是
大
于
⌈
n
2
⌉
的
有
(
f
(
x
)
−
f
0
(
x
)
)
i
≡
0
(
m
o
d
x
n
)
,
i
>
=
2
有
g
(
f
0
(
x
)
)
+
g
′
(
f
0
(
x
)
)
(
f
(
x
)
−
f
0
(
x
)
)
≡
0
(
m
o
d
x
n
)
f
(
x
)
≡
f
0
(
x
)
−
g
(
f
0
(
x
)
)
g
′
(
f
0
(
x
)
)
(
m
o
d
x
n
)
\sum_{i = 0} ^{\infty} \frac{g ^{(i)}(f_0(x))}{i !}(f(x) - f_0(x)) ^n\\ f(x) - f_0(x)前面的项已经被截了,所以最低次幂是大于\lceil \frac{n}{2} \rceil的\\ 有(f(x) - f_0 (x)) ^ i \equiv 0 \pmod {x ^ n}, i >= 2\\ 有g(f_0(x)) + g'(f_0(x))(f(x) - f_0(x)) \equiv 0 \pmod {x ^ n}\\ f(x) \equiv f_0(x) - \frac{g(f_0(x))}{g'(f_0(x))} \pmod {x ^ n}\\
i=0∑∞i!g(i)(f0(x))(f(x)−f0(x))nf(x)−f0(x)前面的项已经被截了,所以最低次幂是大于⌈2n⌉的有(f(x)−f0(x))i≡0(modxn),i>=2有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 ) ) = 1 f ( x ) − h ( x ) ≡ 0 ( m o d x n ) f ( x ) ≡ f 0 ( x ) − 1 f 0 ( x ) − h ( x ) − 1 f 0 2 ( x ) ( m o d x n ) f ( x ) ≡ 2 f 0 ( x ) − h ( x ) f 0 ( x ) ( m o d x n ) 对于给定的h(x)，\\ 有g(f(x)) = \frac{1}{f(x)} - h(x) \equiv 0 \pmod {x ^ n}\\ f(x) \equiv f_0(x) - \frac{\frac{1}{f_0(x)} - h(x)}{-\frac{1}{f_0 ^ 2(x)}} \pmod{x ^n}\\ f(x) \equiv 2f_0(x) - h(x) f_0(x) \pmod {x ^ n}\\ 对于给定的h(x)，有g(f(x))=f(x)1−h(x)≡0(modxn)f(x)≡f0(x)−−f02(x)1f0(x)1−h(x)(modxn)f(x)≡2f0(x)−h(x)f0(x)(modxn)
待补……
多项式开根
对 于 给 定 的 h ( x ) 有 g ( f ( x ) ) = f 2 ( x ) − h ( x ) ≡ 0 ( m o d x n ) f ( x ) ≡ f 0 ( x ) − f 0 2 ( x ) − h ( x ) 2 f 0 ( x ) ( m o d ( ) x n ) f ( x ) ≡ f 0 2 ( x ) + h ( x ) 2 f 0 ( x ) ( m o d x n ) f ( x ) ≡ 1 2 ( f 0 ( x ) + h ( x ) f 0 ( x ) ) ( m o d x n ) 对于给定的h(x)\\ 有g(f(x)) = f ^ 2(x) - h(x) \equiv 0 \pmod {x ^ n}\\ f(x) \equiv f_0(x) - \frac{f_0 ^2(x) - h(x)}{2f_0(x)} \pmod (x ^n)\\ f(x) \equiv \frac{f_0 ^ 2(x) + h(x)}{2f_0(x)} \pmod {x ^ n}\\ f(x) \equiv \frac{1}{2}(f_0(x) + \frac{h(x)}{f_0(x)}) \pmod {x ^n}\\ 对于给定的h(x)有g(f(x))=f2(x)−h(x)≡0(modxn)f(x)≡f0(x)−2f0(x)f02(x)−h(x)(mod()xn)f(x)≡2f0(x)f02(x)+h(x)(modxn)f(x)≡21(f0(x)+f0(x)h(x))(modxn)
待补……
多项式 exp \exp exp
对 于 给 定 的 h ( x ) 有 g ( f ( x ) ) = ln f ( x ) − h ( x ) ≡ 0 ( m o d x n ) f ( x ) ≡ f 0 ( x ) − ln f 0 ( x ) − h ( x ) 1 f 0 ( x ) ( m o d x n ) f ( x ) ≡ f 0 ( x ) ( 1 − ln f 0 ( x ) + h ( x ) ) ( m o d x n ) 对于给定的h(x)\\ 有g(f(x)) = \ln f(x) - h(x) \equiv 0 \pmod {x ^ n}\\ f(x) \equiv f_0(x) - \frac{\ln f_0(x) - h(x)}{\frac{1}{f_0(x)}} \pmod {x ^ n}\\ f(x) \equiv f_0(x)(1 - \ln f_0(x) + h(x)) \pmod {x ^ n}\\ 对于给定的h(x)有g(f(x))=lnf(x)−h(x)≡0(modxn)f(x)≡f0(x)−f0(x)1lnf0(x)−h(x)(modxn)f(x)≡f0(x)(1−lnf0(x)+h(x))(modxn)
待补……