「多项式牛顿迭代」
前置知识
导数
微积分
基本问题
给定一个 (n) 次多项式 (F(x))，求多项式 (G(x)) 满足：
[F(G(x))equiv 0mod x^n ]
设有
[F(G_0(x))equiv 0mod x^n
]
根据泰勒展开得
[F(G(x))=sum^{infty}_{n=0}frac{F^{(n)}(G_0(x))(G(x)-G_0(x))^n}{n!}
]
[ecause F(G(x))equiv 0mod x^n
]
[ herefore sum^{infty}_{n=0}frac{F^{(n)}(G_0(x))(G(x)-G_0(x))^n}{n!} equiv 0mod x^n
]
由于 (G(x)) 是一个 (n) 次多项式，且是在 ((mod; x^n)) 的意义下，所以 (n=2) 以后的项都被模成了 (0) 。
[F(G_0(x))+F'(G_0(x))(G(x)-G_0(x)) equiv 0mod x^n
]
[F(G_0(x))+F'(G_0(x))G(x)-F'(G_0(x))G_0(x) equiv 0mod x^n
]
[F'(G_0(x))G(x)equiv F'(G_0(x))G_0(x) - F(G_0(x))mod x^n
]
[G(x)equiv G_0(x) - frac{F(G_0(x))}{F'(G_0(x))}mod x^n
]
解得
[G(x)equiv G_0(x) - frac{F(G_0(x))}{F'(G_0(x))}mod x^n
]