Остановка итерационного цикла по условию и возврат значения, соответствующего условию - PullRequest
Новая
       26

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

0 голосов
/ 19 мая 2019

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

Я просмотрел несколько сообщений в блоге и даже некоторые вопросыздесь, но я довольно новичок в 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 или что-то в этом роде, и при последней итерации функции Ньютонаon отстает от поля, функция iterate останавливается, и у меня есть окончательный результат

Ответы [ 3 ]

4 голосов
/ 19 мая 2019

Вариант ответа 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.Для этого мы используем стандартную хитрость архивирования списка с собственным хвостом..* Это дает нам бесконечный список пар, из которых мы отбрасываем элементы, пока разница между компонентами пары не станет достаточно маленькой.В этот момент мы извлекаем заголовок оставшегося списка (пару) и берем второй компонент.

1 голос
/ 19 мая 2019

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

0 голосов
/ 21 мая 2019

Получение 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 и отметить параллели.

...