按条件停止迭代循环并返回与条件匹配的值

Question

我正在尝试在 Haskell 上实现 Newton-Raphson 方法，到目前为止，我已经设法通过使用 iterate 函数让它工作，但问题是它会重新调整由于迭代函数的性质，一个无限列表，所以我正在寻找一种方法，当迭代中获得的值落入设定的误差范围内时停止循环，并返回所述值

我在这里看了一些博客文章，甚至还有一些问题，但我对 haskell 还很陌生，对语法并不完全精通，所以对我来说，阅读代码示例或文档现在真的很难.

f(x) 和 g(x)（导数）的定义无关紧要：

newton x0 = iterate step x0
    where step xn = xn - ((f xn)/(g xn))

我目前正在使用 GHCi 提示符中的 take 4 $ newton 3.5 获取给定列表的第一个元素，但是 iterate 返回的列表是无限的，所以我不能使用尾部在其上运行。

我的想法是在某处设置一个常量，margin = 0.0001或类似的东西，当牛顿函数的最后一次迭代落后于边际时，iterate函数停止，我有最终结果

Answer 1

您想测试 newton 生成的连续值对。这意味着 Prelude 中的 dropWhile 还不够，因为它只测试单个元素。相反，您可以使用 MissingH:

中的类似 dropWhileList

newton :: Double -> Double
newton x0 = dropWhileList (not . goal) (iterate step x0) !! 1
    where
    step xn = xn - ((f xn)/(g xn))
    goal (xa:xb:_) = abs (xb - xa) < margin
    goal _ = False

!! 1 给你列表的第二个元素。虽然它是一个部分函数（如果列表没有第二个元素，它会失败），但在这里使用它是安全的（因为 iterate 生成一个无限列表，只要牛顿法你就会得到一个结果收敛）。

Answer 2

仅使用标准函数的 duplode 答案的变体：

newton :: Double -> Double
newton x0 = (snd . head . dropWhile (not . goal)) (zip approxs (tail approxs)) 
    where
    approxs = iterate step x0
    step xn = xn - (f xn / g xn)
    goal (xa, xb) = abs (xb - xa) < margin

为了确定我们的目标是否已经达到，我们需要检查 iterate 生成的无限列表的相邻元素对。为此，我们使用了标准技巧，即用自己的尾巴压缩列表。（如果你觉得特别厚颜无耻，可以考虑使用 (zip <*> tail) approxs 而不是 zip approxs (tail approxs)。这样你就不必在表达式中两次提到 approxs，这确实有点毫无意义。 )

这给了我们一个无限的对列表，我们从中删除元素，直到一对组件之间的差异变得足够小。那时我们提取剩余列表（一对）的头部并获取第二个组件。

Answer 3

正在取货oisdk's suggestion of using until...

until :: (a -> Bool) -> (a -> a) -> a -> a

...对于不直接生成列表的实现：

newton :: Double -> Double
newton = snd . until goal (move . snd) . move
    where
    step xn = xn - (f xn)/(g xn)
    move xn = (xn, step xn) -- The cheeky spelling is (,) <*> step
    goal (xa,xb) = abs (xb - xa) < margin

值得将其与进行比较并注意相似之处。

按条件停止迭代循环并返回与条件匹配的值

Stopping an iterate loop by a condition and returning the value that matched the condition

haskell

newtons-method