多项式——多项式函数

我们使用牛顿迭代法计算多项式函数。

多项式对数函数

对于函数 $\ln P(x)$ 来说：

$$(\ln P(x){)}^{\prime }=\frac{P^{\prime }(x)}{P(x)}$$

所以我们能在 $O(n\log n)$ 的时间内计算出 $\ln P(x)$ 。

多项式指数函数

已知 $e^{P(x)}=Q(x)$ ，那么 $\ln Q(x)=P(x)$ 即解 $F(Q)=\ln Q-P=0$ 。

根据牛顿迭代法 $F(Q)=\ln Q-P$ 并且 $F^{\prime }(Q)=\frac{1}{Q}$ 。带入牛顿迭代式得到：

$$Q_{k+1}=Q_k-(\ln Q_k-P)Q_k=Q_k(1+P-\ln Q_k)$$

多项式开根

已知 $\sqrt{P(x)}=Q(x)$ ，那么 $P(x)=Q(x{)}^2$ 即解 $F(Q)=Q^2-P=0$ 。

根据牛顿迭代法 $F(Q)=Q^2-P$ 并且 $F^{\prime }(Q)=2Q$ 。带入牛顿迭代式得到：

$$Q_{k+1}=Q_k-\frac{Q_k^2-P}{2Q_k}$$

多项式快速幂