Останов цикла итерации по условию и возврат значения, которое соответствует условию

Я пытаюсь реализовать метод Ньютона-Рафсона на Haskell, и до сих пор мне удавалось заставить его работать с помощью функции iterate, но проблема в том, что он повторно настраивает бесконечный список из-за характера функции итерации, поэтому я Я ищу способ остановить цикл, когда значение, полученное в итерации, попадает в заданную погрешность и возвращает указанное значение

Я просмотрел некоторые сообщения в блогах и даже некоторые вопросы здесь, но я довольно новичок в haskell и не полностью разбираюсь в синтаксисе, поэтому для меня сейчас очень сложно читать примеры кода или документацию.

Определения f(x) и g(x) (производной) не имеют значения:

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

В настоящее время я работаю, беря первые элементы заданного списка, используя take 4 $ newton 3.5 в приглашении GHCi, но список, возвращаемый iterate, бесконечен, поэтому я не могу использовать для него хвостовую функцию.

Моя идея состоит в том, чтобы установить где-то константу, margin = 0.0001 или что-то в этом роде, и когда последняя итерация функции newton отстает от поля, функция iterate останавливается, и у меня есть окончательный результат


haskell newtons-method
person MasterGeekMX    schedule 18.05.2019    source источник
comment
Может быть, вы хотите рассмотреть takeWhile.   -  person n. 1.8e9-where's-my-share m.    schedule 19.05.2019
comment
список, возвращаемый iterate, бесконечен, поэтому я не могу использовать для него хвостовую функцию. Почему бы и нет? tail отлично работает с бесконечными списками.   -  person melpomene    schedule 19.05.2019
comment
Дополнительное примечание: если вы хотите использовать newton с другими функциями и полями, вам может быть полезно передать f, g и margin в качестве аргументов.   -  person duplode    schedule 19.05.2019
comment
Как насчет функции until?   -  person oisdk    schedule 19.05.2019

Ответы (3)


arrow_upward
4
arrow_downward

Вариант ответа 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 в выражении, что, по общему признанию, немного бессмысленно.)

Это дает нам бесконечный список пар, из которого мы удаляем элементы до тех пор, пока разница между компонентами пары не станет достаточно малой. В этот момент мы извлекаем голову оставшегося списка (пара) и берем второй компонент.

person melpomene    schedule 18.05.2019
comment
Я бы сказал, что этот ответ является определенным улучшением: если вы хотите протестировать пары последовательных значений, вам лучше буквально тестировать пары значений :) - person duplode; 19.05.2019

arrow_upward
1
arrow_downward

Вы хотите протестировать пары последовательных значений, сгенерированных newton. Это означает, что dropWhile из Prelude будет недостаточно, так как он проверяет только отдельные элементы. Вместо этого вы можете использовать что-то вроде этого dropWhileList от MissingH:

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 генерирует бесконечный список, у вас будет результат, пока метод Ньютона сходится).

person duplode    schedule 18.05.2019

arrow_upward
0
arrow_downward

Принимая предложение oisdk об использовании 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

Стоит сравнить это с реализацией zip на основе melpomene и отметить параллели.

person Community    schedule 20.05.2019