HOROWITZ

时间：2020-01-16 23:20:19 阅读：69 评论：0 收藏：0 [点我收藏+]

Horowitz-Ostrogradsky方法

Hermite方法避免了完全分解，但仍要求无平方分解和关于 $技术分享图片$ 的部分分式分解。Horowitz-Ostrogradsky方法则不需要其他工具，通过待定系数法将问题归结为线性方程的求解问题。

设 $技术分享图片$ 其中 $技术分享图片$ 为积分的有理部分，由部分分式的结果可知 $技术分享图片$ ， $技术分享图片$ 。求导得到 $技术分享图片$ 从而问题归结为求 $技术分享图片$ ， $技术分享图片$ 满足 $技术分享图片$ 且 $技术分享图片$ ， $技术分享图片$ 。以 $技术分享图片$ ， $技术分享图片$ 的系数作为未知变量，这是一个至多 $技术分享图片$ 维的线性方程组问题。

注1 设 $技术分享图片$ ，则Hermite方法的时间复杂度为 $技术分享图片$ [3]，其中 $技术分享图片$ 为乘法的复杂度。而Horowitz-Ostrogradsky方法的复杂度为 $技术分享图片$ （解线性方程组），尽管渐进意义上后者要比前者慢将近两个量级，但在实践中还是要分析具体情况而定。

Rothstein-Trager方法

下面的问题是如何求出对数部分，因此我们设 $技术分享图片$ 无平方因子的首一多项式，并可设 $技术分享图片$ 其中 $技术分享图片$ 为互不相同的常数， $技术分享图片$ 为无平方因子的首一多项式，两两互素（可以通过合并项来满足这些条件）。求导得到 $技术分享图片$ 由于 $技术分享图片$ 无平方因子且两两互素可知 $技术分享图片$ 记 $技术分享图片$ ，则有 $技术分享图片$ 及 $技术分享图片$ 于是对于 $技术分享图片$ $技术分享图片$ 最后一个等式成立是因为 $技术分享图片$ 从而 $技术分享图片$

由式(3)可以看出，当我们找出系数 $技术分享图片$ 后即可通过最大公因子的计算求出 $技术分享图片$ 。如何求出 $技术分享图片$ 呢？同样的论证可以知道 $技术分享图片$ ，而 $技术分享图片$ （此结式称为Rothstein-Trager结式），故求解关于 $技术分享图片$ 的方程 $技术分享图片$ 即可得到所有的系数 $技术分享图片$ 。