上 OI-wiki 学习多项式牛顿迭代,突然感觉很奇怪:
x∗=x−Δx=x−f′(x)f(x)
这就是 Newton's Method 的迭代式。非常感性地,我们直接把 x 换成多项式:
f∗(x)=f(x)−g′(f(x))g(f(x))
感觉这个换元有点抽象了(
不过我的问题不在这里,关键是接下来有一个多项式求逆的例子:
g(f(x))=f(x)1−h(x)
求得 f 使 g(f(x))=0 则 f 为 h 的逆。
接下来套式子(直接摘自 OI-wiki):
f∗(x)=f(x)−g′(f(x))g(f(x))=f(x)−f2(x)1f(x)1−h(x)
what?为什么 g′(f(x)) 会是这个东西?以我(也许并不扎实的)理解:
g(f(x))=f(x)1−h(x)⇒g(x)=x1−h(f−1(x))
其中 f−1 是 f 的反函数,即 f−1∘f=f∘f−1=id,∘ 是多项式复合。
咳咳,接下来求导:
g′(x)=−x21−h′(f−1(x))⋅[f−1(x)]′=−x21−h′(f−1(x))⋅f′(f−1(x))1
接下来再代回来:
g′(f(x))=−f2(x)1−f′(f−1(f(x)))h′(f−1(f(x)))=−f2(x)1−f′(x)h′(x)
这这和上面完全不一样啊!这 h(x) 不导了吗?!