0
votes

Arrêter une boucle d'itération par une condition et renvoyer la valeur qui correspond à la condition

J'essaie d'implémenter la méthode Newton-Raphson sur Haskell, et jusqu'à présent, j'ai réussi à la faire fonctionner en utilisant la fonction itérer , mais le problème est qu'elle renvoie une liste infinie en raison de la nature de la fonction d'itération, je cherche donc à trouver un moyen d'arrêter la boucle lorsque la valeur obtenue dans une itération tombe dans une marge d'erreur définie, et de renvoyer ladite valeur

J'ai regardé quelques articles de blog et même quelques questions ici, mais je suis assez nouveau dans haskell et je ne connais pas complètement la syntaxe, donc pour moi, lire des exemples de code ou de la documentation est vraiment difficile à présent.

Définitions de f (x) et g (x) (les dérivés) ne sont pas pertinents:

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

Je travaille actuellement en prenant les premiers éléments de la liste donnée, en utilisant take 4 $ newton 3.5 dans l'invite GHCi, mais la liste retournée par iterate est infinie, donc je ne peux pas utiliser de fonction de queue dessus.

Mon idée est de définir une constante quelque part, margin = 0,0001 ou quelque chose comme e à, et lorsque la dernière itération de la fonction newton tombe derrière la marge, la fonction itérer s'arrête, et j'ai le résultat final

haskell newtons-method

4 commentaires

Peut-être voulez-vous envisager takeWhile .

" la liste retournée par iterate est infinie, donc je ne peux pas utiliser une fonction de queue dessus. " Pourquoi pas? tail fonctionne très bien sur des listes infinies.

Note tangentielle: si vous souhaitez utiliser newton avec différentes fonctions et marges, il peut être utile de passer la marge f , g et comme arguments.

Que diriez-vous de la fonction jusqu'à ?

3 Réponses :

1
votes

Vous souhaitez tester des paires de valeurs consécutives générées par newton . Cela signifie que dropWhile du Prelude ne suffira pas, car il ne teste que des éléments individuels. À la place, vous pouvez utiliser quelque chose comme ceci dropWhileList de 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 vous donne le deuxième élément de la liste. Bien qu'il s'agisse d'une fonction partielle (elle échoue si la liste n'a pas de deuxième élément), elle est ici sûre à utiliser (comme iterate génère une liste infinie, vous aurez un résultat tant que la méthode de Newton converge).

0 commentaires

4
votes

Une variante de la réponse de duplode qui n'utilise que des fonctions standard:

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

Pour déterminer si notre objectif a été atteint, nous devons examiner les paires adjacentes d'éléments de la liste infinie produite par itérer . Pour ce faire, nous utilisons l'astuce standard consistant à compresser la liste avec sa propre queue. (Si vous vous sentez plus effronté, pensez à utiliser (zip tail) approxs au lieu de zip approxs (tail approxs) . De cette façon, vous n'êtes pas obligé de le faire. mentionner approxs deux fois dans l'expression, ce qui est certes un peu inutile.)

Cela nous donne une liste infinie de paires, à partir de laquelle nous supprimons des éléments jusqu'à la différence entre les composants d'un la paire devient assez petite. À ce stade, nous extrayons la tête de la liste restante (une paire) et prenons le deuxième composant.

1 commentaires

Je dirais que cette réponse est une nette amélioration: si "vous voulez tester des paires de valeurs consécutives", il vaut mieux tester littéralement paires de valeurs :)

0
votes

Reprenant la suggestion de oisdk d'utiliser jusqu'à ...

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

... pour une implémentation qui ne génère pas littéralement de liste:

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

Cela vaut la peine de comparer cela avec l'implémentation basée sur le zip de melpomene et en notant les parallèles.

0 commentaires