如何知道牛顿的方法何时会失败使用Haskell？

Question

在Haskell中,我使用以下函数来查找多项式的根:

polyNewton :: (Fractional a, Ord a) => Poly a -> a -> a`

polyNewton p s = if (abs(polyValue p s) <= (0 + 1e-10)) then s else polyNewton 
p (s - (polyValue p s) / (polyValue (polyDeriv p) s))

其中polyValue是一个函数,它找到多项式p的y值,x值x,而polyDeriv是一个返回多项式p的导数的函数.

对于大多数情况,此代码非常有效,除非多项式没有任何实际根(函数在x轴上方)或者给出了错误的初始猜测.无论如何确定牛顿的方法是否会事先失败,以便我的函数不会无限期地运行？

Answer 1

要大致确定N次多项式的根源 - 如果有的话 - 知道它的所有极值就足够了,因为你必须只有一个根

• 在任何相邻的负最小值和正最大值之间
• 在最左边的极值的左边,如果它是负的最小值或正的最大值
• 在最右边的极值的右边,如果它是负的最小值或正的最大值

极值本身就是导数的根,它很方便地是一个N -1 的多项式,所以你可以递归地向下走,直到你得到线性(或二次)的情况,在这种情况下找到根是很简单的(事实上,确实如此) ).