求助多项式牛顿迭代
  • 板块学术版
  • 楼主toolazy
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/10/22 22:29
  • 上次更新2024/10/23 10:19:04
查看原帖
求助多项式牛顿迭代
1033727
toolazy楼主2024/10/22 22:29

上 OI-wiki 学习多项式牛顿迭代,突然感觉很奇怪:

x=xΔx=xf(x)f(x)x^*=x-\Delta x=x-\frac{f(x)}{f'(x)}

这就是 Newton's Method 的迭代式。非常感性地,我们直接把 xx 换成多项式:

f(x)=f(x)g(f(x))g(f(x))f^*(x)=f(x)-\frac{g(f(x))}{g'(f(x))}

感觉这个换元有点抽象了(

不过我的问题不在这里,关键是接下来有一个多项式求逆的例子:

g(f(x))=1f(x)h(x)g(f(x))=\frac 1{f(x)}-h(x)

求得 ff 使 g(f(x))=0g(f(x))=0ffhh 的逆。

接下来套式子(直接摘自 OI-wiki):

f(x)=f(x)g(f(x))g(f(x))=f(x)1f(x)h(x)1f2(x)f^*(x)=f(x)-\frac{g(f(x))}{g'(f(x))}=f(x)-\frac{\frac1{f(x)}-h(x)}{\frac1{f^2(x)}}

what?为什么 g(f(x))g'(f(x)) 会是这个东西?以我(也许并不扎实的)理解:

g(f(x))=1f(x)h(x)g(x)=1xh(f1(x))g(f(x))=\frac 1{f(x)}-h(x)\Rightarrow g(x)=\frac 1x-h(f^{-1}(x))

其中 f1f^{-1}ff 的反函数,即 f1f=ff1=idf^{-1}\circ f=f\circ f^{-1}=\text{id}\circ 是多项式复合。

咳咳,接下来求导:

g(x)=1x2h(f1(x))[f1(x)]=1x2h(f1(x))1f(f1(x))g'(x)=-\frac 1{x^2}-h'(f^{-1}(x))\cdot [f^{-1}(x)]'=-\frac 1{x^2}-h'(f^{-1}(x))\cdot\frac 1{f'(f^{-1}(x))}

接下来再代回来:

g(f(x))=1f2(x)h(f1(f(x)))f(f1(f(x)))=1f2(x)h(x)f(x)g'(f(x))=-\frac 1{f^2(x)}-\frac{h'(f^{-1}(f(x)))}{f'(f^{-1}(f(x)))}=-\frac1{f^2(x)}-\frac{h'(x)}{f'(x)}

这这和上面完全不一样啊!这 h(x)h(x) 不导了吗?!

2024/10/22 22:29
加载中...